Experiments with crafty perft command
Guy Macon
1 through 8 in order to calculate how many possible moves there are.
From the crafty docs:
| perft <depth> is used to confirm that the move generator and bitmap
| operators are working properly. The command starts with the current
| position and counts the moves it can generate, make, and unmake.
| Many programs run this command from a standard position to make
| sure their move generator does not miss generating odd moves like
| en passant captures and promotions. Running perft from a standard
| position can also confirm that the make/unmake code correctly
| updates the board so that the totals remain constant across
| different machines and programs, since no alpha/beta or evaluation
| things are done. If <depth> is greater than 5 or 6, it will take
| a *long* time, since this is basically a minimax tree traversal
| that will visit *every* node within the <depth> search horizon.
Here is the log of my run, with comments after:
-----------------------------------------------
EPD Kit revision date: 1996.04.21
unable to open book file [./book.bin].
book is disabled
unable to open book file [./books.bin].
Crafty v17.14
White(1): perf
generated 20000000 moves, time=14.25 seconds
generated 1403410 moves per second
White(1): perft 1
total moves=20 time=0.00
White(1): perft 2
total moves=400 time=0.00
White(1): perft 3
total moves=8902 time=0.02
White(1): perft 4
total moves=197281 time=0.54
White(1): perft 5
total moves=4865609 time=13.13
White(1): perft 6
total moves=119060324 time=331.83)
White(1): perft 7
total moves=-1099065436 time=8557.78
White(1): perft 8
total moves=-900366964 time=230010.11
-----------------------------------------------
Observations/comments:
I asked a question on the crafty mailing list
about modifying crafty to use 64 bit variable so that
perft doesn't return negative numbers for perft 7 and
perft 8.
Each ply takes about 25 times longer to compute and has
about 25 times more moves. (I wonder for how many plies
this will hold true?)
perft 2 total moves = 400 time = 0.00 ( Time * ??, Moves * 20 )
perft 3 total moves = 8902 time = 0.02 ( Time * ??, Moves * 22 )
perft 4 total moves = 197281 time = 0.54 ( Time * 2?, Moves * 22 )
perft 5 total moves = 4865609 time = 13.13 ( Time * 24, Moves * 24 )
perft 6 total moves = 119060324 time = 331.83 ( Time * 25, Moves * 24 )
perft 7 total moves = -1099065436 time = 8557.78 ( Time * 26, Moves * ?? )
perft 8 total moves = -900366964 time = 230010.11 ( Time * 27, Moves * ?? )
Here are my estimates for number of moves, for perft 7 and higher,
assuming * 25 for each ply:
perft 7 = 120,000,000
perft 8 = 3,000,000,000
perft 9 = 75,000,000,000
perft 10 = 1,875,000,000,000 = 1.9e+12
perft 11 = 4.7e+13
perft 12 = 1.2e+15
perft 13 = 2.9e+16
perft 14 = 7.3e+17
perft 15 = 1.8e+19
perft 16 = 4.6e+20
perft 17 = 1.1e+22
perft 18 = 2.9e+23
perft 19 = 7.2e+24
perft 20 = 1.8e+26
Here is the time variation from run to run (about 10%)
perft 5 time=
13.13 13.08 13.05 13.06 13.06 13.09 13.27 13.11 14.06
13.06 13.20 13.53 13.68 13.61 13.28 13.32 13.16 13.12
13.14 13.83 13.51 13.49 13.16 13.19 13.26 13.97 14.32
Here are the run times on 233Mhz Pentium MMX w/64MB RAM:
perft 6 took 5.5 minutes
perft 7 took 2.4 hours
perft 8 took 2.6 days
perft 9 will take about 2 months
perft 10 will take about 120 years.