The game of ‘Walls’ is comprised of an NxN board of squares (like chess, for example) and two players (say A and B), where N is odd and greater than 1. Each game is played twice, one time with player A starting the game and another with player B making the first move. The game has a start state, play rules that determine legal moves and an end state. Once a game ends, there is a certain accounting that decides the game result. These concepts are explained below. I suggest you first design a game with N=3.

Your objective, as the programmer is to design, in detail, build and test an artificial agent (AA for short) capable of playing the game, as optimally as possible, against a human player or another AA. To do so you need to build a search tree (often called game tree) that includes every possible move starting from the initial state of the game, and all possible future moves, all the way down to the leaf nodes (dead-ends with no possibility of future moves). The search tree is searched to decide on the best current move, which is the move that is most likely to lead to an eventual win in the game. An example of a search tree and how it is used to decide game is referred to below, also.

Start state. The game starts with a clear board with the two players placed at horizontally symmetric positions, which are at equal distances from and as close as possible to the center of the board (without overlapping). A player has a ‘face’ which indicates the direction of its forward movement. At the start of the game each player is facing outward towards the closest edge to it.

Play rules. The players take turns making moves. A player can: try and move forward (try-forward), turn 90 degrees left (turn-left) or turn 90 degrees right (turn-right). A player can only move into an empty square or into a square with a ‘brick’ bearing its name. A player cannot move into a square that has a ‘brick’ of the opposite type, or off the edge of the board, or into a square currently occupied by the opposite player. Anytime player X moves forward from an unmarked square, that square is filled with a brick marked X (signifying its origin).