Need help with Minimax Algorithm

[Bob Zoloman]

I am trying to implement a minimax algorithm based on this pseudo code below. Could anyone tell me if this pseudo code is correct, because I'm haivng a hell of a time getting it to work. Some things I don't get are:

1. In the MinMove function why do they use move > best_move (identical to max move). Shouldn't the min move try to minimiz max's advantage, thus it should be < (or better yet <= )?

2. Assuming best_move and move are integer values, how can I assign a null type value or -infinity / +inifity? Since minimax starts evaluating from bottom up, say for example it is evaluating the last MaxMove (very top of tree - root) and it's default best_move value = 0, and the move value returned is -1, but there are currently no moves returned by MaxMove, so it must return the -1 move, but will not since it is less than zero. What if there are a couple different moves that return a loss (-1) and MaxMove will not include any of them because they are less than zero, thus causing the program to error out.

3. Why is the if -> GameEnded function not also included in the MinMove?

Sorry for the all the questions, but I've been at this for a long time, and most online resources really suck. All I'm after is an algorithm that is actually correct, and I'm almost positive this one is not.

I found it at this site in case anyone is interested:
http://ai-depot.com/LogicGames/MiniMax.html

MinMax (GamePosition game) {
  return MaxMove (game);
}
 
MaxMove (GamePosition game) {
  if (GameEnded(game)) {
    return EvalGameState(game);
  }
  else {
    best_move <- {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game));
       if (Value(move) > Value(best_move)) {
          best_move <- move;
       }
    }
    return best_move;
  }
}
 
MinMove (GamePosition game) {
  best_move <- {};
  moves <- GenerateMoves(game);
  ForEach moves {
     move <- MaxMove(ApplyMove(game));
     if (Value(move) > Value(best_move)) {
        best_move <- move;
     }
  }
 
  return best_move;
}  

[ August 12, 2006: Message edited by: Bob Zoloman ]

[Bob Zoloman]

I got it to work, in case anyones interested this is the pseudo code that works for me.

    
MinMax (GamePosition game) {
  return MaxMove (game);
}
 
MaxMove (GamePosition game) {
  if (GameEnded(game)) {
    return EvalGameState(game);
  }
  else {
    best_move <- {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game));
       if (Value(move) >= Value(best_move) // more condition checks {
          best_move <- move;
       }
    }
    return best_move;
  }
}
 
MinMove (GamePosition game) {
if (GameEnded(game)) {
    return EvalGameState(game);
  }
  else { 
    best_move <- {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MaxMove(ApplyMove(game));
       if (Value(move) <= Value(best_move) // more condition checks) {
          best_move <- move;
       }
    }
     return best_move;
  }
}
 

 

[ August 12, 2006: Message edited by: Bob Zoloman ]