ESTR1002, 2024-2025 Course Project Page 1 of 13
ESTR1002
Problem Solving by Programming
2024 – 2025 Term 1
Course Project – Chinese Checker
ESTR1002, 2024-2025 Course Project Page 2 of 13
Figure 1: the game board of a
general Chinese checker. Source:
https://en.wikipedia.org/wiki/Chinese_checkers
1. Introduction
Chinese checker is a turn-based board game played by two,
three, four or even six people. The rules are simple. Each player
takes turns to move one of their chess pieces, aiming to be the
first to move all their chess pieces across the game board from
one’s initial camp to the opposite side of the star corner—using
single-step moves or multi-jump moves over some other pieces.
You SHOULD first learn how to play it:
https://www.coolmathgames.com/0-chinesecheckers
This project is a simplified version of the game. We consider
only two players seated at the opposing corners of an 8x8
square board; see Figure 2 below. Each player has six chess
pieces of his/her own. In general, the game is won by being the
first to transfer all of one's pieces from his/her camp into the
opponent’s camp. In each turn, a player can move one of his/her chess pieces by either
(i) moving one single step to an adjacent empty cell or (ii) jumping through empty cells
on the game board over some other pieces successively; we will show you some examples
later in this spec.
1.1 Project overview
In this course project, you need to submit (see Section 6 in this spec. for details)
1) [basic] a C program to provide an interactive gameplay for two human players.
2) [basic] an embedded computer player to replace one of the two human players.
3) [bonus] our great tournament: compete with the computer player of your classmates.
2. Game Rule
2.1 Game board
The board consists of an 8x8 grid of 64 cells, see Figure 2.
• There are two players in this game.
• Each player has six pieces, e.g., blue or red.
• Each player's camp consists of six cells on top-left and
bottom-right corners of the game board; see Figure 2.
• The game starts with each player's camp filled by pieces
of his/her own color.
We store the game board using a one-dimensional integer
array of length 89. The location of each cell in the board is represented using an integer
in [11, 88]. For example, location “47” means the fourth row and the seventh column.
• The upper-left corner of the board is 11.
• The cell on its right is 12.
• The cell just under 11 is 21. See the cell coordinates below.
Figure 2. The initial game
board of “Chinese checker” ---
this is the name of the game.
ESTR1002, 2024-2025 Course Project Page 3 of 13
Figure 3. Encoding of the piece locations.
Since we use an array of length 89, except for the 64 positions on the board, other
positions are unused, where chess pieces should not be placed. Also, beware of the “array
out of bound error” in this project.
The game always starts with the blue player, whose camp is located at the upper-left
corner.
2.2 Represent the cells of the board
• Empty cells: 0. For example, if the value of board [67] is zero, this means that
there’s no chess piece on the cell at 6th row and 7th column.
• Positions with blue chess piece: 1. For example, if the value of board [45] is one,
this means that there’s a blue chess piece at 4th row and 5th column.
• Positions with red chess piece: 2. For example, if the value of board [45] is two,
this means that there’s a red chess piece at 4th row and 5th column.
• All other positions outside the game board: -1.
2.3 Play sequence
• The player of the top-left corner always moves first.
• Pieces may move only in eight possible directions (orthogonally and diagonally).
• In each turn, a player can have the following possible moves:
o a single-step move to an adjacent empty cell; see possible moves #1a and #1b in
Figure 4. Example possible moves for example horizontal and diagonal moves,
respectively;
o a single-jump move to an empty cell with one jump over some other pieces (can
be the player’s own piece or opponent’s piece); see possible moves #2a and #2b
in Figure 4. Example possible moves for example vertical and diagonal jumps,
respectively;
o also, we can have a long distance jump to an empty cell with exactly one single
piece in the middle between the lifting and landing locations in that jump; see
possible move #3 in Figure. 4; and
o a multi-jump move with more than one jumps successively through some empty
cells, while having only one single piece in the middle between the landing and
lifting cells for each jump; see example moves #4a, #4b, and #4c in Figure 4.
11 12
21
(7,7)
22
33
ESTR1002, 2024-2025 Course Project Page 4 of 13
Figure 4. Example possible moves, starting from the current game board shown on the top left corner.
Figure 5. Example invalid moves, starting from the current game board shown on the left.
2.4 Game End condition: Win or Draw
There are only two possible “end game” conditions, i.e., one of the two players wins; or
the game is a draw. The detailed conditions are specified as follows:
(1) WIN: After a move has been made, a player A wins the game if his/her opponent’s
camp is filled with pieces, among which at least one belongs to A; and
(2) DRAW: after each player has moved 100 steps, if there is no winner, then the game
ends with a draw.
3. Programming Guidelines
We describe some key functions as guidelines for you. Please note that we do not use the
online judge for the project, but still, you should follow some formats for consistent
grading.
ESTR1002, 2024-2025 Course Project Page 5 of 13
3.1 Program Design of “Chinese Checker”
Figure 6. The program flow.
Note: you may create additional functions (e.g., to check if a chess piece can jump over
another one) in your program to make your program more modular and easier to debug.
This is also for you to learn and try the divide-and-conquer concept we discussed in class.
3.2 Requirements
Though the online judge system is not provided, you have the following set of
requirements for consistent and fair grading.
• Your program must read inputs from the keyboard, so that we can test your code
consistently, i.e., we will input a sequence of four-digit integers and see if your
program can generate the expected results.
• Note that we will try some invalid moves and see if your program can find them.
• Your program must print the results to the terminal / command prompt.
• During each round of the game, your program must report:
o the current status of the game board using the above representation;
o print the next player; and
o if a player places a chess piece on an illegal position, print out the notification,
and ask the user to input again.
• At the end of the game, you must report
o who is the winner, or a draw.
3.3 Function #1: Initialize the game board
In this function, you simply initialize the board array according to the description in
Sections 2.1.
ESTR1002, 2024-2025 Course Project Page 6 of 13
3.4 Function #2: Display user interface
First, you should write a function to draw the user interface, i.e., to print the game board
on the terminal/command prompt, given the 1-D array as the function input. We use
• ‘#’ to represent blue,
• ‘O’ to represent red, and
• ‘ . ’ to represent an empty cell.
Figure 7 below shows a sample screenshot of the game board presented Figure 2.
Figure 7. An example of printing the game board.
3.5 Function #3: Read a move from the user
Second, you need to write a function to ask and receive the next move from the user. We
use a four-digit integer to represent a move, where the first and last two digits represent
the starting (lifting) location and ending (landing) location, respectively. For example,
2161 means moving the piece on 2nd row 1st column to 6th row 1st column, regardless of
the intermediate locations. See Figure 8: We use “2161” to represent the move “from (2,1)
to (6,1) after two jumps”.
Figure 8. We use "2161" to represent the move “from (2,1) to (6,1)”.
3.6 Function #4: Check if a move is valid
The inputs by a player may not always be correct, e.g., the provided starting location may
not contain a piece, the piece cannot be moved/jumped to the target location, or the input
is not a four-digit integer at all! This is the more challenging component in the basic part
of this project. Hint: use recursion. To check whether a move is valid, your program
should check if
(1) each input is a four-digit integer, otherwise, print “Invalid input format, please input
again:”;
(2) each input location (both starting and ending) is within the game board range “[1,1]
to [8,8]”, otherwise, print “Input out of the game board, please input again:”;
(3) there exists a chess piece from the current player at the provided starting location,
otherwise, print “Invalid starting location, please input again:”;
(4) there should not be any chess piece at the ending location, otherwise, print “Invalid
ending location, please input again:”; and
ESTR1002, 2024-2025 Course Project Page 7 of 13
(5) the move from the starting location to ending location should be valid, i.e., following
the rules specified in Section 2.3 Play sequence, otherwise, print “The move violates
the game rule, please input again:”.
3.7 Function #5: Check if the game is over
Every time a player finishes a move, your program should call a function, which checks if
the game ends or continues (based on the current player), according to the rules specified
in Section 2.3 “Game End” condition: Win or Draw. If the game is over, print the winner.
Also, if both players have finished the maximum allowed number of moves and there are
no winners, the function should return a value to indicate a “draw” rather than “win” or
“continue”.
3.8 Test your “human v.s. human” gameplay
We have provided to you two sample test files on the course webpage (blackboard) for
you to download and test “human vs. human” gameplay.
Note that since your gameplay should support both “human v.s. human” mode and
“human v.s. computer” mode, at the very beginning of the game, your program should ask
the user to choose between the two modes by inputting an integer. Here, “1” means
“human v.s. human” and “2” should mean “human v.s. computer”.
A typical case is like this:
ESTR1002, 2024-2025 Course Project Page 8 of 13
4. Computer Player
After finishing the “human vs. human” part, you will come to the most challenging and
exciting part of the project, where we replace the function in Section 3.5 Function #3:
Read a move from the user by a computer player function.
To implement a computer player, you mainly need to finish one function. The prototype
of the function is defined below:
int ai_player ( int player , const int * board );
This function needs the following inputs:
• int player: the chess piece that the current player uses: blue is 1 and red is 2.
• const int *board: this is a one-dimensional array (const means constant, i.e., your
function should not modify the contents of the input array) that represents the
current cell conditions in the game board, same at what is defined in Section 2.2:
o Empty cells: 0. For example, if board [67] = 0, this means that there’s no chess
piece on the cell at 6th row and 7th column, you may put a chess piece there.
o Positions with blue chess piece: 1. For example, if board [45] = 1, this means that
there’s a blue chess piece at 4th row and 5th column.
o Positions with red chess piece: 2. For example, if board [45] = 2, this means that
there’s a red chess piece at 4th row and 5th column.
o Other positions not on the board: -1.
• The return value (int): this function returns a four-digit integer that represents a
move; see Section “3.5 Function #3: Read a move from the user” for its meaning.
4.1 “Human v.s. computer” mode
Since you already have a function from Sec. 3.5 to scan a user input from the human, you
can simply replace it by the ai_player function you just implemented in your main
program to support the “human v.s. computer” mode, without implementing other game
logics twice. At the beginning of your program, if the user chooses mode “2”, your
program should enter the “human v.s. computer” mode. You may further ask the user to
choose between “computer plays first” of “human plays first”, or, you may always let the
computer to play first/second.
4.2 [Bonus] The great tournament!!!
This bonus part is an extra!!! After evaluating the “human v.s. human” and “human v.s.
computer” parts of your program, we will evaluate how smart your computer player is
by creating a tournament for the computer players of all the students in the class to
compete against one another.
Below is the game rule:
• For each student’s computer player, it will play two games against the computer
player of each of the other classmates.
• In each of these two games (between the same pair of students), each computer
player takes turns to use the blue chess piece and to start the game first.
ESTR1002, 2024-2025 Course Project Page 9 of 13
• You score 2 points for each game you win and 1 point for each draw; you got zero
points if you lose or your program does not follow any requirements we define in
this project specification.
4.3 Requirements of the computer player (for both “human v.s. computer”
and the great tournament)
• You must follow the prototype defined in Section “4. Computer Player” to implement
your computer player.
• It should produce valid moves, and it should not modify the input game board.
• Note that your computer player may play first or play second, meaning that your
chess pieces may start from the upper-left OR lower-right corner.
• Your “submitted” computer function shouldn’t contain any print statement,
otherwise, the tournament system may wrongly judge your results. Note that you
may have print statements when you debug your code but remember to comment
them out before submission.
• For fairness in the competition, your computer player must produce an output
within a reasonable amount of time, i.e., within 5 seconds on the lab’s computer.
• You need to carefully test your code to make sure your code won’t damage our
tournament system, e.g., the “array out of bounds” error!!!
• No “main() function” in your submitted files for the computer tournament part.
Please note that if your program does not follow any one of the above requirements, you
may get zero points for the “human v.s. computer” part or the tournament.
ESTR1002, 2024-2025 Course Project Page 10 of 13
5. Submission
We have created two submission boxes on Blackboard:
• Basic program: the entire program, including all .c and .h files that supports
“human vs. human” and “human vs. computer” and
• Great tournament: your code ONLY for the computer player to attend the
tournament.
5.1 Submission format for basic program
Your submission for the basic program should be a single zip file named as
basic_<studentID>.zip (e.g., basic_1155123456.zip)
which contains and should only contain all .h and .c files in your project. The TA will
download your submission files from Blackboard and compile them during the project
demo to form an executable game using gcc, CodeBlocks, or Visual Studio for testing.
5.2 Submission format for the great tournament
Your submission for the great tournament should contain only two files:
• aiplayer_<studentID>.h (e.g., aiplayer_1155123456.h)
In this file, you must need to define the following function:
int ai_player_<studentID> ( int player , const int * board );
• aiplayer_<studentID>.c (e.g., aiplayer_1155123456.c)
where <studentID> is your own student ID. In this file, you may have more
functions for your main computer player function above to call.
In the submitted zip file for computer player, you need to include the above .h file and all
the necessary functions inside the above .c file for your computer player to work. To
implement a stronger computer player, you may define additional functions in your .c file.
However, you must follow the above naming convention (i.e. add your own “_studentID”
at the end of all your function names), so that your TA can take your .c file and compile it
with other student’s .c files without having any ambiguity, i.e., same function name from
different students. We may deduct your project marks, if you fail to follow this convention.
Also, use .c rather than .cpp and .C as the extension of your source code file.
Submission Note:
- After preparing your submission files according to the above formats, you need to
upload the files (see above) to the corresponding submission boxes in blackboard.
Please see blackboard for the details.
- You may submit multiple times for each submission box, and we take the last
submission before the deadline as your submission for grading.
- Furthermore, we will do plagiarism checks on your submission against others and
against the Internet.
Submission Deadline:
- Pre-tournament deadline (optional): Nov 24, 11:59pm
- Ultimate deadline: Nov 27, 11:59pm
- Demo day is on Nov 28 in class.
ESTR1002, 2024-2025 Course Project Page 11 of 13
6. Grading
This project has two parts for grading. Note again that the basic part of the project (part
1 below) takes up 16% of the whole course and the bonus part (part 2 below) is extra.
Part 1: the basic game program (16%)
• The basic “human vs. human” part takes up 12% of the whole course.
• The basic “human vs. computer” part takes up another 4% of the whole course.
During the project demo (on the demo day during the last lecture), the TAs will compile
your program, and then test your program in the following ways:
(i) interactively try your game with “human vs. human”;
(ii) pipe some sample text files in the above format into your game executable and see
if the results are correct, as expected (you will learn the meaning of “pipe” in class
later); and
(iii) try “human vs. computer” in your game to see if the moves selected by your
computer player are always valid, etc.
Part 2: The great tournament
Please read Sec. 4.2 again for the rules of the great tournament.
After all matches are completed, we will sum up the points that each student gained as
his/her total tournament score. Then, we will rank the students based on the total scores.
Each student may then obtain extra bonus points (beyond the basic scores in the course)
based on his/her ranking; see the table below.
Ranking Bonus Credit (of the
whole course)
1 3.0 bonus pts
2-3 2.2 bonus pts
4-7 1.4 bonus pts
8-15 0.6 bonus pts
ESTR1002, 2024-2025 Course Project Page 12 of 13
7. Project Schedule
Week Date Tasks Expected to be done
9 Oct 28 The project will be released on Blackboard course homepage
(and will be discussed in class on Oct 28)
Start to write the basic game:
• Function: Initialize game board
• Function: Display user interface
• Start thinking over - Condition: “Location valid?”
• Start thinking over how to find all squares?
Etc.
At home: implement the rest of the game.
10 - 11 Nov 11 • Around this date, you should have completed the basic
game without the computer player, so that you can focus
on your computer player for remained time.
12-13 Before
Submission
Deadline
Finish the basic program,
finish a working computer player (valid moves ONLY) &
perfect your computer player (with better strategies).
13 Pretournament
Nov 24
11:59pm
• If you submit your computer player before this predeadline,
we will take your code to compete with others
in a pre-tournament and will let you know your results
and also let you know if your code has any problems.
• The pre-tournament is volunteer-based, and has no
contributions to the final score. However, it may allow
you to know your program’s capability and whether it
has any compilation problem, so that you can work out
a better program before the deadline.
13 Nov 27
11:59pm
Deadline of submitting (1) the basic program & (2) the
computer player.
13 Nov 28
2:30pm4:15pm
DEMO DAY:
1) TA will evaluate the basic program of all the students
one by one in the lab (must present and wait).
2) TA will run the great tournament.
ESTR1002, 2024-2025 Course Project Page 13 of 13
8. Academic Honesty
Every submission will be inspected using plagiarism detection software. The worst
possible punishment is to have this course failed. For regulations and details, please refer
to the following URL:
https://www.cuhk.edu.hk/policy/academichonesty/Eng_htm_files_(2013-14)/p06.htm
Last but not least, please take note of the following declaration that we presume that you
agree on if you submit your project code.
/**
* ESTR 1002 Problem Solving by Programming
*
* Course Project
*
* I declare that the assignment here submitted is original
* except for source material explicitly acknowledged,
* and that the same or closely related material has not been
* previously submitted for another course.
* I also acknowledge that I am aware of University policy and
* regulations on honesty in academic work, and of the disciplinary
* guidelines and procedures applicable to breaches of such
* policy and regulations, as contained in the website.
*
请加QQ：99515681 邮箱：99515681@qq.com WX：codinghelp
