int minmax(Board game, int depth)
{
if (game.IsFinished() || depth < 0)
return game.Score(game.Turn);
int alpha = int.MinValue + 1;
foreach (Point move in game.Generate_Moves())
{
Board currentBoard = game;
currentBoard.Do_Move(move);
alpha = max(alpha, -minmax(currentBoard, depth-1));
currentBoard.Undo_Move(move);
}
return alpha;
}
The thing is that this little function tells me if the game is a win, a lose or a draw, but how can i get the move that will led me to a win? My Point class is a simple Class With 2 coordinates X, Y and i want to get the answer as a point so i can latter say something like game.Do_Move(myPoint)
.
In case some functions aren't obvious:
game.IsFinished()
- returns true if win/lose/draw else otherwise
game.Score(turn)
- returns -1/0/1 in case is a lose/draw/win for the player with the next move
game.Generate_Moves()
- returns a List with available moves
game.Do_Move()
- void that applies the move to game
game.Undo_Move()
- talks for itself
It would be enough if the minimax function which gets called on the root node of the game tree returns both, the choosen move and the score. For all other nodes of the game tree, the function needs only to return the score. Thus the usual way is to implement two slightly different minimax functions – Look at Note #2 in the description to this NegaMax Framework.
Applied to your minimax interface you would have following additional function:
int minimaxWithMove(Board game, int depth, Point& choosen)
{
assert (!game.IsFinished() && depth > 0); // not possible at root node
int alpha = int.MinValue + 1;
foreach (Point move in game.Generate_Moves())
{
Board currentBoard = game;
currentBoard.Do_Move(move);
int score = -minmax(currentBoard, depth-1);
if (score > alpha)
{
alpha = score;
choosen = move;
}
}
return alpha;
}
Note that I have removed the call to Undo_Move
as it is not needed because you make a copy of game
in each iteration.