25,161
edits
Changes
Created page with "'''Home * Engines * Fixafan''' FILE:Patent, Mechanical Fan, 1830.png|border|right|thumb|360px| Fan Moved by Mechanism <ref>[https://commons.wikimedia.org/..."
'''[[Main Page|Home]] * [[Engines]] * Fixafan'''
[[FILE:Patent, Mechanical Fan, 1830.png|border|right|thumb|360px| Fan Moved by Mechanism <ref>[https://commons.wikimedia.org/wiki/File:Patent,_Mechanical_Fan,_1830.png Patent drawing] of Fan Moved by Mechanism by [http://ead.lib.virginia.edu/vivaxtf/view?docId=wm/viw00021.xml 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, [https://en.wikipedia.org/wiki/Mechanical_fan Mechanical fan from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Fixafan''', (Fix a Fan)<br/>
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|move ordering]] on the efficiency of [[Alpha-Beta|alpha-beta]] search. Fixafan was written in [[C]] on a [https://en.wikipedia.org/wiki/Solbourne_Computer Solbourne 5/600] dual [[SPARC]] processor machine running [[Unix]]. It used a two-dimensional [[8x8 Board|8x8 board]] array, and, focusing on move ordering, a [[Material|material]] only [[Evaluation|evaluation]], and [[Iterative Deepening|iterative deepening]] with [[Aspiration Windows|aspiration windows]] of ± 2 pawns <ref>[[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]], advisor [[Monroe Newborn]]</ref>.
=Move Ordering=
Eight [[Move Ordering|move ordering]] heuristics were implemented and examined, in isolation and combination - beside the chess dependent [[MVV-LVA|MVV/LVA ]] ordering of [[Captures|captures]], seven variations of the [[Killer Heuristic|killer heuristic]], aka [[Countermove Heuristic|countermove heuristic]] or [[History Heuristic|history heuristic]], including the [[Best Move|best move]] probed from the [[Transposition Table|transposition table]] (BEST_TT). Opposed to static move ordering applied during [[Move Generation|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 [[Move List|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|node]] counts, CPU time, [[Branching Factor|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 [[Beta-Cutoff|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 Node|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=
* [[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]], advisor [[Monroe Newborn]]
=External Links=
* [https://en.wikipedia.org/wiki/Fix Fix from Wikipedia]
* [https://en.wiktionary.org/wiki/fix fix - Wiktionary]
* [https://en.wikipedia.org/wiki/Fan Fan from Wikipedia]
* [https://en.wikipedia.org/wiki/Fan-out Fan-out from Wikipedia]
* [https://en.wiktionary.org/wiki/fan fan - Wiktionary]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[FILE:Patent, Mechanical Fan, 1830.png|border|right|thumb|360px| Fan Moved by Mechanism <ref>[https://commons.wikimedia.org/wiki/File:Patent,_Mechanical_Fan,_1830.png Patent drawing] of Fan Moved by Mechanism by [http://ead.lib.virginia.edu/vivaxtf/view?docId=wm/viw00021.xml 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, [https://en.wikipedia.org/wiki/Mechanical_fan Mechanical fan from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]
'''Fixafan''', (Fix a Fan)<br/>
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|move ordering]] on the efficiency of [[Alpha-Beta|alpha-beta]] search. Fixafan was written in [[C]] on a [https://en.wikipedia.org/wiki/Solbourne_Computer Solbourne 5/600] dual [[SPARC]] processor machine running [[Unix]]. It used a two-dimensional [[8x8 Board|8x8 board]] array, and, focusing on move ordering, a [[Material|material]] only [[Evaluation|evaluation]], and [[Iterative Deepening|iterative deepening]] with [[Aspiration Windows|aspiration windows]] of ± 2 pawns <ref>[[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]], advisor [[Monroe Newborn]]</ref>.
=Move Ordering=
Eight [[Move Ordering|move ordering]] heuristics were implemented and examined, in isolation and combination - beside the chess dependent [[MVV-LVA|MVV/LVA ]] ordering of [[Captures|captures]], seven variations of the [[Killer Heuristic|killer heuristic]], aka [[Countermove Heuristic|countermove heuristic]] or [[History Heuristic|history heuristic]], including the [[Best Move|best move]] probed from the [[Transposition Table|transposition table]] (BEST_TT). Opposed to static move ordering applied during [[Move Generation|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 [[Move List|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|node]] counts, CPU time, [[Branching Factor|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 [[Beta-Cutoff|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 Node|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=
* [[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]], advisor [[Monroe Newborn]]
=External Links=
* [https://en.wikipedia.org/wiki/Fix Fix from Wikipedia]
* [https://en.wiktionary.org/wiki/fix fix - Wiktionary]
* [https://en.wikipedia.org/wiki/Fan Fan from Wikipedia]
* [https://en.wikipedia.org/wiki/Fan-out Fan-out from Wikipedia]
* [https://en.wiktionary.org/wiki/fan fan - Wiktionary]
=References=
<references />
'''[[Engines|Up one Level]]'''
