Question

tic-tac-toe game. Add functionality to the program so when the button is clicked for the AI to take a turn, a heuristic is applied for each of the possible moves, a possible move is selected and the game state and GUI are properly updated. Once complete, the program should be able to play a single game of tic-tac-toe with the user.

C#

Answer 1

Assuming that the data structure used is 3X3 matrix.

The game's logic can be broken into different functions for better understanding:

1. A Boolen function 'moves_left' to check whether any more possible moves can be made.Returns True is moves are available, else returns False.
2. A function named 'victory' to check for any possible winning at that particular instance after both the user's and the system's turn.
3. A function named 'my_min_max' to make the next move that can take place and return the value to the game board.
4. A fucntion named 'find_next_best_move' that selects the best alternative among the possivle moves.

In Detail:

The find_next_best_move function will return the co-ordinates for the next move.

To find the next best move for the AI my_mini_max algorithm can be used. The my_mini_max algorithm is an algorithm which uses backtracking mechanism used in decision making problems. TicTacToe is one such application where the my_mini_max algorithm can be made use of. Here, the idea is to use the same algo to find out the best move for AI.

If interested you may go through the mini_max algorithm to get a bigger picture of what my_mini_max algo does

The function replicates the my_mini_max algorithm to simulate the possible optimal sets of future moves of both human player and AI. The function returns a score which can be used to evaluate if the selected move is the best move.

For more clarity,

Suppose the board is in a position like this:

[ 'x', 'o', '_' ]

[ 'o', 'o', '_' ]

[ 'x', 'x', '_' ]

The find_next_best_move will iterate over the board and if the position is empty, it marks that position and calls the my_mini_max function. myMiniMax function will then optimally simulate the next moves by both user and checks if the current move played by the player returns the max score. The find_next_best_move function will check for the best scores returned for each empty spaces and best position is returned.

This means that the next position will be (2, 2) in the above case.

[ 'x', 'o', '_' ]

[ 'o', 'o', '_' ]

[ 'x', 'x', 'x' ]

The above is just an example to illustrate on single case of selecting the next best move.

Note: During the game, the player and the system earn points based on their move. It is based on this value that the AI is performed to choose the best move that can earn the system a better chance to win.

The functions and the detailed working of the game is explained with comments in the code below.

  // Function 'moves_left'. static Boolean moves_left(char [,]b) { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(b[i,j] =='_') // if the space is emptyreturn true; return false; } //Function 'victory'. static int victory(char [,]b) { for(int r=0;r<3;r++) // Checking for row victory (Xs or Os) { if(b[r,0] ==b[r,1] && b[r,1] == b[r,2]) { if(b[r,0] == player) return +10; else if(b[r,0] == opponent) return -10; } } for(int col=0;col<3;col++) // Checking for column victory (Xs or Os) { 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; } } if(b[0,0] ==b[1,1] && b[1,1] ==b[2,2]) // checking for diagonal victory (Xs or Os) { 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]) // checking for diagonal victory (Xs or Os) { if(b[0,2] == player return +10; else if(b[0,2] == opponenet) return -10; } return 0; } //Function 'my_min_max'. static int my_min_max(char [,]b,Boolean isuser) { int point = victory(b); if (point == 10) // If user has won the game return point; if (point == -10) // If system has won the game return point; if (moves_left(b) == false) // If there are no more moves and no winner then it is a tie return 0; if (isuser) // If user's move { 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 (b[i,j] == '_') { // Make the move b[i,j] = player; best = Math.Max(best, my_min_max(b,!isuser)); // Call minimax recursively and choose the maximum value b[i,j] = '_'; // Undo the move } } } return best; } else // If system's move { int best = 1000; // Traverse all cells for (int i=0;i<3;i++) { for (int j=0;j<3;j++) { if (b[i,j] == '_') // Check if cell is empty { b[i,j] = opponent; // Make the move best = Math.Min(best,my_min_max(b,!isuser)); // Call minimax recursively and choose the minimum value // Undo the move b[i,j] = '_'; } } } return best; } } //Function 'find_next_best_move'. static Move find_next_best_move(char [,]b) { int bestvalue = -1000; Move bestMove = new Move(); bestMove.row = -1; bestMove.col = -1; // Traverse all cells, evaluate 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++) { if (b[i,j] == '_') // Check if cell is empty { b[i,j] = player; // Make the move int movevalue = my_mini_max(b,false); // compute evaluation function for this move. b[i,j] = '_'; // Undo the move // update the bestvalue by comparing the movevalue and the existing bestvalue. if (movevalue > bestvalue) { bestMove.row = i; bestMove.col = j; bestvalue = movevalue; } } } } return bestMove; }