Fixafan

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Fixafan

Fan Moved by Mechanism [1]

Fixafan, (Fix a Fan)
the thesis chess program by Eric Thé, published in appendix D of his 1992 Master's thesis as subject of an analysis of move ordering on the efficiency of alpha-beta search. Fixafan was written in C on a Solbourne 5/600 dual SPARC processor machine running Unix. It used a two-dimensional 8x8 board array, and, focusing on move ordering, a material only evaluation, and iterative deepening with aspiration windows of ± 2 pawns [2].

Move Ordering

Eight move ordering heuristics were implemented and examined, in isolation and combination - beside the chess dependent MVV/LVA ordering of captures, seven variations of the killer heuristic, aka countermove heuristic or history heuristic, including the best move probed from the transposition table (BEST_TT). Opposed to static move ordering applied during generation time, dynamic move ordering heuristic reorders remaining moves after searching early ones, by looking whether new killers appeared two plies ahead, still to try inside the movelist, now considering next.

Experiments

The experiments were made using the 24 positions of the Bratko-Kopec Test searching on the depth of 6 or 7 (midgame) and 9 (endgame) plies, comparing performance by measuring of node counts, CPU time, average branching factor (ABF), and a "Killer average" (KA), which is the ratio of number of "kills" versus number of reordered nodes per level. A kill is when a cutoff occurs within the subset of moves reordered at a node. If a certain heuristic or combination of heuristics reordered N moves at the front of a node's movelist, and a cutoff occurs after searching one of the N moves, then a kill is registered. One should consider the fact that Fixafan evaluates only material balance at all leaf nodes, and therefor the last level of all iterations is not expanded and searched thoroughly as with all previous levels. Instead, the highest capture is immediately taken as the best move and all other moves are ignored. The consequence of this shortcut is that the ABF for the last level of every iteration can never exceed 1.00.

Results

BEST_TT was clearly the most effective heuristic reducing the tree size by 70% and search time by 75% on average compared to a null test (no ordering heuristic at all, quiet sliding moves generated before captures), followed by MVV/LVA captures, which also raises the efficiency when combined with any of the other heuristics not dependent on the properties of chess. The history heuristic consumed just 4.5% less execution time than the null test. Although HH had a high Killer average, most of the cutoffs seemed to happen too late to be effective. Small improvements in BEST_TT + Captures were noticed when complemented with countermove and the level dependent killer heuristic. Using two killer slots was slightly advantageous, while dynamic re-ordering reduced the tree size with disappointing time results.

Publications

External Links

References

  1. Patent drawing of Fan Moved by Mechanism by James Barron, November 27, 1830. The original drawing for this patent was destroyed by a fire in the Patent Office in 1836. The coverage date is the original patent date. This drawing is a restoration created in 1837 or shortly thereafter, Mechanical fan from Wikipedia, Wikimedia Commons
  2. Eric Thé (1992). An analysis of move ordering on the efficiency of alpha-beta search. Master's thesis, McGill University, advisor Monroe Newborn

Up one Level