ケイルズ

ケイルズは、1908 年にヘンリー・デュドニーによって発明された、組み合わせゲーム理論における単純な公平ゲームです。想像上のボウリングのピンの列が与えられ、プレーヤーは順番に 1 本のピンまたは隣接する 2 本のピンを倒し、すべてのピンがなくなるまで続けます。オクタルゲームの表記法を使用すると、ケイルズは0.77と表されます。

ケイルズは、ボウリングのピンを表すトークンの列を使ってプレイします。列の長さは任意です。2 人のプレイヤーが交互にプレイします。各プレイヤーは、自分の番に、任意の 1 本のピン (そのピンに直接ボールを投げる) または隣接する 2 本のピン (両方のピンにボールを投げる) を取り除くことができます。通常のプレイ規則では、合法的な移動手段がない (つまり、すべてのピンがなくなった) プレイヤーは負けとなります。このゲームは、ミゼールルールを使用してプレイすることもできます。この場合、移動できないプレイヤーが勝ちます。

ケイルズはヘンリー・デュドニーによって発明された。^{[1] [2]} リチャード・ガイとセドリック・スミスは、スプレイグ＝グランディ理論を用いて、初めて通常プレイ版を完全に分析した。^{[3] [4]}ミゼール版は1973年にウィリアム・シバートによって分析されたが、彼は1989年までその研究を発表しなかった。^[5]

「Kayles」という名前は、フランス語の「quilles」の英語化であり、「ボウリングのピン」を意味します。

ほとんどのプレイヤーは、通常の Kayles では、列の長さが 0 より大きい場合は必ず最初のプレイヤーが勝つことにすぐに気付きます。この勝利は、対称戦略を使用して達成できます。最初の動きでは、最初のプレイヤーは列が同じ長さの 2 つのセクションに分割されるように移動する必要があります。これにより、今後のすべての動きがどちらかのセクションに制限されます。これで、最初のプレイヤーは、反対の列で 2 番目のプレイヤーの動きを真似るだけです。

長さ の行のnim 値が何であるかを尋ねる方が興味深いです。これはしばしば と表記されます。これは数字ではなく、nimberです。Sprague -Grundy の定理により、 は、結果として生じる 2 つのセクションのnim 値のnim 和のすべての可能な動きに対するmexです。たとえば、 ${\displaystyle n}$${\displaystyle K_{n}}$${\displaystyle K_{n}}$

${\displaystyle K_{5}={\mbox{mex}}\{K_{0}+K_{4},K_{1}+K_{3},K_{2}+K_{2},K_{0}+K_{3},K_{1}+K_{2}\},\,}$

長さ5の行から、位置に移動できるからです

${\displaystyle K_{0}+K_{4},\quad K_{1}+K_{3},\quad K_{2}+K_{2},\quad K_{0}+K_{3},{\text{ および }}K_{1}+K_{2}.\,}$

値の再帰計算（ から開始）により、次の表にまとめられた結果が得られます。表の の値を見つけるには、と書き、行 a、列 b を確認します。 ${\displaystyle K_{0}=0}$${\displaystyle K_{n}}$${\displaystyle n}$${\displaystyle 12a+b}$

この時点で、nim値シーケンスは周期12で周期的^[5]になるため、表のそれ以降の行はすべて最後の行と同一になります。

ドットとボックス内の特定の位置はケイルの位置に還元されるため^[6]、一般的なドットとボックスの位置を分析するにはケイルを理解しておくと役立ちます。

通常のプレイでは、ケイルズはスプレイグ・グランディ理論を用いて多項式時間で解くことができる。^[3]

ノード ケイルズはケイルズをグラフに一般化したもの。各ボウルが目的の頂点とそのすべての隣接頂点を「ノックダウン」(削除) します。あるいは、このゲームは 2 人のプレイヤーが一緒に独立集合を見つけるゲームと見なすことができます。勝者の決定は、境界付き小惑星数 (集合内の任意の頂点の閉近傍を削除しても集合の残りの頂点が同じ接続コンポーネントに残るような頂点の最大部分集合のサイズとして定義される) を持つ任意のグラフ族に対して多項式時間で解決できます。^[7]

同様に、クリーク形成ゲームでは、2人のプレイヤーがグラフ内のクリークを見つけなければなりません。最後にプレイしたプレイヤーが勝ちます。Schaefer (1978) ^{[8] は、}これらのゲームの結果を決定することはPSPACE 完全であることを証明しました。同じ結果は、ノード Kayles の党派バージョンにも当てはまります。このバージョンでは、すべてのノードに対して、プレイヤーの 1 人だけがその特定のノードをノックダウンターゲットとして選択できます。

• 組み合わせゲーム理論
• オクタルゲーム
• ドーソンズ・ケイルズ
• ニバー