[Computer-go] Semeais

[valkyria at phmp.se]

Quoting Petr Baudis <pasky at ucw.cz>:

>   Hi!
>
> On Thu, Jan 13, 2011 at 12:52:58PM +0100, Kahn Jonas wrote:
>> By the way, has anybody tried the most basic way to settle semeais in
>> playouts? I mean:
>> * Spot semeais (not basic at all, but probably necessary for almost all
>> approaches).
>
>   I think one problem is, most programs use only chain information, not
> group information (well, "group" is chain in Pachi lingo, but that is
> rather unfortunate historical remnant) - then, in many cases part of an
> eye will be considered a different group, etc. Another problem is that
> during simulation, most programs do not judge chain _safety_ at all;
> they do not check if it can live independently, is seki, is making
> nakade within larger group (Pachi checks this newly now), or is in
> semeai. The problem is, this kind of analysis is very expensive. It is
> difficult to code it without many bugs in the first place, it will bias
> the simulations even worse than now if inaccurate, and it is very slow
> so it must work well even with small number of playouts.
>
>   (Maybe Zen and Valkyria are doing high-level analysis like above,
> though...)

Valkyria does some high-level stuff but perhaps it would be more  
accurate to call it medium level stuff. Nowhere in the code will  
Valkyria represent full groups that are connected tactically for  
example. This is not possible in the playouts. But see below for some  
ideas, what I do for one type of semeai and perhaps can one extend  
this idea to semeais in general.

What I try to do in Valkyria is to detect particular shapes that could  
be an indication of a critical semeai for example. In general I follow  
a lazy computation approach. There always some cheap tests so that  
when the patterns fires the complicated code are called only for a  
small number of cases.

The drawback is that one cannot really do any general algorithms this  
way. There are thousands of special situations in go and each  
situation has its own "trigger pattern" and it is own code to make  
sure a move can and should be played (or pruned I do that in Valkyria  
as well).

For an example of where the most complex computing in the current  
version of Valkyria take look at this game from Little Golem

http://www.littlegolem.net/jsp/game/game.jsp?gid=1226980

Valkyria lost this game despite spending 10 minutes per move for most  
of the game.

In this situation there is a semeai with an eye. The old version of  
Valkyria could not play the white approach move correctly before the  
liberties were filled, so the monte carlo evaluation failed totally in  
this game.

The black group with the eye is easily detected and whenever this  
happens some special code is called that then marks up all liberties  
of the surrounding white blocks that are critical to the semeai. Later  
when the liberties of the any of the surrounding white groups change  
this semeai is reevaluated and if the position is critical a move to  
capture the black stones is generated.

This  scheme means the board representation is updated in the normal  
Play(pos) procedure with some semeai information for this kind of  
special cases. It does not slow down Valkyria much because the test  
(to find the eye and the suicide this need to be present for this  
particular situation) does not fire so often in the playouts. The  
Tactical() function that returns forced moves checks the board  
representation to see if there are any critical semeai moves of this  
type. Normally all "tactical" code goes into the tactical() function  
that checks for local forced moves to the two last moves, but I found  
it was not possible to do that effectively and I had to do the  
updating in Play(pos) for the board representation because the  
sensitive liberties needs to be updated for each move in the playouts  
to ensure no mistakes are made. The tactical() function does not have  
any state remembered from move to move.

I think I could probably extend this scheme to other kinds of semeais.

The thing is that to make it efficient one needs to compute the  
complicated stuff in a lazy way. So one needs to identify the possible  
critical situation.

Perhaps the best way to handle semeais is simply to have a rich board  
representation that includes updating all *possible* semeai (just as a  
liberties as well as suicidal and illegal moves are kept updated  
accurately all the time for Valkyria). But doing so effectively and  
error free may be really tricky.

At first such a program would probably be very slow compared to other  
new programs and appear very weak in testing. But it may indeed it may  
be necessary to be able to handle all positions in 19x19 Go correctly  
in the playouts. When the playouts have a blind spot the number of  
playouts does not help at all.

Valkyria also do a lot of correct stuff for 2 and some 3 liberty  
semeais, but these are then more programmed in usual pattern->action  
way without any special representations. The trouble with semeais is  
that locally the correct move or the last threat is just a simple dame  
filling move so it is impossible to make pattern->action thing work  
unless the liberty count is small.

Eyeshapes are much simpler because a single eye is usually local and  
one just have to bias the tree part (or play it them in the playouts.  
Valkyria does both) to search critical moves for eyes. Valkyria can  
also detect life if stones has been captured so it will also stop  
attacking eyes if the group is known to be alive. The IsAlive()  
function is a generic function that I sometimes call to avoid playing  
unnecessary moves. But it can only be called in rare cases.

Best
Magnus