What is the best known speed of move generation?

[Uri Blass]

Movei 449 on 2.2 GHz does perft 6 in 4.673 seconds and perft 7 under two minutes.

Code: Select all

new
perft 5
perft(5) = 4865609,time=203
perft 6
perft(6) = 119060324,time=4673
perft 7
perft(7) = 3195901860,time=117708

Uri uses hashing with perft.

Note that
I changed it not to use hash with that version when I wanted to check the new move generator that also mark checks and I did not change it back.

I also disabled some speed trick to calculate perft by only calculating number of moves in the last ply without generating them so
If you want fast perft you need the public version.

Uri

[friedeks]

To get a more complete picture, some results from my experimental Java engine:
Athon X2 @ 2200MHz, JDK 1.6, JRockit JVM:

Full move generation with makeMove in leaf nodes:
Perft 6 : rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 0
Nodes: 119060324 Time 26,51s knps: 4491

Move generation without makeMove in leaf nodes:
Perft 6 : rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 0
Nodes: 119060324 Time 9,79s knps: 12166

Move generation without makeMove in leaf nodes and caching:
Perft 6 : rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 0
Nodes: 119060324 Time 3,93s knps: 30302

[hgm]

Wow! Perft 8 in under 2 minutes.

Perhaps I should stress that this is (mostly) without making / unmaking the last ply, just generating moves and then lookig at the move-stack pointer to see how many there are. (That is what I mean by 'bulk counting'.) Only King moves and e.p. captures are actually made to check them for legality.

The version that is on my website now does not update a hash key during MakeMove(), as it seemed a bit unfair to require the update of a hash key if there is no hashing. It does test if it should update one, though (and if hashing is switched on, then immediately does the probe after update).

I considered not making the last ply a more meaningful speed measure for comparing with engines. In a search tree, there are two kind of end leaves: those where the evaluation is below alpha, (in which case you will do a move generation to get captures to try in QS), or where it is above beta (where in most cases you would not make the move to it, but prune it in the node below for futility). So the typical end leave does move or capture generation, and then comes to the conclusion that it doesn't want to make any of the generated moves, because they are all futile or bad captures.

So you typically end the tree with move generation, with 1 Make / Unmake per MoveGen for getting in the node, rather than ending with ~40 Make/Unmakes per MoveGen. A perft that makes the last ply thus puts way to much emphasis on the speed of the Make/Unmake, and far too little on the MoveGen itself.

But just out of curiosity, I included a compile-time switch in the perft (now posted as the source on the website, and also as executable) that disables the bulk counting, but Makes/Unmakes all moves.

It seems that this approximately doubles the required time (from 5.6 to 12 sec for perft(6), on the 1GHz Athlon XP):

Code: Select all

$ ./mperft 6
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, Making / UnMaking last ply

perft(1)=20 ( 0.000 sec)

perft(2)=400 ( 0.000 sec)

perft(3)=8902 ( 0.000 sec)

perft(4)=197281 ( 0.020 sec)

perft(5)=4865609 ( 0.480 sec)

perft(6)=119060324 (12.018 sec)

$ ./qperft 6
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

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

perft(5)=4865609 ( 0.220 sec)

perft(6)=119060324 ( 5.608 sec)

[Aleks Peshkov]

Perft seems to be a popular Russian game.
Меряемся производительностью perft

What is average NPS drop ratio when converting average Perft engine to Alpha-Beta?

[hgm]

Almost none (with material + piece-square table differential eval only).

But you count nodes differently, of course. The perft(6) (without Make/UnMake) you would count as a 5-ply search, with 486k nodes. The 6th ply would merely be concluding that none of the generated moves is worth searching (i.e. not a capture, or futile).

[smrf]

At a c2d@2.0GHz (one thread) my old SMIRF code gives:

Code: Select all

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

  +-*--b--c--d--*--f--g--*-+ MS Vis.Studio C++ 32-Bit-Vers. 13.10
8 |[r][n][b][q][k][b][n][r]| (Compilation: Oct 13 2007)
7 |[p][p][p][p][p][p][p][p]|
6 |   :::   :::   :::   :::| Perft Testseries
5 |:::   :::   :::   :::   |
4 |   :::   :::   :::   :::| (without caching)
3 |:::   :::   :::   :::   |
2 |<P><P><P><P><P><P><P><P>| Smirf Test No.&#58;  0
1 |<R><N><B><Q><K><B><N><R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time&#58; +10.00 Sec.

Ply      Nodes     all &#40;x&#41;     &#40;ep&#41;    all (+)      (#)  Prom.    Cstl.    Sec.
-------------------------------------------------------------------------------
1           20           0        0          0        0      0        0       0
2          400           0        0          0        0      0        0       0
3         8902          34        0         12        0      0        0       0
4       197281        1576        0        469        8      0        0       0
5      4865609       82719      258      27351      347      0        0   0.172
6    119060324     2812008     5248     809099    10828      0        0   4.610
7   3195901860   108329926   319617   33103848   435767      0   883453   118.8
-------------------------------------------------------------------------------


FEN&#58; r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 25

  +-*--b--c--d--*--f--g--*-+ MS Vis.Studio C++ 32-Bit-Vers. 13.10
8 |&#91;r&#93;&#58;&#58;&#58;   &#58;&#58;&#58;&#91;k&#93;&#58;&#58;&#58;   &#91;r&#93;| &#40;Compilation&#58; Oct 13 2007&#41;
7 |&#91;p&#93;   &#91;p&#93;&#91;p&#93;&#91;q&#93;&#91;p&#93;&#91;b&#93;   |
6 |&#91;b&#93;&#91;n&#93;   &#58;&#58;&#58;&#91;p&#93;&#91;n&#93;&#91;p&#93;&#58;&#58;&#58;| Perft Testseries
5 |&#58;&#58;&#58;   &#58;&#58;&#58;<P><N>   &#58;&#58;&#58;   |
4 |   &#91;p&#93;   &#58;&#58;&#58;<P>&#58;&#58;&#58;   &#58;&#58;&#58;| &#40;without caching&#41;
3 |&#58;&#58;&#58;   <N>   &#58;&#58;&#58;<Q>&#58;&#58;&#58;&#91;p&#93;|
2 |<P><P><P><B><B><P><P><P>| Smirf Test No.&#58;  1
1 |<R>   &#58;&#58;&#58;   <K>   &#58;&#58;&#58;<R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time&#58; +10.00 Sec.

Ply     Nodes     all &#40;x&#41;     &#40;ep&#41;   all (+)     (#)     Prom.     Cstl.   Sec.
-------------------------------------------------------------------------------
1          48           8        0         0       0         0         2      0
2        2039         351        1         3       0         0        91      0
3       97862       17102       45       993       1         0      3162      0
4     4085603      757163     1929     25523      43     15172    128013  0.156
5   193690690    35043416    73365   3309887   30171      8392   4993637  7.516
6  8031647685  1558445089  3577504  92238050  360003  56627920 184513607  308.3
-------------------------------------------------------------------------------

Please note, that because of the different nature of move generators, numbers are only comparable if generators would produce related statistics with such data, especially check threats and mates counts. Without that statistics SMIRF would be tremendously faster.

Reinhard.

[hgm]

Agreed; check testing was tremendously expensive, this is why I left it out.

If I were to implement it, I would probably chose the following way:

First identifyline-ups between stm Sliders and opponent King (from the Slider list, typically 5 pieces only). For any such alignment scan the ray. A single intervening piece of the stm that is not pinned is can then deliver discovered check. Its moves are then generated and marked accordingly.

For the direct checks, I would use a test similar to the 0x88 capture test. I would run through the piece list, and for any vector piece-King I would have tabulated a list of possible King->CheckSquare vectors (upto 2 for N,B,R, and upto 12 for a Queen. I would mark all of them on a scratch board. The ToSquare of each generated move would than be tested against this scratch board for matching piece type. On a match I would scan the ray connecting CheckSquare and King.

This seems a reasonably efficient way to do it, where the amount of work would go down with the occupation of the board.

[bob]

Wow! Perft 8 in under 2 minutes.

Perhaps I should stress that this is (mostly) without making / unmaking the last ply, just generating moves and then lookig at the move-stack pointer to see how many there are. (That is what I mean by 'bulk counting'.) Only King moves and e.p. captures are actually made to check them for legality.

How do you weed out the _other_ illegal moves? perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea. And the idea was that a perft total counts _only_ legal moves. If you do as you say, you will make illegal moves at the last ply when a piece is pinned on your own king...

The version that is on my website now does not update a hash key during MakeMove(), as it seemed a bit unfair to require the update of a hash key if there is no hashing. It does test if it should update one, though (and if hashing is switched on, then immediately does the probe after update).

Perft has become quite distorted over the years. It was originally defined as "legal moves only, made _and_ unmade". This includes a _full_ make/unmake, not some stripped-down version, no hashed totals, just a tree-walk of legal moves to a fixed depth doing whatever you do for a normal search.

Somehow that has become badly corrupted...

I considered not making the last ply a more meaningful speed measure for comparing with engines. In a search tree, there are two kind of end leaves: those where the evaluation is below alpha, (in which case you will do a move generation to get captures to try in QS), or where it is above beta (where in most cases you would not make the move to it, but prune it in the node below for futility). So the typical end leave does move or capture generation, and then comes to the conclusion that it doesn't want to make any of the generated moves, because they are all futile or bad captures.

So you typically end the tree with move generation, with 1 Make / Unmake per MoveGen for getting in the node, rather than ending with ~40 Make/Unmakes per MoveGen. A perft that makes the last ply thus puts way to much emphasis on the speed of the Make/Unmake, and far too little on the MoveGen itself.

But just out of curiosity, I included a compile-time switch in the perft (now posted as the source on the website, and also as executable) that disables the bulk counting, but Makes/Unmakes all moves.

It seems that this approximately doubles the required time (from 5.6 to 12 sec for perft(6), on the 1GHz Athlon XP):

Code: Select all

$ ./mperft 6
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, Making / UnMaking last ply

perft(1)=20 ( 0.000 sec)

perft(2)=400 ( 0.000 sec)

perft(3)=8902 ( 0.000 sec)

perft(4)=197281 ( 0.020 sec)

perft(5)=4865609 ( 0.480 sec)

perft(6)=119060324 (12.018 sec)

$ ./qperft 6
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

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

perft(5)=4865609 ( 0.220 sec)

perft(6)=119060324 ( 5.608 sec)

[Uri Blass]

How do you weed out the _other_ illegal moves? perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea. And the idea was that a perft total counts _only_ legal moves. If you do as you say, you will make illegal moves at the last ply when a piece is pinned on your own king...

You can look at the code.
He clearly does not generate illegal moves of pinned pieces

Here is one of his comments:

"/* Pintest, starting from possible pinners in enemy slider list */
/* if aiming at King & 1 piece of us in between, park this piece */
/* on pin stack for rest of move generation, after generating its */
/* moves along the pin line. */"

It is clear that he counts only legal moves otherwise he could not get correct numbers.

Perft has become quite distorted over the years. It was originally defined as "legal moves only, made _and_ unmade". This includes a _full_ make/unmake, not some stripped-down version, no hashed totals, just a tree-walk of legal moves to a fixed depth doing whatever you do for a normal search.

Somehow that has become badly corrupted...

No

This is not correct.

Perft is simply a function to calculate the number of possible games with n moves.

It can be used as a tool to debug the move generator but it is not the only use.

Even if you do not make the last ply then it is still useful as debugging tool for the move generator because you clearly need to make moves earlier and if you have bugs in your makemove function then you will not get correct results.

It can be also useful to debug your hash tables because if you have hash collisions because of bad numbers in the hash and use perft with hash then you are not going to get correct numbers.

Uri

[hgm]

How do you weed out the _other_ illegal moves? perft was something I created years ago as an option in Crafty for debugging, and everyone copied the idea. And the idea was that a perft total counts _only_ legal moves. If you do as you say, you will make illegal moves at the last ply when a piece is pinned on your own king...

Such moves are not generated. It is far faster not to generate such moves in the first place, than generate them, and subsequently having to test _every_ move for not being pinned to the King. So you benefit in 3 ways: It saves the time of both generating _and_ testing illegal moves, and it saves on testing the legal moves.

Perft has become quite distorted over the years. It was originally defined as "legal moves only, made _and_ unmade". This includes a _full_ make/unmake, not some stripped-down version, no hashed totals, just a tree-walk of legal moves to a fixed depth doing whatever you do for a normal search.

Somehow that has become badly corrupted...

I see it more as being credited for its full potential...

As Uri already pointed out, the numbers themselves are immensely useful for debugging move generation and tree walk. And usually only deep searches are able to set up the rare occasions that suffer from bugs. So obtaining the numbers is a non-negligible effort, and not obtaining in the most efficient way possible would be madness. Not making the moves unnecessarily saves about a factor 2, hashing on a deep perft might save you another factor 10..

And, like I said, engines usually don't make the moves they generate in the end-leaves either. So for timing an engine under construction, Make / UnMake of the last ply would invite you to make completely wrong and counterproductive 'optimizations'.