Questions for the Stockfish team

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Gerd Isenberg
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Are we missing something?

Post by Gerd Isenberg » Mon Jul 26, 2010 11:46 am

UncombedCoconut wrote:Hi, sorry my explanation did not help.
bhlangonijr wrote: 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.
bhlangonijr wrote: 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
Posts: 922
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Are we missing something?

Post by AlvaroBegue » Mon Jul 26, 2010 12:01 pm

Gerd Isenberg wrote: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
Posts: 319
Joined: Fri Dec 18, 2009 10:40 am
Location: Naperville, IL

Re: Are we missing something?

Post by UncombedCoconut » Mon Jul 26, 2010 6:12 pm

AlvaroBegue wrote:
Gerd Isenberg wrote: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
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Are we missing something?

Post by Chan Rasjid » Mon Jul 26, 2010 9:21 pm

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
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
michiguel
Posts: 6388
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Are we missing something?

Post by michiguel » Mon Jul 26, 2010 9:31 pm

Gerd Isenberg wrote:
UncombedCoconut wrote:Hi, sorry my explanation did not help.
bhlangonijr wrote: 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.
bhlangonijr wrote: 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
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Are we missing something?

Post by Gerd Isenberg » Mon Jul 26, 2010 9:50 pm

michiguel wrote: 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 ;-)

User avatar
michiguel
Posts: 6388
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Are we missing something?

Post by michiguel » Mon Jul 26, 2010 10:09 pm

Gerd Isenberg wrote:
michiguel wrote: 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
Posts: 2128
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Are we missing something?

Post by Gerd Isenberg » Mon Jul 26, 2010 10:29 pm

michiguel wrote:
Gerd Isenberg wrote:
michiguel wrote: 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
Posts: 482
Joined: Thu Oct 16, 2008 2:23 am
Location: Milky Way
Contact:

Re: Are we missing something?

Post by bhlangonijr » Mon Jul 26, 2010 11:47 pm

michiguel wrote:
Gerd Isenberg wrote:
michiguel wrote: 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
Posts: 319
Joined: Fri Dec 18, 2009 10:40 am
Location: Naperville, IL

Re: Are we missing something?

Post by UncombedCoconut » Mon Jul 26, 2010 11:56 pm

bhlangonijr wrote: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.

Post Reply