DF: thanks for the link to this new (to me technique). I'll implement it
soon.
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.
DF: how many ply is your usual search? I'm getting 3 to 6 ply in the main
search, but the quiescence search often adds another 3 to 8 ply. The Q
search has almost all the nodes.
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
DF: patterns are really important. I don't have "bad move" patterns since
there are almost no absolutely bad moves. I use patterns to generate moves,
and only try moves that are suggested by a pattern. Weak moves are just
moves that have no pattern to suggest them.
What seems to be the case in GO is that you can be a lot more
liberal about pruning moves without hurting the search.
DF: yes, this is true. There are usually a small number of tactical moves,
based on life/death or local shapes (say to defend the border of a
territory), and a lot of quiet moves with very similar values. If you find
one or more tactical moves you can prune all the quiet moves. If there are
no big tactical moves, then there will usually be many good quiet moves, so
as long as one is in the set of moves you try you will get a similar result.
DF: for example, go books make a big deal about where to extend along the
side, or when to play in one corner or another, but the difference between
these various moves is usually only a few points.
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.
DF: this is what I meant by "internal iterative deepening". When there is
no hash table entry, I do a iterative deepening search from this position
rather than just depending on the move generator for move ordering. Do you
mean that I should do a less deep search?
> ManyFaces12 uses:
>
> -Iterative deepening, with hash table
>
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.)
DF: I don't have parity issues. The evaluation function is tuned to avoid
the problem (so it's not just a simple sum of the ownership of each point on
the board).
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.
DF: I know about MTD(F), but I prefer PVS since it's simpler. I want
something I can debug :)
> -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.
DF: Null move works really well for me. My main search move generator is
very expensive (because it has to do a full life/death evaluation), so null
move has the extra benefit of avoiding move generation.
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.
DF: Killer should work well since a big tactic is not affected much by other
moves on the board. My move generator usually finds the big tactics, so it
won't help me as much.
> -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.
DF: this is important, and a big part of my evaluation and move generator.
I don't think you can do "clearly dead" with a small playout since it is so
shape dependent. If a group has a single 5 point eye, it takes a lot of
search to find out if it is a single eye or multiple eyes. It's even worse
in typical positions because often a group is strong only because it can
capture an adjacent group. The key here is counting liberties. If 1 group
has more liberties (in the go-semeai sense) it will win. Counting liberties
is much easier than search (but you have to account for eye counts, common
liberties, connections with throwin, etc). The proper rules for counting
liberties are well understood and described in many beginner books.
DF: don't forget that you need to make sacrifice and Atari moves from dead
groups to make a dead shape to kill an enclosing group.
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?
DF: I prefer alpha-beta to UCT because the evaluation is so slow. Since I
only do about 100 evals/sec, my tree is pretty small, and I don't think I
can get the statistics needed for UCT.
- 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
> [email protected]
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
