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.
- A program equipped with machinery for grinding Computer Science students into flour or meal.
- 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*
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.
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:
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).
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.
The application is divided into three main subsystems and respective abstract implementations:
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.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 AI engine makes use of the following techniques to achieve the best results:
com.belasius.ai
, and connected to the game model through implementation
in com.belasius.mulino.agent
.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.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.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!
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: