Elena Fersman and Leonid Mokrushin Algorithmic Project

Title: Heuristic Tree Search Algorithms or One can try Java at chess. (depth=5)

Participants

Elena Fersman [elenaf@docs.uu.se]
Leonid Mokrushin [leom@docs.uu.se]

Aims and Goals

Give an overview of the different traditional tree search algorithms
Show how heuristics are introduced in those algorithms
Create and implement a prototype using tree search techniques

Problem Statement, Applications

"If you can't beat your computer at chess, try kickboxing."
-Anon.

How can a computer play chess? For many people that is an important question. Chess seems like a distinctly human activity requiring intelligence and thought, so how can a computer possibly play chess? Actually computers are now the best chess players on the planet, even though they do it totally blindly and the number of possibilities that need to be explored is astronomically large - approximately 10E+44 (the number of particles in the universe is estimated to be 10E+80).
Applications are limited by people interested in this old as Adam game and students, especially from Uppsala University :)

Known Results - So how do computers play chess?

There are two basic strategies for restricting the number of possibilities. The so-called Shannon type A strategy considers all possible moves up to certain number of plies at which point some criteria is applied. It behaves almost like human chess players do. For the evaluation of a position, an evaluation function assigns to each position a number showing how good or bad this situation is for both of players.
The second strategy, Shannon type B strategy, which limits the number of moves that are considered at each level. A move generator determines a set of reasonably good replies (approximately 8) for each given position.
Some common techniques to improve both strategies have been developed. These techniques have allowed computers with the same basic speed to play significantly better through time.

MiniMax and NegaMax
Alpha-Beta Cut
Opening Books
Endgame Database
Aspiration Search
Transposition Table
Iterative Deepening
Principal Variation Search
Memory Enhanced Test or MTD(f)
Enhanced Transposition Cutoff
Killer Heuristic
History Heuristic
Null move Heuristic
Quiescence Search
Selective Extensions etc.

Techniques Used/Compared/Invented/Eliminated

Used:

NegaScout - is a directional search algorithm for computing the minimax value of a node.

Compared:

Alpha-Beta Cut - is the major refinement for reducing the number of positions that has to be searched. The idea relies on the fact that once a strong reply has been found by your opponent in a given situation, the computer may stop considering ways of improving this situation and focus on moves that avoid such a position altogether.
Principal Variation Search - is a variation of alpha-beta search where all nodes outside the principal variation (alternation of best own moves and best opponent moves from the root to the depth of the tree) are searched with a zero window. The idea is that with perfect move ordening all moves outside the principal variation will be worse than the principal variation itself.
NegaScout - is the further refinement of principal variation search.

Invented:

Improved Random Transposition Cutoff - is the search moves ordering procedure. The idea is to try capturing moves first and then randomize the order of evaluation for the remaining moves.
Game Tree Leaves Evaluation - the function that for each leave of the game tree calculates an integer value representing current situation of the game relative to the tree root. This function takes into account amount of existing pieces, their costs and the costs of attacks of both players.

Programs

Latest Java chess player (executable .jar file, parameter - tree search depth)
You can play it online (You need to install Swing Plug-in for your browser)
Note (SV): If your browser does not support latest plugins, just do the following:
1. ssh -X -l saps01 peg
2. cd public_html/FersmanMokrushin/chess
3. java Chess 3 &
  (meaning that the program will count 3 moves deep)
4. Enjoy (my netscape does not support plug-ins)
Source code

Experimental Data

The following diagrams are available in .ps format:

MaxDepth=3

Conclusions, Comparisons, Problems for Future Research

The narrower the AlphaBeta window, the more cutoffs you get, the more efficient the search is.
Hence algorithms using zero window (such as Pricipal Variation Search and NegaScout) are better than classical AlphaBeta.
It's more efficient to start the search close to it's goal. Heuristics help us to guess this start.
Some specific information, e.g. captures are often good moves, so we try them first.
There is more efficient than NegaScout algorithms - MTD(f) (used in strongest MIT chess program), which stores already seen nodes in memory to get rid of overheads in multiple re-search phases. But it's require additional techniques to be implemented such as hashing and first move guess.