public abstract class MinMaxAI extends Controller
The minimax algorithm assigns a score to each possible game configuration g. The score is assigned recursively as follows: if the game g is over and the player has won, then the score is infinity. If the game g is over and the player has lost, then the score is negative infinity. If the game is a draw, then the score is 0.
If the game is not over, then there are many possible moves that could be made; each of these leads to a new game configuration g'. We can recursively find the score for each of these configurations.
If it is the player's turn, then they will choose the action that maximizes their score, so the score for g is the maximum of all the scores of the g's. However, if it is the opponent's turn, then the opponent will try to minimize the score for the player, so the score for g is the minimum of all of the scores of the g'.
You can think of the game as defining a tree, where each node in the tree represents a game configuration, and the children of g are all of the g' reachable from g by taking a turn. The minimax algorithm is then a particular traversal of this tree.
In practice, game trees can become very large, so we apply a few strategies to narrow the set of paths that we search. First, we can decide to only consider certain kinds of moves. For five-in-a-row, there are typically at least 70 moves available at each step; but it's (usually) not sensible to go on the opposite side of the board from where all of the other pieces are; by restricting our search to only part of the board, we can reduce the space considerably.
A second strategy is that we can look only a few moves ahead instead of planning all the way to the end of the game. This requires us to be able to estimate how "good" a given board looks for a player.
This class implements the minimax algorithm with support for these two
strategies for reducing the search space. The abstract method moves(Board) is used to list all of the moves that the AI is willing to
consider, while the abstract method estimate(Board) returns
the estimation of how good the board is for the given player.
gameChanged