[computer-go] Positions illustrative of computer stupidity ?

[Chrilly]

>> I can't help but feel we are missing something.   With UCT we miss those
>> wonderful beta cutoff's that you get with straightforward alpha beta
>> pruning - but with alpha beta pruning you are still exploring a lot more
>> useless nodes.    It seems the 2 are just not very compatible.
>>
>> Currently UCT does seem like the best choice by far.
> Yes, in the current state of the art. What would be great is to understand 
> in
> what extend this would continue to be true if we change the evaluation
> function. What I believe (but this is only intuition, this have to be
> proved !), is that UCT is very efficient in Go because our evaluation
> function is bad. With a good/(very)^+ good evaluation function, alpha-beta
> would become much better than UCT. I think this is clearly the case if you
> can reach the end of the game in the tree for example.
> I don't know if someone tried UCT in chess to see the results. As we often
> assume that the evaluation function in chess is much better than in Go, it
> would be a good test case?
>
I have not tried UCT for chess, but i have tried to combine UCT with the 
Suzie-Eval. Not to the end of the game, but up to 11 plies deep.
I compared this with the standard 4 to 5 Plies Alpha-Beta search.  All 
experiments were done on 19x19 (Suzie runs only at that size).
First of all I had better results with iterative deepening. Searching 
1,3,5,7,9,11 Plies. Each depth was given a fixed node count. Only when the 
best move was clearly better the next iteration depth was started earlier.
It producted reasonable strategic play, some good moves, but the number of 
really bad moves was also higher than with Alpha-Beta. The increased search 
depth and the random nature of the search finds better the stupidities of 
the eval.
I stopped this experiments, because I had/have the feeling that the playing 
behaviour is dominated in all cases by the eval and that I should spent 
effort there. Additionally with a shallow Alpha-Beta search it is easier to 
find the reason of bad moves. One can go down the criticial line and can 
look what went wrong. With UCT this is almost impossible.
I tried out also some sort of Alpha-Cutoff. As long as the current best move 
in a node was good enough to refute the line, no new move was tried out. The 
whole search was a (strange) mixture of the UCT idea and Alpha-Beta.
The Suzie eval is also too slow for statistic sampling on 19x19.


In hindsight I am also from the theoretic point of view sceptical about the 
idea. One probably gets the Austrian-Opinion-Poll problem. It seems to be 
very difficult to create an unbiased eval. It is also a problem of 
weighting. One extreme value can dominate the other more realistic ones. One 
has certainly to introduce some form of robust statistics. E.g. using the 
median instead of the mean or ignoring the minimum and the maximum value.


Chrilly