L'approche qualité avec OCaml

Vous connaissez déjà les pièces, voici maintenant le jeu.

On énonce en six points la règle du jeu de tétrominos (à deux joueurs) :

• chaque joueur dispose de cinq tétrominos ;
• chaque joueur dépose tour à tour une de ses cinq pièces sur une grille rectangulaire de 5 x 8 cases ;
• avant la pose une pièce peut être librement orientée et retournée ;
• après la pose une pièce est inamovible et conserve sa position jusqu'à la fin de la partie
• le premier joueur qui ne peut plus poser une de ses pièces a perdu ;
• si la grille est totalement couverte par les dix pièces des deux joueurs alors la partie est déclarée nulle.

On appelle valeur théorique du jeu celle qui est vraie parmi ces trois valeurs possibles :

• first wins : il existe une stratégie gagnante pour le premier joueur ;
• second wins : il existe une stratégie gagnante pour le deuxième joueur ;
• tie game : deux joueurs « parfaits » font toujours une partie nulle.

On se propose, avec nos connaissances en OCaml, de calculer cette valeur théorique en trois étapes.

Mais d'abord, faisons plusieurs observations qui découlent directement de la règle du jeu :

• le plateau de jeu contient 40 cases ;
• la durée d'une partie est d'au maximum cinq coups par joueur ;
• la valeur théorique du jeu dépend uniquement de trois paramètres qui sont : la main de chaque joueur, de l'occupation du plateau de jeu et, bien sûr (puisque c'est là toute la question de la valeur théorique) de qui a la main ;
• en particulier la valeur théorique du jeu ne dépend pas de la couleur des cases occupées.

Précisons notre vocabulaire :

• avoir la main signifie avoir l'initiative de jouer ;
• la main d'un joueur est l'ensemble des pièces que ce joueur n'a pas encore posées sur le plateau de jeu ;
• l'occupation d'une case ne peut prendre que deux valeurs : libre ou occupée ;
• la couleur d'une case occupée ne peut prendre que deux valeurs : bleue ou rouge ;
• le premier joueur (first) désigne celui qui a la main, le second joueur (second) désigne celui qui n'a pas la main ;
• chaque joueur est alternativement first/second.

D'une part nous appellerons tableau de jeu la structure de donnée choisie pour représenter les trois paramètres dont dépend la valeur théorique du jeu.

D'autre part il faut savoir qu'un entier OCaml (du type int) contient au minimum 31 bits. Il nous faudra donc deux entiers pour représenter le plateau de jeu si un bit à 0 désigne une case vide et un bit à 1 désigne une case occupée.

Nous choisissons de couper le plateau de jeu en deux parties, horizontalement, de sorte que 20 bits représenteront les 20 cases supérieures du plateau et 20 autres bits représenteront les 20 cases inférieures du plateau.

Du coup, dans chacun des deux entiers, il reste encore 11 bits à notre disposition. Or il nous suffit de cinq bits pour représenter une main si un bit à 0 désigne une pièce déjà posée et un bit à 1 désigne une pièce dans la main. Assez opportunément le tableau de jeu (ou bitboard) sera donc constitué de deux entiers, le premier contiendra la main du premier joueur et la partie supérieure du plateau, le second contiendra la main du second joueur et la partie inférieure du plateau. La notation 0bBBBBB désigne un nombre de cinq bits en numérotation binaire. Les informations de main sont placées à partir du 20^e bit pour laisser assez de place pour le masque d'occupation du plateau.

type hand = int;; 

let hand_i = 0b00001 lsl 20
and hand_l = 0b00010 lsl 20
and hand_o = 0b00100 lsl 20
and hand_s = 0b01000 lsl 20
and hand_t = 0b10000 lsl 20
;;

let hand_mask  = 0x1F00000
and board_mask = 0x00FFFFF
;;

type bitboard = {first: int; second: int};;
type piece    = {upper: int; lower:  int};;

Le type piece désigne les cases occupées par une certaine pièce posée à une certaine position, il est identique au type bitboard excepté qu'il ne contient pas d'information de main.

Au début du jeu les joueurs possèdent toutes les pièces et aucune case n'est occupée, le tableau de jeu initial est donc :

{first = hand_mask; second = hand_mask};;

Pour chacun des tétrominos I.L.O.S.T. nous avons besoin de la liste de toutes ses positions possibles sur le plateau de jeu.

D'abord, étant donné une pièce p, la fonction unfold_piece p a b c génère la liste de toutes les positions possibles de cette pièce sur le plateau, avec a une liste de décalages pour lesquels p reste dans la partie supérieure du plateau, b une liste de décalages pour lesquels p est à cheval sur la partie supérieure et la partie inférieure, et enfin c une liste de décalages pour lesquels p reste dans la partie inférieure du plateau :

let unfold_piece p a b c =
  let lower_part n =
    if n >= 20 then p lsr (n - 20)
    else (p lsl (20 - n)) land board_mask
  in List.flatten [
    List.map (fun n -> {upper = p lsr n; lower = 0}) a;
    List.map (fun n -> {upper = p lsr n; lower = lower_part n}) b;
    List.map (fun n -> {upper = 0; lower = p lsr (n - 20)}) c;
  ];;

Ensuite, en fournissant les listes a b c adéquates, on spécialise unfold_piece pour des pièces de largeur 3 et de hauteur 2, des pièces de largeur 2 et de hauteur 3, la pièce de largeur 1 et de hauteur 4, la pièce de largeur 4 et de hauteur 1, et enfin de la pièce carrée de côté 2 :

let unfold_piece_3x2 p =
  unfold_piece p
  [0;1;2; 5;6;7; 10;11;12] [15;16;17] [20;21;22; 25;26;27; 30;31;32]
and unfold_piece_2x3 p =
  unfold_piece p
  [0;1;2;3; 5;6;7;8] [10;11;12;13; 15;16;17;18] [20;21;22;23; 25;26;27;28]
and unfold_piece_1x4 p =
  unfold_piece p
  [0;1;2;3;4] [5;6;7;8;9; 10;11;12;13;14; 15;16;17;18;19] [20;21;22;23;24]
and unfold_piece_4x1 p =
  unfold_piece p
  [0;1; 5;6; 10;11; 15;16] [] [20;21; 25;26; 30;31; 35;36]
and unfold_piece_2x2 p =
  unfold_piece p
  [0;1;2;3; 5;6;7;8; 10;11;12;13] [15;16;17;18] [20;21;22;23; 25;26;27;28; 30;31;32;33]
;;

On appelle alors:

• j la pièce qui miroite la pièce l ;
• z la pièce qui miroite la pièce s ;
• 0 la rotation d'angle nul ;
• 1 la rotation d'un quart de tour dans le sens horaire ;
• 2 la rotation de deux quarts de tour dans le sens horaire ;
• 3 la rotation de trois quarts de tour dans le sens horaire.

On obtient la liste de toutes les positions possibles des 19 tétrominos orientés à l'aide de ces 19 déclarations :

let tetro_i0 = unfold_piece_1x4 0b10000100001000010000
and tetro_i1 = unfold_piece_4x1 0b11110000000000000000
and tetro_l0 = unfold_piece_2x3 0b10000100001100000000
and tetro_l1 = unfold_piece_3x2 0b11100100000000000000
and tetro_l2 = unfold_piece_2x3 0b11000010000100000000
and tetro_l3 = unfold_piece_3x2 0b00100111000000000000
and tetro_j0 = unfold_piece_2x3 0b01000010001100000000
and tetro_j1 = unfold_piece_3x2 0b10000111000000000000
and tetro_j2 = unfold_piece_2x3 0b11000100001000000000
and tetro_j3 = unfold_piece_3x2 0b11100001000000000000
and tetro_oo = unfold_piece_2x2 0b11000110000000000000
and tetro_s0 = unfold_piece_3x2 0b01100110000000000000
and tetro_s1 = unfold_piece_2x3 0b10000110000100000000
and tetro_z0 = unfold_piece_3x2 0b11000011000000000000
and tetro_z1 = unfold_piece_2x3 0b01000110001000000000
and tetro_t0 = unfold_piece_3x2 0b11100010000000000000
and tetro_t1 = unfold_piece_2x3 0b01000110000100000000
and tetro_t2 = unfold_piece_3x2 0b01000111000000000000
and tetro_t3 = unfold_piece_2x3 0b10000110001000000000
;;

Déclarations dans lesquelles 0bBBBBBBBBBBBBBBBBBBBB est un nombre en binaire, sur 20 bits distribués en quatre morceaux de cinq bits, chaque morceau de cinq bits représentant l'occupation de la pièce orientée sur une rangée horizontale de la partie supérieure du plateau, la position initiale de la pièce orientée étant toujours dans le coin supérieur gauche. La fonction unfold_pieceWxH applique à la pièce les décalages appropriés qui lui font prendre toutes les autres positions envisageables.

Enfin on obtient la liste de toutes les positions possibles des cinq tétrominos non orientés à l'aide de ces cinq déclarations :

let tetro_i = List.flatten [tetro_i0;tetro_i1]
and tetro_l = List.flatten [tetro_l0;tetro_l1;tetro_l2;tetro_l3;tetro_j0;tetro_j1;tetro_j2;tetro_j3]
and tetro_o = List.flatten [tetro_oo]
and tetro_s = List.flatten [tetro_s0;tetro_s1;tetro_z0;tetro_z1]
and tetro_t = List.flatten [tetro_t0;tetro_t1;tetro_t2;tetro_t3]
;;

Souvenez-vous de la fonction rev_map_filter :

let rev_map_filter p f l =
  let rec loop l acc =
    match l with
    | [] -> acc
    | h::t ->
        if p h then loop t (f h::acc)
        else loop t acc
  in loop l [];;

Au lieu de lui donner la liste vide [] comme valeur initiale de l'accumulateur acc nous pourrions très bien lui donner une liste quelconque, de ce fait on réaliserait un append en plus de map et filter, ce qui nous donne une nouvelle version, rev_append_map_filter :

let rev_append_map_filter p f l1 l2 =
  let rec loop l acc =
    match l with
    | [] -> acc
    | h::t ->
        if p h then loop t (f h::acc)
        else loop t acc
  in loop l1 l2;;

C'est cette version que nous mettrons dans notre module ListXP.

Pour générer les coups légalement jouables, il nous faut définir une fonction du type :

bitboard -> bitboard list

Nous l'appellerons play_moves, elle démarre avec une liste vide [] et pour chacun des tétrominos I.L.O.S.T. elle augmente cette liste avec les nouveaux tableaux de jeux générés par la possession de ce tétromino en utilisant rev_append_map_filter :

let play_moves (b: bitboard ) =
  let hand1  = b.first  land hand_mask 
  and hand2  = b.second land hand_mask 
  and board1 = b.first  land board_mask 
  and board2 = b.second land board_mask
  in
  let can_move p =
    (p.upper land board1) lor 
    (p.lower land board2) = 0
  and play_move h p =
    {first  = p.upper + board1 + hand2;
     second = p.lower + board2 + hand1 - h}
  in let legal_moves h t acc = 
    if (hand1 land h) = 0 then acc
    else ListXP.rev_append_map_filter can_move (play_move h) t acc
  in begin 
    if (b.first land hand_mask) = 0 then
      []
    else
      let i = legal_moves hand_i tetro_i [] in
      let l = legal_moves hand_l tetro_l  i in
      let o = legal_moves hand_o tetro_o  l in
      let s = legal_moves hand_s tetro_s  o in
      let t = legal_moves hand_t tetro_t  s in
                                          t
  end;;

Voici simplement le type game qui prend les trois valeurs théoriques possibles pour un jeu de stratégie à information complète pour deux joueurs :

type game = First | Second | Tie;;

Nous définissons ainsi la valeur théorique d'un tableau de jeu :

• si cinq coups par joueur ont été joués alors le résultat est Tie ;
• sinon ce tableau peut générer une liste de tableaux par la fonction play_moves ;
• si cette liste est vide alors le résultat est First ;
• sinon si cette liste contient au moins un tableau dont la valeur est First alors le résultat est Second ;
• sinon si cette liste contient au moins un tableau dont la valeur est Tie alors le résultat est Tie ;
• sinon le résultat est First.

Nous écrivons maintenant la fonction eval qui donne la valeur théorique d'un tableau de jeu au nième coup suivant cette définition :

let rec eval (b: bitboard ) n =
  if n = 10 then Tie
  else eval_list (play_moves b) (succ n)
and eval_list l n =
  let rec loop l acc =
    if acc = Second then acc
    else match l with
    | [] -> acc
    | h::t ->
       ( match eval h n with
       | First  -> Second
       | Second -> loop t acc
       | Tie    -> loop t Tie )
  in loop l First;;

Ainsi que le code principal qui affiche la valeur théorique du jeu (la valeur théorique du tableau de jeu initial) :

print_string
  ( match eval {first = hand_mask; second = hand_mask} 0 with
  | First  ->  "First wins\n"
  | Second ->  "Second wins\n"
  | Tie    ->  "Tie game\n" );;