ポジショナルゲーム

ポジショナルゲーム[ ^{1] [2]}は2人のプレイヤーが対戦する組み合わせゲームの一種で、以下のように記述されます。

• ${\displaystyle X}$ –有限の要素の集合。多くの場合、ボードと呼ばれ、その要素はポジションと呼ばれます。${\displaystyle X}$
• ${\displaystyle {\mathcal {F}}}$ –のサブセットの族。これらのサブセットは通常、勝利セットと呼ばれます。${\displaystyle X}$
• ゲームに勝つための基準。

ゲーム中、プレイヤーは、どちらかのプレイヤーが勝利するまで、交互に、以前に獲得されていないポジションを獲得します。 のすべてのポジションが獲得され、どのプレイヤーも勝利しなかった場合、ゲームは引き分けとみなされます。 ${\displaystyle X}$

ポジショナル ゲームの典型的な例は、三目並べです。このゲームには、ゲーム ボードの 9 つのマス目と、勝利を決定する 8 つのライン (水平 3 本、垂直 3 本、斜め 2 本) があり、勝利の基準は、勝利セット全体を最初に保持したプレーヤーが勝利することです。ポジショナル ゲームのその他の例としては、ヘックスやシャノン スイッチング ゲームがあります。 ${\displaystyle X}$${\displaystyle {\mathcal {F}}}$

あらゆるポジショナルゲームには、正確に3つの選択肢があります。最初のプレーヤーが勝利戦略を持っているか、2番目のプレーヤーが勝利戦略を持っているか、両方のプレーヤーが引き分けを強制する戦略を持っているかです。^{[2] : 7}これらのゲームの研究で興味深い主な問題は、特定のゲームでこれら3つの選択肢のどれが当てはまるかということです。

ポジショナル ゲームは有限かつ決定論的で、完全な情報を持っています。したがって、理論上は完全なゲーム ツリーを作成し、これら 3 つのオプションのどれが当てはまるかを判断することが可能です。ただし、実際には、ゲーム ツリーは膨大になる可能性があります。したがって、ポジショナル ゲームは通常、より洗練された組み合わせ手法を使用して分析されます。

多くの場合、ポジショナルゲームへの入力はハイパーグラフと見なされます。この場合、

• の要素は頂点（または点）と呼ばれ、Vで表されます。${\displaystyle X}$
• の要素はエッジ（またはハイパーエッジ）と呼ばれ、EまたはHで表されます。${\displaystyle {\mathcal {F}}}$

ポジショナルゲームには多くのバリエーションがあり、ルールや勝利基準が異なります。

強力なポジショナルゲーム（メーカーメーカーゲームとも呼ばれる）

勝利セットのすべての要素を最初に獲得したプレイヤーが勝利します。ボードのすべての要素を獲得した状態でゲームが終了したが、勝利セットのすべての要素を獲得したプレイヤーがいない場合は、引き分けとなります。例としては、古典的な三目並べがあります。

メイカー・ブレーカーゲーム

2 人のプレイヤーは、メイカーとブレーカーと呼ばれます。メイカーは、勝利セットのすべての要素を獲得すると勝ちます。ボードのすべての要素を獲得した状態でゲームが終了し、メイカーがまだ勝利していない場合、ブレーカーが勝ちます。引き分けはあり得ません。例として、シャノン スイッチング ゲームがあります。

回避者と執行者のゲーム

プレイヤーは、Avoider と Enforcer と呼ばれます。Enforcer は、Avoider が勝利セットの要素をすべて獲得した場合に勝ちます。ボードのすべての要素を獲得した状態でゲームが終了し、Avoider が勝利セットを獲得していない場合は、Avoider が勝ちます。メイカー ブレーカー ゲームと同様に、引き分けはあり得ません。例としてSimがあります。

矛盾ゲーム

プレイヤーはバランサーとアンバランサーと呼ばれます。バランサーは、すべての勝利セットで各プレイヤーが頂点のおよそ半分を占めるようにすれば勝ちます。そうでない場合はアンバランサーが勝ちます。

ウェイターとクライアントのゲーム（ピッカーとチューザーのゲームとも呼ばれる）

プレイヤーはウェイターとクライアントと呼ばれます。各ターンで、ウェイターは 2 つのポジションを選択し、クライアントにそれを示します。クライアントはそのうちの 1 つを選択できます。

偏ったポジショナルゲーム

各ポジショナルゲームにはバイアスバリアントがあり、最初のプレーヤーは一度にp 個の要素を取得でき、2 番目のプレーヤーは一度にq 個の要素を取得できます (バイアスバリアントでは、 p = q =1)。

次の表は、文献で広く研究されている特定のポジショナル ゲームをいくつか示したものです。

• 位相ゲーム、位置ゲームを無限集合に一般化したもの
• バナッハ・マズールゲームは、位相空間上で特定の部分集合から選択してプレイするゲームであり、勝利条件はメイカー・ブレーカーゲームに似ている。