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

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

Post by mphuget » Fri Apr 10, 2020 6:56 am

Hello, Dann (and all),

I guess it could be worthwhile to decide which details we need and then I change my code to obtain them
My first requirement would be to fill the table as shown on https://www.chessprogramming.org/Perft_Results. I hate empty spaces :-)

This exercise has four interests for me:
1. Working on GPGPU with CUDA, and especially how to balance the load between CPU and GPU. This could give me a nice powerful move generator for my chess engine (and possibly a mate solver).
2. Enter the realm of multi-GPU programming
3. Considering large (well, this is more than large) amount of data to generate and process.
4. Start and resume these large simulations

I have a GTX 1070 at home, that could be a nice first take on programming GPU, but I have the chance to be academic and a Computer Science lab for students at the University is full of RTX 2070 (16 PC in the room) with AMD Ryzen. These PCs are idle on nights, weekends and holidays (and lockdown). I will deploy on these machines as soon as I have something that works

Cheers,
mph

Dann Corbit
Posts: 11238
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 8:00 am

Bitcoins are the currency of criminals. BTC mining fuels the worst sort of gangsters on the planet.
What sort of people want to keep the banks out of their transactions and hide both the sender and the receiver?
There is no legitimate reason for that.
I have hardware to make many thousands of dollars mining bitcoins.
I have only disdain for this activity.
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.

User avatar
Ajedrecista
Posts: 1456
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

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

Post by Ajedrecista » Fri Apr 10, 2020 9:07 am

Hello Marc-Philippe:
mphuget wrote:
Fri Apr 10, 2020 6:56 am
Hello, Dann (and all),

I guess it could be worthwhile to decide which details we need and then I change my code to obtain them
My first requirement would be to fill the table as shown on https://www.chessprogramming.org/Perft_Results. I hate empty spaces :-)

[...]
I guess you are aware of other source with that kind of statistics for higher depths than currently CPW shows (depth 9 right now at CPW):

Statistics on chess games

There is also a thread at TalkChess with similar purposes than yours:

Level 11 Perft statistics

Both links are in the CPW article of perft results. You might find them interesting for verification purposes. OTOH, I can not point to anything interesting regarding how to deal with large integer overflows... Internet searches might help you. Good luck!

Regards from Spain.

Ajedrecista.

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 » Fri Apr 10, 2020 9:53 am

Dann Corbit wrote:
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.
Yes. that position results 1 Node.

Code: Select all

Depth               Nodes        Mnps        Time
    0                   1       0.000       0.000
    1                   0       0.000       0.000
    2                   0       0.000       0.000
=================================================
                    Nodes        Mnps        Time
Total                   1       0.000       0.000
Perft is what is it is. A tool for specific purpose.
When you start "improving" aka adding more stuff(draw detection/etc...) you cannot compare the results.
About over-engineering: https://www.youtube.com/watch?v=-AQfQFcXac8

I have written my own random number number generator so it's good to see this hashing actually works. I expect collisions but that hasn't happened. And bulletproof coding is MOOT anyway.

Dann Corbit
Posts: 11238
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 4:50 pm

JohnWoe wrote:
Fri Apr 10, 2020 9:53 am
{snip}
Perft is what is it is. A tool for specific purpose.
When you start "improving" aka adding more stuff(draw detection/etc...) you cannot compare the results.
{snip}
While the number of possible moves from a given position is interesting, I cannot imagine that I am the only person who would like to see them classified.

So I will invent a new word:
PerftC
Perft classified.
It will not change the node count. It will just tell us a bit more about what it saw.
But am I the only one who wants to know how many direct mates there are within 12 plies?
I guess I am a strange bird.
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.

User avatar
hgm
Posts: 24655
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 » Fri Apr 10, 2020 5:27 pm

I think SMIRF did provide such a 'fully informed' perft.

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

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

Post by BlueStar » Wed Jul 29, 2020 9:24 pm

The move generator in NADYA2.0 (with the exception of discovery and double checks) captures all of the data on https://www.chessprogramming.org/Perft_ ... l_Position and more (including stalemates) but doesn't care about 50 move rule or tie by repetition.

This has helped me enormously with debugging a slower speed perft. As opposed to focusing on raw speed, I choose pure accuracy which makes NADYA an order of magnitude slower that high-end engines. Even though you greatly slow your generator by tracking the extra board statistics, that extra data makes it an order of magnitude easier to debug (IMO). Now that the generator passes every perft test I throw at it, I'm making it faster. For example, a 30% increase in less than a week.

Since I'm using Prolog as my compiler, I also planned to track the statistical data so when I add my NLP module, it will act like a chess query database with almost no extra work since I've taken advantage of the built-in backtracking of the language. EXAMPLE= "? for [insert FEN] show occurrence of pawn promotion to (N) where result = checkmate max depth 8"

BlueStar
Posts: 16
Joined: Fri Apr 10, 2020 12:41 am
Full name: Craig Hoibakk

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

Post by BlueStar » Thu Jul 30, 2020 12:55 am

BlueStar wrote:
Wed Jul 29, 2020 9:24 pm
...and more (including stalemates)....
I will say, this however, is a compile option (at least for stalemate), as calculating this at the leaf level (in my implementation) is way to time prohibitive/costly.

Post Reply