Why bother with 9x9 Go ?!

[Patricia Hughes and David Elsdon <babel17@xxxxxxxxxx>]

Dear All,

Antti Huima wrote:

> If I understood correctly, David asked for an algorithm that scores
> finished games, not unfinished positions. Some people have implemented
> scoring algorithms for finished games, e.g. Dave Dyer.

That is correct Antti. And I shall be taking up the offer of some C++ code
from from Paul Leonard.

> > Although Antti Huima and you are proposing some "promising" AI method,
> > I still doubt your algorithms will work if you have not calculated the
> > speed of evolution of your programs. 9 x 9 & 19 x 19 are of huge
> > difference -- it's the difference of a chess program and a go program.
> > Why people bother a 9 x 9 board?

> What is `speed of evolution'?
>
> The difference of a chess program and a go program is not in the board
> size. I haven't seen a grandmaster 9x9 go algorithm yet, although
> grandmaster chess algorithms exist. Why shouldn't people bother to
> understand the 9x9 game, as that would clearly lead to deep understanding
> at least of the tactical parts of a go program??
>
> My "promising" AI method (assuming you refer to the idea for acquising
> patterns) is not directly related to board size as it is simply a method
> for mining often occurring patterns from game records.

I'm not clear on what Mousheng Xu means by "speed of evolution". There are
certainly a number of issues involved with going from a successful program on
a 9x9 board to a successful program on a 19x19 board. In the case of a
non-learning program there is the problem of "combinatorial explosion" caused
by search times increasing "non-linearly" with the number of points on the
board. (Here, "non-linearly" can be taken as typical British understatement.)
The other problem is the scale-ability of the the ideas on which the program
is based. My program has no problem with the "combinatorial explosion"
because the computation time for all of the concepts which I use, and all of
my rules, increases linearly with the number of points on the board. So my
program takes 4.5 times longer to play Go on a 19x19 board compared with
playing on a 9x9 board. But, I do have some problems with the scale-ability
of my ideas. However, I expect that the development of rules and concepts to
handle 19x19 Fuseki and Joseki will sort this out. We'll see !!

I do not know what problems learning programs have in moving from a 9x9 board
to 19x19, but I would expect them to come under the same headings of
combinatorics and scale-ability. And clearly different learning techniques
will have different problems. I expect to be working with Dr Andras Lorincz
and some of his sudents at the Eotvos Lorand University here in Budapest to
interface my Go program to a learning system which will use Time Difference
Learding and Function Approximation. I expect to start off with a 9x9 board
here so that the program can first learn the tactics of the game before
moving to a larger board to learn the strategy. So in this situation starting
with a 9x9 board is clearly advantageous in speeding the overall learning
process, just as it makes good sense to teach people on a small board.

Another reason for starting on a 9x9 board is purely pschological. I found
that the thought of writing a Go program for a 19x19 board was too much. I
did not know where to start. So I reduced the size of the problem by reducing
the size of the board. I started with a 5x5 board !!

I now have a program which has a clearly won game against Many Faces (playing
at level 7) on a 9x9 board. Unfortunately, it goes on to lose.

But I'm working on it !!  :-)

Regards

David