Author: Gunnar Andersson
Date: 01:32:29 08/30/99
Go up one level in this thread
On August 29, 1999 at 17:19:24, vitor wrote: >all i know about probcut by michael buro is that its some sort of extension or >pruning heuristic. i would appreciate if anyone could explain it. thanks. It's a way to selectively prune branches of the game tree. I use it in my Othello program Zebra in the following way: * First, the standard deviation between search results from different search depths are determined for positions from all game stages. I.e., for each pair (DEEP,SHALLOW), the st.dev. of the difference between result from DEEP-ply search and SHALLOW-ply search are computed. In this offline procedure, full alpha-beta is used. As the branching factor in Othello is quite small (6-18 in top games), the highest value of DEEP I used is 14. Evaluation functions for Othello typically estimate the final disc difference; the standard deviations are a couple of discs (< 5) for all pairs (DEEP,SHALLOW) I tried (up to (14,1)). * During the search, Probcut is used as follows: Suppose we want to search the window [a,b] to DEEP plies. Then we first search [b',b'+1] to SHALLOW plies where b'=b+c*sigma where sigma is the standard deviation and C is a magic constant (I use 1.1 in Zebra). If this search gives fail-high a fail-high is reported for the DEEP-ply search. If not, [a'-1,a'] is searched to SHALLOW plies where a'=a-c*sigma, and if this gives a fail-low, then a fail-low is reported for the DEEP-ply search. Otherwise, a standard DEEP-ply search is performed. * You will want to use several (DEEP,SHALLOW) pairs in the search and use the corresponding sigmas (which are game-stage dependent of course). In fact, you can use (DEEP,SHALLOW) values for which you haven't been able to calculate the standard deviations - extrapolating relevant standard deviations give useful values anyway. This way, I use DEEP values up to 18 in Zebra. The reason why ProbCut works so fine in Othello is probably that the game isn't quite as tactical as chess or checkers. A requirement seems to be that the evaluation function is of high quality - also within the domain of Othello, many people have reported ProbCut hurting performance. All successful implementations of ProbCut are using evaluation functions where all parameters have been calculated using various regression techniques. / Gunnar
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.