オクタルゲーム

オクタルゲームは、2人用のゲームの一種で、トークンの山からトークン（ゲームの駒または石）を取り除くゲームです。ニムゲーム、ケイルズゲーム、および類似のゲームの一般化として、組み合わせゲーム理論で研究されてきました。^{[1] [2]}

8 進法ゲームは公平です。つまり、一方のプレイヤーが実行できるすべての動きは、もう一方のプレイヤーも実行できます。1 回の動きで取り除くことができるトークンの数、および (この数に応じて) ヒープ全体を取り除けるか、ヒープのサイズを縮小できるか、ヒープを 2 つのヒープに分割できるかが異なります。これらのルールの違いは、8 進数を使用したコーディング システムによって簡潔に記述できます。

八進法ゲームは、トークンを山に分けた上でプレイします。2人のプレイヤーが交代で動き、移動が不可能になるまで続けます。各移動は山の1つだけを選択し、

• ヒープ内のすべてのトークンを削除し、ヒープを残さない。
• トークンの一部を削除し、小さなヒープを1つ残すか、
• いくつかのトークンを削除し、残りのトークンを 2 つの空でないヒープに分割します。

選択されたヒープ以外のヒープは変更されません。通常のプレイでは、最後に動いたプレイヤーが勝ちます。このゲームは、最後に動いたプレイヤーが負けるミゼール プレイでもプレイできます。

このようにヒープを使ってプレイされるゲームでは、各ヒープの許容移動は元のヒープのサイズによって決まり、文献ではテイクアンドブレイキングゲームと呼ばれています。 ^[1]オクタルゲームはテイクアンドブレイキングゲームのサブセットであり、許容移動はヒープから 取り除かれる トークンの数によって決まります。

ゲームの8進コードは次のように指定されます。

0 . d ₁ d ₂ d ₃ d ₄ …、

ここで、8進数d _nは、プレイヤーがヒープからn個のトークンを取り除いた後に、0、1、または2個のヒープを残すことができるかどうかを指定します。数字d _nは、

• ゼロヒープを残すことが許可されている場合は 1、そうでない場合は 0。
• 1つのヒープを残すことが許可されている場合は2、そうでない場合は0。
• 2 つのヒープを残すことが許可されている場合は 4、そうでない場合は 0。

ゼロ トークンはヒープとしてカウントされません。したがって、 nトークンのヒープを完全に削除できる場合、数字d _{n は}奇数であり、そうでない場合でも同じです。 1 ヒープの結果d _nの指定は、 n を超えるヒープからnトークンを削除する場合に適用されます。 2 ヒープの結果d _nは、少なくともn +2 のヒープからnトークンを削除し、残りを 2 つの空でないヒープに分割する場合に適用されます。

8 進ゲームでは、小数点の左側の数字 4 を使用することで、トークンを削除せずにヒープを 2 つの部分に分割できます。これは、ヒープを 2 つの不均等な部分に分割するGrundy のゲームの動きと似ています。ただし、標準的な 8 進ゲーム表記では、不均等な部分の制約を表現することはできません。

有限個の非ゼロ桁のみを含む 8 進ゲームは、有限 8 進ゲームと呼ばれます。

組み合わせゲーム理論における最も基本的なゲームはNimである。これは、任意の数のトークンをヒープから取り除くことができ、0個または1個のヒープが残るゲームである。Nimの8進コードは0.333…であり、出版された文献では次のように記載されている。

${\displaystyle 0.{\dot {3}}}$、

循環小数のように循環部分を表す。しかし、循環部分は8進分数と同じ役割を果たさないことを認識することが重要です。

${\displaystyle 0.0{\dot {7}}}$

そして

${\displaystyle 0.1}$

8 進分数としては等しいにもかかわらず、同一ではありません。

Kaylesゲームは、通常、 n 個のピンが並んだ状態でプレイするものとして視覚化されますが、 n 個のカウンターのヒープでモデル化することもできます。ヒープから 1 個または 2 個のトークンを取り除き、残りを 0 個、1 個、または 2 個のヒープに配置できます。Kayles の 8 進コードは0.77です。

ドーソンのチェスは、トーマス・レイナー・ドーソンが1938年に著した『Caissa's Wild Roses』で提示したチェスのパズルから生まれたゲームです^{。 [3]} このパズルは、1つのランクで隔てられた向かい合ったポーンの列を含むものとして提示されました。このパズルは公平なゲームとして提示されていませんが、キャプチャが必須であるという仮定は、プレーヤーが任意のファイルで移動しても、そのファイルとその隣接するファイル（存在する場合）がそれ以上考慮されなくなり、反対側のプレーヤーが移動することを意味します。これをn個のトークンのヒープとしてモデル化すると、プレーヤーは1、2、または3個のトークンのヒープ全体を削除したり、ヒープを2つまたは3つのトークンで減らしたり、3つのトークンを取り除いた後にヒープを2つに分割したりできます。ドーソンのチェスは、したがって8進コード0.137で表されます。

0.07 のDawson's Kaylesと呼ばれるゲームでは、1 つの動きは、ヒープから 2 つのトークンを削除し、残りを 0、1、または 2 つのヒープに分配することです。Dawson's Kayles は、ドーソンのチェスとの (明らかではない) 類似性から名付けられました。これは、n +1 個のトークンのドーソンのケイルのヒープが、 n個のトークンのドーソンのチェスのヒープとまったく同じように動作するからです。Dawson's Kayles は、ドーソンのチェスの いとこであると言われています。

Nimのような 8 進数ゲームは、すべての動きがヒープを 0 個または 1 個のヒープに変換しますが、表示される数字が 0、1、2、3 のみであるため、4進数ゲームと呼ばれます。8 進数表記法は、数字によってヒープを 3 つの部分に分割できる16 進数ゲームを含むように拡張することもできます。実際、任意の大きな基数が可能です。4 進数、8 進数、16 進数のゲームの分析により、これらのゲームのクラスは互いに著しく異なることが示されており、^[1]より大きな基数の挙動はそれほど精査されていません。

スプレイグ・グランディ定理は、サイズ n のヒープは、通常 G(n) と表記される、指定されたサイズのnim ヒープと同等であることを意味します。したがって、オクタル ゲームの分析は、サイズが増加するヒープの nim 値のシーケンスを見つけることです。このシーケンス G(0)、G(1)、G(2) ... は通常、ゲームの nim シーケンスと呼ばれます。

これまで解析された有限八進ゲームはすべて、ニムシーケンスが究極的に周期的であることを示しており、すべての有限八進ゲームが究極的に周期的であるかどうかは未解決の問題である。これはリチャード・ガイによって組合せゲームの分野における重要な問題として挙げられている。^[4]

8 進法ゲームを完全に分析すると、そのニム シーケンスの周期と前周期が見つかります。数学的プレイで勝つ方法には、有限の 8 進法ゲームが周期的であることを証明するために必要なのは、ニム シーケンスの有限の数の値だけであることが示されており、これによりコンピューターによる計算への扉が開かれました。

8進数が最大3桁の8進ゲームは長年にわたって解析されてきました。非自明な8進ゲームは79個あり、そのうち14個が解決されています。

• 1967年にジャック・ケニオンが.156を樹立^[1]
• 1976年にリチャード・オースティンが.356、.055、.644、.165を記録した^[1]
• 1989年にアニル・ガンゴリとセイン・プラムベックが.16、.56、.127、.376をマーク^[1]
• 2000年から2002年にかけてアヒム・フラメンカンプが.454、.104、.106、.054、.354を記録した^[5]

アヒム・フラメンカンプによる数百万のニム値の計算にもかかわらず、このようなゲームは63個残っています。^[5]