6.370 | MIT IEEE/ACM Programming Competition IAP 2001 Due: See Schedule |
Contents:
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.
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/.
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. |
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.
<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.
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.
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 | 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. |
Criteria for acceptance/elimination of submissions at the preliminary rounds will be refined at this date.
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.
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.
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.
konaneCommon
),
along with Javadoc-generated HTML documentation, that should be used
in writing a submission.
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. |
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.
The technical requirements and instructions for submission are given in readme.txt. This file is also included in the downloadable Java archive, 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: |
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