IL MULINO

Nine Men's Morris Game

By Biagio Miceli Jr.

Columbia University, Spring 2006
Artificial Intelligence (CSW4701)
Professor S. Stolfo
Project #3
E-mail: bm2227@columbia.edu

Mulino is the word for the classic Nine Men's Morris game in Italian. It also means "Mill", which is a common name for the game in English as well. According to the Free Dictionary, a mill is [roughly] defined as:

mill 1 [mil]
n.
    1. A program equipped with machinery for grinding Computer Science students into flour or meal.
    2. A device or mechanism that grinds AI students.

In order words, the purpose of The Mill is to beat the pants off the other students in the Nine Men's Morris tournament. If properly built, The Mill should also produce a tasty substance known as "college credits," as well as the biproduct called "personal gratification." *g*

Project Deliverables

The following deliverables have been handed in as part of the project. Please see the text that follows for full explanation

mulino1.0-src.zip 58 kb Source-only distribution.
mulino1.0-project.zip 1,294 kb Full project, including Eclipse project file.
mulino1.0-bin.jar 433 kb Binary distribution.
mulino1.0-doc.zip 354 kb Mulino API Documentation, also viewable online here.

Running the Binary Release

Written entirely in Java 2 Standard Edition 5.0, this game may be run on any platform for which the J2SE Runtime Environment (JRE) 5.0 is implemented. The J2SE Development Kit (JDK) 5.0 may also be used for running the application, but the JRE is smaller and may already be installed on the machine running the game. Both may be downloaded here. Please ensure that the correct version is being used. JDK/JRE 1.5 is synonymous with 5.0.

Once the JDK or JRE is installed, there are two ways to run the binary release:

  1. Double-click the .jar file. This will only work if the file associations were properly set when the JRE was installed
    or
  2. From a command line, with the Java bin directory in your PATH, run the following command:
    java -jar mulino1.0-bin.jar

The user will be prompted for who will play each player (computer or human), their colors (black or white), and the move time limit in seconds. Do not click cancel when prompted for the time limit, as that feature has not yet been implemented.

The game will begin with the player chosen as "Player 1". The top area of the window shows prompts for the current move and status, as well as the last player's move. This can be used to quickly see the computer's last move during the tournament. To the right of the window is a history of moves in this game. Moves may be entered in the textbox below the history list by entering the move and either pressing enter or clicking the "Go!" button. Moves may also be made by clicking or dragging pieces on the game board. Moves entered in the textbox should be entered as column-row coordinates, in the format indicated by the project instructions. Optionally, capture moves may be entered separately from the slide/place/jump move (for example, A1-D1,G7 is equivalent to entering A1-D1 then G7 separately).

Building and Debugging

While the JRE may be used to execute the runtime JAR file, the JDK is required for building and debugging the code. It can also be downloaded here.

I highly recommend Eclipse IDE 3.1 for viewing and navigating the code, although it is not required for running the binary version of Mulino. The current release of Eclipse for Java development can be downloaded here. Once installed, the extracted project may be imported into the Eclispe workspace through File-->Import and selecting "Import existing project into workspace".

Packages and classes have been documented using comments in Javadoc format. To view the API documentation for the application, complete with descriptions of each package and class, click here. In addition, names have been selected to make the code be as self-descriptive as possible, and may also be viewed as part of the documentation.

Debug and informational logs can be configured through file log4j.properties in the src directory. By replacing the word "info" with "debug", "warn" or "error", the logging level may be changed. See comments in this file for details on how to enable/disable logging.

Software Architecture

The application is divided into three main subsystems and respective abstract implementations:

The Mulino Game Model
The classes and packages under com.belasius.mulino.model embody the concepts and rules of the game Nine Men's Morris. This includes the concept of a board, the pieces, game rules, and an API through which any implementation of a Player interface can interact with the game. Most importantly, this package encodes the representation of the game board as a bitboard; in this case, two 24-bit integers. Using a carefully planned bitboard encoding allows board manipulations, such as modification, checking and transformation, to be achieved in just a few instructions.
The Graphical User Interface
The main panel, board, pieces and game control components are defined in package com.belasius.mulino.gui and below. The only exception is the main application class, which is in the root of com.belasius.mulino. The HumanPlayer class provides an implementation of a Player which can interact wth the game model. These classes also provide drag-and-drop support for pieces, graphical presentation of game events, and other user interface functionality.
The Artificial Intelligence Agent
The game's AI engine employs a variety of techniques. See below for a brief list and descriptions of each.

AI Engine

The AI engine makes use of the following techniques to achieve the best results:

Alpha-beta minimax search
A generic implementation of the algorithm is provided in the package com.belasius.ai, and connected to the game model through implementation in com.belasius.mulino.agent.
Iterative deepening with time cutoff
Once the Game requests a move from the ComputerPlayer, it initiates an iterative deepening alpha-beta minimax search on a separate thread. Once to time limit elapses, the search is interrupted, and the result of the last completed search is returned.
Multi-threaded idle-time searching
The agent class ComputerPlayer provides an implementation of the Player interface which, while waiting for the other player to respond, searches for best possible moves for each possible opponent move. Once the opponent moves, other moves are discarded, and search continues for the allowed time limit starting from the last completed search depth. This allows the agent to search more deeply, while still responding within the required time limit.
Board equivalence classes
It was observed that the game board may be rotated, flipped, or turned inside-out without changing the relative positions of the game pieces. Combined with a carefully chosen board encoding, conceptually equivalent board configurations were elimated from the search space, reducing the number of possible boards by a factor of SIXTEEN! The bitboard encoding chosen allowed this to be done using basic bit manipulations such as rotation and shifting.
Transposition table with LRU cache
A transposition table built on a third-party "least-recently used" cache elimates the need to reevaluate repeated games states while searching. If a move is found during the search that is equivalent to one that was recently evaluated or expanded, its previous score is used, eliminating the need to reevalute that move. The cache is reset on each new search (including various iterations of iterative deepening). During any given search, it can hold a maximum of 30,000 nodes, with older nodes being removed first.
Game-playing strategies
Game-playing strategies were taken from numerous sources, as well as from personal observation. Given more time, however, these strategies could be greatly improved.

The Tournament

Mulino has been tested on Windows XP only, so please be sure it operates correctly on your platform before running in the tournament. It should run fine on other platforms, so please use the fastest system available, provided the game works correctly!

Instructions for running and playing the game are specified in the "Running the Binary Release" section above.

WARNING: Some features not required for Project #3 were only partially implemented and may cause problems if used. In particular, do NOT use the "New Game" feature before the end of the game! It only works after the game has finished, or when playing "Human vs. Human" mode. To abort a game and start over, please close and reopen the application. Also, the "Take Back Last Move" feature may work, but there are still a few bugs hiding there, so please avoid using it during the tournament!

I wish to extend my gratitude to whoever will represent me in the tournament. After all the work that went into this project, I wish I could be present! I'm currently living in Rome, Italy, and it would be difficult to be there in person... so I thank you for filling in for me! Please email me and let me know how it went!

Acknowledgements

The following additional components or elements were used which were not created by the author of this program, but are used with implicit or explicit permission from the authors: