Introduction

Why is this important?

In this application you will design a single player turn based game where the player is required to block the path of an A.I. controlled cat by selecting tiles around the cat. If the player blocks the path of the cat, they win but if the cat escapes off the board, you lose.

This game helps give an introduction to turn based games where one of the participants is an A.I.

For reference, a copy of the game can be found here: Chat Noir

Assumptions

We assume that you have recently completed the Rock, Paper, Scissors tutorial.
We assume that you have already installed reach, if not refer to the Reach > Rock, Paper, Scissors!
We assume you are using the console for the frontend of the application.
We assume that you have installed the Reach lib npm package. If not refer to the Reach > Rock, Paper, Scissors! tutorial.
We assume that we are working in a folder called le-chat-noir.

Learning outcomes

After this workshop you should be able to:

Make a turn based application.
Add artificial intelligence to your game.

Problem analysis

Here we think through the problem before we start implementing it. This is important because it’s easier to come up with the application after we understand what it does.

Questions to ask ourselves

Which participants are involved?
What functions do each of the participants perform?
Is there any shared functionality?
Do we have some defaults?

You can go ahead and think about these then write your answers in the form of comments inside your index.rsh file.

When you are ready you can look at our answers for reference. Remember that multiple answers can be correct, you do not have to have exactly what we have.

Our answers

Participants involved

Functions performed by each of the participants

Alice:

Bob:

Functions shared by participants

The defaults

Representing the game state

Now that we know the participants and what they need to do, let’s figure out how to represent our game state, that is, the game board and the cat position. Considering that the game is made up of a 9 x 9 board, think of a way we can represent all the board tiles and their state.

Our answers

We have two options here, we either represent the board as a grid (2 dimensional array) of booleans as shown below:

Or we can represent the board as an array of booleans of size 81. We use booleans to represent if the player has clicked it or not.

Notice that we added 4 more positions on the outside of the board, their use will be explained in the checks part. Do not consider them right now.

The choice of how the game board is represented doesn’t change much in our program apart from how the algorithm for the cat movement is implemented and the checks on the game state.

We went ahead and used the option where we use one array of size 81.

We represent the cat position as an unsigned integer.

Checks

What checks do we have to implement based on the game play?

Our answers

There are three checks needed, one for when the cat is trapped, one for when the cat is blocked and a check to know if the game is over.

We could check all the tiles on the edge of the board to know that the cat is off the board but an easier way is to connect all the edges on one side of the board to a new imaginary position shown as 81, 82, 83 and 84 in the board representation diagram shown above. And check if the cat is on one of those instead.

Program flow

Based on the demo of the game, how should the game play out? Write out the flow you think is right.

Our answers

Assertions

There are some things we know that have to be true for the program to continue. These checks help make sure that no weird scenario happens in the program. In this case we use 3 statements, require, assert and assume when we are sure of an outcome to happen. They vary in their uses as can be seen here: Check: Check Assert: Assert

What things must be true for the program to continue at a point?

Our answers

We know that the game must be over for us to continue on to paying out the participants. The winner must be either the cat or the player.

We also know that all the board tiles clicked on the frontend should be less than 81 based on our game board structure.

Interactions

We have the following questions to answer: How do we represent the board? How do we implement the cat movement in the frontend?

Our answers

Representing the board.

Given that we are running the application from our consoles we have to come up with a way to see the movements being made by both the cat and the player. We can do this with the use of a helper function that takes in the board array and iterates through it while displaying free and blank positions based on the value of that index to the console as well as the current position of the cat. Again, depending on which option you chose at Representing the game state, this may defer. We chose the second option so this is our function:

And this is the output:

Implementing cat movement

So let’s stop and ask ourselves a few questions, how will the cat know where to move next? How will the cat make sure to avoid obstacles in its path? This is where we need to come up with an artificial intelligence of sorts.

There are many algorithms that could help with this such as the A* algorithm but in this case we go for a simpler approach and we select a random number from an array of possible moves to add to the current position of the cat to get the new position.

The trick here is to identify that if the cat is away from the edge, it has 8 possible moves; otherwise if it lands on the edge of the board, it should move off the board represented by the positions of 81, 82, 83 and 84 in our board diagram. (Refer back to it for clarity).

You can check out the implementation below.

Things to consider

Remember when it comes to getting the new position of the player we need to wait until the user actually returns a response. This is one of the more challenging aspects of this application. Try to think of a way to fix this.

Our answers

Using promises will help you solve this, as opposed to immediately returning something in the function that gets the player position, we wait for a promise to resolve with the value of the tile clicked and return that value. This is already included in the Reach library for you via the ask function. So we used that.

We imported the ask function.

And used it to get the position from the user as below.

Don’t forget to add this ask.done( ) to the end of your file to let the app know you will not be asking anymore questions. If we do not add this the app will hang at the end.

All together now

Our Reach backend

"reach 0.1";

const gameBoard = Array(Bool, 81);
const cat_move = UInt;
const [isOutcome, PLAYER_WINS, CAT_WINS] = makeEnum(2);
const state = Object({ "0": gameBoard, "1": UInt });

// Checks

// Cat escaped check
// Check the position of the cat that it is not on one of the tiles on positions 81, 82, 83 or 84.
const catOffBoard = (cat_position) =>
  cat_position === 81 ||
  cat_position === 82 ||
  cat_position === 83 ||
  cat_position === 84;

// Cat trapped check
// Check all surrounding tiles to see if the cat is surrounded.
const catTrapped = (board, cat_position) => {
  if((cat_position < 71) && (cat_position > 9)){

    const p0 = board[cat_position + 10];
    const p1 = board[cat_position + 9];
    const p2 = board[cat_position + 8];
    const p3 = board[cat_position - 10];
    const p4 = board[cat_position - 9];
    const p5 = board[cat_position - 8];
    const p6 = board[cat_position + 1];
    const p7 = board[cat_position - 1];
    return p0 && p1 && p2 && p3 && p4 && p5 && p6 && p7;
  }else{
    return false;
  }

};

// Game over
// We know the game is over if the cat has escaped or the cat is trapped.
const gameCheck = (board, cat_position) =>
  catOffBoard(cat_position) || catTrapped(board, cat_position);

const Player = {
  // See the outcome
  seeOutcome: Fun([UInt], Null),
  // Inform timeout
  informTimeout: Fun([], Null),
  // Logging function
  log: Fun(true, Null),
};

export const main = Reach.App(() => {
  // Alice will be the Cat in this case
  const Alice = Participant("Alice", {
    ...Player,
    // Get cat move
    getNode: Fun([gameBoard, cat_move], UInt),
    // Update cat position on board
    updateCatPosition: Fun([UInt], Null),
    // Initialize the game board
    initGameBoard: Fun([], gameBoard),
  });

  // Bob will be the other player
  const Bob = Participant("Bob", {
    ...Player,
    // Get player move
    getPosition: Fun([], UInt),
    // Accept Wager
    acceptWager: Fun([UInt], Null),
    // Update game board with new player position
    updateBoard: Fun([gameBoard], Null),
  });

  init();

  const informTimeout = () => {
    each([Alice, Bob], () => {
      interact.informTimeout();
    });
  };

  Alice.only(() => {
    // Generate random position to move first, since the cat starts at the center
    // It will always be 40
    const randomizedBoard = declassify(interact.initGameBoard());

    /* We can also set the wager to make sure someone advanced
      at the game doesn’t place a *high wager and take all the funds we have. */
    const wager = 1;

    // We also need to set the deadline
    const deadline = 10;

    // We know from the demo game that the cat always starts from the center
    const start_cat_position = 40;
  });

  Alice.publish(wager, deadline, start_cat_position, randomizedBoard).pay(
    wager
  );
  commit();

  Bob.only(() => {
    interact.acceptWager(wager);
  });

  // The second one to publish always attaches
  Bob.pay(wager)
    .timeout(relativeTime(deadline), () => closeTo(Alice, informTimeout));

  var [board, cat_position] = [randomizedBoard, start_cat_position];

  invariant((balance() == 2 * wager));

  while (
    gameCheck(
      board,
      cat_position
    ) === false
  ) {
    commit();

    Alice.only(() => {
      const new_cat_position = declassify(
        interact
        .getNode(board, cat_position)
      );
      interact.updateCatPosition(new_cat_position);
    });
    Alice.publish(new_cat_position);
    commit();

    const updated_cat_position = new_cat_position;

    Bob.only(() => {
      const position = declassify(interact.getPosition());
      assume(position < 81);
    });
    Bob.publish(position);
    commit();

    Bob.only(() => {
      assume(position < 81);
      const newBoardState = board.set(position, true);
      interact.updateBoard(newBoardState);
    });
    Bob.publish(newBoardState);

    [board, cat_position] = [newBoardState, updated_cat_position];
    continue;
  }

  assert(
    gameCheck(
      board,
      cat_position
    ) === true
  );

  const [toAlice, toBob] = catOffBoard(cat_position)
    ? [2, 0]
    : [0, 2];

  transfer(toAlice * wager).to(Alice);
  transfer(toBob * wager).to(Bob);
  commit();

  each([Alice, Bob], () => {
    interact.seeOutcome(
      catOffBoard(cat_position)? 1: 0
    );
  });

  exit();
});

Our JavaScript Frontend

import { loadStdlib, ask } from "@reach-sh/stdlib";
import * as backend from "./build/index.main.mjs";
const stdlib = loadStdlib(process.env);

const startingBalance = stdlib.parseCurrency(100);

const [accAlice, accBob] = await stdlib.newTestAccounts(2, startingBalance);

const ctcAlice = accAlice.contract(backend);
const ctcBob = accBob.contract(backend, ctcAlice.getInfo());

// Representing the game state
let cat_position = 40;
let board = Array(81).fill(false);

// Function to print the board to the console
const showBoard = (arr) => {
  console.log();
  for (let i = 0; i < 9; i++) {
    // Holds the contents of a single line
    let line = "";
    for (let j = 0; j < 9; j++) {
      if (j % 9 === true) {
        break;
      } else {
        // This shows the position of the tile in front of the tile for example 0:
        let placeHolder = "";

        // Check if the position is less than 10
        if (i * 9 + j < 10) {
          // We add a space to the beginning of the placeholder to make the output look neat
          placeHolder = ` ${i * 9 + j}:`;
        } else {
          placeHolder = `${i * 9 + j}:`;
        }

        if (i * 9 + j === cat_position) {
          // Add a cat emoji
          line += placeHolder + "🐱 ";
        } else {
          if (arr[i * 9 + j] === true) {
            // Add a blocked emoji
            line += placeHolder + "❌ ";
          } else {
            // Add a free space emoji
            line += placeHolder + "🔵 ";
          }
        }
      }
    }
    console.log(line);
  }
  console.log();
};

const Player = (who) => ({
  seeOutcome: (winner) => {
    // Array of outcomes
    const outcome = ["Player Wins", "Cat Wins"];
    const parsed_winner = parseInt(winner._hex, 16);
    console.log(outcome[parsed_winner]);
  },
  informTimeout: () => {
    console.log(`${who} took too long to play`);
  },
  log: (info) => {
    console.log(info);
  },
});

await Promise.all([
  backend.Alice(ctcAlice, {
    ...stdlib.hasRandom,
    ...Player("Alice"),
    // implement Alice's interact object here

    // getNode: Fun([gameBoard, cat_move], UInt),
    getNode: (board, cat_position) => {
      console.log("Cat making a move...");
      // We parse the cat position we get from the backend to convert it to decimal
      const parsed_cat_position = parseInt(cat_position._hex, 16);
      // Return the new position for the cat
      let movement_array = [];
      switch (parsed_cat_position) {
        // Case1: Cat is in the corners
        case 0:
          movement_array = [83, 82];
          break;
        case 8:
          movement_array = [75, 76];
          break;
        case 72:
          movement_array = [9, 10];
          break;
        case 80:
          movement_array = [1, 4];
          break;

        // Case2: Cat is at the left most column
        case 9:
        case 18:
        case 27:
        case 36:
        case 45:
        case 54:
        case 63:
          movement_array = [82 - parsed_cat_position];
          break;

        // Case3: Cat is at the right most column
        case 17:
        case 26:
        case 35:
        case 44:
        case 53:
        case 62:
        case 71:
          movement_array = [84 - parsed_cat_position];
          break;

        // Case4: Cat is at the top most column
        case 1:
        case 2:
        case 3:
        case 4:
        case 5:
        case 6:
        case 7:
          movement_array = [83 - parsed_cat_position];
          break;

        // Case5: Cat is at the bottom most column
        case 73:
        case 74:
        case 75:
        case 76:
        case 77:
        case 78:
        case 79:
          movement_array = [81 - parsed_cat_position];
          break;

        // Case6: Cat is away from the edge of the grid (8 positions)
        default:
          movement_array = [10, 9, 8, 1, -1, -10, -9, -8];
      }

      let new_position = 0;
      do {
        let step =
          movement_array[Math.floor(
Math.random() * movement_array.length)];
        new_position = parsed_cat_position + step;
      } while (
        new_position < 0 ||
        new_position > 84 ||
        board[new_position] === true
      );

      return new_position;
    },

    // updateCatPosition: Fun([UInt], Null),
    updateCatPosition: (newPosition) => {
      cat_position = parseInt(newPosition._hex, 16);
      console.log("New Cat position: ", cat_position);
      // Print the board to the screen
      showBoard(board);
    },

    // initGameBoard: Fun([], gameBoard),
    initGameBoard: () => {
      const gameState = (function () {
        let arr = Array(81).fill(false);
        // Block a random number of tiles between 10 and 4
        for (let i = 0; i < Math.floor(Math.random() * (10 - 4) + 4); i++) {
          let index = 0;
          do {
            index = Math.floor(Math.random() * 81);
          } while (arr[index] === true || index === 40);
          arr[index] = true;
        }
        return arr;
      })();
      board = gameState;
      console.log("### Initialized Board ###\n");
      // Print the board to the screen
      showBoard(board);
      return gameState;
    },
  }),
  backend.Bob(ctcBob, {
    ...stdlib.hasRandom,
    ...Player("Bob"),
    // implement Bob's interact object here

    // getPosition: Fun([], UInt),
    getPosition: async() => {
      let newPosition = 0;
        do{
          // Ask user to enter a position to block
          newPosition = await ask.ask('Enter a new position (0 - 80): ', parseInt);

        }while(board[newPosition] === true || cat_position === newPosition);

        console.log(`Bob moves to position: ${newPosition}`);
        return newPosition;
    },

    // acceptWager: Fun([UInt], Null),
    acceptWager: (wager) => {
      console.log(
        `Bob accepted the wager of ${stdlib.formatCurrency(parseInt(wager._hex, 16), 4)}`
      );
    },

    // updateBoard: Fun([gameBoard], Null),
    updateBoard: (gameBoard) => {
      board = gameBoard;
      // Print the board to the screen
      showBoard(board);
    },
  }),
]);
ask.done();
console.log("Goodbye, Alice and Bob!");

GitHub Repository

Our version of this app can be found at this link: GitHub Link

Conclusion

In this workshop you learnt how to:

Make a turn based application.
Add artificial intelligence to your game.

Congratulations on building a Reach application on your own with a little bit of help.

From here you can go ahead to explore more workshops here: https://docs.reach.sh/workshop/

Command Palette

Comments

More from this blog

Introduction

Why is this important?

Assumptions

Learning outcomes

Problem analysis

Questions to ask ourselves

Our answers

Participants involved

Functions performed by each of the participants

Alice:

Bob:

Functions shared by participants

The defaults

Representing the game state

Our answers

Checks

Our answers

Program flow

Our answers

Assertions

What things must be true for the program to continue at a point?

Our answers

Interactions

Our answers

Representing the board.

Implementing cat movement

Things to consider

Our answers

All together now

Our Reach backend

Our JavaScript Frontend

GitHub Repository

Conclusion