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 :(

Code Java:

---

/** 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;
}

---

Quote:

---

Originally Posted by Herah

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.

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:

Code java:

---

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.

Code java:

---

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.

Quote:

---

Originally Posted by dabdi

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.