Team course project (2 people)

Gopher & Dodo hex-board game AI

Université de Technologie de Compiègne · IA02 Problem Solving and Logic Programming (spring 2024)

An AI for Mark Steere's two-player hex games Gopher and Dodo: axial-coordinate board, legal-move generation, a mobility evaluation and memoised Minimax search.

Background

This was the final project of IA02 “Problem Solving and Logic Programming” at UTC. The course supplied a referee server (gndserver) and an HTTP client (gndclient.py) handling registration, pairing, timing, legality checks and state synchronisation. Our job was the AI core, jeux.py: board modelling, legal-move generation, position evaluation and search.

The opponents are two two-player hex games designed by Mark Steere: Gopher and Dodo. Neither rule set is complicated, but hex adjacency and the counter-intuitive “no legal move means you win” rule make legal-move and terminal detection easier to get wrong than in ordinary board games.

Rules

Gopher

  • The board starts empty; Red plays first and may place anywhere;
  • every later move must touch exactly one enemy piece and zero friendly pieces;
  • no pass is allowed;
  • the last player able to place a piece wins.

A hex board of size n has 3n(n-1)+1 cells: 37 for n=4 and 91 for n=6.

Dodo

  • Pieces are placed at the start according to the server’s corners or one_line layout;
  • each move shifts one of your pieces one cell straight or diagonally forward, onto an empty cell;
  • if you have no legal move on your turn, you win — the opposite of the usual chess convention.

Implementation

  • Board: axial coordinates (x, y) represent the hex grid; initialize_board builds the n=4/6 cells and the Dodo starting layout.
  • Legal moves (legals): Gopher scans the neighbours of enemy pieces and keeps empty cells with exactly one enemy and no friendly neighbour; Dodo uses three forward directions per colour, with in-bounds and empty-target checks.
  • Transitions (apply_action): Gopher places a piece; Dodo clears the origin and fills the destination.
  • Evaluation: the current version uses a mobility heuristic, -len(legals(...)) — fewer available moves means a worse score.
  • Search: minmax plus memoize, keyed on the full board, depth, side to maximise, root player, board size and game name. The root enumerates moves and searches four more plies, five half-moves in total.
  • Game shell: prints an ASCII board each turn, dispatches to the Gopher or Dodo strategy from the server’s game name, and leaves the course-provided gndclient.py untouched.

Results and limits

With gndserver.exe -game gopher -random running locally, test_client.py completes a full game and prints Ending: 1 wins with a score of 1 and Red wins!.

Rough local measurements (Windows 11, Python 3.14):

  • Dodo 4×4, one move at depth 4: about 4.5 s;
  • Gopher 4×4 against a random opponent, full game: about 1.7 s.

The limitations are explicit:

  • no time management — a fixed depth of 4 can time out on 6×6 boards;
  • the evaluation only counts mobility and ignores terminal states;
  • legals rescans state repeatedly, so the real cost is close to O(n⁴);
  • Gopher always opens at (0,0) instead of searching the first move;
  • the memoisation cache is unbounded and grows across games;
  • there are no automated tests, only manual and scripted checks.

Course archive

The repository’s tp/ folder also keeps the IA02 exercises and tutorial sheets: propositional and first-order logic, SAT (including a Sudoku encoding and Gophersat samples), Prolog (family relations, Mastermind), ASP with Clingo, and a Minimax tic-tac-toe. They are independent of the Gopher & Dodo project and serve as a complete learning archive.

Source and rule documents: https://github.com/yicongl1/Gopher-and-Dodo

Technical notes

01 Hex boards: coordinates, neighbours and legal moves Axial coordinates, six neighbours, board bounds, and the two very different legal-move rules of Gopher and Dodo. 02 Minimax with memoisation: cache keys, depth and evaluation Why depth belongs in the cache key, the two problems with a mobility evaluation, and why this version has no alpha-beta.

Related skills

  • C++
  • Git