Perft(13) betting pool

[Sven]

All this talk leads nowhere. Let us consider a real example. Suppose I have an LMR tree where each node has 10 moves, and the first 2 are searched at full depth, and the remaining 8 are reduced 1 ply. How would you take the p_i and w_i?

Help!

I fully agree to the quoted part that I emphasized above. But instead of continuing to discuss on the level of (old or new) examples, would all of you, HGM, Michel, and Daniel, please give a brief but sufficiently precise description of the method itself (algorithm, formula, ...) that you prefer for estimating perft(X), e.g. perft(13), without repeating your arguments or counter-arguments? I am running into big trouble to follow your discussion simply for the reason that the biggest part of it is repetition of arguments why A misunderstood B and why C is right and D is wrong

Please, to all of you three, if you try to do that, just limit yourself to describing the method, without any stuff like "which is what I already wrote 27 posts ago while all others consistently ignored it"

Sven

[Daniel Shawul]

What is the point of this modified example? Obviously I would select somewhere in the middle since the average tree size would still be in there and still mutiply by 10. If all moves are reduced equally , I would still select more often in the middle. My w_is is still 10. My estimate is biased. My heuristic is simple. So what ?

And you would proportion based on tree size, I get it. But how would you come up with those proportions in the first place for each move ? That asks for more heuristic than I am using.

[Daniel Shawul]

Please, to all of you three, if you try to do that, just limit yourself to describing the method, without any stuff like "which is what I already wrote 27 posts ago while all others consistently ignored it"

But belive me when I tell you that I need to do that in this case. Because I was under the impression that a biased method which is fast is for LMR perft is being sought. I knew it wouldn't give correct results and yet I am being bashed now because my method is biased. I even warned the "opponent" and got no reply. I knew that. I knew that. I knew that Then why don't we move on ? I don't know.

[hgm]

I think we are talking about a method where the perft(N) of each node is estimated as w_i*perft(N-1) of the single daughter position after a move i, selected with probability p_i.

This estimation can be used from the root (where it obviously makes sense only if you repeat it many times, and average the perft estimates) or only in deeper nodes of a conventional perft tree walk (where you automatically have many). That does not really matter.

About the example: so all your w_i are 10. So now tell us what your p_i are, so we can see how biased your estimate actually is...

As for my algorithm, I would figure that the unreduced trees are probably bigger than the reduced ones, and thus need higher p_i. I would not think they are 10times as big, because the LMR would probably reduce the effective branching factor compared to the real one. So I would make a wild guess that they are only 5 times as large, as I know it hardly matters whether my guess is good or bad.

So I would take p_1 = p_2 = 5/18, and the other eight p_i = 1/18. And I would take w_1 = w_2 = 18/5, and all other w_i = 18. (1 and 2 are the unreduced moves).

Now any bets as to who would be more accurate after 10, 100, 1k, 10k, 100k, 1Ms samples?

[Daniel Shawul]

I think we are talking about a method where the perft(N) of each node is estimated as w_i*perft(N-1) of the single daughter position after a move i, selected with probability p_i.

This estimation can be used from the root (where it obviously makes sense only if you repeat it many times, and average the perft estimates) or only in deeper nodes of a conventional perft tree walk (where you automatically have many). That does not really matter.

About the example: so all your w_i are 10. So now tell us what your p_i are, so we can see how biased your estimate actually is...

As for my algorithm, I would figure that the unreduced trees are probably bigger than the reduced ones, and thus need higher p_i. I would not think they are 10times as big, because the LMR would probably reduce the effective branching factor compared to the real one. So I would make a wild guess that they are only 5 times as large, as I know it hardly matters whether my guess is good or bad.

So I would take p_1 = p_2 = 5/18, and the other eight p_i = 1/18. And I would take w_1 = w_2 = 18/5, and all other w_i = 18. (1 and 2 are the unreduced moves).

Here we go again.
First your estimation is simply wrong. You need to know the _branching factor_ to compare subtree sizes. But you only gave depth reuction which makes it meaning less. _If_ we only reduced at the current ply I could use a formula like BF^N / BF^(N - 1) = BF so the un-reduced sub-trees is that much bigger than the reduced sub-tree. With recursive reductions it will be different but still dependent on BF. So it still needs us to estimate BF for our perft ?? That is why I keep on saying your heuristic better be damn good. The fact that you have 10 moves at one ply doesn't mean BF is 10 everywhere which you seem to be implying by your calculation. Infact it increases from ply to ply in the opening position.

Like I said my heuristic is simple and can give good estimates for the LMR perft we were talking about i.e if every move gets reduced by 1 such that
d , d-1, d-2, ...., 0 are the depths. That is the tree we experimented with.

[Daniel Shawul]

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.

[hgm]

Here we go again.
First your estimation is simply wrong.

Well, so what? Who cares? As long as it gives me the perft I am looking for with arbitrary good precicion,it is good enough for me...

You need to know the _branching factor_ to compare subtree sizes. But you only gave depth reuction which makes it meaning less. _If_ we only reduced at the current ply I could use a formula like BF^N / BF^(N - 1) = BF so the un-reduced sub-trees is that much bigger than the reduced sub-tree. With recursive reductions it will be different but still dependent on BF. So it still needs us to estimate BF for our perft ?? That is why I keep on saying your heuristic better be damn good. The fact that you have 10 moves at one ply doesn't mean BF is 10 everywhere which you seem to be implying by your calculation. Infact it increases from ply to ply in the opening position.

Like I said my heuristic is simple and can give good estimates for the LMR perft we were talking about i.e if every move gets reduced by 1 such that
d , d-1, d-2, ...., 0 are the depths. That is the tree we experimented with.

All words, and no substance.You still do not tell what your p_i are and which knowledge was required to obtain them. You still do not tell us how much off your result is...

[Daniel Shawul]

All words, and no substance.You still do not tell what your p_i are and which knowledge was required to obtain them. You still do not tell us how much off your result is...

Sounds like you are sorry you can't do your simple example right..
I said my estimate is biased but you jumped in with the unbiased assumption, so can't help you there. That was never my argument. The example we were discussing has an averge depth of d/2 which my simple heuristic gets right. Here you try to pull the mean away and then ask me how wrong it would be ?
Is that few enough words for you ? Promise next one will be shorter ..

[hgm]

OK, so the bottom line is your method cannot handle this simple case.

Ours could.

I would say that pretty much says it all, right?

[Daniel Shawul]

Yes your method can handle it with a magician's help.
I can ask him to tell me where the average is so improve my method too.