Perft

Discussion about development of draughts in the time of computer and Internet.
Post Reply
BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sat Nov 22, 2008 18:05

Couldn't resist to have a look at Perft (on a rainy dark day like this).
So i tweaked my program again and now i reached 22.48 sec. for the initial position.

Bert

TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE » Sat Nov 22, 2008 18:40

For the Woldouby position at level 15, I mesure 9.48". That seems not very good and I have to look for some enhancements in the king move generator.
Gérard

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma » Sat Nov 22, 2008 19:16

BertTuyt wrote:Couldn't resist to have a look at Perft (on a rainy dark day like this).
So i tweaked my program again and now i reached 22.48 sec. for the initial position.

Bert

Nice going, Bert, you beat my time with 0.13s The speed crown goes back to you.

BTW, I implemented your suggestion of generating the (from, dest, captured) triple during move generation, only computing the move when needed. On my pc it was about 5-7% faster than my previous method. But on Ed's pc the timing was 22.97 so somewhat slower than what I had.

Rein

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Mon Nov 24, 2008 21:49

Rein, in case of the Woldouby position my time is 7.75 sec , whereas you score a 6.97.
So there you still hold the record.
Hope I find some time for some further optimizations here.
Keep you posted.

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sat Nov 29, 2008 17:08

Perft remains addictive.
Based on some "side" remarks (thanks to Rein, Gerard and Ed) , i started to change larger parts of my MoveGenerator.
I am still working on it (especially the King Routine is not completely ready).
But the intermediate result I now get for the Initial Board Position is 22.09 seconds ( so i hope to get through the 22 sec. barrier soon).

Keep you all posted,

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sun Nov 30, 2008 11:50

Herewith the Damage Perft status on Sunday Morning (30-Nov):

* Initial Position ( 11 Ply) : Pos. 1665861398 Time 21.86 sec.
* Woldouby (15 Ply) : Pos. 346184885, Time 6.83 sec.

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sun Nov 30, 2008 12:30

I also now included the 2nd Perft test position.

It seems that I still need to do some further optimization, as for this position Rein's program is still faster.

Ply 9, Pos. 1216917193. Time 12.92 sec (Rein measured a 12.11 sec.)

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sun Nov 30, 2008 13:44

Herewith the Damage Perft status on Sunday afternoon (30-Nov) for all 3 test positions:

* Initial Position ( Ply 11): Pos. 1665861398 Time 21.89 sec.
* 2nd Position ( Ply 9): Pos. 1216917193. Time 11.82 sec
* Woldouby ( 15 Ply): Pos. 346184885, Time 6.74 sec.

Bert

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma » Tue Dec 02, 2008 08:06

BertTuyt wrote:Herewith the Damage Perft status on Sunday afternoon (30-Nov) for all 3 test positions:

* Initial Position ( Ply 11): Pos. 1665861398 Time 21.89 sec.
* 2nd Position ( Ply 9): Pos. 1216917193. Time 11.82 sec
* Woldouby ( 15 Ply): Pos. 346184885, Time 6.74 sec.

Bert
congrats Bert! that's really fast. can you also do a run with no-bulk counting?

Rein

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Wed Dec 03, 2008 17:51

Rein, will do so during the weekend, as I have little time to do that in between.
If you could do the same and post already your results for the test positions 1 - 3, I will do the same then sat-sun.

Think this will give a clue regarding the effectiveness of the Move/Unmove routines. Guess your score will be better then mine.

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Wed Dec 03, 2008 19:06

Rein, I found some time in between (have to check if i did not make any errors, and included all new routines).

Herewith the timing of the 3 testroutines (without bulk-counting).

1. 47.75 sec.
2. 26.05 sec.
3. 12.96 sec.

Bert

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Wed Dec 03, 2008 19:08

Sorry, small type, in my previous mail I should say test-positions, not test-routines.

Bert

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma » Sat Dec 06, 2008 10:30

BertTuyt wrote:Sorry, small type, in my previous mail I should say test-positions, not test-routines.

Bert
I have tested (thanks again to Ed for running this on his quad) 4 different routines, both with bulk-counting and without. The differences between these routines are entirely in the data structures and make/unmake methods. The algorithms for finding the legal moves are identical in all cases.

Routine 0) (My original one). A move is represented as a struct with 3 bitboards (delta_black, delta_white, delta_kings). The current position is being updated by 3 XOR operations, both for making and unmaking a move.

Routine 1) (A hybrid between my original one and Bert's routine). A move is represented as in Routine 0, but I also store a position_list[MAX_PLY]. Making a move is as before, but with storage in the position_list, but unmaking is a simple pointer decrement.

Routine 2) (Bert's routine). A move is represented as a struct with 4 fields (from_sq, dest_sq, captured, move_type). Making a move is a switch statement with 8 cases (4 move types times 2 colors) and 4 inlined make_move routines (each 3 lines). Again, a position_list[MAX_PLY] is used for storing make_move results, and unmake is a pointer decrement.

Routine 3) (Ed's routine). A move is represented as a successor position with 3 fields (black, white, kings). Both a make_move and unmake_move routines are pointer increment/decrement. (essentially: the make_move is done during move generation).

Code: Select all

BULK=0	 Rein	hybrid 	Bert	Ed
Initial	40,98	40,37	51,06	33,45
Random	 23,49	23,46	29,87	18,44
Woldouby  10,77	10,71	13,65	 9,24
				
BULK=1	 Rein	hybrid 	Bert	Ed
Initial	23,15	23,32	24,26	22,15
Random	 11,91	12,05	13,29	11,75
Woldouby   6,99	 7,21	 7,47	 6,99
My tentative conclusions from this are the following. Bert may have the fastest perft() with bulk_couting score so far, but my guess is that this is more due to his fast move generation algorithm that to his move_struct data structure. At least it's slower in my implementation (they are a similar percentage slower than Bert's implementation, both with and without bulk_counting, so I guess it's indeed our different move generation algorithms that explain the difference). Ed may not have the fastest perft score out there, but that is mainly due to his lack of ghost squares. Especially without bulk_counting, Ed's list of successors is by far the fastest, and Bert's method seems to be slowest.

Real search trees are different of course than to two extreme cases of generating + making/unmaking all leave nodes (as with no bulk_counting) or making/unmaking none of them (as with bulk_counting). But it seems the less orderd your search trees are, the more attractive Ed's method becomes. The only drawback is that incremental updating of hash keys and material evaluation becomes more expensive (but Ed's hash method has cleverly adapted to that problem as well).

Rein

BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt » Sat Dec 06, 2008 14:36

Rein/Ed, thanks sharing this with us.

I also think that my Move Structure and Move Routine is far from optimal.
Especially without bulk-counting this becomes obvious.

Later today I will post some timing (for the non-bulk counting), where I want to measure the time (within the Perft) for MoveGeneration and the actual Move/Unmove.

So then we can directly compare these results, and I think it will become clear that the Move in my case is the reason for the relatively low performance.

Maybe also good to share the development environment which we use, as some compilers are really good in optimization, so we compare apples with apples.

I use the MS Visual Studio ( 2008 Team-Suite ), with optimization . Think Ed also uses this software, so our results should be in line.

Bert

Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma » Sat Dec 06, 2008 16:25

BertTuyt wrote:Rein/Ed, thanks sharing this with us.

I also think that my Move Structure and Move Routine is far from optimal.
Especially without bulk-counting this becomes obvious.

Later today I will post some timing (for the non-bulk counting), where I want to measure the time (within the Perft) for MoveGeneration and the actual Move/Unmove.

So then we can directly compare these results, and I think it will become clear that the Move in my case is the reason for the relatively low performance.

Maybe also good to share the development environment which we use, as some compilers are really good in optimization, so we compare apples with apples.

I use the MS Visual Studio ( 2008 Team-Suite ), with optimization . Think Ed also uses this software, so our results should be in line.

Bert
You can very easily compute the timings for Move Generation and Make/Unmake by comparing the results of bulk and no-bulk counting. The difference between e.g. perft(11,BULK=1) and perft(11,BULK=0) on the initial position is 1665861398 pairs of Make/Unmake calls. Then you need also the timings for ply=10 for both and then you can deduce the timings for a move_generate() call as well.

Rein

Post Reply