1997 ACM Hong Kong Chapter Computer Chinese Checkers Competition

Table of Contents
Introduction to Chinese Checkers Competition
How to play the game?
Objective and Rules
The Interface Package

A computer Chinese checkers competition will be held during the 1997 Annual ACM Hong Kong Chapter Scholastic Programming Contest. While teams compete in the programming contest, at another location of the contest site a competition will be held for Chinese checkers playing programs, which are to be written and submitted before contest day.

During each game, two Chinese checkers playing programs, executing as separate processes on personal computers or workstations running Unix, play against each other using a common protocol mediated by the organizer's ``mediator program'' executing as yet another process. This document describes the rules of Chinese checkers and the protocol understood by the mediator program.

Everyone must have played Chinese checkers at one time or another. Specifically, we will adopt for the contest the simpliest version of the game in which the objective is to move all of ones marbles across the board as quickly as possible. Thus the rules are here only for reference purposes and should correspond to everyone's understanding of the game. Note however that we have defined more precisely the criteria for winning, and adopted a time limit for the programs to make its moves, which are intended to make the games more interesting.

The game is played on a six-pointed star-shape board by two players. There are 121 positions on the board and they are numbered from 1 to 121 as shown in Figure 1. At the beginning of a game, each player's ten marbles occupy a triangular area at an opposite side of the board. We call this the home area of a player. The four other triangular areas are called neutral zones. Since the board is embedded in a hexagonal grid, each position on it is generally connected to neighbors in six directions, except when located at the boundary or a corner, in which case the position has 5, 4, or 2 neighbors. At each turn, a player can move any one of his marbles into a neighboring position, provided that such a position exists and is not already occupied by another marble, either belonging to him or his opponent. A marble may also in one move make a sequence of jumps over other marbles, which either belong to the player or his opponent. Each jump must be made according to the following rule. Suppose the marble at A jumps over a marble at B. The former will land at position C, where B is equidistance from A and C, and A, B, and C are colinear. The jump is only allowed if every position on the line AC (inclusive) exists, and none of these are occupied before the jump except A and B. When a marble is moved to an adjacent position, or takes a sequence of jumps, it may not end up in a position in a neutral zone. The intermediate steps of a sequence of jumps, however, may use positions in the neutral zones.

Figure 1: Board positions are numbered 1 to 121. Home area of a player consist of positions 1 to 10; that of its opponent 112 to 121. The neutral zones are the positions 11-14, 24-26, 36-37, 47; 20-23, 33-35, 45-46, 56; 66, 76-77, 87-89, 99-102; and 75, 85-86, 96-98, 109-111.

The objective of the game is to move all of ones marbles into the home area of one's opponent before one's opponent moves all his marbles into one's own home area. A game is considered a draw if player 1 makes the first move of the game, and player 2 moves all his marbles into player 1's home area one move after player 1 moves all his marbles into player 2's home area.

The computers on which the Chinese checkers playing programs will run will be PC compatibles running Linux, with a processor comparable to a 75MHz Pentium.

For simplicity, the Chinese checkers playing programs will simply be referred to as the players and the mediator program as the mediator below.

When a game begins, the mediator starts up each player as a child process. The child processes will subsequently communicate with the mediator by reading from their standard input stream and writing to their standard output stream.

Since these streams are in reality connected to pipes created by the mediator, output must be flushed after each message is written by the C++ I/O manipulator ``flush'' or the C function ``fflush''.

The mediator starts the game by sending a message to each player. The messages sent to the two players are different: one of the two is requested to begin first. An even number of games are played between any two players, giving each a equal number of times to begin.

Each player is given five minutes to make all its moves. Since the players and mediator run on a multiprogrammed operating system, the time used by a player is the time used by its process. The player must not fork any other processes.

The player may decide to spend more time making certain moves and less making others. When a player fails to make all its marble reach its opponent's home area within five minutes, each move thereafter must be made within one second. In other words, the mediator maintains two clocks, one for each player, initialized to zero at the beginning of the game. An any given time, only one of the clocks runs: that of the player who is computing its next move.

As soon as the player makes its move by sending a message to the mediator, its clock stops, the mediator announces its move to its opponent, and its opponent's clock restarts.

Such a clock is different from a real chess clock in that during the time that one player is computing its next move, the other player may not carry out any computation. The mediator ensures this by suspending a player after receiving a move from it and resuming it before sending its opponent's move to it.

To protect against playing programs which simply do not move their marbles out of their home area, after the time alloted to a player expires (5 minutes in the above example), if any of its marbles is left in or is moved into its own home area, the player is considered to have lost.

The 121 positions of the playing board are numbered 1 to 121 from bottom to top, left to right. The two players will have its own perspective of the board, its home area always being numbered 1 to 10. The mediator will perform the necessary translation to maintain consistency in the messages passed between the two players.

A player must maintain information on the current board configuration since no part of the protocol provide this information. It must also ensure that each move it makes is legal because the mediator will consider the player to have lost when an illegal move is received from it. The player can obtained the amount of time it has used by making the system call ``times''. It can also assume that its opponent's move, sent to it by the mediator, is always legal.

Although a move may contain multiple jumps, it can be represented by its starting and ending positions. Note that this does not uniquely identify a single move but this does not matter for all practical purposes. The message sent from the player to the mediator to represent a move is a single text line containing two integers, each in the range [1..127], separated by whitespaces.

The mediator informs a player that it is now the player's turn to move by sending it the move just made by its opponent, in the player's own coordinate system. The format of the message is the same as for the message sent by the players.

The initial message sent from the mediator to each of the two players consists of a single text line. The line will contain the number 1 for the player who is expected to make the first move. The line will contain the number 2 for the player who is expected to make the second move.

The sources for an initial version of the mediator and two versions of the executable of an example of a player are contained in the file cc.tgz. To use them, un-tar the file and execute "make" in the directory "ccjudge". To play a game between two players, execute the command

ccj ../player/player1 ../player/player2

in the directory "ccjudge".

The methods in which the players are invoked and the protocol with which the mediator communicates with the players will not change in future versions of the mediator. Only better display, logging, error checking, etc. will be added to it, and these will be made publicly available when they are ready.

That completes our specification. Please direct any bug report, questions, and suggestions to Dr. Andrew Choi (choi@cs.hku.hk), or Dr. Benjamin Kao (kao@cs.hku.hk).