Gionnino9000

About the Project

Gionnino9000 is the team I took part in the Tablut Challenge 2022 with, a competition organized for the Fundamentals of Artificial Intelligence M course at Alma Mater Studiorum, University of Bologna. Our agent — an AI player capable of playing the board game Tablut — is called Tavoletta.

The rules are the interesting part of a competition like this one: your agent connects to a server running the game engine, and it has one minute per move. Not one minute of thinking on your gaming rig, either: everything runs on a virtual machine with 4 CPUs, 8 GB of RAM, no GPU and no internet connection. Whatever your agent is going to do, it has to do it there.

The Game

Tablut is an ancient Nordic board game, played on a 9x9 grid, and the competition adopts the so-called Ashton rules. The two sides are asymmetric:

• the defender (white) has 8 pawns and the king, and has to help the king escape;
• the attacker (black) has 16 pawns, and has to besiege the castle and capture the king.

Initial state of an Ashton Tablut board

The board has special tiles: the camps (the black starting positions), the castle (where the king starts) and the escape tiles at the edges. Pawns move orthogonally, any number of tiles, and can’t jump over other pawns, camps or the castle; once a black pawn leaves its camp it can’t get back in.

Captures are what make the game tricky: a pawn is captured when the opponent surrounds it on two opposite sides, while the king can only be captured if surrounded on every side. Camps and the castle act as a wall for capture purposes, and the capture must be “active” — moving your own pawn between two enemies is safe. White moves first; the game ends when the king reaches an escape tile (white wins), the king is captured (black wins), a player can’t move (that player loses), or the same state repeats twice (draw).

Tavoletta

The agent is written in Java, on top of the game engine and client code provided by professor A. Galassi, and talks to the server with JSON messages over a socket.

For the search we used the AIMA libraries (the ones that come with Artificial Intelligence: A Modern Approach): TavolettaSearch extends IterativeDeepeningAlphaBetaSearch — minmax with alpha-beta pruning and iterative deepening, bounded by the time limit — and overrides eval() so that non-terminal states are scored by our own heuristics:

@Override
protected double eval(State state, State.Turn player) {
    // Needed to make heuristicEvaluationUsed = true, if the state evaluated isn't terminal
    super.eval(state, player);

    // Return heuristic value for the given state
    return game.getUtility(state, player);
}

Iterative deepening is what makes the one-minute budget usable: the search keeps deepening until time runs out, and there’s always a best move ready to be sent. There’s also a TavolettaMCTS class extending the AIMA Monte Carlo Tree Search, which we experimented with but didn’t end up fielding.

Both heuristics evaluate a state as a weighted sum of a handful of features, plus flat bonuses in specific situations.

The Attacker Heuristic

Black plays differently depending on the phase of the game — we switch to late game when white is down to fewer than 5 pawns — so there are two sets of weights:

The RHOMBUS_POS feature is the one I like the most: in the early game the agent is rewarded for arranging its pawns into a rhombus formation around the board, a shape that pre-emptively covers the escape routes instead of chasing the king around:

// Matrix of favourite black positions in the initial stages to block the escape ways
private final int[][] rhombus = {
              {1,2},       {1,6},
        {2,1},                   {2,7},

        {6,1},                   {6,7},
              {7,2},       {7,6}
};

On top of the weighted sum, black gets a small aggression bonus when white pawns are in danger, and a flat bonus in the late game when the king can actually be captured.

The Defender Heuristic

White has a single set of weights, with the safety of its own pawns as the dominant term:

Before anything else, the defender checks whether the king can be captured in the state being evaluated — no point in scoring a position where you’re about to lose — and it gets a flat bonus for states where the king has an open escape route.

Some Numbers

On the competition VM, with 60 seconds per move, Tavoletta explored on average 3.6 million nodes playing black and 3.5 million playing white, reaching depth 5 in both cases.

Preparation

A good chunk of the work happened before writing any agent code. We learned to actually play the game, then went through the projects of the previous years — which we collected in a hall of fame with the approach each team took, from multi-threaded C with bitmasks to Rust players that dominated the tournament while being impossible to compile.

To design and discuss strategies I also built Tablut Tactics, a small tool to set up board positions and reason about them without having to play a full game every time.

Running It

You need the server running, then the player, then a second client — which can be another agent, a random one or the GUI client included in the repository:

java -jar ./Tavoletta.jar WHITE 60 localhost

The parameters are the side to play (WHITE or BLACK), the timeout in seconds and the server address.

Tavoletta vs Tavoletta, sped up 40x

The Result

We didn’t make it to the final round — the tournament was played in two groups, and ours was a rough one — but we did come home with a special prize, awarded by “the unquestionable maximum authorities in matter of coolness”: Contemporary Art.

Contemporary Art — you know why

The Name

Since I know you’re wondering:

• Tablut sounds like tavola (plank, in Italian);
• Tavoletta (small plank) is the Italian name of Plank, Jonny’s imaginary friend in Ed, Edd n Eddy;
• Jonny is Jonnino in the Italian dub, which became Gionnino — absolutely not because we misspelled it when we signed up for the competition;
• 9000 is a nerd reference to HAL9000, from 2001: A Space Odyssey.

End of the name explanation.

Team Members

Federico Andrucci	Karina Chichifoi	Alex Gianelli	Michele Righi