Concepts

At its core, Macao is a general game playing AI for JavaScript games. It is based on the Monte Carlo Tree Search algorithm.

Macao requires almost no configuration to add to your project. To get started you only need to understand its Core Concepts:

• Game State
• Player Action
• Generating Actions
• Applying an Action
• Is the Game Over?
• Did I Win? Did I lose? By how much?

This document is intended to give a high-level overview of these concepts, while providing links to detailed concept specific use cases.

Game State

When programming your game, you will have to decide upon an object type to store the state of the game. Macao doesn't get in your way when it comes to deciding on the shape of your game state object. The only thing it asks of you is that you store game states in a JavaScript object, and that the object has a property named player. The player property should store a player identification, it could be a string or a number, whatever you prefer. Each game state should have an associated player property that identifies the player having just played... the player responsible for making the game state what it is.

Here are a few examples of game state objects that would be compatible with Macao:

const gameState = {
  board: [0, 1, 0, 0, 1, 0]
  player: 1
}

const otherGameState = {
  myBoard: [
    ['X', 'O', 'X'],
    ['O', 'X', 'O'],
    ['X', 'O', 'X']
  ],
  player: 'X'
}

const yetAnotherGameState = {
  gameBoard: 446 //bitboard
  someCondition: true
  someOtherCondition: false
  somePropertyThatYouNeedToTrack: 67
  player: 2
}

As you can see, the game state object can take pretty much any shape you like, as long as it has a player property.

Player Action

In programming your game, you will also have to come up with a way to represent player actions. In this, Macao gives you complete free rein. You can represent actions however you please. Player actions will be consumed and produced by some of the functions you will have to write in order to make your game, and Macao, work.

Generating Actions

One of the functions you will need to write for your game, and that you will need to pass to Macao, is a function that generates all possible legal moves given a certain game State. For instance, let's imagine that we are making a simple Tic-Tac-Toe game and that we are representing the board and the game State like this, where 0 represents an empty square, 1 represents an X square and -1 represents an O square:

const ticTacToeGameState = {
  board: [
    [-1,  0,  1],
    [ 1,  1, -1],
    [-1,  0,  0]
  ],
  player: -1
}

Let's also imagine that we had decided upon a very simple Action object type that only contained the 0 indexed coordinates of the move to be made, something like this:

const action = { row: 0, column: 1}

Now we would need to write a function that takes in the game State as an argument and returns an array of Action objects. For this simple game of Tic-Tac-Toe it could look like this:

const generateActions = (state) => {
  const result = []
  state.board.forEach((rowArray, row) => {
    rowArray.forEach((value, column) => {
      if (value === 0) result.push({ row, column })
    })
  })
  return result
}

Pretty simple, isn't it? All we are doing is looking at each square and pushing the coordinates of the empty squares to our result array. Of course, in more complicated games, this function can get much more complex.

Applying an Action

Next, you'll have to write a function that takes State object and an Action object as arguments, in that order, and that returns a new State object after applying the Action. Make sure to return a new State, do not mutate the State passed in as an argument. Following the above Tic-Tac-Toe example, here's what this function could look like:

const applyAction = (state, action) => {
  const jSONBoard = JSON.stringify(state.board)
  const newBoard = JSON.parse(jSONBoard)
  newBoard[move.row][move.col] = state.player * -1
  const newState: TicTacToeState = {
    board: newBoard,
    player: state.player * -1
  }
  return newState
}

So what is going on here? First, we are copying the state board, by value, to the newBoard variable. This makes sure we don't mutate the state board. Then we are applying the move to our newBoard. Using 1 and -1 as player ids in 2 player games makes switching between players easy, as you can simply multiply by -1 to flip players. Then it's just a matter of constructing the newState and returning it. As simple as that.

Is the Game Over?

Coming up with a way to check if the game is over is something that has to be done in every type of game. To work with Macao, you will need to write a function that takes in a State as an argument and return true if the game is over, and false if it isn't. Here is an example, continuing with our simple Tic-Tac-Toe game:

const isStateTerminal = (state) => {
  for (let i = 0; i < 3; i++) {
    // check rows to see if there is a winner
    if (
      state.board[i][0] === state.board[i][1] &&
      state.board[i][1] === state.board[i][2] &&
      state.board[i][0] !== 0
    ) {
      return true
    }

    // check cols to see if there is a winner
    if (
      state.board[0][i] === state.board[1][i] &&
      state.board[1][i] === state.board[2][i] &&
      state.board[0][i] !== 0
    ) {
      return true
    }
  }

  // check diags to see if there is a winner
  if (
    state.board[0][0] === state.board[1][1] &&
    state.board[1][1] === state.board[2][2] &&
    state.board[0][0] !== 0
  ) {
    return true
  }

  if (
    state.board[0][2] === state.board[1][1] &&
    state.board[1][1] === state.board[2][0] &&
    state.board[0][2] !== 0
  ) {
    return true
  }

  // check to see if the board is full and therefore a draw
  const flattenBoard = state.board.reduce((p, c) => p.concat(c))
  if (flattenBoard.every(value => value !== 0)) return true

  return false
}

Did I Win? Did I lose? By how much?

Finally, you'll need to write a function that determines the value of a terminal game State, from the perspective of a given player. The function will take a game State, and a player ID, as arguments, in that order. It will return a Number. For out Tic-Tac-Toe example, will will use a value of 1 to mean that the player in question has won the game. A value of -1 will indicate that the player has lost, and a value of 0 means there is a draw. Although a different reward scheme will work with the algorithm, we recommended that you use this one for two player games. Here is what our function looks like:

const calculateReward = (state, player) => {
  for (let i = 0; i < 3; i++) {
    // check rows to see if there is a winner
    if (state.board[i][0] === state.board[i][1] && state.board[i][1] === state.board[i][2]) {
      if (state.board[i][0] === player) return 1

      return -1
    }

    // check cols to see if there is a winner
    if (state.board[0][i] === state.board[1][i] && state.board[1][i] === state.board[2][i]) {
      if (state.board[0][i] === player) return 1

      return -1
    }
  }

  // check diags to see if there is a winner
  if (state.board[0][0] === state.board[1][1] && state.board[1][1] === state.board[2][2]) {
    if (state.board[0][0] === player) return 1

    return -1
  }

  if (state.board[0][2] === state.board[1][1] && state.board[1][1] === state.board[2][0]) {
    if (state.board[0][2] === player) return 1

    return -1
  }

  return 0
}