6.37 MIT IEEE/ACM Programming Competition IAP 2001 Due: See Schedule

Contents:

Introduction

Your assignment will be to write a program that plays Konane. Konane is an ancient Hawaiian board-game akin to checkers. It is played on a rectangular board with tokens of two colours placed in a checker-board pattern. Players alternate moving their pieces, jumping over and removing their opponents pieces until one player is left without any valid moves.

Game Description

This section gives a description of the rules of Konane as it will be played in this competition. The game is a variant of Ancient Konane.

The game is played on a rectangular board, which is divided into a grid of squares (like a chessboard). The number of squares on the board will be varied through the competition, but will consist of at least 100 squares arranged in a 10 x 10 pattern. Board of dimensions odd x odd are disallowed.Tokens of two colours (white and black, for simplicity) are arranged on the board in a checker-board pattern with white at top left. For example, a 11 x 12 board will contain 66 white tokens and 66 black tokens.

Each player is randomly associated with a colour at the beginning of a game. Then, the token at the centre and an adjoining token (of the other colour) is removed to make moves possible. In this contest, the row and column number of the removed tokens is determined as follows:
`middle row = (height - 1) / 2`
`middle column 1 = (width - 1) / 2`
`middle column 2 = middle column 1 + 1`
where row and column numbering begins with 0, `height` is the number of rows, and `width` is the number of columns.

In Konane, players alternate making moves, with white beginning first. A valid move consists of a player moving one of his tokens over an adjoining token (of another colour) and placing it in the empty square just beyond and in the same line. The opponent's token is then removed from the board. Every valid move consists of at least one jump. Multiple jumps are allowed in a single move provided that they occur in a straight line; L-shaped jump sequences are not allowed. All tokens that have been jumped over are removed from the board. Players are not allowed to "advance" their tokens as in chess or checkers.

The first player to run out of valid moves loses. This may mean that a player has lost all his tokens, or that the tokens are positioned so no valid move is possible. In this competition, players will also be allotted a certain time to finish the game. A player who runs out of time before his opponent does loses as well.

We suggest that you play the game by hand early on to familiarize yourself with the rules of the game.

Technical Guidelines

Development Tools

The programming contest will be conducted entirely in the Java language. Teams are free to use any development platform, but their solutions will be expected to compile and run with the latest Java Development Kit (JDK) and Java Runtime Enviroment (JRE) on Athena (v1.3.0); specifically, we will be using IBM's high-performance Java compiler called jikes with Sun's 1.3 runtime libraries located in `>jdkpath</jre/lib/rt.jar` to compile contest solutions. All solutions that compile using Sun's javac compiler will also compile with jikes, but more quickly and efficiently. More information regarding jikes can be found at http://oss.software.ibm.com/developerworks/opensource/jikes/project. We are also considering using IBM's JVM on Linux for the tournament, pending more thorough testing. None of these decisions, however, will affect your current development with Sun tools.

Also, the cksum utility in GNU textutils will be used to calculate checksums of each team's source code. Hence, it is recommended that contestants use Athena workstations for development if possible. To use JDK 1.3.0 on Athena instead of the default 1.1.7, type the following at the shell prompt:

```athena% add java athena% setenv PATH /mit/java_v1.3.0/bin:\$PATH```

To use the jikes compiler, type the following at the shell prompt:

`athena% add jikes`

and add the following to your classpath:

`/mit/java_v1.3.0/jre/rt.jar`

The contest organizers have worked with Java on Linux, Solaris, and Microsoft Windows. Sun's JDK and JRE can be downloaded for Windows and Solaris from http://java.sun.com. The IBM's Sun-certified JDK 1.3 is available for Linux at http://www.ibm.com/java/jdk/linux130/index.html.

The source for textutils (which contains cksum), and other GNU tools can be downloaded from ftp://aeneas.mit.edu in the pub/gnu directory and compiled in a POSIX-compliant environment. In Microsoft operating systems, Robert Ragno's port of cksum to Win32 is available from http://web.mit.edu/ieee/iap/www/cksum.exe. If you prefer to work in a POSIX-compliant environment within Windows, including standard GNU tools like make, cvs, and cksum, we recommend the free Cygwin environment from Redhat at http://sources.redhat.com/cygwin/.

Package Overview

Teams will be provided with a downloadable Java archive file, konane.jar, which contains the konaneCommon package:

 Konane Container class of constants used in all game packages. White and black tokens are represented by public static final byte fields. BoardGrid Class representing the Konane gameboard. Contains a rectangular array of token values and methods to validate positions, sides, moves, to return valid moves in the board, and to execute moves that will change the state of the board. Move Class representing a move. It consists of a comment string, an initial position (x,y) and a final position (x,y). Player An abstract class. It is the Java object that represents a team and plays for them.

Task Overview

Every submission must contain a class named `Player` that extends `konaneCommon.Player`. The constructor for the `Player` class is the empty constructor by default and accepts no parameters. If the `Player` class needs to perform initialization code, it should override the constructor but should still accept zero parameters. The task of a team is to override the `makeMove` method of `konaneCommon.Player`   to return a valid `Move` given two parameters: an initial `BoardGrid` and a time limit in milliseconds.

A Konane game is simulated by two `Player` objects that alternate making `Moves` on a `BoardGrid`. Play continues until one `Player` object either runs out of moves, runs out of time, or forfeits. A Player may forfeit by returning a `Move` object with the comment value set to `**FORFEIT**`. The return of an illegal move will be interpreted as a programming error and will cause an immediate forfeit of the game.

The submission requirements are listed below and are elaborated in the Detailed Requirements and in readme.txt in the Java archive.

1. The team submission should define a package with a unique name of the form `<teamname>`_xx where `<teamname>` is any string of 22 or less characters chosen from [a-z,A-z,0-9] and `xx` is the number assigned to each team upon registration. Each team's contact person should e-mail their package name to the contest organizers at 6370@mit.edu as soon as possible.
2. The team package should include a class named Player that extends konaneCommon.Player.
3. The Player class should override the Player.makeMove method, which is the entry point into team-written code.
4. The team-written source code should not define any new threads of execution.
5. The team-written source code should not interface with non-Java code, compiled native libraries, precompiled Java bytecode, or any Java code not written by the team explicitly for this particular contest, with the exception of the `BoardGrid`, `Move`, `Konane`, and `Player` classes in the `konaneCommon package`, and the standard runtime classes in jre/lib/rt.jar of Sun's JDK 1.3. Use of Java's Reflection classes, use of Class methods to access classes not written by the team, file system operations, or network operations is not allowed.
6. Team submissions should consist of team-written source code in a jar file named after the team and a checksum of the source files. Teams should send their jar file and checksum as e-mail attachment to 6370@mit.edu by the contest deadlines listed earlier in this document.

Schedule

Timeline

You will work in teams of three. All members of a team have to be currently registered MIT students. Incomplete teams may add members with the permission of the organizers. Teams are expected to have familiarized themselves with the rules of this competition.
Stage Date Location Comments
Specification Release Jan 7th online Specifications released.
Guest Lecture Jan 17th 4-370 Prof. Michael Ernst talks about Konane.
Preliminary Rounds Jan 21st private Benchmark teams for latter half of contest.
Lab Hours Jan 22nd-27th 34-501 Reserved lab space to test platform compliance.
Code Submission Jan 29th e-mail Complete source code turned in.
Qualifying Rounds Jan 27th-29th TBA Identifying top 8 qualifiers for the live contest.
Live Contest Jan 30th 26-100 Live contest for top 8 teams.

Guest Lecture (January 17th)

Prof. Michael Ernst will give a lecture on Combinatorial Game Theory based on his previous work with Konane. The lecture will be from 1-2 pm in room 4-370. A listing of Prof. Ernst's publications can be found at http://sdg.lcs.mit.edu/~mernst/pubs/.

Criteria for acceptance/elimination of submissions at the preliminary rounds will be refined at this date.

Preliminary Rounds (January 21st)

Teams will turn in submissions which will be privately played against one another. All submissions will be required to be fundamentally functional by this date, ie. they are required not to return an illegal move over the course of the test tournament. Seedings for the final phase of the competition will be determined at this stage. The best two submissions at this stage will be obfuscated, compiled and made available to all teams to benchmark against.

The submission deadline is 9 AM, 21st January 2001. The technical details of submission are to be found in Section 4 of the detailed requirements.

The top two submissions will also receive byes in the elimination rounds. Submissions that are invalid and/or do not demonstrate adequate progress at this stage may be eliminated from the competition at the discretion of the organizers.

Qualifying Rounds (January 29th)

Submissions will be compiled, and then played against one another automatically. Contestants are free to inspect the process. We will begin a process of elimination of teams to reduce the field to eight teams for the final live contest on January 30th.

The submission deadline is 10 AM, 29th January 2001. The technical details of submission are to be found in Section 4 of the detailed requirements.

The format of the elimination rounds is still being worked on. It will most probably involve double elimination. This information will be posted here as soon as it is decided.

What We Give You

Each team is provided with this document, which is a printable record of the rules of Konane, the submission requirements, the contest schedule and other essential information. Teams are also provided with a downloadable jar file, konane.jar which contains the following.

• A common package of Konane classes (`konaneCommon`), along with Javadoc-generated HTML documentation, that should be used in writing a submission.
• A trivial reference implementation to serve as an example and against which team submissions can be tested.
• A test program to play two implementations against each other.

Frequently Asked Questions

 Q) Why is the reference player so slow on Athena JDK 1.3? A) This problem was due to the busywait loop used in Simulator and the combination of the Solaris 1.3 JVM and Solaris's lack of preemptive multitasking. The `Simulator` (and `ClientThread`) now both use a wait/ notifyAll mechanism. Thanks to Chris Peikert for pointing this out. Q) What hardware will be used to run my Player? A) Your players will be run within client JVMs on the Dell Linux machines found in many Athena clusters. You may use these machines to test your players under tournament conditions. Q) What size will the board be during the tournament? A) As described in the online specs, the board size will be a randomly chosen rectangle with a width from 10 to 15 columns and a height of 10 to 15 rows, inclusive. Boards with an odd number of squares are disallowed. You may choose to write your algorithm to scale well for any board size, or you may choose to optimize it for certain board sizes. Currently we are going to vary the board size from game to game during the tournament. Q) How long will each `Player`'s time limit be during the tournament? A) The time limit will be on the order of 2-5 minutes, or about 222222 milliseconds. Q) Will my `Player` be able to save state, and if so, how much? A) Yes, each Player is loaded and instantiated at the beginning of each game and remains persistent throughout the game. The JVM hosting your `Player` will be running with a limited heap size on the order of 32MB; all your state must be handled in RAM, as operations on the local file system or over a network will not be allowed. Q) When will the source code for the game engine be released? A) The full source for the game engine and graphics routines will probably not be ready for public release until after the tournament is over. The relevant classes of the game engine (dealing with player loading and timing) are currently being released in konane.jar.

Helplines

If you have a technical question about these specifications, first see if your question can be answered by the Detailed Requirements in Appendix 1. Also check the 6.370 contest website for the most recent revision of the specifications. If you have an administrative question about the contest, go to the website directly: http://web.mit.edu/ieee/iap/www/

If your questions are still unanswered, e-mail the contest organizers at 6370@mit.edu. Please remember that 6.370 is currently completely student run, so we might not have all the resources to answer your questions. Also, the contest organizers assume you have a basic knowledge of Java and/or have reference materials to consult.

If you have a question about the Java programming language, you might want to try Sun's Java forums and tutorials at: http://java.sun.com

There is now an Athena mailing list, 6370-discuss@mit.edu, for both teams and organizers to discuss technical issues and answer questions about the contest. We hope that contestants will use these to involve themselves with the technical support process.

Appendix 1: Detailed Requirements

The technical requirements and instructions for submission are given in readme.txt. This file is also included in the downloadable Java archive, konane.jar.

Appendix 2: Konane.jar

 REVISION 7, 25 January 2001 NOTE: Downloading with Netscape in Windows mangles the jar file. If you are using Windows, use another browser or secure file transfer method to retrieve the konane.jar. konane.jar, 111 KB Contains the compiled konaneCommon class files, konaneCommon documentation, reference implementation, a test program, and the technical readme file, which also contains a log of changes made to the jar file. You can extract the jar file by typing the following at your shell prompt: `jar xvf konane.jar`.

Change Log

This section will detail the changes made during revisions of this handout. You may use the version number at the bottom of your hardcopy to determine what has changed since you printed this handout.
 Revision 1.01 Initial release. Revision 1.1 Corrected size of konane.jar file. Removed link to zip archive. Changed use of Athena JDK to v1.3.0 from v1.1.7 in `Development Tools`. Revision 1.2 Added instructions to add the java locker before adding the Athena 1.3.0 JDK to PATH in `Development Tools`. Added link to Robert Ragno's port of cksum to Win32 in `Development Tools`. Added more specific formula for calculating the row and column of the removed tokens to `Game Description`. Expanded Restriction #5 in `Detailed Requirements` to forbid use of reflection, class loading, file system operations, and network operations. Added `Frequently Asked Questions` section. Updated size of Rev. 3 konane.jar in `Appendix 2`. Revision 1.3 Added time and location of guest lecture. Added hyperlinks to change log. Revision 1.4 Added reference to 6370-discuss mailing list to Helplines. Updated size of Rev. 4 konane.jar in Appendix 2. Revision 1.5 Added link to PDF lecture slides of guest lecture. Released submission deadline for preliminary rounds. Revision 1.6 Clarified Restriction #5 on interfacing with non-team-written classes in Task Overview Revision 1.7 Compiler? But I...—updated compilers to be used in the tournament in Development Tools. Updated FAQ to include details about tournament hardware, time limits, board sizes, and the simulator bug. Updated size of Rev. 6 konane.jar in Appendix 2. Revision 1.8 Changed valid board sizes. Augmented submission format instructions. Extended final submission deadline.

rev 1.8 2001/01/25 16:00:00 arjunrn