Gionnino9000

Il Progetto

Gionnino9000 è il team con cui ho partecipato alla Tablut Challenge 2022, la competizione organizzata per il corso di Fondamenti di Intelligenza Artificiale M, all’Alma Mater Studiorum, Università di Bologna. Il nostro agente — un’AI capace di giocare al gioco da tavolo Tablut — si chiama Tavoletta.

La parte interessante di una competizione del genere sono i vincoli: l’agente si connette a un server che esegue il motore di gioco e ha un minuto per mossa. E non un minuto sul proprio PC da gaming: gira tutto su una macchina virtuale con 4 CPU, 8 GB di RAM, niente GPU e niente connessione a Internet. Qualunque cosa faccia il tuo agente, deve farla lì.

Il Gioco

Tablut è un antico gioco da tavolo di origini nordiche, che si gioca su una griglia 9x9; la competizione adotta le cosiddette regole di Ashton. I due schieramenti sono asimmetrici:

il difensore (bianco) ha 8 pedine e il re, e deve aiutare il re a fuggire;
l’attaccante (nero) ha 16 pedine, e deve assediare il castello e catturare il re.

Stato iniziale di una partita ad Ashton Tablut

La griglia comprende delle caselle speciali: i campi (le posizioni di partenza dei neri), il castello (dove parte il re) e le vie di fuga ai bordi. Le pedine si muovono ortogonalmente, di un numero qualsiasi di caselle, senza poter scavalcare altre pedine, i campi o il castello; una pedina nera che esce dal proprio campo non può più rientrarci.

Sono le catture a rendere il gioco insidioso: una pedina viene catturata quando l’avversario la circonda su due lati opposti, mentre il re può essere catturato solo se circondato su ogni lato. Campi e castello si comportano da barriera ai fini della cattura, e la cattura dev’essere “attiva”: muovere una propria pedina fra due avversarie è sicuro. Il bianco muove per primo; la partita finisce quando il re raggiunge una via di fuga (vince il bianco), il re viene catturato (vince il nero), un giocatore non può più muovere (e perde), oppure lo stato di gioco si ripete due volte (pareggio).

Tavoletta

L’agente è scritto in Java, sopra al motore di gioco e al codice client forniti dal professor A. Galassi, e comunica col server tramite messaggi JSON su socket.

Per la ricerca abbiamo usato le librerie AIMA (quelle di Artificial Intelligence: A Modern Approach): TavolettaSearch estende IterativeDeepeningAlphaBetaSearch — minmax con alpha-beta pruning e iterative deepening, limitato dal tempo a disposizione — e sovrascrive eval() in modo che gli stati non terminali vengano valutati dalle nostre euristiche:

@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);
}

È l’iterative deepening a rendere utilizzabile il budget di un minuto: la ricerca continua ad approfondire finché il tempo non scade, e c’è sempre una mossa migliore pronta da inviare. Nel progetto c’è anche una classe TavolettaMCTS, che estende il Monte Carlo Tree Search di AIMA: l’abbiamo sperimentata, ma non è quella che abbiamo schierato.

Entrambe le euristiche valutano uno stato come somma pesata di poche feature, più dei bonus flat in situazioni particolari.

Euristica dell’Attaccante

Il nero gioca in modo diverso a seconda della fase di gioco — si passa al late game quando il bianco scende sotto le 5 pedine — quindi ci sono due set di pesi:

Feature	Significato	Early game	Late game
`WHITE_EATEN`	pedine bianche già catturate	45%	40%
`BLACK_ALIVE`	pedine nere ancora in gioco	35%	30%
`BLACK_SUR_K`	pedine nere attorno al re	15%	25%
`RHOMBUS_POS`	pedine nella formazione a rombo	5%	—
`BLOCKED_ESC`	pedine che bloccano le vie di fuga	—	5%

RHOMBUS_POS è la feature che mi piace di più: nell’early game l’agente viene premiato se dispone le proprie pedine in una formazione a rombo attorno alla scacchiera, una figura che copre preventivamente le vie di fuga invece di inseguire il re per il tabellone:

// 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}
};

Oltre alla somma pesata, il nero riceve un piccolo bonus di aggressività quando ci sono pedine bianche in pericolo, e un bonus flat nel late game quando il re è effettivamente catturabile.

Euristica del Difensore

Il bianco ha un unico set di pesi, in cui domina la sicurezza delle proprie pedine:

Feature	Significato	Peso
`SAFE_PAWNS`	pedine bianche non catturabili	42%
`WHITE_ALIVE`	pedine bianche ancora in gioco	35%
`BLACK_EATEN`	pedine nere già catturate	18%
`KING_MOVEMENT`	direzioni in cui il re è libero di muoversi	5%

Prima di ogni altra cosa, il difensore controlla se nello stato che sta valutando il re può essere catturato — non ha molto senso dare un buon punteggio a una posizione in cui stai per perdere — e riceve un bonus flat per gli stati in cui il re ha una via di fuga aperta.

Qualche Dato

Sulla VM della competizione, con 60 secondi per mossa, Tavoletta ha esplorato in media 3,6 milioni di nodi giocando col nero e 3,5 milioni col bianco, raggiungendo in entrambi i casi la profondità 5.

Preparazione

Buona parte del lavoro è avvenuta prima di scrivere una riga dell’agente. Abbiamo imparato a giocare davvero, poi siamo andati a studiare i progetti degli anni precedenti — che abbiamo raccolto in una hall of fame con l’approccio di ciascun team, dal C multi-thread con le bitmask ai player in Rust che dominavano il torneo pur essendo impossibili da compilare.

Per progettare e discutere le strategie ho anche realizzato Tablut Tactics, un piccolo strumento per impostare posizioni sulla scacchiera e ragionarci sopra senza dover giocare ogni volta una partita intera.

Esecuzione

Serve il server in esecuzione, poi il player, poi un secondo client — che può essere un altro agente, uno random, oppure il client con GUI incluso nella repository:

java -jar ./Tavoletta.jar WHITE 60 localhost

I parametri sono il colore con cui giocare (WHITE o BLACK), il timeout in secondi e l’indirizzo del server.

Tavoletta contro Tavoletta, velocizzato 40x

Il Risultato

Al girone finale non ci siamo arrivati — il torneo si giocava in due gruppi, e il nostro era piuttosto tosto — ma a casa ci siamo portati un premio speciale, assegnato dalle “indiscutibili massime autorità in materia di figaggine”: Contemporary Art.

Contemporary Art — you know why

Spiegazione del Nome

Dato che so che te lo stai chiedendo:

Tablut somiglia a tavola;
Tavoletta è il nome italiano di Plank, l’amico immaginario di Jonnino in Ed, Edd & Eddy;
Jonny in italiano è Jonnino, che è diventato Gionnino — assolutamente non perché abbiamo sbagliato a scriverlo quando ci siamo iscritti alla competizione;
9000 è una piccola nerd reference a HAL9000, di 2001: Odissea nello spazio.

Fine della spiegazione del nome.

Membri del Team



Federico Andrucci	Karina Chichifoi	Alex Gianelli	Michele Righi