Board Game Students Challenge

Board Game Students Challenge a.galassi@unibo.it Sat, 15/12/2018 - 16:34

Each year, since 2014, as part of the course of Foundaments of Artificial Intelligence M, groups of students are invited to design a little prototype of an Artificial Intelligence able to play board games

 

Benchmarks

  • 2019: Tablut
  • 2015-2018: Nine Men's Morris. Information regarding this challenge are available in the specific page.
  • 2014: a part of Nine Men's Morris (first phase)

 

Results

This experience has led to:

  • New knowledge acquisition: autonomous study of AI techniques not taught during the course (Genetic Algorithms, Neuroevolution, Negamax, NegaScout, BNS)
  • Knowledge consolidation and motivation improvement: students declare themselves as more motivated by the challenge, and that it has helped them to learn the course concepts
  • Course exam performance improvement: at average, better final marks and smaller percentage of exam failure

 

Papers

The results of the research conducted from 2015 to 2017 have been presented at the XVIth International Conference of the Italian Association for Artificial Intelligence:

 

Nine Men's Morris Students Challenge

Nine Men's Morris Students Challenge a.galassi@unibo.it Sun, 15/10/2017 - 16:56

Each year, from 2015 to 2018, as part of the course of Foundaments of Artificial Intelligence M, groups of students have been invited to design a little prototype of an Artificial Intelligence able to play to the game of Nine Men's Morris.

 

This experience has led to:

  • New knowledge acquisition: autonomous study of AI techniques not taught during the course (Genetic Algorithms, Neuroevolution, Negamax, NegaScout, BNS)
  • Knowledge consolidation and motivation improvement: students declare themselves as more motivated by the challenge, and that it has helped them to learn the course concepts
  • Course exam performance improvement: at average, better final marks and smaller percentage of exam failure

 

This research has been presented at the XVIth International Conference of the Italian Association for Artificial Intelligence:

 

For any questions, feel free to contact professor Paola Mello (paola.mello *at* unibo.it), engineer Federico Chesani (federico.chesani *at* unibo.it) or Andrea Galassi (a.galassi *at* unibo.it).

 

Nine Men's Morris Good Moves Dataset

Thanks to this competition it has been possible to create a dataset of good moves for this game, that can be freely used for any machine learning approach: dataset page.

 

Acknowledgements

Thanks to every student who has participate to this competition:

Arianna Zanetti, Alessio Paccoia, Mirco Nani, Alessio Tonioni, Francesco Burelli, Antonio Murgia, Francesco Lo Cascio, Mirko Collura, Costantino Casaburi, Silvio Olivastri, Andrea Battaglia, Andrea Zanotti, Pierluigi Zama Ramirez, Niccolò Aimi, Francesco Giorgianni, Massimiliano La Ferrara, Angelo Maglione, Raffaele Rotella, Alessio Durinzi, Stefano Nicoletti, Alessandro Di Cesare, Filippo Franzoni, Tommaso Madonia, Andrea Galassi, Francesco Ricci, Cosimo Scarcella, Leo Gioia, Amedeo Palopoli, Alfonso Solimeo, Alessandro Vadruccio, Paolo Sarti, Marco Di Vincenzo, Marcello Ballanti, Dario Alise, Giuseppe Di Marzo, Federico Ruggeri, Dario Pasquali, Sara Bevilacqua, Nicola Lazzari, Andrea Rossetto, Nicola Ghiselli, Michele Gelsomini, Giocanni Grammatico, Alessandro Celi, Matteo Carano, Daniele Pettinari, Leonardo Mora, Leonardo Baroncelli, Francesco Calabria, Kevin Zaini, Alex Casadio, Simone Nigro, Nikos Thomopulos, Boschini Matteo, Silvestri Mattia, Guardati Simone, Buratti Luca, Gianessi Mattia, Berlati Alessandro, Corni Gabriele, Andraghetti Lorenzo, Bombino Andrea, Di Felice Marco, Damini Enrico, Stivala Giada, Cinesi Andrea, Neri Giacomo, Paternesi Claudio, Foti Daniele, Alessi Nicola, Zirondelli Alberto, Buscaroli Riccardo, Pastore Valerio, Tempesta Giuseppe, Torchi Andrea, Domeniconi Federico, Gavagna Andrea, Stella Federico, Chiossi Luca, Feraudo Angelo, Staffolani Alessandro, Nicolò Scarpa, Marco Raminella, Antonini Lorenzo, Baratta Giovanni, Della Penna Roberto, Magnani Paolo, Frabetti Filippo, Semprini Nicola, Grasso Antonio, Bonfiglioli Luca, Rosa Lorenzo.

2014/2015 Challenge Results

2014/2015 Challenge Results a.galassi@unibo.it Mon, 03/04/2017 - 18:25

Winner

The winner of the 2014/2015 competition, with 12 wins out of 12, is called DeepMill and is available at Github.

 

Partecipant Teams

Any student who has partecipated is free to notify any inaccuracy to Andrea Galassi ( andrea.galassi7 *at* unibo.it )

Team 1: negaGlik

Project written in C language.

Uses the NegaScout algorithm to perform a state space search.

Focus on limiting the number of access to memory through static data structures and on limiting the occupied space.

The heuristic function consider many elements, giving a different weight to each one according to the game phase.

Result achived: 10/12 wins.

Team 2: Squadra Ginew

Project written in Java language.

Performs a state space search with Iterative Deepening and alpha-beta algorithm.

Members: Aimi Niccolò, Zama Ramirez Pierlugi, Zanotti Andrea.

The project is available here (courtesy of the authors).

Result achived: 4/12 wins.

Team 3: Nexus

Project written in Java language.

Result achived: 1/12 win.

Team 4: Duniro

Project written in Java language.

Board representation contains many informations, it is based upon "positions" linked between each other.

Exploit state space search using Limitated Iterative Deepening and alpha-beta algorithm.

The heuristic function is slightly different for each phase and analyzes many factors, among which there are the number of completed and almost completed mills.

Result achived: 4/12 wins.

Team 5: DeepMill

Project written in Java language.

Compact representation of the state: two binary representation of the board (2 integer of 32 bits) and two integer counters for the number of checkers in players' hands.

A search in the state space is made using Iterative Deepening and the NegaScout algorithm (which is an improvment of alpha-beta search).

Uses a different heuristic function for each phase, considering the number of blocked checkers, the number of Mills present and other factors, focusing on blocking the adversary's checkers.

Uses a Transposition table: during the search, each visited state is saved in an Hash Map which exploit some symmetries of the problem to evaluate the heuristic faster and therefore speed up the search.

The original project is available here (courtesy of the authors).

The updated project is available at Github.

Members: Madonia Tommaso, Di Cesare Alessandro and Franzoni Andrea.

Result achived: 12/12 wins.

Team 6: UgoBugo

Project written in Java language.

Uses the NagaScout algorithm to perform the search in the state space

Members: Galassi Andrea.

Result achived: 4/12 wins.

Team 7: Unknown

Project written in Java language.

Members: Scarcella Cosimo e Ricci Francesco.

The project is available here (courtesy of the authors).

Result achived: 7/12 wins.

 

 

2015/2016 Challenge Results

2015/2016 Challenge Results a.galassi@unibo.it Tue, 04/04/2017 - 11:53

Winner

The winner of the 2015/2016 competition, with 14 wins out of 18, is called Samaritan.

 

Partecipant Teams

Any student who has partecipated is free to notify any inaccuracy to Andrea Galassi ( andrea.galassi7 *at* unibo.it )

Team 1: Alphabot

Binary representation of the board using two integers.

Iterative deepening search with alpha-beta pruning.

Multi-threaded idle-time searching.

The heuristic function is based on the value of the player's checkers.

Result achived: 10/18 wins.

Team 2: BotQuixote

State represented as arrays of bytes.

Perform state space search with Negamax algorithm and iterative deepening.

Use a revisited "Pectu-Holban" heuristic function and rely on transposition table to speed up the search.

Idle-time searching.

The project is available here (courtesy of the authors).

Team members: Ballanti Marcello, Di Vincenzo Marco e Sarti Paolo.

Result achived: 10/18 wins.

Team 3: Samaritan

Board state represented as two integers.

MTD(f) search algorithm with use of alpha-beta pruning and transposition tables.

The heuristic function consider many aspects of the board with different weights. The weights have been defined through genetic algorithms.

Iterative deepening search.

Result achived: 14/18 win.

Team 4: Cogito ergo Expando

Board state represented as an integer array.

Search in the state space with Negamax algorithm.

Transposition table to speed up the search.

Idle-time seatch based on the prediction of opponent move.

Iterative search and static state to improve memory usage.

Result achived: 1/18 wins.

Team 5: Mulinator

The project is available here (courtesy of the authors).

Team members: Lazzari Nicola and Rossetto Andrea

Result achived: 1/18 wins.

Team 6: TI GUSTA LA MANGUSTA?!

Alpha-beta search with Iterative Deepening.

Heuristic function based on mill possibility of the two players.

Result achived: 8/18 wins.

Team 7: DEEPLELE

Use of the AIMA library.

It performs an alpha-beta search that can be stopped with a timeout.

Parametric heuristic functions that changes according to game phase.

Result achived: 12/18 wins.

Team 8: Cook Iothin

Alpha-beta search with Iterative deepening.

Random choice of the next move during exploration.

The project is available here (courtesy of the authors).

Team members: Baroncelli Leonardo, Calabria Francesco and Zaini Kevin.

Result achived: 9/18 wins.

Team 9: BarbaMill

Board represented as two integer.

Alpha-beta search with iterative deepening and move sorting.

Idle-time search.

Members: Casadio Alex, Nigro Simone.

The project is available here (courtesy of the authors).

Result achived: 9/18 wins.

Team 10: La gallina Rosita

Negamax search.

Parametric heuristic function with different weight for each phase.

Use of enumerative instead of strings for the representation of the state.

To avoid memory limits, a single game state is mantained and changed through the search.

The project is available here (courtesy of the authors).

Team members: Thomopulos Nikos

Result achived: 11/18 wins.

2016/2017 Challenge Results

2016/2017 Challenge Results a.galassi@unibo.it Tue, 04/04/2017 - 14:59

Winner

The winner of the 2016/2017 competition, with 9 wins and 5 draws out of 14 matches, is called Akatsuki.

A sum up of the competition results can be found in the attached file "2017end". The detailed results are illustrated in the file "2017results", while the output of each match is available in the file "2017matches".

 

Partecipant Teams

Any student who has partecipated is free to notify any inaccuracy to Andrea Galassi ( a.galassi *at* unibo.it )

Team 1: MoulinBleu

Negascout algorithm.

State as a 3D byte matrix.

Use of hashtable (Zobrist hashing).

Heuristic: number of open mills and number of checkers.

 

Team 2: Akatsuki

Heuristic inspired by Petcu–Holban one, but takes into account also the opponent player situation.

 

Team 3: EUropean Genius

State as a 3x8 matrix. 

The heuristic function changes according to the moment of the game (not only the phase, but also the phases of a phase).

 

Team 4: Benchwarmers

Iterative Deepening Search.

The heuristic function takes into account the opponent checkers.

 

Team 5: MOLINARO

Negascout search, use of Peter Brook library.

Iterative Deepening.

Heuristic inspired by Petcu–Holban, but further parameter tuning.

 

Team 6: Mulino Bianco

State as a long integer (64 bit)

Symmetries considered to limit the possible actions generation.

Iterative Deepening with a different search algorithm for each phase.

Use of transposition table.

Heuristic function parameters tuned using genetic algorithms.

 

Team 7: Jar Jar

State as 2 integer of 4 bytes.

Use of 4 different heuristics according to the game phase.

Use of Best Node Search.

 

Team 8: bejoke

Heuristic function based on Fibonacci weights.

2017/2018 Challenge Results

2017/2018 Challenge Results a.galassi@unibo.it Sat, 15/12/2018 - 16:21

 The server used for the competition of this year can be found in the attached file "Mulino2018".

A sum up of the competition results can be found in the attached file "2018end". The detailed results are illustrated in the file "2018results", while the output of each match is available in the file "2018matches".

Winner

The winner of the 2017/2018 competition, with 10 wins and 2 draws out of 12 matches, is called CIRAM.

 

Partecipant Teams

Any student who has partecipated is free to notify any inaccuracy to Andrea Galassi ( a.galassi *at* unibo.it )

Team 1: Theta Team

 

 

Team 2: CIRAM

 

 

Team 3: FuffaTeam

 

Team 4: J*

 

 

Team 5: ᕦ(ò_ó)ᕤ

 

 

Team 6: Mulino Exception

 

 

Team 7: MillGates