プログラミング
Leanにおける組み合わせゲーム
Combinatorial Games in Lean (github.com)
要約
このリポジトリは、Lean 4を用いて組み合わせゲーム理論のトピックを形式化することを目的としています。組み合わせゲームは、2人のプレイヤーが交互に状態を変更し、完全情報、有限性、引き分けなしという特徴を持つゲームです。Nim、Hackenbush、Chompなどが例として挙げられます。リポジトリでは、一般的な組み合わせゲームの理論、特定のゲーム(Posetゲーム、Hackenbushなど)、ニムバーの理論、シュルレアル数の理論の形式化を目指しています。
全文翻訳
Leanにおける組み合わせゲーム
Lean 4での組み合わせゲーム理論のトピックの形式化。
それは何ですか?
組み合わせゲームとは、2人のプレイヤーがプレイし、終了が決まっており、完全情報を持つゲームのことです。言い換えれば、2人のプレイヤー(左と右と呼ばれる)が、常に完全な知識を持っているゲームの状態を交互に変更します。ゲームは永遠に続くことはなく、次に打つ手がないプレイヤーが負けとなります。引き分けはありません。
組み合わせゲームの例としては、Nim、Hackenbush、Chomp などがあります。例に当てはまらないものとしては、確率的要素を持つポーカー、引き分けがありうるチェス、あるいは永遠に続くガレ–スチュワートゲーム(ただし、それらに関する詳細はこちらのリポジトリを参照)があります。
スコープに含まれるもの
このリポジトリは、主に4つのことを形式化することを目指しています。
- 一般的な組み合わせゲームの理論(温度、支配された位置、可逆な位置など)
- 特定の組み合わせゲームの理論(ポセットゲーム、Hackenbush、三目並べなど)
- ニム数の理論(代数閉体であることを証明する、最も単純な拡張定理を証明する)
- シュール数の理論(体の構造を確立する、ハン数としての表現を証明する)
参考文献
組み合わせゲーム理論の開発は、主にConway (2001) に基づいており、さまざまなより現代的なリソースで補完されています。
- Conway, J. H. - On numbers and games (2001)
- Dierk Schleicher and Michael Stoll - An Introduction to Conway's Games and Numbers (2005)
- Siegel, A. N. - Combinatorial game theory (2013)