MinMax uses an evaluation function to quantify the "goodness" of a position. An easy example could be that a position that is a win for a computer might get the value of +1; a draw could get 0; and a position that the computer has lost would get a -1. A position for which this assignment can be determined by examining the board is known as a terminal position.
If a position is not a terminal, the value of the position is determined by recursively assuming optimal play by both sides. This is known as a MinMax strategy because one player (the human) is trying to minimize the value of the position while the other player (the computer) is trying to maximize it.
Alpha-Beta Pruning is by far the most commonly implemented intelligent game-playing algorithm where no information is lost. It belongs to the depth-first-searches family, and it has a complexity of either Ordo( b^(d/2) ) or Ordo( (b+1)^(d/2) ) depending on if d is even respectively odd. The d represents the depth of the search tree, and b (the branching factor) represents the width of the game board.
A ply is a sigle players action, and every ply analyze, adds one to the depth of the search tree. I've used a depth between 4 and 6 sofar, but hope to manage to optimize a bit to be able to look further ahead in the future. I've put some energy into developing a smart eval-function, but it is currently too big&slow. If you are interested, look at your Java Console during a game. Btw, does the IE have a Java Console? Well, it's a free world and you choose your own browser...
Latest recompilation: 1999-08-18 (yepps, found a bug ;-)