tor 2005-08-18 klockan 10:58 +0200 skrev Jens Yllman: > > Gunnar wrote: > >> Daniel Jacober wrote: > >> > I'm a student of computer sience in Switzerland. For my AI classes I'm > >> > writing a document about GO. Therefore I also analysed your > >> > documentation and source code. I was particularly looking for the kind > >> > of algorithms you're using. > >> > > >> > One thing I couldn't find out is wether you also use Alpha-Beta > >> > Prunning to reduce the size of the search tree. Could you also tell me > >> > why you're (or why you're not) using Alpha-Beta Prunning. > >> > >> We don't. Historically this is because the reading started with > >> win/lose outcomes only and then alpha-beta reduces to a simpler search > >> which just terminates when a win is found. Later on ko results were > >> added and then alpha-beta would be meaningful, but due to ko results > >> being relatively uncommon we have not found it worth the extra code > >> complexity. Also there's an issue with the caching of read results > >> which needs to contain more information when used with alpha-beta. > > > > However, in my opinion (I am not sure this opinion is shared by the rest > > of the GNU Go team though) we will need alpha-beta in the long run. The > > reason is the following: > > Ko searches have considerable higher branching factor, but they are > > pretty rare. At the current depth settings, this means that they consume > > a small portion of the total time, but this can change drastically when > > depth levels get increased. (In fact, many of the extremely slow moves > > in level 15 or higher reported on this list involve kos.) > > > > The extra code complexity is not negligeable, unfortunately. > > > > Arend > > > Is it not also true that the way moves are selected today is kind of a > pruning. So alpha-beta does not add that much to the pruning. I guess > if/when we get more moves from pattern/heuristics vi might need alpha-beta > pruning. Also I guess that since we already have a pruned set, alpha-beta > might only be bad for our search. > > Am I right or am I wrong. I do not have any scientific facts behind my > statement. > >
Actually, the optimisations I was working on mentioned in http://lists.gnu.org/archive/html/gnugo-devel/2005-08/msg00018.html where beginnings of alpha-beta-pruning for the reading code. I stopped dead when I ran across the caching/hash problem as I could not verify whether the pruning was correct - ideally, it shouldn't change anything but the reading node counts, but with the caches giving bogus results every once in a while, I could not check this. Nevertheless, with regression breakage that was pretty small, indicating that I at least was pretty close to a correct implementation, I got reading node count decreases by about 8%. Impact on time was negligible, but at least the additional complexity didn't result in a slowing down that was higher than the gain from pruning. Timing results on my machine are rather imprecise, though. /Martin _______________________________________________ gnugo-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/gnugo-devel
