Dans le billet 19 bits, nous avions posé les bases d'un jeu de morpion, en détaillant l'implémentation du plateau de jeu, de l'arbre des positions utilisée pour étudier les coups possibles et de l'évaluation statique d'une position. Les deux fonctions clés -à ce stade, les détails de l'implémentation du plateau ne sont plus importants- étaient les suivantes:
buildGTree :: Int -> GameTree -- crée l'arbre de jeu en partant d'une position
prune :: Int -> GameTree -> GameTree -- taille l'arbre de jeu pour n'en conserver que n niveaux
prune :: Int -> GameTree -> GameTree -- taille l'arbre de jeu pour n'en conserver que n niveaux
L'algorithme minimax
Evaluer une position de façon statique est assez limité: ne vous est-il jamais arrivé, concentrés que vous étiez sur une stratégie pour mettre en échec l'adversaire, d'oublier qu'il avait lui aussi une liberté de mouvement? Ou bien (je fais appel à des souvenirs de jeunesse) d'être obnubilés par la rangée de pièces rouges que vous constituiez au "Puissance 4" avant d'en être frustrés par un impeccable rang de pièces jaunes?
L'algorithme minimax prend en compte les motivations de l'adversaire; il sait qu'il choisira le meilleur coup pour lui, pas pour vous. Si on assigne un score à une position, d'autant plus élevé qu'il vous favorise et d'autant plus bas qu'il favorise l'adversaire, vous choisirez la position qui a le score le plus élevé, et l'adversaire celle qui a le score le plus faible: regarder en avant dans la partie, c'est donc alterner maximum et minimum des positions possibles.
La première étape est donc d'attribuer de façon statique un score à chaque position. Nous avons déjà la fonction d'évaluation, nommée à juste titre static. Il nous faut un moyen de l'appliquer à l'arbre de jeu:
| Code Haskell : | Sélectionner tout |
1 2 3 | mapTree :: (Int -> Int) -> GameTree -> GameTree mapTree f (Node n []) = Node (f n) [] -- feuille mapTree f (Node n ns) = Node (f n) (map (mapTree f) ns) -- branche |
Avec:
> mapTree static . buildGTree $ pos
On a donc l'arbre des évaluations statiques en partant d'une position
On peut alors définir maximise et minimise:
| Code Haskell : | Sélectionner tout |
1 2 3 4 5 6 7 | maximise :: GameTree -> Int maximise (Node n []) = n maximise (Node _ ns) = maximum $ map minimise ns minimise :: GameTree -> Int minimise (Node n []) = n minimise (Node _ ns) = minimum $ map maximise ns |
Modularité de la composition fonctionnelle et paresseuse
Pour récapituler, nous pouvons désormais évaluer une position avec la fonction:
evaluate :: Int -> Int -- lance la co-récursion minimise / maximise
evaluate = maximise . mapTree static . prune 5 . buildGTree -- 5 est en quelque sorte le niveau de difficulté du jeu
Chaque composant est indépendant des autres: je peux remplacer presqu'à loisir, sans toucher à quoique ce soit d'autre, chacune des fonctions utilisées. Je peux utiliser une nouvelle fonction de maximisation -c'est ce que nous ferons tout de suite avec l'optimisation alpha-beta- ou une nouvelle fonction d'évaluation statique, une nouvelle fonction d'élagage de l'arbre, etc.
Qui plus est, et contrairement aux apparences, grâce à l'évaluation paresseuse, je ne traverse l'arbre qu'une seule fois! Je peux donc rajouter des étapes d'optimisation ou de retraitement à ma convenance!
L'optimisation alpha-bêta
Pour donner un exemple de cette modularité, nous allons réécrire la fonction de maximisation en y incluant l'optimisation alpha-bêta. Elle repose sur une observation simple, quoique contre-intuitive: pour déterminer le minimum maximal (et réciproquement le maximum minimal), il n'est pas nécessaire de parcourir toute la liste des minima (maxima). Cela permet d'éviter l'évaluation d'un certain nombre de coups qui ne se réaliseront que si l'adversaire veut se tirer une balle dans la jambe...
Par exemple:
> maximum (minimum [2,1]) (minimum [0,5,-6,8,5,4,2,-1,-9,3,2,0,5,1,4,2])
--il n'est pas nécessaire d'évaluer la partie en vert: de toute façon, zéro comme minimum potentiel est déjà inférieur au minimum de la première liste
--il n'est pas nécessaire d'évaluer la partie en vert: de toute façon, zéro comme minimum potentiel est déjà inférieur au minimum de la première liste
On peut capturer cette optimisation dans la fonction suivante:
| Code Haskell : | Sélectionner tout |
1 2 3 4 5 6 7 | alphaBetaMinimum :: [[Int]] -> [Int] alphaBetaMinimum (nums : rest) = (potentialMin) : (omitIf (<=) (potentialMin) rest) |
Il ne nous reste plus qu'à créer la fonction d'appel:
| Code Haskell : | Sélectionner tout |
1 2 3 4 5 6 | abMaximise :: GameTree -> Int abMaximise = maximum . abMaximise' abMaximise' :: GameTree -> [Int] abMaximise' (Node n []) = [n] abMaximise' (Node _ subs) = alphaBetaMinimum . map abMinimise' $ subs |
et à modifier evaluate:
evaluate = abMaximise . mapTree static . prune 8 . buildGTree -- on va plus loin dans l'arbre, et plus vite!
Conclusion:
Ce billet était le dixième de ce blog. J'espère avoir montré, au fur et à mesure, l'intérêt et peut-être la beauté d'une programmation fonctionnelle modulaire et concise. Je continuerai dans les billets suivants à alterner présentation de langages, de concepts et de cas pratiques. Je pense néanmoins, dans le prochain billet, me livrer à une réflexion plus générale sur la variété des langages et le sens de cette variété -en réaction, au moins partiellement, à la très intéressante discussion en cours sur le forum.
Exercices
- une des optimisations possibles de l'algorithme minimax est de ne retenir que les n meilleurs coups à disposition de l'adversaire pour poursuivre l'évaluation. Donnez un exemple d'implémentation.
- quelles modifications imposerait l'application de l'algorithme au jeu de dames? Quelles fonctionnalités pourrait offrir un langage pour les minimiser?
- quelles modifications imposerait l'application de l'algorithme au jeu de dames? Quelles fonctionnalités pourrait offrir un langage pour les minimiser?
Pour faciliter l'expérimentation, le code source consolidé est disponible en pièce-jointe (extension en .txt car les fichiers haskell ne sont pas acceptés par le site !! / à transformer en .hs avant utilisation)[ATTACH]174609d1/a/a/a" />