Archived

This topic is now archived and is closed to further replies.

Peter19852001

How to implement the game 'Go'

Recommended Posts

Today I ''ve decided to make the game ''Go''. I know that the AI part is going to be quite complicated, so I am going to implement one that allows two human players to play first. However, implementing this is not trivial. Any help will be greatly appreciated. Could anyone who have implemented this game before give me some advice on 1. how to represent the game state 2. how to determine which portion of the ''stones'' on the board are dead and should be captured Since this game uses a square board, it is natural to use an 2d array , which stores black,white or empty, to represent the game state. Is this a good choice? Another choice I can think of now is to use a structure to store a block of ''stones'' that are ''linked together''. What opinion do you have?

Share this post


Link to post
Share on other sites
You should be aware that Go is one of the most complicated games to write an AI for. There have been endless discussions about writing "good" opponents. Representing the game state itself sould be almost trivial, but there are quite a lot of subtleties in playing the game.

The links here might be interesting to you.

EDIT: sorry, I read over the "no AI" part... If you want a program that just lets two players play Go, then a simple 2D array should be fine since you wouldn't have to worry too much about efficiency. However, if you intend to let the computer be the judge, you should put some thought into recognizing "caught" stones, hopeless positions and so on. Perhaps let the computer search for enclosed positions first and then let the humans decide what to make of the position.

[edited by - Shadowdancer on July 7, 2003 11:02:25 AM]

Share this post


Link to post
Share on other sites
I have a half-done Go implimentation that I''ve been making on and off for a while. I have two arrays representing the board - one for this turn and one for last turn - and each array can have one of three states: black, white, empty.



Qui fut tout, et qui ne fut rien
Invader''s Realm

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
[offtopic]
IIRC, the currently best GO AI was beaten by a 4-year old. (of course (s)he was not a beginner, but young & amateur nevertheless)
[/offtopic]

Share this post


Link to post
Share on other sites
a 2d array i think is the best solution

for each cell u could use 1 byte 0 - empty 1 - black 2 - white and set the msb( | 0x80) if its conquered

also use the array as a graph and after each move determine if each of the cells to see if they form a cycle. if they do use a flood fill alghoritm to mark all the cells inside as taken.

u could implement a simple AI using the risc of capture of each cell and determining the next move based on the riscs so that by doing it u will have the lowest risc. however this strategy is only for defense. the hard thing to do offensive AI for GO si that its hard to program the AI to create a strategy.







/*ilici*/

Share this post


Link to post
Share on other sites
quote:
Original post by Peter19852001
1. how to represent the game state.

Since this game uses a square board, it is natural to use an 2d array , which stores black,white or empty, to represent the game state. Is this a good choice?

A simple 2D array is probably just fine. Worry about optimizing the board representation later. You will probably also want to save a copy of the board after every move (for history, undo, and/or ko).
quote:
2. how to determine which portion of the ''stones'' on the board are dead and should be captured

Another choice I can think of now is to use a structure to store a block of ''stones'' that are ''linked together''.


It is much easier to count the liberties for a stone that was touched, rather than maintaining a list of groups. It might take an extra millisecond...

Share this post


Link to post
Share on other sites