ツェルメロの定理（ゲーム理論）

ゲーム理論において、ツェルメロの定理は、プレイヤーが交互に行動し、偶然が意思決定プロセスに影響を及ぼさない、完全情報に基づく有限の2人ゲームに関する定理である。この定理によれば、ゲームが引き分けに終わらない場合、2人のプレイヤーのうち1人が必勝戦略（つまり、勝利を強制できる）を持っている必要がある。別の言い方をすると、引き分けが可能であるという条件を除いてこれらの条件をすべて満たすゲームでは、最初のプレイヤーが勝利を強制できるか、2番目のプレイヤーが勝利を強制できるか、または両方のプレイヤーが少なくとも引き分けを強制できるかのいずれかである。^[1] この定理は、 1913年にチェスの例としてこの定理を証明したドイツの数学者で論理学者のエルンスト・ツェルメロにちなんで名付けられた。

ツェルメロの定理は、完全情報と交互の動きを伴う有限段階の2人用ゲームすべてに適用できる。ゲームは、以下の条件を満たす必要がある。ゲームには2人のプレイヤーがいる。ゲームは完全情報に基づく。ボードゲームは有限である。2人のプレイヤーは交代で手番を回せる。偶然の要素は存在しない。ツェルメロは、このタイプのゲームは数多く存在すると述べたが、彼の定理は主にチェスゲームに適用されてきた。^{[2] [3]}

チェスに当てはめると、ツェルメロの定理は「白が勝利を強制できるか、黒が勝利を強制できるか、あるいは両者が少なくとも引き分けを強制できるか」のいずれかであると述べている。^{[2] [3]}

ツェルメロのアルゴリズムはゲーム理論の基礎となるアルゴリズムですが、有限ゲーム以外の分野にも応用できます。チェス以外にも、ツェルメロの定理はコンピュータサイエンスのあらゆる分野に適用されています。特に、モデル検査や値の相互作用に応用されています。^[4]

ツェルメロの研究によると、完全情報を持つ2人ゼロサムゲームでは、プレイヤーが勝てる位置にいる場合、他のプレイヤーがどのような戦略を採用しても、そのプレイヤーは常に勝利を強制できる。さらに、結果として、プレイヤーが勝てる位置にいる場合、ゲーム内の位置の数以上の動きが必要になることは決してない（位置とは、駒の位置と次に動くプレイヤーの位置として定義される）。^[1]

1912年、ケンブリッジで開催された第5回国際数学者会議で、エルンスト・ツェルメロは2つの講演を行った。最初の講演では数学分野の基礎における公理的手法と遺伝的手法について取り上げ、2番目の講演ではチェスのゲームについて語った。2番目の講演がきっかけでツェルメロはゲーム理論に関する論文を執筆した。熱心なチェスプレイヤーだったツェルメロは、集合論をチェスのゲームに応用することに関心があった。定理を説明したツェルメロのオリジナルの論文「 チェスの理論における理論の応用」は、1913年にドイツ語で出版された。これはゲーム理論に関する最初の論文とみなすことができる。^{[5]ウルリッヒ・シュヴァルベとポール・ウォーカーは1997年にツェルメロの論文を英語に翻訳し、}ツェルメロとゲーム理論の初期の歴史の付録として出版した。^[1]

ツェルメロは、偶然性のない 2 人ゲームのクラスを考察します。このクラスでは、プレイヤーは完全に反対の利益を持ち、有限の数のポジションしか可能ではありません。ゲームでは有限の数のポジションしか可能ではありませんが、ツェルメロは停止規則を考慮していないため、動きの無限のシーケンスを許容します。したがって、彼は無限のゲームの可能性を許容します。次に、次の 2 つの問題に取り組みます。

1. プレイヤーにとって「勝利」の立場にいるとはどういう意味でしょうか。また、これを客観的な数学的方法で定義することは可能ですか。
2. プレイヤーが勝てる立場にある場合、勝利を強制するために必要な移動回数を決定できますか?

最初の質問に答えるために、ツェルメロは、必要十分条件は、ある集合が空でないことであり、その集合には、他のプレイヤーのプレイ方法に関係なくプレイヤーが勝つことができるすべての可能な一連の動きが含まれると述べています。しかし、この集合が空の場合、プレイヤーが達成できる最高の結果は引き分けです。そこでツェルメロは、プレイヤーが負けを無限回の手数だけ延期できる、つまり引き分けになる可能性のあるすべての可能な一連の動きを含む別の集合を定義します。この集合は空である可能性もあります。つまり、対戦相手が正しくプレイした場合、プレイヤーは有限回の手数だけ負けを回避できます。しかし、これは対戦相手が勝ちを強制できることと同等です。これがツェルメロの定理の現代版すべてに共通する基礎となっています。

2 番目の質問について、ツェルメロは、ゲーム内のポジションの数よりも多くの動きが必要になることは決してないと主張しました。彼の証明は背理法による証明です。つまり、プレーヤーがポジションの数よりも多くの動きで勝つことができると仮定します。鳩の巣原理によ​​り、少なくとも 1 つの勝利ポジションが 2 回出現している必要があります。したがって、プレーヤーは最初の出現時に 2 回目と同じようにプレイし、ポジションの数よりも少ない動きで勝つことができた可能性があります。

1927年、ハンガリーの数学者デーネス・ケーニヒはツェルメロの論文を改訂し、元の研究のいくつかの欠陥を指摘した。まず第一に、ケーニヒは、ツェルメロは、例えば白が勝ちの局面にいる場合、ゲーム内の局面の数よりも少ない手数で常に勝利を強制できることを実証していないと主張する。ツェルメロは、白は関連する勝ちの局面の可能性が最初に現れたときに行動を変え、繰り返さずに勝つことができると主張した。しかし、ケーニヒは、この議論は1回のゲームでの移動数を可能な局面の数よりも少なくするだけでは不十分であるため、正しくないと主張する。したがって、ツェルメロは、勝っているプレーヤーが常に繰り返さずに勝つことができると主張したが、証明はしなかった。ケーニヒによる2番目の反論は、「ある局面が最初に現れたときに2番目と同じことをして、より少ない手で勝つ」という戦略は、その局面で黒が動く番である場合は実行できないというものである。しかし、この議論は正しくない。なぜなら、ツェルメロは黒と白のどちらが動くかという2つの局面を異なるものとして考えたからである。^[5]

ツェルメロは証明方法として後方帰納法を使ったと信じられてきた。しかし、ツェルメロの定理に関する最近の研究では、後方帰納法はチェスの戦略を説明するために使われていなかったことが実証されている。一般に信じられていることとは反対に、チェスは50手ルールまたは3回繰り返しルールの少なくとも1つがなければ有限ゲームではない。厳密に言えば、チェスは無限ゲームであるため、後方帰納法はこのゲームでミニマックス定理を提供しない。^[6]

後方帰納法は、時間を遡って推論するプロセスです。これは、完全情報の展開形ゲームを分析して解決するために使用されます。この方法は、ゲームを最後から分析し、最初に戻るまで遡ります。このプロセスでは、後方帰納法によって、最後の動きをしたプレイヤーにとって最善の戦略が決定されます。次に、ゲームの最後から2番目のプレイヤーの最終戦略が決定されます。このプロセスが繰り返され、ゲームのすべてのポイントで最善のアクションが見つかりました。したがって、後方帰納法によって、元のゲームのすべてのサブゲームのナッシュ均衡が決定されます。 ^[4]

ツェルメロの原論文に後方誘導が含まれていない理由はいくつかあります。

まず、シュワルベとウォーカー (2001) による最近の研究では、ツェルメロの論文に後方帰納法の基本的な考え方が含まれていることが実証されましたが、ツェルメロはこの定理について正式な声明を出していません。ツェルメロのオリジナルの方法は、非反復という考え方でした。後方帰納法について最初に言及したのは、 1928 年にカルマール・ラースローです。カルマールは、ツェルメロとケーニヒの研究を論文「抽象ゲームの理論について」で一般化しました。カルマールは、「勝てる状況が与えられた場合、どれだけ早く勝利を強制できるか」という疑問に取り組んでいました。彼の論文では、プレイヤーが勝てる状況であれば、反復なしで勝利することが可能であることが示されました。カルマールの非反復の証明は、後方帰納法による証明でした。カルマールは、論文でサブゲームと戦術の概念を導入しました。カルマールの中心的な主張は、あるポジションが勝ちポジションになるには、プレイヤーが有限の手で勝つ必要があるということである。また、プレイヤーAにとっての勝ちポジションは、プレイヤーBにとっては常に負けポジションである。^[7]

• 原著論文（ドイツ語）
• ウルリッヒ・シュヴァルベ、ポール・ウォーカー、「ツェルメロとゲーム理論の初期の歴史」、ゲームと経済行動、第 34 巻、2001 年、123-137 ページ、オンライン