シャノンスイッチングゲーム

シャノンスイッチングゲームは、 2人のプレーヤーが対戦する接続ゲームで、1951年より前に「情報理論の父」と呼ばれるアメリカの数学者で電気技師のクロード・シャノンによって発明された。 ^{[1] 2人のプレーヤーが交代で任意の}グラフ の辺に色を付ける。一方のプレーヤーは、2つの異なる頂点を自分の色の辺のパスで結ぶことを目標とする。もう一方のプレーヤーは、自分の色を使って（または、同等に、辺を消すことで）これを阻止することを目標とする。このゲームは、通常、長方形のグリッド上でプレイされる。このゲームの特別なケースは、 1950年代後半にアメリカの数学者デビッド・ゲイルによって独自に発明され、ゲイルまたはブリッジイットとして知られている。^{[2] [3]}

このゲームは、 AとBという 2 つの特別なノードを持つ有限グラフ上でプレイされます。グラフの各辺は、色を付けたり削除したりできます。2 人のプレイヤーはShortとCut と呼ばれ、交互に動きます。Cut の番では、Cut はグラフから任意の色の付いていない辺を削除します。Short の番では、Short はまだグラフ内にある辺に色を付けます。Cut がグラフをAとBが接続されていないものに変えることができれば、Cut の勝ちです。Short がAからBへの色付きのパスを作ることができれば、Short の勝ちです。ゲームは有限回数の移動後に必ず終了し、2 人のプレイヤーのうちの 1 人が勝たなければなりません。Short、Cut、または最初に移動したプレイヤーには、任意のグラフ上で勝利戦略が存在することが保証されています。^[4]

ShortゲームとCutゲームは双対性があります。つまり、両方のプレイヤーが同じ目標を持つようにゲームを言い換えることができます。つまり、特定のエッジeを持つ特定のエッジ セットを確保することです。Short は、eとともに回路を構成するエッジ セットを確保しようとします。一方、Cut は、 eとともにカットセット (2 つのサブグラフを接続するエッジの最小セット) を構成するエッジ セットを確保しようとします。

有向グラフと有向マトロイド上でプレイされるシャノンスイッチングゲームのバージョンは理論的目的で説明されているが^{[5] [6]}、対応する商用ゲームは公開されていない。

アメリカの数学者デイビッド・ゲイルが考案し、 1958 年 10 月のScientific American 誌のマーティン・ガードナーのコラムで説明されているこのゲームでは、異なる色の点が 2 つのグリッドにオフセットされて重ねられています。1 人のプレーヤーが 1 つのグリッドで直交する隣接する点をリンクし、もう 1 人のプレーヤーがもう 1 つのグリッドを使用します。1 人のプレーヤーはグリッドの上部を下部にリンクしようとし、もう 1 人のプレーヤーは左側を右側にリンクしようとします。このゲームは、長方形のグリッドでプレイされるシャノン スイッチング ゲームに相当します。引き分けは発生せず、最初のプレーヤーが正しいプレイをすれば常に勝つことができます。

この方式を実装したボードゲームは、1960年にハッセンフェルド・ブラザーズによって「ブリッジ・イット」という名前で販売されました。^[7]このゲームは、5x6の長方形のグリッドが2つ交互に配置された台座（1つは黄色、もう1つは赤）が付いたプラスチックのボード、赤と黄色のプラスチック製の橋が20個ずつ2セット、および橋を取り付けるための対応するペグで構成されていました。プレーヤーは、同じ色の隣接する2つの台座に交互に橋をかけていき、一方のプレーヤーが、自分の色でマークされたボードの2つの反対側をつなげるまで続けます。説明書には、ゲームのバリエーションが説明されています。各プレーヤーは限られた数の橋（たとえば10個）を受け取ります。すべての橋を配置したときにどちらのプレーヤーも勝利しなかった場合、プレーヤーは自分の番に、勝利するまで自分の橋の1つを再配置できます。このゲームは長い間生産されていません。

Game of Gale の電子実装は、Ludii ゲーム ポータルで入手できます。

シャノンスイッチングゲームは、メイカーの勝利パターンが接続パスである メイカーブレーカーゲームの特殊なケースとして見ることができます。

弱い関連性のある接続ゲームHexは、六角形のグリッド上でプレイされ、6 つの接続性があります。一般化された Hex は、Shannon ゲームと同様にグラフ上でプレイされますが、エッジを色付けする代わりに、Hex ではプレイヤーは頂点を色付けします。これらのゲームは、構造と特性がまったく異なります。

紙と鉛筆を使って長方形の点の配列 (またはグラフ用紙) 上で遊ぶもう 1 つの接続ゲームは、子供のゲーム「ドット アンド ボックス」です。プレーヤーは交互に、任意の 2 つの隣接する点を縦または横の線で結びます。線が四角形を完成すると、プレーヤーはその四角形にイニシャルを記入します。すべての線が塗りつぶされた後、最も多くの四角形を取ったプレーヤーが勝者となります。

^{Gale の拡張版である Qua は、N 3}セルのグリッドで構成された 3D ゲーム ボード キューブ上で 3 人のプレイヤーがプレイします。N は、ゲーム ボード キューブの端にあるセルの数と同じ奇数です。初期の Qua Cube ゲーム ボードのレイアウトとルールについては、Board Game Geek のエントリで説明されています。^[8]

無向スイッチングゲームの明示的な解は、マトロイド理論を用いて、1964年に発見された。ショートは、2つの区別された頂点を含む頂点の集合と、 上でサポートされている残りの選択されていない辺の2つの互いに素な部分集合が存在する位置を目指すべきであり、その2つの部分集合のいずれかが（すでに選択された辺と一緒に） 内のすべての頂点を接続するような位置を目指すべきである。ショートがこの特性を持つ位置をもたらす動きをすることができる場合、ショートは他のプレイヤーが何をするかに関係なく勝つことができる。そうでなければ、カットが勝つことができる。^{[2] [9]}${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

PSPACE困難になり得る他の接続ゲームとは異なり、^{[10] [11]}無向スイッチングゲームの最適な動きは、 1動きあたり多項式時間で見つけることができます。 Cutによって選択されたエッジをグラフから削除し、Shortによって選択されたエッジを縮小すると、結果のグラフは開始グラフのマイナーになります。区別された頂点をそれぞれ接続する2つの互いに素な木の存在をテストする問題は、マトロイド分割問題として表すことができ、多項式時間で解決できます。あるいは、ネットワークフローアルゴリズムを使用して同じ問題を解決することもできます。

• TwixT、正方形のグリッド上の異なる、より難しい接続ゲーム

ウィキメディア・コモンズには、シャノンスイッチングゲームに関連するメディアがあります。

• グラフゲーム、シャノンスイッチングゲームのJava実装