Interaction

Question 1

Construire une fenêtre présentant un point qu’il est possible de déplacer avec les flèches du clavier.

On utilisera la fonction bind comme dans l’exemple suivant

def key(event):
    ...

fen.bind("<space>", key)

Question 2

Ajouter des points (météores) suivants des trajectoires rectilignes uniformes partant des bords de la fenêtre à des positions, directions et vitesses aléatoires.

Question 3

Implémenter une méthode de détection décidant si l’objet de la question 1 a été touché par un météore.

Intelligence artificielle : Morpion

Représentation

Question 4

Comment représenter en mémoire une grille de morpion ? Un grille plus un ensemble de coups déjà joués plus l’information de la dernière personne ayant joué est appelé une configuration.

Question 5

Représenter la grille dans une fenêtre.

Question 6

Écrire une fonction utilisant les clics de la souris pour placer les coups des joueurs.

Pour détecter les clics de souris, on utilisera la méthode bind appliquée à un canevas comme dans l’exemple suivant

def souris(event):
    ...

can.bind('<Button-1>', souris)

Question 7

Écrire une fonction décidant de si une configuration est terminale, c’est à dire si soit l’un des joueurs à gagner, soit il n’est plus possible de jouer.

I.A.

L’arbre des coups d’un jeu est l’ensemble des parties possibles :

[$\blue{A}$, circle, draw, edge=->, blue [$\red{B_1}$, circle, draw, edge=->, red [$\blue{C_1}$, circle, draw, edge=->, blue [$\vdots$, edge=->, red] ] [$\blue{C_2}$, circle, draw, edge=->, blue [$\vdots$, edge=->, red] ] ] [$\red{B_2}$, circle, draw, edge=->, red [$\blue{C_3}$, circle, draw, edge=->, blue [$\vdots$, edge=->, red] ] [$\blue{C_4}$, circle, draw, edge=->, blue [$\vdots$, edge=->, red] ] ] ]

Ici chaque couleur désigne soit le (l’ordinateur), soit l’ (l’humain). Chaque nœud du graphe est une configuration du jeu.

Question 8

Écrire une fonction qui, étant donnée une configuration, construit l’ensemble des configurations possible en un coup. Si $C$ est une configuration, on notera $\succ C$ l’ensemble des configurations atteignable en un coup.

Question 9

Écrire une fonction qui, étant donnée une configuration du jeu, construit l’arbre des configurations possibles à partir de cette configuration (utiliser une fonction récursive).

Question 10

Écrire une fonction qui donne l’intérêt du joueur pour une configuration terminale, c’est à dire, étant donnée une configuration terminale, renvoie $1$ si la configuration est gagnante (pour le joueur), $-1$ si elle est perdante (toujours pour le joueur), et $0$ si il y a égalité.

L’intérêt de l’opposant pour une configuration terminale est l’opposée de l’intérêt du joueur (cf. jeux à somme nulle).

On va maintenant pouvoir calculer l’intérêt d’une configuration à partir de l’intérêt des configurations terminales. Pour cela, on utilise les deux hypothèse suivantes : chaque joueur joue le coup qui maximise l’intérêt la configuration obtenue.

Soit $A$ et $B$ les deux joueurs, on notera dans la suite $I_A$ et $I_B$ leurs fonctions d’intérêt. Soit une configuration $C_A$ où la dernière personne ayant jouée est $A$. C’est donc à $B$ de jouer. L’intérêt de $C_A$ pour $B$ est le maximum de ses intérêts pour les configurations de $\succ C_A$ (le joueur $B$ a en effet le loisir de jouer le coup qui maximise son intérêt). Ou encore, du point de vu de $A$ :

$$I_A(C_A) = \min_{C_B \in \succ C_A} I_A(C_B).$$

Question 11

Écrire les fonctions $I_A$ et $I_B$.

Question 12

Écrire une fonction qui, étant donnée une configuration $C_A$, détermine le coup à jouer pour $B$.

Hubert Godfroy