RE: computer-go: perfect players

[Mika Kojo <mkojo@xxxxxxx>]

Seth, 

The book by Osborne & Rubinstein is a bit formal and thus its often a
bit unclear what they are really saying. However, on page 100, second
paragraph (of sixth printing 1999), it states clearly; 

  "One conclusion we can draw from the result, coupled with the
  results on strictly competitive games in Section 2.5, is that each
  player in chess has a strategy that guarantees his equilibrium
  payoff (a result first proved by Zermelo (1913)). Since chess has
  finitely many possible histories (once a position is repeated three
  times the game is declared a draw), Proposition 99.2 implies that it
  has a subgame perfect equilibrium and thus also a Nash equilibrium;
  since it is strictly competitive, any Nash equilibrium strategy of a
  player guarantees the player his equilibrium payoff. Thus either
  White has a strategy that guarantees that it wins, or Black has a
  strategy that guarantees that it wins, or each player has a strategy
  that guarantees that the outcome of the game is either a win for it
  or a draw."

The last sentence contradicts your translation of the Proposition 99.2
(on page 99).

-- Mika

Azathoth writes:
> I have read many of the responses to this thread, and some of the
> suggestions seem to ignore the word "perfect".
> The book I am referencing is full of proofs written in hard to read formal
> logical notation, so, even though they might be hard to understand, they
> are still validly constructed proofs.
> 
> A better paraphrase from the book (book talks about chess, not go):
> 
> Similar to chess, go is a strictly competitive game with finitely many
> histories (the ko rule prevents a game from returning to a previous
> state), and thus, as proved by Zermelo in 1913, has subgame perfect
> equilibrium and Nash equilibrium. Despite this fact, the equilibrium has
> yet to be calculated, and, even if were, it is doubtful that a human
> player would be able to implement the resultant strategy.
> 
> 
> And so it goes,
> -seth
> 
> On Fri, 4 May 2001, Mika Kojo wrote:
> 
> > 
> > Seth, 
> > 
> > perhaps you should consider your translation again. There surely are
> > games where even a perfect player would lose if not given the *choice*
> > of color.
> > 
> > -- Mika
> > 
> > Azathoth writes:
> > > from the book: A Course in Game Theory(1994, Martin J. Osborne & Ariel
> > > Rubinstein)
> > > "Every finite extensive game with perfect information has a subgame
> > > perfect equilibrium"(p.99)
> > > 
> > > In english: assuming perfect ability to analyze a game, he can develop a
> > > strategy that will ensure him of at least an tie, no matter what strategy
> > > the opponent is using. 
> > > 
> > > And so it goes,
> > > -seth
> > > 
> > > On Fri, 4 May 2001, Allan Crossman wrote:
> > > 
> > > > 
> > > > >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)
> > > > 
> > > > 
> > > 
> > 
>