Nine Men's Morris

Nine Men's Morris a.galassi@unibo.it Mon, 03/04/2017 - 15:35

Nine Men's Morris is a popular board game also known as Mill, Cowboy Checkers, Merrils, Mulino, Mulinello Grisia, Tris, or Filetto.
It has been chosen as benchmark for a series of research activities.

Information about the rules of the game can be found in the free resources (bottom of the page) or on the wikipedia page.

 

Each 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 intelligent agent able to play to the game.

This challenge have made possible to acquire data which have been used for:

 

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

 

Related papers from our research group

 

Useful free resurces

 

Neural Nine Men's Morris

Neural Nine Men's Morris a.galassi@unibo.it Sun, 15/10/2017 - 17:17

If you use this software as part of any work, please cite it as:

F. Chesani, A. Galassi, M. Lippi and P. Mello, "Can Deep Networks Learn to Play by the Rules? A Case Study on Nine Men's Morris", 2018, in IEEE Transactions on Games, Volume 10, Issue 4, DOI: 10.1109/TG.2018.2804039

The accepted version of this work (post-print) can be found here (bottom of the page).

 

NNMM logo

Introduction

Neural Nine Men's Morris (NNMM) is a software capable to build, train, test and use Deep Neural Networks which can be used for playing the game of Nine Men's Morris.
It has been demonstrated that the system is capable to learn to play by the rules of the game, even if the knowledge of those rules has not been provided to it.

It has been designed by Andrea Galassi, as part of his master thesis in Computer Science Engineering ("Ingegneria Informatica", in italian), and it has been improved as part of a successive work, that will be published in the journal IEEE Transactions on Games.


Please feel free to contact the authors of this work for further questions: Andrea Galassi (a.galassi *at* unibo.it), Paola Mello (paola.mello *at* unibo.it), Federico Chesani (federico.chesani *at* unibo.it).

For further information, a link to Andrea's master thesis is available at the bottom of the page among the useful resources.

 

Software and implementation

The software is under the MIT License and is available here: NNMM.

The system has been written in Python language, relying on the Lasagne, Theano and Numpy libraries.

NNMM architecture

System Architecture

NNMM relies on 3 neural networks to decide the move to make. Each network is dedicated to the choice of one of the three parts of the final move.

These parts are:

  • TO (T): where the checker will be placed
  • FROM (F): what checker will be moved
  • REMOVE (R): what adversary's checker will be removed.

The system is designed to allow whichever configuration of the three decisions. In the image is depicted the system workflow with a TFR configuration.

 

Training and Testing results

NNMM has demonstrated to be able to learn to play by the game rules without having knowledge about them.

The configurations of the system has been trained (TFR, FTR and RFT) on the Matches Dataset and successively tested on the same dataset and on the State Dataset. Both dataset are available here: Nine Men's Morris Good Moves Dataset.

The accuracy scores on the Matches Dataset have been about 37%.

All the configurations, tested on both dataset, have been able to suggest a legal move (a move that follows the rules of the games) in more than the 99% of cases.

 

Useful  free resurces

 

Nine Men's Morris Good Moves Dataset

Nine Men's Morris Good Moves Dataset federico.chesa… Fri, 03/03/2017 - 12:36

If you use these datasets as part of any work, please cite it as:

F. Chesani, A. Galassi, M. Lippi and P. Mello, "Can Deep Networks Learn to Play by the Rules? A Case Study on Nine Men's Morris", 2018, in IEEE Transactions on Games, Volume 10, Issue 4, DOI: 10.1109/TG.2018.2804039

The accepted version of this work can be found here (bottom of the page)

 

Brief history of these datasets

This data sets are collections of states of the game Nine Men's Morris, which have been created with the purpose to apply machine learning to train softwares to play to the game, and to test their performances.

  • The Good Moves Dataset (also called Matches Dataset) contains couples state-move and can be used for train systems.
  • The State Dataset contains only game states and can be used for testing purposes.

These datasets have been created by Andrea Galassi, as part of his master thesis in Computer Science Engineering ("Ingegneria Informatica", in italian) and as part of a successive work.
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.

 

Good Moves Dataset (Matches Dataset)

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/she 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.

 

Reachable States Dataset

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. It has been generated exploring the space of the game states applying random choices from a reachable configurations.

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

 

Data format

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.

 

 

NNMM: Neural Nine Men's Morris

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% of cases the chosen move is legal)
  • The system has an accuracy of the whole move of about 37%

 

For more information about neural networks, NNMM and its testing, see Neural Nine Men's Morris.

 

Useful free resurces