Introduction

[Matt Gokey <mgokey@xxxxxxxxxx>]

Hello everyone,

Thought it was about time I introduced myself to everyone.  I was
introduced to the game of Go only a month or so ago and immediately
found it fascinating and started working on a program.  I'm a software
developer for a financial services company located in Wisconsin, but
always enjoy a good programming exercise as a hobby outside of work.

All I've done so far is board management, rule enforcement, basic
scoring, data structures and algorithms for the basic objects, designing
a user interface, etc.  Initially, I started working on an engine for
play, until I quickly gained more of an appreciation of the problem
domain.  I've decided I'm not going to put any great effort into doing a
multitude of things already tried, though it would be fun and quite
challenging.  I've been reading this list's archives recently, studying
anything else I can find about the game, and playing some too.  The
amount of work that has been put into this game is staggering and the
outcome quite humbling, to us all I think (IMHO).  This is a challenge
worth working on !-)

Anyway, I'm hoping to provoke more discussion about computer Go methods
so that I can listen to the wisdom that all of you have acquired over
the years and possibly open up some new lines of discussion.  Reading
the archives, its obvious everyone is willing to share research, ideas,
methods, databases, even some code.  But even after only studying the
techniques used to date over the last few weeks, I want to back up away
from the problem to gain a fresh perspective and try to think "outside
the box" as the saying goes, so I'm not interested in discussing
specific techniques and algorithms (not the hardest part anyway), but
rather general concepts, hopefully some fresh ones.  So here goes...

We all know why Go is so hard for computers and why Chess is so easy
(comparatively), but consider this:  Imagine trying to write a chess
program that plays using the techniques being employed for Go, that is
primarily static evaluation using heuristics, rule sets, pattern
matching, goal directed searches but allowing no full tree searches as
we are restricted to in programming Go because of the search space and
lack of a reliable position evaluation (My apologies for the exaggerated
simplicity - the work done so far is quite impressive).  Would we get
anywhere (i.e. master level) with this approach?  Thoughts, comments,
anyone?

Some of this has been tried in the chess domain and has failed there as
well I think.  It doesn't seem possible to handle the subtle variations
in position using techniques like this in many complex games (Chess,
Checkers, Othello, Go, etc.).  The only good way to truly "read a
position" seems to be to play it out to a reasonable depth.   How can
one predict future positional characteristics accurately using only the
current position?  I don't think it's possible.?  Anyone disagree?

Having said that and given the fact that people do not play chess the
way computers do, and people do not play Go primarily by reading out
variations (although because the board remains static as compared to
chess, its easier to read out specific lines of play, if you have to)
how do Go masters play so well?  From what I've read, correct me if I'm
wrong, strong Go players only choose a very few candidate moves and
sometimes read out deep but narrow variations for comparison and
validity.  Interesting - this sounds strikingly similar to how chess
masters choose lines of play.  The point I'm making is despite the vast
differences between Chess and Go, and that Go is arguably more
difficult, there are similarities.   Good chess programs do not play
like humans play and I don't think a good (dan level) Go program will
play like humans play.  The AI progress made to date is simply not up to
the task, and I would argue that we can not develop AI powerful enough
to handle a complex domain like Go using Go.  To develop AI to this
degree we're going to need to start at the beginning, like nature did -
start simply and with stepwise self refinement.  Hard coding the
knowledge - via patterns, rules, special purpose algorithms, etc.  seems
to be working to a degree, but I have read over and over again that the
programs don't really seem to understand the positions and so make
blunders that cause them to lose games.  As the size of the hard coded
knowledge set increases, the difficulty in keeping the consistency and
integrity of the set as a whole, I have a feeling, will increase
exponentially.  In short, I'm of the opinion we can't likely create a
good (dan level) Go playing program by modeling (AI or not) our
perception (probably flawed) of human playing techniques.  What does
everyone think?

I'm not saying that the techniques used to date aren't useful nor that a
Go program could be written like a chess program-it certainly can't, but
I think we need to find aspects of the game of Go that we can exploit
using realistic computational resources.   I'd like to do some research
in new and promising areas but I am not sure what might be worth
exploring.  I have some high level ideas that I will introduce in my
next post, hoping to start a discussion that together may form some
concrete ideas for further research/work.  How about anyone else, have
any new ideas you're willing to share?

I'm hoping this will spark some discussion and am waiting in
anticipation for responses by the world's best go programmers!  Thanks
for listening.

Matt