The Expectimax algorithm is an extension of the Minimax algorithm, adapted to games involving elements of chance, such as dice or card games. Unlike Minimax, which only deals with strategic decisions between two players, Expectimax includes a processing level for random events.

2.1 Basic concept:

In games with chance:

•       Decision nodes (Max or Min): represent the choices made by players (as in Minimax).

•       Chance nodes (Chance): represent random events (e.g. dice roll, draw a card). These nodes use probabilities to evaluate possible actions.

Expectimax calculates the mathematical expectation of the value of the chance nodes to integrate the probabilities into the optimal strategy.

2.2 Structure of the Expectimax tree:

•       Max Nodes: Correspond to the decisions of the player who seeks to maximize his score.

•       Nodes Min: If the game is competitive, they represent the opponent who seeks to minimize the score of the main player.

•       Chance nodes: Correspond to the results of random events, where each branch is weighted by its probability.

2.3   How the algorithm works:

The algorithm runs recursively:

•       Max/Min Nodes: Evaluates each possible action and selects the one that maximizes or minimizes the value according to the player concerned.

•       Chance Nodes: Calculates the weighted expectation of the values of the following nodes.

Where P(s) is the probability of the event corresponding to the successor s.