Chess - Programming - Expectimax Search

The Expectimax search algorithm is a game theory algorithm used to maximize the expected utility.

It is a variation of the Minimax algorithm.

• While Minimax assumes that the adversary (the minimizer) plays optimally, the Expectimax does not.
• This is useful for modelling environments where adversary agents are not optimal, or their actions are based on chance.

• What if there is a possibility of the minimizer making a mistake (or not playing optimally).
• Therefore going right might sound more appealing or may result in a better solution.

In the Expectimax tree, minimizer nodes are replaced by chance nodes.

• The Chance nodes take the average of all available utilities giving us the ‘expected utility’.
• The maximizer node chooses the right sub-tree to maximize the expected utilities.

Advantages of Expectimax over Minimax:

• Expectimax algorithm helps take advantage of non-optimal opponents.
• Unlike Minimax, Expectimax ‘can take a risk’ and end up in a state with a higher utility as opponents are random (not optimal).

Disadvantages:

• Expectimax is not optimal.
• It may lead to the agent losing (ending up in a state with lesser utility).
• Expectimax requires the full search tree to be explored.
• There is no type of pruning that can be done, as the value of a single unexplored utility can change the Expectimax value drastically.
• Therefore it can be slow.
• It is sensitive to monotonic transformations in utility values.
• For Minimax, if we have two states S1 and S2, if S1 is better than S2, the magnitudes of the evaluation function values f(S1) and f(S2) do not matter as along as f(S1)>f(S2).
  • For expectimax, magnitudes of the evaluation function values matter.

Algorithm:

• If the current call is a maximizer node, return the maximum of the state values of the nodes successors.
• If the current call is a chance node, then return the average of the state values of the nodes successors (assuming all nodes have equal probability).
• Different nodes can have different probabilities.
• The function is called recursively until it reaches a terminal node (the state with no successors).
• Then return the utility for that state.

Time complexity: O(bm) Space complexity: O(b*m), where b is branching factor and m is the maximum depth of the tree. Applications: Expectimax can be used in environments where the actions of one of the agents are random.

Expectimax Search