Thread: 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;
}

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.