Move Generation Speed

[Dan Honeycutt]

From the Attack Table thread (which got so long and drifted far afield from attack tables I decided to start anew):

Uri said:

Movei during a game generate between 10 and 15 million moves per second on A3000.

Reinhard replied:

wow!

First, Uri - how do you measure that. Do you take a perft value and back out time spent making and unmaking moves?

Second, Reinhard - Your move generator seems to be faster. You posted a perft from the start position of 119060324 nodes in 4.9 sec - thats about 24 million moves per sec plus you have make/unmake time. Why wow? What am I missing?

Third, anybody - Both Uri and Reinhard (as I understand it) are including scoring information with the moves as they generate them. Anyone have data on move generation speed for move generators that do nothing but generate moves? Maybe Vincent's worlds fastest move generator.

Dan H.

[Reinhard Scharnagl]

Hi Dan,

I said "wow!" because of the very high number of moves during a GAME (which I interpreted as during usage of the whole engine). During a PERFT test Smirf would generate about 23 million moves a second (P4 2.8 GHz), that means, that during a game it would be far away from Uri's figure.

If you would be interested in generated preevaluated and sorted moves' performance (at 8x8 and 10x8 boards): here Smirf is generating about 22 million moves depending on the actual situation, especially whether being inside a check threat or not. See for that some test data outputs: http://www.chessbox.de/Down/CRC_Test_02.txt

Reinhard.

[Reinhard Scharnagl]

Hi again Dan,

you seem to be interested in generating net moves results. That I could not provide this moment. But I could give you some examples in generating unsorted moves with only piece capturing preevaluation. Such moves could be generated by Smirf at a rate of about 38 million moves a second (P4 2.8 GHz). For that see: http://www.chessbox.de/Down/CRC_Test_02a.txt

Reinhard.

[Uri Blass]

Hi Dan,Thanks for the new thread(for some reason it seems that I skipped Reinhard's post)

To your question:

I can measure the number of generated moves simply by adding the number of legal moves to a counter after every time that I generate moves and I found that in the opening position it is slightly more than 10,000,000 nodes per second(in the middle game it is probably bigger because there are more legal moves to analyze when only in simple endgames it may be smaller).

In big majority of the cases I generate all the moves after making moves so if I make more than 500,000 moves per seconds in the opening position and movei on fast hardware does it then it means that I generate more than 10,000,000 moves per second.

Note that I calculate evaluation function only for moves that I make and not for moves that I generate.

Movei is not a fast searcher based on the number of moves that it makes or the number of positions that it evaluates..

I simply generate all moves immediately after making them in almost every case.
I mentioned not having function to generate only captures as one reason
for the big number.
Another reason is that I do not use hash for pruning but only for order of moves andI find if a move is in the hash simply by generating all moves and having a loop.

I guess that smirf is faster than movei and Reinhard has nothing to worry
about speed.

I think that it is possible that he care too much about speed optimzation and there are more important things to care about.

Being twice faster give only something like 50-70 elo when better algorithm can give a lot more than it.

Uri

[Reinhard Scharnagl]

Hi Uri,

you are right, speed (especially the move generator) is not that important. But just completing my first real engine (long time ago I had written a Z80 based very poor chess program), I am happy with such milestone results. But not because of its fast move generation alone, more because I find my data structures verified as enabling a good performance.

Reinhard.

[Dan Honeycutt]

Thanks Uri and Reinhard.

It seemed like there was some "apples" and "oranges" comparisons. On decent hardware we're all seeing:

1) Raw moves generated in the 10's of millions.
2) moves generated, made, and unmade (perft) in the millions.
3) moves searched in the 100's of thousands.

I agree with both of you that move generation speed is not of great consequence. My move generation is not fast but that's not what costs me time - king safety is. I take out king safety and, bang, another ply. But playing strength drops noticably.

I'm getting ready to write just a move generator (plus make/unmake) for the purpose of reading and following a pgn file. For this application speed is completely unnecessary. So, as is logical, I thought I'd try to make it as fast as I could. I want to do something different than my bitboard generator just to play around with it. So I'm looking for ideas. I may email Vincent.

Dan H.

[Reinhard Scharnagl]

Hi Dan,

I'm getting ready to write just a move generator (plus make/unmake) for the purpose of reading and following a pgn file.

so it would be good (as always) to have a legal move only generator including information of captures, check threats, promotions etc. within the generated moves (as Smirf is yet and only doing).

I have come quite far with my Smirf GUI, which is yet able to read, write and comment 8x8 and 10x8 games (PGN based), but I have no built in knowledge therein on legal moves. The GUI requests such data from the engine. That is nearly the same type of information, you would need for your intentions. What do you think on pseudo legal move generators?

Reinhard.

[Dan Honeycutt]

Hi Reinhard:

To rad a pgn (and verify that it's not corrupt) I'll need capture, check, promotion etc - everything that a SAN move would say. For the pgn reader I'll end up with only legal moves - I don't know if I'll do legal generation or psudo-legal and test each one.

Regarding psudo-legal vs legal in general: I presently do legal move generation. Before generating moves I call a function that produces a map of who is pinned and where they can go (squares from the king to and including the pinnor). The mechanics of this function are much the same as my in-check function. Just looking at the code I'd say my pin set function costs about 3 in-checks. So if I have a branching factor of 3 it's break even - I spend 3 in-checks to generate and I save three in-checks not having to test the moves.

Dan H.

[Reinhard Scharnagl]

Hi all,

to come back to this new thread topic: how much faster could a move generator be made when changing from C/C++ to Assembler? And which languages are you using for your engine? Is your engine written in only one unic language? Which influence has the chosen compiler? What are your experiences with different compilers?

Reinhard.

[Uri Blass]

I know nothing about assembler and use no assembler.

I use microsoft visual C++6 during developement but Dan Corbit also help me by using a faster compiler to compile movei.

Uri

[Dan Honeycutt]

Hi Reinhard:

how much faster could a move generator be made when changing from C/C++ to Assembler?

Back in ~1984 I wrote, by today's standards, a fairly simple chess program 100% in x86 assembly. I don't care to go back. A profiler is going to have to show me a major bottleneck that I can't get rid of with C/C++ before I'll even think about assembly. A move generator is not it.

Dan H.

[Dan Honeycutt]

I should add - I do this for fun. To Gerd Isenberg assembly programming may be fun but for me it's more like torture.

Dan H.

[Ralf Schäfer]

Hi all,

well, I don't know how much faster move generation can be when switching from c++ to assembler, but when Spike uses Java instead of c++ then he reaches maybe 55% - 60% of the speed. It seems that Java isn't longer that slow as many expects.

best
Ralf

[Dan Honeycutt]

I wrote:

I may email Vincent.

I emailed Vincent and he kindly and promptly sent me diep's move generator. I can only surmise that it must be fast; it's some of the strangest looking code I've ever seen. If he didn't use terms like pawn and bishop you'd never guess that this code had anything to do with the game of chess.

This is going to take some time to ingest.

Dan H.

[Reinhard Scharnagl]

Hi Dan,

partially I would agree: using x86 based assembler is a kind of an act of penance. But I have some experiences with 68xxx which has been interesting and also with an ARM RISC CPU at an Acorn, which has been a very productive experience. I suppose PowerPC and successors also to be very interesting CPUs for using assembler.

Programming with assembler would need much more time than with C++. So it would need something like a sponsor to become able to work continuously on such an assembler project. But I would not be afraid to start such an exotic thing - nevertheless there seems to be only a very small interest in supporting chess programmers today. Thus things will stay as they are, and I still use C++.

Reinhard.

[Dan Honeycutt]

Hi Reinhard:

Going all the way backto the 8 bit days (I started with Z80 assembly with my Radio Shack Trash-80) I did a little bit with 68xx processors, which I liked. Never did any 68xxx but if I were thinking about getting serious with assembly I look into a Power PC. But I think I'll stay with C. Back then you could tell how fast your code would be by looking at the clocks for the instructions you used. Now the cpus are so complex I wouldn't know if my code was any good or not. It would probably end up being slower than C with a good optimizing compiler.

Dan H.

[Reinhard Scharnagl]

Hi Dan,

well Z80 - I remember myself programming at a Sharp MZ80K - that times are really gone.

Concering x86 CPUs you may be right with optimizers. Borland C++ Builder 6 is giving a very slow result compared with MS Visual C++, but I have had inverse results, too.

But such nice RISC CPUs as the StrongARM and its successors are really inviting to be fed with assembler sources :-) .

Reinhard.

[Zach Wegner]

I know a bit of x86 assembly, probably not enough to write a chess program though. I do not know any PowerPC assembly and I hate the GCC assembly syntax(inline assembly) so I do not use it. C code is also much easier to read and modify, not to mention the portability.

Regards,
Zach

[Reinhard Scharnagl]

Hi adrewfan (?),

why using a pseudo name?

Speed also depends on the used engine (CPU). All results with more than 5 million legal moves a second should be regarded as good (my opinion). But to become comparable to my values, they have to contain some more info like being a check threat etc.. Here are my values to this position:

Code: Select all

FEN: rnb2rk1/pp3pbp/4p1p1/q1p5/3PP3/2P1BN2/P2Q1PPP/2R1KB1R w K - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10
8 |[r][n][b]:::   [r][k]:::| (Compilation: Oct 22 2004)
7 |[p][p]:::   :::[p][b][p]|
6 |   :::   :::[p]:::[p]:::| Perft Testseries
5 |[q]   [p]   :::   :::   |
4 |   :::   <P><P>:::   :::| (without caching)
3 |:::   <P>   <B><N>:::   |
2 |<P>:::   <Q>   <P><P><P>| Smirf Test No.: 00
1 |:::   <R>   <K><B>:::<R>|
=>+-a--b--c--d--*--f--g--*-+ Break Time 2.0 Sec.

Ply     Nodes    all (x)   (e.p.)    all (+) all (++)    Promot.    Castl. Sec.
-------------------------------------------------------------------------------
1          34          1        0          0        0          0         0    0
2        1110        141        0          9        0          0         0    0
3       39065       2257        2          9        0          0       160    0
4     1314340     166220        0      25701        0          0         0  0.1
5    47523000    3679045     3679      85390        0          0    276748  1.7
6  1619546990  208394549     4629   44362501     9373          0         0 62.4
-------------------------------------------------------------------------------

FEN: rnb2rk1/pp3pbp/4p1p1/q1p5/3PP3/2P1BN2/P2Q1PPP/2R1KB1R w K - 0 1

  +-a--b--c--d--e--f--g--h-+ MS Vis. Studio C++ Vers. 13.10
8 |[r][n][b]:::   [r][k]:::| (Compilation: Oct 22 2004)
7 |[p][p]:::   :::[p][b][p]| Testscenario (unsorted):
6 |   :::   :::[p]:::[p]:::| Move generation
5 |[q]   [p]   :::   :::   |
4 |   :::   <P><P>:::   :::| Smirf Test No.: 00
3 |:::   <P>   <B><N>:::   |
2 |<P>:::   <Q>   <P><P><P>| Move Count:  34*750000
1 |:::   <R>   <K><B>:::<R>| per Second:  42929292
=>+-a--b--c--d--*--f--g--*-+ Time:        0.594 sec

  0.000 a2-a4    0.000 a2-a3    0.000 c3-c4    0.000 h2-h4    0.000 h2-h3
  0.000 g2-g4    0.000 g2-g3    0.000 d4-d5    0.938 d4xc5    0.000 e4-e5
  0.000 Nf3-h4   0.000 Nf3-g1   0.000 Nf3-e5   0.000 Nf3-g5   0.000 Bf1-a6
  0.000 Bf1-b5   0.000 Bf1-c4   0.000 Bf1-d3   0.000 Bf1-e2   0.000 Be3-h6
  0.000 Be3-g5   0.000 Be3-f4   0.000 Rc1-a1   0.000 Rc1-b1   0.000 Rc1-d1
  0.000 Rc1-c2   0.000 Rh1-g1   0.000 Qd2-d1   0.000 Qd2-d3   0.000 Qd2-b2
  0.000 Qd2-c2   0.000 Qd2-e2   0.000 Ke1-d1   0.000 Ke1-e2

Even because that position does not own any checking move, I could not decide here, whether your generator is providing such information.

Reinhard.