Perft(13) betting pool

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Daniel Shawul
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Perft(13) betting pool

Post by 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.
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Perft(13) betting pool

Post by Sven »

Daniel Shawul wrote:
Sven Schüle wrote:
Daniel Shawul wrote:Sven,
Uri is saying that he did not mean to count shorter games when he said count legal games. I see no where where he tells that shorter games should not be included but now he is claiming that is what he had in mind.
Did you increment the legal games count when shorter games are encountered or even the total games count. With the bit higher estimate i.e 1.997e18, I thought that could be the case.
My implementation counts shorter games as "illegal" games (i.e. "does not count them as legal"), and therefore also increments the total games counter for these. This is how I understood the initial description given by Uri, and this is also what I think is most natural. But it may be wrong, or not optimal, I don't know yet.
That is not you. I understood it that way too. This is the second time Uri writes something and says something else when I explained to him. Any game gets counted either as illegal or legal. How are we supposed to figure out we should never consider shorter games, only he knows.

Later I figured out that either those are counted separately at each ply and multiplied with their own Upper bounds OR should not be counted as games all. The later means you just assume shorter games never happened, both legal and total counts remain the same. If you increment even one of them it becomes _biased_. So now he is saying he meant the latter.
Sorry, I can't find such a statement by Uri. What he wrote a couple of pages above in this thread was:
Uri Blass wrote:I did not mean to count games which do not reach the last ply because they are not translated to a long sequence but only to a short sequence and I choose a random long sequence with my non efficient method.

Maybe there was a misunderstanding about my method but I certainly meant that a sequence is translated to a legal game only if all the numbers in it can be translated to legal moves(including the last number in it).
which seems to confirm exactly my (and your) initial understanding that shorter games should be counted as "illegal" games, but without mentioning a third category "legal (shorter) games not contributing to the total game counter".
Daniel Shawul wrote:
I think there is some confusion about the term "counting" in this context. The proposal you made a couple of posts above seems to imply that shorter games should not affect both the count of legal games and the total count of games. Could you please explain again why you expect this to be better than not doing so? You asked me to implement it but I did not do it so far, and would like to understand it first.
I don't know if it will change the result that much or not, but you could try the second method above which assumes the game never occurred when it ends prematurely. If a game ends at ply 4 for example, you are going to multiply them with an upper bound of U(1) * U(2) ... U(13), when in reality it should have been U(1)*U(2)*U(3). This can cause great inflations as I have shown in my previous example.
Still don't understand what you say ... Where do you see that shorter games are "multiplied with an upper bound of U(1) * U(2) ... U(13)"? Uri multiplies (nLegalGames / nTotalGames) with that term. Reducing nTotalGames by excluding all shorter games would even increase the overall result since you divide by nTotalGames.
Daniel Shawul wrote:
How does Peter's method deal with shorter games?

Should we even consider to exclude game-terminating moves from the list of generated moves (which might become expensive) so that our random games are always full-length games?
Yes just ignore the game when it becomes terminated before ply 13 is reached for Perft(13). I don't even know how many of those we have anyway ,but they could make the estimate biased.
Nobody answered my first question so far ... What I can see in Peter's implementation is that for shorter random games a node count of 0 is returned.

@Peter: Do you include these "0-games" in your final calculation of the average estimate or not?

@Daniel again: As to my second question, you did not get my point yet. I am not talking about only ignoring the *games* ending prematurely, I am talking about possibly excluding those moves from the move list that terminate the game prematurely. This would make all shorter games go away automatically since any random move selection - except at the last ply where end-of-game is no special case - would ensure that the game continues. Since perft counts full-length games only, this would be the most natural and consequent way of estimating perft(N) based on MC methods, regardless whether we are using the method of Uri, Peter, HGM or any other one. In case of Uri's method the upper bound values U(i) should be calculated based on the same principle, too, to be *very* accurate.

But the drawback of this would be the additional cost of detecting and excluding all game-terminating moves (except at last ply) at movegen time.

The question is also whether omitting this additional accuracy has a measurable effect on the estimate or not. If we state that it hasn't then we are back again at the point where the exact method of dealing with shorter games has to be defined. Here I vote for the simple way: count them as "illegal" but contributing to the total game count.

Sven
petero2
Posts: 683
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: Perft(13) betting pool

Post by petero2 »

Michel wrote:
I estimated the standard deviation to 2.22e16 for this weight function, so I gave up on that approach.
However this is still better than uniform MC isn't it? Is this for 10^6 games?

Anyway if one really wants to tune weights one shouldn't one have
error bars for the variance as well (to avoid drawing unsound conclusions)?
Yes this was for 1e6 games, and it is better than uniform MC, which gave me about 2.55e16.

I agree my tuning method was very unscientific as there were no error bars for the standard deviations. However, I think manually tuning the weights is too hard. I will try the idea to automatically estimate the x_i and the sigma_i during runtime instead.
Daniel Shawul
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Perft(13) betting pool

Post by Daniel Shawul »

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

Code: Select all

    Sum = &#40;legal_games&#91;1&#93; / Total_games&#91;1&#93;) * U&#40;1&#41;
         + &#40;legal_games&#91;2&#93; / Total_games&#91;2&#93;) * U&#40;1&#41; * U&#40;2&#41;
         ...
         + &#40;legal_games&#91;13&#93; / Total_games&#91;13&#93;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; ... * U&#40;13&#41;
To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = &#40;legal_games / total_games&#41; * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = (&#40;legal_games + 1&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = (&#40;legal_games&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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  = (&#40;legal_games&#41; / &#40;total_games&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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
Posts: 10216
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Perft(13) betting pool

Post by Uri Blass »

Daniel Shawul wrote:Here is the formula to count all leaf nodes including those shorter ones

Code: Select all

    Sum = &#40;legal_games&#91;1&#93; / Total_games&#91;1&#93;) * U&#40;1&#41;
         + &#40;legal_games&#91;2&#93; / Total_games&#91;2&#93;) * U&#40;1&#41; * U&#40;2&#41;
         ...
         + &#40;legal_games&#91;13&#93; / Total_games&#91;13&#93;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; ... * U&#40;13&#41;
To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = &#40;legal_games / total_games&#41; * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = (&#40;legal_games + 1&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = (&#40;legal_games&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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  = (&#40;legal_games&#41; / &#40;total_games&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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
Posts: 2271
Joined: Mon Sep 29, 2008 1:50 am

Re: Perft(13) betting pool

Post by 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
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Perft(13) betting pool

Post by Sven »

Uri Blass wrote:
Daniel Shawul wrote:Here is the formula to count all leaf nodes including those shorter ones

Code: Select all

    Sum = &#40;legal_games&#91;1&#93; / Total_games&#91;1&#93;) * U&#40;1&#41;
         + &#40;legal_games&#91;2&#93; / Total_games&#91;2&#93;) * U&#40;1&#41; * U&#40;2&#41;
         ...
         + &#40;legal_games&#91;13&#93; / Total_games&#91;13&#93;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; ... * U&#40;13&#41;
To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = &#40;legal_games / total_games&#41; * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = (&#40;legal_games + 1&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = (&#40;legal_games&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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  = (&#40;legal_games&#41; / &#40;total_games&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Perft(13) betting pool

Post by Daniel Shawul »

Daniel Shawul wrote: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&#40; log&#40;parent_nodes&#41; / child_nodes&#41;)
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&#41; Start from the root and do 10 Monte carlo simulations for each move
b&#41; Pick the best node to expand using UCB formula I provided above
c&#41; Expand the selected node which will be one of the biggest nodes with the right formula.
d&#41; 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
Posts: 4185
Joined: Tue Mar 14, 2006 11:34 am
Location: Ethiopia

Re: Perft(13) betting pool

Post by Daniel Shawul »

Sven Schüle wrote:
Uri Blass wrote:
Daniel Shawul wrote:Here is the formula to count all leaf nodes including those shorter ones

Code: Select all

    Sum = &#40;legal_games&#91;1&#93; / Total_games&#91;1&#93;) * U&#40;1&#41;
         + &#40;legal_games&#91;2&#93; / Total_games&#91;2&#93;) * U&#40;1&#41; * U&#40;2&#41;
         ...
         + &#40;legal_games&#91;13&#93; / Total_games&#91;13&#93;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; ... * U&#40;13&#41;
To count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)

Code: Select all

    Sum = &#40;legal_games / total_games&#41; * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
Now if you increment the legal_games when you have a short win at ply 2, it means we have

Code: Select all

    Sum  = (&#40;legal_games + 1&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
which is wrong!!
And if you count it as illegal which means you increment the total_games count only

Code: Select all

    Sum  = (&#40;legal_games&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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  = (&#40;legal_games&#41; / &#40;total_games&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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  = (&#40;legal_games&#41; / &#40;total_games&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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  = (&#40;legal_games&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Perft(13) betting pool

Post by Sven »

Daniel Shawul wrote: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.
Daniel Shawul wrote: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  = (&#40;legal_games&#41; / &#40;total_games + 1&#41;) * U&#40;1&#41; * U&#40;2&#41; * U&#40;3&#41; .... * U&#40;13&#41;
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