[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: computer-go: [Question] Alpha-Beta Pruning & Null Move
At 05:38 PM 4/25/2001 +0200, Mark Boon wrote:
Don's description of 'null move pruning' is what I thought it would be. I
used something similar in Goliath as one of the criteria to stop reading
certain variations. It had rather vague concepts of 'urgency' and
'stability' to decide whether to (continue to)read in a certain situation or
not. The original driver was that static evaluation turned out to be almost
useless in situations that are not stable. So unstable situations had to be
read further. One of the ways to determine whether a situation was stable
was to allow one side to move twice and see if it would lead to an
unacceptable result for the side that 'passed locally', taking into account
the average value of a move for the side that 'passed'.
Many Faces's static evaluation includes a measure of stability, or confidence
in the result, and I use that, rather than null move, to decide to keep
reading.
In tactical reading, a pass is also sometimes allowed but I wonder if it can
be regarded as a null move. It is used to prevent one side of being forced
to play and actually make his position worse because the only moves
available to him are filling his own liberty or filling his own eye.
Many Faces also uses pass during tactical reading. As you say, this is
required to avoid filling your own eyes, or filling a common liberty in a seki.
One of the best usages of null moves I find in the endgame. Sente moves are
generally doubled in value. To find out if a move is sente, try moving twice
and see if the result gets doubled or more.
Does anyone actually have experience with making a program play endgame
properly? I have briefly looked into it using brute-force in a local
situation, but wasn't very successful. What I wanted for example is a
program to be able to see that the value of a gote move would be higher than
evaluated if it could be followed up by a profitable sente sequence. This is
a very basic technigue that even most kyu players master, but it seems
surprisingly difficult for programs. A slightly more sophisticated
technigue, which I also thought to be easy for computers, is to evaluate
what gote moves either side can make locally, see which side can make the
bigger move and award that side half of the difference. (For example, if
black cannot make any points, but white can make two points, evaluate it as
one point for white.) After a months worth of work the results were still
very poor so I wondered if anyone else tried.
I handle the endgame with patterns that suggest move sequences, and the
values of
the moves in the patterns include gote and sente followup sequences. Since
these
values are set by hand in the patterns, they only work for those endgame
situations
where I have made a pattern. I have about 400 endgame patterns, and with
that it
plays the endgame reasonably well.
I think Martin did something with reading local endgame sequences...
Mark
David Fotland