クラム（ゲーム）

クラムは方眼紙（または任意の種類のグリッド）上でプレイする数学ゲームです。これはドミニアリングの公平なバージョンであり、ルールの唯一の違いは、プレイヤーがドミノをどちらの方向にも置けることですが、結果的には非常に異なるゲームになります。このゲームは、ジェフリー・モット・スミスによる「プラッグ」や「ドット・アンド・ペア」など、さまざまな名前で呼ばれてきました。クラムは、サイエンティフィック・アメリカン誌でマーティン・ガードナーによって普及されました。^[1]

ルール

このゲームは、方眼紙の上で、任意のデザインを描いた上でプレイします。6×6 の正方形やチェッカーボードなどの長方形のボードでプレイするのが最も一般的ですが、完全に不規則な多角形や円筒形のボードでプレイすることもできます。

2 人のプレイヤーがドミノのコレクションを持ち、順番にグリッド上に配置します。プレイヤーはドミノを水平または垂直に配置することができます。関連ゲームの Domineering とは異なり、2 人のプレイヤーが実行できる動きは同じであるため、Cram は公平なゲームです。

すべての公平なゲームと同様に、勝利には 2 つの慣例があります。通常のゲームでは、最初に動けなくなったプレイヤーが負け、逆にミゼールバージョンでは、最初に動けなくなったプレイヤーが勝ちます。

対称遊び

通常の Cram の勝利戦略は、偶数対偶数ボードでも偶数対奇数ボードでも単純です。偶数対偶数の場合、2 番目のプレーヤーが対称プレイで勝利します。これは、プレーヤー 1 の任意の動きに対して、プレーヤー 2 が水平軸と垂直軸にわたって対応する対称的な動きをすることを意味します。ある意味で、プレーヤー 2 はプレーヤー 1 の動きを「模倣」します。プレーヤー 2 がこの戦略に従うと、プレーヤー 2 は常に最後の動きをするため、ゲームに勝利します。

奇数対偶数の場合、同様の対称プレイにより最初のプレイヤーが勝ちます。プレイヤー1は最初のドミノをグリッドの中央2マスに置きます。次にプレイヤー2が動きますが、その後はプレイヤー1が対称的にプレイできるため、プレイヤー1の勝利が確実になります。^[2]

対称プレイは、ミゼールバージョンでは役に立たない戦略です。その場合、プレイヤーが負けるだけになるからです。

通常版

グランディ値

クラムは公平なゲームであるため、スプレイグ・グランディの定理によれば、通常のバージョンでは、どのクラムの位置も、指定されたサイズのニムヒープと等しく、グランディ値とも呼ばれます。いくつかの値は『数学的プレイの勝利方法』に記載されています。特に 2 × nボードでは、 nが偶数の場合は値が 0 、nが奇数の場合は値が 1 になります。

対称戦略では、偶数対偶数のボードでは Grundy 値が 0 になることを意味しますが、偶数対奇数のボードの場合は、Grundy 値が 1 以上になることを意味します。

既知の値

2009年、Martin Schneiderは3×9、4×5、5×7の盤面までのGrundy値を計算しました。^{[3] 2010年、Julien LemoineとSimon Viennotは、もともと}Sproutsゲーム用に開発されたアルゴリズムをCramゲームに適用しました。^[4]これにより、3×20、4×9、5×9、6×7、7×7の盤面までのGrundy値を計算できるようになりました。^[5] Piotr Belingは、これらの結果を6×9、7×8、7×9の盤面まで拡張しました。^[6]

3 × nボードの n=1 から n=20 までの現在知られている Grundy 値のシーケンスは、1、1、0、1、1、4、1、3、1、2、0、1、2、3、1、4、0、1、0、2 です。パターンは見られません。

以下の表は、両方の寸法が 3 より大きいボードの既知の結果を詳細に示しています。n × m ボードの値は m × n ボードの値と同じなので、表の上部のみを示します。

ミゼールバージョン

ミゼール・グランディ値

ゲーム G のミゼールグランディ値は、コンウェイの著書「数とゲームについて」で、ミゼールプレイで 2 番目のプレイヤーの勝利が G+n となるような唯一の数 n として定義されています。^[7]これは通常のプレイでの通常のグランディ値と非常によく似ていますが、それほど強力ではありません。特に、ゲームの合計のミゼールグランディ値を、それぞれのミゼールグランディ値からのみ推論することはできません。

2009年、マーティン・シュナイダーは、3×9、4×6、5×5の盤面までのミゼール・グランディの値を計算しました。^[3] 2010年、ジュリアン・ルモワンヌとシモン・ヴィエノは、これらの結果を3×15、4×9、5×7の盤面まで拡張し、6×6の盤面の値も算出しました。^[5]

3 × nボードの現在知られているミゼール・グランディ値のシーケンスは、n=1 から n=15 まで、0、0、1、0、0、1、0、0、1、0、0、1、0、0、1 です。このシーケンスは周期 3 の周期であると推測されます。^[5]

隣の表には、両方の寸法が 3 より大きいボードの既知のミゼール結果が詳しく示されています。

参考文献

Berlekamp, Elwyn R. ; Conway, John H. ; Guy, Richard K. (2003).数学ゲームで勝つ方法. AK Peters, Ltd.

^ ガードナー、マーティン(1974)。「数学ゲーム：クラム、クロスクラム、クアドラファージ：とらえどころのない勝利戦略を持つ新しいゲーム」。サイエンティフィック・アメリカン。230 ( 2): 106–108。doi :10.1038/scientificamerican0374-102。
^ Uiterwijk, Jos (2020年12月). 「組み合わせゲーム理論を用いたCramの解決」. ResearchGate .
^ ab Das Spiel Juvavum、マーティン・シュナイダー、修士論文、2009
^ ジュリアン、ルモワンヌ;サイモン、ヴィエノット (2010)。「ニンバーは避けられない」。arXiv : 1011.5841 [math.CO]。
^ abc 正常とミゼールの計算記録 Cram、Julien Lemoine、Simon Viennot の Web サイト
^ 公平なゲームを解くための Rust ソフトウェア Piotr Beling
^ John H., Conway (2000). On Numbers and Games . AK Peters, Ltd.

[1] ガードナー、マーティン(1974)。「数学ゲーム：クラム、クロスクラム、クアドラファージ：とらえどころのない勝利戦略を持つ新しいゲーム」。サイエンティフィック・アメリカン。230 ( 2): 106–108。doi :10.1038/scientificamerican0374-102。

[2] Uiterwijk, Jos (2020年12月). 「組み合わせゲーム理論を用いたCramの解決」. ResearchGate .

[Schneider-3] Das Spiel Juvavum、マーティン・シュナイダー、修士論文、2009

[4] ジュリアン、ルモワンヌ;サイモン、ヴィエノット (2010)。「ニンバーは避けられない」。arXiv : 1011.5841 [math.CO]。

[sproutsWiki-5] 正常とミゼールの計算記録 Cram、Julien Lemoine、Simon Viennot の Web サイト

[Beling-6] 公平なゲームを解くための Rust ソフトウェア Piotr Beling

[7] John H., Conway (2000). On Numbers and Games . AK Peters, Ltd.