David,
There are many variations of this technique, but what they all have in
common is the assumption that once you have searched some number of
child moves (perhaps 2 or 3) then (with good move ordering) there is
much reduced chance than one of the remaining moves will be
useful. Often the remaining moves are searched with reduced
depth. Also, most programs have constraints on this (don't reduce
checks, out of checks, attacking moves, etc.) Some programs limit
the total number of reductions in a given line.
This is sometimes called "history reductions" (not a very accurate
description in general) because some programs use the history heuristic
and prune moves using this same basic technique but based on having low
"history scores." Some programs only reduce a few ply from end
nodes.
The implementation details vary significantly from program to program
and the prejudices and superstitions that we programmers carry over to
our programs.
But this is considered one of the major recent advances in computer
chess - and just about every chess program jumped in strength 50-100
ELO all of sudden when this started to be used.
In my alpha/beta searcher a very simple minded version is actually
working very well - it will take weeks though to test and refine
this. The only thing I am doing now is:
At any given node ...
If less than 4 ply remaining ....
if move is not a capture ....
if at least 5 moves have been tried ...
do not search the subtree.
This probably wouldn't work in Chess without better conditions. And
it can probably be improved a lot GO too, the next thing I will do is
(at the very least) include (not prune) atari moves.
I also have a nice set of patterns inherited from Lazarus. I set the
strongest version of Lazarus to do deep searches and kept ELO ratings of
the 20 points patterns (5x5 with corners cut off.) This produced a
nice set of patterns and I use this mostly for finding silly moves.
I will probably add to the conditions that all strong patterns should be
played no matter what.
Right now I use weak patterns to "veto" moves from the tree. If a
move is below a given rating I don't even try it if I am on the last 4
ply of the search. All of the patterns fitting this critiera represent
moves any player would consider pretty weak 99% of the time, such as
moving into the corner point when nothing is happening. The most
common pattern pruned is moving to an edge when nothing is nearby.
What I really want to find is a more general way of identifying weak
moves. What seems to be the case in GO is that you can be a lot more
liberal about pruning moves without hurting the search. Amazingly, at
the same depth, using the veto patterns along with selectivity
simultaneously made the program stronger and faster. Normally you
don't get both at the same time because you are dealing with
trade-offs. In this case, I think the veto patterns probably
strengthen the program because of the noisy evaluation function. I am
basically making it impossible (at low depth levels) to play a "bad"
move. For instance moving to a1 in the opening, although very
unlikely is possible with a MC evaluation function but when I use the
patterns it is impossible.
I have more comments in response to yours:
David Fotland wrote:
> Hi Don,
>
> I never heard of this technique before. Are there any more you can share?
>
Since you are using hash tables, I assume you are aware of ETC
(Enhanced Transposition Cutoffs.) ?
For anyone unaware - it works like this:
1. If a hash table entry does not exist for a given move.
2. Do a quick search of the children - in the hopes of finding a
cutoff.
At interior nodes it's cheap and it will provide a cutoff sometimes when
a direct cutoff is not in the table. If it does not provide a cutoff
it might be used to narrow the alpha beta window.
> ManyFaces12 uses:
>
> -Iterative deepening, with hash table
>
My experimental alpha/beta searcher doesn't even have hash tables
yet. I have to think about how to implement this because scores are
probabilistic. Even worse, they can be based on varying numbers of
play-outs since I stop play-outs early when it appears that the score
will not shrink the alpha beta window.
I will probably first try a version that pretends none of this is an issue.
Do you have "parity" issues in ManyFaces? This is a problem in GO
with a MC evaluation function. An odd ply search seems to return a
substantially higher score than an even ply search, and it seems like
you cannot compare an odd to an even ply search. This affects the
hash table implementation signficantly because you cannot take a cutoff
based on scores of a different parity. (at least not without a
"slop" margin.)
I'm currently trying to find a workable scheme to deal with this. It's
even a worse problem with MC evaluation because of the nature of
mini-max - the highest scoring move at end nodes tends to gravitate
towards a move with more error. (I think this could explain why
selectivity may actually give more realistic evaluations at end nodes -
not as many choices, so less chances to find one grossly in error.)
> -Zero-window search (beta is alpha+1, and research when fail high)
>
Currently I'm doing straightforward alpha beta with no aspiration
search. Again, this is more dicey with a fuzzy evaluation
function. If a zero width window search fails high - it might not
fail high on the re-search!
I will still probably try it but I will have to "play silly games" with
the search.
Do you know about MTD(F) ? Although hardly any programs use it, it
is a win. All searches are zero width and you have a driver that
"zero's in on the correct score" so it's rather like a best first
search. You must have hash tables for this to work but it's quite
effective and it has always given me about 10 - 15 % over even PVS
search.
I think it's not used much in chess because it can be tricky. It's
conceptually trivial, but it ends up being a little tricky to get
right. One problem is that it can be tricky getting a nice looking
principal variation because EVERY search is a search failure. That
problem is solvable but there is trickiness. In PVS your principal
variation is always formed from scores inside the alpha beta window.
Another reason it may not be used in chess is tradition. You don't get
the conventional display of information since each iteration is composed
of many re-searches. So you don't get move list countdowns and the
same move may get selected many times even during the same
iteration. So it's definitely not traditional chess program
friendly. It's probably less human friendly reporting information as
a result.
CilkChess used this and it was actually implemented by the Aske Plaat,
the researcher who formulated the idea and was a postdoc at MIT when I
was developing the program.
MTD(F) may actually work pretty well with the way I'm "cheating" with
the evaluation function in the experimental alpha beta searcher - we
will see ....
> -Null move (reduce depth by one, only try null when beta is not infinite,
> only one null move allowed per variation)
>
How is this working? My sense of this is that it would work well in
GO if your program is not overly dependent on life and death via global
searching. In other words, if it has good life and death in the
evaluation function.
I haven't tried this yet the MC searcher. There really isn't much to
try until I can get reasonable depths and deal with the parity problem.
> -Try null first, then the best move from the previous iteration (from the
> hash table), then moves in the order suggested by the move generator. The
> move generator gives a pretty good ordering since it estimates the number of
> points gained by the move.
>
I'm sorting moves by the pattern scores and I think it works well with
the pruning algorithm I described - it increases the chances that the
strongest patterns are tried first.
I also use the killer heuristic which seems very effective. I haven't
really gotten into heavy tuning - I suspect my move ordering is far from
optimal but I will get into this more when I implement hash tables.
> -Full ply extension when there is one forced move
> -Fractional ply extensions
>
I will experiment with extensions for atari moves and perhaps captures.
I want to identify serious atari and capture moves from unimportant
ones. It seems silly to extend an atari or capture move of a group
that is clearly dead anyway.
So one thing I have in mind that I am pretty hopeful of is to do a
preliminary small "play-out" analysis at parent nodes to do the
"territory mapping thing" which will provide great help for move
extensions, pruning and move ordering.
> I plan to add:
> -2 killer moves, then history heuristic
>
Killers seem to work very well. History, not as well - but each
implementation is different, perhaps it will work well for you. I
have found that global table with good moves in the right order works
very well - and you can just modify this original move list. I'm
not yet doing it here in the specific program, but it worked well in a
previous go alpha beta searcher.
> -This pruning idea from Don.
> -Internal iterative deepening
> -Some kind of iterative widening
> -narrow search window based on result of previous iteration
>
> Today I search 20 to 40 moves at the root, then 10 moves per ply during the
> main search, then a tapering quiescence search with no maximum depth.
>
> I find developing search code less satisfying then working on the evaluation
> function. If I add knowledge to the evaluation function I know the program
> is stronger. When I make a change to the search parameters I can only test
> to see what happened. It's a much more trial-and-error process.
>
I hate tuning the move ordering. It's just busy-work for me. You are
mostly just running timing tests and trying things in different
combinations - what a pain. But you have to do it.
> Still, I have to do it because global search makes the program much, much
> stronger.
>
I have often wondered if it would be possible to take a more
conventional evaluation function (like in ManyFaces) and apply the basic
principles of best first searching, perhaps a hybrid of UCT. Instead
of playing random games to the end you just apply the evaluation
function in a straightforward way and handle the tree portion pretty
much like UCT. You still balance exploitation and exploration like
UCT. Have you considered such an approach?
- Don
> David
>
>
> -----Original Message-----
> [EMAIL PROTECTED] On Behalf Of Don Dailey
>
>
> The various versions I'm testing are selective, I use a technique
> similar to that used in modern chess programs of aborting the search
> at a given node after only a few children nodes have been tried when
> the expectation remains below alpha.
>
> There are many potential tricks that can speed up the search greatly
> and I've barely scratched the surface, but I have done a couple of
> simple basic things that appear to be working very well.
>
>
>
> _______________________________________________
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
