Quoting Petr Baudis <[email protected]>:
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
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
