Questions for the Stockfish team

[Gerd Isenberg]

I looked back through the thread a bit, and see this has already been rehashed. I have not looked through all of it though, so must have missed some I am sure (the thread is kind of long at this point).

OK, it is a good point many have made...different numbers are indeed generated. However, it seems like the same properties should hold right? I don't see any reason for alpha-beta to detract from the effects aimed for in any way...the nodes not expanded are known to have no effect if they are expanded, and while they change what number will be generated next by causing the pseudo-number generator to use a different seed...why would that be a bad thing? It just doesn't make sense to me that skipping superfluous random number generations should fundamentally effect the properties of the tree.

I apologize if this has already been covered and I am rehashing old areas. Feel free to ignore me, reference me to old posts, or call me stupid if desired.

-Sam

Hehe, no need to apologize, Sam. Seems alpha-beta isn't the best algorithm to demonstrate the Beal effect. I think the guys from other game domains like Backgammon considering chance nodes, or the Monte Carlo UCT (Upper Confidence bounds applied to Trees) searchers have some better understanding of what happens here

Cheers,
Gerd

[bob]

I looked back through the thread a bit, and see this has already been rehashed. I have not looked through all of it though, so must have missed some I am sure (the thread is kind of long at this point).

OK, it is a good point many have made...different numbers are indeed generated. However, it seems like the same properties should hold right? I don't see any reason for alpha-beta to detract from the effects aimed for in any way...the nodes not expanded are known to have no effect if they are expanded, and while they change what number will be generated next by causing the pseudo-number generator to use a different seed...why would that be a bad thing? It just doesn't make sense to me that skipping superfluous random number generations should fundamentally effect the properties of the tree.

I apologize if this has already been covered and I am rehashing old areas. Feel free to ignore me, reference me to old posts, or call me stupid if desired.

-Sam

The more I think about it, the more I think you are correct here. We are still using alpha/beta to "prove" that one branch has better (or worse) mobility than another. The main plus for minimax would be reduced depth, which reduces this "Beal effect". I have artificially done this in 23.3 anyway, to address the "too strong" issue...

[bob]

1. you mentioned:

skill=1 turns all pruning, reductions and extensions completely off...

does this include that qs will stop when depth = -x (-1) ?

No. search and q-search are completely unmodified. The only thing that gets whacked out is the null-move reduction depth (set to zero), LMR reductions (both are set to zero), etc. But the code doesn't change in search. Only change is in evaluate where the evaluation picks up the random part.

2. if not...

well, emulating mobility works better the higher the branching factor is.

qsSearch-subtree has by its nature a smaller bf than a simple mm-tree(or ab).

And because emulating mobility is sensitive to the bf, i see at least
two reasons not to compare emulating-mm(ab)-mobility with emulating-qs-mobility.

- the bf
- and the undefined search depth.

I don't think the q-search hurts a thing. What it does is to search a very narrow tree, and back up the "best" score to the first full-width ply. And that ply is where the real "mobility" effect comes from..

(so, qs is _only_ sampling,measuring tactical moves, and will give a probability to
have a capture,promotion.Thats what i meant with _tacticalMobility_, and i think
it is just another subject which the sampling is based on, than it was researched
by Beal (?!y/n this is a question) )

maybe the quintessence of sampling/emulating mobility vs. _tacticalMobility_
is the same, but maybe not.

Anyway, thx for response

regards, Michael

[michiguel]

I looked back through the thread a bit, and see this has already been rehashed. I have not looked through all of it though, so must have missed some I am sure (the thread is kind of long at this point).

OK, it is a good point many have made...different numbers are indeed generated. However, it seems like the same properties should hold right? I don't see any reason for alpha-beta to detract from the effects aimed for in any way...the nodes not expanded are known to have no effect if they are expanded, and while they change what number will be generated next by causing the pseudo-number generator to use a different seed...why would that be a bad thing? It just doesn't make sense to me that skipping superfluous random number generations should fundamentally effect the properties of the tree.

I apologize if this has already been covered and I am rehashing old areas. Feel free to ignore me, reference me to old posts, or call me stupid if desired.

-Sam

Yes, I really do not understand what is the purpose of keep searching when you found a cutoff already. Whether the score is ridiculous (i.e. random) is irrelevant. No matter how much you keep searching, you will return beta anyway.

Miguel

[michiguel]

I looked back through the thread a bit, and see this has already been rehashed. I have not looked through all of it though, so must have missed some I am sure (the thread is kind of long at this point).

OK, it is a good point many have made...different numbers are indeed generated. However, it seems like the same properties should hold right? I don't see any reason for alpha-beta to detract from the effects aimed for in any way...the nodes not expanded are known to have no effect if they are expanded, and while they change what number will be generated next by causing the pseudo-number generator to use a different seed...why would that be a bad thing? It just doesn't make sense to me that skipping superfluous random number generations should fundamentally effect the properties of the tree.

I apologize if this has already been covered and I am rehashing old areas. Feel free to ignore me, reference me to old posts, or call me stupid if desired.

-Sam

Hehe, no need to apologize, Sam. Seems alpha-beta isn't the best algorithm to demonstrate the Beal effect. I think the guys from other game domains like Backgammon considering chance nodes, or the Monte Carlo UCT (Upper Confidence bounds applied to Trees) searchers have some better understanding of what happens here

Cheers,
Gerd

Alpha beta is better than minimax to demonstrate the beal effect because it is faster (the deeper, the more pronounced is the effect).

Miguel

[bhlangonijr]

If PRNG results were truly i.i.d. random variables, minimax and plain alpha-beta from the same root position give the same probability distribution for score / root move. What's less clear is what happens when aspiration windows and re-searches are used, if searching a subtree twice can give different results.

If it is true I should withdraw the statements I've made here. Can you point me to some background regarding your assertion?

[Chan Rasjid]

I looked back through the thread a bit, and see this has already been rehashed. I have not looked through all of it though, so must have missed some I am sure (the thread is kind of long at this point).

OK, it is a good point many have made...different numbers are indeed generated. However, it seems like the same properties should hold right? I don't see any reason for alpha-beta to detract from the effects aimed for in any way...the nodes not expanded are known to have no effect if they are expanded, and while they change what number will be generated next by causing the pseudo-number generator to use a different seed...why would that be a bad thing? It just doesn't make sense to me that skipping superfluous random number generations should fundamentally effect the properties of the tree.

I apologize if this has already been covered and I am rehashing old areas. Feel free to ignore me, reference me to old posts, or call me stupid if desired.

-Sam

I don't yet understand minimax fully and less so what pure minimax is. Neither do I know much of what is a game of "perfect information". I try only to post what I seem to know as correct with much holes in knowledge and uses "intuition" (?) to fill the gaps.

Alphabeta should be sufficient in demonstrating the Beal effect - the Beal Effect is minimax search with "perfect knowledge". It is just a peculiar aspect of minimax and, maybe, the Beal effect is nature's way about "perfect knowledge" which is above "perfect information" - both players equally and absolutely have perfect knowledge when both have no knowledge.

Only a while ago did I know what is meant by "random numbers independent of positions" :-
1) a normal alphabeta returns a deterministic best pv barring subtleties.
2) alphabeta with a random evaluation from hash also returns a deterministic best pv.
3) alphabeta with a evaluation from rand() do not return a deterministic best pv. It may return any one of the legal moves as the best move and research don't give the same pv.
But both 2) and 3) should exhibit the Beal Effect and possibly with the same probabilistic properties.

I think it might be possible to analyze the Beal effect without knowing much what happen at the leaves but through bounds (alpha, beta) passed up and the best score passed down the tree. At any node with (alpha, beta) and N search scores to select from, the probability that the node is the new pv increases with N. It does not matter if this node fails low or fails high. The pv will exhibit the Beal Effect.

4) The score return from the root search probably could also be used as a random number generator.
5) The best move returned is NOT a random move selected randomly, but selected "intelligently" due to the Beal's effect.

Rasjid

[UncombedCoconut]

If PRNG results were truly i.i.d. random variables, minimax and plain alpha-beta from the same root position give the same probability distribution for score / root move. What's less clear is what happens when aspiration windows and re-searches are used, if searching a subtree twice can give different results.

If it is true I should withdraw the statements I've made here. Can you point me to some background regarding your assertion?

It's basically because minimax itself can be said to "ignore" all nodes pruned by alpha-beta. Here's my attempt at a complete explanation.

Consider a fixed game tree, with N leaves.
Treat minimax and alpha-beta, on that tree, as functions of N random numbers: just plug them in, in order, when the algorithm calls evaluate.
Say you have an input, r[1] .. r[N], to alpha-beta. Form a corresponding input e[1] .. e[N] to minimax as follows:
Say the evaluations made by alpha-beta are of the leaf nodes numbered l[1] .. l[n].
Set e[l] = r, i = 1 .. n.
Map the final (unused) inputs to alpha-beta to the remaining (unconsulted) leaf nodes.
By construction, (r[1] .. r[n]) -> (e[1] .. e[n]) is a bijection.
Since alpha-beta pruning is sound, alpha-beta(r[1] .. r[n]) = minimax(e[1] .. e[n]).
Since the bijection works by permuting inputs (which are i.i.d.), the input sequences r[1] .. r[n] and e[1] .. e[n] are equally probable.
All this means the output of alpha-beta and the output of minimax are equivalent random variables.

[bhlangonijr]

If PRNG results were truly i.i.d. random variables, minimax and plain alpha-beta from the same root position give the same probability distribution for score / root move. What's less clear is what happens when aspiration windows and re-searches are used, if searching a subtree twice can give different results.

If it is true I should withdraw the statements I've made here. Can you point me to some background regarding your assertion?

It's basically because minimax itself can be said to "ignore" all nodes pruned by alpha-beta. Here's my attempt at a complete explanation.

Consider a fixed game tree, with N leaves.
Treat minimax and alpha-beta, on that tree, as functions of N random numbers: just plug them in, in order, when the algorithm calls evaluate.
Say you have an input, r[1] .. r[N], to alpha-beta. Form a corresponding input e[1] .. e[N] to minimax as follows:
Say the evaluations made by alpha-beta are of the leaf nodes numbered l[1] .. l[n].
Set e[l] = r, i = 1 .. n.
Map the final (unused) inputs to alpha-beta to the remaining (unconsulted) leaf nodes.
By construction, (r[1] .. r[n]) -> (e[1] .. e[n]) is a bijection.
Since alpha-beta pruning is sound, alpha-beta(r[1] .. r[n]) = minimax(e[1] .. e[n]).
Since the bijection works by permuting inputs (which are i.i.d.), the input sequences r[1] .. r[n] and e[1] .. e[n] are equally probable.
All this means the output of alpha-beta and the output of minimax are equivalent random variables.

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?

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_!

[UncombedCoconut]

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.