Le but de cette session d'exercices est d'implémenter le jeu tic-tac-toe en OCaml, ainsi qu'un bot contre lequel jouer, en se conformant à la signature suivante :

module type Tictactoe = 
    sig
        type move = Empty | X | O
        type board

        val empty_board : board
        val possible_moves : board -> move 
                             -> (string * board) list
        val play_move : board -> move -> string 
                        -> (string * board) option
        val string_of_board : board -> string
        val string_of_move : move -> string
        val winning_config : board -> bool 
        val propose_move : board -> move -> string -> string option
    end

Exercice 0 - Programmation du jeu de base

• Problème 0 : Implémentez les fonctions string_of_move et string_of_board qui renvoient une chaîne représentant leur entrée.

• Problème 1 : Implémenter trois fonctions check_collumns, check_lines, check_diags de type board -> bool qui retournent true si une colonne, une ligne ou une diagonale contient respectivement trois occurrences du même move autre que Empty, sinon false. Utilisez ces fonctions pour implémenter la fonction winning_config : board -> bool qui vérifie qu'une configuration donné représente une configuration gagnante.

• Problème 2 : Implémenter une fonction play_move : board -> move -> string qui prend en entrée une configuration (représentée par une valeur de type board), le move à effectuer (X ou O, représenté par une valeur de type move) et une chaîne de caractères parmi "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "ccet :

• Si la case du tableau dont les coordonnées sont données par la chaîne d'entrée est vide, la fonction renvoie une Some (s, b') où b' est le tableau mis à jour de façon à ce que cette case soit maintenant occupée par X ou O selon le cas.

• Sinon, la fonction renvoie None.

• Problème 3 : Implémenter la fonction possible_moves : board -> move -> (string * board) list option qui prend en entrée une configuration (le premier argument) et une valeur de type move (le second argument, que nous supposons être soit X soit O) et qui retourne :

• None si aucun jeu n'est possible en utilisant la valeur de type move fournie.

• Some l, où l contient tous les coups possibles représentés comme des paires d'une chaîne de caractères (la coordonnée à laquelle jouer) et le tableau qui en résulte.

Exercice 1 - Programmation d'un robot

Pour cet exercice, nous utiliserons le type suivant pour représenter notre arbre de jeu, que nous utiliserons pour analyser les mouvements possibles et leurs gains.

• Problème 0 : Implémentez une fonction make_tree : board -> move -> string qui prend comme arguments la configuration courante, la dernière valeur du coup joué (X ou O), et la coordonnée où il a été joué (sous forme de chaîne) et renvoie un arbre de jeu dont la racine est est la configuration donnée.

• Problème 1 : Implémenter une fonction qui prend en entrée le plateau actuel, la dernière valeur du coup joué et sa coordonnée, et qui retourne une proposition pour le prochain coup. La fonction doit utiliser l'arbre de jeu construit avec make_tree pour analyser le jeu et proposer un coup qui a la possibilité de mener à une victoire pour le joueur dont les coups sont de valeur opposée à celle donnée (par exemple si le dernier coup a été X, nous voulons un coup pour O qui a l'opportunité de lui faire gagner la partie).

Devoir à rendre avant le 27 octobre 2023, 23h59, heure de Paris: Proposez et

implémentez une fonction propose_move alternative qui remplace celle que nous avons implémentée dans le cadre de l'Exercice 1, Problème 1. Un exemple d'algorithme alternatif est le suivant :

1) Etant donné une configuration du plateau de tic-tac-toe, le dernier coup joué et l'endroit où il a été joué, construire l'arbre de jeu t.

2) Noter tous les enfants de la racine de t en fonction d'une certaine métrique et retourner le coup qui correspond à l'enfant ayant le meilleur score.

Un exemple d'une telle métrique pour un arbre est par exemple donné en pondérant chaque feuille par +1 si elle est gagnante pour le joueur, +1 si elle est à égalité, et -1 si elle est gagnante pour l'adversaire, et enfin en faisant la somme de ces poids sur toutes les feuilles.