computer-go: Understanding lookahead revisited

["GL7: David Elsdon" <gl7@xxxxxx>]

Hi

It's over a year since I asked about lookahead (why does it work ?) and
received a wide range of responses. I thought I'd do some empirical
research into the problem tosee if that helped my 
understanding.

I do a minimax search (with alpha-beta cutoffs), no pruning, no
quiescence searching. I build a game tree from a root node having value
R. The tree has uniform branching factor B and depth D. At each node I
assume that the best move leaves the value of the position unchanged, the
next best move reduces the value of the position by 1, the next by 2 and
so on. I clobber each position's actual value to give an evaluation
value. The evaluation values are normally distributed with a mean of the
actual value and a standard deviation of S.

With this setup I have investigated a huge number of game trees and
played with the values of R, B, D and S. I found that lookahead is very
useful. The deeper you look ahead the more likely you are to find the
best move. I have given the mean of the backed up values (at the root
node) and the standard deviation of this value in a couple of examples of
my investigations below:

1000 tests: branchingfactor
B=7 root value R=7 standard deviation S=17
Depth | best move | 2nd best | 3rd best | mean root   :
standard 
      |   chosen 
|         
|          |
evaluation  : deviation
  1   |   183    
|   201    |   145   
|  26.88345   : 10.86960
  2   |   217    
|   207    |   162   
|  -2.37967   : 5.694094
  3   |   297    
|   194    |   164   
|  21.47438   : 3.553388
  4   |   392    
|   250    |   177   
|  -4.91499   : 2.112542
  5   |   489    
|   274    |   162   
|  19.98318   : 1.479812
  6   |   594    
|   267    |   111   
|  -5.42937   : 1.124261
  7   |   707    
|   228    |   
56    |  19.74062   : 0.905707
  8   |   771    
|   200    |   
25    |  -5.56029   : 0.766832
  9   |   790    
|   186    |   
23    |  19.64960   : 0.652859

1000 tests: branchingfactor B=37 root value R=7 standard deviation
S=17
Depth | best move | 2nd best | 3rd best | mean root  : standard
      |  chosen  
|         
|          | evaluation :
deviation
  1   |   102    
|   107    |    
87   |  31.07319  : 9.184497
  2   |   205    
|   175    |    133  
|  -8.45302  : 4.145862
  3   |   362    
|   220    |    162  
|  25.64635  : 2.518201
  4   |   457    
|   285    |    148  
|  -10.1639  : 1.599545
  5   |   570    
|   284    |    
99   |  24.82316  : 1.183593


In the first test the chances of picking the best move increase
from 18.3% with a one ply search, up to 79% chance with a nine ply
search. In the second test with a wider tree the results are even more
impressive.

The difference between the backed up values from odd and even plies
indicates that  handling lookahead on unbalanced trees needs some
care. 

I do have a lot more results lying around and can easily perform other
experiments if anyone has some suggestions.

My feeling is that the relationship between the distribution of values
across the successors to a particular node and the error function is
particularly important. I am not convinced that a normal distribution is
the right one, but it seemed a good place to start. In reality I am sure
that both the  distribution of values across the successors to a
particular node and the error function are dependent on the position and
the evaluation function. For example, some evaluation function may
exhibit a particular error distribution when the position involves a big
semeai.  

Comments, suggestions ?? Confirmation - or refutation - of my results
would be welcome.

Cheers

David