Research projects: Chocolate game
Research projects: Chocolate game
What is Chocolate bar game? / チョコレートゲームとは
Each player takes it in turn to break the bar in a straight line along the grooves into two parts, and eats the part without the bitter corner. The player who breaks the chocolate bar so as to leave his opponent with the single bitter block (blue block) is the winner.
2人のプレーヤーが交互にチョコレートを食べます.ここで,プレーヤーは必ず線に沿ってチョコレートを切って食べなければなりません.最終的に苦いチョコ(青いチョコレート)を食べさせられたプレイヤーが負けとなります.
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.