Description du jeu Othorro

Dans ce TP, on va faire une intelligence artificielle pour une variante du jeu Othello : le jeu Othorro !

En cas de doute, vous pouvez consulter les règles d'Othello ici.

Othorro est un jeu à deux joueurs, noir et blanc, qui jouent tour à tour sur un plateau de \(n \times n\) cases qui contient initialement 4 pions en haut à gauche. Exemple pour un plateau de taille 6 :

En commençant par le joueur noir, chaque joueur place un pion, ou passe si c'est impossible, en faisant en sorte d'entourer des pions adverses entre deux de ses pions. Tous les pions entourés dans les huit directions (haut, bas, gauche, droite et les quatre diagonales) sont alors remplacés par des pions de la couleur du joueur courant.

Exemple : le coup central ici par noir va tout prendre :

Dans Othorro, le plateau n'est pas un carré mais un tore ! Cela signifie qu'il n'y a pas de bords : si on sort par le côté gauche, on revient par le côté droit, même chose pour les directions verticales.

Voici indiqués sur le plateau par des croix les coups possibles du joueur noir, le premier joueur, sur le plateau initial :

S'il choisit de faire le coup en haut à droite, sur la deuxième ligne, on obtient alors le plateau suivant, sur lequel on a indiqué par des croix les coups possibles du joueur blanc :

Ici, ce sont, mis à part les conditions du tore, les mêmes règles qu'Othello. On rajoute une nouvelle règle : on permet de faire des coups circulaires en rajoutant un pion dans une ligne complète de pions de la couleur adverse :

La partie se termine quand aucun joueur ne peut jouer, le gagnant est alors celui qui a le plus de pions de sa couleur.

Représentation en OCaml et implémentation des règles

On va considérer les types

type joueur = Blanc | Noir
type case = Vide | Pion of joueur
type plateau = case array array

Un plateau est toujours une matrice carrée, donc il suffit de calculer la taille du array englobant pour en déduire sa dimension. La case p.(x).(y) est sur la ligne x et la colonne y.

Question 1. Écrire une fonction

val plateau_initial : int -> plateau

qui prend en entrée une taille \(t \ge 2\) et crée un plateau avec la configuration initiale des pions.

Question 2. Optionnel, mais ça vous sera utile.

Écrire une fonction

val plateau_affiche : plateau -> unit

qui affiche un plateau sous une représentation textuelle lisible, comme :

#O....
O#....
......
......
......
......

Question 3. Écrire une fonction

val opposant : joueur -> joueur

qui renvoie l'opposant du joueur donné.

Question 4. Écrire des fonctions

val plateau_case : plateau -> int -> int -> case
val plateau_place : plateau -> int -> int -> case -> unit

qui renvoient, ou modifient, la case associée aux coordonnées passées en entrée. Ces fonctions peuvent prendre des coordonnées qui ne sont pas dans \(\range{0}{t-1}^2\), où \(t\) est la taille du plateau, compte tenu du fait qu'on est sur un tore.

Indication : (-3) mod 5 vaut -3 en OCaml, car le reste \(r\) de la division de \(a\) par \(b\) y vérifie seulement \(|r| < |b|\) et a le signe de \(a\). Pour avoir un nombre positif, on peut rajouter des valeurs, ici (-3 + 5) mod 5 qui vaut bien 2. C'est une remarque cruciale pour les bords.

On supposera ici que les valeurs \(v\) données sont toujours telles que \(v + t \ge 0\).

Question 5. Écrire une fonction

val coups : plateau -> joueur -> (int * int) list

qui renvoie la liste des coups, c'est-à-dire la liste des positions possibles où le joueur donné peut placer un pion. Compte tenu des remarques précédentes, ces positions n'ont pas besoin d'être dans \(\range{0}{t-1}^2\).

Question 6. Écrire une fonction

val plateau_copie : plateau -> plateau

qui effectue une copie complète d'un plateau. C'est-à-dire que si on modifie le plateau copie, on ne change rien au plateau d'origine.

Question 7. Écrire une fonction

val joue_coup : plateau -> joueur -> int * int -> plateau

qui prend en entrée un plateau, un joueur et un coup valide, et l'applique sur le plateau, c'est-à-dire place le pion et retourne tous les pions adverses qu'il faut retourner.

Cette fonction ne modifie pas le plateau en entrée mais renvoie un nouveau plateau.

Évaluation et stratégie gloutonne

Question 8. Écrire une fonction

val mobilite : joueur -> plateau -> int

qui renvoie la différence entre le nombre de coups du joueur sur le plateau donné et le nombre de coups de son adversaire. On parle de score de mobilité.

Question 9. Écrire une fonction

val materiel : joueur -> plateau -> int

qui renvoie la différence entre le nombre de pions du joueur et le nombre de pions de son adversaire. On parle de score matériel.

Question 10. En déduire une fonction

val evalue : joueur -> plateau -> joueur -> int

où evalue j p j' renvoie la somme des scores de mobilité et matériel vis-à-vis du joueur j. Le paramètre j' sera ici ignoré, mais il sera utile dans la suite.

Cette fonction sera celle qu'on va utiliser pour les stratégies du cours.

Question 11. Écrire une fonction

val joue : (joueur -> plateau -> joueur -> int) ->
    plateau -> joueur -> plateau option

où joue eval p j renvoie :

• None si le joueur j n'a pas de coup possible dans le plateau p ;
• Some p' sinon, où p' est, de tous les plateaux atteints, celui qui a la plus grande valeur eval j p' j' où j' est l'opposant de j. En cas d'égalité, on garde le premier coup dans l'ordre de la liste renvoyée par coups.

Question 12. Écrire une fonction

val combat : int ->
    (joueur -> plateau -> joueur -> int) ->
    (joueur -> plateau -> joueur -> int) -> plateau

où combat taille eval_noir eval_blanc va créer un plateau initial et faire jouer tour à tour noir et blanc selon les fonctions d'évaluation passées en entrée, avec la fonction joue précédente.

Quand les deux joueurs passent successivement, la partie s'arrête et la fonction renvoie le plateau correspondant.

Note : je vous conseille d'afficher la suite des plateaux pour pouvoir mettre au point le code ensuite.

Question 13. Écrire une fonction

val gagnant : plateau -> joueur

qui renvoie le joueur gagnant sur un plateau (en cas d'égalité, c'est noir qui gagne).

Minmax et élagage \(\alpha\)-\(\beta\)

Question 14. Écrire une fonction

val minmax : (joueur -> plateau -> joueur -> int) -> int
    -> joueur -> plateau -> joueur -> int

où minmax eval prof j p courant renvoie la valeur obtenue par la stratégie minmax visant à maximiser l'évaluation de j dans le cas où c'est au joueur courant de jouer dans le plateau p.

Le paramètre prof régit la profondeur de recherche : quand prof est nul, on renvoie l'évaluation directe de la partie.

Remarque

On peut alors utiliser minmax evalue prof comme fonction d'évaluation pour joue : c'est pour cela que evalue prend en dernier paramètre le joueur qui doit jouer. Il faut aussi penser au cas où courant doit passer, sans que la partie soit terminée pour autant.

Question 15. Écrire une fonction

val alpha_beta : (joueur -> plateau -> joueur -> int) -> int
    -> joueur -> plateau -> joueur -> int

qui procède comme la précédente mais en utilisant l'élagage \(\alpha\)-\(\beta\). Ici, ces deux paramètres ne sont pas présents, on pourra les faire apparaître dans une fonction auxiliaire récursive.

On pourra s'inspirer du pseudo-code présent sur la page Wikipédia.

Exemples de sorties

On vous donne la sortie de la correction pour les commandes suivantes :

let p = plateau_initial 5
val p : plateau =
  [|[|Pion Noir; Pion Blanc; Vide; Vide; Vide|];
    [|Pion Blanc; Pion Noir; Vide; Vide; Vide|];
    [|Vide; Vide; Vide; Vide; Vide|];
    [|Vide; Vide; Vide; Vide; Vide|];
    [|Vide; Vide; Vide; Vide; Vide|]|]

let _ = plateau_case p 0 1
- : case = Pion Blanc

let _ = plateau_case p (-5) 6
- : case = Pion Blanc

let _ = plateau_place p 0 1 (Pion Noir); p
- : plateau =
[|[|Pion Noir; Pion Noir; Vide; Vide; Vide|];
  [|Pion Blanc; Pion Noir; Vide; Vide; Vide|];
  [|Vide; Vide; Vide; Vide; Vide|];
  [|Vide; Vide; Vide; Vide; Vide|];
  [|Vide; Vide; Vide; Vide; Vide|]|]

let _ = coups p Blanc
- : (int * int) list = [(1, 2); (4, 0); (4, 2)]

let _ = coups p Noir
- : (int * int) list = [(1, 4); (2, 0); (2, 4)]

let _ = joue_coup p Blanc (4,0)
- : plateau =
[|[|Pion Blanc; Pion Noir; Vide; Vide; Vide|];
  [|Pion Blanc; Pion Noir; Vide; Vide; Vide|];
  [|Vide; Vide; Vide; Vide; Vide|];
  [|Vide; Vide; Vide; Vide; Vide|];
  [|Pion Blanc; Vide; Vide; Vide; Vide|]|]

let _ = mobilite Noir p
- : int = 0

let _ = materiel Noir p
- : int = 2

let _ = evalue Noir p Blanc
- : int = 2

let _ = joue evalue p Noir
- : plateau option =
Some
 [|[|Pion Noir; Pion Noir; Vide; Vide; Vide|];
   [|Pion Noir; Pion Noir; Vide; Vide; Pion Noir|];
   [|Vide; Vide; Vide; Vide; Vide|];
   [|Vide; Vide; Vide; Vide; Vide|];
   [|Vide; Vide; Vide; Vide; Vide|]|]

Dans le dernier exemple, les trois coups possibles de noir donnent la même évaluation (5) : c'est le premier, (1, 4), qui est retenu.

Exemple de partie