HN 日本語サマリー

← 一覧へ戻る
プログラミング

Leanにおける組み合わせゲーム

Combinatorial Games in Lean (github.com)

27 pointsby wertyk3 コメント

要約

このリポジトリは、Lean 4を用いて組み合わせゲーム理論のトピックを形式化することを目的としています。組み合わせゲームは、2人のプレイヤーが交互に状態を変更し、完全情報、有限性、引き分けなしという特徴を持つゲームです。Nim、Hackenbush、Chompなどが例として挙げられます。リポジトリでは、一般的な組み合わせゲームの理論、特定のゲーム(Posetゲーム、Hackenbushなど)、ニムバーの理論、シュルレアル数の理論の形式化を目指しています。

全文翻訳

Leanにおける組み合わせゲーム

Lean 4での組み合わせゲーム理論のトピックの形式化。

それは何ですか?

組み合わせゲームとは、2人のプレイヤーがプレイし、終了が決まっており、完全情報を持つゲームのことです。言い換えれば、2人のプレイヤー(左と右と呼ばれる)が、常に完全な知識を持っているゲームの状態を交互に変更します。ゲームは永遠に続くことはなく、次に打つ手がないプレイヤーが負けとなります。引き分けはありません。

組み合わせゲームの例としては、Nim、Hackenbush、Chomp などがあります。例に当てはまらないものとしては、確率的要素を持つポーカー、引き分けがありうるチェス、あるいは永遠に続くガレ–スチュワートゲーム(ただし、それらに関する詳細はこちらのリポジトリを参照)があります。

スコープに含まれるもの

このリポジトリは、主に4つのことを形式化することを目指しています。

参考文献

組み合わせゲーム理論の開発は、主にConway (2001) に基づいており、さまざまなより現代的なリソースで補完されています。