Perft

[BertTuyt]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

Bert

[Rein Halbersma]

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]

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]

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