Homework #1 - Ataxx Reloaded

This homework assignment is over. See the agent vs. human player framework (has a known bug) as well as the scoreboard (may be in progress of being updated).

Not too long ago, in 1988, Dave Crummack and Craig Galley invented a new game that was supposed to be more playable on a computer than on a board. A bit inspired by Reversi/Othello, this game a similar "infection" of nearby pieces (Min's comment: perhaps one of the earlier computer viruses?). Over the next few years, the game found its limelight, being featured both as an arcade game but also as a PC minigame-within-a-game (7th guest).

In terms of our terminology for the agent environment, Ataxx is a fully observable, strategic, deterministic game. The game always results in a win for one of the two players. So what are you going to do? You are going to play the game of Ataxx -- not as yourself but through the surrogate of your program.

Stumped? How exactly do you code an AI to play this game? Well, like every thing else in this course, we code an agent. An agent takes sensory input and reasons about it, and then outputs an action at each time step. You thus need to create a program that can read in a representation of the board (that's the input) and output a legal move in Ataxx. You then need a utility function to evaluate how good a board is to your agent. The better your evaluation function, the better your agent will be at picking good moves. You need to put some thought into the structure of your utility function.

Aside from the utility function, you also need to decide a strategy for exploring the search space. Certainly you can use minimax search but you may want to decide whether you want to use alpha-beta pruning on top of this. It depends on whether your agent's architecture will allow it to make a move within the allotted time (see below).

You can do this assignment in Java, C++, or the language of your choice. If you use Java, you can extend the provided basic sample program (see below) to build your customized game player. The only condition is that your game player must obey the standard input and output to allow the system to enter it in our round-robin competition. Your program will be run multiple times, as it will be invoked once for every turn of the game. Any program that requires an interpreter (e.g., Java) to load your program or script will need a simple shell script to do the proper invocation (see below).

How to play the Game

We will be using the following rules for this homework. These are intentionally different from the rulesets that exist for Ataxx out there, so please read our rules carefully! Given that the game is not entirely the original Ataxx, Jun Ping has termed it "Ataxx Reloaded".

Initial Board Setup

Each player -- black and white -- starts off with 2 pieces. The black pieces occupy the top-left and bottom-right corners and the white ones occupy the top-right and bottom-left corners. The starting position is shown below:

	0	1	2	3	4	5	6
0
1
2
3
4
5
6

Objective

The objective of this game is to end the game with more pieces on the board. This is achieved by filling up more spaces on the board than your opponent, once the game has ended. The game ends if 1) the board is filled; 2) you or your opponent do not have any pieces left; or 3) the game reaches its 100th turn (a turn is defined as a pair of moves from both players). If a player has no possible valid moves or makes an invalid move, the move is considered forfeited. For example, in the board below, white wins as black has fewer pieces when the game is finished. (Updated Wednesday, September 22, 2010 10:32:25 PM SGT) A draw is only possible if on the end of the 100th turn, both players have the same number of pieces.

	0	1	2	3	4	5	6
0
1
2
3
4
5
6

Ataxx Reloaded Moves

In the original Ataxx game, players alternate moves, with black playing as the first player. On each turn, a player moves a piece of his color either horizontally, vertically or diagonally 1 or 2 squares away, to a blank square. If the piece is moved one square, the piece replicates, leaving a piece new piece of its own color behind. If moved two squares, the piece jumps, vacating its original location. When a piece moves to its destination, it converts all neighboring pieces to its own color (horizontally, vertically as well as diagonally).

In our Ataxx reloaded, the possible jump moves have been modified. You can only jump horizonally, vertically or diagonally two squares (L-shaped Western chess knight moves are disallowed). Furthermore, jumps of three squares vertically and horizontally are allowed.

	0	1	2	3	4	5	6			0	1	2	3	4	5	6			0	1	2	3	4	5	6
0									0									0
1									1									1
2									2									2
3								Move:	3								Infect:	3
4								(4,5 to 4,2)	4									4
5									5									5
6									6									6

For example, black can move his piece at 4,5 two spaces vertically to 4,2, which is a jumping move of 3. Doing so vacates the original position at 4,5 but ends up infecting 4 additional white pieces for overall shift of +8 pieces, from a running score of 10-14 to 14-10.

Program Specification

Your program should run without any command-line arguments. All inputs will be given on the standard input, and all outputs should be written to the standard output. The input is either an identify request or a move request, and your program should respond accordingly. Your program will always play black.

Identify request

The identify request will be a command identify on a single line:

identify

For this command, your program should output the name that you have given your agent: a non-empty string (up to 80 ASCII printable characters in length, with no carriage returns). If you include a URL in the printable name, we will try to link to the specified web page in the game logs. A possible response could be:

The Four-Leaf Clover

but you can be more creative than that. The identify string will be used to identify agents with their rankings against other players. See taglines for the Breakthrough game players created by previous 3243 students for ideas - be creative!

Move request

The move request will be a command move, followed a single integer on the next line representing the ~~number of turns elapsed~~ (Updated Wednesday, September 22, 2010 10:14:32 PM SGT) current move number, followed by another integer on the next line representing the size of the board (always "7", meaning 7x7), followed by seven lines with fourteen characters each, representing the board. The starting state is thus represented by the input:

move
1
7
1:0:0:0:0:0:2:
0:0:0:0:0:0:0:
0:0:0:0:0:0:0:
0:0:0:0:0:0:0:
0:0:0:0:0:0:0:
0:0:0:0:0:0:0:
2:0:0:0:0:0:1:

Empty spaces are represented by 0s. Black pieces are represented by 1s, and white pieces are represented by 2s.

Given a move request, your agent should output a move pair using the (x-y) coordinate system shown in the board examples. For example, moving the black piece from 4,5 to 4,2 would be output as a single line with 8 characters:

4:5:4:2:

Your program should always output a legal move. Moves will be validated by the game playing framework and any illegal moves will result in a decrease in the score of your assignment. If your player makes an illegal move, the competition framework will choose a random move on your behalf. Your agent must always make a move; it is not allowed to skip moves.

Your program may not take more than 5 real-time seconds to make a move. If your program does not output a coordinate within 5 seconds, it will be terminated and your agent will be deemed to have forfeited its move. We will be running the agents on sunfire (SunOS 5.10), when the system's load is light. Note that the computational throughput of sunfire is underwhelming; if you develop your assignment on your own computer (laptop or desktop), don't be surprised that your agent is not able to evaluate as many moves on sunfire as on your own computer.

Submission Formatting

For us to grade this assignment in a timely manner, we need you to adhere strictly to the following submission guidelines. They will help me grade the assignment in an appropriate manner. You will be penalized if you do not follow these instructions. Your matric number in all of the following statements should not have any spaces and any letters should be in CAPITALS. If you are doing this assignment as a team of two, your matric numbers should be strung together with a dash (-) separating the two (e.g., U000000X-U111111Y) in all of the formatting comments below. You are to turn in the following files:

A plain text documentation file README-<matric number>.txt (e.g., README-U000000X.txt): this is a text only file that describes any information you want me to know about your submission. You should not include any identifiable information about your assignment (your name, phone number, etc.) except your matric number and email (we need the email to contact you about your grade, please use your u*******@nus.edu.sg address, not your email alias). This is to help you get an objective grade in your assignment, as we won't associate matric numbers with student names.
Any source code: We will be reading your code, so please do us a favor and format it nicely.
A Makefile or build.xml that will build an executable named agent-<matric number>, (e.g., agent-U000000X) from the source code using make or ant. This will have to run directly on sunfire, it is highly suggested that you compile your code on sunfire before turning it in. We will not be responsible for compiler failures.

These files will need to be suitably zipped in a single file called submission-<matric number>.zip. Please use a zip archive and not tar.gz, bzip, rar or cab files. Make sure when the archive unzips that all of the necessary files are found in the current directory (please do not nest your files in internal folders). Upload the resulting zip file to the IVLE workbin by the due date: 2010 September 30, 11:59:59 pm SGT. There absolutely will be no extensions to the deadline of this assignment. Read the late policy if you're not sure about grade penalties for lateness.

Grading Guidelines

The grading criteria for the assignment is:

15% Performance against other players
30% Minimax and/or Alpha-Beta code
45% Evaluation Function
10% Documentation / Instruction following

Disclaimer: percentage weights may vary without prior notice.

Miscellaneous Links

Sample java code for your agent is available here: submission-U000000X.zip (requires Java 1.5 or later). You should unpack this file (even if you are not writing your agent in java), run the program and check the outputs and formatting.
You can now play Ataxx Reloaded against the random agent in the sample java code, here at the Ataxx Reloaded game driver. When the submission deadline is over, we will enable your own agents in this framework, so you can play against them.
Timers and interrupts: as your program may run out of time in doing its computation you may want to have a timer or interrupt force your agent to an "urgent" state in order to quickly arrive at a move if the time limit is near.
- In Java: we do this with threads and timers. Go look up these classes and see how they are used.
- In C++: we do this with signals. We set a signal handler to do an urgent move if the execution time draws near. When the program starts we can install this signal handler and program a signal to fire close to the time limit. You can set an SIGALRM signal to fire at 5 seconds.
The basic idea is the same in both languages, although the syntax and naming conventions differ. You can use the IVLE forum to share what knowledge you can glean from the net.
Board Game Geek has a more complete description and a couple of reviews on this game.
Pressibus has a fairly complete description of the game, probably better than Wikipedia, but the links to game demos are out of date.
You can play a hexagonal version of the original Ataxx at both Miniclip as well at the original site at Neave
If you have an iPad, iPhone or an Android phone, there are implemented versions for these platforms (which are fairly recent -- less than a month for the Droid version). Can you code a nicer version? Or at least a smarter one?

Min-Yen Kan <kanmy@comp.nus.edu.sg> Sunday, August 22, 2010 06:55:54 PM SGT | Version: 1.0 | Last modified: Tue Aug 22 00:00:00 2007

CS 3243 - Introduction to Artificial Intelligence

Menu