Re: computer-go: perfect players

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

I think  it's important  to define perfect  play in terms  that either
player can execute.   Even if you are losing in  terms of final score,
you can play "perfectly" by maximizing territory.  Also, it just seems
crufty that  perfect play should  be related in  any way to  what komi
happens to be in use.

In chess, it's  a different because it's not  considered even slightly
relevant what is  on the board.  In Go you count  the territory to see
who won.

Since this  discussion is highly  theoretical, I guess you  can define
perfect play  any way you want.   In chess, the  most basic definition
would be any move that  presevered the game theoretical value, such as
"if you  have a win, play any  move that preserves the  win."  This is
fairly ugly  because in Chess you can  throw away a win  simply by not
making progress, due  to the crufy 50 move rule.  The  50 move rule is
not a very  satisfying solution to the problem  of not making progress
in chess, but  something had to be done!  If you  threw out this rule,
you would actually change some drawn positions to wins!

So in Chess you can define perfect play in a way that ignores the
50 move rule and be optimal.    Here is what I would suggest:
  
   1. The shortest pathway (in terms of moves) to the win if it
      is possible.

   2. The longest pathway to being checkmated if you are losing.
  
   3. The longest pathway to stalemate, or position repetition
      if the position is a draw.


Point  3 is  a  little weird,  but  the idea  is that  if  you have  a
positional draw, instead of immediately heading for the game theoretic
draw, delay it as long as possible!

Endgame  databases in  chess basically  follow points  1 and  2.  Some
databases go for the "shortest  pathway to conversion" which is easier
to   manage  because   databases   are  stored   according  to   piece
configurations.  If  you have  2 pawns versus  1 pawn,  many databases
will  try to  get to  1 pawn  versus 0  pawns as  quickly  as possible
instead of maximizing the number of  moves to checkmate.  It has to do
with how they are constructed.

Don






   Date: Fri, 4 May 2001 08:58:05 +0200
   From: heikki@xxxxxxxxxxxxxxxxx
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   On Fri, May 04, 2001 at 12:11:52AM -0400, Don Dailey wrote:
   > So I would simply propose that you always play the move leading to the
   > largest  territory gain.   If  there  is more  than  1 choice,  choose
   > randomly among them.

   This is assuming that it is better to win by 200 points than by 2. Is there
   any justification for this belief, especially for "perfect" players. Would
   it not be as good to choose among any moves that can be proved to win, one
   that does so quickest, or one that leaves the opponent least reasonable
   choices, or something else.

   -H

   -- 
   Heikki Levanto  LSD - Levanto Software Development   <heikki@xxxxxxxxxxxxxxxxx>