Question

I need help with my programming assignment. The language used should be java and the algorithm should use search trees so that you play against the computer and he chooses the best move. The tree should have all possibilities on the leaves and you could use recursion to so that it populates itself. The game can be a 3*3 board (no need the make it n*n). Please put comments so that I can understand it. Thanks

The game of ‘Walls’ is comprised of an NxN board of squares (like chess, for example). 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.

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).

End state. The game ends when either every square on the board contains a brick or both players are stalled. A player is stalled, by definition, if it makes 9 consecutive moves without laying a new brick. A stalled player is not allowed to make any more moves.

Game result. Once the end state of the game is reached, the player with the greater number of bricks bearing its name wins 2 points (the other receiving 0). If both players lay the same number of bricks then the result is a draw, with each player receiving 1 point

Answer 1

// C++ program to find the next optimal move for
// a player
#include<bits/stdc++.h>
using namespace std;

struct Move
{
   int row, col;
};

char player = 'x', opponent = 'o';

// This function returns true if there are moves
// remaining on the board. It returns false if
// there are no moves left to play.
bool isMovesLeft(char board[3][3])
{
   for (int i = 0; i<3; i++)
       for (int j = 0; j<3; j++)
           if (board[i][j]=='_')
               return true;
   return false;
}

// This is the evaluation function as discussed
// in the previous article ( http://goo.gl/sJgv68 )
int evaluate(char b[3][3])
{
   // Checking for Rows for X or O victory.
   for (int row = 0; row<3; row++)
   {
       if (b[row][0]==b[row][1] &&
           b[row][1]==b[row][2])
       {
           if (b[row][0]==player)
               return +10;
           else if (b[row][0]==opponent)
               return -10;
       }
   }

   // Checking for Columns for X or O victory.
   for (int col = 0; col<3; col++)
   {
       if (b[0][col]==b[1][col] &&
           b[1][col]==b[2][col])
       {
           if (b[0][col]==player)
               return +10;

           else if (b[0][col]==opponent)
               return -10;
       }
   }

   // Checking for Diagonals for X or O victory.
   if (b[0][0]==b[1][1] && b[1][1]==b[2][2])
   {
       if (b[0][0]==player)
           return +10;
       else if (b[0][0]==opponent)
           return -10;
   }

   if (b[0][2]==b[1][1] && b[1][1]==b[2][0])
   {
       if (b[0][2]==player)
           return +10;
       else if (b[0][2]==opponent)
           return -10;
   }

   // Else if none of them have won then return 0
   return 0;
}

// This is the minimax function. It considers all
// the possible ways the game can go and returns
// the value of the board
int minimax(char board[3][3], int depth, bool isMax)
{
   int score = evaluate(board);

   // If Maximizer has won the game return his/her
   // evaluated score
   if (score == 10)
       return score;

   // If Minimizer has won the game return his/her
   // evaluated score
   if (score == -10)
       return score;

   // If there are no more moves and no winner then
   // it is a tie
   if (isMovesLeft(board)==false)
       return 0;

   // If this maximizer's move
   if (isMax)
   {
       int best = -1000;

       // Traverse all cells
       for (int i = 0; i<3; i++)
       {
           for (int j = 0; j<3; j++)
           {
               // Check if cell is empty
               if (board[i][j]=='_')
               {
                   // Make the move
                   board[i][j] = player;

                   // Call minimax recursively and choose
                   // the maximum value
                   best = max( best,
                       minimax(board, depth+1, !isMax) );

                   // Undo the move
                   board[i][j] = '_';
               }
           }
       }
       return best;
   }

   // If this minimizer's move
   else
   {
       int best = 1000;

       // Traverse all cells
       for (int i = 0; i<3; i++)
       {
           for (int j = 0; j<3; j++)
           {
               // Check if cell is empty
               if (board[i][j]=='_')
               {
                   // Make the move
                   board[i][j] = opponent;

                   // Call minimax recursively and choose
                   // the minimum value
                   best = min(best,
                       minimax(board, depth+1, !isMax));

                   // Undo the move
                   board[i][j] = '_';
               }
           }
       }
       return best;
   }
}

// This will return the best possible move for the player
Move findBestMove(char board[3][3])
{
   int bestVal = -1000;
   Move bestMove;
   bestMove.row = -1;
   bestMove.col = -1;

   // Traverse all cells, evalutae minimax function for
   // all empty cells. And return the cell with optimal
   // value.
   for (int i = 0; i<3; i++)
   {
       for (int j = 0; j<3; j++)
       {
           // Check if celll is empty
           if (board[i][j]=='_')
           {
               // Make the move
               board[i][j] = player;

               // compute evaluation function for this
               // move.
               int moveVal = minimax(board, 0, false);

               // Undo the move
               board[i][j] = '_';

               // If the value of the current move is
               // more than the best value, then update
               // best/
               if (moveVal > bestVal)
               {
                   bestMove.row = i;
                   bestMove.col = j;
                   bestVal = moveVal;
               }
           }
       }
   }

   printf("The value of the best Move is : %d\n\n",
           bestVal);

   return bestMove;
}

// Driver code
int main()
{
   char board[3][3] =
   {
       { 'x', 'o', 'x' },
       { 'o', 'o', 'x' },
       { '_', '_', '_' }
   };

   Move bestMove = findBestMove(board);

   printf("The Optimal Move is :\n");
   printf("ROW: %d COL: %d\n\n", bestMove.row,
                               bestMove.col );
   return 0;
}