Re: computer-go: Most simple Go rules

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

The only correction I would make to your nicely done analysis is that
3^361 should be considered a LOWER BOUND, not an upper bound.

I think there  are MUCH more than   3^361 possible game states.   Yes,
there  is precisely this number  of  "configurations of stones" but  a
position should consider 2 other things:

 1.  Side to move.   This is not a biggy, but does put you off by a
     factor of 2 (actually, slightly less than this.)   This is not
     very important but I thought I would mention it.

 2.  Game history.    A position is not just the configuration you
     see on the board,  it's the unique move order that got you to
     that position.   Because repetition is forbidden in the context
     of this discussion,  two identical configurations cannot be considered
     exactly the same position unless the context is the same.  You can
     construct examples where a move is illegal in one case (due to repetition)
     but not in the other.


When considering  an upper bound  to  the number  of legal games, this
move  history stuff  is  not  relevant because  your analysis  already
accounts for all possible move orderings.

Don




   X-Sender: fantius@xxxxxxxxxxxxxxxxx
   X-Mailer: QUALCOMM Windows Eudora Version 4.3.2
   Date: Thu, 21 Jun 2001 18:57:48 -0400
   From: Chris Fant <fantius@xxxxxxxxxxxxxxxxx>
   References: <Pine.OSF.3.96.1010621112204.15829A-100000@xxxxxxxxxxxxxxxxx>
   Mime-Version: 1.0
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain; charset="us-ascii"; format=flowed
   Content-Length: 1201

   How can there be an infinite number of positions?  An upper bound on 
   positions is 3^361 and only a small fraction of those are legal.  The 
   number of games is not infinite either since you can only be in each board 
   position once.  An upper bound on the number of games is the number of 
   legal board positions factorial.  Now thats a big number.  An approximation 
   (not upper bound) is 361 factorial.


   At 05:25 PM 6/21/2001 -0400, you wrote:


   >On Thu, 21 Jun 2001, Xinwei Kong wrote:
   >
   > > The most simple Go rules:
   > >
   > > Rule 1: never allow to repeat a previous board state unless pass
   > > Rule 2: both pass end the game
   > > Rule 3: only stones on the board counts
   >
   >Obviously you must mean in addition to the rules of capture, who goes
   >first, suicide, etc.
   >
   > >
   > > I think it is enough to solve all the problems(even super Ko), and
   > > it is more like ancient chinese rules if you play to the end. It is
   > > theoretically to grantee an end since there are only finite number
   > > of possible positions.
   > >
   >
   >I think that there are most likely an infinite number of positions in this
   >game since either player can fill their own eyes causing occupied points
   >to again become empty.
   >
   >Tim