Re: Can every game be unambigeously reconstructed from the set of board positions occuring therein?

sebastianwinkel@xxxxxxxxxxxxxx wrote: 
Hi,

thinking about a superko detection algorithm recently, I got puzzled by
the question if the footprint of a game uniquely determines the
sequence of moves. By "footprint", I am referring to the set of
positions the game consists of, and the game may comply with chinese
rules (positional superko).

I suppose that each set of positions can be arranged in at most one
legal order. At first glance, I couldn't see a formal reasoning,
though.


Yes, in fact by extreme coincidence, this is Lemma 1 in our
(me and Gunnar Farnebäck's) upcoming paper on the combinatorics of go:

\begin{defin}[game graph]
Let $G(m,n)$ be the directed graph whose vertices are the legal $m\times n$
positions, and which has an edge from position $p$ to a different position
$q$, whenever $q$ is the result of a white or black move from $p$.
\end{defin}

\begin{lemma}
Outgoing edges from a position are in 1-1 correspondence with the moves
that are not single-stone suicides.
\end{lemma}

\begin{proof}
Consider a move at point $(x,y)$ by player $c$ in position $p$.
In case this is not a suicide, the resulting position $q$ has one more
stone of color $c$, at position $(x,y)$.
In case the move is a suicide, then by assumption, the resulting position $q$
only differs from $p$ in having fewer stones of color $c$,
and $(x,y)$ was the last liberty of these stones in position $p$.
In both cases the edge $(p,q)$ uniquely identifies the move.
\end{proof}

regards,
-John
.

Relevant Pages