Perft(13) betting pool

[hgm]

If I am asked to estimate the perft with playing only _one_ game. I would bias my move selection towards the average value i.e 75 and multiply by 6.

This is nonsense. There is nothing for you to bias. You cannot pick moves with a relative probability 12:8:6:2:1 and then pick them with other probabilities at the same time...

[Daniel Shawul]

This is nonsense. There is nothing for you to bias. You cannot pick moves with a relative probability 12:8:6:2:1 and then pick them with other probabilities at the same time...

What does that mean at all ?
Anyway you should demonstrate your estimate with an example you prefer.

Edit:
Say sub-tree sizes are 120, 80, 60 , 20 and 10 for each of the moves.
Say you have some kind of heuristic to determine the weights i.e pick your multipliers and weights. Then play one game (simulation) and estimate perft for one ply tree. I hope it is clearer now...That is the object of biasing isn't it? To get better estimates with lower number of games as possible.

[Michel]

Ok I see the confusion.

The fact that the multiplier should be the inverse of the probabilty is
a universal law. It works for any collection of tree sizes.

Of course if you _know_ the tree sizes you can cheat and assign (probabilities,multipliers) which work for that particular collection.
Like picking 75 with probabilty 1 and using multiplier 363/75.

[Daniel Shawul]

Michael it is really very easy. I repeat the question here

Say sub-tree sizes are 120, 80, 60 , 20 and 10 for each of the moves.
Say you have some kind of heuristic to determine the weights i.e pick your multipliers and weights. Then play one game (simulation) and estimate perft for one ply tree. I hope it is clearer now...That is the object of biasing isn't it? To get better estimates with lower number of games as possible.

What I am saying is lets say you have a super-duper heuristic which can tell you the size of the trees. Lets _assume_ that then how do you distribute the probabilities. With fixed multiplier (number of legal moves i.e 5 in this case), biasing towards the larger or smaller sub-trees is bad!

You guys are saying the multiplier is also different. And you even said the multiplier multiplied with probablity is 1. Then what is the point if you get the same estimate which ever move you pick?? You don't know the average perft in the first place.

If you are sure about your argument please do the example and demonstrate how your weighing would work. Sorry but I can only say that you both forgot something...

[hgm]

That is the point. If the tree size is known, you just return that known size. Always 100% accurate.

This whole business of estimating is only useful for cases where you don't know the tree size, and it could be anything. So when you say sub-tree #1 is 150, you mean anything from 100 to 200, (say).

To get a correct average of the estimate when repeating thesampling infinitely often both when the sub-tree size is 100 and 200 is only possible when the weight times the sampling probability is exactly 1.

With a FIXED multiplier any biasing is bad. Not because it gives large variance, but because it gives a wrong value most of the time. First requirement is to get an estimate that is on average always CORRECT, so that you can converge it by driving up the number of samples. Only then it becomes convenient to have small variance, so it converges faster. Fastconvergence to a wrong value is not an asset. Being conditionaly correct (Like: "this sampling procedure gives me the correct value IF the tree size is 100") neither.

[Daniel Shawul]

That is the point. If the tree size is known, you just return that known size. Always 100% accurate.

This whole business of estimating is only useful for cases where you don't know the tree size, and it could be anything. So when you say sub-tree #1 is 150, you mean anything from 100 to 200, (say).

To get a correct average of the estimate when repeating thesampling infinitely often both when the sub-tree size is 100 and 200 is only possible when the weight times the sampling probability is exactly 1.

With a FIXED multiplier any biasing is bad. Not because it gives large variance, but because it gives a wrong value most of the time.

Yes it is biased we agreed up on that a long time ago.. This whole discussion started when we wanted to estimate it faster. I cautioned Micheal so many times already about _accuracy_ being the ultimate point here. Now I think you should withdraw your statement about me being wrong when I clearly did the example with a constant number of legal moves i.e 5. I am 100% right when I say that the heuristic should bias towards the average value. Yes of course you don't know which move gives that which is why I told Michael it is difficult to construct a heuristic!!

Ok moving on to your case,where different probabilities and multipliers are to be used as you and Michael said. I don't even know how that is going to work but I am cool to learn. With Michael suggestion so far the (probability * multiplier = 1) , which begs the question of what the point is? You also said any move picked will return the same value. But you both missed we don't know the average in the first place ...

The question is _given_ a good heuristic that estimates sub-tree sizes, how would you distribute the weights. Not towards the larger or smaller sub-trees according to what we have so far. If you say otherwise , please demonstrate with an example using different weights and multipliers as you suggested.

[hgm]

Yes it is biased we agreed up on that a long time ago.. This whole discussion started when we wanted to estimate it faster.

I agreed on no such thing. If your estimate is incorrect, we are done talking. Getting a wrong estimate faster is not an acheivement. I already suggested the ultimate method for that": Guess tree size = 0. You will have it iinstantly...

I cautioned Micheal so many times already about _accuracy_ being the ultimate point here. Now I think you should withdraw your statement about me being wrong when I clearly did the example with a constant number of legal moves i.e 5. I am 100% right when I say that the heuristic should bias towards the average value.

I don't agreeat all. But perhaps I misunderstand your goal. If it is to produce a meaningless number in an efficient way, you might do a good job. But I thought we were estimating the tree size by sampling. Whatyoupropose does NOT do that. So I think you are 100% wrong...

Yes of course you don't know which move gives that which is why I told Michael it is difficult to construct a heuristic!!

Ok moving on to your case,where different probabilities and multipliers are to be used as you and Michael said. I don't even know how that is going to work but I am cool to learn. With Michael suggestion so far the (probability * multiplier = 1) , which begs the question of what the point is? You also said any move picked will return the same value. But you both missed we don't know the average in the first place ...

Well, in the case of depth reduction you have good prior reason to assume the perft tree is 25 times smaller. So you would sample the non-reduced moves with 25 times larger probability than the reduced. That sometimes an unreduced perft is zero, because the position was a checkmate, is just bad luck, as there is no way to predict that. It is part of the intrinsic variance. But you canmake reasoable guesses based on the depth. Thatisnot unrealistic at all. And even when they are a bitoff, the worst that happens is that you do converge slightly slower than optimal. (But still much faster than with theprior assumption that reduced and unreduced treesareequally large on average/)

The question is _given_ a good heuristic that estimates sub-tree sizes, how would you distribute the weights. Not towards the larger or smaller sub-trees according to what we have so far. If you say otherwise , please demonstrate with an example using different weights and multipliers as you suggested.

We should destinguish two kind of examples:
1) To show that chosing weight * probability != 1 will give a wrong value.
2) Ofweight * probability == 1, the lowest variance is obtained by taking p_i proportional to sqrt(x_i^2+s+i^2).

Which would you like to see?

[Daniel Shawul]

I agreed on no such thing. If your estimate is incorrect, we are done talking. Getting a wrong estimate faster is not an acheivement. I already suggested the ultimate method for that": Guess tree size = 0. You will have it iinstantly...

Good then. So to make it clear we were discussing on a biased but faster estimator when you jumped in.

Here is the statement you failed to read before you jumped in.

It should certainly be possible to get to the perft estimate faster with a biased move selection. But we should keep in mind that here we are mainly concerned about accuracy of estimate more than speed. I think in about 1 million games three significant digits will be secured. The faster we try we make the more unreliable the result will be. If you look at my result with LMR perft, the biased estimator gave a better result than the unbiased one. Then I thought wrongly that it was better. But the reality was non-uniform trees require much more number of games than uniform perft like trees to get better estimates.. I don't know how many games will actually be required because Peter got also 30% off result after so many games, but in theory it should converge to the correct result. I am still curious to know how many more games will be required..

Btw for tree search speed is more important than accuracy. For instance UCT tree search with a plain uniform PRNG is proven to give exact results as alpha-beta search with infinite number of games, since it is an unbiased estimator. But in practice the biased approach is prefered because it gives better results with lower number of games.

I don't agreeat all. But perhaps I misunderstand your goal. If it is to produce a meaningless number in an efficient way, you might do a good job. But I thought we were estimating the tree size by sampling. Whatyoupropose does NOT do that. So I think you are 100% wrong...

Reply to another blabber from you

It should certainly be possible to get to the perft estimate faster with a biased move selection. But we should keep in mind that here we are mainly concerned about accuracy of estimate more than speed. I think in about 1 million games three significant digits will be secured. The faster we try we make the more unreliable the result will be. If you look at my result with LMR perft, the biased estimator gave a better result than the unbiased one. Then I thought wrongly that it was better. But the reality was non-uniform trees require much more number of games than uniform perft like trees to get better estimates.. I don't know how many games will actually be required because Peter got also 30% off result after so many games, but in theory it should converge to the correct result. I am still curious to know how many more games will be required..

[hgm]

It should certainly be possible to get to the perft estimate faster with a biased move selection. But we should keep in mind that here we are mainly concerned about accuracy of estimate more than speed. I think in about 1 million games three significant digits will be secured. The faster we try we make the more unreliable the result will be. If you look at my result with LMR perft, the biased estimator gave a better result than the unbiased one. Then I thought wrongly that it was better. But the reality was non-uniform trees require much more number of games than uniform perft like trees to get better estimates.. I don't know how many games will actually be required because Peter got also 30% off result after so many games, but in theory it should converge to the correct result. I am still curious to know how many more games will be required..

That does not say anything about making an incorrect estimate. It only talks about biasing the move selection, not about biasing the estimate. I (and also Michel) of course have always assumed you wanted to do that while keeping the estimate correct, rather than turning it into a random-number generator for numbers of the order of, but otherwise unrelated to the tree size. Which is trivial to do (by compensating the bias with the weights by keeping the product equal to 1).

[Daniel Shawul]

It should certainly be possible to get to the perft estimate faster with a biased move selection. But we should keep in mind that here we are mainly concerned about accuracy of estimate more than speed. I think in about 1 million games three significant digits will be secured. The faster we try we make the more unreliable the result will be. If you look at my result with LMR perft, the biased estimator gave a better result than the unbiased one. Then I thought wrongly that it was better. But the reality was non-uniform trees require much more number of games than uniform perft like trees to get better estimates.. I don't know how many games will actually be required because Peter got also 30% off result after so many games, but in theory it should converge to the correct result. I am still curious to know how many more games will be required..

That does not say anything about making an incorrect estimate. It only talks about biasing the move selection, not about biasing the estimate. I (and also Michel) of course have always assumed you wanted to do that while keeping the estimate correct, rather than turning it into a random-number generator for numbers of the order of, but otherwise unrelated to the tree size. Which is trivial to do (by compensating the bias with the weights by keeping the product equal to 1).

I said we are concerned about accuracy than speed ! What else does it mean ? You can reach to some target with lightning bolt speed and yet is an incorrect result.. Isn't what you were trying to make fun of before you realized I did infact mention that?

I even compared it with normal tree search and that the opposite is true in that case.

Btw for tree search speed is more important than accuracy. For instance UCT tree search with a plain uniform PRNG is proven to give exact results as alpha-beta search with infinite number of games, since it is an unbiased estimator. But in practice the biased approach is prefered because it gives better results with lower number of games.

I am sure I can dig up some more but by now it should be clear.