Introduction à l'algorithme Minimax avec une implémentation Java

1. Vue d'ensemble

Dans cet article, nous allons discuter de l'algorithme Minimax et de ses applications en IA. Comme il s'agit d'un algorithme de théorie des jeux, nous allons implémenter un jeu simple en l'utilisant.

Nous discuterons également des avantages de l'utilisation de l'algorithme et verrons comment il peut être amélioré.

2. Présentation

Minimax est un algorithme de prise de décision, généralement utilisé dans une partie à deux joueurs au tour par tour . Le but de l'algorithme est de trouver le prochain coup optimal.

Dans l'algorithme, un joueur est appelé le maximizer, et l'autre joueur est un minimizer. Si nous attribuons un score d'évaluation au plateau de jeu, un joueur essaie de choisir un état de jeu avec le score maximum, tandis que l'autre choisit un état avec le score minimum.

En d'autres termes, le maximiseur fonctionne pour obtenir le score le plus élevé, tandis que le minimiseur essaie d'obtenir le score le plus bas en essayant de contrer les mouvements .

Il est basé sur le concept de jeu à somme nulle. Dans un jeu à somme nulle, le score total d'utilité est divisé entre les joueurs. Une augmentation du score d'un joueur entraîne une diminution du score d'un autre joueur. Ainsi, le score total est toujours nul. Pour qu'un joueur gagne, l'autre doit perdre. Des exemples de tels jeux sont les échecs, le poker, les dames, le tic-tac-toe.

Un fait intéressant: en 1997, l'ordinateur de jeu d'échecs d'IBM Deep Blue (construit avec Minimax) a battu Garry Kasparov (le champion du monde d'échecs).

3. Algorithme Minimax

Notre objectif est de trouver le meilleur coup pour le joueur. Pour ce faire, nous pouvons simplement choisir le nœud avec le meilleur score d'évaluation. Pour rendre le processus plus intelligent, nous pouvons également regarder vers l'avenir et évaluer les mouvements de l'adversaire potentiel.

Pour chaque mouvement, nous pouvons envisager autant de mouvements que notre puissance de calcul le permet. L'algorithme suppose que l'adversaire joue de manière optimale.

Techniquement, nous commençons par le nœud racine et choisissons le meilleur nœud possible. Nous évaluons les nœuds en fonction de leurs scores d'évaluation. Dans notre cas, la fonction d'évaluation peut attribuer des scores uniquement aux nœuds de résultat (feuilles). Par conséquent, nous atteignons récursivement les feuilles avec des scores et propagons les scores en arrière.

Considérez l'arbre de jeu ci-dessous:

Maximizer commence par le nœud racine et choisit le déplacement avec le score maximum. Malheureusement, seules les feuilles ont des scores d'évaluation avec elles, et donc l'algorithme doit atteindre les nœuds feuilles de manière récursive. Dans l'arborescence de jeu donnée, c'est actuellement au tour du minimiseur de choisir un mouvement à partir des nœuds feuilles , donc les nœuds avec des scores minimum (ici, les nœuds 3 et 4) seront sélectionnés. Il continue de sélectionner les meilleurs nœuds de la même manière, jusqu'à ce qu'il atteigne le nœud racine.

Maintenant, définissons formellement les étapes de l'algorithme:

  1. Construisez l'arbre de jeu complet
  2. Évaluer les scores des congés à l'aide de la fonction d'évaluation
  3. Sauvegardez les scores des feuilles à la racine, en tenant compte du type de joueur:
    • Pour le joueur maximum, sélectionnez l'enfant avec le score maximum
    • Pour le joueur minimum, sélectionnez l'enfant avec le score minimum
  4. Au nœud racine, choisissez le nœud avec la valeur maximale et effectuez le déplacement correspondant

4. Mise en œuvre

Maintenant, implémentons un jeu.

Dans le jeu, nous avons un tas avec n nombre d'ossements . Les deux joueurs doivent ramasser 1,2 ou 3 os à leur tour. Un joueur qui ne peut prendre aucun os perd la partie. Chaque joueur joue de manière optimale. Étant donné la valeur de n , écrivons une IA.

Pour définir les règles du jeu, nous allons implémenter la classe GameOfBones :

class GameOfBones { static List getPossibleStates(int noOfBonesInHeap) { return IntStream.rangeClosed(1, 3).boxed() .map(i -> noOfBonesInHeap - i) .filter(newHeapCount -> newHeapCount >= 0) .collect(Collectors.toList()); } }

De plus, nous avons également besoin de l'implémentation pour les classes Node et Tree :

public class Node { int noOfBones; boolean isMaxPlayer; int score; List children; // setters and getters } public class Tree { Node root; // setters and getters }

Nous allons maintenant implémenter l'algorithme. Il faut un arbre de jeu pour regarder en avant et trouver le meilleur coup. Implémentons cela:

public class MiniMax { Tree tree; public void constructTree(int noOfBones) { tree = new Tree(); Node root = new Node(noOfBones, true); tree.setRoot(root); constructTree(root); } private void constructTree(Node parentNode) { List listofPossibleHeaps = GameOfBones.getPossibleStates(parentNode.getNoOfBones()); boolean isChildMaxPlayer = !parentNode.isMaxPlayer(); listofPossibleHeaps.forEach(n -> { Node newNode = new Node(n, isChildMaxPlayer); parentNode.addChild(newNode); if (newNode.getNoOfBones() > 0) { constructTree(newNode); } }); } }

Now, we'll implement the checkWin method which will simulate a play out, by selecting optimal moves for both players. It sets the score to:

  • +1, if maximizer wins
  • -1, if minimizer wins

The checkWin will return true if the first player (in our case – maximizer) wins:

public boolean checkWin() { Node root = tree.getRoot(); checkWin(root); return root.getScore() == 1; } private void checkWin(Node node) { List children = node.getChildren(); boolean isMaxPlayer = node.isMaxPlayer(); children.forEach(child -> { if (child.getNoOfBones() == 0) { child.setScore(isMaxPlayer ? 1 : -1); } else { checkWin(child); } }); Node bestChild = findBestChild(isMaxPlayer, children); node.setScore(bestChild.getScore()); }

Here, the findBestChild method finds the node with the maximum score if a player is a maximizer. Otherwise, it returns the child with the minimum score:

private Node findBestChild(boolean isMaxPlayer, List children) { Comparator byScoreComparator = Comparator.comparing(Node::getScore); return children.stream() .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed()) .orElseThrow(NoSuchElementException::new); }

Finally, let's implement a test case with some values of n (the number of bones in a heap):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal() { miniMax.constructTree(6); boolean result = miniMax.checkWin(); assertTrue(result); miniMax.constructTree(8); result = miniMax.checkWin(); assertFalse(result); }

5. Improvement

For most of the problems, it is not feasible to construct an entire game tree. In practice, we can develop a partial tree (construct the tree till a predefined number of levels only).

Then, we will have to implement an evaluation function, which should be able to decide how good the current state is, for the player.

Even if we don't build complete game trees, it can be time-consuming to compute moves for games with high branching factor.

Fortunately, there is an option to find the optimal move, without exploring every node of the game tree. We can skip some branches by following some rules, and it won't affect the final result. This process is calledpruning. Alpha–beta pruning is a prevalent variant of minimax algorithm.

6. Conclusion

L'algorithme Minimax est l'un des algorithmes les plus populaires pour les jeux de société informatiques. Il est largement appliqué dans les jeux au tour par tour. Cela peut être un bon choix lorsque les joueurs ont des informations complètes sur le jeu.

Ce n'est peut-être pas le meilleur choix pour les jeux avec un facteur de branchement exceptionnellement élevé (par exemple jeu de GO). Néanmoins, avec une mise en œuvre correcte, cela peut être une IA assez intelligente.

Comme toujours, le code complet de l'algorithme peut être trouvé sur GitHub.