Re: [gnugo-devel] The Module Formerly Known As Endgame

[Gunnar Farnebäck]

Warning, these comments are sometimes rather negative and
unconstructive but there are some more constructive suggestions at the
end.

Eric wrote:
> What happens if we replace minimax search and
> alpha-beta pruning by more recent search tree pruning
> techniques, e.g. recent advances in AI Planning?

This is a key question. I have no idea but I would be very interested
in the answer.

> We could probably get an increase in the size of the
> board we were able to solve. Say that now we were able
> to solve 5x5 boards.

Actually 5x5 go has already been solved. It was solved two years ago
by Erik van der Werf.

From his announcement:
| Yesterday my program solved 5x5 Go starting with the first move in the
| centre. As was expected it is a win for the first player with 25 points
| (the whole board belongs to black).
| 
| I used an iterative deepening Alpha-beta search (PVS) with:
| - Transposition tables (2-deep replacement scheme, 2 x 2^24 entries)
| - Enhanced transposition cut-offs
| - Symmetry lookups in the Transposition table
| - 2 killer moves
| - History heuristic
| - Benson's algorithm for unconditional live (extended with unconditional
| territory)
| - Heuristic evaluation for positions that are not fixed by benson
| 
| The solution was found at 22 ply deep (23 for the empty
| board).(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz)

> Next, we relax the search goal. Instead of saying "Win
> the game for black", we could say something like "Take
> prisoners". This is entirely reasonable.

No, it's not.

> Surely some Go games must exist in which taking prisoners leads to
> winning. These are the games that the planner will look for.

Occasionally the players get into sharp positions with races to
capture, where the player who loses his stones totally crumbles.
However, it's not easy to provoke such situations (except ones where
you don't have a chance to win). Furthermore just capturing some stone
is almost never an interesting goal, it has to be lots of stones or
the right stones.

(It is relevant to analyze whether each string on the board can be
captured or not, called tactical reading in GNU Go, but that knowledge
is not sufficient to win a game.)

> Because we have a relaxed search goal now, we would be
> able to solve 6x6 boards (i'm just pulling these size
> increases out of thin air). Right? Because we're not
> trying to win the game anymore. In the new scenario,
> "solving" the 6x6 game board just means constructing a
> plan for taking prisoners on that board. This
> relatively simpler goal can (sometimes) be solved with
> less effort.

That may be possible but it has very little to do with getting strong
at go.

> Because we re-plan everytime we want to make the next
> move, now we would be able to solve 7x7 boards. Right?
> Because it is no longer necessary to search through
> the opponent's possible moves! Surely some Go games
> must exist in which it is possible to capture some of
> the opponent's forces that are already on the board,
> without the opponent making any further moves that
> help you to capture him. These are the games that the
> planner will look for.

This doesn't make any sense to me.

> GNU Go extends smaller patterns to the 19x19 Go board
> by looking at all the possible ways that a pattern can
> be placed on the board. But for GNU Go, the pattern
> matching step itself is very inexpensive - a single
> operation, I would guess.

Not a single operation, but it is fairly well optimized and relatively
inexpensive. 

> An idea is to do the search for each dragon that
> appears on the 19x19 game board. Put differently, draw
> a 9x9 square around each dragon, with the dragon in
> the center. Note that some squares may be smaller than
> 9x9 (because some dragons will be on the edges of the
> 19x19 board).

I'm sorry to be harsh, but from a go playing perspective this approach
makes absolutely no sense at all.

> With all of the above being said, I would like to make
> a final comment: One suggestion I got from this list
> is that there is more to playing Go than just taking
> prisoners (I believe it was Gunnar's, but I could be
> wrong).

My comment was about the endgame, but it applies also to the game as a
whole. 

> So that's my whole idea. Seriously folks, this idea
> just needs a little bit of work to make it elegant.
> The foundation is sound.

Sorry, but the foundation is not sound at all.

> In fact, I claim that if we can get even this naive strategy
> implemented, then it would knock the socks off of an exclusive
> pattern matching GNU Go.

GNU Go hasn't been exclusively pattern matching since version 1.2,
which incidentally is way, way, weaker than current versions.

Now to the more constructive part. I can appreciate that capturing
stones is an attractive goal in that it is a well defined task and
easy to understand. However, just capturing random stones is often not
a significant event in the perspective of the whole game. What is much
more significant is reaching the state of invincible (the same as
unconditionally alive in the sense of Benson's algorithm). Although
most games end with only a few, or none, stones being invincible, it
is highly relevant as the goal for a deep search. In fact the most
sensible definitions of life and death in go depends exactly on the
ability to gain invincibility under alternating play. Moreover GNU Go
already has code to determine invincibility as well as unconditional
death and unconditional territory.

With that said I would suggest three different subproblems that you
can consider attacking. Actually the first one is by far the most
important and useful, but maybe one of the last two is more attractive
in some sense.

1. Determining life and death in a fully enclosed position.

While insufficient in itself to get a strong go program, this is a
very important problem. There are lots and lots of test positions
available to evaluate algorithms. There also exists one very good
program dedicated to this problem, Thomas Wolf's GoTools, to compare
against.

Two examples, one trivial and one very hard:

|OOOOO
|XXXXO
|X..XO
|...XO
|X.XXO
+-----

|.OOOO.
|OO..OO
|X..X.O
|X..X.O
|X..X.O
|O..X.O
+------

It is understood that the surrounding white (O) stones are already
invincible and the problem concerns the vertices inside those (16
vertices in the first example and 22 vertices in the second example).
White's objective is to capture all black stones, or equivalently to
make all enclosed vertices into either invincible white stones,
unconditionally dead black stones, or unconditional white territory.
Black's objective is to stop white from reaching its goal, preferrably
by making invincible black stones. One would want to determine the
result with either player moving first.


2. Solving 6x6 go.

This probably wouldn't have any direct relevance for play on larger
boards but it would have a considerable academic value. The idea would
be to solve 6x6 go properly, without simplifying assumptions. This can
be formulated as searching until as many vertices as possible are
unconditionally settled with the aim for each player of controlling as
many vertices as possible more than the other player.

It is perfectly possible that solving 6x6 go is intractable even with
the most advanced algorithms, so I would suggest starting with 5x5 go
and try to improve on the speed of Erik's solution.


3. Tactical reading.

GNU Go already has a fairly good tactical reading module, but it still
wouldn't hurt if it was considerably faster and/or more accurate.

The problem here is to determine whether a specified string can be
captured, without regard to what happens to other stones or whether
the opponent can strike back and capture the capturers.

/Gunnar