DIMACS TR: 2007-05

Game Seki

Authors: Diogo V. Andrade, Konrad Borys, Vladimir Gurvich and Gabor Rudolf


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