Is this code correct?
This code was adapted from this alphabeta pseudocode. AlphaBeta search is often mentioned but getting the code 100% correct is tricky.
IGame
is an interface with two methods:
getScore()
- evaluates the current game state from the viewpoint of the AI
generateMoves()
- creates possible moves from the current game state.
class Search
{
Move bestMove;
Move findBestMove(int ply, IGame g)
{
bestMove = null;
alpha_beta(ply, g, Integer.MINIMUM, Integer.MAXIMUM);
return bestMove;
}
int alpha_beta(int depth, IGame g, int alpha, int beta)
{
if (depth == 0 || g.isGameFinished()) return g.getScore();
Move[] gameMove = g.generateMoves();
for (int i = 0; i < gameMove.length; i++)
{
g.execute(gameMove[i]);
int score = -alpha_beta(depth - 1, -beta, -alpha);
g.undo(gameMove[i]);
if (alpha < score)
{
alpha = score;
bestMove = gameMove[i];
}
if (beta <= alpha) return alpha;
}
return alpha;
}
}