オクタルゲーム

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

八進法ゲームは公平性を重視しており、片方のプレイヤーが行えるすべての動きは、もう片方のプレイヤーも行える。各ゲームは、一手で取り除くことができるトークンの数、そして（この数に応じて）ヒープ全体を取り除けるか、ヒープのサイズを縮小できるか、ヒープを2つに分割できるかがそれぞれ異なる。これらのルールの違いは、八進数を用いたコード体系によって簡潔に記述できる。

ゲームの仕様

八進ゲームは、トークンを山に分け、それを使ってプレイします。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つの空でないヒープに分割する場合です。

八進ゲームでは、小数点の左側の数字4を用いることで、トークンを一切減らすことなくヒープを2つの部分に分割できる場合があります。これは、ヒープを2つの不均等な部分に分割するグランディのゲームにおける動きに似ています。しかし、標準的な八進ゲーム記法では、不均等な部分の制約を表現することができません。

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

特定の8進ゲーム

ニム

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

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

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

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

と

${\displaystyle 0.1}$

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

ケイルズ

ケイルズというゲームは通常、 n個のピンを並べたゲームとして描かれますが、n個のカウンターを積み重ねたゲームとしてモデル化することもできます。プレイヤーは積み重ねた中から1個または2個のトークンを取り除き、残りのトークンを0個、1個、または2個の積み重ねた中に置くことができます。ケイルズの8進数は0.77です。

ドーソンのチェス

ドーソンのチェスは、トーマス・レイナー・ドーソンが1938年著作『Caissa's Wild Roses』で提示したチェスパズルから派生したゲームである。 ^[3] このパズルは、1段ずつ離れた向かい合ったポーンの列を含むものとして提示された。このパズルは公平なゲームとして提示されているわけではないが、捕獲が必須であるという仮定は、プレーヤーがどのファイルでも移動しても、そのファイルとその隣接するファイル（もしあれば）がそれ以上考慮されず、反対側のプレーヤーが移動するという結果になるだけである。これをn個のトークンのヒープとしてモデル化すると、プレーヤーは1個、2個、または3個のトークンのヒープ全体を削除したり、ヒープを2個または3個のトークンで減らしたり、3個のトークンを削除した後にヒープを2つに分割したりすることができる。ドーソンのチェスは、したがって、8進コード0.137で表わされる。

ドーソンのケイルズ

ドーソンのケイルズと呼ばれるゲーム0.07では、1つの動きは、ヒープからちょうど2つのトークンを取り除き、残りを0個、1個、または2個のヒープに分配することです。ドーソンのケイルズは、ドーソンのチェスとの（自明ではない）類似性から名付けられました。ドーソンのケイルズのn + 1個のトークンのヒープは、ドーソンのチェスのn個のトークンのヒープと全く同じように動作します。ドーソンのケイルズはドーソンのチェスの いとこであると言われています

他の基底への一般化

Nimのような八進ゲームは、一手ごとにヒープが0個または1個のヒープに変化するため、四進ゲームと呼ばれます。これは、出現する数字が0、1、2、3のみであるためです。八進記法は、数字によってヒープを3つの部分に分割できる十六進ゲームにも拡張できます。実際、任意の大きな基数が可能です。四進ゲーム、八進ゲーム、十六進ゲームの分析は、これらのゲームの種類が互いに著しく異なることを示しています^[1]。そして、より大きな基数での挙動については、それほど精査されていません。

ニム列

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

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

計算記録

八進ゲームを完全に解析すると、そのニム列の周期と前周期が求められます。『数学的ゲームで勝つための方法』では、有限八進ゲームが周期的であることを証明するには、ニム列の有限個の値のみが必要であることが示されており、これがコンピュータによる計算への扉を開きました。

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]

参考文献

1. バーレカンプ、エルウィン・R.、ジョン・H・コンウェイ、リチャード・K・ガイ (1982).数学的遊びの必勝法. 第1巻. アカデミック・プレス. ISBN 0-12-091101-9。『数学的遊びのための勝利の方法（第2版）』として改訂・再版。AK Peters Ltd. 2004年。ISBN
    1-56881-130-6。
2. コンウェイ、ジョン・ホートン(1976).数とゲームについて. アカデミック・プレス. ISBN  0-12-186350-6。改訂版として再版— (2000)。数字とゲームについて。AK Peters Ltd. ISBN
    1-56881-127-6。
3. ドーソン、トーマス・レイナー（1973年）。『フェアリーチェスの5つの古典』ドーバー出版
4. リチャード・K・ガイ「組み合わせゲームにおける未解決問題」『ゲーム・オブ・ノー・チャンス』1996年
5. Achim Flammenkamp、オクタルゲーム