OpenChess

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!

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.

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.

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?

Qperft does the following on a 2.4GHz i3 (1 core):
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.

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.

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.

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).