Re: [computer-go] Alpha-beta and computer go.
Additional info: Also, I changed the late move reduction algorithm to make it more correct. Here is exactly what I do: 1. At any node - I first must try 3 moves before considering anything else. 2. Additionally, I try captures even if I've already tried 3 moves. 3. Otherwise, I reduce the depth 2 ply. 4. If 2 ply search returns a score alpha, I re-search to full depth. 5. If a reduction produces a 0 ply search or less, I simply call the evaluation function. I reduce 2 ply to deal with the parity problem. However there is still a parity issue in some cases when the reduction parity doesn't match the re-search parity - so this may not be my final formula. I generally test everything I try so I usually don't get answers for at least a day or two. - Don Don Dailey wrote: 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 I want to clarify this.FooBar is currently doing fixed 3 ply search and not looking at the time clock on CGOS time-controls. BUT, this is for 9x9 games. It occurred to me that you might be talking about 19x19 games which I haven't tested. I don't currently use any form of quies because my evaluation function consists of N play-outs, where N might be around 100 - 200 play-outs or so. It might still be useful to have a layer that deal with difficult to resolve situations but with play-outs you don't need quiescence the same way you would with a static evaluation function that is relatively naive about tactics such as a chess style evaluation function. Sometimes FooBar has 2 or more minutes left at the end of a totally played out game doing fixed 3 ply searches. A lot of the time is taken up by just 3 or 4 early moves and most of the 3 ply searches return very quickly - so FooBar would be doing a fair number of 4 ply searches in the middle game if I had time-control.I'll fix this soon, hopefully it will give a nice improvement - I hope to get about 50 ELO or more for this. To get even time management I may have to sacrifice 2 or 3 of the 3 ply searches to get a more 4 ply searches. I can do 5 ply searches in about 85 seconds per move on average - it varied from about 40 seconds to 200. I did this estimate with 10 middlegame positions. The branching factor seems to be about 3.5 per iteration.I'm going to test this to 7 ply later. *DEPTH TIME BF - - - 22.2 - 37.93.6 4 24.33.1 5 84.73.5 * ___ 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/
RE: [computer-go] Alpha-beta and computer go.
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.
Re: [computer-go] Alpha-beta and computer go.
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
