Wed Mar 22 10:02:06 GMT-8 2006 - This assignment is finished. The final scoreboard is now available. You can now play some of the other players in the Breakthrough game driver.

Homework #1 - 6x6 Breakthrough

Breakthrough was the winner of the 2001 8x8 Game Design Competition, sponsored by About.com and Abstract Games Magazine. When Dan Troyka formulated it, it was originally for a 7x7 board. We're going to play it on a 6x6 board to limit the complexity (only slightly though -- does anyone care to compute some approximate savings?)

In terms of our terminology for the agent environment, Breakthrough 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 Breakthrough -- 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 Breakthrough. 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. Certaintly 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 alloted 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 basic sample class 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).

Breakthrough and Technical Description

Initial Board Setup / Input

Each player -- black and white -- has 12 counters occupying two rows on opposite sides of the board (exactly as Chess would be set up on a 6x6 board).

6
5
4
3
2
1
	A	B	C	D	E	F

Your program should run without any command-line arguments and should respond accordingly to two types of input: move requests and identify requests.

The board will be represented as a grid that you will have to parse as input. The sample code will show you how to read this data structure into memory for your class to use. In actuality, your program will receive the following as input: the command move, followed a single integer on the next line representing the number of turns elapsed, followed by a line with the dimensions of the board (always "6 6"), followed by six lines with six characters each, representing the board. The starting state is thus represented by the input:

move
1
6 6
bbbbbb
bbbbbb
------
------
wwwwww
wwwwww

Blank spaces are represented by the dash character (not an underscore). Pawns are always represented by lowercase ASCII letters. Your program can also receive the command identify as a single line, which should output the name that you have given your agent: a string (up to 80 ASCII printable characters in length, with no carriage returns). A identify request could be answered by:

Min's breakthrough agent v1.0 - I honk for game players

but you can be more creative than that. The identify string will be used to identify agents with their rankings against other players. See last year's taglines for their Hex game player for ideas - be creative!

Rules / Output

Win by moving one piece to the opposite side. Pieces move one space forward or diagonally forward, and capture diagonally forward. In the diagram below, the pawn at b4 can go to any of the three spaces; the white pawn at e1 can either choose to move by going diagonally right or capture by going diagonally left. It cannot move or capture by moving forward; its forward move is blocked by the black pawn.

6
5
4
3
2
1
	A	B	C	D	E	F

Your program will always play white, whose objective is to move a white pawn to row 6. Given a move request, your agent should output a move pair in CAPITALS, using the coordinate system shown in the figure. For example, moving the lower right white pawn to capture the black pawn to its forward left would be output as a single line with 4 characters:

E1D2

meaning to move the pawn at e1 (must be white's) to d2. 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 competitin 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 3 real-time seconds to make a move. If your program does not output a coordinate within 3 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 Solaris 4), when the system's load is light.

Submission Formatting

For me to grade this assignment in a timely manner, I 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., U00000X-U11111Y) 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-U00000X.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 (I 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 I won't associate matrics with student names.
Any source code: I will be reading your code, so please do me a favor and format it nicely.
A makefile or build.xml that will build an executable named agent-<matric number>, (e.g., agent-U00000X) 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. I 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 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: 16 Feb 06, 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 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 Breakthrough against the random agent in the sample java code, here at the Breakthrough Game Driver. Later on, I 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 3 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 Geek has a more complete description and a couple of reviews on this game.
Little Golem has a server to link human players together to play this via the web (but the 8x8 version, as of November 2005)
Wikipedia has a definition of Breakthrough in its pages.

A total of 67 different hosts have accessed this document in the last 187 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 7 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.

Min-Yen Kan <kanmy@comp.nus.edu.sg> Mon Jan 23 23:06:06 2006 | Version: 1.0 | Last modified: Wed Mar 22 10:05:35 2006

CS 3243 - Foundations of Artificial Intelligence

Menu