Introduction

A computer Chinese Checkers Competition will be held during the 2004 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. Both contests are held this year on 2004-06-12[Sat]. The venues are as follows:

Event	Time	Location
Scholastic Programming Contest	1030-1745	Room 702, Oen Hall Building East Wing (OEE), The Hong Kong Baptist University.
Chinese Checkers Competition	1330-1730	Room 802, Oen Hall Building West Wing (OEW), The Hong Kong Baptist University.

The time for the Chinese Checkers Competition is from 1:30pm to 5:30pm. All winners are invited to the dinner and award presentation ceremony at 7:00pm at the Renfrew Seafood Restaurant, 3/F, David C. Lam Building, 34, Renfrew Road, Kowloon Tong.

In this competition, 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.

How to play the game?

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 equidistant 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.

                       121

                     119 120

                   116 117 118

                 112 113 114 115

99 100 101 102 103 104 105 106 107 108 109 110 111

  87  88  89  90  91  92  93  94  95  96  97  98

    76  77  78  79  80  81  82  83  84  85  86

      66  67  68  69  70  71  72  73  74  75

        57  58  59  60  61  62  63  64  65

      47  48  49  50  51  52  53  54  55  56

    36  37  38  39  40  41  42  43  44  45  46

  24  25  26  27  28  29  30  31  32  33  34  35

11  12  13  14  15  16  17  18  19  20  21  22  23

                  7   8   9   10

                    4   5   6

                      2   3

                        1
          

Objectives and Rules

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 2GHz Pentium 4.

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 obtain 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 Interface Package

The sources for the mediator is available in the resources folder. To use them, use tar xvzf ccjudge.tar.gz and run make in the directory ccjudge. To play a game between two players, execute the command

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.

Contact information

Chinese Checkers Competition Chair: YIP Chi Lap [Beta], Department of Computer Science and Information Systems, The University of Hong Kong. <clyip@csis.hku.hk>

For registration information, bug reports, questions, and suggestions, please contact clyip@csis.hku.hk.