Loading article…
Chompは、小さな正方形のマス目で構成された長方形のグリッド上でプレイする2人用戦略ゲームです。このグリッドは、チョコレートバーのブロックのようなものと考えてください。プレイヤーは順番に1つのブロックを選び、その下と右にあるブロックと一緒に「食べる」（ボードから取り除く）ことになります。左上のブロックは「毒」が仕込まれており、それを食べたプレイヤーは負けとなります。
Chompのチョコレートバーを使った形式はDavid Galeによるものですが、固定された整数の約数を選ぶという形で表現された同等のゲームは、それ以前にFrederik Schuhによって発表されています。
以下は、4×5のマス目から始まる典型的なゲームにおける一連の手順を示しています。
プレイヤーAは右下隅から2つのブロックを食べます。プレイヤーBは最下段から3つのブロックを食べます。プレイヤーAは毒ブロックの右隣のブロックを選び、11個のブロックを食べます。プレイヤーBは残りの列から3つのブロックを食べ、毒ブロックだけが残ります。プレイヤーAは最後のブロックを食べなければならず、負けとなります。
プレイヤーAが4×5のバーから始めた場合に勝利できることが証明されているため、Aの少なくとも1つの手は間違いであることに注意してください。
m × n Chompの中間位置は、整数分割 (非増加正整数列) λ 1 ≥ λ 2 ≥···≥ λ rであり、λ 1 ≤ n かつr ≤ mである。それらの数は二項係数である。これはmとnとともに指数関数的に増加する。[ 1 ]
Chompは公平な2人対戦完全情報ゲームのカテゴリーに属し、 Sprague–Grundyの定理によりNimによって分析可能である。
1×1以外の長方形の初期配置であれば、先手プレイヤーが勝つことができます。これは、戦略盗用論法を用いて示すことができます。まず、先手プレイヤーのどの初期手に対しても、後手プレイヤーが必勝戦略を持っていると仮定します。次に、先手プレイヤーが右下のマスだけを取るとします。この仮定に基づけば、後手プレイヤーはこれに対して勝利を強制する対応策を持っていることになります。しかし、もしそのような必勝対応策が存在するならば、先手プレイヤーはそれを最初の手としてプレイし、勝利を強制できたはずです。したがって、後手プレイヤーは必勝戦略を持つことはできません。
コンピュータは、適度な大きさの二次元盤面であれば、このゲームの必勝手を容易に計算できる。しかし、局面の数が指数関数的に増加するにつれて、より大きな盤面ではこれは不可能になる。
正方形の初期配置（つまり、n ≥ 2の任意のn × n ）の場合、勝利戦略は簡単に明示できます。最初のプレイヤーは、毒マスでつながった、同じ長さの 1 行 1 列のL字型を 2 番目のプレイヤーに提示します。次に、2 番目のプレイヤーがL字型の一方の腕で何をしたとしても、最初のプレイヤーはもう一方の腕で同じ動きをし、常に再び対称的なL字型を 2 番目のプレイヤーに提示します。最終的に、このL 字型は単一の毒マスに退化し、2 番目のプレイヤーは敗北します。
同様に、任意のn × 2 ( n ≥ 2の場合) も自明です。勝利への最初の動きは常に右下のマスです。この動きの後、盤面は (毒マスを無視して) 2 つの縦のマス目の鎖として考えることができ、勝利するには、もう一方の鎖でプレイヤー 2 の動きを真似るだけです。ただし、勝利への他の道は、多くの場合、より複雑です。
3次元版Chompは、(i,j,k)とインデックス付けされたブロックで構成された直方体状のチョコレートバーを初期状態とします。1つの操作は、選択したブロックの対応するインデックス以上のインデックスを持つ任意のブロックと、そのブロックを一緒に取り出すことです。同様に、Chompは任意の次元数に一般化できます。
Chomp は数値的に記述されることもあります。初期自然数が与えられ、プレイヤーは初期数の正の約数を交互に選択しますが、1 または以前に選択した約数の倍数を選択することはできません。このゲームはn次元Chomp をモデル化しており、初期自然数はn個の素因数を持ち、Chomp ボードの次元はその素因数分解における素数の指数によって与えられます。Ordinal Chompは、いくつかの次元が序数である無限ボードでプレイされます。たとえば、2 × (ω + 4) バーなどです。1 つの操作は、任意のブロックを選択し、選択したブロックの対応するインデックス以上のインデックスを持つすべてのブロックを取り除くことです。ω × ω × ω Chomp の場合は注目すべき未解決問題であり、勝利する最初の操作を見つけると100 ドルの報酬が提供されています[ 2 ] 。
より一般的に言えば、チョンプは最小要素を持つ任意の半順序集合上でプレイできます。一手は、任意の要素とそれより大きいすべての要素を取り除くことです。最小要素を取ったプレイヤーは負けとなります。
チョンプのあらゆるバリエーションは、毒を使わずにミゼールプレイのルールを用いることでプレイできます。最後のチョコレートブロックを食べたプレイヤーは毒を盛られるのではなく、単に最後のプレイヤーであるという理由で負けとなります。これは、チョンプを単独でプレイする場合の通常のルールと同じですが、チョンプの選言和をプレイする場合とは異なり、最後のチョコレートブロックを食べたプレイヤーだけが負けとなります。
