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

メイカーブレーカーゲームは、ポジショナルゲームの一種です。^{[1] : 13–24}ほとんどのポジショナルゲームと同様に、メイカーブレーカーゲームは、ポジション/ポイント/要素の集合( ) と勝利セットの族( -のサブセットの族)によって記述されます。メイカーとブレーカーと呼ばれる2人のプレイヤーが、交互にまだ取られていない要素を取ってプレイします。 ${\displaystyle X}$${\displaystyle {\mathcal {F}}}$${\displaystyle X}$

メーカー-ブレーカー ゲームでは、メーカーが勝利セットのすべての要素を保持できれば勝ち、ブレーカーがこれを阻止できれば、つまり各勝利セットで少なくとも 1 つの要素を保持できれば勝ちます。引き分けはあり得ません。各メーカー-ブレーカー ゲームでは、メーカーまたはブレーカーのいずれかが勝利戦略を持っています。これらのゲームに関する主な研究上の疑問は、これら 2 つのオプションのどちらが成立するかということです。

古典的な Maker-Breaker ゲームはHexです。このゲームでは、勝利セットはすべてボードの左側から右側へのパスです。Maker は接続されたパスを所有することで勝利し、Breaker は左から右への接続されたパスをすべてブロックするため、上から下への接続されたパスを所有することで勝利します。

三目並べは、メイカー・ブレーカーゲームとしてプレイできます。このバリアントでは、メイカーの目標は 3 つのマス目を連続して選ぶことであり、ブレーカーの目標はメイカーが 3 つのマス目を選ばないようにすることです。このバリアントでは、ブレーカーに勝利戦略があります。これは、2 番目のプレーヤーがドロー戦略を持つ古典的なバリアント (強力なポジショナル ゲーム) とは対照的です (強力なポジショナル ゲーム#メイカー・ブレーカー ゲームとの比較を参照)。

正のCNF（すべて正のリテラル）上の順序なしCNFゲーム^[2]は、MakerがCNFを偽造しようとし、Breakerがそれを満たそうとするMaker-Breakerゲームと考えることができます。

ゲームの盤が何らかのグラフ（通常は完全グラフとみなされる）の辺集合であり、勝利集合の族が（ここでは接続性など何らかのグラフ特性（通常は単調増加とみなされる [明確化?]））である場合の Maker-Breaker ゲームのプレイに関する研究がいくつか行われています。^[3]たとえば、シャノンスイッチングゲームは、勝利集合が 2 つの異なる頂点間のパスである Maker-Breaker ゲームです。 ${\displaystyle E}$ ${\displaystyle G}$${\displaystyle {\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ は性質 }}{\mathcal {P}}\}}$${\displaystyle {\mathcal {P}}}$

メイカー・ブレーカーゲームでは、通常メイカーが先にプレイ​​します。しかし、ブレーカーを先にプレイ​​させることも可能です。先手は常に有利です。後手メイカーの勝利戦略は、先手メイカーの勝利戦略につながります。同じことはブレーカーにも当てはまります。^{[1] : 15}${\displaystyle (X,{\mathcal {F}})}$${\displaystyle (X,{\mathcal {F}}).}$

さらに、すべてのゲームについて、その横断ゲームを定義することができます。この横断ゲームでは、勝利セットは元のゲームの各勝利セットに接する最小セットです。たとえば、元のゲームで勝利セットが { {1,2,3},{4,5,6} } である場合、双対ゲームでは { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} } になります。すると、 で最初にプレイするブレーカーの勝利戦略は、で最初にプレイするメーカーの勝利戦略とまったく同じになります。^{[4] : 2}${\displaystyle (X,{\mathcal {F}})}$ ${\displaystyle (X,{\mathcal {F^{*}}})}$${\displaystyle (X,{\mathcal {F}})}$${\displaystyle (X,{\mathcal {F^{*}}})}$

さらに、 Maker-Breaker ゲームの代替のMisère規則として、Avoider-Enforcer ゲームと呼ばれるものがあります。

Maker-Breakerゲームは、各セットのサイズが6に制限されていてもPSPACE完全である。^[5] 最初の結果は1978年のもので、各セットのサイズが11に制限されており、^[6]ゲームは(POS CNF 11)と表現されていた。 ${\displaystyle G}$

Maker-Breaker ゲームを解くには、いくつかの種類の戦略が一般的に使用されます。

一部のゲームでは、 Xの要素(またはそのサブセット) を、互いに素なペアのセットに分割することができます。特定の条件下では、プレーヤーは次のような貪欲な戦略を使用して勝つことができます: 「対戦相手がペアiの要素を選択するたびに、ペアiの他の要素を選択します。」

「特定の条件」は Maker と Breaker で異なります。ペアリング戦略を参照してください。

強いポジショナルゲームにおけるファーストの勝利戦略はすべて、メーカーブレーカーバリアントにおけるメーカーの勝利戦略でもあります (強いポジショナルゲーム#メーカーブレーカーゲームとの比較を参照)。特に、強いポジショナルバリアントでドローが不可能な場合、メーカーブレーカーバリアントではメーカーに勝利戦略があります。その逆は必ずしも当てはまりません。メーカーブレーカーバリアントでのメーカーの勝利戦略は、強いバリアントでのファーストの勝利戦略であるとは限りません。強いバリアントでは、セカンドがファーストより先に勝利セットを獲得することで勝つことができるためです。

対照的に、メイカー-ブレーカー ゲームにおけるブレーカーのすべての勝利戦略は、強いポジショナル バリアントにおけるセカンドのドロー戦略でもあります。

メイカー/ブレーカーによってすでに取得された要素の数に基づいて 、各勝利セットにポテンシャルを割り当てる関数を見つけることができるとします。ポテンシャル関数は、次のプロパティを満たす必要があります。

• 勝利セットの可能性は 0 から 1 の間です。
• Breaker が要素を取得すると、その要素を含むすべてのセットのポテンシャルは 0 に低下し、0 のままになります。
• Maker が要素を取得すると、それを含むすべての (壊れていない) セットのポテンシャルが増加します。
• Makerが所有するセットのポテンシャルは1です。

そして、潜在的合計が 0 より大きい場合は Maker が勝ち、潜在的合計が 1 より小さい場合は Breaker が勝ちます。したがって、

• 初期合計が 0 より大きく、Maker が潜在的な合計が弱く増加するようにプレイできる場合、これは Maker にとって勝利の戦略です。
• 初期合計が 1 未満で、Breaker が潜在的な合計が弱く減少するようにプレイできる場合、これは Breaker にとって勝利の戦略です。

ポール・エルデシュとジョン・セル​​フリッジは、ブレーカーに勝利戦略を保証する一般条件を提示しました。^[7]彼らはポテンシャルベースの戦略を使用しました。彼らは、 占有されていない頂点を持つ任意の（壊れていない）勝利セットのポテンシャルを と 定義しました。したがって、Maker が占有するセットのポテンシャルは確かに です 。Maker が要素を取るたびに 、それを含むすべてのセットのポテンシャルはに増加します。つまり、 だけ増加します。Breaker が要素を取るたびに、それを含むすべてのセットのポテンシャルは 0 に低下します。つまり、 だけ減少します。すべての要素に、Maker がそれを取った場合の合計ポテンシャル増加に等しい値、つまり を割り当てます。Breaker の勝利戦略は、最も高い値 を持つ要素を選択することです。これにより、Breaker の最初のターン以降、ポテンシャルが常に弱く減少することが保証されます。したがって、Breaker の最初のターンでのポテンシャルが 1 未満の場合、Breaker が勝ちます。 Maker の最初のターンでは、最大でポテンシャルを 2 倍にすることができます (すべての勝利セットに含まれる要素を取得することによって)。したがって、ゲーム開始時にポテンシャルが 1/2 未満であれば十分です。要約すると、エルデシュ-セルフリッジ定理は次のようになります。 ${\displaystyle E}$${\displaystyle |E|}$${\displaystyle 2^{-|E|}}$${\displaystyle 2^{-0}=1}$${\displaystyle 2^{-(|E|-1)}}$${\displaystyle 2^{-|E|}}$${\displaystyle 2^{-|E|}}$${\displaystyle w(v):=\sum _{v\in E}2^{-|E|}}$

の場合、Breaker の勝ちとなります${\displaystyle \sum _{E\in {\mathcal {F}}}2^{-|E|}}}2^{-|E|}1/2}$${\displaystyle {\mathcal {F}}}$。

この定理は、非常に簡単に確認できる条件を与え、この条件が満たされると、Breaker の最適戦略を計算するための効率的なアルゴリズムも与えます。

ポテンシャル関数には確率的な解釈があります。勝利セットのポテンシャルとは、ゲームが今後ランダムにプレイされた場合に、Maker がそのセットを所有する確率です。したがって、ポテンシャルの合計は、ゲームがランダムにプレイされた場合に Maker が所有する勝利セットの予想数です。ポテンシャルの合計が 1 未満の場合は常に、Maker が所有するセット数が 0 になるようにゲームをプレイする方法がなければなりません。ポテンシャルの合計が 1 未満になるようにすることで、Breaker は基本的にこの確率的主張をランダム化せず、ゲームの最後には確実になります。

なお、Breaker が先にプレイ​​した場合は、条件が に変わります。 ${\displaystyle \sum _{E\in {\mathcal {F}}}2^{-|E|}}}2^{-|E|}1}$

特に、勝利セットがすべてサイズkの場合（つまり、ゲームハイパーグラフが k一様である場合）、エルデシュ-セルフリッジ定理によれば、勝利セットの数が 未満であれば常にブレーカーが勝利する。^[7]${\displaystyle |{\mathcal {F}}|<2^{k-1}}$${\displaystyle 2^{k-1}}$

数は限られています。 つまり、勝利セットの数がちょうど であり 、Maker が勝利戦略を持つ -一様ハイパーグラフが存在します。たとえば、高さ の完全な二分木を考えてみましょう。これには葉があります。V をツリー ノードの集合として定義し、H をルートから葉までのすべてのパスの族として定義 します。Maker はルートを選択することから始めます。次に、Breaker が左のサブツリーの要素を選択した場合、Maker は右のサブツリーのルートを選択し、その逆も同様です。このように続けることで、Maker は常に完全なパス、つまり勝利セットを選択できます。 ${\displaystyle 2^{k-1}}$${\displaystyle k}$${\displaystyle 2^{k-1}}$${\displaystyle k-1}$${\displaystyle 2^{k-1}}$${\displaystyle 2^{k-1}}$

すべての勝利セットがペアごとに独立しており、そのサイズが少なくとも 2 の場合、Breaker はペアリング戦略を使用して勝つことができます。

ここで、勝利セットがほぼ互いに素であると仮定します。つまり、任意の 2 つの勝利セットには共通する要素が最大で 1 つしかありません。すべての勝利セットのサイズが で、勝利セットの数が 未満の場合(ある固定定数 c について)、Breaker には勝利戦略があります。^[8] したがって、この状況は Breaker にとって一般的な場合よりも簡単ですが、勝利セットが互いに素である場合よりも困難です。 ${\displaystyle k}$${\displaystyle 4^{kc{\sqrt {k}}}}$

要素集合の次数を、この集合を含む異なる勝利集合の数として定義する。集合族のペア次数を と表記し、要素ペアの最大次数（すべてのペアの最大値）として定義する。すべての勝利集合のサイズが で、勝利集合の数が より多い場合、Maker には勝利戦略がある。^{[9] ：定理 1}${\displaystyle d_{2}}$${\displaystyle k}$${\displaystyle 2^{k-3}\cdot d_{2}\cdot |X|}$

この戦略は、エルデシュとセルフリッジが使用したのと同じポテンシャル関数を使用します。つまり、占有されていない要素（およびブレーカーによって占有されている要素がない） を持つ勝利セットのポテンシャルは です。要素の価値は、ブレーカーがその要素を取得した場合の合計ポテンシャル減少であり、メーカーがその要素を取得した場合の合計ポテンシャル増加と同じです。メーカーの戦略は、最も価値の高い要素を取得することです。 ${\displaystyle E}$${\displaystyle |E|}$${\displaystyle 2^{-|E|}}$

Maker が要素を取るたびに、それを含むすべての勝利セットのポテンシャルは 増加します。Breaker が要素を取るたびに、それを含みMaker の要素を含まないすべてのセットのポテンシャルは 減少します。したがって、一度触れられた勝利セットだけを考えると、潜在的合計は弱く増加します。潜在的合計が減少するのは、Maker の要素と Breaker の要素の両方を含むセットの場合のみです。これらのセットは を獲得しますが、その後 を失うため、全体として を失います。このようなセットには少なくとも 2 つの要素があるため、このような各セットは最大で 1/4 を失います。限定ペア次数の仮定により、このようなセットの数は最大でd ₂です。したがって、各ラウンドの後、潜在的合計は最大でd ₂ /4 減少します。ラウンドの数は |X|/2 であるため、最終的な潜在的合計は初期ポテンシャルよりも最大で 小さくなります。初期ポテンシャルは です。 ${\displaystyle 2^{-|E|}}$${\displaystyle 2^{-|E|}}$${\displaystyle 2^{-|E|}}$${\displaystyle 2^{-(|E|-1)}}$${\displaystyle 2^{-|E|}}$${\displaystyle d_{2}\cdot |X|/8}$${\displaystyle |{\mathcal {F}}|\cdot 2^{-k}}$

の場合、最終的な潜在的可能性は 0 より大きいため、潜在的可能性が 1 である勝利セットが少なくとも 1 つ存在します。このセットは Maker が所有します。 ${\displaystyle |{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8}$

の彩色数は、Xの要素を着色するために必要な最小の色数であり、Xのどの集合も単色にならない。の彩色数 が3の場合、Makerは勝利戦略を持っている。^[10]${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$

次の表は、プレイヤーの 1 人が勝利戦略を持つことを保証するいくつかの条件をまとめたものです。「タイトネス」列の条件は、戦略が機能しなくなる特定のハイパーグラフがわかっている場合を示します。

すべての条件において、k は勝利セットのサイズです (つまり、ゲーム ハイパーグラフはk均一です)。

両方のプレイヤーが Breaker の目標を達成すること (つまり、各勝利セットに少なくとも 1 つの要素があること) を希望するゲームをプレイすることも可能です。その場合、ゲームは必ずしもゼロサムではなく、両方のプレイヤーが勝つ可能性があります。実際、Maker-Breaker ゲームで Breaker が勝利戦略を持っているときはいつでも、Breaker-Breaker ゲームで 2 人の Breaker が両方とも勝つ可能性があります。

この戦略の応用として、ハイパーグラフを彩色する効率的なアルゴリズムがある。k一様ハイパーグラフの頂点を 2 色で彩色し、各ハイパーエッジで両方の色を表現するとしよう。エルデシュは 1963 年に確率的手法を用いて、ハイパーエッジの数が 未満のときは常にそのような彩色が存在することを証明した。言い換えれば、そのような彩色が存在するためにはハイパーグラフは 2 一様でなければならない。(特性 B を参照) しかし、その証明は構成的ではなかった。ブレーカーの構成的勝利戦略を用いると、2 人のブレーカーがそれぞれの勝利戦略で対戦することでハイパーグラフを彩色できる。どちらのプレイヤーも勝利する。つまり、各プレイヤーはすべてのハイパーエッジに少なくとも 1 つの頂点を持つことになる。^{[1] : 17–20}${\displaystyle 2^{k-1}}$${\displaystyle {\mathcal {F}}}$

勝つために、Maker は勝利セット全体を占有する必要はなく、そのようなセットの一部を所有するだけでよいとします。この場合、Breaker はいつ勝つことができますか?

1 セットにm 個の要素がある (ただし、Breaker は要素を所有していない)。各勝利セットのサイズが少なくともmで、セットの数が 未満の場合、Breaker は依然として勝利戦略を持っています。この戦略では、ポテンシャル関数を使用します。「壊れた」セットのポテンシャルは 0 で、壊れていないセット E のポテンシャルは です。 ここで、r(E) は、Maker が勝つために取得する必要がある要素の数です。したがって、すべての勝利セットの初期ポテンシャルは であり 、Maker が占有するセットのポテンシャルは 1 です。ここからの証明は、エルデシュ-セルフリッジの定理と同じです。^{[9] : 補題 1}${\displaystyle 2^{m-1}}$${\displaystyle 2^{-r(E)}}$${\displaystyle 2^{-m}}$

勝つためには、Maker が1 つの勝利セット内の要素のt分の 1 だけを所有する必要があるとします ( )。したがって、Breaker は、すべてのセット内のポイントの (1- t )より大きい部分を所有する必要があります。定数を定義します(標準バリアントでは)。 ${\displaystyle 1/2<t\leq 1}$${\displaystyle c_{t}:=(2t)^{t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}}$${\displaystyle t=1,c_{t}\to 2}$

• ならば、ブレイカーは${\displaystyle \sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}}}$ 最初に をプレイするときに 勝利戦略を持つ。^{[9] ：補題3}
• ならば、ブレイカーは${\displaystyle \sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}}$2番目にプレイするときに勝利戦略を持っている。^[11]

特に、すべてのセットのサイズがkで、その数が 未満の 場合、Breaker (最初にプレイする) が勝利戦略を持ちます。 ${\displaystyle {c_{t}}^{k}}$

この戦略では、ポテンシャル関数を使用します。勝利セットのポテンシャルは と定義されます。ここで、r はセットを占有するためにメーカーが取得する必要がある要素の数、sはセットを破るためにブレーカーが取得する必要がある要素の数です。メーカーがセットを占有する場合、そのポテンシャルはある時点で少なくとも 1 になります。したがって、ポテンシャルの合計を 1 未満に保つことができれば、ブレーカーが勝ちます。ブレーカーの戦略は、その要素を含む勝利セットのポテンシャルの合計として定義される、最も高い値を持つ要素を取得することです。 ${\displaystyle (2t)^{-r}(2-2t)^{-s}}$

Maker が要素を取るたびに、それを含むすべてのセットのポテンシャルは 2 t倍になるため、現在のポテンシャルの (2 t -1) 倍に増加します。Breaker が要素を取るたびに、それを含むすべてのセットのポテンシャルは (2-2 t ) 倍になるため、現在のポテンシャルの (1-2 t ) 倍に増加します。Breaker と Maker の両方が同じセットに触れるたびに、そのポテンシャルは 2 t (2-2 t ) 倍になるため、現在のポテンシャルの -(2 t -1) ²倍に増加します。Breaker の要素は最も高い値を持つため、ポテンシャルの合計は常に減少します。したがって、最初のポテンシャルの合計が 1 未満の場合、Breaker が勝ちます。

頂点 ( ) と勝利セット ( )が無限にある場合、Maker-Breaker ゲームの定義は微妙になります。この場合、すべてのj > 0 に対して、Breaker がj ターンまでに Maker が勝利セットを完全に占有するのを防ぐことができる 場合、Breaker は勝利戦略を持っていると言えます。 ${\displaystyle |V|=\infty }$${\displaystyle |H|=\infty }$

• 派閥ゲーム
• 等差数列ゲーム
• 偏ったポジショナルゲーム
• 回避者と執行者のゲーム