Re: computer-go: new topics

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

> 3) David Fotland.  You have been a generous contributor to this group over
> the years.  We doubt that you have stopped innovating and we doubt that you
> have changed the way you feel about the computer-Go community, so out with
> it.  What are your latest innovations?
I've been spending most of my time recently fighting with the public 
schools to get my
son an appropriate education, unfortunately.

Many Faces is stronger recently, and I think there are two reasons.  One is 
the full board
life and death search.  I enhanced it last year to make the results a 
little more stable, and I
continue to fix bugs.  When it wins, it is often because it kills 
something.  The life
and death search runs first, before any other look-ahead.

The second is that I removed most code related to "Urgent moves".  I had 
followed the
go proverb that urgent moves come before big moves, and had marked certain 
shape
moves as urgent.  I realized a couple of years ago that that was a 
mistake.  Urgent moves
come before big moves, only because they are bigger :)  So if the value of 
a move is accurate,
there is no need to distinguish urgent from big moves.

This month I'm throwing out all of my full board look-ahead code, and 
rewriting it (or refactoring, to
use the latest computer science fad buzzword :)  Now that version 11 is 
shipping I can
make some major changes.

My old full board search algorithm was to play sequences from the Joseki 
library or pattern database,
followed by a full board quiescence search.  The quiescence search first 
made local moves based on shape
and local tactical stability, then made moves to kill or save unsettled 
groups anywhere on the board.
There was special alpha-beta code that referenced the Joseki library, and 
separate code that referenced
the pattern database, and a common quiescence search.

A problem with this search was that the quiescence code didn't have access 
to the move trees developed
by the full board life and death search, and often tried inferior 
moves.  Sometimes the program clearly
understands some life and death fight for several moves, then tenukis and 
gives it up.  This is
why.

Rather than try to add more complexity to the existing search code, I 
decided to simplify it into a
single alpha-beta search, with multiple move generators.  I wrote the new 
code in parallel
with the old code, thinking that I would start with code that did exactly 
the same search, to
debug it, then modify the new code to add the new functions.  Of course 
immediately I found
a few major bugs in the old code :)  So there is some merit to coding an 
algorithm twice,
and comparing the results...  As of today, the two pieces of code are not 
very close to searching
the same, but maybe in a few weeks.  When this change is done, you will see 
it back on IGS,
for testing.

David

PS, as for 5x5 go, I think it's interesting, but I wouldn't use retrograde 
analysis, and one bit per
position.  I don't think searching the full tree from the beginning is that 
hard, if you are able to
easily recognize terminal nodes.  For example, we know that after black 
moves in the center,
white can't live, so if you recognize the position after the first move as 
a win for black, the
perfect game tree only has one node in it :)  If you want to be a little 
more thorough and use
Benson's algorithm to recognize when black is won, and alive, and have a 
reasonable move
generator, I still doubt there are more than a few billion nodes in the 
tree.  Since black has
such a huge advantage, it unlikely you need to look at more than 1 move 
when black moves,
and 10 to 15 ply should be enough to prove a result.  At 15 ply, the number 
of leaf nodes is
24*22*20*18*16*14*12 ~= 500 million.  Symmetry of the first white move 
reduces this by a factor
of 8, and a transposition table will reduce it still further.

The only problem with trying to solve 5x5 go is that we already know the 
answer, B+25.  7x7
go is much more interesting.  I think it is also solvable using forward 
search, but is much
more difficult.