perft and repetition

[Grzegorz Sidorowicz]

Have you got any statistc about number of repetitions, checks, checkmates detected during perft test?

Regards
Greg

[Reinhard Scharnagl]

Hi Greg,

Have you got any statistc about number of repetitions, checks, checkmates detected during perft test?

some months ago I had still supported counting of checkmates, but that seems to be of less interest. That statistic I originally supported has had the purpose to help finding bugs in the move generator, where mates are of less importance.

Checks will be counted in my current statistic, but counting double checks which have also been counted earlier now has been skipped.

Counting of repetitions seems to be possible only if using cache. But because caching does not guarantee to have all previous positions at hand, you will not be able to always have a correct result. Moreover you will have to distinguish repetitions of different levels.

Instead of repetitions I still document the (last) average success percentage of retreiving cached data.

Reinhard.

[Grzegorz Sidorowicz]

Yes, repetition detection is possible if we are using hashing function but mistakes which could be result of this checking aren't disadvantage. This information can be helpful to detection of errors in hashing function.

[Volker Annuss]

Repetitions are not used in perft calculation by definition. See http://homepages.caverock.net.nz/~peter/perft.htm

Greetings,
Volker

[Tord Romstad]

Hi Grzegorz!

How is the work on your new engine going?

Have you got any statistc about number of repetitions, checks, checkmates detected during perft test?

I usually don't collect such statistics, but of course it would be easy to add. If you have any concrete positions (hexagonal or 8x8 rectangular) , I can run perft tests with Scatha/Glaurung and post the results.

Repetitions are not used in perft calculation by definition. See http://homepages.caverock.net.nz/~peter/perft.htm

Volker, I think you didn't understand the question correctly. You are right that repetitions are not considered when computing perft numbers, but of course repetitions can still occur inside the perft search. Grzegorz wants to count them.

Tord

[Grzegorz Sidorowicz]

This positions are not used to reduction tree but you can count what you want I need number of repetitions to compare to my program. Number of repetitions in perft test is always the same. It is constant value. For detecting position insted hash code we can use fen position (which is always the same) and in result we will have always the same result. The same number of positions. It only depends on quality of implementation of perft test in engine. Bad engine will show wrong number correct engine will show correct number. Of course showing number of reptitions isn't obligation so in consequence some times correct engine can be correct without showing any number and analagous wrong engine still will be wrong

[Reinhard Scharnagl]

Yes, repetition detection is possible if we are using hashing function but mistakes which could be result of this checking aren't disadvantage. This information can be helpful to detection of errors in hashing function.

Well, I think using a cached Perft alone would already do. You just have to calculate into sufficiently deep plys and compare to results coming from uncached Perft.

P.S.: Using a transposition table will lead to the occurrence of the lost of some cached data. So how to count all repetitions?

Reinhard.

[Grzegorz Sidorowicz]

How is the work on your new engine going?

....some weeks, some weeks

I usually don't collect such statistics, but of course it would be easy to add. If you have any concrete positions (hexagonal or 8x8 rectangular) , I can run perft tests with Scatha/Glaurung and post the results.

I'm interested in initial position for rectangular, depth 4 to 9

Thank you Tord!

P.S.
Now I'm working a little more and I decided to build Hexodus as engine like Scatha. I always remember everything

[Anonymous]

P.S.: Using a transposition table will lead to the occurrence of the lost of some cached data. So how to count all repetitions?

I can think of at least two ways, that both will not need a transposition table. One will use hash keys, however. The methods can be more or less efficient (and the least efficient one would be easiest to code).

Without hash keys: Just store the whole position in a format convenient to you with every move in a stack. This could be a whole board array, a whole color array, castling state and ep. It could be rather condensed, for example storing information for two squares in one byte (color and piece), or even using something like the huffman encoding you proposed.
After every move, go back to the root position in two ply steps (meaning looking up the stored position in the "position stack") and comparing the current position with it. Of course, one only has to go back to the last irreversible move.

If you have hash keys available anyway, instead of storing and comparing positions, comparing hash keys will be enough (when using 64 bit, the chance of an error is extremly low). Or one could compare hash keys and still save the old positions. Only in the case of the same hash key, one would need to do the whole position compare (Which may be a bit costy).

One can have it even more efficient, by having a seperate position hash of say 0x1000 entries (perhaps one for each side). With each move, increment it. repetition_hash[side_to_move][hash_key & 0xfff]++. In most cases, the result will be one. Only if bigger than one, compare with the stored positions in the same ways as described above.

BTW. My make_move function already returns the repetition counter. It also does the hash key updates - whether I use hash or not (it is just not worth it, to optimize this away). I use this same make_move in perft, so counting repetitions is almost free for my engine.

There is one subtle point, which my engine will not handle correctly. I actually know of no engine, that handles it correctly. When an ep move seems possible (just done a double step, and the moved pawn has one pawn neighbor on the same rank of opposite color), but the neighbor pawn is pinned to his king (ep is not really possible), I don't handle this correctly, and would count the next time this position is hit (this time it will naturally have no ep possibility) not as an repetition. But it really is one.

I did a database search once in Dann Corbit's 3 million games, and this situation never occured. It is of course possible in a general perft tree.

Regards,
Dieter

[Reinhard Scharnagl]

Hi Dieter,

look at the following example results:

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++ Vers. 13.10
8 |[r][n][b][q][k][b][n][r]| (Compilation: Apr 16 2005)
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.: 00
1 |<R><N><B><Q><K><B><N><R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time 200.0 Sec.

Ply        Nodes      all (x)    (e.p.)     all (+)   Prom.     Castl.     Sec.
-------------------------------------------------------------------------------
1             20            0         0           0       0          0        0
2            400            0         0           0       0          0        0
3           8902           34         0          12       0          0        0
4         197281         1576         0         469       0          0        0
5        4865609        82719       258       27351       0          0      0.2
6      119060324      2812008      5248      809099       0          0      4.4
7     3195901860    108329926    319617    33103848       0     883453    114.3
8    84998978956   3523740106   7187977   968981593       0   23605205     3102
-------------------------------------------------------------------------------

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

  +-*--b--c--d--*--f--g--*-+ MS Vis. Studio C++ Vers. 13.10
8 |[r][n][b][q][k][b][n][r]| (Compilation: Apr 15 2005)
7 |[p][p][p][p][p][p][p][p]|
6 |   :::   :::   :::   :::| Perft Testseries
5 |:::   :::   :::   :::   | (With TT Caching 256.0 MB / 4-fold)
4 |   :::   :::   :::   :::| TT Access Success 48.5%
3 |:::   :::   :::   :::   |
2 |<P><P><P><P><P><P><P><P>| Smirf Test No.: 00
1 |<R><N><B><Q><K><B><N><R>|
=>+-*--b--c--d--*--f--g--*-+ Break Time 25.0 Sec.

Ply        Nodes      all (x)    (e.p.)     all (+)   Prom.     Castl.     Sec.
-------------------------------------------------------------------------------
1             20            0         0           0       0          0        0
2            400            0         0           0       0          0        0
3           8902           34         0          12       0          0        0
4         197281         1576         0         469       0          0        0
5        4865609        82719       258       27351       0          0      0.1
6      119060324      2812008      5248      809099       0          0      1.3
7     3195901860    108329926    319617    33103848       0     883453     15.6
8    84998978956   3523740106   7187977   968981593       0   23605205    216.4
-------------------------------------------------------------------------------

Using a transposition table has lead to a 93% reduction of consumed time. Ignoring that caching and retreiving stored data would consume time itself, you could estimate at least 93% of all positions here being repetitions, but probably the rate is indeed even higher.

I hardly could imagine a methode to store those positions without any lost by overwriting cached contents sometimes, especially at deeper plys.

Reinhard.

[Grzegorz Sidorowicz]

Reinhard I believ you knew I thought about detecting draw by repetition not about detecting all repetitions the same positions?
Of course my request to Tord was a little wrong because in fact I need results for level 8 to 10 but I didn't correct my request because number of all repetitions on path is also intersting for me.

By the way, you reached great result in speed. You needed only 1.3 seconds for reach level 6! For me it is incredible, it is about 15 times faster than need my program to reach this level.
There have to be hidden trick
If no I go to kill myself
What is your machine?

[Reinhard Scharnagl]

Hi Grzegorz,

By the way, you reached great result in speed. ... There have to be hidden trick :-)
If no I go to kill myself :) What is your machine?

first you cannot use the second statistic for to compare genuine Perft results, because it is using cached partial sums stored in the transposition table. You may compare to the first statistic (nevertheless there have been discussions on that point). I am using a P4 at 2.8 GHz under Windows XP pro.

Regards, Reinhard.

P.S.: There are no tricks. My Perft uses the original move generating, making and unmaking procedures as my Smirf engine does.

[Anonymous]

Using a transposition table has lead to a 93% reduction of consumed time.

Reinhard, of course, using a transposition tables (TTs) will not give correct reption counts (and in real play will have unsolved problems regarding repetions). In the post I answered, you asked:"So how to count all repetitions?". I only wanted to answer that question. Perhaps you meant it only in the context of TTs. I have no answer, there (at least no answer, that will be efficient).

Dieter