Perft(13) betting pool

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Daniel Shawul
Posts: 3501
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Wed Jul 27, 2011 3:31 pm

I am serious: you have not understood yet any of Uri's and my posts on that specific issue. You are too fast IMO. Uri's clarification was precise, and he never said something different. A main problem may be that "counting" or "not counting" shorter games has several different meanings, and you will only get the right meaning from the context.

Read again, please. I am not joking.

Then please try to answer my open questions. I hope everything will be cleared up soon.
Don't be so quick to judge you might be surprised. I am not joking :)

Code: Select all

Sum  = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
There is a possible source of your misunderstanding. Uri used the word "increment" but in the sense that shorter games are handled the same way as full-length games (for both types the total_games counter is incremented). So since total_games includes shorter games there is no such "total_games + 1". And this is the same he wrote before.

And I explained to you in my previous post why I think that this formula is not "wrong" (U(i) covering all ever possible games including also shorter games).
No you misunderstood.
My legal_games, and total games are being incremented as each game is being played that is both starting from 0.
You can fix the total_games from the start but it doesn't matter. The point is those shorter games should not be in the total games count period.

Say I have counters legal_games=5 and total_games=100 that is I already played 100 games and 5 of them are legal (with no shorter game encountered so far) , and then suddenly I got a shorter win game when I play one more game i.e on my 101th test, how do you increment now ?
I am saying you leave both as they are as in (a) below
a) legal_games = 5, and total_games = 100
If you do
b) legal_games = 6 and total-games = 101
Or
c) legal_games = 5 and total_games = 101
it becomes _biased_. And I can prove it to you but please say which one you do (a) , (b) or (c), before we continue.

Sven
Posts: 3697
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Perft(13) betting pool

Post by Sven » Wed Jul 27, 2011 3:58 pm

Daniel Shawul wrote:
I am serious: you have not understood yet any of Uri's and my posts on that specific issue. You are too fast IMO. Uri's clarification was precise, and he never said something different. A main problem may be that "counting" or "not counting" shorter games has several different meanings, and you will only get the right meaning from the context.

Read again, please. I am not joking.

Then please try to answer my open questions. I hope everything will be cleared up soon.
Don't be so quick to judge you might be surprised. I am not joking :)

Code: Select all

Sum  = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
There is a possible source of your misunderstanding. Uri used the word "increment" but in the sense that shorter games are handled the same way as full-length games (for both types the total_games counter is incremented). So since total_games includes shorter games there is no such "total_games + 1". And this is the same he wrote before.

And I explained to you in my previous post why I think that this formula is not "wrong" (U(i) covering all ever possible games including also shorter games).
No you misunderstood.
My legal_games, and total games are being incremented as each game is being played that is both starting from 0.
You can fix the total_games from the start but it doesn't matter. The point is those shorter games should not be in the total games count period.

Say I have counters legal_games=5 and total_games=100 that is I already played 100 games and 5 of them are legal (with no shorter game encountered so far) , and then suddenly I got a shorter win game when I play one more game i.e on my 101th test, how do you increment now ?
I am saying you leave both as they are as in (a) below
a) legal_games = 5, and total_games = 100
If you do
b) legal_games = 6 and total-games = 101
Or
c) legal_games = 5 and total_games = 101
it becomes _biased_. And I can prove it to you but please say which one you do (a) , (b) or (c), before we continue.
You have a funny interpretation of words sometimes :-) "Incrementing" as both Uri and I were using means to add 1 to some variable. It does not necessarily mean (and in this case it does not mean) that the "+ 1" has to occur in the final formula. If I tell you that I increment the counter of animals passing my way by 1 each time I encounter the next animal, what is the final number of animals after I stop counting? nAnimals, or nAnimals + 1?

I don't think about calculating any perft estimate unless all MC games are finished, so I don't get your point of looking at one snapshot after 100 games, then "suddenly" game no. 101 occurs and is shorter than N plies. That is irrelevant for me. I look at the final outcome. All games are counted with "total_games". Exactly all full-length legal games are counted with "legal_games". So when all is finished I have one formula "(legal_games / total_games) * (product of all U(i))".

If you insist on your snapshot, and if I assume that the test run is finished after your 101 games, then it is (c) what Uri and I are doing. But please avoid using the "+ 1" again in your formula since it is misleading for the overall understanding of the final perft estimation.

Sven

Daniel Shawul
Posts: 3501
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Wed Jul 27, 2011 4:05 pm

f you insist on your snapshot, and if I assume that the test run is finished after your 101 games, then it is (c) what Uri and I are doing. But please avoid using the "+ 1" again in your formula since it is misleading for the overall understanding of the final perft estimation.
Great! Finally we understand each other :) And the method will be _biased_.
What you should have done in your way of counting was to decrement the total_games when you encounter the a short win, and also also do not increment illegal or legal game counter. So if you intended to play a million games, then when you have one short game you should have considered as if you played 999999

In my next post I will try to repeat my post a couple of days ago showing why it is _biased_.
Are you ready for it? :)

Sven
Posts: 3697
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Perft(13) betting pool

Post by Sven » Wed Jul 27, 2011 4:25 pm

Daniel Shawul wrote:
If you insist on your snapshot, and if I assume that the test run is finished after your 101 games, then it is (c) what Uri and I are doing. But please avoid using the "+ 1" again in your formula since it is misleading for the overall understanding of the final perft estimation.
Great! Finally we understand each other :) And the method will be _biased_.
What you should have done in your way of counting was to decrement the total_games when you encounter the a short win, and also also do not increment illegal or legal game counter. So if you intended to play a million games, then when you have one short game you should have considered as if you played 999999

In my next post I will try to repeat my post a couple of days ago showing why it is _biased_.
Are you ready for it? :)
Ready to go :-) I understand your intention (I already understood it before). Furthermore I hope that your proof will also care about all the other points I made before, including:

- that the product of all U(i) covers all ever-possible games, so also shorter games, so that not including the shorter games in nLegalGames sounds suspicious for me,

- that I could imagine, to achieve an even bigger level of perfection, to completely strip all game-terminating moves (i.e. mating or in theory stalemating) from all move lists except those at the last ply to ensure that we only play 100% full-length MC games (which could be slightly different from what you want to do due to the possibly different range of random numbers given by possibly smaller values of U(i)),

- and that I think that your proposed formula which I shorten as "estimatedPerft(N) := sum(i=1..N) ((nLegalGames / nTotalGames) * product(j=1..i) (U(i)))" adds parts to the perft estimation that are not included in the exact perft(N) value which only counts fulll-length paths.

Curious regards,
Sven

Daniel Shawul
Posts: 3501
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Wed Jul 27, 2011 4:36 pm

Sven Schüle wrote:
Daniel Shawul wrote:
If you insist on your snapshot, and if I assume that the test run is finished after your 101 games, then it is (c) what Uri and I are doing. But please avoid using the "+ 1" again in your formula since it is misleading for the overall understanding of the final perft estimation.
Great! Finally we understand each other :) And the method will be _biased_.
What you should have done in your way of counting was to decrement the total_games when you encounter the a short win, and also also do not increment illegal or legal game counter. So if you intended to play a million games, then when you have one short game you should have considered as if you played 999999

In my next post I will try to repeat my post a couple of days ago showing why it is _biased_.
Are you ready for it? :)
Ready to go :-) I understand your intention (I already understood it before). Furthermore I hope that your proof will also care about all the other points I made before, including:

- that the product of all U(i) covers all ever-possible games, so also shorter games, so that not including the shorter games in nLegalGames sounds suspicious for me,

- that I could imagine, to achieve an even bigger level of perfection, to completely strip all game-terminating moves (i.e. mating or in theory stalemating) from all move lists except those at the last ply to ensure that we only play 100% full-length MC games (which could be slightly different from what you want to do due to the possibly different range of random numbers given by possibly smaller values of U(i)),

- and that I think that your proposed formula which I shorten as "estimatedPerft(N) := sum(i=1..N) ((nLegalGames / nTotalGames) * product(j=1..i) (U(i)))" adds parts to the perft estimation that are not included in the exact perft(N) value which only counts fulll-length paths.

Curious regards,
Sven

Like I have already said in my old post with an example, you use the summation forumula _if_ you want to count intermediate leaf nodes in your perft. If not then you ignore shorter games completely. In your case what should have been done is decrement the total_games count . I have stated that in my previous post , so please don't try to make that an issue now :) I am making some cool drawings.

Artistic regards,

Daniel Shawul
Posts: 3501
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Wed Jul 27, 2011 5:16 pm

Image

Take the tree in the first diagram. The upper bounds are
U(1) = 10, U(2) = 3 and U(3) = 10. Peter's method works on that legal tree itself.
OTOH Uri's method converts that to the hypothetical tree with illegal moves in it as shown
in the second drawing. You can see all nodes at the _same ply_ will have the same BF if illegal
moves are introduced. The second drawing is for the leftmost branch only, so the same thing happens
for the right part.

Now you can see that the probablity of a move (illegal or legal) being selected is
the same at each ply. So we can have
P(1) = 1/10
P(2) = 1/3
P(3) = 1/10
And the probablity of game ending at each ply is a product
PGame(1) = P(1) = 1/10
PGame(2) = P(1) * P(2) = 1/30
PGame(3) = P(1) * P(2) * P(3) = 1/300

Now when a random game reaches the last ply that is ply 3, it is rewarded by
R(3) = U(1) * U(2) * U(3) = 300
When it ends at ply 2
R(2) = U(1) * U(2) = 30
And if it ends at ply 1
R(1) = U(1) = 10

If it is illegal its reward is 0 at any ply.
R(illegal) = 0
So R * Pgame at each ply is 1, thereby counting the terminal nodes at each ply.
------------------------------------------------------
So with this understanding the total count _including_ all terminal nodes is as follows.
If you consider shorter games same way as longer games (treat them similarly)
Total = 300 * ( 1/ 300 * (2 + 3 + 3 + 3 + 10)) + 300 * (1/10) * 8
= 21 + 240 = 261 !!
That is way more than the expected 29.
If you want to calculate Perft(3) as those nodes that reach ply 3 only then
that is Perft(3) = 21.

To estimate that we should completely ignore shorter games in which case
Total = 300 * ( 1/ 300 * (2 + 3 + 3 + 3 + 10)) = 21
This is exactly what you should do. When you increment the total_games count you
are saying I had one long game that turned out illegal. That will underestimate the perft result making it below 21. Note that most of the games will be short since those 8 moves at ply 1 take away 80% of the games away and if you increment the total games with that number. The perft result will be a disaster. I am not sure what exactly the result will be but something around 20% of 21 that is 4!!
If you want to count _all_ leaf nodes use the proper reward at ply 1 for each of those 8 moves
Total = 21 + 10 * 1/10 * 8 = 21 + 8 = 29 which is the exact Pertt(3) including intermediate
terminal nodes.
I hope this makes it clear
cheers

Sven
Posts: 3697
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Perft(13) betting pool

Post by Sven » Wed Jul 27, 2011 5:38 pm

Daniel Shawul wrote:And the probablity of game ending at each ply is a product
PGame(1) = P(1) = 1/10
PGame(2) = P(1) * P(2) = 1/30
PGame(3) = P(1) * P(2) * P(3) = 1/300
I don't get this part. We are talking about "short games" as "legal but short games" when a legal move terminates the game by mate or any possible terminal draw. But you do not know the probability for that. The terms you are giving seem to be related to "illegal short games". Or did you mean that you define those probabilities to have the values you gave? Does not seem so.

That alone puts your example calculation into question.
Daniel Shawul wrote:Now when a random game reaches the last ply that is ply 3, it is rewarded by
R(3) = U(1) * U(2) * U(3) = 300
When it ends at ply 2
R(2) = U(1) * U(2) = 30
And if it ends at ply 1
R(1) = U(1) = 10
Here you are obviously talking about your proposal, to use the summation formula you gave. Two points arise for me:

1) In your previous post you wrote sth. like "use the summation formula ... if one wants to count also the short games within the perft estimate". But if I don't want to? Exact perft(N) does not count them.

2) A proof that Uri's method with all clarifications given so far were biased should not refer to formula like this which are not part of Uri's method. In Uri's formula all games ending at ply 1 or 2 are rewarded by 0, too.

Sven

Daniel Shawul
Posts: 3501
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Wed Jul 27, 2011 5:56 pm

I don't get this part. We are talking about "short games" as "legal but short games" when a legal move terminates the game by mate or any possible terminal draw. But you do not know the probability for that. The terms you are giving seem to be related to "illegal short games". Or did you mean that you define those probabilities to have the values you gave? Does not seem
Uri's tree complicates the calculation but proving Peter's method is easier since it is a _legal_game tree. It is buried somewhere in this thread.
The probabilities are assumed at _infinite_ number of games. Since we are using a Uniform PRNG. Each move whether legal/illegal will have a probability of 1/10 at ply 1. Then the probablity of any game (that reaches ply 3) being played is 1/10 * 1/3 * 1/10 = 1/300.
So the result we get is the expected value (after many number of games).
The 8 illegal short games will have each 1/10 resulting in 80% of all games going to them after many games are played. That is why they so bias the result. Even 1 short game at ply 1 bias the result by as much as 20.
Here you are obviously talking about your proposal, to use the summation formula you gave. Two points arise for me:

1) In your previous post you wrote sth. like "use the summation formula ... if one wants to count also the short games within the perft estimate". But if I don't want to? Exact perft(N) does not count them.
Use the summation formula if you want to count all intermediate leaf nodes in your perft. For example for an LMR perft this is much more sensible than counting only those that reach ply 13 f.i because they would be too few. Anyway just avoid infecting your legal games and total games count by shorter games to get 21 in my example.
The summation is for counting _all_ terminal nodes i.e to get a result of 29 in my example. Forget this one now.
2) A proof that Uri's method with all clarifications given so far were biased should not refer to formula like this which are not part of Uri's method.

Sven
See Uri has changed his mind when Peter proved his method as unbiased. He claims it is unbiased now. He even gave me a proof of it.
In Uri's formula all games ending at ply 1 or 2 are rewarded by 0, too.
You didn't read all of my post. When you increment the total_games count when you have shorter games. Or in your way of counting when you forget to decrement the total-games count then it becomes biased..
You would get something around 4 with what you are using now and that is after inifnite number of games.

I quote the relevant part
This is exactly what you should do. When you increment the total_games count you
are saying I had one long game that turned out illegal. That will underestimate the perft result making it below 21. Note that most of the games will be short since those 8 moves at ply 1 take away 80% of the games away and if you increment the total games with that number. The perft result will be a disaster. I am not sure what exactly the result will be but something around 20% of 21 that is 4!!
cheers

P.S: If you have doubts about my proof wait for Uri. I just used an example tree similar to what he has been using to proof biased ness.
Look at the proof for Peter's method using Uri's example some where in this thread.

Daniel Shawul
Posts: 3501
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Perft(13) betting pool

Post by Daniel Shawul » Wed Jul 27, 2011 6:08 pm

Ok, here is a similar proof using the same example for Peter's legal tree
I will list down all those 21 games at ply 3 and 8 games at ply 1 with their probabilities.

2x
(1/10,1/2,1/2)
3x
(1/10,1/2,1/3)
3x
(1/10,1/3,1/3)
3x
(1/10,1/3,1/3)
10x
(1/10,1/3,1/3)

And for ply 1 games
8X
(1/10)

The rewards will be
2x
40
3x
60
3x
90
3x
90
10x
300

And for ply 1 games
8x
10

So you see again the product of reward * probability = 1 needed for proof of unbiasedness. And it increment perft count by 1 each time

Got to got out for lunch now.
cheers

Sven
Posts: 3697
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Perft(13) betting pool

Post by Sven » Wed Jul 27, 2011 6:34 pm

Daniel Shawul wrote:
I don't get this part. We are talking about "short games" as "legal but short games" when a legal move terminates the game by mate or any possible terminal draw. But you do not know the probability for that. The terms you are giving seem to be related to "illegal short games". Or did you mean that you define those probabilities to have the values you gave? Does not seem
Uri's tree complicates the calculation but proving Peter's method is easier since it is a _legal_game tree. It is buried somewhere in this thread.
The probabilities are assumed at _infinite_ number of games. Since we are using a Uniform PRNG. Each move whether legal/illegal will have a probability of 1/10 at ply 1. Then the probablity of any game (that reaches ply 3) being played is 1/10 * 1/3 * 1/10 = 1/300.
So the result we get is the expected value (after many number of games).
The 8 illegal short games will have each 1/10 resulting in 80% of all games going to them after many games are played. That is why they so bias the result. Even 1 short game at ply 1 bias the result by as much as 20.
Here you are obviously talking about your proposal, to use the summation formula you gave. Two points arise for me:

1) In your previous post you wrote sth. like "use the summation formula ... if one wants to count also the short games within the perft estimate". But if I don't want to? Exact perft(N) does not count them.
Use the summation formula if you want to count all intermediate leaf nodes in your perft. For example for an LMR perft this is much more sensible than counting only those that reach ply 13 f.i because they would be too few. Anyway just avoid infecting your legal games and total games count by shorter games to get 21 in my example.
The summation is for counting _all_ terminal nodes i.e to get a result of 29 in my example. Forget this one now.
2) A proof that Uri's method with all clarifications given so far were biased should not refer to formula like this which are not part of Uri's method.

Sven
See Uri has changed his mind when Peter proved his method as unbiased. He claims it is unbiased now. He even gave me a proof of it.
In Uri's formula all games ending at ply 1 or 2 are rewarded by 0, too.
You didn't read all of my post. When you increment the total_games count when you have shorter games. Or in your way of counting when you forget to decrement the total-games count then it becomes biased..
You would get something around 4 with what you are using now and that is after inifnite number of games.

I quote the relevant part
This is exactly what you should do. When you increment the total_games count you
are saying I had one long game that turned out illegal. That will underestimate the perft result making it below 21. Note that most of the games will be short since those 8 moves at ply 1 take away 80% of the games away and if you increment the total games with that number. The perft result will be a disaster. I am not sure what exactly the result will be but something around 20% of 21 that is 4!!
cheers

P.S: If you have doubts about my proof wait for Uri. I just used an example tree similar to what he has been using to proof biased ness.
Look at the proof for Peter's method using Uri's example some where in this thread.
:?:

Sorry, Daniel, you are mixing up everything. You are too fast. Your way of argumentation is not fully logical. You refer to the proof for Peter's method which is nowhere doubted, but is completely irrelevant here. We are at the point where you wanted to prove that Uri's estimation method were biased when including nShortLegalGames within nTotalGames. I do not see that proof yet. You are not addressing the points I have made before, e.g. about "unknown probability of prematurely game-terminating legal moves (mate etc.)". You continue to talk about "illegal short games biasing the result" even though exactly the ratio of illegal vs. total games (from which the real result based on the ratio of legal vs. total games) forms the essential part of Uri's method.

What should I do next to make you understand what I wrote, and how Uri's method works?

I am off, too, until tomorrow. Have a nice evening!

Sven

Post Reply