Projet de cours en binôme

IA de jeux hexagonaux Gopher & Dodo

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.

Contexte

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.

Règles

Gopher

  • Le plateau est vide au départ ; Rouge commence et peut poser n’importe où ;
  • chaque coup suivant doit toucher exactement une pièce adverse et aucune pièce alliée ;
  • aucun passage n’est autorisé ;
  • le dernier joueur capable de poser une pièce gagne.

Un plateau hexagonal de taille n compte 3n(n-1)+1 cases : 37 pour n=4, 91 pour n=6.

Dodo

  • Les pièces sont placées au départ selon la configuration corners ou one_line du serveur ;
  • chaque coup déplace une pièce d’une case tout droit ou en diagonale vers l’avant, sur une case vide ;
  • si vous n’avez aucun coup légal à votre tour, vous gagnez — l’inverse de la convention habituelle.

Implémentation

  • Plateau : coordonnées axiales (x, y) ; initialize_board construit les cases n=4/6 et la disposition initiale de Dodo.
  • Coups légaux (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.
  • Transitions (apply_action) : Gopher pose une pièce ; Dodo vide l’origine et remplit la destination.
  • Évaluation : la version actuelle utilise une heuristique de mobilité, -len(legals(...)) — moins de coups disponibles, moins bon score.
  • Recherche : 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.
  • Enveloppe de jeu : affiche un plateau ASCII à chaque tour, choisit la stratégie Gopher ou Dodo selon le nom renvoyé par le serveur, et ne modifie pas gndclient.py.

Résultats et limites

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) :

  • Dodo 4×4, un coup à profondeur 4 : environ 4,5 s ;
  • Gopher 4×4 contre un adversaire aléatoire, partie complète : environ 1,7 s.

Les limites sont explicites :

  • pas de gestion du temps : la profondeur fixe de 4 peut dépasser le temps sur un plateau 6×6 ;
  • l’évaluation ne compte que la mobilité et ignore les états terminaux ;
  • legals reparcourt state plusieurs fois, d’où un coût réel proche de O(n⁴) ;
  • Gopher ouvre toujours en (0,0) au lieu de chercher le premier coup ;
  • le cache de mémoïsation est illimité et s’accumule entre les parties ;
  • pas de tests automatisés, seulement des vérifications manuelles et scriptées.

Archive de cours

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

Notes techniques

01 Plateaux hexagonaux : coordonnées, voisins et coups légaux Coordonnées axiales, six voisins, bornes du plateau, et les deux règles de coups légaux de Gopher et Dodo. 02 Minimax avec mémoïsation : clés de cache, profondeur et évaluation Pourquoi la profondeur entre dans la clé, les deux problèmes de l'évaluation par mobilité, et l'absence d'alpha-beta.

Compétences associées

  • C++
  • Git