Le minimax, en théorie des jeux, est une méthode qui vise à minimiser la perte attendue. Pour ce faire, le joueur suppose que la décision prise par son adversaire sera défavorable. C'est-à-dire que le pire scénario est attendu avant le mouvement de l'adversaire.
Pour le dire autrement, la méthode minimax consiste à prendre la meilleure décision en supposant que l'autre joueur choisira le pire des cas pour vous.
Il faut tenir compte du fait que cette méthode est applicable dans un jeu à deux (deux joueurs) et qu'elle n'est pas coopérative, mais un jeu à somme nulle. Cela signifie que ce qu'un joueur gagne est perdu par l'autre et vice versa. Par conséquent, chaque agent aura intérêt à maximiser sa propre utilité, même si cela nuit à l'autre.
À ce stade, nous devons également nous rappeler que la théorie des jeux est une branche des mathématiques et de l'économie qui étudie le choix qui optimise la situation d'un individu lorsque les coûts et les avantages ne sont pas fixés à l'avance, mais dépendent des décisions des autres.
Algorithme Minimax dans un arbre de décision
Nous pouvons voir comment la méthode minimax est appliquée dans un arbre de décision à plusieurs nœuds. Le jeu commence en bas et se termine par un résultat au plus haut niveau.
À la base de l'arbre, l'adversaire fait le premier pas, donc le pire résultat est attendu. Ensuite, au deuxième niveau, c'est au joueur x qui cherchera à maximiser son profit, en tenant compte de la décision préalablement prise par l'adversaire.
Au troisième niveau, c'est à nouveau le tour de l'adversaire et ainsi de suite. Nous allons montrer un exemple ci-dessous.
Exemple d'algorithme Minimax
Dans l'arbre de décision suivant, nous montrons les résultats obtenus par le joueur x à chaque instant du jeu. A la base, au premier niveau, l'adversaire prend la décision. Pour cette raison, les scénarios sont donnés dans lesquels le joueur peut perdre -10 ou gagner 5.
Au deuxième niveau, c'est au joueur x, donc il maximisera son profit. Entre perdre 10 ou gagner 1, vous gagnerez 1. De même, entre gagner 5 ou 7, vous gagnerez 7.
Ensuite, c'est à nouveau le tour de l'adversaire, donc les scénarios seront donnés dans lequel le joueur x a le plus mauvais résultat, -3 et 4, selon les cas. Enfin, entre perdre 3 ou gagner 4, le joueur x prendra la décision qui permettra à ce dernier.
Nous devons prendre en compte que les valeurs de chaque nœud dépendront d'une fonction d'utilité.
Pour mieux comprendre l'arbre, supposons qu'à la base la décision porte sur la distribution du produit. Le concurrent (l'adversaire) peut sous-traiter la distribution (voir la partie gauche de l'arbre). Dans ce cas, il doit choisir, par exemple, entre le croupier A et B. Ainsi, il choisit le premier, faisant perdre 10 au joueur x (s'il choisissait B, le joueur x gagnerait 12).
Cependant, peut-être que l'adversaire préfère distribuer lui-même sa marchandise, pouvoir louer des véhicules motorisés ou acheter un camion. Des deux scénarios, choisissez le premier qui est le moins flatteur pour le joueur x car il en gagne 5 et non 10.
