Perft(13) betting pool

[Daniel Shawul]

Here is the formula to count all leaf nodes including those shorter ones

Code: Select all

    Sum = (legal_games[1] / Total_games[1]) * U(1)
         + (legal_games[2] / Total_games[2]) * U(1) * U(2)
         ...
         + (legal_games[13] / Total_games[13]) * U(1) * U(2) * U(3) ... * U(13)

To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)

Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is again wrong!!
They are both wrong because they are being multiplied by the incorrect upper bound when
it should have been the upper bound perft value for that ply where the game terminated.

The correct _unbiased_ estimator will be to consider that the shorter game never happened i.e don't increment any of the counters

Code: Select all

    Sum  = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)

So he meant he meant this one. Otherwise his estimate will be _biased_

Let me make sure we are on the same page first before we continue.

[Uri Blass]

Here is the formula to count all leaf nodes including those shorter ones

Code: Select all

    Sum = (legal_games[1] / Total_games[1]) * U(1)
         + (legal_games[2] / Total_games[2]) * U(1) * U(2)
         ...
         + (legal_games[13] / Total_games[13]) * U(1) * U(2) * U(3) ... * U(13)

To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)

Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is again wrong!!
They are both wrong because they are being multiplied by the incorrect upper bound when
it should have been the upper bound perft value for that ply where the game terminated.

The correct _unbiased_ estimator will be to consider that the shorter game never happened i.e don't increment any of the counters

Code: Select all

    Sum  = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)

So he meant he meant this one. Otherwise his estimate will be _biased_

Let me make sure we are on the same page first before we continue.

I meant the last formula but I practically start by a random sequnece
in my method and not by a random game(in the meaning of a game in chess. I call every sequence a game in the total number of games so maybe the definition is confusing)

I have a random sequence 1<=X(1)<=U(1),...1<=X(n)<=U(n) when n=13
Every sequence increase the number of Total games.
I try to see if I can translate all the numbers to legal moves to increase the number of legal games.

If X(1),X(2),X(3),X(4) are translated to f3 e5 g4 Qh4 mate then the full sequence is counted in the total games but not in the legal games of 13 plies because the fact that I have X(5) means that I have a number that I cannot translate to a legal move so practically I increment the total games when I have a short win based on part of the sequence but I do not increment the legal games.

[Michel]

I will try the idea to automatically estimate the x_i and the sigma_i during runtime instead.

That would be very interesting (although it is not very clear to me
how to do this).

Even if it is expensive in CPU time it will still give an indication if a substantial variance reduction is achievable.

[Sven]

Here is the formula to count all leaf nodes including those shorter ones

Code: Select all

    Sum = (legal_games[1] / Total_games[1]) * U(1)
         + (legal_games[2] / Total_games[2]) * U(1) * U(2)
         ...
         + (legal_games[13] / Total_games[13]) * U(1) * U(2) * U(3) ... * U(13)

To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)

Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is again wrong!!
They are both wrong because they are being multiplied by the incorrect upper bound when
it should have been the upper bound perft value for that ply where the game terminated.

The correct _unbiased_ estimator will be to consider that the shorter game never happened i.e don't increment any of the counters

Code: Select all

    Sum  = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)

So he meant he meant this one. Otherwise his estimate will be _biased_

Let me make sure we are on the same page first before we continue.

I meant the last formula but I practically start by a random sequnece
in my method and not by a random game(in the meaning of a game in chess. I call every sequence a game in the total number of games so maybe the definition is confusing)

I have a random sequence 1<=X(1)<=U(1),...1<=X(n)<=U(n) when n=13
Every sequence increase the number of Total games.
I try to see if I can translate all the numbers to legal moves to increase the number of legal games.

If X(1),X(2),X(3),X(4) are translated to f3 e5 g4 Qh4 mate then the full sequence is counted in the total games but not in the legal games of 13 plies because the fact that I have X(5) means that I have a number that I cannot translate to a legal move so practically I increment the total games when I have a short win based on part of the sequence but I do not increment the legal games.

@Uri: I use your post to reply but the contents of my reply is directed mainly towards Daniel. Thanks for your clarification!
-----

@Daniel: this should clean up your slight misunderstanding

Apart from that, since I must assume that your reply was a reply to my previous post (I can't check it even in threaded view due to reaching maximum indentation ), what about my other points?

Back to the "short games" issue and to your proposed formula:
- How do you calculate Total_games for i < 13? Is it the number of (legal or illegal) games that ended after i moves?
- And if so, is this also the case for Total_games[13]?
- So is it right that essentially you want to include the estimated number of shorter games within the estimate for perft(13), even though the correct value for perft(13) will not include shorter paths?

Your formula is not obvious to me so I have to insist on pursuing the details.

Furthermore, since we now know that the term "total_games" also includes all shorter games in Uri's method, I do not get the point why you think that (legal_games / total_games) * U(1) * U(2) * ... * U(N) would be wrong somehow. The U(i) values, being maximum possible BFs, do cover all kinds of games, including also shorter ones, don't they? So either we include shorter games on both sides: in total_games and in U(i), or we exclude them on both sides, e.g. by removing all game-terminating moves from the move lists as I proposed above. Your proposal seems to be a mixture IMO.

Sven

[Daniel Shawul]

The reason why I wanted you to start from the root is because within the tree we are using _uniform_ sampling. One way to decrease the variance could be using upper confidence bound by saving the first 1-3 plies in memory. I mentioned the following formula a while back that is used for UCT, I am sure it can be modified to give much better results than any heuristic since this one learns it dynamically. But it requires complicated programming..

Code: Select all

X = Xmean + Constant * sqrt( log(parent_nodes) / child_nodes))

Select the node with maximum X value. The second term which is the variance is meant for a mean score between 0 < X < 1 but I am sure it can be modified for our case. Anyway even using simple proportioning based on mean nodes count at the tree, this _dynamic_ adjustement should be better than any heuristic.

Here the idea for this kickass algorithm. You can say it is UCT for perft but I haven't actually implemented it so it can be all for nothing if I made some mistake in planning somewhere

Code: Select all

a) Start from the root and do 10 Monte carlo simulations for each move
b) Pick the best node to expand using UCB formula I provided above
c) Expand the selected node which will be one of the biggest nodes with the right formula.
d) Do this recursively for the children of that big node

So this algorithm explores the bigger nodes more often, while the smaller nodes will have their estimates from small number of simulations. No need for heuristic, no need for fixed depth expansion unlike the one we are doing i.e ply 3-6 fixed with uniform sampling.

If I have to write out my imagination, this algorithm will be so good as to be the best. But I could be wrong somewhere. Opinions ?

[Daniel Shawul]

Here is the formula to count all leaf nodes including those shorter ones

Code: Select all

    Sum = (legal_games[1] / Total_games[1]) * U(1)
         + (legal_games[2] / Total_games[2]) * U(1) * U(2)
         ...
         + (legal_games[13] / Total_games[13]) * U(1) * U(2) * U(3) ... * U(13)

To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)

Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

which is again wrong!!
They are both wrong because they are being multiplied by the incorrect upper bound when
it should have been the upper bound perft value for that ply where the game terminated.

The correct _unbiased_ estimator will be to consider that the shorter game never happened i.e don't increment any of the counters

Code: Select all

    Sum  = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)

So he meant he meant this one. Otherwise his estimate will be _biased_

Let me make sure we are on the same page first before we continue.

I meant the last formula but I practically start by a random sequnece
in my method and not by a random game(in the meaning of a game in chess. I call every sequence a game in the total number of games so maybe the definition is confusing)

I have a random sequence 1<=X(1)<=U(1),...1<=X(n)<=U(n) when n=13
Every sequence increase the number of Total games.
I try to see if I can translate all the numbers to legal moves to increase the number of legal games.

If X(1),X(2),X(3),X(4) are translated to f3 e5 g4 Qh4 mate then the full sequence is counted in the total games but not in the legal games of 13 plies because the fact that I have X(5) means that I have a number that I cannot translate to a legal move so practically I increment the total games when I have a short win based on part of the sequence but I do not increment the legal games.

@Uri: I use your post to reply but the contents of my reply is directed mainly towards Daniel. Thanks for your clarification!
-----

@Daniel: this should clean up your slight misunderstanding

Yeah right But seriously I don't know if you are serious or not based on the questions you ask me below. He basically said we misunderstood him Or admitted to his method being biased (if he increments any of the counters when there is a shorter game) OR he didn't meant to count shorter ones at all.

Apart from that, since I must assume that your reply was a reply to my previous post (I can't check it even in threaded view due to reaching maximum indentation ), what about my other points?

Back to the "short games" issue and to your proposed formula:
- How do you calculate Total_games for i < 13? Is it the number of (legal or illegal) games that ended after i moves?
- And if so, is this also the case for Total_games[13]?
- So is it right that essentially you want to include the estimated number of shorter games within the estimate for perft(13), even though the correct value for perft(13) will not include shorter paths?

Your formula is not obvious to me so I have to insist on pursuing the details.

Furthermore, since we now know that the term "total_games" also includes all shorter games in Uri's method, I do not get the point why you think that (legal_games / total_games) * U(1) * U(2) * ... * U(N) would be wrong somehow. The U(i) values, being maximum possible BFs, do cover all kinds of games, including also shorter ones, don't they? So either we include shorter games on both sides: in total_games and in U(i), or we exclude them on both sides, e.g. by removing all game-terminating moves from the move lists as I proposed above. Your proposal seems to be a mixture IMO.

Sven

I am even confused by his recent reply.

I meant the last formula but I practically start by a random sequence
in my method and not by a random game(in the meaning of a game in chess. I call every sequence a game in the total number of games so maybe the definition is confusing)

So he means this

Code: Select all

    Sum  = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)

This doesn't increment any of them so it is _unbiased_.
Later he says this

If X(1),X(2),X(3),X(4) are translated to f3 e5 g4 Qh4 mate then the full sequence is counted in the total games but not in the legal games of 13 plies because the fact that I have X(5) means that I have a number that I cannot translate to a legal move so practically I increment the total games when I have a short win based on part of the sequence but I do not increment the legal games.

So this means the total games got incremented which implies the formula

Code: Select all

    Sum  = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)

So it becomes _biased_.

You said you also increment the total games so his method is biased.
So in your next post please select the formula you use and print it out so we avoid any possible confusions.

[Sven]

Yeah right But seriously I don't know if you are serious or not based on the questions you ask me below. He basically said we misunderstood him Or admitted to his method being biased (if he increments any of the counters when there is a shorter game) OR he didn't meant to count shorter ones at all.

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.

I am even confused by his recent reply.
[...]
Later he says this

If X(1),X(2),X(3),X(4) are translated to f3 e5 g4 Qh4 mate then the full sequence is counted in the total games but not in the legal games of 13 plies because the fact that I have X(5) means that I have a number that I cannot translate to a legal move so practically I increment the total games when I have a short win based on part of the sequence but I do not increment the legal games.

So this means the total games got incremented which implies the formula

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).

Sven

[Daniel Shawul]

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]

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]

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?