Feb 99 Prog Challenge
Volume Number: 15
Issue Number: 2
Column Tag: Programmers Challenge
Feb 99 Programmers Challenge
by Bob Boonstra, Westford, MA
Chinese Checkers
For this month's Challenge, I've reached once again into my stash of board games, this
time coming up with one I haven't played in a very long time: Chinese Checkers. The
prototype for the code you should write is:
#if defined(__cplusplus)
typedef struct Position {
long row;
long col;
} Position;
void InitChineseCheckers(
long numPlayers, /* 2..6 */
long gameSize, /* base of home triangle, 3..63, you have
size*(size+1)/2 pieces */
long playerPosition[6], /* 0..5, entries 0..numPlayers-1 are
valid */
long yourIndex /* 0..numPlayers-1, your position is
playerPosition[yourIndex] */
);
void YourMove(
Position *from, /* originating position */
Position *to /* destination position */
);
void OpponentMove(
long opponent, /* index in playerPosition[] of the player making
move */
Position from, /* originating position */
Position to /* destination position */
);
void TermChineseCheckers(void);
#if defined(__cplusplus)
}
#endif
Chinese checkers is played on a six-pointed star shaped board by 2 to 6 players. The
board can be viewed as six equilateral triangles attached to a hexagon. Each Position on
the board is connected to six adjacent positions (ignoring boundary conditions), one
each to the left, right, upper left, upper right, lower left, and lower right. At the
beginning of a game, each player's pieces occupy one of the six triangular areas,
referred to as that player's home position. The triangular area opposite the player's
home position is called that player's goal position. The triangular areas that are not
part of the home or goal positions are called neutral zones for that player. The
objective of the game is to move your pieces from your home to your goal before any
other player does the same.
Standard Chinese Checker boards use a board where each player has 10 pieces,
initially placed in a home triangle with 4 positions at its base. We'll refer to the base
of the home triangle as the gameSize. I've also seen games with 6 pieces per player (a
gameSize of 3). In our game, the gameSize can be anywhere from 3 to 64, resulting in
anywhere from 6 to 2016 pieces per player.
To communicate game play between my test code and your solution, we need a
numbering system for the board. The positions on the board are described using row
and column values. The board will have 4*gameSize rows, numbered from 0 to
4*gameSize-1. The star shape dictates that row r has the following number of
positions:
0 to ‹gameSize-1 r+1
gameSize to ‹2*gameSize-1 4*gameSize-r+1
2*gameSize to ‹3*gameSize-1 r+1
3*gameSize to ‹4*gameSize-1 r+1-4*gameSize
The columns in row r with c columns are numbered from -(c-1)/2 to +(c-1)/2,
inclusive, for even numbered rows, and from -(c/2)+1 to (c/2), inclusive, for odd
numbered rows. For a position (r,c) in an even numbered row, the adjacent positions
are (r,c-1), (r,c+1), (r+1,c), (r+1,c+1), (r-1,c), and (r-1,c+1). For the same
position in an odd-numbered row, the adjacent positions are (r,c-1), (r,c+1),
(r+1,c), (r+1,c-1), (r-1,c), and (r-1,c-1). (Provided, of course, that those
positions exist on the board).
0: 0
1: 0 1
2: -1 0 1
3: -1 0 1 2
4: -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
5: -5 -4 -3 -2 -1 0 1 2 3 4 5 6
6: -5 -4 -3 -2 -1 0 1 2 3 4 5
7: -4 -3 -2 -1 0 1 2 3 4 5
8: -4 -3 -2 -1 0 1 2 3 4
9: -4 -3 -2 -1 0 1 2 3 4 5
10: -5 -4 -3 -2 -1 0 1 2 3 4 5
11: -5 -4 -3 -2 -1 0 1 2 3 4 5 6
12: -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
13: -1 0 1 2
14: -1 0 1
15: 0 1
16: 0
A move in Chinese Checkers can be either a non-jump move or a sequence of contiguous
jumps. Relocating a piece from one position to an unoccupied adjacent position is a
non-jump move. Jumping over an adjacent occupied position into an unoccupied
position, collinear with the first two, is considered a jump. A single jump move can
consist of jumping a single piece over an occupied position, followed by a jump from
the new location over an adjacent piece to still another location, repeated as many
times as the board situation allows. No pieces are removed from the board at any time.
A move may not begin or end in a neutral zone triangles, although a multi-jump move
may include an intermediate position in the neutral zone. Some Chinese Checker rules
allow a player to pass; this is not allowed in our game.
Your InitChineseCheckers routine will be called at the beginning of each game with the
game parameters, the number of players in the game (numPlayers), the size of the
board (gameSize, described above), the board position for each player
(playerPosition[]), and your index as a player in the game (yourIndex). The
playerPosition is numbered clockwise starting from the (0,0) position.
After every player has been initialized, the player at playerPosition[0] will be asked
to play by calling his YourMove routine. That player should return the Position of the
piece he is moving in *from, and the position he is moving to in *to. For a non-jump
move, the two positions must be adjacent. For a jump move, there must be a valid
sequence of jumps between *from and *to. If you cannot make a legal move, set *from
to the location of one of your pieces and *to to that same location. Illegal moves will
result in disqualification.
After a player moves, the other players will be notified of the move by calling their
OpponentMove routines, providing the index of the moving player in opponent, and the
positions moved from and to in those parameters, respectively.
The game is over when one player has moved all of his pieces from the home area to the
goal area, provided all players have had the same number of turns to move. At the end
of the game, TermChineseCheckers will be called, where you can deallocate any
memory allocated during the game.
The evaluation will consist of solutions playing against one another in combinations of
between 2 and 6 players per game. Each solution will play the same number of games
against each other solution, with the same number of opportunities to play first, with
fair seating arrangements that will be determined after I see how many solutions are
submitted. The winner will be the solution that wins the most games in the least
amount of time. Specifically, the winner will be the solution with the greatest score,
where the score is two times the number of games won, plus the number of games
drawn, minus a time penalty of 1 game per second of execution time. Execution time
will include the time used by all of your routines: InitChineseCheckers, YourMove,
OpponentMove, and TermChineseCheckers.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions may be coded in C, C++, or Pascal.
Three Months Ago Winner
Congratulations to Tom Saxton for submitting the winning solution to the December,
1998, Rendezvous and Docking Challenge. Contestants were required to maneuver a
spacecraft through a collection of orbiting objects to a successful docking with a target.
The objective was to minimize both the fuel expended, measured as the total change in
the velocity vector throughout the flight, and the amount of execution time used to
perform the rendezvous. This was an extraordinarily difficult problem to solve. One
person wrote to say that the final docking maneuver would have been a very difficult
Challenge all by itself. Tom was the only one persistent enough to complete and submit
a correct solution, or any solution at all, for that matter.
The test code consisted of four scenarios in a simulated solar system like our own. The
first scenario, which I dubbed "Shuttle-Zarya" after the first space station assembly
flight, involved maneuvering a ship in earth orbit to a target in a different earth orbit.
The second required a ship in earth orbit to land on the moon. At least I called it a
"landing" - the requirements for differential velocity at docking were very generous,
so one might better refer to it as a controlled crash. The most demanding scenario, both
in terms of the total delta-V required to accomplish the rendezvous and in terms of the
amount of wall clock time needed to complete the simulation, was the third, where the
ship starting in earth orbit was required to land on the Jovian moon Ganymede. The
fourth and final scenario required the ship to leave earth orbit and land on the tiny
Martian moon Phobos. In all cases the ship had an infinite supply of fuel available,
with an engine that delivered between 10 and 30 meters/sec/sec of acceleration, or
roughly 1 to 3 earth gravities..
For transfer between two orbits around the same object, the orbital technique
requiring the least amount of velocity change is an elliptical transfer orbit tangent to
the original and the final orbits. These orbits are called Hohmann transfer orbits,
named after the person first recognizing its usefulness. Of course, these orbits allow a
rendezvous only if the target object is at the point of intersection when the ship
arrives at that point. This is why launch opportunities for real life Mars probes, for
example, only occur at certain times, when the planets are properly aligned. In our
problem, the ship and the target were not aligned in any particular way, so the
Hohmann transfer did not always apply directly. One could have waited around until the
alignment was correct, but Tom chose a different approach.
Tom's approach approximates the N-body problem presented by the Challenge as a
collection of 2-body problems, recognizing the fact that the gravitational effect of one
body is usually dominant. His solution includes four steps. Step 1 is to break the ship
out of the orbit of any object that the target was not orbiting. Step 2 is to enter orbit
around the object that the target is orbiting. Step 3 is to intersect the target orbit in
the vicinity of the target. The final step is to close on the target and match velocities.
The rendezvous state is stored in an ROK ("Rendezvous Orbit Kind") variable, and the
state transitions occur in the _Plan routine.
The method used for the first step (escape orbit) is less efficient than it might be, in
that the resulting orbit can overshoot the intended transfer orbit, although it gets the
job done. This is evident in the Phobos test case, where the escape orbit actually takes
the ship well outside the orbit of Mars. Tom comments, in private email, "The problem
there is the inefficiency with which I escape the Earth's orbit. I didn't have time to
come up with a general way to determine an optimal Hohmann transfer from the
starting Earth orbit (or more generally, a starting orbit around a moon of an
arbitrary planet). So, I just blast out of orbit when the ship is moving parallel to the