地図塗り絵ゲーム

組み合わせゲーム理論では、いくつかの地図色付けゲームが研究されています。基本的な考え方は、領域が描かれた地図が与えられますが、すべての領域が色付けされているわけではありません。2 人のプレーヤー (左と右) が、地図色付け問題と同様に、さまざまな制約の下で、1 ターンごとに 1 つの未着色領域を交互に色付けします。移動制約と勝利条件は、特定のゲームの特徴です。

プレイヤーの中には、 4 色定理のように、双対グラフの頂点を色付けする方が簡単だと感じる人もいます。このプレイ方法では、領域は小さな円で表され、隣接する領域の円は線分または曲線で結ばれます。この方法の利点は、ターンでマークする必要がある領域が小さいことと、表現が紙や画面上で占めるスペースが通常少ないことです。最初の利点は、鉛筆と紙の代わりにコンピューター インターフェイスでプレイする場合、それほど重要ではありません。 碁石やチェッカーでプレイすることもできます。

各ゲームに固有の制約は、色付け領域でプレイヤーが使用できる色のセットです。左と右で使用できる色が同じ場合、ゲームは公平です。そうでない場合は、ゲームは党派的です。色のセットはゲームの状態によっても異なります。たとえば、使用する色は、前の移動で使用した色と異なることが要求される場合があります。

移動に対するマップベースの制約は、通常、色付けする領域とその隣接領域に基づきますが、マップ カラーリング問題では、領域は、単一点よりも長い境界に沿って交わる場合に隣接領域とみなされます。 古典的なマップ カラーリング問題では、2 つの隣接領域に同じ色を与えてはなりません。古典的な移動制約は、領域を隣接領域と同じ色で色付けすることを禁止することによって、これを強制します。反古典的な制約は、領域を隣接領域のいずれかの色と異なる色で色付けすることを禁止します。

別の種類の制約は含意です。これは、最初の移動後の各移動で、前の移動で色付けされた領域の隣接部分を色付けする必要があるというものです。 反含意は、別の可能な制約です。

隣接する領域に異なる色または同一の色を使用するように要求するなど、他の種類の制約も可能です。この概念は、グラフ距離2 の領域に適用するものと見なすことができ、より大きな距離に一般化できます。

勝者は通常、最後に手番を終えたプレイヤーです。これは通常のプレー規則と呼ばれます。ミゼールプレー規則では、最後に手番を終えたプレイヤーが負けとなります。囲碁のように、地を数えるなど、他の勝ち負けの条件も考えられます。

(Silverman, 1971) に登場したこれらのゲームはすべて、古典的な移動制約を使用しています。公平なゲーム「モノクローム」では、使用できる色は 1 色のみであるため、移動するたびに、色付きの領域とその近隣がゲームから除外されます。「バイクローム」では、両方のプレーヤーが 2 色を選択できますが、これは古典的な条件に従います。両方のプレーヤーが同じ 2 色から選択するため、ゲームは公平です。「トライクローム」は、これをプレーヤーに 3 色に拡張します。この条件は任意の固定数の色に拡張でき、さらにゲームを生み出すことができます。Silverman が述べているように、4 色定理は、任意の平面マップを 4 色で色付けできることを示していますが、一部の色が塗りつぶされているマップには適用されないため、4 色以上を追加するとゲームに影響する可能性があります。

「Col」では、古典的な制約を受ける 2 つの色がありますが、左は領域を B"l"ue にのみ色付けでき、右は領域を R"ed" にのみ色付けできます。したがって、これはパルチザン ゲームです。プレイ中に左と右で異なる動きが可能になるためです。

「スノート」では、2 色の同様の党派的割り当てが使用されていますが、反古典的制約が課されています。つまり、隣接する領域に異なる色を割り当てることはできません。領域を色付けすることは、雄牛と雌牛にフィールドを割り当てることとして説明されており、隣接するフィールドには、放牧から気をそらさないように、異性の牛がいない必要があります。

これらのゲームは、(Conway, 1976)で紹介され、分析されました。名前は制約の違い (古典的な地図の色付けと動物の鳴き声) を暗記するためのものですが、Conway は同僚の Colin Vout と Simon Norton にもこれらのゲームを考案させたと考えています。

公平なゲーム「コンタクト」(Silverman、1971) では、単一の色を使用し、含意制約 (最初の色の後のすべての移動は、最後に色付けされた領域の隣) が適用されます。Silverman は、「ミゼールコンタクト」 の例も提供しています。

地図色付けゲームの概念は、色付けのルールが多少異なる 「Angels and Devils」などのゲームにまで拡張できます。

• コンウェイ、ジョン・ホートン（1976年）。数字とゲームについて。アカデミック・プレス。ISBN 0-12-186350-6。改訂版として再版
• — (2000).数字とゲームについて。AKピーターズ。ISBN 1-56881-127-6。
• シルバーマン、デビッド L. (1971)。『Your Move』、マグロウヒル。改訂版として再版
• — (1991). Your Move: 愛好家のための論理、数学、単語パズル。ドーバー・プレス。ISBN 0-486-26731-8。