I need help reviewing my mini-max algorithm
Hi,
I've created a game of chess bottom up - I've been working on it for about one year now. This is a for fun project that I'm working on for pleasure, not a homework assignment or some.
I have reached the point where I'm interested in making a computer player who makes 'smart' decisions. I read chapter 5 of the AI (Modern Approach) book, and learned how to implement the minimax algorithm. I understand conceptually how it works, and I translated the pseudo code in the book into the following listed at the bottom of the post. I made several observations:
1) with depth of 1, the algorithm seems to choose the best 'Move' with simple end game scenarios ( i.e. mate in 1 ) when i select depth 1
2) with a simple mate in 2 scenario, the algorithm doesn't seem to pick the best move with depth of 4 ( look two full moves ahead ).
Can someone who is perhaps more familiar with minimax take a peek at my code and perhaps offer some suggestions as to why this may be the case? I know my implementation right now is not optimal, since I use a copy constructore to keep track of game states, as opposed to performing a move undo - however, I'm not looking to optimize the algorithm just yet. Any help is appreciated.
public Move miniMax(Board chess_board, Player opponent,int depth){
long time = System.currentTimeMillis();
examinedNodesCount = 0;
// calculate a decision using the minimax
ArrayList legalMoves = getPlayerLegalMoves();
int highest_seen_value = Integer.MIN_VALUE;
int lowest_seen_value = Integer.MAX_VALUE;
Move best_move =null;
examinedNodesCount += legalMoves.size();
for (int i = 0; i < legalMoves.size(); i++ ){
int value = 0;
try{
Board b =new Board(chess_board);
Player c =new Player(this);
Player o =new Player(opponent);
Move move =new Move((Move)legalMoves.get(i));
c.makeMove(b, o, move);
System.out.print("mp: " +move);
value = minimaxValue(b, o, c, depth - 1, move);
if ( c.playerIdentity =="White"){
if (value > highest_seen_value){
highest_seen_value = value;
best_move = move;
}
}else{
if (value < lowest_seen_value){
lowest_seen_value = value;
best_move = move;
}
}
}catch(Exception e){}
System.out.println();
}
time = System.currentTimeMillis() - time;
Table.ChatPanel p = Table.getChatPanel();
float time_per_board = (float)time /(float)examinedNodesCount;
float boards_per_second = (float)1000 / (float)time_per_board;
p.writeToDisplay("INFO:\nsearch depth = " +depth+
"\n# examined boards: " + examinedNodesCount +
"\ntotal time: " +time+" ms " +
"\navg time per board: " + time_per_board +" ms " +
"\n# boards per second: " + boards_per_second +
"\n move chosen: " +best_move);
return best_move;
}
privatestaticint minimaxValue(
Board chess_board,
Player current_player,
Player opponent_player,
int depth,
Move m ){
int ret_val = 0;
if (depth == 0 ||
current_player.isInCheckMate() ||
opponent_player.isInCheckMate()){
ret_val = Board.evaluateBoard(chess_board, current_player, opponent_player);
System.out.print(" with eval of: " +ret_val+", ");
}elseif (current_player.getIdentity() =="White"){
ArrayList legalMoves = current_player.getPlayerLegalMoves();
int highest_seen_value = Integer.MIN_VALUE;
examinedNodesCount += legalMoves.size();
for (int i = 0; i < legalMoves.size(); i++ ){
int value = 0;
try{
Board b =new Board(chess_board);
Player c =new Player(current_player);
Player o =new Player(opponent_player);
Move move =new Move((Move)legalMoves.get(i));
System.out.print("\t=> " +move);
c.makeMove(b, o, move);
value = minimaxValue(b, o, c, depth - 1, move);
if (value > highest_seen_value){
highest_seen_value = value;
}
}catch(Exception e){}
}
ret_val = highest_seen_value;
}
else{
ArrayList legalMoves = current_player.getPlayerLegalMoves();
int lowest_seen_value = Integer.MAX_VALUE;
examinedNodesCount += legalMoves.size();
for (int i = 0; i < legalMoves.size(); i++ ){
int value = 0;
try{
Board b =new Board(chess_board);
Player c =new Player(current_player);
Player o =new Player(opponent_player);
Move move =new Move((Move)legalMoves.get(i));
System.out.print("\t=> " +move);
c.makeMove(b, o, move);
value = minimaxValue(b, o, c, depth - 1, move);
}catch(Exception e){}
if (value < lowest_seen_value){
lowest_seen_value = value;
}
}
ret_val = lowest_seen_value;
}
return ret_val;
}
