Re: [computer-go] Minimax with random evaluations

[Don Dailey <drd@xxxxxxx>]

>  In many games having lots of move options correlates somewhat with
>  a good position. But, as noted previously, this is not very
>  relevant in the context of go.

It looks like it may be relevant in GO too.  Of course this depends on
what you mean by relevant.    

Random evaluation is a very poor evaluation in any reasonable game you
choose, but the interesting result is that random evaluation combined
with a search leads to something much better than completely aimless
play.

In my tests of 5x5 Go, 5 ply random evaluation beats random play with
an 81% score over 1000 games.

In 7x7 Go, 5 ply random evaluation beats random play with an 82.4%
score over 523 games.

Not very impress when you consider the huge amount of extra work being
done, but quite impressive when you consider the evaluation function
used!

- Don




   X-Original-To: computer-go@xxxxxxxxxxxxxxxxx
   Date: Mon, 24 Jan 2005 12:33:44 +0200
   From: Antti Huima <antti.huima@xxxxxxxxxxxxxxxxx>
   X-Accept-Language: en-us, en
   X-Enigmail-Version: 0.90.0.0
   X-Enigmail-Supports: pgp-inline, pgp-mime
   X-OriginalArrivalTime: 24 Jan 2005 10:33:45.0256 (UTC)
	   FILETIME=[2E745A80:01C50200]
   Cc: 
   Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
   Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
   X-Spam-Score: -5.811
   X-Spam-Flag: NO
   X-Scanned-By: MIMEDefang 2.42

   Russell Wallace wrote:

   >On Fri, 21 Jan 2005 09:19:50 -0500, Don Dailey <drd@xxxxxxxxxxxxxxxxx> wrote:
   >  
   >
   >>Evaluation function is:   #define EVAL (8192 - (rand() & 0x3fff))
   >>I'm not sure it matters and could just as easily have used rand()
   >>    
   >>
   >
   >I don't understand this - what benefit would minimax search give if
   >the evaluation function is random? How is the result different from
   >just making a random move?
   >
   >(Maybe I'm missing something obvious, in which case enlightenment
   >would be appreciated :))
   >
   >- Russell
   >_______________________________________________
   >computer-go mailing list
   >computer-go@xxxxxxxxxxxxxxxxx
   >http://www.computer-go.org/mailman/listinfo/computer-go/
   >  
   >
   If you search one ply as MAX player, you get higher evaluation score 
   when the number of available move options increases, because the 
   expected maximum value gets higher.

   If you search two plys, beginning at MIN player, the lowest score will 
   be on move for which the opponent has the least number of answers 
   available. This pattern continues inductively.

   But the main point is that at the last branch before the search horizon, 
   random evaluation scores function as a noisy way to calculate the number 
   of options available. In many games having lots of move options 
   correlates somewhat with a good position. But, as noted previously, this 
   is not very relevant in the context of go.

   Regards,

   -- 
   Antti Huima (Mr.)
   Director, Conformiq Tools
   mobile: +358 40 528 8667
   email: antti.huima@xxxxxxxxxxxxxxxxx

   Conformiq Software Ltd.
   Stella Terra, Lars Sonckin kaari 16
   FIN-02600 Espoo, Finland
   tel: +358 10 286 6300
   fax: +358 10 286 6309 
   http://www.conformiq.com/

   _______________________________________________
   computer-go mailing list
   computer-go@xxxxxxxxxxxxxxxxx
   http://www.computer-go.org/mailman/listinfo/computer-go/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/