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