[computer-go] Former Deep Blue Research working on Go

[Eric Boesch]

On 10/8/07, Tapani Raiko <Tapani.Raiko at tkk.fi> wrote:
> > May sound unpolite. But Deep Blue reached a very
> > important step in IA. They will be known for ever.
> > But, from a research point of view, they didn't much
> > really. It was mainly a technological/technical
> > achivement.
> >
> Maybe they will reimplement Mogo, try a null-move tweak, use a
> supercomputer, and claim to have the strongest computer Go player ever. :-)

Naive null move is unhelpful because throughout much of a go game,
almost every move is better than passing, but generalizations of null
move can help in local fights, where most of the board really doesn't
matter. Thomsen calls lambda search an extension of null move. I
implemented a local search that involved a "pass to fill outside
liberties" move that acted as a stand-in for all nonlocal moves. Maybe
Feng-hsiung has something similar in mind. For programs that read out
local goals in the first place, it's natural to implement some method
-- lambda proof-number search with inversions, as in Thomsen's MadLab,
is probably one of the better ones -- to insure you're not searching
the whole board just to solve, say, a lousy crane's nest
(http://senseis.xmp.net/?CranesNestTesuji). I think Mogo and
CrazyStone do not do this, instead using very good whole-board vision
to compensate for relatively weak local tactics.

Even MadLab can be slow to solve the kind of tactical problems you
would think it. MadLab's search is admissible (though a bit buggy in
case of ko), and it seems that admissible search is often very hard
even when making a guess that is probably right is easy. With many
harder problems (MadLab did solve some some tricky, let's say 3 dan
level, problems very quickly, when the key variation stayed reasonably
narrow all the way to the end) I concluded that MadLab was finding the
tesujis that you would normally call the "solution", but then getting
bogged down in the easier (to human eyes) life and death problem of
mopping up cut-off chains. There are endless practical examples of
easy to guess, hard to prove positions, with wide-branching (even
after narrowing the search region down to intersections that really
matter), deep, boring, straightforward grinds towards inevitable
victory, where a glance or 100 Monte Carlo simulations might reveal
the correct answer. For example, can a black stone in the center of an
empty 19x19 board live? Of course the answer is yes. Okay, now try to
prove it -- or don't, because it's my bet that even with computer
help, no one will succeed in doing so in the next five years. In
running battles with sketchy boundaries and nothing resembling an eye
yet, you can usually forget about trying to prove who will win. (If
the aforementioned stone in the center of the board had the 17x17
region above the first line all to itself, it might still be dead --
strong players say that if just the border of the 19x19 board is
filled with stones of one color, then with correct play by both sides,
the other player cannot live anywhere inside.) Even in the closed and
semi-closed go problems the Smart Tools team examined in their paper,
they said (I'm paraphrasing from memory, but I hope I get the gist
right) that often, proving the correct answer with their tsume-go
solver took far longer than just being 95% sure. Similar issues also
arise in chess, but are easier to handle within a classic alpha-beta
framework -- if proving checkmate is hard but recognizing the sure win
is easy, it's usually because one side forces a material advantage,
which even the crudest static evaluator can recognize. If you're
writing a generalize go playing program, there's plenty of opportunity
to admissibly optimize tactical searches, but don't expect tweaking
the admissible elements of your search to the limit to adequately
compensate for lack of guessing skill when proof is not practical,
even if  the search is meant only for clearly tactical problems and
not for direct application to opening play, strategic decisions, or
loose positions.