Code: Select all
X = Xmean + Constant * sqrt( log(parent_nodes) / child_nodes))
Moderators: hgm, Harvey Williamson, bob
Code: Select all
X = Xmean + Constant * sqrt( log(parent_nodes) / child_nodes))
Sorry, I can't find such a statement by Uri. What he wrote a couple of pages above in this thread was:Daniel Shawul wrote: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.Sven Schüle wrote: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.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.
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.
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".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).
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: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.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.
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.Daniel Shawul wrote: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.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 this was for 1e6 games, and it is better than uniform MC, which gave me about 2.55e16.Michel wrote:However this is still better than uniform MC isn't it? Is this for 10^6 games?I estimated the standard deviation to 2.22e16 for this weight function, so I gave up on that approach.
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)?
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)
Code: Select all
Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)
Code: Select all
Sum = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
Code: Select all
Sum = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
Code: Select all
Sum = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)
I meant the last formula but I practically start by a random sequneceDaniel Shawul wrote:Here is the formula to count all leaf nodes including those shorter onesTo count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)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)
Now if you increment the legal_games when you have a short win at ply 2, it means we haveCode: Select all
Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)
which is wrong!!Code: Select all
Sum = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
And if you count it as illegal which means you increment the total_games count onlywhich is again wrong!!Code: Select all
Sum = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
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 countersSo he meant he meant this one. Otherwise his estimate will be _biased_Code: Select all
Sum = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)
Let me make sure we are on the same page first before we continue.
That would be very interesting (although it is not very clear to meI will try the idea to automatically estimate the x_i and the sigma_i during runtime instead.
@Uri: I use your post to reply but the contents of my reply is directed mainly towards Daniel. Thanks for your clarification!Uri Blass wrote:I meant the last formula but I practically start by a random sequneceDaniel Shawul wrote:Here is the formula to count all leaf nodes including those shorter onesTo count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)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)
Now if you increment the legal_games when you have a short win at ply 2, it means we haveCode: Select all
Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)
which is wrong!!Code: Select all
Sum = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
And if you count it as illegal which means you increment the total_games count onlywhich is again wrong!!Code: Select all
Sum = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
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 countersSo he meant he meant this one. Otherwise his estimate will be _biased_Code: Select all
Sum = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)
Let me make sure we are on the same page first before we continue.
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.
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 somewhereDaniel 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..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.Code: Select all
X = Xmean + Constant * sqrt( log(parent_nodes) / child_nodes))
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
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.Sven Schüle wrote:@Uri: I use your post to reply but the contents of my reply is directed mainly towards Daniel. Thanks for your clarification!Uri Blass wrote:I meant the last formula but I practically start by a random sequneceDaniel Shawul wrote:Here is the formula to count all leaf nodes including those shorter onesTo count leaf nodes at ply 13 only Uri uses (Note we have one counter for both)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)
Now if you increment the legal_games when you have a short win at ply 2, it means we haveCode: Select all
Sum = (legal_games / total_games) * U(1) * U(2) * U(3) .... * U(13)
which is wrong!!Code: Select all
Sum = ((legal_games + 1) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
And if you count it as illegal which means you increment the total_games count onlywhich is again wrong!!Code: Select all
Sum = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
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 countersSo he meant he meant this one. Otherwise his estimate will be _biased_Code: Select all
Sum = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)
Let me make sure we are on the same page first before we continue.
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.
-----
@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
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)
Code: Select all
Sum = ((legal_games) / (total_games)) * U(1) * U(2) * U(3) .... * U(13)
So this means the total games got incremented which implies the formulaIf 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.
Code: Select all
Sum = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)
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.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.
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.Daniel Shawul wrote:I am even confused by his recent reply.
[...]
Later he says thisSo this means the total games got incremented which implies the formulaIf 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.Code: Select all
Sum = ((legal_games) / (total_games + 1)) * U(1) * U(2) * U(3) .... * U(13)