Re: computer-go: 5x5 Go is solved?

["Andrew Derrick Balsa" <andrebalsa@xxxxxxxxxxxxxxxxxx>]

Hi Stefan,

To answer your question: yes!

Here is the definition, quoted from wikipedia:
(http://www.wikipedia.org/wiki/Solved_board_games)

A two-player game can be "solved" on several levels. 

1) In the weakest sense, solving a game means proving whether the first
player will win, lose, or draw from the initial position, given perfect
play on both sides. 

2) More typically, solving a game means providing an algorithm which
secures a win for one player, or a draw for either, against any possible
moves by the opponent, from the initial position only. 

3) The strongest sense of solution requires an algorithm which can
produce perfect play from any position, i.e. even if mistakes have
already been made on one or both sides. For a game with a finite number
of positions, this is always possible with a powerful enough computer, by
checking all the positions. However, there is the question of finding an
efficient algorithm, or an algorithm that works on computers currently
available.

On Sun, 20 Oct 2002 20:57:43 +0200, "Stefan Mertin"
<stefanmertin@xxxxxxxxxxxxxxxxx> said:
[...]

> Perhaps I am too much player (of modest strength) and
> not enough mathematician, but arenīt there lots of 
> very interesting possible positions in 5x5 Go that 
> your program doesnīt cover...?

That is the strongest sense (3) as defined above. Erik's solution is (2).
> 
> I think e.g. of all the very fine 5x5 ploblems in "GoWorld"
> or of all the perhaps even more interesting games, were 
> black is not allowed to put his first move in the centre!
> 
> What I really would enjoy is a program that tells me in 
> (nearly) ANY position something about EVERY move - 
> at least if it is a winning or a loosing line or jigo.

That's another approach, which one can describe as "brute force". Erik
used a more selective approach which enabled him to find a solution in 4
hours on a single PC.

Each type of solution has a different application and/or usefulness. Go
Perfect play on 5 x 5 was already solved, if I understand it well, but
Erik's solution has the merit of being an elegant way to reduce the
problem to a manageable size.

BTW does anybody have an English translation of the original article that
described the previous solution?

Thanks, 
Best,
--
Andrew D. Balsa
andrebalsa@xxxxxxxxxxxxxxxxx


--
http://fastmail.fm - Or how I learned to stop worrying and love email
again