Projet de cours en binôme
Université de technologie de Compiègne · IA02 Résolution de problèmes et programmation logique (printemps 2024)
Une IA pour les deux jeux hexagonaux à deux joueurs de Mark Steere, Gopher et Dodo : plateau en coordonnées axiales, génération des coups légaux, évaluation par mobilité et Minimax avec mémoïsation.
C’était le projet final d’IA02 « Résolution de problèmes et programmation logique » à l’UTC. Le cours fournissait un serveur arbitre (gndserver) et un client HTTP (gndclient.py) qui gère l’inscription, l’appariement, le temps, la légalité des coups et la synchronisation de l’état. Notre travail portait sur le cœur de l’IA, jeux.py : modélisation du plateau, génération des coups légaux, évaluation de la position et recherche.
Les adversaires sont deux jeux hexagonaux à deux joueurs de Mark Steere : Gopher et Dodo. Les règles ne sont pas compliquées, mais l’adjacence hexagonale et la règle contre-intuitive « aucun coup légal = victoire » rendent la génération des coups et la détection de fin de partie plus délicates que dans un jeu classique.
Gopher
Un plateau hexagonal de taille n compte 3n(n-1)+1 cases : 37 pour n=4, 91 pour n=6.
Dodo
corners ou one_line du serveur ;(x, y) ; initialize_board construit les cases n=4/6 et la disposition initiale de Dodo.legals) : Gopher examine les voisins des pièces adverses et garde les cases vides avec exactement un voisin ennemi et aucun allié ; Dodo utilise trois directions avant par couleur, avec contrôle des bornes et de la case vide.apply_action) : Gopher pose une pièce ; Dodo vide l’origine et remplit la destination.-len(legals(...)) — moins de coups disponibles, moins bon score.minmax + memoize, avec pour clé le plateau complet, la profondeur, le camp qui maximise, le joueur racine, la taille du plateau et le nom du jeu. La racine énumère les coups puis descend de quatre niveaux, soit cinq demi-coups.gndclient.py.Avec gndserver.exe -game gopher -random en local, test_client.py termine une partie complète et affiche Ending: 1 wins with a score of 1 puis Red wins!.
Mesures locales approximatives (Windows 11, Python 3.14) :
Les limites sont explicites :
legals reparcourt state plusieurs fois, d’où un coût réel proche de O(n⁴) ;(0,0) au lieu de chercher le premier coup ;Le dossier tp/ du dépôt conserve aussi les exercices et fiches de TD/TP d’IA02 : logique propositionnelle et du premier ordre, SAT (avec un encodage de Sudoku et des exemples Gophersat), Prolog (relations familiales, Mastermind), ASP avec Clingo et un tic-tac-toe Minimax. Ils sont indépendants du projet Gopher & Dodo et constituent une archive d’apprentissage complète.
Code et documents de règles : https://github.com/yicongl1/Gopher-and-Dodo