Re: computer-go: perfect players

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

The perfect  player shouldn't be deterministic,  this makes it
easier to get incrementally better results against it by experimenting
with different lines of play.

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.

But if  you want  determinism,  your  idea  is  pretty good.  I  would
suggest  that you still choose  the biggest territory  win, but have a
list of  tie breaking criteria  that you hit one  at a  time until you
have a clear choice.  You don't need to do anything arbitrary, you can
probably always come up with a tie break rule that attempts to confuse
the opponent.

Here is an example:

  1. Play the move gaining the most territory at end of game.

  2. If more than one move qualifies, choose the one that gives
     the opponent the least number of "best moves" (by the same
     criteria.)

  3. If there is still a tie, choose among those moves that survived
     steps 1 and 2.  Perhaps by playing the move that "requires" 
     the best response to be located farther away (the other side
     of the board for example.)   The assumption is that these
     moves are less obvious,  I don't really know if this is
     true however.

  4. Move on to next criteria.

  5. And next.

Probably not many moves would survive the first 3 steps.  

Don


   From: "Fant, Chris" <chris.fant@xxxxxxxxxxxxxxxxx>
   Date: Thu, 3 May 2001 22:43:39 -0400 
   MIME-Version: 1.0
   X-Mailer: Internet Mail Service (5.5.2650.21)
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain;
	   charset="iso-8859-1"
   Content-Length: 2009

   Yes, that's a good point.  If a perfect player has a choice of two moves,
   each of which will lead to a loss against an opposing perfect player with
   the same final score and in the same number of moves, how does he choose?
   So my definition of a perfect player was not completely unambiguous.  Let me
   add one more attribute: He must make the move that leads to the fewest
   number of tied-for-best-move choices for his opponent over the remaining
   course of the game.  This is a worthwhile thing to do in case he is only
   playing against a near-perfect player.  But, obviously, we are still not
   quite there.  If I were coding a perfect player (I just haven't had the
   time) and wanted him to be completely deterministic, I would just take the
   first move in my move list.  But since that varies with architecture, and we
   (or maybe just I) want an architecture independent definition of the perfect
   player, I think the only thing left to do is to make the move nearest the
   beginning of the board (in a row-major sense).  Yes, its completely
   inelegant, but how else can you define the perfect move for a situation like
   that one?


   -----Original Message-----
   From: Allan Crossman [mailto:a.crossman@xxxxxxxxxxxxxxxxx]
   Sent: Thursday, May 03, 2001 7:35 PM
   To: computer-go@xxxxxxxxxxxxxxxxx
   Subject: RE: computer-go: perfect players



   >If you define perfect the way I define it (no mind reading or learning
   about
   >your opponent), you would only need to play two games, one with player A as
   >Black, one with player A as white.  Both games would be exactly the same
   >because both players are exactly the same (perfect).

   This is only true if at no point does either player have two or more moves
   that lead to the same result. In fact I suspect that for Go and many other
   games there are probably millions of possible "perfect games".




		       Allan Crossman
		  http://www.faldara.co.uk
   ------------------------------------------------------
   PGP Keys: 0x497F13C8 (New) and 0xCEC9FAE1 (Compatible)