hmm ...UncombedCoconut wrote:Hi, sorry my explanation did not help.
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: 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 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.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 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