1-      Introductin :

The resolution of two-player games such as chess is based on algorithms for exploring decision trees such as Minimax and its optimization, the Alpha-Beta Pruning. These algorithms are essential in AI for strategy games. Here is an overview of how they work:

Tree structure:

•       Each node represents a state of the game.

•       The levels of the tree alternate between the two players:

•       Maximizer: Seeks to maximize his score.

•       Minimizer: Seeks to minimize the Maximizer score.

          1.2- Principle :

1-      We explore the tree to the leaves (or a limited horizon in complex games like chess).

2-      Final states are evaluated using an evaluation function that gives a score (for example:  +∞ for a win, -∞ for a loss).

3-      Scores are coming up through the tree:

o   Maximizer nodes take the maximum value of children.

o   Minimizer nodes take the minimum value of children.

    1.3- Complexity :

      •       Problem: The tree size grows exponentially with depth.

•       For a game of chess: high number of legal positions and possible moves.

Example – Minimax -:

Solution:

      2- Alpha-Beta Pruning (Élagage Alpha-Bêta) :

Alpha-beta improves the effectiveness of Minimax by removing branches from the tree that cannot influence the final result.

  2.1- Concept:

•       Alpha: The best value that the Maximizer can guarantee so far.

•       Beta: The best value that the Minimizer can guarantee so far.

•       When a branch cannot change the outcome for a player (because a better solution has already been found elsewhere), it is ignored.

  2.2- Benefits:

•       Significantly reduces the number of nodes scanned.

•       Can reach a depth equivalent to the Minimax while saving time.

2.3   - Main steps:

When exploring a node:

•       Updates alpha and beta.

•       If beta <= alpha, the exploration of this branch is stopped (cut).

Example - Alpha-Beta Pruning :

Solution :