Shortcuts

This section briefly describes some shortcuts which may be used to improve the performance of your program. This is considered advanced material, and is not discussed in any detail. If you are brave and wish to try these techniques, however, a wealth of material is available on the Internet.

Hashing (Transposition Tables)
This technique essentially involves storing the results of searches in memory. Should the same position be reached at another point in the search tree by a different sequence of moves (this is called a transposition), the value of the position can just be looked up in the transposition table instead of being computed by search. The technique is often called hashing because most often a hash value is computed for a given position and then used as the index into a very large array of board positions and scores. In some instances, however, different positions will generate the same hash value. While the hash function should be optimised to reduce this, these "collisions" should be detected and catered for. Although hashing is quite simple in the MiniMax algorithm, it becomes rather complicated in the alpha-beta algorithm, because most position scores will not be exact, but rather an upper bound or lower bound score for a position. Because of this confusion, hashing can be a leading source of bugs in alpha-beta search programs.

Openings Libraries
Because of the complexity of the initial stages of the game, many AI programs use a large database of moves to navigate through the opening. This is called an openings library, or openings book. Production of openings book is most often an enormous amount of effort, involving the advice of expert/grandmaster players, but if done well can give a program a distinct edge going into the middle game. However, many leading programs have suffered ignominious defeat in tournaments when a "bug" in their opening book led them into a losing position. Should you wish to use an opening library in this tournament, it must be your own work and you should be able to demonstrate the methodology (eg manual capture, automated master game analysis, extended-time search etc) you used to create it.

Endgame Databases and Other Tricks
In an endgame in which one side has a small advantage over the other, it usually requires a very deep search to translate this advantage into a win. Often, this depth of search will be beyond the capability of an AI engine which has played into what amounts to a "won" position. This can result in the intense frustration of watching your program making aimless moves in a won position, and ultimately drawing the game.

As a result, programs which might be very capable in the opening and middlegame can end up looking very lame in the endgame. There are at least three possible approaches toward remedying this:

• Use a specialised endgame search with a stripped-down evaluation (looking for wins, loses or draws) to try and get deeper into the game tree. In this way you might be able to get deep enough into the tree to find the necessary sequence to win the game.
• Use a specialised endgame evaluation which has special heuristics for the individual cases posed by the endgame. For instance, you might write endgame code that knows how to corner an opponent's king with your king and rook.
• Use an endgame database. This is an exhaustive (and generally very large) database listing all the possible positions and the best move in each position for a finite number of pieces. As with openings libraries, however, should you wish to use an endgame database, it must be your own work and you should be able to demonstrate how it was produced. Although endgame databases have proved highly effective in Draughts, the vast number of endgame possibilities in Chess means that endgame databases can be far to large to be practical.