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

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
mphuget
Posts: 12
Joined: Fri Mar 01, 2019 11:46 am
Full name: Marc-Philippe HUGET

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

Post by mphuget » Sat Apr 04, 2020 9:31 am

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

User avatar
hgm
Posts: 24570
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

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

Post by hgm » Sat Apr 04, 2020 11:18 am

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.

User avatar
mvanthoor
Posts: 236
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

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

Post by mvanthoor » Sat Apr 04, 2020 3:54 pm

Newer programming languages such as Rust actually provide u128.

Dann Corbit
Posts: 11149
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

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

Post by Dann Corbit » Sat Apr 04, 2020 7:32 pm

There are arbitrary precision libraries for many languages
Perft 14 and 15 have already been counted:
https://www.chessprogramming.org/Perft_Results
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

mphuget
Posts: 12
Joined: Fri Mar 01, 2019 11:46 am
Full name: Marc-Philippe HUGET

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

Post by mphuget » Sun Apr 05, 2020 11:00 am

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
Posts: 11149
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

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

Post by Dann Corbit » Sun Apr 05, 2020 7:45 pm

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
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

JohnWoe
Posts: 183
Joined: Sat Mar 02, 2013 10:31 pm

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

Post by JohnWoe » Thu Apr 09, 2020 8:34 pm

Dann Corbit wrote:
Sun Apr 05, 2020 7:45 pm
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
Posts: 1112
Joined: Sun Mar 12, 2006 5:46 pm
Location: Vancouver

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

Post by tmokonen » Thu Apr 09, 2020 9:13 pm

JohnWoe wrote:
Thu Apr 09, 2020 8:34 pm

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
Posts: 11149
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

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

Post by Dann Corbit » Fri Apr 10, 2020 12:56 am

JohnWoe wrote:
Thu Apr 09, 2020 8:34 pm
Dann Corbit wrote:
Sun Apr 05, 2020 7:45 pm
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:

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.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Milos
Posts: 3642
Joined: Wed Nov 25, 2009 12:47 am

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

Post by Milos » Fri Apr 10, 2020 1:28 am

Dann Corbit wrote:
Sun Apr 05, 2020 7:45 pm
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. ;)

Post Reply