TP 1 : Rappel de Python

On va programmer une IA stochastique pour le célèbre jeu du Pierre Feuille Ciseau. On trouvera ici une implémentation simple du jeu où l’IA joue de façon aléatoire. L’idée est la suivante : on va garder en mémoire des statistiques sur la façon dont le joueur adverse joue. Plus précisément, on va se rappeler $N(m_1,m_2,m_3)$ pour $m_1,m_2,m_3 \in \{p,f,c\}$, qui correspond au nombre de fois où le joueur a joué ces coups-là à la suite. Par exemple, $N(p,f,p)$ est le nombre de fois où le joueur a joué consécutivement “Pierre”, puis “Feuille” puis “Ciseau”. Le prochain mouvement de l’IA sera alors défini ainsi: si $m_1,m_2$ sont les deux derniers coups du joueur, on va considérer que le coup suivant le plus probable du joueur est $m_3$ telle que $N(m_1,m_2,m_3)$ est maximal. L’IA jouera donc le coup qui bat $m_3$.

Par exemple, si le joueur vient de jouer $m_1,m_2$ et qu’on a $N(m_1,m_2,c) = 3$, $N(m_1,m_2,p) = 2$, $N(m_1,m_2,f)=10$, alors l’IA va jouer $c$ car il est très probable que le joueur joue $f$ au prochain coup. Si le joueur joue le coup $m'$, on mettra ensuite à jour $N(m_1,m_2,m')$ en l’incrémentant pour garder les statistiques à jour.

Pour cela, on va modéliser une suite de trois coups comme une chaîne de trois caractères dans “p”, “f” et “c” et on va utiliser un dictionnaire stat : dict[str,int] qui va associer une chaîne de trois caractères à un nombre de coup.
1. Dans main, initialiser stat à 0 pour chaque suite de trois coups.
2. Écrire une fonction most_probable_move(stat, m1, m2) qui renvoie le coup du joueur le plus probable sachant qu’il vient de jouer m1 puis m2.
3. Modifier la boucle de la fonction main pour mettre à jour la variable stat après chaque coup du joueur.
4. Modifier la fonction iaMove pour qu’elle joue comme décrit plus haut.
5. Essayez de battre votre IA :).
Il est peu efficace de stocker trois mouvements comme une chaîne de caractères. On va considérer que Pierre est $0$, Feuille est $1$ et Ciseau est $2$. On stockera une suite de mouvement $m_1,m_2,m_3$ comme $9m_1+3m_2+m_0$. Par exemple, “pfc” sera représenté par le nombre $9 \times 0+3 \times 1 + 2 = 4$. Adaptez votre code à cette nouvelle représentation.
Refactorisez le code précédent. On voudra :
- Une classe abstraite Player. Elle aura deux méthodes : une méthode move(self) qui renvoie le prochain coup à jouer et une méthode update_strategy(self, cplayer) qui met à jour des structures de données internes à la classe en fonction du dernier coup cplayer qui vient d’être joué par l’autre joueur.
- Des classes héritées : HumanPlayer, RandomPlayer, StocPlayer qui implémente move(self) et update_strategy(self,player). HumanPlayer.move correspond à un mouvement récupéré via le clavier, RandomPlayer.move correspond à un mouvement aléatoire uniforme et StocPlayer a la stratégie de la question précédente.
- Une classe Pfc. Son constructeur prend deux Player. Elle a une méthode play(self) qui fait jouer les deux joueurs l’un contre l’autre.
Implémentez une stratégie BeatStocPlayer qui bat StocPlayer systématiquement.

On considère le jeu de Nim suivant : $N$ bâtons sont disposés devant deux joueurs. Chacun leur tour, un joueur peut enlever $1$, $2$ ou $3$ bâtons. Le joueur qui prend le dernier bâton perd.

On définit $G_i$ à vrai si et seulement si le joueur qui commence dans un jeu avec $i$ bâton est sûr de gagner.
1. Montrer que $G_2, G_3, G_4$ sont vraies.
2. Montrez que si $G_i$ n’est pas vraie, alors le joueur qui ne commence pas est certain de gagner. On pourra le montrer par récurrence sur $i$.
3. Montrez que si $G_{i-1}$, $G_{i-2}$ et $G_{i-3}$ sont toutes les trois vraies, alors $G_i$ est fausse. De même, montrez que si au moins une des valeurs $G_{i-1}$, $G_{i-2}$ ou $G_{i-3}$ est fausse, alors $G_i$ est vraie.
Écrire une fonction strategy(n) qui renvoie une liste de Booléens g de taille n+1 tel que g[i] vaut $G_i$.
Implémenter le jeu de Nim où un joueur joue contre une IA. L’IA devra toujours gagner si elle commence dans une position gagnante.

Dans cet exercice, le but est d’implémenter un algorithme capable de reconnaître une courbe tracée en un seul mouvement (par exemple à la souris ou sur un écran tactile). On va utiliser pour cela un algorithme performant connu sous le nom de $1 Recognize. On pourra aussi consulter le papier par Wobbrock, Wilson et Li présentant la technique (voir notamment le pseudocode annexe A).

On représente une courbe par une liste de paires de float. Par exemple [(0.0,0.0), (1.0,0.0), (1.0,1.0)] correspond à une courbe où l’on a démarré au point $(0,0)$ puis on est allé au point $(1,0)$ et enfin au point $(1,1)$. On dispose d’une courbe $C$ tracé par l’utilisateur ainsi que plusieurs courbes templates $T_1,\dots,T_p$ (par exemple “carré”, “rond” et “triangle”). Notre but est de trouver le template le plus proche de $C$. Pour cela, on a besoin de définir une distance entre deux courbes. On peut le faire ainsi si $C$ et $T$ ont le même nombre $N$ de points:

\[ d(C,T) = (1/N)\sum_{i=0}^{N-1} \sqrt{(C[i][0]-T[i][0])^2+(C[i][1]-T[i][1])^2}\]

On fournit 1dollar.py qui contient un code permettant de dessiner une courbe à la souris. La suite des points est ensuite affichée grâce à la méthode _on_button_release.

Implémenter une fonction qui prend deux courbes ayant le même nombre de points en entrée et renvoie leur distance.

Cette approche a deux problèmes : premièrement, il est rare que $C$ ait le même nombre de points que $T$. Pour cela, on fixe un $N$ ($N=32$ dans le papier) et on renormalise $C$ et $T$ pour qu’ils aient chacun $N$ points uniformément répartis. Pour cela, on regarde la longueur totale $L$ de la courbe (la somme de la taille des segments) et on va chercher à ne garder que $N$ point espacées de $I = L/(N-1)$. Pour cela, on part du premier point $p_0=(x_0,y_0)$ et on va chercher le point $p_i=(x_i,y_i)$ suivant tel que la courbe entre $p_0$ et $p_{i-1}$ vaut $D<l$ mais $D+d \geq l$ où $d$ est la distance entre $p_{i-1}$ et $p_i$. On prend un nouveau point $q$ qui est une interpolation entre $p_{i-1}$ et $p_i$ définit par $((I-D)/d)(p_{i}-p_{i-1})$. On repart ensuite de $q$ et on cherche le point suivant de la même façon (voir le pseudocode dans le papier). Voici un exemple de renormalisation (le résultat est en rouge) :

Implémenter la fonction resample(c, N) qui renormalise une courbe c en N point.

Le deuxième problème avec cette approche est qu’elle dépend de la position de la courbe dans le plan, de sa taille et de sa rotation. On va donc normaliser une dernière fois. Pour cela, on va commencer par calculer le barycentre de la courbe (ce qui correspond à prendre la moyenne des $x$ et la moyenne des $y$).

Écrire une fonction normalize(c, size) qui normalise la courbe ainsi (on pourra séparer en plusieurs sous-fonctions).
- Calculer le barycentre $B=(b_x,b_y)$ de c.
- On recentre la courbe pour que le barycentre soit en $(0,0)$. Pour cette opération et la précédente, on fait juste une translation $(x,y) \mapsto (x-b_x, y-b_y)$.
- On effectue une rotation de c pour qu’il y ait un angle $0$ entre le premier point et le barycentre $B$. Comme le barycentre est maintenant en $0$, il suffit de faire une rotation centré en $(0,0)$ qui ramène le premier point de $c$ sur l’axe $0$. Pour cela, on fait $x \mapsto (x \cos \theta + y \sin \theta, x \sin \theta - y \cos \theta)$. Et $\theta = -\arctan(y_0/x_0)$.
- On redimensionne pour que la figure tiennent dans une fenêtre de taille size par size. Pour cela, on calcule la largeur et la hauteur de la courbe. La largeur est définie comme $w=x_d-x_g$ où $x_g$ (resp. $x_d$) est la coordonnée $x$ du point le plus à gauche (resp. droite). La hauteur est définie comme $h=h_t - h_b$ où $h_t$ (resp. $h_b$) est la coordonnée $y$ du point le plus haut (resp. le plus bas). On peut ensuite normaliser les points par $(x,y) \mapsto (size \times (x/w), size \times (y/h))$.

On s’aidera du pseudo-code donné dans le papier original (annexe A).

Une rotation pour que l’angle entre le barycentre (vert) et le premier point soit 0

Écrire une fonction classify(c, T, N=64, size=100) où T est une liste de courbe. La fonction renvoie la courbe de T qui est la plus proche de c une fois que c et toutes les courbes de T ont été normalisées. On pourra tester l’efficacité en créeant