ペアリング戦略

ポジショナルゲームにおいて、ペアリング戦略とは、プレイヤーが勝利を保証し、あるいは少なくとも引き分けに持ち込むために用いる戦略です。これは、ゲーム盤上のポジションを互いに素なペアに分割することに基づいています。対戦相手がペアのポジションを選んだ場合、プレイヤーは同じペアのもう一方のポジションを選びます。

例

5×5の三目並べを考えてみましょう。12個の互いに素な盤面のペア（1,...,12で表す）を作成できます。^{[1] : 3}

11	1	8	1	12
6	2	2	9	10
3	7	*	9	3
6	7	4	4	10
12	5	8	5	11

中心要素 (* で示される) はどのペアにも属さないことに注意してください。この戦略では必要ありません。

水平、垂直、斜めの各ラインには、少なくとも1つのペアが含まれます。したがって、次のペア戦略を使用して、強制的にドローを成立させることができます。「相手がペアiの要素のいずれかを選択するたびに、ペアiのもう1つの要素を選択する」。ゲーム終了時には、各勝利ラインの要素を1つずつ獲得します。したがって、相手が勝つことは不可能です。

両方のプレイヤーがこの戦略を使用できるため、ゲームは引き分けになります。

この例は、任意のMaker-Breakerゲームに一般化されています。このようなゲームでは、Makerの目標は勝利セット全体を占領することであり、Breakerの目標は各勝利セットの要素を所有することで、それを防ぐことです。

メーカーのペアリング戦略

Makerのペアリング戦略には、次のような要素ペアの集合が必要である: ^{[1] : 119}

• すべてのペアはペアワイズディスジョイントです。
• 各ペアの少なくとも 1 つの要素を含むすべてのセットには、何らかの勝利セットが含まれます。

ブレイカーがペアの要素を選ぶたびに、メイカーは同じペアのもう一方の要素を選びます。最終的に、メイカーのセットには各ペアから少なくとも1つの要素が含まれます。条件2により、メイカーは勝利セット全体を占有します（メイカーが後攻の場合でも同じです）。

例として、ルートを除く完全二分木の頂点をすべて含むゲームボードを考えてみましょう。勝利セットとは、葉からルートの2つの子のいずれかへのすべてのパスです。各要素をその兄弟とペアにすることで、要素をペアに分割できます。ペアリング戦略により、Makerは後攻でも勝利が保証されます。Makerが先攻の場合、ゲームボードにルートが含まれていても勝利できます。最初のステップではルートを選択し、それ以降は上記のペアリング戦略に従います。

ブレーカーのペアリング戦略

Breaker のペアリング戦略には、次のような要素ペアのセットが必要です。

• すべてのペアはペアワイズディスジョイントです。
• すべての勝利セットには少なくとも 1 つのペアが含まれます。

Makerがペアの要素を選ぶたびに、Breakerは同じペアのもう一方の要素を選びます。最終的に、Breakerは各ペアに要素を1つずつ持ちます。条件2により、Breakerは各勝利セットに要素を1つずつ持ちます。

5x5の三目並べにおけるこのようなペアリング戦略の例が上記に示されています。^{[1] ：2～3は}4x4と6x6の三目並べの他の例を示しています。

Breaker がペアリング戦略を持つもう 1 つの単純なケースは、すべての勝利セットがペアごとに分離されており、そのサイズが少なくとも 2 である場合です。

参考文献

1. ヘフェッツ、ダン;マイケル・クリヴェビッチ;ストヤコビッチ、ミロシュ。ティボル・サボ（2014）。ポジショナルゲーム。オーバーヴォルファッハセミナー。 Vol. 44. バーゼル: Birkhäuser Verlag GmbH。ISBN 978-3-0348-0824-8。