Func' programming - un blog homéopathique

N.B : Ce billet est largement inspiré de l’article de John Hugues : Why functional programming matters.

Madame la Marquise m’a foutu les morpions…
Dans un précédent billet, je promettais une courte série sur une A.I. simple et modulaire pour jeux de plateaux, sous la forme d’un hommage aux morpions. Cette A.I. met à profit les possibilités de composition de fonctions et d’évaluation paresseuse introduites dans les précédents billets.

Un plateau de morpions
J’ai décidé de faire tenir mon plateau de jeu dans un entier. Aucune nécessité à cela, bien entendu, mais j’en profite pour montrer que l’optimisation n’est pas étrangère aux langages « de haut niveau » qui peuvent très bien travailler avec des bits.
Un plateau est donc décomposé de la façon suivante :

• Bits 0-8 : les jetons du joueur (on a qu’à dire les croix)
• Bits 9-17 : les jetons de l’ordinateur (donc les ronds)
• Bit 18 : 0 si c’est le tour du joueur, 1 pour l’ordinateur.

Un arbre de plateaux
Pour que l’A.I puisse faire des coups éclairés, il faut qu’elle puisse se projeter dans le déroulement de la partie. La façon classique de le lui permettre est de créer un « arbre de jeu », dans lequel chaque position qu’il est possible d’atteindre à partir d’un plateau p est son enfant :

p

/ | \

e1 e2 e3

Mais mettons d’abord au point les détails d’une position.

Manipuler des bits
Haskell propose un système de modules assez complet. Pour en effleurer la surface, je précise seulement que vous devrez ajouter « import Data.Bits » au début de votre programme, ou, dans l’interpréteur, indiquer « :module Data.Bits », pour utiliser certaines des fonctions employées dans ces bouts de code.

Comme la position d’un joueur est encodée sur 9 bits, il nous faut un masque pour cacher le reste :

mask9 :: Int --les valeurs entières sont par défaut des Integer (infinis), préciser donc le type Int (32/64 bits) pour une optimisation sans effort
mask9 = 2^9-1 -- #111111111b ( ! ce n’est pas un littéral Haskell ; pas hélas de représentation binaire native)

turnBit :: Int --pour donner un nom au bit qui détermine de qui c’est le tour.
turnBit = 18

allMoves :: [Int] --tous les mouvements possibles : une compréhension de liste qui sera mémoïsée après sa première utilisation
allMoves = [2^x | x <- [0..8]]

Bit I/O
Pour simplifier l’écriture des positions, nous écrivons deux petites fonctions pour faire nos opérations de lecture et d’écriture dans les positions encodées dans un entier : une pour lire (decomp), une pour écrire (rebuild).

rebuild :: Int -> Int -> Int -> Int --trois entiers pour en faire un seul : à qui de jouer, la position du joueur, la position de l’ordinateur
rebuild t c p = p .|. (shiftL c 9) .|. (shiftL t turnBit) -- shiftL x n : déplace n fois à gauche les bits de x / .|. est le « ou » binaire

NB : (x, y, z) est un « tuple » à trois éléments : contrairement aux listes, ils peuvent être hétérogènes.

decomp :: Int -> (Int, Int, Int) --l’opération inverse
decomp p = (if testBit p 18 then 1 else 0, (shiftR p 9) .&. mask9, p .&. mask9)

L’élégance fonctionnelle
Grâce au pattern matching et à la composition de fonctions, nous pouvons écrire une fonction dense et courte (je vous encourage à lire les billets précédents si certains éléments vous manquent pour la compréhension) pour générer les possibles positions suivantes :

nextPositions :: (Int, Int, Int) -> [Int]
nextPositions (1, c, p) = map (\x -> rebuild 0 x p) . map (.|. c) . filter (\m -> (m .&. (p .|. c)) == 0) $ allMoves
nextPositions (0, c, p) = map (rebuild 1 c) . map (.|. p) . filter (\m -> (m .&. (p .|. c)) == 0) $ allMoves

nextPositions utilise le pattern matching pour récupérer de façon élégante les informations contenues dans le tuple généré par decomp :

nextPositions . decomp $ 0 --génère les positions possibles après la position initiale (tout à 0, c’est le tour du joueur)

L’infini est un outil bien pratique
Il nous faut tout de même une structure hôte, l’ arbre, pour placer les positions générées. Haskell permet de définir de nouveaux types grâce au mot-clé data. La syntaxe (dans sa forme la plus simple –il faudra vraiment que je revienne sur le système de type de Haskell dans un autre billet) est :

data NomDeType = constructeur arg1 arg2 … argN

Dans notre cas, nous l’avons dit, chaque nœud contient une position et ses enfants (qui sont aussi des arbres de jeux ; c’est une structure récursive, encore !) :

data GameTree = Node Int [GameTree]

Il nous suffit donc, pour générer l’arbre de jeux, d’appliquer le constructeur de GameTrees aux positions suivantes de celle dont on part :

buildGTree :: Int -> GameTree
buildGTree p = Node p (map buildGTree (nextPositions . decomp $ p))

Si j’écris :

buildGTree 0

j’obtiens l’arbre de jeu entier des morpions –mais je pourrais l’utiliser pour un jeu où les possibilités sont infinies, grâce à l’évaluation paresseuse ! N’en sera évalué que ce je demanderai…

Une fonction pour dompter l’infini
Il y aurait quand même un certain danger à lancer l’évaluation sur l’arbre infini. Après tout, même pour un jeu de morpions, il y a 9 ! = 362880 parties possibles. Alors imaginez qu’on réutilise notre squelette pour un jeu d’échec !

Il nous faut donc une fonction équivalente à take (cf billet précédent) qui fonctionne pour les arbres :

prune :: Int -> GameTree -> GameTree
prune 0 (Node t _) = Node t []
prune n (Node t rest) = Node t (map (prune (n-1)) rest)

prune n gt --donne les n premiers niveaux de l’arbre

Pour être tranquilles avant le prochain billet
Dans le prochain billet, nous mettrons en place l’A.I. à proprement parler, sous la forme de l’algorithme minimax, avec le raffinement alpha-bêta. Pour pouvoir nous concentrer là-dessus, terminons ce billet par l’écriture d’une fonction d’évaluation statique : elle détermine le score sans regarder les positions suivantes. Elle est simple : elle renvoie 1 si l’ordinateur gagne, -1 si c’est le joueur et 0 sinon.

Pour déterminer si les positions sont gagnantes, un peu d’infrastructure est nécessaire :

makeMask :: [Int] -> Int --construit un masque à partir de la liste des bits allumés
makeMask = foldr ((+) . (2^)) 0 --encore un pliage de liste ! ((+) . (2^)) < = > \x y -> 2^x + y

-- la liste des bits allumés dans les positions gagnantes
winners’ = [[0,1,2], [3,4,5], [6,7,8], -- lignes

[0,3,6], [1,4,7], [2,5,8], -- colonnes
[0,4,8], [2,4,6]] -- diagonales

winners = [makeMask onBits | onBits <- winners’] --on met le tout dans une structure pour que le calcul soit mémoïsé

Il suffit ensuite de comparer avec la position des deux joueurs :

NB : les pipes ( | ) dans la fonctions sont des « gardes ». Elles correspondent à un switch dans un autre langage : si la condition qui les suit est vraie, la fonction retourne l’expression qui suit cette condition.
La syntaxe est :
NomFonction args

| condition = expression
…
| otherwise = expression --otherwise < = > par défaut

static :: (Int, Int, Int) -> Int --à employer avec decomp
static (_, p, c)

| any (\x -> x == x .&. p) winners = -1 -- any f lst est vraie si f est vraie pour au moins un élément de lst / .&. = binary and
| any (\x -> x == x .&. c) winners = 1
| otherwise = 0

Et voilà ! en quelques lignes de code (dont une bonne part aurait pu / dû être généralisée – un arbre est une structure bien pratique et très commune, après tout), nous avons déjà fait l’essentiel du travail. Dans le prochain billet, l’A.I proprement dite et quelques réflexions sur la modularité particulière des programmes fonctionnels !

Exercices :

- représentez le plateau d’un jeu de dames
- quelle fonction d’évaluation statique pourrait être utilisée pour le jeu de dames ?
- lisez l’article dont le billet est inspiré, qui donne d’autres exemples intéressants d’implémentations modulaires pour différents algorithmes
- pour les bons en maths : si une position gagnante ne conduit à la génération d’aucune position nouvelle, de combien de positions l’arbre de jeu complet sera-t-il constitué ?