move generation speed

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

move generation speed

Postby Folkert van Heusden » 03 Jan 2012, 10:47

Hi,

What are the move generation speeds one can expect from a current chess engine?
My engine, written in Java, running on a 2GHz system (single thread core2) does 3.9k with validation (check, check mate) and 83k without validation.

explanation:
83/3.9k: number of scenes for which the list of moves was generated. the moves for both white and black are generated. the scene calculated is the starting scene, so with all pieces on their starting field
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands

Re: move generation speed

Postby H.G.Muller » 03 Jan 2012, 13:44

I don't know how you measured this, but simply putting a loop around your move generator to execute it a million or a billion times while timing how long it takes to finish is not a reliable method. It would severely overestimate the speed, because the first few iterations would train the brach-prediction logic for perfect prediction, while in practical move-generation algorithms the execution time is often dominated by mispredictions. Same with caching formemory-intensive move generators (like magic bitboard).

More realistic would be to run a peft(6) using that move generator (not making the final ply, so almost no time is spent on Make/Umake). That would also make it easy to compare with other perft speeds.
User avatar
H.G.Muller
 
Posts: 3167
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: move generation speed

Postby Folkert van Heusden » 03 Jan 2012, 13:53

H.G.Muller wrote:I don't know how you measured this, but simply putting a loop around your move generator to execute it a million or a billion times while timing how long it takes to finish is not a reliable method. It would severely overestimate the speed, because the first few iterations would train the brach-prediction logic for perfect prediction, while in practical move-generation algorithms the execution time is often dominated by mispredictions. Same with caching formemory-intensive move generators (like magic bitboard).


Hmmm true. I could "solve" that somewhat by generating a random setup for each invocation

H.G.Muller wrote:More realistic would be to run a peft(6) using that move generator (not making the final ply, so almost no time is spent on Make/Umake). That would also make it easy to compare with other perft speeds.


Looking at it: is it generating a tree of scenes with all possible moves for a certain depth? Am I required to do evaluation during that?
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands

Re: move generation speed

Postby H.G.Muller » 03 Jan 2012, 14:38

Folkert van Heusden wrote:Looking at it: is it generating a tree of scenes with all possible moves for a certain depth? Am I required to do evaluation during that?


Indeed. It is just a simple way of generating lots of positions, without requiring a lot of extra code. No evaluation or anything.
User avatar
H.G.Muller
 
Posts: 3167
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: move generation speed

Postby Folkert van Heusden » 30 Jan 2012, 22:00

Ok my chess engine now does 44k nodes per second (on average) in the first move black after e2-e4 (5 plies) on a AMD Phenom(tm) II X6 1090T (which is a 6 core cpu running at 3.2GHz with 0.5MB cache according to /proc/cpuinfo).

Java "binary" can be retrieved from http://www.vanheusden.com/DeepBrutePos/
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands

Re: move generation speed

Postby Folkert van Heusden » 02 Jul 2012, 17:28

Folkert van Heusden wrote:Ok my chess engine now does 44k nodes per second (on average) in the first move black after e2-e4 (5 plies) on a AMD Phenom(tm) II X6 1090T (which is a 6 core cpu running at 3.2GHz with 0.5MB cache according to /proc/cpuinfo). Java "binary" can be retrieved from http://www.vanheusden.com/DeepBrutePos/


Current version does:
min. speed: 15788.0, max. speed: 55223.0, average: 41457.0 (nodes per second)
for depth 5 and 30 seconds per move

This night I had it running with depth 7 and max time of 1200 seconds:

Code: Select all
[Event "DeepBrutePos v1.3 versus DeepBrutePos v1.3"]
[Site "Gouda, the Netherlands"]
[Date 2012.7.2"]
[Round "1"]
[White "DeepBrutePos v1.3"]
[Black "DeepBrutePos v1.3"]
[Result "1-0"]

1.Nb1c3 Pe7e5 2.Pg2g3 Pf7f5 3.Ph2h3 Pf5f4 4.Rh1h2 Pf4xg3 5.Ra1b1 Pc7c6 6.Nc3d5 Pg3g2 7.Pd2d4 Pc6xd5 8.Qd1d3 Pb7b5 9.Pa2a4 Pe5e4 10.Rh2h1 Pe4xd3 11.Bc1d2 Qd8f6 12.Ng1f3 Pd3xe2 13.Rb1d1 Pe2xf1=N 14.Rd1a1 Pb5xa4 15.Rh1h2 Nf1xd2 16.Ke1xd2 Pd7d6 17.Ra1g1 Pa7a5 18.Rg1a1 Pg2g1=R 19.Ra1f1 Rg1g5 20.Kd2d3 Rg5g2 21.Kd3e2 Rg2xh2 22.Ke2d1 Ph7h6 23.Rf1e1 Ke8d7 24.Re1e7 Kd7xe7 25.Pc2c4 Qf6xf3 26.Kd1d2 Rh2xf2 27.Kd2e1 Qf3e2  0-1
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 2 guests