LP102 2019 Spring
Homework 1
Abstract
Write a C [1] program that can play the games of Go and GoBan.
1 Introduction of Go and Goban
Go (called WeiQi in China) and Goban (called WuZiQi in China) are ancient
board games. The board is marked by horizontal and vertical lines. Stones,
white or black, will be placed on the intersections of lines. Two players will
use different colors of stone, and put their stones in turn on the board. Go
and Gomoku have different rules of winning. The rules of the two games are
simple. We can find online documents for their rules.
Rules of Go:
The picture above is from https://tromp.github.io/go/le…
1
https://en.wikipedia.org/wiki…
https://senseis.xmp.net/?Basi…
Rules of Goban:
https://en.wikipedia.org/wiki…
2 Gaming data storage
2.1 Board and stone
A 2–dimentional array of integers is used to record the stones on the board.
If the board has 19 × 19 lines, then we can use an 19 × 19 board. At a
line interscetion on the board, there are 3 possible stone occurrences there:
Empty, Black, White. We can use 3 different integers of represent the 3
stones, such as 0, 1, 2. Initially, the board is empty, which means each item
in the 2D arrary of the board is Empty. When a user pick a coordinate, say
E 6, to place a stone, say a black stone, if Black is represented as 1, then
the corresponding update of the board can be represented as the following
assignment statement:
board4 = 1
2.2 Game play history record
We can use a 3D integer array to record the history of a game, which is
a sequence the positions where stones are put during the game. We don’t
need to remember which position is black or white in the history, since we
assume a black stone is always put first. This history array will be saved to
a file on a hard drive, or be loaded from a hard drive to memory.
3 Display of gaming data
The board and stones can be printed using ASCII characters at the command
line. Here is some screen record of playing GNU Go:
White (O) has captured 0 pieces
Black (X) has captured 0 pieces
A B C D E F G H J K L M N O P Q R S T Last move: White C5
19 . . . . . . . . . . . . . . . . . . . 19
2
18 . . . . . . . . . . . . . . . . . . . 18
17 . . . . . . . . . . . . . . . . O . . 17
16 . . . + . . . . . + . . . . . O X . . 16
15 . . . . . . . . . . . . . . . . O . . 15
14 . . . . . . . . . . . . . . . X . . . 14
13 . . . . . . . . . . . . . . . . . . . 13
12 . . . . . . . . . . . . . . . . . . . 12
11 . . . . . . . . . . . . . . . . . . . 11
10 . . . + . . . . . + . . . . . X . . . 10
9 . . . . . . . . . . . . . . . . . . . 9
8 . . . . . . . . . . . . . . . . . . . 8
7 . . . . . . . . . . . . . . . . . . . 7
6 . . . . . . . . . . . . . . . . . . . 6
5 . .(O). . . . . . . . . . . . . . . . 5
4 . . . + . . . . . + . . . . . + . . . 4
3 . . . X . . . . . . . . . . . . . . . 3
2 . . . . . . . . . . . . . . . . . . . 2
1 . . . . . . . . . . . . . . . . . . . 1
A B C D E F G H J K L M N O P Q R S T
black(9): o2
White (O) has captured 0 pieces
Black (X) has captured 0 pieces
A B C D E F G H J K L M N O P Q R S T Last move: Black O2
19 . . . . . . . . . . . . . . . . . . . 19
18 . . . . . . . . . . . . . . . . . . . 18
17 . . . . . . . . . . . . . . . . O . . 17
16 . . . + . . . . . + . . . . . O X . . 16
15 . . . . . . . . . . . . . . . . O . . 15
14 . . . . . . . . . . . . . . . X . . . 14
13 . . . . . . . . . . . . . . . . . . . 13
12 . . . . . . . . . . . . . . . . . . . 12
11 . . . . . . . . . . . . . . . . . . . 11
10 . . . + . . . . . + . . . . . X . . . 10
9 . . . . . . . . . . . . . . . . . . . 9
8 . . . . . . . . . . . . . . . . . . . 8
7 . . . . . . . . . . . . . . . . . . . 7
6 . . . . . . . . . . . . . . . . . . . 6
3
5 . . O . . . . . . . . . . . . . . . . 5
4 . . . + . . . . . + . . . . . + . . . 4
3 . . . X . . . . . . . . . . . . . . . 3
2 . . . . . . . . . . . . .(X). . . . . 2
1 . . . . . . . . . . . . . . . . . . . 1
A B C D E F G H J K L M N O P Q R S T
GNU Go is thinking…
white(10): E4
Here is the screen shot of playing Goban using with another board design:
This the game setting:
board-size: 13; win-size: 5; lines-on-board: Yes
Enter to continue
!!!!!!! Welcome to Dragon Go !!!!!!
A B C D E F G H J K L M N
13 +—+—+—+—+—+—+—+—+—+—+—+—+ 13
| | | | | | | | | | | | |
12 +—+—+—+—+—+—+—+—+—+—+—+—+ 12
| | | | | | | | | | | | |
11 +—+—+—+—+—+—+—+—+—+—+—+—+ 11
| | | | | | | | | | | | |
10 +—+—+—+—+—+—+—+—+—+—+—+—+ 10
| | | | | | | | | | | | |
9 +—+—+—+—+—+—+—+—+—+—+—+—+ 9
| | | | | | | | | | | | |
8 +—+—+—+—+—+—+—+—+—+—+—+—+ 8
| | | | | | | | | | | | |
7 +—+—+—+—+—+—+—+—+—+—+—+—+ 7
| | | | | | | | | | | | |
6 +—+—+—+—+—+—+—+—+—+—+—+—+ 6
| | | | | | | | | | | | |
5 +—+—+—+—+—+—+—+—+—+—+—+—+ 5
| | | | | | | | | | | | |
4
4 +—+—+—+—+—+—+—+—+—+—+—+—+ 4
| | | | | | | | | | | | |
3 +—+—+—+—+—+—+—+—+—+—+—+—+ 3
| | | | | | | | | | | | |
2 +—+—+—+—+—+—+—+—+—+—+—+—+ 2
| | | | | | | | | | | | |
1 +—+—+—+—+—+—+—+—+—+—+—+—+ 1
A B C D E F G H J K L M N
It is now move of BLACK
Please give the coordinates (a letter and a digit) to put your stone, according to the board:
d5
A B C D E F G H J K L M N
13 +—+—+—+—+—+—+—+—+—+—+—+—+ 13
| | | | | | | | | | | | |
12 +—+—+—+—+—+—+—+—+—+—+—+—+ 12
| | | | | | | | | | | | |
11 +—+—+—+—+—+—+—+—+—+—+—+—+ 11
| | | | | | | | | | | | |
10 +—+—+—+—+—+—+—+—+—+—+—+—+ 10
| | | | | | | | | | | | |
9 +—+—+—+—+—+—+—+—+—+—+—+—+ 9
| | | | | | | | | | | | |
8 +—+—+—+—+—+—+—+—+—+—+—+—+ 8
| | | | | | | | | | | | |
7 +—+—+—+—+—+—+—+—+—+—+—+—+ 7
| | | | | | | | | | | | |
6 +—+—+—+—+—+—+—+—+—+—+—+—+ 6
| | | | | | | | | | | | |
5 +—+—+—X—+—+—+—+—+—+—+—+—+ 5
| | | | | | | | | | | | |
4 +—+—+—+—+—+—+—+—+—+—+—+—+ 4
| | | | | | | | | | | | |
3 +—+—+—+—+—+—+—+—+—+—+—+—+ 3
| | | | | | | | | | | | |
2 +—+—+—+—+—+—+—+—+—+—+—+—+ 2
| | | | | | | | | | | | |
1 +—+—+—+—+—+—+—+—+—+—+—+—+ 1
A B C D E F G H J K L M N
5
It is now move of WHITE
Please give the coordinates (a letter and a digit) to put your stone, according to the board:
e5
A B C D E F G H J K L M N
13 +—+—+—+—+—+—+—+—+—+—+—+—+ 13
| | | | | | | | | | | | |
12 +—+—+—+—+—+—+—+—+—+—+—+—+ 12
| | | | | | | | | | | | |
11 +—+—+—+—+—+—+—+—+—+—+—+—+ 11
| | | | | | | | | | | | |
10 +—+—+—+—+—+—+—+—+—+—+—+—+ 10
| | | | | | | | | | | | |
9 +—+—+—+—+—+—+—+—+—+—+—+—+ 9
| | | | | | | | | | | | |
8 +—+—+—+—+—+—+—+—+—+—+—+—+ 8
| | | | | | | | | | | | |
7 +—+—+—+—+—+—+—+—+—+—+—+—+ 7
| | | | | | | | | | | | |
6 +—+—+—+—+—+—+—+—+—+—+—+—+ 6
| | | | | | | | | | | | |
5 +—+—+—X—0—+—+—+—+—+—+—+—+ 5
| | | | | | | | | | | | |
4 +—+—+—+—+—+—+—+—+—+—+—+—+ 4
| | | | | | | | | | | | |
3 +—+—+—+—+—+—+—+—+—+—+—+—+ 3
| | | | | | | | | | | | |
2 +—+—+—+—+—+—+—+—+—+—+—+—+ 2
| | | | | | | | | | | | |
1 +—+—+—+—+—+—+—+—+—+—+—+—+ 1
A B C D E F G H J K L M N
You can design you own board and stone display. Notice that on the
board between marks of H and J, there is no I, since I is indistinguishable
to the digit 1.
6
Figure 1: Overview of the calling relationship of different component.
4 Program structure
4.1 Overview
Fig. 1 shows the calling relationship between different logical components
of the program.
For example, from the command line, the operations of loading a game
and playing a new game can be activated. Explanations of the calling relationships
between different logcal components, as shown in the graph, are
provided in the next subsection.
4.2 Logical components
Command line: The game program should allow command–line argument.
For example, suppose the name of the executable file is game,
then the following are possible commands with their explanation.
– game go 9 : Start a new Go game with a 9 × 9 board.
– game goban 13 : Start a new Goban game with a 13× 13 board
– game load game1.gm : Load the game that is saved as the file
game1.gm, which should be a file saved earlier by this program,
then go to the main menu.
7
– game : Start a new game, then the user will be asked for the
choice of game of and the board size, or to load a game with given
file name.
Saving a game: Ask the user for the file name, then write the game
information (Go or Goban, board size, game history) to the file. This
can be implemented using the fwrite() function. This operation is
reached after playing a game or continuing playing a game. Go to the
main menu afterwords.
Loading a game: Ask the user to provide the name of file of a saved
game, load the data items from the file to memory, following the order
when these data items are saved to the file. This can be implemented
using the fread() function. This operation can be triggered from the
command line, or from the menu. Go to the menu afterwords.
Playing a new game. Initially, no stone is on the board. A black stone
will be put on the board first. Repeat the following 2 steps until end
of game is reached:
- Print the current game information: print the board, show the
stones on the board, indicate what is the last move, and whose
turn to play now. - Accept the user’s input of coordinate.
– If the user’s input is not an allowed coordinate, ask the user
to input again.
– If the user’s input is quit, or any word start with q, go to the
end of game.
– If the user’s input is a valid coordinate, update the data of
the board and the game history. If a winner can be decided,
or no more stone can be placed on the board, show the game
result and who is the winner (draw is possible), and go to
the end of game.
End of game. Ask the user to save the game or not. If user says yes,
activate the operation of saving the game. Go to the menu afterwords.
Note that if user says no, the game data are still in the memory, and
the game can be possibly replayed or continued when the user choose
to do so at the menu; when a new game starts, the unsaved data will
be gone.
8
Replaying a game: Assume that the game data are already in memory,
play the game 0te0]p by step. The user can hit the enter to see the
next move of the game, or type quit to end the game replay.
Continuing a game: Assume that the game data are already in memory.
If an old game is just loaded, then continue to play the old game.
If the current game is just ended (or quit by user), then the current
game data is in memory and the user will continue to play the game
that is jused quit (paused).
Menu: When a user start the game at command line without argument,
or finished playing a game, the (menu will appear. This is the
main menu of the system; a programmer can design sub–menus for
smaller tasks. The menu will ask a user to choose from:
– Play a new game. Do the operation of playing a new game.
– Load a game. Do the operation of loading a game.
– Replay a game. Do the operation of replaying a game. A user
can replay the current game whose data are already in memory.
If a user want to replay an older and saved game, then the game
should be loaded first.
– Continue a game. Suppose the data of a game is in memory (an
old game is loaded, or the current game is just quit by the user).
– Quit. This will end the program.
After the task of each choice is done, except the Quit choice, the user
sees the main menu again. - Requirements and Bonus
Requirements:
The code should original and self–made.
The code should be organized in several files. For example, one file
for showing board, one file for the main menu, one file for the game
operations.
The user’s input should be verified. When some wrong input is given,
the program should respond some error message and ask the user to
try again. The input queue should be cleared before the next input.
9
For the Goban game, complete the full game implementation.
For the Go game, only three rules need to be implemented:
– The rule of capturing stones: When a block of connected stones
are dead (with 0 qi), they should be taken out from the board
immediately.
– The rule of no-entering: It is not allowed to put a stone in a
position, if that position is fully surrounded (has 0 qi), unless
puting stone can kill some neighboring opponent stones.
– Then rule of game ending: When there is no position available to
put a stone on the board, the game ends. An empty position that
are surrounded by white and the border belongs to white, otherwise
belongs to black. The player who occupies more positions is
the winner.
Bonus You can choose to do some bonus work.
Implement some other rules of playing Go to make it like a real game.
For exmaple, allow the game to end without putting stones at all
possible positions. When both user agrees to end a game, the game
ends.
Add some time requirements to play the game. When a player runs
out the player’s time, the player lose the game.
Set up some user’s account. So that a player can load the game that
the player played.
Some advanced user interface, for example, display the names (or file
names) of all the games that recorded, so that the user can easily
choose one to replay.
Implement some simple AI, so that the computer to play with human.
Other possible and interesting design of the game.
Write a readme.txt file to explain in details your work: your design, considerations,
difficulties and solutions, experience of cooperation with team
members.
10 - Grading of the Program
Your program will be graded by its quality and style. Detailed policy of
grading is included in the file HmkGradingPolicy.txt. At most 20 points can
be awarded for the optional operations, depending on the complexity and
design quality. - Submission
Due time: Monday 22 April 2019, 10:00pm.
Compile and debug and run your program.
At most 2 students can form a group and do the work together.
Your code should be pretty, i.e, you should indent and align your lines
and code nicely and logically following some pretty-printing style.
At the top of each of your source files (.c or .h files), write your name,
last four digits of student id and date as comments.
Attach all of your source code files to an email (.c, .h or .txt files). Do
not attach binary files (.o, .obj, .exe or executable) files, since doing so
will make your email being considered as virus by the Gmail system.
You are welcome to write a file (readme.txt) to explain your code and
discuss the problems that you met in coding.
The title of your program should be like:
nameD1|D2
If there are 2 students do the homework together, put their names in
the title. Clear indicate in the email and the readme file the names,
classes of the student, and the work load division between the students.
References
[1] Stephen Prata. C Primer Plus (6th Edition)(Developer’s Library).
Addison-Wesley Professional, Indianapolis, IN, USA, 2013.
WX：codehelp