computer-go: Advanced stuff

[Heikki Levanto <heikki@xxxxxx>]

Hi,

The way to represent boards, stones, and liberties is interesting, and I am
sure there are many other ways to do it (for example, you can get quite far
with board-sized bitmaps). But in a way all this is trivial, we all know
what liberties are, and can find a way to represent them. But how do you
folks approach the difficult questions of go programming? A good question to
start discussing in 2001...

I can think of two main approaches: Bottom up and top down. Bottom up is
probably the easier way to program, just go through the whole board and see
if you can find moves "can cut here", "can make eyes there". Once you have
them all listed, choose the best. Top down is (naturally) the opposite,
analyze the situation, make plans, find moves that implement them: "I am
behind in territory, but there is a weak group". "Ergo, attack the weak group
and either kill it or gain influence this way". "Can not kill, attack for
influence". "Run out with the surrounding group". "One point jump is good
for running out". "Yes, it works - play at K6".

Of course these are just two points on a continuous line, there must be
millions of alternatives in between - and some on either side. And other
millions on other lines, like whole-board evaluation and minimax search.


Or - to look at the situation from another direction - is it fair to assume
that most programs consist basically of four steps, of which some can be so
trivial as almost not to be there. I mean:
  1) analyzing the position
  2) Producing proposals 
  3) Choosing one
  4) Refining and verifying it, discarding it if no good

Seen in this framework, one key difference between programs is the level of
abstraction the proposals are made. On bottom-up programs these are moves,
with estimates of the values. On top-down programs these are more abstract
ideas, and the refining process will eventually come with a concrete move
and an estimate of the value of it.


My gut feeling is that most of the current programs are close to the
bottom-up end of this spectrum. I expect they would be the easier ones to
write, and thus the most common. BUt do you think this will hold in the
future as well? Is it not tempting to believe in some "higher-level" "AI" to
make more educated decisions on what to spend all the CPU power on, and what
to try to achieve? Maybe this is where a new (dedicated?) programming
language would shine?


Further discussion: What approaches have I missed completely? What reasons
there might be to speak for top-down or bottom-up approaches in the near or
far future? Any chance we will ever settle down with the one "most
promising" approach (like chess programs seem to have done)? Any other
comments?




-- 
Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
               "In Murphy we Turst"