performance

Program Performance and Analysis

   It is difficult to quantify all of the aspects of the program, as deciding whether a move is “good” or “bad”
requires expert chess players, and even they could disagree for a particular board situation. The chess program,
however, can be evaluated simply by having people play against it to get a feel for how well it performs. Certain
statistics can certainly be expressed numerically, and those will be discussed at the end of this section.
    Overall the program attains an amateur level of play. In test matches against other people, it can consistently beat
beginner and occasional players, provides a challenge to the average player, and is consistently beat by experienced
human opponents. The testing was done on the default static board evaluation function with a ply of 3 and a quiescence
ply of 5, which provides for a reasonable amount of computer thinking time (on the order of seconds). The program
is also outperformed by existing software, such as GNU Chess. The program will easily take advantages of blatan
t mistakes by a human; it will sometimes make keen moves which an average player will be fooled by; but it will also
sometime make awkward moves -particularly in convoluted board positions mid game - this due to the limited depth the
quiescence is allowed to go to.
    There are a number of reasons to account for the program's shortcomings. The program is implemented in Java, which is
an interpreted language and hence has relatively slow execution times. There is no end-game database, so it does very poorly
in the final phases. This is also because the ply depth is fixed, so even though it could search to deeper plies within the same
amount of time (since there are fewer pieces), it’s not allowed to do so. The flaws of the current end-game strategies are
most evident when the computer plays itself - since the algorithms are deterministic, it will often find itself in a looping situation,
where each side keeps making the same moves back and forth without any progress. Also, the parameters in the static
board evaluation function lose a lot of meaning when there are few pieces left on the board, further degrading the computer's
performance.
    The major bottleneck for the program is evaluating board positions and determining legal moves. The key boils down to
how the board is represented. Currently the program implements the simplest possible board representation (see the algorithms
section for more details). It is particularly time consuming to compute the mobility, threats, and protects factors for each piece
on the board - and this must be done not only at the leaves of the search tree, but also at each branch (for the purposes of
efficient sorting for alpha-beta pruning). Because of all these computations, the depth search is practically limited to 3 or 4 ply
(with quiescence extensions to 2 or 3 more plies) for reasonable computational times (under a minute per move).
    The speed of the program had a large effect on the genetic algorithms I used to attempt to optimize the static board evaluation
function parameters (see the algorithms section for more details on this). Even with a ply of 2 for each player, and a maximum limit
of 50 moves per game, the tournament still took hours to complete. Since only a small finite amount of all possible evaluation
functions was ever present in the matches, it made it impossible to find the optimums. Whereas this was possible for a game like
checkers, the sheer complexity of chess would require literally years of computational time to optimize the parameters via this
method.
    The following tables list some sample running times and number of board evaluations per move made by the program.
They were averaged from 30 move computer vs. computer games, on the default static board evaluation funcion. The program
was run on an AMD Athlon 1.4+ Ghz machine with 256MB of memory. The first two tables list performance without alpha-beta
pruning, and the latter to with it. Clearly, the pruning decreases both running time and the number of board positions needing to
be evaluated. This is particularly evident for higher plies. The tables also demonstrate that having quiescence coupled with
alpha-beta pruning actually not only improves the moves themselves (which can’t be quantified, but can be experienced by
playing the machine and noting it’s a tougher competitor), but can also decrease the number of boards that need to be evaluated
(since extending the search can yield convincingly good moves faster, thus helping alpha-beta cut off more branches).

Standard Min-Max Search

Time per move (milliseconds)	Quiescence 1	Quiescence 2	Quiescence 3	Quiescence 4
Ply 1	20	23	26	42
Ply 2	N.A.	150	130	155
Ply 3	N.A.	N.A.	5456	6247

Boards scored (per move)	Quiescence 1	Quiescence 2	Quiescence 3	Quiescence 4
Ply 1	46	51	51	71
Ply 2	N.A.	952	784	843
Ply 3	N.A.	N.A.	34242	38599

Min-Max Search with Alpha-Beta Pruning

Time per move (milliseconds)	Quiescence 1	Quiescence 2	Quiescence 3	Quiescence 4
Ply 1	20	22	23	34
Ply 2	N.A.	105	114	144
Ply 3	N.A.	N.A.	3510	2438

Boards scored (per move)	Quiescence 1	Quiescence 2	Quiescence 3	Quiescence 4
Ply 1	46	50	51	68
Ply 2	N.A.	613	500	660
Ply 3	N.A.	N.A.	18545	11567

Back to the main page.