Please comment on my Perft speeds

Code, algorithms, languages, construction...
Post Reply
ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Please comment on my Perft speeds

Post by ppyvabw » Fri Jul 10, 2015 12:18 am

Hi, only posted on here a couple of times before.

I am currently re-writing my engine (She's called Eva after the Bond actress) to use Bitboards and multi-threading. It is my first foray into writing multi-threaded anything, if I'm honest, let alone chess programs.

I am a bit disappointed with the speeds of my Perft function, although my impression is that there is a lot of misinformation regarding perft speeds in regard to different programmers using different metrics, and also some truly outlandish figures that I simply don't believe (like ~10 seconds for depth 7??!!!) So I'm hoping to get some perspective from experts.

Here are my results from the starting position to depth 7:

Perft(1) = 20 in 0.001312 sec
Perft(2) = 400 in 0.001263 sec
Perft(3) = 8902 in 0.004491 sec
Perft(4) = 197281 in 0.023202 sec
Perft(5) = 4865609 in 0.419626 sec
Perft(6) = 119060324 in 10.080624 sec
Perft(7) = 3195901860 in 277.148570 sec

(I have just run these off now, but I set Perft 8 running whilst I went to the pub the other evening and it was done by the time I got back, but Perft 9 had not completed after 24hrs.)

This is just my move generator without updating hashkeys or anything else, and my move generator calculates pseudo-legal moves; it is on a machine with AMD FX-8350 8 core 4MHz processor. As I say, this is my first attempt to write multi-threaded code, and for the Perft function all I did was create a new thread for each child of the root node. I don't know if this was the best approach (in particular, will creating more threads than there are cores for this application slow stuff down?), but it was really just to check that my move generator and position class were thread safe, and obviously to remove bugs, which *I think* I have now done having tested a number of positions.

Thanks in advance!

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Please comment on my Perft speeds

Post by hyatt » Fri Jul 10, 2015 6:12 pm

Here's Crafty's output on a 2.0 ghz MacBook Air (Intel i7 dual core but only using one core, 2012 version of the macbook):

White(1): perft 6
total moves=119060324 time=3.81
White(1): perft 7
total moves=3195901860 time=104.91

You are about 2x slower than Crafty or so. For a part of your program that will be maybe 10% of the total search time when doing a real game-tree search. I would not spend months optimizing 10% of the total code you will be using, yet. At some point, doubling the speed will be a gain. But doubling the speed of perft will improve the speed of the entire engine by 5% (now runs in 1/2 the time of the original 10%)

So far as I know, perft came from early Crafty versions. I used it to debug the early move generation stuff when I went from normal to rotated bit boards. Some have corrupted the idea into a "mini-game" of its own, see how fast it can be pushed. To the point of using hashing to avoid generating subtrees already visited, etc. My perft times above are straight times to generate/make/unmake the moves in the tree, to the depth specified. No optimization tricks used.

ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Re: Please comment on my Perft speeds

Post by ppyvabw » Fri Jul 10, 2015 8:04 pm

Hi,

Thanks very much for your feedback. Given the processor I'm using (I obviously meant to say 4GhZ), I would expect my results to be faster than they are, so I think it's going to be worth spending at least a little time trying to gain some additional speed. Not certain how yet though.

ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Re: Please comment on my Perft speeds

Post by ppyvabw » Fri Jul 10, 2015 9:34 pm

Does crafty generate legal moves? If so, it wouldn't need to make the final move as mine does, as mine only generates pseudo-legal moves. Could that account for my reduction in speed?

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Please comment on my Perft speeds

Post by H.G.Muller » Sat Jul 11, 2015 10:24 am

Qperft does the following on a 2.4GHz i3 (1 core):

Code: Select all

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=           20 ( 0.000 sec)
perft( 2)=          400 ( 0.000 sec)
perft( 3)=         8902 ( 0.000 sec)
perft( 4)=       197281 ( 0.002 sec)
perft( 5)=      4865609 ( 0.073 sec)
perft( 6)=    119060324 ( 1.586 sec)
perft( 7)=   3195901860 (41.509 sec)
Qperft has semi-legal move generation: it does not generate moves with pinned pieces that expose the King, but its King can step in check, and some e.p. captures can also be illegal. So it only makes those moves to check their legality.

ppyvabw
Posts: 29
Joined: Sat Nov 01, 2014 12:51 am
Real Name: Adam

Re: Please comment on my Perft speeds

Post by ppyvabw » Sat Jul 11, 2015 6:40 pm

Hi,

Thanks for your reply.

I am 80% certain my speeds are because I am not bulk counting the horizon nodes, although I could be wrong. When I switch to run on one core, I look to be getting speeds roughly the same order of magnitude as you guys for one depth lower (eg depth 5 in around 2 secs). So I have decided to attempt to adapt my move generator to calculate legal moves and see what happens. It will make the rest of my program simpler, and I would probably attempt it later anyway, so it may as well be now. Will post up some new times when I have it working.

Cheers.

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Please comment on my Perft speeds

Post by hyatt » Sat Jul 11, 2015 10:34 pm

ppyvabw wrote:Hi,

Thanks for your reply.

I am 80% certain my speeds are because I am not bulk counting the horizon nodes, although I could be wrong. When I switch to run on one core, I look to be getting speeds roughly the same order of magnitude as you guys for one depth lower (eg depth 5 in around 2 secs). So I have decided to attempt to adapt my move generator to calculate legal moves and see what happens. It will make the rest of my program simpler, and I would probably attempt it later anyway, so it may as well be now. Will post up some new times when I have it working.

Cheers.

Crafty doesn't bulk count anything either. It is a pure generate followed by make/unmake for each move. To reject illegal moves, at the next ply the first thing done is to generate captures. If the king is captured it returns instantly rejecting the previous move, which now is not counted. On the last ply I make moves and if the side on move is in check after a move, I reject it. But it is a little faster to do the interior nodes as I do.

I am not a big fan of legal move generators, except for one special case. Most moves are not illegal, and checking this during move generation will really slow you down. The one special case is when you start off in check. Now most moves are illegal, and generating only legal moves is faster.

H.G.Muller
Posts: 190
Joined: Sun Jul 14, 2013 10:00 am
Real Name: H.G. Muller

Re: Please comment on my Perft speeds

Post by H.G.Muller » Sat Jul 11, 2015 11:26 pm

Checking legality of each move in the move generator is indeed needlessly expensive,when not in check. In qperft I don't check any moves for legality. The reason it does not generate illegal non-King moves is not that they are somehow rejected after generation. It is because it first detects pinned pieces, and uses a special move-generation code for those, only allowing moves along the pin ray. This actually saves time, because you generate fewer moves.

For in-check positions it uses a special move generator depending on the type of check: double (King moves only), contact (King moves + capture of the checker) or distant (King moves + checker capture + interposition).

Post Reply