Count the number of nodes of perft(14) and beyond

[mphuget]

Hello everyone,

By curiosity (or not) I am wondering how it is possible to store the number of nodes when we count perft(14) and beyond: the number of nodes is greater than 2^64, do we consider an overflow and we let the count continue and we add on 128 bits when it is finished? I remember Steven Edwards answered about the count on TalkChess but unable to find it once again.

Thanks in advance for your ideas

mph

[hgm]

Yes, you would need larger counters. But you would need these only in the nodes close to the root. IIRC Qperft already distinguishes by depth when it should store 32-bit or 64-bit counters during hashing.

[mvanthoor]

Newer programming languages such as Rust actually provide u128.

[Dann Corbit]

There are arbitrary precision libraries for many languages
Perft 14 and 15 have already been counted:
https://www.chessprogramming.org/Perft_Results

[mphuget]

Hello Dann,

I know Dann but I want to try Perft using GPU as did Ankan by the past, first using his approach and try to run it on the cloud, then provide my own approach

Cheers,
mph

[Dann Corbit]

Something I would be keenly interested is it to save all the terminal (decided) positions.
How many distinct wins, losses, and draws are there is known. But *what are they* is not known.
I guess that newer cards can use Ankan's code and get answers much faster.
You can buy a box with a big rack of cards in it. Big money, though.
I guess that buying the time on a GPU cluster will cost a lot too.

Perft is a fascination, like computing the digits of pi. I would also be interested in statistics.
Obviously, at ply 1 there are zero checkmates, zero captures, zero promotions, zero draws. But what do percentages look like as a function of ply?

I think it would be a lot more interesting to study the information rather than just generate it, but in order to study it, it will be necessary for the generator to have some tweaks so that we have the ability to study the data.

Another thing I think would be incredibly interesting would be an AND/OR proof search for checkmates and draws since it only needs a move generator that knows if a position is won/lost/drawn. Since they expand the nodes as a function of probability, who knows how deep such an engine might search? It might even be an effective chess engine

I am really interested in your project and wish you success on it. All my GPUs are folding proteins right now, but I might give you some GPU time when the Corona 19 virus thing is over

[JohnWoe]

Something I would be keenly interested is it to save all the terminal (decided) positions.
How many distinct wins, losses, and draws are there is known. But *what are they* is not known.
I guess that newer cards can use Ankan's code and get answers much faster.
You can buy a box with a big rack of cards in it. Big money, though.
I guess that buying the time on a GPU cluster will cost a lot too.

Perft is a fascination, like computing the digits of pi. I would also be interested in statistics.
Obviously, at ply 1 there are zero checkmates, zero captures, zero promotions, zero draws. But what do percentages look like as a function of ply?

I think it would be a lot more interesting to study the information rather than just generate it, but in order to study it, it will be necessary for the generator to have some tweaks so that we have the ability to study the data.

Another thing I think would be incredibly interesting would be an AND/OR proof search for checkmates and draws since it only needs a move generator that knows if a position is won/lost/drawn. Since they expand the nodes as a function of probability, who knows how deep such an engine might search? It might even be an effective chess engine

I am really interested in your project and wish you success on it. All my GPUs are folding proteins right now, but I might give you some GPU time when the Corona 19 virus thing is over

There is no draws in perft. Perft is only useful in opening positions as a performance tool. And hunting some en passant/castling/ etc bugs as there is lots of shuffling. For example KK is totally valid for perft. But that doesn't give valuable data about anything. Perft goodness depends totally on what kind of data it's given.

However in FIDE chess draws need to claimed, so in that sense that endless shuffling is legal.

[tmokonen]

There is no draws in perft. Perft is only useful in opening positions as a performance tool. And hunting some en passant/castling/ etc bugs as there is lots of shuffling. For example KK is totally valid for perft. But that doesn't give valuable data about anything. Perft goodness depends totally on what kind of data it's given.

However in FIDE chess draws need to claimed, so in that sense that endless shuffling is legal.

I have used perft routines to help me with other debugging tasks. I wrote a specialized perft that calls my evaluation function, flips the board, and calls eval again, to check for evaluation symmetry. I also wrote a specialized perft to help me debug incremental hash, by comparing incremental hash against a calculated hash.

[Dann Corbit]

Something I would be keenly interested is it to save all the terminal (decided) positions.
How many distinct wins, losses, and draws are there is known. But *what are they* is not known.
I guess that newer cards can use Ankan's code and get answers much faster.
You can buy a box with a big rack of cards in it. Big money, though.
I guess that buying the time on a GPU cluster will cost a lot too.

Perft is a fascination, like computing the digits of pi. I would also be interested in statistics.
Obviously, at ply 1 there are zero checkmates, zero captures, zero promotions, zero draws. But what do percentages look like as a function of ply?

I think it would be a lot more interesting to study the information rather than just generate it, but in order to study it, it will be necessary for the generator to have some tweaks so that we have the ability to study the data.

Another thing I think would be incredibly interesting would be an AND/OR proof search for checkmates and draws since it only needs a move generator that knows if a position is won/lost/drawn. Since they expand the nodes as a function of probability, who knows how deep such an engine might search? It might even be an effective chess engine

I am really interested in your project and wish you success on it. All my GPUs are folding proteins right now, but I might give you some GPU time when the Corona 19 virus thing is over

There is no draws in perft. Perft is only useful in opening positions as a performance tool. And hunting some en passant/castling/ etc bugs as there is lots of shuffling. For example KK is totally valid for perft. But that doesn't give valuable data about anything. Perft goodness depends totally on what kind of data it's given.

However in FIDE chess draws need to claimed, so in that sense that endless shuffling is legal.

Some draws must fall out of perft. For instance this position (admittedly too deep for modern hardware) is an example of a draw because white has no legal moves:
[d]8/8/8/8/1r6/2k5/7r/K7 w - -
And a move generator must be aware of no legal moves (it's either a checkmate or a draw).
It seems fairly trivial to add material draws also, just for statistical purposes.
Draws by repetition are another matter, as are draws by expiration of the halfmove clock at 100.

I guess, though, that the problem with the draw numbers would not actually be fully correct, because any position can be a draw by repetition at some point.

So maybe only the checkmates are really interesting.

[Milos]

I am really interested in your project and wish you success on it. All my GPUs are folding proteins right now, but I might give you some GPU time when the Corona 19 virus thing is over

The net effect for humanity would be much higher if you just mined BTC and gave away all the mined money to support research directly.