SolvingGo/Discussion

Sub-page of SolvingGo

General

Bildstein: I said this earlier, but someone (accidentally?) edited it out: The SolvingGo page seems to be talking about figuring out how long it would take to find the perfect game by an exhausting search. I think the consensus is that this would take an unreasonably long time (almost forever). I want to say that I think that it is at least conceivable that we could devise some provable ways to say that one move is better than another move, in some cases. A simple example might be proving that play on the first two lines is sub-optimal on the first move. A more complicated example might be proving that the best way to reduce a hovercraft group in the end-game is to hane at the end of the weak leg. Whole classes of these optimisations could be found, and in doing so, the search tree that needs to be navigated would be much, much thinner. In theory, this might even be able to make the problem tractable.

Legal Postions

L max

Upper bound on the number of legal positions is 3^361 * 362

(see SolvingGo/Discussion-Lmax)

see also Number of Possible Outcomes of a Game

Malweth: Yes

ChiralSym?: This is only an upper bound. It is not necessarily a tight upper bound. Clearly the max number of legal positions cannot be greater than this, however it could be less.

Pashley It clearly must be much less, since so many of the possible positions are illegal with zero-eye groups on the board.

Truc Where does the factor of 362 come from?

Tirian Not only do you need to have the position of each stone on the board, but you also need to know if any of the empty squares are illegal for the opposing player due to ko restrictions.

[Diagram]
How completely must we encode this?  

In this diagram, just indicating which spots are filled with black, white, or no stones does not indicate whether Black may now play at A. (In fact, my earlier comment that you needed to encode the last move is also wrong, since a reply at A would be illegal if and only if that last move captured a stone at A regardless of where it was played.) And you'd also want to know whose move it is. So, on reflection, an upper bound would be (3^361) * 2 * 362, so that you could indicate whether one of the points or no point is eligible for the next play. (Another method would be to indicate the position BEFORE the last move, whose turn it was, and either where they played or whether they passed.)

Truc It's hard to talk about numbers without first defining what things mean, so let's define some things here.
Let's define a board-legal position to be one where no stones or chains of stones have zero liberties.
A game-legal position is a position which can be reached through alternating play. Some things that follow from these definitions:

  • Every game-legal position is also a board-legal position
  • The number of board-legal positions is bounded by 3^361

So it follows that the number of game-legal positions, which can't be bigger than the number of board-legal positions, is also bounded by 3^361. There, I avoided the confusing ko issue altogether ;).

Pashley But for each of the 3^361 combinations of stones on the board, you have many possible complete positions. Is it Black's move or White's? Is there a ko? Where?

Tirian I agree with Pashley that Truc's proof is unconvincing, but moreover it is not wholly relevant. Whether the upper bound is 3^361 or approximately 3^366, I think we can agree that it is both finite and pragmatically uncountable, which are the key facts more than any precise number. For instance, a fifty-page proof that the number of important gamestates to calculate was really around 3^100 would still be of no application to the solution process. If it were, we'd be on schedule to solve the 9x9 board instead of dreaming of techniques to tackle 7x7.


SolvingGo/Discussion last edited by pashley on August 16, 2005 - 11:04
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library