Results 1 to 3 of 3
  1. #1
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    161
    Rep Power
    2

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

    Thanks in advance!

    Java 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!");
    	}
    	
    	...
    }
    Last edited by Zelaine; 01-04-2014 at 03:56 PM.

  2. #2
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    161
    Rep Power
    2

    Default Re: Minimax Algorithm = very confusing

    For your information: I created the algorithm using this pseudocode, which may or may not be incorrect:

    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.)
    Last edited by Zelaine; 01-04-2014 at 09:08 PM.

  3. #3
    Zelaine is offline Senior Member
    Join Date
    Aug 2013
    Location
    Sweden
    Posts
    161
    Rep Power
    2

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

Similar Threads

  1. Minimax Algorithm
    By AtoN in forum Java Gaming
    Replies: 1
    Last Post: 04-05-2011, 02:40 AM
  2. build search tree on minimax algorithm...
    By me26 in forum Java Gaming
    Replies: 2
    Last Post: 06-29-2010, 08:24 AM
  3. Minimax game theory with mancala
    By jigglywiggly in forum New To Java
    Replies: 2
    Last Post: 01-01-2010, 12:04 PM
  4. Minimax ai, oh lordy
    By jigglywiggly in forum New To Java
    Replies: 2
    Last Post: 12-11-2009, 08:24 PM
  5. Creating the evaluation function for Minimax
    By matzahboy in forum New To Java
    Replies: 7
    Last Post: 11-05-2009, 03:29 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •