Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Simply don't understand minimax...

  1. #1
    Member
    Join Date
    Oct 2011
    Posts
    40
    My Mood
    Stressed
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Simply don't understand minimax...

    I have been working on this for hours, and have done quite a bit of research. It seems I just cannot connect the dots in my head to understand this.
    I am writing a tic tac toe type program, and need to implement and AI using a minimax algorithm. I know what the behind it is, and what it's designed to do, but just can't seem to figure out how to get it into my program. Heck, I went so far as to hire a tutor to help. After 3 hours with him today, and a lot of wasted cash, I am no closer. He had no idea what minimax was.

    My game is similar to tic tac toe, except the board can be larger depending on what the user chooses. When someone scores, their pieces are removed from the board but the game continues.

    I can't imagine recursing through all of those options, so I am just wanting the algorithm to find the next best scoring option. My board is a 2D array, where most of the examples I see deal with 1D arrays. I could use any help that you can give me.

    The game works fine now for 2 human players.
    Methods are written for checking board, clearing board, checking win etc. I guess I just don't understand how to recursively create new boards and return values on the moves.


    This is what I have so far.
    I guess I need to know how to use my methods to increase the value of position Value. I know, my question is a mess, sorry

    /** minimax method to compute best possible computer move*/
    public int[][] compMove(int[][]gameBoard, int boardSize, int playerNumber, int row, int col){
    	int bestMoveIndex = 0;
    	int bestValue = +1000;
    	int [][] bestMoves = new int[boardSize][boardSize];
    	for(int i = 0; i<boardSize; i++)
    		for(int k = 0; k<boardSize; k++){
    			if(gameBoard[i][k] == 0 && playerNumber == 1)
    				gameBoard[i][k] = 1;
    			int value = maxSearch(gameBoard);
    			if(value < bestValue){
    				bestValue = value;
    				bestMoveIndex= 0;
    				bestMoves[bestMoveIndex][k] = i;
    			}
    			else if(value == bestValue){
    				bestMoves[bestMoveIndex++][k] = i;
    				gameBoard[i][k] = 0;
    			}
    		CompPlacePiece(bestMoves, i, k, playerNumber);
     
    		}
    	return gameBoard;
    }
    public int maxSearch(int[][]gameBoard, int playerNumber){
    	int positionValue = 0;
     
    	return positionValue;
    }


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,332
    My Mood
    Hungover
    Thanks
    143
    Thanked 624 Times in 535 Posts

    Default Re: Simply don't understand minimax...

    Quote Originally Posted by Herah View Post
    I guess I just don't understand how to recursively create new boards and return values on the moves.
    This tells me that you don't have a problem with minimax specifically, but with state-based search in general. Minimax comes after that.

    If I were you, I'd start by creating a method that takes a game board and whose turn it is (X or O) and returns a List of all the potential game boards that could result from that turn.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Member
    Join Date
    Jun 2011
    Posts
    56
    Thanks
    2
    Thanked 7 Times in 6 Posts

    Default Re: Simply don't understand minimax...

    First of all you should not create new board every time you make a move. That is a total waste of space and time.
    Instead have methods to make and unmake a move. Also you need an evaluation function for positions at the leaves of the tree . Terminal states are scored as a win , loss or draw. In the case of tic-tac-toe that would be if a player forms a horizontal/vertical or diagonal line.

    What you need to implement:
    int board[3][3];      
    void make(Move m,c);    //mark the square m (m.x,m.y) to c . c is either X or O
    void unmake(Move m);   //similar to make but it sets the square to blank
    void generateMoves(List<Move>)  //generate a list of moves. This is simply list of blank squares for tic-tac-toe
    int evaluate();           //evaluate a positon as win/loss/or draw (100,-100 and 0 resp.)

    Then you do nega-max as follows as follows.
    int negaMax( int depth ) {
         //do static evaluation at terminal states
         if ( depth == 0 )               
              return evaluate();   
         //start from worst possible score i.e a loss = -100
         int score,max = -100;       
         // generate list of legal moves
         Vector<Move> moves = new Vector<Move>();
         generateMoves(moves);    
         for (Move m : moves)  {
            //make the move AND switch sides i.e player != player
         	make(m);
            //recursive call with a reduced depth of 1
            score = -negaMax( depth - 1 );   
            // keep the best score                             
            if( score > max )     
                max = score
            //return to previous state again remember to switch sides
            unmake(m);               
        }
        //return max score
        return max;
    }
    I hope the comments help you understand the algorithm. If not say so and I will do my best.

  4. #4
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,332
    My Mood
    Hungover
    Thanks
    143
    Thanked 624 Times in 535 Posts

    Default Re: Simply don't understand minimax...

    Quote Originally Posted by dabdi View Post
    First of all you should not create new board every time you make a move. That is a total waste of space and time.
    Instead have methods to make and unmake a move.
    I disagree with this advice. You might be technically computationally correct, but chances are the OP is going off of code provided to him by an instructor, so changing it will probably introduce more trouble than it's worth.

    But like I said, I think the OP is having some problems that are more fundamental than the actual minimax algorithm.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. Help me to understand this
    By Madhushan in forum Java Theory & Questions
    Replies: 2
    Last Post: September 10th, 2011, 08:47 AM
  2. I don't understand what I'm supposed to do
    By dmcettrick in forum What's Wrong With My Code?
    Replies: 1
    Last Post: May 11th, 2011, 09:34 AM
  3. Minimax
    By Scotty in forum Java Theory & Questions
    Replies: 1
    Last Post: May 2nd, 2011, 08:21 AM
  4. CONNECT FOUR GAME-MINIMAX TO ALPHABETA ALGORITHM
    By AJreal in forum Algorithms & Recursion
    Replies: 0
    Last Post: March 6th, 2011, 02:30 PM
  5. Connect 4 involving minimax.
    By mandar9589 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: July 21st, 2009, 10:52 AM