Expectiminimax tree

The Expectiminimax algorithm is an enhanced version of the minimax algorithm, which takes into account random elements such as the fall of a cube. Therefore, the algorithm finds in game programming of zero-sum games with two participants such as backgammon its most common use.

Properties

The algorithm is similar in many parts of the conventional MiniMax algorithm, but is extended by a case distinction. All sorts of events ( for example, result from different eyes numbers) are calculated separately, as if they were real. Then, all the resulting probability as branches of a likelihood depth are then multiplied by the probability of its occurrence and added. The sum then is the criterion for the known Minimierungs-/Maximierungsprozess. The values ​​in the tree so that the same formal mathematical definition of the expected value ( engl. expected value).

Pseudo-code

The Expectiminimax algorithm was first proposed by Donald Michie. The following is the pseudo code is given:

Function expectiminimax ( Branch, depth)

IF branch is a Bewertungsast OR DEPTH = 0          return the heuristic evaluation of the current situation      IF the opponent is on the train          / / Give back the rated with the lowest value train          let α: = ∞          FOR EVERY train the branch              α: = min ( α, expectiminimax ( successor, depth -1))      ELSE IF we are on the train          / / Give back the rated with the highest value train          let α: = - ∞          FOR EVERY train the branch              α: = max ( α, expectiminimax ( successor, depth -1))      ELSE IF random event          / / Return average rating of all options back          let α: = 0          FOR EVERY successor of the branch              α: = α (probability [ successor ] * expectiminimax ( successor, depth -1))      return α evaluation function

The evaluation function must evaluate the current position in the tree, as in the MiniMax algorithm based on heuristics. Unlike the MiniMax algorithm, however, the range of the function plays a crucial role. If, in the MiniMax algorithm for gain or loss positions marked with or, performs such handling in Expectiminimax algorithm to loss of information. If a player can reach as eye number a good situation for example with a 1, 2 and 3, but loses if he rolls a 4, it is apparent in the algorithm at same probabilities: The train is discarded, although it only leads to a small probability to losing the game. This effect is particularly problematic at the end of a game when accumulate profit and loss reviews and may occur in the same probability depth. To prevent such errors, fixed ranges of values ​​must be defined and profit and loss evaluations are treated separately. In practice, most complex data types are used as evaluation values ​​, which is divided in assessing the situation in basic rating and win / loss opportunity.

Pruning

An efficient design of computation by cutting away branches ( pruning ) as in the alpha-beta algorithm is also possible in the Expectiminimax algorithm. However, the implementation is designed by defining specific ranges of values ​​of complex and differs for different applications. In addition, the pruning is much less efficient than the MiniMax and Alpha - Beta algorithm, so that the effort of an implementation usually not worth it.