> 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. Jens Yllman _______________________________________________ gnugo-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/gnugo-devel
