Re: computer-go: About Viking

["Eric Boesch" <ericboesch@xxxxxxxxxxx>]

> I almost forgot my main principle:
> There should be no compromises in how the program represents
> things. Either a chain of stones is connected or it is not, and
> the program should know exactly why.
That last sentence is my main principle too; and it seems that we agree that 
methodical positional reading (as opposed to relying exclusively on a static 
pattern database) is the way to achieve it.  Every time you use an 
assumption to limit your search space, you are sacrificing both accuracy 
(your assumption may be wrong) and speed (if you don't keep track of which 
spaces are relevant to the achievement of a goal, then to achieve any 
accuracy at all, you must be conservative, so you will usually be 
considering too many locations, which increases search time).

I intend (by February 2099) to generate a set of life/death and connection 
rules on the fly (if no applicable rule is in the cache already) by using 
alpha/beta searches over incrementally expanded search spaces.  The initial 
search space for a life/death problem is determined by the principle "the 
only direct way to capture a group is to play on one of its liberties."  If 
the group is capturable, then the search space is expanded by reapplying the 
same principle -- "the only direct way to prevent the capture is to play on 
one of the group's liberties, or to play on a liberty of a potential 
capturing stone".  Indirect attacks and defenses are just chains of direct 
attacks and defenses.  The "knowing exactly why" part, then, involves 
remembering which stones and liberties had an indirect effect on your final 
conclusion.

How do you maintain all these rules?  One possibility is a truth-maintenance 
scheme, where you say "moving here means that these groups might no longer 
be connected, and this group might no longer be dead".  But I didn't just 
want to remember what's true now; I wanted to cache rules about hypothetical 
positions too.

The basic approach I am taking is to maintain the rules in a tree of 
questions.  For example, a question might be, "What is the color of the 
vertex immediately underneath the target stone -- same, different, empty, or 
border?", and the next question would depend on the answer to that question. 
 Eventually, you either reach a leaf of the tree which has a conclusion 
("the target stone is alive if the defender moves first", "the target stone 
is dead", "we tried to figure out what happens if the defender moves first, 
but the search tree was too big"), or you find out that this is a new 
position that needs to be searched.

Does anyone have any "been there, done that" comments?  A really good one 
could convince me to bail out on the whole thing. :)


_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com