Quote:Original post by Ohforf sakeOne detail to keep in mind about pure minimax is that it plays towards the best outcome given that both players play optimal, which in tic tac toe is a draw.
It doesn't try to fool the opponent into traps, because it assumes that the opponent won't fall for them.
This is the one problem with using minimax for TTT. The computer will play a guaranteed winning move at any point in the game if one exists, but it otherwise doesn't differentiate between moves that it anticipates leading to a draw as it assumes the player will always make the proper move. For example, even though playing a corner to start forces the opponent into a single move (in the middle), the computer will play anywhere because it assumes the player will always play in the middle if it chooses a corner, etc. etc.
At any rate, I have a TTT game written in C++ in which my AI uses minimax. I have it set up with a Board class, but that isn't strictly necessary. You should also be able to implement it similar to the following pseudocode.
You will want a function that returns a "score" from the perspective of the computer player using the function you use to check your game board for the current game state:
int EvaluateBoard(board){ int nGameState = CheckGameState(board); if(nGameState == computer wins) return large positive int; (LARGE_INT) if(nGameState == player wins) return large negative int; (-LARGE_INT) if(nGameState == draw) return 0; return -1; //still playing}
A function that generates a container of available moves from a board is also helpful:
container<int> GetValidMoves(board){ container<int> nContainer; for(each location on the board) { if(location is not occupied) nContainer.push_back(location); } return nContainer;}
Your Minimax function takes a board and returns a move. It will utilize a Min (and via Min, a Max) function that takes a board and returns a score.
int MiniMax(board){ int nBestScore = -LARGE_INT; //stores the best score evaluated, initially set to the value associated with a human player win container<int> nBestMoves; //container to store the moves yielding the nBestScore; container<int> nValidMoves; nValidMoves = GetValidMoves(board) //valid moves for the board while(!(nValidMoves.empty())) //we're going to loop over all of the valid moves { SetSquare(board, nValidMoves.front(), ComputerPiece); //set the square associated with the first valid move to the computer's piece int nScore = Min(board); //call the int Min(board) function which ultimately will return a score based on the final board state if(nScore > nBestScore) { nBestScore = nScore; //the score becomes our new best score nBestMoves.clear(); //we have a new best score, so our best moves are no longer the best, get rid of them nBestMove.push_back(nValidMoves.front()); //add the move to the best moves container } else if (nScore == nBestScore) { nBestMove.push_back(nValidMoves.front()); //add the move to the best moves container } SetSquare(board, nValidMoves.front(), EmptyPiece); //return the square to its original state nValidMoves.pop_front(); //we're finally done with the move, discard it } return (random move from your nBestMoves container); //choose a random move from your best moves to add some variety}
int Min(board) returns a score based on the final board state, it calls Max (which in turn calls Min), until a GameOver state is reached:
int Min(board){ int nMoveScore = EvaluateBoard(board); if(!(nMoveScore == -1)) return nScore; //if we're not still playing, the game is over so return the score; int nBestScore = LARGE_INT; //Min is from the player's perspective, from which LARGE_INT represents a loss container<int> nValidMoves; nValidMoves = GetValidMoves(board); while(!(nValidMoves.empty())) { SetSquare(board, nValidMoves.front(), PlayerPiece); //set the square to the player piece int nScore = Max(board); //we've made a move, so evaluate the board from the other player's perspective if(nScore < nBestScore) //if we found a better move for the human player { nBestScore = nScore; } SetSquare(board, nValidMoves.front(), EmptyPiece); //reset the square; nValidMoves.pop_front(); } return nBestScore;}
int Max(board) is the same as Min except from the computer player's perspective, so swap -LARGE_INT for LARGE_INT, (nScore > nBestScore) for (nScore < nBestScore), ComputerPiece for PlayerPiece, and Min(board) for Max(board).
I'm sure this can be streamlined, but for a Tic-Tac-Toe game where at most you are evaluating 9 moves, it's not really necessary IMO.
[Edited by - Crowseye on February 15, 2010 12:52:08 PM]
