Homework #1 - 6x6 Lines of Action

This assignment is now over. Check out the game driver (that has all the working submitted agents and the scoreboard out. Cheers!

Lines of Action was invented by Claude Soucie, and got widely spread when Sid Sackson included it in his book A Gamut of Games. It was originally formulated for an 8x8 chess board, but we are going to play it on a 6x6 board to limit the complexity.

In terms of our terminology for the agent environment, Lines of Action 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 Lines of Action -- 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 Lines of Action. 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).

Rules of the Game

We will be using the following rules for this homework. There are several different rulesets for Lines of Action out there, so please read our rules carefully!

Initial Board Setup

Each player -- black and white -- has 8 checkers. The black checkers occupy the topmost and bottommost rows, while the white checkers occupy the leftmost and rightmost rows of the board. The starting position is shown below:

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

Objective

The main objective of this game is to achieve a winning position. We say that a player has a winning position when all his checkers are connected either horizontally, vertically or diagonally. For example, the following position is a winning position for black:

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

If a player has only one checker left, then that player has a winning position. Also, if a move results in both players having winning positions, then the player that made the move is considered to have won. However, if a move causes the opponent player to have a winning position, then the opponent wins.

In the rare event that a player has no legal moves without having a winning position, he loses.

Moves

In this game, players alternate moves, with black playing as the first player. On each turn, a player moves a checker of his color either horizontally, vertically or diagonally. The checker moves as many squares as the number of checkers (of any color) in the line of movement. A checker may jump over other friendly checkers, but not over enemy checkers. It may be moved to a square containing an enemy checker, resulting in the removal of that enemy checker. Consider the position below:

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

For example, black can move his checker at B2 two spaces horizontally to D2, since there are two checkers in that row. However, black is not allowed to move the B2 checker to B6, since it would jump over white checkers. On the other hand, black can choose to move the B2 checker to E5, jumping over a friendly checker and capturing the white stone in E5, resulting in the winning position as shown in the previous diagram.

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 NuaH agent: a lazy player that makes random moves

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 Breakthrough game player for ideas - be creative!

* nuah. [adjective] Hokkien for feeble; weak; deficient in character or intelligence; but usually used to describe a lack in energy or force or effect.

Move request

The move request will be a command move, followed a single integer on the next line representing the number of turns elapsed, followed by another integer on the next line representing the size of the board (always "6", meaning 6x6), followed by six lines with six characters each, representing the board. The starting state is thus represented by the input:

move
1
6
.XXXX.
O....O
O....O
O....O
O....O
.XXXX.

Empty spaces are represented by the dot character. Black pieces are represented by X, and white pieces are represented by O.

Given a move request, your agent should output a move pair in CAPITALS, using the coordinate system shown in the diagrams. For example, moving the black checker from D1 to B3 would be output as a single line with 4 characters:

D1B3

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 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 5.10), when the system's load is light.

Submission Formatting

For me 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 matrics with student names.
Any source code: We 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-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: 2007 October 1, 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 Lines of Action against the random agent in the sample java code, here at the Lines of Action 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 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.
BoardSpace has a server to link human players together to play the 8x8 version via the web. On this server, you may also choose to play against a robot.
Little Golem has a server to link human players together to play the 8x8 version via the web.
Wikipedia has a definition of Lines of Action in its pages.

A total of 61 different hosts have accessed this document in the last 197 days; your host, 3.137.175.166, has accessed it 1 times.

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

Yee Fan Tan <tanyeefa@comp.nus.edu.sg> Tue Aug 22 00:00:00 2007 | Version: 1.0 | Last modified: Tue Aug 22 00:00:00 2007

CS 3243 - Foundations of Artificial Intelligence

Menu