David, Just one comment on the ETC. This is not internal iterative deepening. Internal iterative deepening is a technique to find a high quality move that hopefully will give you a cutoff (when it gets searched.) It's a good technique to use but it isn't ETC.
However, ETC will sometimes give you an immediate cutoff with NO search. That's the whole point of it. In other words, if a hash table move doesn't give you a useable score, then one of the children nodes could have a hash table score that will allow you to quit without searching. It's clearly worth checking for and will reduce your tree about 15 - 20 percent. So you look at the children nodes, do a hash table lookup on each of them, and if the depth is right you might manage to get a cutoff without actually searching. You also asked how deep I search. FooBar searches 3 ply deep period because I have no time -control. If I had time control I would be searching 3 or 4 play in the opening and middle game and perhaps 5 or 6 when I get fairly close to the end game. There is no quies, because play-outs by their nature act as a quies search and an evaluation function at the same time. However, it's possible that I could benefit from an abbreviated quies of some kind, perhaps just look at atari moves and their responses or something like that for a ply or two. - Don David Fotland wrote: > 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/
