Solitaire Clobber: A One-Player Game of Strategy and Reduction

Title: Solitaire Clobber: A One-Player Game of Strategy and Reduction

Research Question: How can one reduce the number of stones in a Solitaire Clobber game, and what are the implications for the game's strategy and complexity?

Methodology: The researchers studied the game of Solitaire Clobber, a one-player variant of the two-player board game Clobber. They analyzed the reducibility of checkerboard configurations, focusing on one-dimensional boards consisting of a single row of stones. They used mathematical proofs and algorithms to determine necessary and sufficient conditions for a configuration to be 1-reducible, i.e., reduced to a single stone.

Results: The researchers found that the number of stones and clashing stones cannot be a multiple of three for a Clobber position to be 1-reducible. They also discovered that for truly two-dimensional rectangular checkerboard configurations, the condition is both necessary and sufficient. However, they showed that deciding 1-reducibility is NP-complete for general configurations. Furthermore, they found that the one-dimensional checkerboard configuration can be reduced to approximately n/4 stones, with an additional stone if n is congruent to 3 modulo 4. This result was independently obtained by Grossman.

Implications: The findings have implications for the game's strategy and complexity. The necessary and sufficient conditions for 1-reducibility provide a clear guideline for players to determine the reducibility of their configurations. The NP-completeness result indicates that finding the optimal reduction for general configurations can be computationally challenging. The one-dimensional reduction result suggests that players should focus on achieving a checkerboard configuration with as many matching stones as possible to minimize the number of stones.

Open Problems: The researchers identified several open problems, including finding efficient algorithms for 1-reducibility, studying the reducibility of other game variants, and exploring the game's potential for further strategic development.

Link to Article: https://arxiv.org/abs/0204017v2 Authors: arXiv ID: 0204017v2