Perft 12 in progress

[sje]

I am currently working on calculating Perft(12) for the initial array. My first attempt at this failed a verification test due to false positive transposition table matches when using hash signatures with an effective 60 bit length. I have since added 64 bits to the signature length for an effective total of 124 bits and have restarted the attempt.

I say "effective length" as the base length in the first attempt was 64 bits, but nine are dropped to make way for storing draft and entry occupation data and several are added due to using the otherwise unused bits for generating a transposition table entry index. The replacement scheme fiddles with the length, eating two or three bits. Two tables are used; one for each color and that adds a bit.

With some 124 bits in play, I think the odds of a false positive from a hash space collision are about the same as disruption from cosmic rays.

Results so far with Perft(11) on nine of the 20 ply one subtrees:

Code: Select all

Na3 2,101,612,201,748,156
Nc3 2,731,501,636,365,779
Nf3 2,704,348,041,301,604
Nh3 2,133,059,306,892,947
a3 1,825,396,176,881,632
a4 2,572,564,331,526,038
b3 2,407,514,849,528,875
b4 2,412,357,918,298,534
c3 2,751,675,948,507,059

[sje]

For the record, there has already been a claim to the calculation of Perft(12) for the initial chess array. It appeared in this forum back in October 2006 and is referenced at:

http://wismuth.com/chess/perft12.txt

Paul Byrne reported his value of 62,854,969,236,701,747 which took a few months of elapsed time. I have been unable to locate any earlier claim, and more importantly, I can't find any verification either. The lack of verification is the main reason for my decision to give it a try myself and is also why I'll provide all twenty ply 1 subtotals along with 20 ply 2 sub-subtotals for each ply 1 subtotal. These numbers will better allow others to verify my attempt.

Example:

Perft([Na3], 11) = 2,101,612,201,748,156

To build the above, the 20 Perft([Na3 x], 10) subtotals are:

Na6 70,164,254,747,876
Nc6 91,710,661,510,033
Nf6 90,221,933,390,595
Nh6 71,156,085,799,766
a5 87,112,726,457,222
a6 61,211,806,080,331
b5 80,265,837,110,112
b6 79,486,175,018,475
c5 101,956,640,896,317
c6 92,057,453,487,994
d5 213,782,760,833,766
d6 152,569,571,614,918
e5 245,413,911,922,747
e6 240,156,512,798,893
f5 68,386,284,663,519
f6 51,715,576,377,483
g5 74,156,576,416,427
g6 82,992,220,161,143
h5 86,892,547,773,711
h6 60,202,664,686,828

[LucenaTheLucid]

Question from a non-programmer here. I guess perft 12 is just a calculation of all possible positions up to depth 12? If so why is this beneficial?

I know that perft is often used to test bugs but why not just go to depth 8 or something easier? Why go any higher?

[Dann Corbit]

Question from a non-programmer here. I guess perft 12 is just a calculation of all possible positions up to depth 12? If so why is this beneficial?

I know that perft is often used to test bugs but why not just go to depth 8 or something easier? Why go any higher?

Well, there can be some esoteric reasons (e.g. promotions and attempted castling across check and other things like that will become much more prevalent in later plies (it is only 6 full moves from the origin by ply 12).

But mostly I think it is just for fun like this project:
http://www.albert.nu/programs/dperft/default.asp

Personally, I would like to have a fast perft that also spits out any mate positions that it encounters as EPD records.

[sje]

From the chess initial array, black queen side castling doesn't occur until ply ten. Some move bugs won't show until a full move after the buggy move is made, so that's two additional ply giving twelve ply total depth. Eight ply is not enough.

[Daniel Shawul]

I guess it is an exercise in distributed computing. Larger depth perfts
would take ages to compute on a single core.

Also larger depth may reveal unexpected bugs. For instance for checkers, from the starting
position, it is necessary to do perft depth=12 to be sure of no bugs related to multiple captures.
You may use different set of starting positions for each feature of the move generation that could
cause bugs but using the starting position seems natural. This requires large depths to cover all
cases f.i promotions in chess.

But I would say it is more of a programing challenge. I guess improving parallel computation
is one goal. Why would people compute PI to billion decimals ?? In my field it 3.14 is good enough

It is also fun !

[Evert]

Question from a non-programmer here. I guess perft 12 is just a calculation of all possible positions up to depth 12? If so why is this beneficial?

I know that perft is often used to test bugs but why not just go to depth 8 or something easier? Why go any higher?

I don't think perft 12 from the start position is all that useful. I usually only go up to perft 5 or 6, which tells me if I have en-passant captures working correctly. Greater depths will let you test whether castling works correctly and whether you get all promotions (including minor promotions) correctly. I'd personally test those with perft scores from more developed positions though.

[sje]

Personally, I would like to have a fast perft that also spits out any mate positions that it encounters as EPD records.

This is fairly easy to do. In fact, while testing the all new CIL toolkit I had one of the emp routines (emp = "enumerate movepaths", my name for "perft") output the list of moves for each mate found. A one line change will produce a FEN record instead. EPD isn't in there yet; I'm doing the PGN stuff first.

I'll post CIL progress notes from time to time. A sneak preview of the toolkit at an very early alpha stage can be had at:

https://public.me.com/chessnotation

Directory: ChessInLisp

The ReadMe file points the way to free Common Lisp processor goodness.

[sje]

A couple more depth 11 subtotals:

Code: Select all

c4 3,119,892,147,087,203
d3 4,588,998,634,450,632

Nine more to go.

[sje]

Having a perft/emp routine can be of great help during the development process of a chess program, as it is a good place to bulid a hook for routine verification.

Example: Say that you have written a program and that you are considering adding a routine to generate only checking moves. To test the new code, the emp routine provides a hook where both the old code (generate + filter) and the new code (generate only checks) are called with the results compared. The modified emp routine can be set to run overnight on the chess initial array or (better) a suite of different positions. When the old and new versions of the code each produce the same result when tested on billions of positions, that's good evidence that the new, improved routine works as intended.