Questions for the Stockfish team

[Gerd Isenberg]

Hi, sorry my explanation did not help.

Hi Justin,

Thanks for the explanation, but I'm afraid I didn't get it right.

I have to mention the number of leaves N is in practice way bigger than the number of distinct random numbers. For instance, I have random integer numbers in the range [0..99] for which will be randomly distributed in the subsequent evaluations calls from the leaves. When you say "N random numbers" it appears you are assigning distinct random numbers for each leaf node. Is that what you meant?

Oh, no, I just meant N outputs from RNG; it's fine if many of them are equal numerically. Imagine making seven dice-rolls: that generates seven random numbers, although you'll get at most six distinct numbers after reading the dice.

The point is alpha-beta will visit only a sub-set of the leaf nodes from the whole game tree. For this obvious reason minimax has a higher probability of getting a bigger number, as it will look at every leaf node from the whole game tree. Again: The random evaluation is position _independent_!

The extra nodes sampled by minimax (vs. alpha-beta) are ones which cannot change the minimax value. Minimax will be able to get a bigger number for some subtrees, but only subtrees which do not matter because the opponent would not allow them to be reached.

hmm ...

The first depth two tree prunes backward (x) and performs 4 "random" leaf evals - {3, 5, 0, 2}. The second is pure minimax and needs two more leaf evals, which may influence the the root as demonstrated. I admit that with bigger bf it becomes more improbable, anyway ...

Code: Select all

           3

     /     |      \
   3       0       2
 /   \    / x     / x
3     5  0   x   2   x


           4

     /     |      \
   3       0       4
 /   \    / \     / \
3     5  0   2   4   5

[AlvaroBegue]

hmm ...

The first depth two tree prunes backward (x) and performs 4 "random" leaf evals - {3, 5, 0, 2}. The second is pure minimax and needs two more leaf evals, which may influence the the root as demonstrated. I admit that with bigger bf it becomes more improbable, anyway ...

Code: Select all

           3

     /     |      \
   3       0       2
 /   \    / x     / x
3     5  0   x   2   x


           4

     /     |      \
   3       0       4
 /   \    / \     / \
3     5  0   2   4   5

Nobody thinks that a specific sequence of numbers, when used as leaf evaluations in minimax or alpha-beta, will give you the same results. If the leaf evaluations are independent and identically distributed random variables, the minimax procedure to back up scores results in a score at the root that is itself a random variable. In a particular search, we are simply sampling one number out of that random variable. The statement is that whether you use alpha-beta pruning or not, you are sampling the same random variable.

[UncombedCoconut]

hmm ...

The first depth two tree prunes backward (x) and performs 4 "random" leaf evals - {3, 5, 0, 2}. The second is pure minimax and needs two more leaf evals, which may influence the the root as demonstrated. I admit that with bigger bf it becomes more improbable, anyway ...

Code: Select all

           3

     /     |      \
   3       0       2
 /   \    / x     / x
3     5  0   x   2   x


           4

     /     |      \
   3       0       4
 /   \    / \     / \
3     5  0   2   4   5

Nobody thinks that a specific sequence of numbers, when used as leaf evaluations in minimax or alpha-beta, will give you the same results. If the leaf evaluations are independent and identically distributed random variables, the minimax procedure to back up scores results in a score at the root that is itself a random variable. In a particular search, we are simply sampling one number out of that random variable. The statement is that whether you use alpha-beta pruning or not, you are sampling the same random variable.

Yes, exactly: the same sequence won't give the same result, but you can translate between inputs to the two algorithms: for instance, I would have used minimax(3,5,0,4,2,5) and still gotten 3.

In my explanation, I "padded" alpha-beta on this tree so it always reads in 6 samples, say your RNG's (3,5,0,2,4,5). I'm guessing that you and Ben-Hur would not like this very much, because alpha-beta just ignores the "x,x" from any input of the form (3,5,0,2,x,x). But minimax would "ignore" the same amount of its random data given input of the form (3,5,0,x,2,x).

I still haven't given thought to the effects of a tree-searching algorithm like PVS: if you do a zero-window search, have to do a full-window re-search, and might sample different leaf values the second time, what changes? It's a more complex question, unless of course you make the "random" number a function of the position.

[Chan Rasjid]

I realized that the "proof" I gave in my last post was no proof as the statement about probability was only true intuitively - "the more moves, the more chances". I now have the proof but I am still uncertain if all these proofs are really acceptable.

At a node with an inherited search bounds (alpha, beta) and N moves, let the scores returned from search() be x(1), x(2),...x(N). For i < N, let P_max(i) be the probability that the max of {x(1), ...x(i)} falls within the open interval (alpha, beta).
1) As there is no reason the value x(i+1) must be outside of the interval (alpha, beta), it has a probability p > 0 to be within the interval. Therefore P_max(i+1) = P_max(i) + p;
2) There is no reason the probability of max(x(i+1), ..., x(N)) be >= beta, i.e the probability that the max of x(1), ..., x(N) be within (alpha, beta) is not 0.

The above 1) and 2) shows the probablity that an alphabeta node returns an exact score increases with N. It might be true for whatever manner of values eval() returns.

Rasjid

[michiguel]

Hi, sorry my explanation did not help.

Hi Justin,

Thanks for the explanation, but I'm afraid I didn't get it right.

I have to mention the number of leaves N is in practice way bigger than the number of distinct random numbers. For instance, I have random integer numbers in the range [0..99] for which will be randomly distributed in the subsequent evaluations calls from the leaves. When you say "N random numbers" it appears you are assigning distinct random numbers for each leaf node. Is that what you meant?

Oh, no, I just meant N outputs from RNG; it's fine if many of them are equal numerically. Imagine making seven dice-rolls: that generates seven random numbers, although you'll get at most six distinct numbers after reading the dice.

The point is alpha-beta will visit only a sub-set of the leaf nodes from the whole game tree. For this obvious reason minimax has a higher probability of getting a bigger number, as it will look at every leaf node from the whole game tree. Again: The random evaluation is position _independent_!

The extra nodes sampled by minimax (vs. alpha-beta) are ones which cannot change the minimax value. Minimax will be able to get a bigger number for some subtrees, but only subtrees which do not matter because the opponent would not allow them to be reached.

hmm ...

The first depth two tree prunes backward (x) and performs 4 "random" leaf evals - {3, 5, 0, 2}. The second is pure minimax and needs two more leaf evals, which may influence the the root as demonstrated. I admit that with bigger bf it becomes more improbable, anyway ...

Code: Select all

           3

     /     |      \
   3       0       2
 /   \    / x     / x
3     5  0   x   2   x


           4

     /     |      \
   3       0       4
 /   \    / \     / \
3     5  0   2   4   5

That is not related to alpha-beta vs minimax. It is related to the fact that the random number sequence change. You may have the same effect running the analysis twice.

Miguel

[Gerd Isenberg]

That is not related to alpha-beta vs minimax. It is related to the fact that the random number sequence change. You may have the same effect running the analysis twice.

Miguel

Deterministic prng with same seed for position independent randoms

[michiguel]

That is not related to alpha-beta vs minimax. It is related to the fact that the random number sequence change. You may have the same effect running the analysis twice.

Miguel

Deterministic prng with same seed for position independent randoms

I know.

I still fail to see why anybody would like to run this as minimax. It is an expensive way to change the pseudo-random sequence.

Miguel

[Gerd Isenberg]

That is not related to alpha-beta vs minimax. It is related to the fact that the random number sequence change. You may have the same effect running the analysis twice.

Miguel

Deterministic prng with same seed for position independent randoms

I know.

I still fail to see why anybody would like to run this as minimax. It is an expensive way to change the pseudo-random sequence.

Miguel

Sure, nobody would use minimax. The point was position independent random eval somehow "contradicts" the alpha-beta equals minimax paradigm. Pure thought experiment, may be related to conspiracy numbers?

Gerd

[bhlangonijr]

That is not related to alpha-beta vs minimax. It is related to the fact that the random number sequence change. You may have the same effect running the analysis twice.

Miguel

Deterministic prng with same seed for position independent randoms

I know.

I still fail to see why anybody would like to run this as minimax. It is an expensive way to change the pseudo-random sequence.

Miguel

I agree with Gerd: It's pure thought experiment.
This is not about best results. The best we can get here is at most a bloated method for calculating mobility anyway...

The point I was making here is that Beal and Smith conducted the "random minimaxing" experiment using minimax in its pure form.

Alpha-beta pruning relies on the dichotomic property of conventional evaluation functions: If black is winning then white is loosing. So it really doesn't make sense looking further if my score >= beta.

The so called Beal effect is strongly related to the dominance - real mobility - property that emerges from the game tree as I search deeper. My concern here is not about the equivalence of probability for random scores backed up to root score. It is actually on how it will affect the probability of chosing a "good" move. For the sake of argument, the "good" move means that it is better than a move picked up randomly. I believe that using alpha-beta would reduce that probability.
That's it.

[UncombedCoconut]

My concern here is not about the equivalence of probability for random scores backed up to root score. It is actually on how it will affect the probability of chosing a "good" move. For the sake of argument, the "good" move means that it is better than a move picked up randomly. I believe that using alpha-beta would reduce that probability.
That's it.

My argument, assuming it is correct, shows that any given root score and best move is returned with equal probability whether you use minimax or alpha-beta. So the quality of move selection is the same.