The following five approaches were tested:
- Magics
- Hyperbola Quintessence
- Dumb7Fill
- Obstruction Difference
- and an unnamed approach which I simply call "No Headache" (at least the author knows why).
A more realistic test would of course including a "real" static evaluation function, use SEE, improve the search (to reach much bigger search depths) and more. Although I doubt that this would change the results significantly, I plan to repeat the same test after improving the engine significantly. Also other attack-getter implementations are on my ToDo list, including Kindergarten bitboards and a few more.
Test result overview:
Code: Select all
Attack-getter variant Perft NPS -% vs. Magics Search NPS -% vs. Magics
===========================================================================
Magics 1509538 4689055
Obstruction Difference 1305917 -13,5% 4480245 -4,5%
"No Headache" 1290733 -14,5% 4411828 -5,9%
Hyperbola Quintessence 1327537 -12,1% 4380272 -6,6%
Dumb7fill 1174150 -22,2% 4102345 -12,5%
Detailled explanations follow below. A typical question might be "why is 'perft' so slow here, slower than search?". Actually it is much faster than it looks like since the reported number of nodes are the visited nodes, not the counted leaves (due to bulk counting).
Any serious comments and thoughts are welcome, of course.
Test description:
System environment
- PC: Lenovo Laptop W530 running Windows 7 Pro SP1
- CPU: Intel Core i7-3610QM CPU @2.30 GHz
Chess program
- private experimental engine "Attack64", not publicly available
- 64 bit C++ program, compiled with MS Visual Studio 2015 Community, no special optimization flags
- single-core program so far
- board representation based on bitboards, several C++ classes but almost no "sophisticated" C++ language features were used
- implements various different techniques for sliding piece attack generation, switchable by preprocessor define in one single source file
- uses HW instructions for popcnt, bsr, bsf, byteswap (intrinsics)
- focus on correctness, fast development and infrastructure for this test, not on playing strength
- very basic alpha-beta searcher without hash table, any kind of pruning or any search improvements (even no killer moves, no history)
- move ordering based on MVV/LVA, best move of previous iteration is searched first, nothing else
- static evaluation: only material + PST, incremental update in makeMove, parameters not tuned
- effective branching factor still very high
Testing conditions
- goal: compare speed (NPS) of various bitboard attack-getter implementations
- for each attack-getter variant the same, very basic tests were performed:
a) run "Perft selftest" of the engine which includes 18 test positions and takes about 20 seconds (total NPS = total nodes visited / total time)
b) search from starting position of chess to fixed depth of 7 plies (takes about 15 seconds due to the high branching factor)
- both test parts were performed three times, each time after restarting the engine, and the average NPS values were calculated
Test output remarks
a) Perft selftest:
Code: Select all
l= ==> number of leaves counted (perft number needed to check correctness)
n= ==> number of nodes visited (relevant for speed)
t= ==> time in centiseconds
lps= ==> leaves per second
nps= ==> nodes per second (the test result)
Code: Select all
nodes ==> total number of nodes visited during full-width + quiescence search
qsNodes ==> nodes visited during quiescence search only (including depth=0 nodes)
nps ==> nodes per second (the test result)
Code: Select all
Magics (L. Hansen/P. Kannan and others)
=======================================
a) Perft selftest:
l= 755136586, n= 28555328, t= 1896, lps=39827879, nps= 1506082
l= 755136586, n= 28555328, t= 1887, lps=40017837, nps= 1513265
l= 755136586, n= 28555328, t= 1892, lps=39912081, nps= 1509266
b) Search starting position to depth 7:
# nodes=69398003 qsNodes=64228262 nps=4685888
# nodes=69398003 qsNodes=64228262 nps=4692224
# nodes=69398003 qsNodes=64228262 nps=4689054
Obstruction Difference (M. Hoffmann/G. Isenberg)
================================================
a) Perft selftest.
l= 755136586, n= 28555328, t= 2194, lps=34418258, nps= 1301519
l= 755136586, n= 28555328, t= 2195, lps=34402577, nps= 1300926
l= 755136586, n= 28555328, t= 2171, lps=34782892, nps= 1315307
b) Search starting position to depth 7:
# nodes=69398003 qsNodes=64228262 nps=4462894
# nodes=69398003 qsNodes=64228262 nps=4503439
# nodes=69398003 qsNodes=64228262 nps=4474403
"No Headache" (M. Hoffmann)
===========================
a) Perft selftest:
l= 755136586, n= 28555328, t= 2213, lps=34122755, nps= 1290344
l= 755136586, n= 28555328, t= 2212, lps=34138182, nps= 1290928
l= 755136586, n= 28555328, t= 2212, lps=34138182, nps= 1290928
b) Search starting position to depth 7:
# nodes=69398003 qsNodes=64228262 nps=4417441
# nodes=69398003 qsNodes=64228262 nps=4409021
# nodes=69398003 qsNodes=64228262 nps=4409021
Hyberbola Quintessence (G. Isenberg/Aleks Peshkov)
==================================================
a) Perft selftest:
l= 755136586, n= 28555328, t= 2152, lps=35089990, nps= 1326920
l= 755136586, n= 28555328, t= 2151, lps=35106303, nps= 1327537
l= 755136586, n= 28555328, t= 2150, lps=35122631, nps= 1328154
b) Search starting position to depth 7:
# nodes=69398003 qsNodes=64228262 nps=4381187
# nodes=69398003 qsNodes=64228262 nps=4372905
# nodes=69398003 qsNodes=64228262 nps=4386725
Dumb7fill (Author: ?)
=====================
a) Perft selftest:
l= 755136586, n= 28555328, t= 2435, lps=31011769, nps= 1172703
l= 755136586, n= 28555328, t= 2430, lps=31075579, nps= 1175116
l= 755136586, n= 28555328, t= 2431, lps=31062796, nps= 1174632
b) Search starting position to depth 7:
# nodes=69398003 qsNodes=64228262 nps=4101536
# nodes=69398003 qsNodes=64228262 nps=4103962
# nodes=69398003 qsNodes=64228262 nps=4101536