# Minimax Algorithm = very confusing

• 01-04-2014, 04:50 PM
Zelaine
Minimax Algorithm = very confusing
Hi guys!

You see, I have been trying to create an algorithm for the computer in my Tic-Tac-Toe game? So I searched for some good ones, and found about this confusing but effective algorithm, at least if you get it working, called Minimax. I tried implementing it into my game. Let's say it was easier said than done. Sometimes I think it's working, but sometimes it doesn't work at all. So here I am today to ask from you to help me with this :) How do I get my algorithm working? I'm also very confused on what the variables BEST_SCORE_COMPUTER and BEST_SCORE_PLAYER in my code should have as starting values, do any of you guys know? Because that might be the problem.

Code:

```import java.util.Scanner; public class TicTacToe{                 private static char BOARD[] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}; // This is the main board itself.         private static int ROWS[][] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6}, {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}}; // These are all the rows one can win by filling.         private static int SCORE, BEST_MOVE_COMPUTER, BEST_SCORE_COMPUTER = -1, BEST_SCORE_PLAYER = 1; // These variables speak for themselves.         private static byte TURN = 1; // 1 means player's turn, and 2 means computer's turn.                 public static void main(String[] args){                        while(!(chooseWinner() >= -1 && chooseWinner() <= 1)){  // If the game isn't over yet.                         if(TURN == 1){                                 displayBoard();                                 makeMove(choosePlayerMove(), 'X');                                 if(!TILE_NOT_CHOSEN) // This checks if the player has chosen a tile that already has been chosen. If the player has,                                                               // the program will not change turn.                                         changeTurn();                         }else if(TURN == 2 && !(chooseWinner() >= -1 && chooseWinner() <= 1)){                                 minimax(); // This is where the computer chooses a tile.                                 makeMove(BEST_MOVE_COMPUTER, 'O'); // This is where it makes its move.                                 if(TURN == 2) // This is just for security reasons, since I also use the TURN variable in the minimax method.                                         changeTurn();                         }                 }                 displayBoard();         }                 ...                 static int minimax(){ // This is where the computer chooses a tile, and also where I think the errors lie.                 int winner = chooseWinner();                 if(winner >= -1 && winner <= 1)  // If the game is over, then return the variable winner.                         return winner;                                 if(TURN == 1){ // This will go through all the player's possible moves.                         for(int tile = 0; tile < BOARD.length; tile++){                                 if(isLegal(tile)){ // This checks if the move is legal, however the computer still sometimes manages to choose a tile                                                       // that has already been chosen.                                         makeMove(tile, 'X'); // This makes the move.                                         changeTurn(); // This changes turn.                                         SCORE = minimax(); // This evaluates the score.                                         undoMove(tile); // This undoes the move.                                                                                 if(SCORE < BEST_SCORE_PLAYER) // If SCORE is lower than the player's current best score, than the player's best                                                                                       // score shall equal SCORE.                                                 BEST_SCORE_PLAYER = SCORE;                                         if(BEST_SCORE_COMPUTER >= BEST_SCORE_PLAYER) // This part confused me a lot, however I think it's for stopping searching for                                                               // better moves if the player already has a better move than the computer.                                                 return BEST_SCORE_PLAYER;                                 }                         }                         return BEST_SCORE_PLAYER;                 }                                 else if(TURN == 2){ // This will go through all the computer's possible moves.                         for(int tile = 0; tile < BOARD.length; tile++){                                 if(isLegal(tile)){                                         makeMove(tile, 'O');                                         changeTurn();                                         SCORE = minimax();                                         undoMove(tile);                                                                                 if(SCORE > BEST_SCORE_COMPUTER){ // If SCORE is greater than the computer's current best score, than the computer's                                                                                             // best score shall equal SCORE.                                                 BEST_SCORE_PLAYER = SCORE;                                                 BEST_MOVE_COMPUTER = tile; // Saves the computer's best move for later use.                                         }if(BEST_SCORE_COMPUTER >= BEST_SCORE_PLAYER) // Same thing as above, I think it's for stopping searching for                                                                 // better moves if the computer already has a better move than the player.                                                 return BEST_SCORE_COMPUTER;                                 }                         }                         return BEST_SCORE_COMPUTER;                 }                                 else                         throw new IllegalArgumentException("The program will never reach this part... ");         }                 ...                 static void changeTurn(){                 if(TURN == 1)                         TURN = 2;                 else if(TURN == 2)                         TURN = 1;                 else                         throw new IllegalArgumentException("Illegal value!");         }                 ... }```
• 01-04-2014, 10:05 PM
Zelaine
Re: Minimax Algorithm = very confusing
For your information: I created the algorithm using this pseudocode, which may or may not be incorrect:

Quote:

alpha-beta(player,board,alpha,beta)
if(game over in current board position)
return winner

children = all legal moves for player from this board
if(max's turn)
for each child
score = alpha-beta(other player,child,alpha,beta)
if score > alpha then alpha = score (we have found a better best move)
if alpha >= beta then return alpha (cut off)
return alpha (this is our best move)
else (min's turn)
for each child
score = alpha-beta(other player,child,alpha,beta)
if score < beta then beta = score (opponent has found a better worse move)
if alpha >= beta then return beta (cut off)
return beta (this is the opponent's best move)
(EDIT: All spaces, including TABs, are removed for some reason, so that's why it looks kind of strange. I don't know what to do about it.)
• 01-05-2014, 02:16 AM
Zelaine
Re: Minimax Algorithm = very confusing
Could someone please answer? Or at least give me some tips on how to do it in a better way. I would be really grateful.