But du TP : déterminer une stratégie gagnante au tic tac toe/morpion en C en utilisant le calcul des attracteurs.

Rappel : à 2 joueurs sur une grille carrée de 9 cases, les joueurs choisissent chacun leur tour des cases libres. Le premier joueur qui aligne 3 cases horizontalement, verticalement ou en diagonale remporte la partie.

Algorithme à suivre pour calculer les positions gagnantes pour J1 :
- Parcours de graphe pour noter les états accessibles et initialiser un tableau D contenant pour chaque sommet son degré sortant
- Parcours du graphe transposé en commençant par les sommets de degré 0 gagnants pour J1 :
  * Pour chaque sommet rencontré appartenant à J1, l'ajouter aux sommets à parcourir, c'est une position gagnante pour J1.
  * Pour chaque sommet rencontré appartenant à J2, décrémenter sa valeur dans le tableau D, si elle arrive à 0, c'est que tous ses successeurs sont des positions gagnantes pour J1, et il s'agit donc d'une position gagnante pour J1. On l'ajoute aussi aux sommets à parcourir.

Considérations pratiques (vous pouvez ignorer ces indications et faire vos propres choix) :
- On peut représenter les états par des nombres entre 0 et 3^9 - 1, correspondant au nombre dont l'écriture en base 3 contient un 0 en position i si la case i est vide, contient un 1 en position i si la case i a été jouée par J1 et contient un 2 en position i si la case i a été jouée par J2. Beaucoup de ces nombres ne correspondent pas à des parties licites de TicTacToe, mais cette borne supérieure est assez petite pour être la longueur d'un tableau d'entiers en C.
- On peut parcourir les cases d'une grille étant donné l'entier qui la représente par divisions euclidiennes successives par 3. Les valeurs prises par les restes correspondent à 0, 1 ou 2 selon le contenu de la case.
- On peut parcourir le graphe de manière implicite sans jamais le construire explicitement. En parcourant les cases d'une grille, on peut savoir quels ont été les coups précédents possibles ou alors quels sont les coups suivants possibles.
- On peut implémenter une pile/file dans un tableau pour parcourir le graphe de manière assez simple car on peut borner facilement la taille nécessaire pour la pile (par exemple, 3^10 est une borne assez large sur le nombre d'arêtes du graphe car chaque sommet à moins de 9 successeurs.

Produit final (au choix selon l'ambition) :
- afficher les positions gagnantes pour le joueur 1
- créer un programme qui ne perd jamais et qui gagne toujours s'il possède une stratégie gagnante à un moment de la partie
- créer un programme qui parfois laisse une chance au joueur humain