Re: computer-go: perfect play

["Magnus Persson" <magnus.persson@xxxxxxxxxx>]

> Wouldn't godevil agaist godevil -match be just like gogod against gogod?
> If the other player doesn't have any weaknesses, how could you exploit
> them? Of course godevil would choose an optimal move with most
> "interesting" (= hard to analyze) outcomes.
> 
> -- 
>  Tapani Raiko, <tapani.raiko@xxxxxxxxxxxxxxxxx>, 050 5225 750,

Well, here some ideas for implementing a GoDevil:

It is of course impossible on the whole board, but for a Life and 
Death problem, the computer should in principle be able to actually 
know the complete move tree, at least in moderately diffcult 
problems.

Strategy 1 is to choose moves that leads the largest optimal subtree.
It is safe and make it harder for the opponent to read.

Strategy 2 is to check the entire tree for suprising moves. It 
depends on the implementation, but if at one node the best move is a 
move that normally has a very low likelyhood to be best in some sense 
compared to the other candidates at that node, then it is a 
surprising move. The program can then check what happens if the 
opponent do not see this move, perhaps a more complicated variation 
will be chosen (helps strategy 1), or even better: there may be only 
variations left that leads to disaster...  or if it is a killer move 
that GoDevil have and it is in subtree that otherwise look simple, 
then it is the perfect trap...

The hard thing is to define what is surprising. Shape could be one 
thing. Ugly shape like empty triangles are hot candidates. I once 
beat a player 3 stones stronger because he thought he would simply 
catch *all* vital stones (but no I did not do it onpurpose, I was 
just lucky...), but collapsed when all of my stones survived thanks 
to en empty triangle.

Best wishes
Magnus
--
Magnus Persson
Department of psychology, Uppsala University
Box 1225, SE-751 42, Sweden
Tel 018-471 2141 (work), 018-460264 (home)
MAILTO: magnus.persson@xxxxxxxxxxxxxxxxx
URL: http://www.docs.uu.se/~magnuspe