Impartial Chocolate Bar Games with a Pass

This paper presents a study of chocolate bar games with a pass. Chocolate bar games are variants of the game Nim in which the goal is to leave your opponent with the single bitter part of the chocolate. In this work, we investigate step chocolate bars of which the width is proportional to the distance from the bitter square. It is well-known that, in classical Nim, the introduction of the pass alters the underlying structure of the game, thereby increasing its complexity considerably; however, in the chocolate bar games treat in this paper the pass move is found to have a relatively minimal impact. Step chocolate bar games without a pass have simple formulas for Grundy numbers. This is not so after the introduction of a pass move, but they still have simple formulas for previous player’s positions. Therefore, the authors address a longstanding open question in combinatorial game theory, namely, the extent to which the introduction of a pass move into a game a↵ects its behavior. The game we develop seems to be the first variant of Nim that is fully solvable when a pass is not allowed and remains yet stable following the introduction of a pass move.

本稿では、一回のパスを導入したチョコレートゲームの研究を紹介する．チョコレートバーゲームは、チョコレートの苦い部分1つを相手に残すことを目的としたゲームNimの変種である。古典的なNimゲームでは、パスの導入がゲームの基本構造を変え、必勝法の解の複雑さを大幅に増大させることが知られている．しかしながら，我々は， ステップ型チョコレートバーにおいて，一回のパスを導入しても必勝法の解の簡潔さを損なわない条件を発見した．私たちが開発したゲームは、パスが許されない場合にも完全に解け，かつ1回のパスが導入された後も解が安定しているNimの最初の変種である．

Publication: 

Ryohei Miyadera, Maakito Inoue and Masanori Fukui. “Impartial Chocolate Bar Games with a pass”, Integers, Volume 16, G5, 2016.