Aller au contenu

Dans ce TP, on va implémenter la stratégie parfaite de résolution du morpion par calcul des attracteurs.

Représentation des données

On va considérer des nombres ternaires pour représenter les plateaux du morpion. C'est assez inefficace car beaucoup de nombres ne vont pas correspondre à des parties atteintes, mais \(3^9 = 19683\) n'étant pas très grand, il sera facile d'en faire un graphe ensuite.

On considère les types OCaml

type case = Vide | Croix | Rond
type etat = case array array
type joueur = J1 | J2

On va associer en ternaire \(0\) à une case vide, \(1\) à une croix et \(2\) à un rond. Un état est une matrice \(3 \times 3\) de cases, on la représentera en ternaire ligne par ligne ainsi :

[| [| c0; c1; c2 |];
   [| c3; c4; c5 |];
   [| c6; c7; c8 |] |]

est représenté par le nombre \(a_0 + 3 a_1 + \dots + 3^8 a_8\) où \(a_i\) est le chiffre associé à ci.

Question 1. Écrire des fonctions :

val nombre_vers_case : int -> case
val case_vers_nombre : case -> int
val nombre_vers_etat : int -> etat
val etat_vers_nombre : etat -> int

effectuant ces conversions.

Corrigé 
let nombre_vers_case c =
    match c with
    | 0 -> Vide
    | 1 -> Croix
    | _ -> Rond

let case_vers_nombre c =
    match c with
    | Vide -> 0
    | Croix -> 1
    | _ -> 2

let nombre_vers_etat n =
    let m = Array.make_matrix 3 3 Vide in
    let v = ref n in
    for i = 0 to 8 do
        m.(i / 3).(i mod 3) <- nombre_vers_case (!v mod 3);
        v := !v / 3
    done;
    m

let etat_vers_nombre m =
    let v = ref 0 in
    for i = 2 downto 0 do
        for j = 2 downto 0 do
            v := 3 * !v + case_vers_nombre m.(i).(j)
        done
    done;
    !v

Exemple

Le nombre \(12410\) correspond ainsi à [|[|Rond; Rond; Croix|]; [|Vide; Vide; Vide|]; [|Rond; Rond; Croix|]|].

Question 2. Écrire une fonction

val compte_pions : etat -> int * int * int

qui renvoie un triplet \((m, n, p)\) où \(m\) est le nombre de cases vides, \(n\) est le nombre de croix de l'état et \(p\) le nombre de ronds.

Corrigé 
let compte_pions m =
    let vides = ref 0 in
    let croix = ref 0 in
    let ronds = ref 0 in
    for i = 0 to 2 do
        for j = 0 to 2 do
            match m.(i).(j) with
            | Croix -> incr croix
            | Rond -> incr ronds
            | _ -> incr vides
        done
    done;
    (!vides, !croix, !ronds)

Question 3. En déduire une fonction

val etat_controle : etat -> joueur

qui renvoie le joueur contrôlant un état, c'est-à-dire celui qui doit jouer. Le joueur J1 joue les croix et commence.

Corrigé 
let etat_controle m =
    let _, croix, ronds = compte_pions m in
    if croix = ronds
    then J1
    else J2

Pour déterminer si un état est valide ou gagnant, il va être nécessaire de compter le nombre d'alignements de trois valeurs identiques.

Question 4. Écrire une fonction

val trois_en_ligne : etat -> case -> int

qui compte le nombre d'alignements de trois valeurs identiques égales à la valeur passée en paramètre.

Corrigé 
let trois_en_ligne m c =
    let trois = ref 0 in
    for i = 0 to 2 do
        if m.(i).(0) = c && m.(i).(1) = c && m.(i).(2) = c
        then incr trois;
        if m.(0).(i) = c && m.(1).(i) = c && m.(2).(i) = c
        then incr trois
    done;
    if m.(0).(0) = c && m.(1).(1) = c && m.(2).(2) = c
    then incr trois;
    if m.(2).(0) = c && m.(1).(1) = c && m.(0).(2) = c
    then incr trois;
    !trois

Question 5. En déduire des fonctions

val etat_valide : etat -> bool
val etat_terminal : etat -> bool
val gagnant : etat -> joueur option

qui vont respectivement :

  • déterminer si un état est valide, c'est-à-dire si on l'atteint naturellement depuis la grille vide en commençant par le joueur Croix et sans continuer à jouer dans une partie gagnée ;
  • déterminer si un état est terminal, c'est-à-dire qu'il est valide et qu'un joueur a gagné ou qu'il n'y a plus de cases libres ;
  • étant donné un état terminal, renvoyer le gagnant s'il y en a un, ou None sinon.
Corrigé

Un état est valide quand il y a autant de croix que de ronds, ou une croix de plus, et que le dernier joueur à avoir joué est le seul à pouvoir avoir un alignement.

let etat_valide m =
    let vides, croix, ronds = compte_pions m in
    (croix = ronds || croix = ronds+1)
    && (trois_en_ligne m Croix = 0 || croix = ronds+1)
    && (trois_en_ligne m Rond = 0 || croix = ronds)

let etat_terminal m =
    let vides, _, _ = compte_pions m in
    etat_valide m
    && (vides = 0 || trois_en_ligne m Croix >= 1 || trois_en_ligne m Rond >= 1)

let gagnant m =
    assert (etat_terminal m);
    if trois_en_ligne m Croix >= 1
    then Some J1
    else if trois_en_ligne m Rond >= 1
        then Some J2
        else None

On obtient ainsi \(5478\) états valides, dont \(958\) terminaux.

Construction du graphe des états

Question 6. Écrire une fonction

val etat_copie : etat -> etat

qui copie un état (attention, ce sont des matrices).

Corrigé 
let etat_copie m =
    Array.init 3  (fun i -> Array.copy m.(i))

Question 7. Écrire une fonction

val suivants : etat -> etat list

qui renvoie la liste des états accessibles depuis un état donné par un coup du joueur qui le contrôle.

Si l'état est terminal, on renverra la liste vide.

Corrigé 
let suivants m =
    let c = match etat_controle m with J1 -> Croix | J2 -> Rond in
    let s = ref [] in
    if not (etat_terminal m)
    then
        for i = 0 to 2 do
            for j = 0 to 2 do
                if m.(i).(j) = Vide
                then begin
                    let m' = etat_copie m in
                    m'.(i).(j) <- c;
                    s := m' :: !s
                end
            done
        done;
    !s

Question 8. Écrire une fonction

val graphe_etats : unit -> int list array

qui renvoie la représentation en listes d'adjacence du graphe des états.

Le graphe comporte ainsi \(3^9\) sommets. On ne calculera pas les états suivants des états non valides, ils auront donc une liste de voisins vide.

Corrigé 
let graphe_etats () =
    let netats = 19683 in
    let gr = Array.make netats [] in
    for e = 0 to netats - 1 do
        let m = nombre_vers_etat e in
        if etat_valide m
        then let ml = suivants m in
            gr.(e) <- List.map etat_vers_nombre ml
    done;
    gr

Calcul des attracteurs

Question 9. Écrire une fonction

val attracteur_initial : int list array -> joueur -> bool array

qui prend le graphe des états et un joueur et renvoie un tableau de booléens indiquant si un état est terminal et gagnant pour ce joueur.

Corrigé 
let attracteur_initial g j =
    let n = Array.length g in
    Array.init n
        (fun e -> let m = nombre_vers_etat e in
            etat_terminal m && gagnant m = Some j)

Question 10. Écrire une fonction

val attracteur_suivant : int list array -> joueur -> bool array -> bool

qui prend le graphe des états, un joueur, un attracteur \(A_i\) donné sous la forme d'un tableau de booléens indiquant si \(e \in A_i\), place dans ce tableau \(A_{i+1}\) et renvoie un booléen indiquant si \(A_i \neq A_{i+1}\).

Corrigé

Un état valide non terminal est ajouté s'il est contrôlé par j et qu'un de ses successeurs est dans l'attracteur, ou s'il est contrôlé par l'adversaire et que tous ses successeurs sont dans l'attracteur.

let attracteur_suivant g j a =
    let nouveaux = ref false in
    let n = Array.length g in
    for e = 0 to n-1 do
        if not a.(e) && etat_valide (nombre_vers_etat e)
            && not (etat_terminal (nombre_vers_etat e))
        then begin
            let controlleur = etat_controle (nombre_vers_etat e) in
            if controlleur = j
                 && List.exists (fun e' -> a.(e')) g.(e)
            then (a.(e) <- true; nouveaux := true);
            if controlleur <> j
                 && List.for_all (fun e' -> a.(e')) g.(e)
            then (a.(e) <- true; nouveaux := true);
        end
    done;
    !nouveaux

Comme on modifie le tableau pendant le parcours, un état ajouté peut servir à en ajouter d'autres lors du même appel : on obtient un ensemble qui contient \(A_{i+1}\) et qui est inclus dans l'attracteur. Cela ne change pas le résultat de la question suivante.

Question 11. En déduire une fonction

val positions_gagnantes : int list array -> joueur -> bool array

qui renvoie un tableau de booléens indiquant si un état est une position gagnante.

Corrigé 
let positions_gagnantes g j =
    let a = attracteur_initial g j in
    while attracteur_suivant g j a do
        ()
    done;
    a

On constate que l'état initial n'est gagnant pour aucun des deux joueurs : le morpion bien joué aboutit à un match nul.

Jouer

Question 12. En déduire une fonction

val joue_bien : int list array -> bool array -> bool array -> int -> int

qui prend un graphe d'états, le tableau des positions gagnantes d'un joueur, le tableau des positions gagnantes de l'adversaire et un état non terminal \(e\) qu'il contrôle.

Si \(e\) est gagnant pour le joueur, on renvoie un coup encore gagnant pour le joueur. Sinon, on essaie de renvoyer un coup qui n'est pas gagnant pour l'adversaire (on vise le nul).

Corrigé 
let joue_bien g pj po e =
    let l = List.filter (fun e -> pj.(e)) g.(e) in
    let l' = List.filter (fun e -> not po.(e)) g.(e) in
    match l, l', g.(e) with
    | t::_, _, _
    | [], t::_, _
    | [], [], t::_ -> t
    | _ -> failwith "etat terminal"

Question 13. On peut maintenant écrire une petite boucle interactive pour jouer au morpion contre notre IA.

Corrigé

Le joueur humain joue les croix. Si son coup termine la partie, l'IA ne joue pas.

let affiche_etat m =
    for i = 0 to 2 do
        for j = 0 to 2 do
            let c = match m.(i).(j) with
                | Croix -> 'X'
                | Rond -> 'O'
                | Vide -> ' ' in
            print_char c;
            if j <> 2 then print_char '|'
        done;
        print_newline ()
    done;
    print_newline ()

let boucle_interactive () =
    let g = graphe_etats () in
    let w1 = positions_gagnantes g J1 in
    let w2 = positions_gagnantes g J2 in

    let p = ref 0 in
    while not (etat_terminal (nombre_vers_etat !p)) do
        affiche_etat (nombre_vers_etat !p);
        let l = g.(!p) in
        List.iteri (fun i e ->
            Printf.printf "Coup %d) %s%s%s :\n"
                i
                (if w1.(e) then "gagnant pour vous" else "")
                (if w2.(e) then "gagnant pour l'adversaire" else "")
                (if not w1.(e) && not w2.(e) then "au mieux nul" else "");
            affiche_etat (nombre_vers_etat e)) l;
        Printf.printf "Saisir numero coup> ";
        flush stdout;
        let i = Scanf.scanf " %d" (fun i -> i) in
        Printf.printf "%d\n" i;
        let e' = List.nth l i in
        if etat_terminal (nombre_vers_etat e')
        then p := e'
        else p := joue_bien g w2 w1 e'
    done;
    affiche_etat (nombre_vers_etat !p);
    match gagnant (nombre_vers_etat !p) with
    | Some J1 -> print_endline "Vous avez gagné !"
    | Some J2 -> print_endline "Vous avez perdu !"
    | None -> print_endline "Match nul."