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.
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.
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.
One more note regarding the estimate of 1.997...e+18 I published a while ago after quickly implementing the method of Uri in my engine. There are at least two factors influencing the accuracy of that number:
1) the low number of sample games I was able to play so far,
2) the fact that the perft(1) upper bound values U(i) are only approximated values u(i) <= U(i) for all i > 7 (or i > 8, I don't remember).
That might explain why this estimate is different from some other estimates given here. The value is simply not accurate enough yet. My CPU time available for such tasks is limited, so please be patient ...
Sven
Those may be possible reasons. I am not sure if the change I proposed will fix it but I am sure the method was biased as we understood it.
Take your time please. As you see I am busy getting bashed
cheers