AI Chess
Algorithms
The program implements the following concepts and algorithms:
1. Board Representation
2. Minmax Searching
3. Alphabeta pruning
4. Null move heuristic
5. Quiescence searching
6. Static board evaluation functions
7. Optimizing board evaluation functions via genetic algorithms
8. Opening Move Database
Back to main page.
Board Representation
The chessboard is represented in the
simplest possible manner  as an 8 by 8 matrix, each containing a Piece (with
a "blank" piece
representing empty board spaces). Furthermore,
flag variables keep track of whether queen/king side castling is allowed
for each
player, and whether an enpassant capture move is allowed at a given point
in time.
In order to save space and time during the minmax search, its optimal
not to have separate board instance at each branch. After all, they
differ only by the position of one piece. Hence each move contains information
not only about which piece was moved from where to where, but
also whether it affected castling, en passant, and whether it captured
an enemy piece in the process. Thus reversing a move on a board is very simple.
The algorithm thus only needs one board object, on which it makes and
reverses all the moves it considers during its search.
Advanced chess playing programs have far more clever board representations,
which operate on bits. Separate instances are kept to keep track of
individual pieces, and often bitwise operations can reveal a lot of information
about board positions very quickly (particularly with respect to pawns).
Years of research have been spent trying to optimize these representations
for speed.
Minmax Searching
The core of the chess playing algorithm
is a local minmax search of the gamespace.
The algorithm attempts to MINimize the opponent's score, and MAXimize
its own. At each depth
(or "ply" as it's as its referred to in computer chess terminology), all
possible moves are examined,
and the static board evaluation function is used to determine the score
at the leafs of the search tree.
These scores propagate up the tree and are used to select the optimal
move at each depth. The bigger
the ply, the better the chosen move will be (as the algorithm is able
to look ahead more moves). The
branching factor is typically between 25 and 40 moves per ply (the average
is around 35).
Alphabeta Pruning
This common pruning
fuction is used to considerably decrease the minmax search space.
It essentially keeps track of the worst and best moves for each
player so far, and using those can
completely avoid searching branches which are guaranteed to yield worse
results. Using this
pruning will return the same exact moves as using minmax (i.e. there
is no loss of accuracy). Ideally,
it can double the depth of the search tree without increasing search time.
To get close to this optimum,
the available moves at each branch should be appropriately sorted.
The sorting is done by the looking at the scores of
each possible move, looking only 1 ply ahead. The
intuitive sort would be to arrange them from best to worst, but that's
not always best. Most moves in
chess end up being ones with small gains and losses (ones that improve
position, not necessarily capturing
pieces), so it makes sense to order the "stand pat" moves first. So the
sorting is based on the absolute value of
the move scores (with the smaller ones coming first).
The average branching factor for minmax in chess is
about 35, but with the alphabeta pruning and sorting,
the program acheives a branching factor of around 25.
Null Move Heuristic
This simple heuristic improves the
beginning of the alphabeta search. Initially, there are no values for what
the worst and best possible moves are, so they default to negative and
positive infinity respectively. But using
this heuristic the algorithm can find an initial lower bound on the best
moves. It lets the opposing player play
two moves in sequence (choosing them based on a smallply minmax search),
and computes the score after that.
Certainly, any move made by the current player should beat a score obtainable
by the opponent getting two chances
to move.
Quiescence Searching
Since the depth
of the minmax search is limited, problems can occur at the frontier. A move
that may seem great may actually be
a disaster because of something that could happen on the very next move.
Looking at all these possibilites would mean increasing
the ply by 1, which is not the solution, as we would need to extend it
to arbitrarily large depths. The goal is thus to search the tree until
"quiescent" positions are found  i.e ones that don't affect the current
positions too much (most maneuvers in chess result in only slight
advantages or disadvantages to each player, not big ones at once). Hence,
looking at higher depths is important only for significant
moves  such as captures. Consider for example a move in which you capture
the opponent's knight with your queen. If that is the
limit of your minmax search, it seems to be a great move  you receive
points for capturing the opponent's knight. But suppose that
in the very next move your opponent can capture your queen. Then the move
is clearly seen as bad, as trading a queen for a knight is
to your disadvantage. Quiescence searching will be able to detect that
by looking at the next move. Again, it doesn't need to do this
for every move  just for ones that affect the score a lot (like captures).
One important caveat in the quiescence searching algorithm
is that it should only look at moves that became available because
of the
current move being made. Consider the following situation. Your bishop is
threatened by an opponent's pawn, and you have the ability to
capture the opponent's knight with a different pawn. Suppose the algorithm
is looking only 1 ply ahead, and is examining some noncapturing
move. It won't notice that the bishop can be captured in the next
turn. But what happens when it's examining the knightcapturing move
with
quiescence. It will see that the opponent can take your bishop, which will
even out the piece possession, making the move not seem as good.
So it's highly likely that the algorithm would pick a move other than capturing
the knight, thus needlessly losing the bishop in the next turn.
To prevent this, the algorithm must look at ONLY those moves available because
of its own move. Since the opponent's
"pawn captures bishop" was available regardless of whether you capture the
knight or not, it should be ignored.
The following picture illustrates an example of this concept:
Static Board Evaluation Function
When the minmax algorithm gets down
to the leaves of its search, it's unlikely that it reached a goal state (i.e.
a checkmate).
Therefore, it needs some way to determine whether the given board position
is "good" or "bad" for it, and to what degree.
A numerical answer is needed so that it can be compared to other board
positions in a quantifiable way. Advanced chess
playing programs can look at hundreds features of the board to evalaute
it. The simplest, and perhaps most intuitive, look
at only piece possession. Clearly, having a piece is better than not having
one (in most cases at least). Furthermore, the
pieces have different values. A pawn is worth the least; the bishop and
knight are next, then the rook, and finally: the queen.
The king is obviously priceless, as losing it means losing the game.
The additional features that my chess program examines are:
 pawn advancement
How far up the board has each pawn advanced. Reaching the opposite end
is important because it promotes the pawn to a different piece.
 piece mobility (separate for each type of piece)
How many different spaces can the given piece move to?
 piece threats (separate for each type of
piece)
How many of the opponent's pieces are threatened by attack? This includes
checks (which is a threat on the king)
 piece protects (separate for each type of piece)
How many of your own piece are protecting the given piece to prevent it
from being captured without reprecussion?
The total number of unique numbers that sum up to give the total board
score is thus 25. The allowable weights for each
feature are forced to be integers. This allows for faster computations
(as opposed to using real numbers). This isn't a real
loss of generality though, as the scale of numbers used can be large (very
large integers to represent piece possession, and
small ones to represent the other features).
Here is a sample board and a partial analysis of how it would be scored:
Consider only white's side of the board (for a full computation, both sides
would be considered):
Posession:
8 pawns
2 bishops
1 knight
2 rooks,
1 queen
Mobility:
Pawns: 8
Bishops: 8
Knights: 5
Rooks: 4
Queen: 3
King: 3
Threats:
Pawns: 2
Protects:
Pawns: 3
Bishops: 2
Knights: 1
Rooks: 0
Queen: 1
King: 3
Each of the above would be multiplied by the weight in the static board
evaluation function being used.
Optimizing board evaluation functions via genetic
algorithms
While certain aspects of evaluating
a board are obvious (such as piece values  a queen is clearly worth more
than a pawn), other
factors are not as easily determined purely by intuition. How much is a
bishop's mobility worth? How important is it to check the opponent?
Is threatening an enemy's piece better than protecting your own? One can
make relatively good educated guesses to such questions, and
thus develop a decent static board evaluation function, but I was hoping
for a more analytical method. My goal was to attempt to optimize
the board evaluation function by utilizing genetic algorithms to determine
it. One module of the program is capable of running chess tournaments,
where the computer plays against itself with different evaluation functions.
It generates random evaluation functions, which then get mutated or
preserved based on how well they perform in the tournaments.
The core of the tournament algorithm does the following.
It has a set of 10 evaluation functions, and pits them all against each other.
Each
side gets to play both black and white for fairness. Subsequently, it selects
the best five, and generates 5 new ones to replace the worst 5. This
continues for any desirable number of iterations (the default was set to
10). There are two version of the algorithm that were run. One was a
"preservation" one, which kept the best 5 "as is" in between iterations.
The other algorithm was a "mutation" one, which kept 1 of the 5, and
mutated the other 4. Each mutation was between a pairing of some 2 of the
best 5 functions.
Determining the winner of a given game is not always
trivial. For time constraints, each game in the tournament is limited to
50 moves, which
won't necessarily yield an outright checkmate. Also, draws are possible.
Furthermore, for low plys (a ply of 2 was used), it is unlikely for the
computer to ever reach checkmate when playing deterministically against
itself (since there is not endgame database). But the genetic algorithm
requires that there be a "winner" for each game played. The way this
done is by scoring the board position from the perspective of each of the
functions. Most likely they will both has a consensus as to which side has
more points (and hence is winning); however, since obviously each side
has a different evaluation function, there is a small probability in a close
game that each side will think it's winning.
The starting functions weren't completely random.
For instance, the piece possession values were always preset to fixed values,
as those
are well known to be good. The fixed piece possession values were as follows:
Since possession is more important than any other factors,
the randomized weights generated for the other were allowed only to be integers
between 0 and 5.
However, this still allowed for relatively large weights overall  for instance,
a rook could theoretically have a mobility of 14 spaces (7 horizontal and
7 vertical),
so even if it's mobility factor was only 3, and there were two rooks, this
was worth a whopping 14*3*2 = 84.
Unfortunately,
the results of the tournaments weren't as productive as one would expect.
This is because the static board evaluation function often seem to be circular
in nature. By this, I mean the following: suppose you have three different
functions, A, B, and C. It is possible that A beats B, B beats C, and C beats
A. Hence it's impossible to tell which one is "better." Clearly, some functions
in extreme cases are always worse than others  for instance, if we make protecting
bishops and knights worthless, but protecting pawns worth a lot, then the
AI using this function is likely to lose key pieces quickly. But for functions
that are deemed "reasonable," the genetic algorithms in their current form
will fail to determine which ones are better overall. Another problem is
that only a very small subset of all possible functions can be examined.
There are 19 factors in each function, each of which can take on 5 different
values. This yields 5^19 possible functions, even with those limitations.
But in each round of a tournament, only 10 functions are examined, by running
10^2 = 100 games, which takes hours even at low ply levels.
Some general observations, however, both from the tournaments
and from observations of individual matches, can be made. The pieces with
higher values ought to have higher mobility/threats/ weights as well. It
makes sense that threatening a queen is more valuable than threatening
a bishop or a knight. The opposite is true for the "protects" weights. It
doesn't make much sense in protecting a queen too much, because if it gets
killed with anything other than the opponent's queen, killing the capturing
piece is little consolation. Protecting knights and bishops is very valuable,
however. In the current scheme, assigning weights to the pawns' parameters
is often detrimental, as there are 8 of them (multiplying all the weights
by 8), and it may cause an unecessary overuse of the piece by the computer.
Pawn advancement seems to be a sufficent parameter for dictating pawn maneuvers.
Checking (threatening) a king is also valuable, as it can be considered a
"local goal" of the ultimate goal, which is a checkmate. With all these
factors in mind, the default static board evaluation has been set to:

Pawn

Knight

Bishop

Rook

Queen

King

Mobility

0

0

0

0

1

0

Threats

0

1

1

2

5

4

Protects

0

1

1

0

0

0

With a pawn advancement weight of 1.
This is by no means the only decent board evaluation function  many others
work just as well, or better in certain games.
More on the speed efficency of this is discussed in the performace
section.
You can also look at the raw data for a run of the preservation
tournament and the mutation tournament.
Opening Move Database
Many combinations of the first few initial moves on
the board are known to establish a good position on the board. Thus, over
the years, chess masters have developed what is essentially an encyclopedia
of these openings. The program can use this database
at the beginning of play  instead of performing the usual local search,
it simply checks whether the moves performed so far fit into
a given opening strategy, and then playes the appropriate response. The
database contains over 2000 openings, stored in a binary,
allowing for constant time access. Furthermore, a textbased version of
the database is available, which can easily be expanded by
a user to include more openings. The program is then capable of parsing
the text and creating a new binary tree of moves out of it.
For many of the very first moves, there are many possible responses. However,
some are deemed more common (or better) than others,
and the program nondeterministically selects the more common responses
with a higher probability than the less common ones.
You can look at the text version of
the database used by the program.
You can also look how to extend
the database.
Back
to main
page.