Perishing Perft !

[sje]

Code: Select all

[] emp 9
Kd1 10,058,850,787
Kd2 26,426,792,221
Ke2 30,443,022,291
Kf1 9,471,852,362
Kf2 25,682,033,541
Rb1 25,387,312,269
Rc1 23,604,805,814
Rd1 16,224,436,570
Rf1 18,108,686,447
Rg1 26,528,861,442
a3 11,045,902,862
a4 12,585,720,147
h3 11,307,295,010
h4 13,174,065,453
Pathway count to depth nine: 260,049,637,216

[hgm]

Quick Perft is also very fast IIRC but on same Mac (compiled on the fly with a simple gcc -O3) it cannot complete without a hash table and takes 25 secs just to reach perft 7.

Yes, a hash gives an enormous speed-up in perfting, where, unlike alpha-beta trees, you are sure to walk every existing transposition.

Although I do have hashing versions of Quick Perft, they are meant mainly to test the hash-table logic and evaluate replacement policies. I decided against putting those on my web-site, as the intended purpose for this perft was to get reliable counts. And with hashing, there always is the possibility of a key collission...

(Originally I wrote the perft for testing my move-generator speed, of course.)

[Uri Blass]

Quick Perft is also very fast IIRC but on same Mac (compiled on the fly with a simple gcc -O3) it cannot complete without a hash table and takes 25 secs just to reach perft 7.

Yes, a hash gives an enormous speed-up in perfting, where, unlike alpha-beta trees, you are sure to walk every existing transposition.

Although I do have hashing versions of Quick Perft, they are meant mainly to test the hash-table logic and evaluate replacement policies. I decided against putting those on my web-site, as the intended purpose for this perft was to get reliable counts. And with hashing, there always is the possibility of a key collission...

(Originally I wrote the perft for testing my move-generator speed, of course.)

In thoery you are right.
practically I do not know about a single case when my results are wrong.
If you want to be sure of no mistake you can still use hash if you use store all the position in the hash and storing all the position can be done easily by 200 bits for every hash entry.

1 bit for the side to move
4 bits for castling right
3 bits for enpassent square
64 bits for every square to tell if the square is empty.
4 bits for the content of every non empty square(4*32=128 in the worst case)

Uri

[Dann Corbit]

Quick Perft is also very fast IIRC but on same Mac (compiled on the fly with a simple gcc -O3) it cannot complete without a hash table and takes 25 secs just to reach perft 7.

Yes, a hash gives an enormous speed-up in perfting, where, unlike alpha-beta trees, you are sure to walk every existing transposition.

Although I do have hashing versions of Quick Perft, they are meant mainly to test the hash-table logic and evaluate replacement policies. I decided against putting those on my web-site, as the intended purpose for this perft was to get reliable counts. And with hashing, there always is the possibility of a key collission...

(Originally I wrote the perft for testing my move-generator speed, of course.)

In thoery you are right.
practically I do not know about a single case when my results are wrong.
If you want to be sure of no mistake you can still use hash if you use store all the position in the hash and storing all the position can be done easily by 200 bits for every hash entry.

1 bit for the side to move
4 bits for castling right
3 bits for enpassent square
64 bits for every square to tell if the square is empty.
4 bits for the content of every non empty square(4*32=128 in the worst case)

Uri

If you hash the full board as a minimized structure, it goes back to the old encoding method where we tried to squeeze the board as small as possible. I believe Karin's Dad got to about 160 bits.

[Uri Blass]

Quick Perft is also very fast IIRC but on same Mac (compiled on the fly with a simple gcc -O3) it cannot complete without a hash table and takes 25 secs just to reach perft 7.

Yes, a hash gives an enormous speed-up in perfting, where, unlike alpha-beta trees, you are sure to walk every existing transposition.

Although I do have hashing versions of Quick Perft, they are meant mainly to test the hash-table logic and evaluate replacement policies. I decided against putting those on my web-site, as the intended purpose for this perft was to get reliable counts. And with hashing, there always is the possibility of a key collission...

(Originally I wrote the perft for testing my move-generator speed, of course.)

In thoery you are right.
practically I do not know about a single case when my results are wrong.
If you want to be sure of no mistake you can still use hash if you use store all the position in the hash and storing all the position can be done easily by 200 bits for every hash entry.

1 bit for the side to move
4 bits for castling right
3 bits for enpassent square
64 bits for every square to tell if the square is empty.
4 bits for the content of every non empty square(4*32=128 in the worst case)

Uri

If you hash the full board as a minimized structure, it goes back to the old encoding method where we tried to squeeze the board as small as possible. I believe Karin's Dad got to about 160 bits.

It is certainly possible to hash with less bits but I do not see the point in doing it.

If we are talking about safe fast perft then the target is to translate every position to a number that is easy to calculate.

If you spend too much time in calculating the hash number your perft is going to be slower inspite of slightly more positions in the hash.

Uri

[GeoffW]

Thanks guys for the help on the perft bug. It took me longer than it should have, but I have now found the cause of the error.

My initial guess was wrong, it wasnt a promotion bug it was an ep bug.

To remove the taken pawn in the ep capture, I was taking the ep square and using that as the location of the pawn. I had missed a line of code to either add or subtract 0x10 to move 1 rank. Despite quite a few asserts dotted around the code, none of them were triggered due to the bug.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1

raw:14 end:14 secs:0.00
raw:206 end:192 secs:0.00
raw:3672 end:3466 secs:0.00
raw:63792 end:60120 secs:0.02 nps:3987000
raw:1287576 end:1223784 secs:0.33 nps:3925537
raw:25449546 end:24161970 secs:6.78 nps:3753067
raw:553838205 end:528388659 secs:141.59 nps:3911452

I also improved the time to perft 7 quite a bit, but it still looks very poor against some others quoted. (P4 @3.4 GHz)

I am not really interested in doing any specialist tricks for perft as I was using it to just prove the correctness of my code. My perft is simply, generate moves -> make move -> undo move

I would be interested to compare some more perft 7 times, for engines that use a similar non-specific perft loop. If you do post some more times, please quote CPU speed to make it more meaningful.

Regards Geoff

[Allard Siemelink]

raw:553838205 end:528388659 secs:141.59 nps:3911452

I also improved the time to perft 7 quite a bit, but it still looks very poor against some others quoted. (P4 @3.4 GHz)

I would be interested to compare some more perft 7 times, for engines that use a similar non-specific perft loop. If you do post some more times, please quote CPU speed to make it more meaningful.

Regards Geoff

No hashing, make/unmake of last ply and check detection included (AMD opteron@2500Mhz):

Code: Select all

perft 7=528388659 ops in 34.922 seconds  ops/ms=  15131,  ticks/op=  165 

[GeoffW]

Hi Allard

Some engines/times I have just tested on my PC

Trace 123 secs
Crafty 101 secs
Hamsters2 7.5 Secs -> Wow, this must be doing lots of hashing

Your time of 35 secs is very impressive indeed, considering it is not hashing and also calculating checks too.

Could you explain in more detail where and when you are making and unmaking moves. There is possibly a simple optimisation that hasn't occurred to me yet ?

Regards Geoff

[Alessandro Scotti]

Hamsters2 7.5 Secs -> Wow, this must be doing lots of hashing

Hi Geoff,
Hamsters till version 0.3 perform hashing but not "lots of it"!
In fact, I added hashing to perft because it allows me to reach deeper perft depths and test hashing code as well.
However, there are some drawbacks that I didn't like:
- hashing is only useable at leaves because I count perft at each depth with a single search;
- only 32 bits are usable without messing with the standard hash table entry too much.
In Hamsters 0.4 I have rewritten the perft code so that it uses "iterative deepening" and also a dedicated hash table where depth is part of the key. With this I can finally say to use "lots of hashing"! And finally, I get 64 bits for the node count and twice the speed of previous perft as well...

http://www.ascotti.org/programming/chess/perft.cpp

[Alessandro Scotti]

Hamsters 0.4x on my Mac Mini (1.6 GHz Intel Core Duo).

With hashing:

Code: Select all

Hamsters 0.4.1 dev X by Alessandro Scotti
s r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1
p 7
D = 1, N = 14 / 14, T = 0 ms (0 KNps)
D = 2, N = 192 / 206, T = 0 ms (0 KNps)
D = 3, N = 3466 / 3672, T = 1 ms (3672 KNps)
D = 4, N = 60120 / 63792, T = 5 ms (12758 KNps)
D = 5, N = 1223784 / 1287576, T = 51 ms (25246 KNps)
D = 6, N = 24161970 / 25449546, T = 521 ms (48847 KNps)
D = 7, N = 528388659 / 553838205, T = 4567 ms (121269 KNps)

Without hashing (here the perft style of 0.3 would be better but anyway...):

Code: Select all

s r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1
p 7
D = 1, N = 14 / 14, T = 0 ms (0 KNps)
D = 2, N = 192 / 206, T = 0 ms (0 KNps)
D = 3, N = 3466 / 3672, T = 0 ms (0 KNps)
D = 4, N = 60120 / 63792, T = 5 ms (12758 KNps)
D = 5, N = 1223784 / 1287576, T = 91 ms (14149 KNps)
D = 6, N = 24161970 / 25449546, T = 1838 ms (13846 KNps)
D = 7, N = 528388659 / 553838205, T = 37911 ms (14608 KNps)

IIRC the biggest improvement to perft speed came from the pseudo-legality test and also good handling of in-check positions doesn't hurt either.

By comparison, here's Kiwi on the same machine (Kiwi does not use these techniques, so it will try to perform a move just to discover it's illegal):

Code: Select all

setboard r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - 0 1
perft 7
perft: depth=7, FEN=r3k2r/p6p/8/8/8/8/P6P/R3K2R w - - - -
  depth=1, nodes=14
  depth=2, nodes=192
  depth=3, nodes=3466
  depth=4, nodes=60120
  depth=5, nodes=1223784
  depth=6, nodes=24161970
  depth=7, nodes=528388659
perft complete: total=553838205 nodes in 124.220 seconds (4458 KNps)