Game of Go

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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:

Multiple stones of a specified color may be placed in a  single "turn".
Each stone displays the group or block to which it belongs. (Blocks are connected groups of stones of the same color).
Stones already placed may  be removed by right clicking. 

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 

Suggestions for Further Explorations

Identify and fix bugs and omissions.
Done January, 2008: Add ability to save and restore board states to/from a file.  
Computer play vs. a human.  (Fat chance!)

 

Original Date: November 11, 2005

Modified: February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.