BQM 373

    Keywords: Question

blubb:

Is every game exactly reconstructable from the set of occuring board positions?

Problem

Consider two board positions A and B and a path of arbitrarily colored moves connecting them. Each position is allowed to occcur at most once, that is, the path, including start and end, has to comply with positional superko. Let's call the set of positions which are hit thereby the "footprint" of that path.

  1. Can two different paths between A and B have the same footprint, at all?
  2. If so, do they necessarily have the same move tally? In other words: Is it possible to calculate a path's move tally from its footprint alone?

Remarks

  • "board position" here does not refer to any particular board point but to the state of the game
  • "arbitrarily colored moves" implies that repeated moves by one color are allowed, like, W W B W B B B W B B ...
  • In a path, each position must be connected to the next one by a single move. That is, compared to its predecessor, a position has to contain exactly one more stone of one color and an unchanged or (in case of captures) smaller number of the other. Hence usually, most permutations of a legal path's footprint give an illegal path.
  • I am mainly interested in the case that the starting and ending positions are fixed, so all we have to care about is the order of intermediate positions. However, if someone finds a more general solution, I wouldn't be angry, either. :)

Yes, a game is reconstructable from the set of occuring board positions. Let me just lay out a sketch of a proof, and you can probably fill in the rest. First, I'll cheat a little and assume the colorings are not arbitrary, but rather alternate BWBWBWB...
Then let's prove by contradiction: let's assume we have (at least) two distinct orderings of the footprint, both of which are legal orderings representing a legal go game.
Let position k be the last board position at which two orderings disagree, so for all moves from k+1 to the end of the game, both orderings agree on the board position. We know k<n, where n is the fixed endpoint move, which all orderings must agree on. Because the move colors alternate, we know which color is placing a stone on turn k, and both orderings must agree on this. Let k1 be the position chosen by the first ordering, and k2 be the position chosen by the second ordering. Let's also assume (without loss of generality) that the move transitioning from k to k+1 involves the addition of a white stone. (the black stone case works exactly the same way.) That move can only change the board by:
adding a single white stone to an empty intersection, and (possibly) removing some black stones.
(I'm ignoring suicide because it's messy.)
First, consider the case where no black stones are removed: Both k1 and k2 must have an empty intersection at the position where the white stone will be, and all of the other points on the board must be the same as they are in k+1. Therefore, k1 and k2 are identical. However, there can't be two identical board positions in the footprint due to the superko rule. Therfore, Some black stones were removed, and k1 and k2 differ only in those removed black stones. Is this possible? No, as we said before, every removal of stones of one color must be accompanied by the addition of a stone of the opposite color. Let's say k1 is the position with the extra black stones. The ordering that shows k1 before k2 is impossible, because it is impossible to remove a group of black stones without adding or removing any other stones, even with an infinite number of moves. I don't feel like I can prove this right now (it probably involves induction), but I'm sure it's true. Thus, our assumption led to a contradiction, which means it's false.
As for the generalized move colorings, I think the ordering is still unique, but my proof would fall apart at the "both k1 and k2 are making moves of the same color" step. If any of this seems iffy, let me know. -emeraldemon


BQM 373 last edited by Dieter on July 5, 2008 - 12:49
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