Difficulty estimating expected minimax values

If the program had known in advance all the draws that should occur during the rest of the game, then finding a solution in a draw game would be completely similar to finding a solution in a draw without a draw, which is performed by the minimax search algorithm during . But since the algorithm that uses the expected minimax values ​​also considers all possible sequences of drawing lots, its operation requires time, where n is the number of different draw variants.

Even if the search depth is limited to some small value of d, because of such extra time, much more significant compared to the minimax algorithm, in most games with random elements it becomes impossible to look into the search tree to a very great depth. In backgammon, n is 21, and b is usually around 20, but in some situations it can be as high as 4,000 for draws involving repeated points. Apparently, all that you can count on is to look forward three half-passes.

Another way to think about this problem is this: the advantage of alpha-beta search is that it ignores future directions of the game, which simply should not be realized if the game always selects the best move. Therefore, the alpha-beta search focuses on the most likely events. In games with a toss of possible sequences of moves, there can be no, since, in order for these moves to be made, the correct draw should be drawn first, which would make them valid.

This is a common problem that arises in any such situation, when uncertainty interferes with the picture of the world: the number of options for further action multiplies to an extraordinary degree, and the formation of detailed action plans becomes meaningless, since the world is likely to play a completely different game.

Undoubtedly, the reader had the idea that it would seem possible to apply some method similar to alpha-beta-clipping to trees of games with nodes of the draw. As it turned out, this possibility does exist. The analysis of the MIN and MAX nodes remains unchanged, but it is also possible to cut off the drawing of lots by using a certain amount of ingenuity.

Consider the draw node C, shown in the figure , and determine what will happen to the value of this node as we research and evaluate its children. Is it possible to find the upper limit of the value C before all its child nodes are checked? (Recall that this is what is required in an alpha-beta search so that you can prune a node and its subtree.)

At first glance, such a requirement may seem impracticable, since the value of node C represents the average value of its child nodes. And until all the draws of lots are considered, this average can be anything, since the unexplored children themselves can have any value whatsoever. However, if the limits of the permissible values ​​of the utility function are set, then it will be possible to determine the limits of this average as well.

For example, if it is determined that all utility values ​​are in the range from +3 to -3, then the values ​​of the leaf nodes become limited, and this, in turn, allows you to set the upper limit of the value of the draw node, without considering all its child nodes.