[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: computer-go: About Viking




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