Each year, 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 to the game of Nine Men's Morris, a popular board game also known as Mill, Cowboy Checkers, Merrils, Mulino, Mulinello Grisia, Tris, or Filetto.

Slides of the current challenge (in italian): 2017 slides

Thanks to this competition 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.

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.

This data set has been created by Andrea Galassi, as part of his master thesis in Computer Science Engineering ("Ingegneria Informatica", in italian). Please feel free to contact him (a.galassi *at* unibo.it) or his thesis supervisors (Paola Mello, paola.mello *at* unibo.it, Federico Chesani federico.chesani *at* unibo.it) for further questions.

For further information, the thesis is available here: Symbolic versus sub-symbolic approaches: a case study on training Deep Networks to play Nine Men’s Morris game.

The dataset consist of 100,154 game states and as many good moves elaborated by an Artificial Intelligence for the game of Nine Men's Morris.

None of the states in the dataset is symmetric to any other, therefore anyone can handle the symmetries as he prefers.

If all the symmetric states are explored, the dataset can reach 1,628,673 pairs.

The dataset contains states both reachable and unreachable during a normal match, decreasing the probability of reaching a training state during a testing match. The moves contained in it could be different from the optimal one, however, it constitutes a good knowledge base, from which other AI system can learn to play the game.

All the data have been generated making play an Artificial Intelligence called Deep Mill against other artificial intelligence and gathering the choices made by Deep Mill during the games.

Three version of the dataset are available:

- The COMPLETE DATASET contains all the data, without the symmetric pairs.
- The GAMING DATASET do not contains data coming from a regular match starting with an empty board. Therefore it contains states which are more unlikely to be reached during a match.
- The EXPANDED DATASET contains all the data and the symmetric pairs.

The dataset does not distinction between black and white checkers but only between player checkers and enemy ones. An entry of the dataset consist of a string of 31 to 35 characters:

- The first 24 characters describe the board state with a letter representing the state of each position: O if the position is empty, M (Mine) if there is a checker of the player and E (Enemy) if there is an opponent one. The position are represented in order as they appear from left to right and from top to bottom
- A sequence of 4 numbers completes the state representation, where the first two numbers represent, respectively, the number of checkers that the player has in its hands and the ones that his adversary has; the last two represent, in the same order, the number of checker that the players have on the board.
- An hyphen divides the game state from the move description, which is written as pairs of coordinates letter-number; the meaning of each coordinate depends on the game phase: the parts of the move are written (if present) in the order FROM, TO and REMOVE.

The dataset consist of 2,085,613 states which are reachable through a finite sequence of legal moves starting from the initial empty board configurations.

None of the states contained in this dataset is present in the Good Moves Dataset.

- The COMPLETE STATES DATASET contains all the states, without the symmetric ones.
- The EXTENDED STATES DATASET contains all the states. with the symmetric ones.

This dataset has been used to train a neural networks system called Neural Nine Men's Morris to play the game, without inserting symbolic knowledge about the game rules.

After training the system has been tested on the whole expanded dataset (therefore considering any symmetric state) and the outcome is:

- The system has learnt the rules (99.55% of cases the chosen move is legal)
- The system has an accuracy of the whole move of 39.54%

For more information about neural networks, NNMM and its testing, see Symbolic versus sub-symbolic approaches: a case study on training Deep Networks to play Nine Men’s Morris game.

- Symbolic versus sub-symbolic approaches: a case study on training Deep Networks to play Nine Men’s Morris game
- Nine Men's Morris Annual Challenge
- Nine Men's Morris challenge, Foundamets of artificial intelligence A.A. 2016--2017
- Ultra-Strong and Extended Solutions for Nine Men Morris, Morabaraba, and Lasker Morris
- Solving Nine Men Morris
- DeepMill
- Nine Men’s Morris: Evaluation Functions

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 Team 2: Akatsuki Team 3: EUropean Genius Team 4: Benchwarmers Team 5: MOLINARO Team 6: Mulino Bianco Team 7: Jar Jar Team 8: bejoke

Attachment | Size |
---|---|

2017matches.zip | 84.49 KB |

2017results.xls | 49.5 KB |

2017end.pdf | 1.64 MB |

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

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

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.

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.

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.

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.

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

Team members: Lazzari Nicola and Rossetto Andrea

Result achived: 1/18 wins.

Alpha-beta search with Iterative Deepening.

Heuristic function based on mill possibility of the two players.

Result achived: 8/18 wins.

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.

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.

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.

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.

Attachment | Size |
---|---|

risultati15-16.zip | 74.61 KB |

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

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

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.

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.

Project written in Java language.

Result achived: 1/12 win.

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.

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.

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.

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.

Attachment | Size |
---|---|

risultati1415.zip | 35.99 KB |