DIMACS TR: 2007-05
Game Seki
Authors: Diogo V. Andrade, Konrad Borys, Vladimir Gurvich and Gabor Rudolf
ABSTRACT
Given a non-negative integral $m \times n$ matrix $A: I
\times J \rightarrow \ZZ_+$, the game {\em Seki} is defined as
follows. Two players $R$ and $C$ take turns and it is specified who
begins (this player is called the {\em first} and the opponent {\em
second}). By one move a player can either reduce
a strictly positive entry of $A$ by $1$ or pass. If both players
pass then the game results in a draw. Player $R$ (respectively, $C$)
wins if a row (respectively, column) appears whose all entries are
equal to $0$. If after a move such a row and column appear
simultaneously then the player who made this last move is the winner.
(We also consider another version, Seki-I, in which this case is
defined as a draw.) If neither $R$ nor $C$ can win in $A$, even
being first, then $A$ is called a {\em seki matrix} or simply a {\em
seki}. Furthermore, $A$ is called a {\em complete seki matrix} (CSM)
if $A$ is a seki and each player {\em must} pass, that is, if a
player makes an active move then the opponent wins.
Seki is a difficult game. We cannot solve it and present only some
partial results and conjectures mostly on the CSMs.
The game is closely related to the so-called seki (shared life)
positions in GO. However, Seki is of independent interest as a
combinatorial game. Those readers who do not know how to play GO can
still understand the whole paper, except Appendix, where we analyze
(seki) positions in GO corresponding to some (seki) matrices. Already
for $3 \times 3$ matrices such positions may be difficult even for
advanced GO players.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-05.pdf
DIMACS Home Page