[computer-go] 9x9 search, tsume-go (was Re: Computer Olympiad photo)

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Fri, Dec 05, 2003 at 12:00:25PM +0100, tesuji@xxxxxxxxxxxxxxxxx wrote:
> Some of the discussions here seem to belong in a computer-chess mailing
> list rather than here.
> 
> Concerning using brute-force, it's not so unreasonable for 9x9. Generally
> games for 9x9 are one of two types:
> - A whole-board fight from start to finish
> - The board gets divided up fairly quickly in stable parts and it the
> whole game is like a big end-game.
> 
> In my experience, games played by software tend to end up in the latter
> category much more often than the first. So a reasonable but fast
> evaluation combined with brute-force search stands a good chance against
> exisitng software which is designed for 19x19.
> 
> But in games of the first category, just brute-force will stand no chance
> whatsoever. Against any 1-dan player making sure the game develops into a
> game of the first category, a brute-force program won't stand a ghost of a
> chance.
> 
> However, end-game is much more important in a 9x9 game than on bigger
> boards, even in a hectic game. So a program that can do that well will
> always have a good chance against software that was made for 19x19 but
> which is playing on a small board. But only up to a certain level...
> 
> In my opinion 9x9 is such a different game that if as much effort was put
> into it as for 19x19 a reasonable level (1-dan?) could have been reached.
> Probably such programs would be a combination of a good evaluation and
> whole-board search. If you can make a program that can read 10 or 12 ply
> deep (or even more) and still have a reasonable idea about territories,
> eyes, etc. it should do much, much better than any existing program.

On the other hand, quite a lot of effort has been put into solving
tsume-go problems (unsurprisingly, since most strong players believe
"if you want to get stronger, study tsume-go" is largely correct). To
my knowledge the techniques which work (which definitely include a lot
of search!) tend to blow up badly before the solidly enclosed area
grows to 9x9. So while I agree with you (Mark) that the opponent
making a whole-board fight is a key problem for existing software, I
am more skeptical than you are that a reasonable amount of programming
effort targeted at 9x9 Go will overcome the problem. Maybe 7x7...

To me the tsume-go thing is a very interesting contrast to computer
Chess, and I can't help being reminded of it when people bring up the
success of brute-force search in Chess. ISTR Bob Hyatt saying that by
the early 1980s or so, Cray Blitz could blow through an entire book of
hundreds of tactics problems before a human would be able to open the
book and read the first problem. (And whether or not I'm remembering
the quote right, the underlying fact seems about right.) In Go, no one
seems to know how to do anything like that for problems at the level
of _Graded Go Problems for Beginners_ volume 4.[1] (I mean the 90+% of
problems there which have an easy-to-define sharp objective, excluding
problems like #53, "what's the best move" in an early middlegame
whole-board position.) And most of the solution diagrams in _GGPfB_
seem to be 9x9 or smaller.

I think I can speak for a substantial fraction of Go programmers here
when I say that if a Chess programmer slumming in the Go programming
world could use even a week of runtime, executing a search algorithm
recognizably adapted from Chess and not overtuned/overtrained for a
particular problem suite, to solve even the most tractable 80% of a
set of hundreds of problems at that level, we'd be pretty damned
impressed. (And for a smaller, but still significant fraction when I
say that as long as the Chess programmers can't, we'll remain somewhat
skeptical about weakness of Go programs being a reflection of
insufficient attention paid to brute force search.:-)

(I'm aware that people -- including, I think, David Fotland on this
list -- have reported higher than 80% success at choosing the right
move in such problems. But what I mean by "solve" is to arrive at a
100% certain answer, so that the program either returns "this *is* the
move" or "I'm not absolutely sure, I need to think more". That is,
"solve" as pros solve such problems, or as computers solve the
corresponding chess problems.)


[1] or, for anyone (perhaps a Chess programmer?:-) who's following
the discussion and wants to see the point without having to shell out
$20 for a problem book and wait for it to be shipped, the (mostly
rather harder) classical Go problems at
 <http://www.g0ertz.de/uligo/classic.html>
But putting on my 3-dan-who-likes-to-teach hat, _Graded Go Problems 
for Beginners_, all 4 volumes, are very good books, and I'd encourage
anyone interested in Go to buy and read any or all of them unless 
his skills are already too advanced to let him benefit from them.


-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
These suspicions of self-deception about self-interest have empirical support 
in social science. For example, people seem to overestimate their own 
generosity, even though they can accurately predict the generosity of 
others.[cite] People are more generous toward richer relatives, rather 
than those who most need help.[cite] And when choosing whether to base 
generosity on relative effort or output, people tend to choose differently 
in each situation the metric that costs them the least.[cite]
  -- <http://hanson.gmu.edu/bioerr.pdf>, on intuitions in another field
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go