Problem Description
 |
|
Black's move. But where? |
Here's my first version of a Delphi
implementation of the ancient Chinese game of Go (called
Wei-chi
in China).
Addendum Nov 21, 2005: Version 2.0
was posted today. Still not complete but better than version 1.
Addendum Jan 10, 2008: Version 3
adds board Save and Load buttons to simplify Go studies. Also
fixes a problem with diagnosing Ko.
Background & Techniques
Go is one of those simple but complex board games. Two
opponents take turns placing black and white stones on a square
board. If you surround a group of opponents stones with yours, the
stones are removed and you get credited with a point for each stone
captured.
If you are not familiar with the game just do a web search on
"Go game rules" or "Go game tutorial" and you'll find plenty of
sites.
Advocates describe it as "the greatest board game ever" and
"more difficult to master than Chess". I'm not, and
never will be, a Go expert. In fact, I don't completely
understand the intricacies of the rules of play. A student who
was looking for an
implementation as part of a senior project wrote to me, and I got caught up in how to
code it. I decided I had better post this first effort for a couple of reasons.
The professor will certainly do an online search after he
submits his project, so he can determine how much of the code is mine and
how much is the student's.
Secondly, I'm hoping that some knowledgeable Go
players out there will be willing to tell me what important features are
missing and what is plain wrong in this version.
Three board sizes are available: 9x9, 13x13, and the official
19x19.
I did implement a debug mode which has some features which might be
handy for skills practice:
For scoring, I just credit the taker with captured stones.
I've seen other information about "live" and "dead"
empty spaces. As I understand it, dead spaces could be filled by one
player but would be suicidal (therefore forbidden) for the other. I
think that "dead" spaces count for the player who could play
there, but I'm not sure about that or whether it's worth the effort to
classify them.
Non-programmers are welcome to read on, but
may want to skip to the bottom of this page to
download executable version of the program.
Notes for programmers
Identifying groups of stones and determining when a
group was surrounded by stones of a the opposite color was harder to code than
expected . The game is
played by placing stones on the intersections of gridlines. A group
is a set of one or more stones of the same color connected by horizontal
and vertical grid lines. A group is captured by surrounding it
with stones of the opposite color.
"Surrounding" means that each horizontal and vertical grid
line extending from the edges of a group is filled with a stone of
the opposite color.
After a few false starts, my solution was
to implement routines that clear all blocks and identify them from scratch
after each stone is placed. Findblocks initiates the process
and the FindBlocksFrom function recursively completes
the search for each block. Function BlockCount is called to
count the blocks in each group and also returns the number of open
edges. Everything could have been done more efficiently,
but there are only a few hundred stones at most and only a few
hundred moves, so the time to start from scratch for each stone played is
not significant.
I have implemented tests to prevent some of
the forbidden stone placements, for example "suicide" moves,
which complete the surrounding of a group of the player's color.
However if the play also completes surrounding of a group of the
opponent's color, then the move is allowed and the opponents groups is
captured. Also I try to detect a situation called "Ko"
which occurs where my stone has been captured, but if I played in the same
location again, I would capture the opponent's stone, setting up a
loop situation. (But
after an intervening move or Pass, I can play in this spot.
There are still situations that I'm not sure how to handle. This one for
example: 
. If white plays the open space between the two blacks, are they both
captured? There are probably other cases which are not
handled properly or at all. I don't plan to make a
career of Go, but I would like to fix the most glaring errors or
omissions, so send that feedback.
By the way, the partial game at the top of this
page is from tutorial site http://playgo.to/interactive/.
The best move for black is the 4 stone capture at column 3, row 5.
Addendum November 21, 2005: Version
2.0 posted today does a better job of handling Ko and suicide
attempts. The question about the picture above was helpfully
answered by programmer/Go-enthusiast Jeff B. Yes, both black
stones are captured (up to 4 blocks could be captured by a single stone
play), but it is not Ko. Black still could not play on either
of the captured locations above though because "suicide" is not
allowed. I also added an "Undo" option to take back
the most current stone played.
The BlockCount functions were rolled into FindBlock
and a new TBlock object keeps stone count, open edge count, and
detail stone location information for each block. The Blocks
array keeps track of all blocks on the board.
Addendum January 10, 2008: Viewer
Childem wrote the other day pointing out that my program incorrectly
called a "Ko" (repeated position) move under conditions where
multiple stones were removed by the 2nd play which replaces the stone
just removed. The resulting board is not a duplicate of the
previous board and so should no be diagnosed. There is a
deficiency in my "Sameboard" procedure which should, (but doesn't), catch
this condition. The viewer helpfully provided a workaround by
checking that only a single stone change by the 1st move is reversed by
the 2nd move. He is quite knowledgeable about the game and I
didn't find the bug after spending a couple hours, so I'm just accepting
his "one stone" check in today's Version 3.
A sample board, Test.txt, is included with
the download zip files. It shows two instances of the
problem that was fixed by this version. To see it, play A, B. A
starting with White (multiple stones removed when the 2nd stone is
played) or C, D, C starting with Black (multiple stones removed when the
1st stone is played). Childem described to me a complex and
rare situation during a game played in Korea in 2005 which apparently
involved a 3 move "loop" not resolved by existing Korean rules.
Chinese rules did cover the situation and call it a draw. Another complex situation for this
"simple" game!
Buttons to save and restore boards were
also added
to simplify setting up sample cases. It saves Board size, current
player color, run mode, and score information as well as the contents of
each cell on the board.
Running/Exploring the Program
