ゲーム木探索 (Minimax・CFR)

対戦ゲームの最適手を探索するアルゴリズム群。ゲーム理論の均衡概念を計算機で求める実装側に相当する。

Minimax 法

2 人零和・完全情報ゲームの探索アルゴリズム。自分は利得最大化、相手は最小化すると仮定して木を評価する。

• alpha-beta 法 で枝刈りし無駄な探索を削減する
• 3 人以上やゼロ和でない場合への一般化（poly-matrix ゲーム、min-max 定理の拡張）は非自明

CFR (Counterfactual Regret Minimization)

不完全情報ゲーム（ポーカー、花札など）を解くアルゴリズム。後悔（regret）を反復的に最小化することで $ϵ$-ナッシュ均衡へ収束することが保証されている。

• Kuhn Poker のような小規模ゲームで実装され、ゲームは EFG (extensive-form game) フォーマットで記述する
• DeepMind の OpenSpiel は EFG 記述や Game 継承で自作ゲームに CFR を適用できる強化学習 OSS

実装上の道具

局面のハッシュ化には Zobrist hashing が使われる。盤ゲーム AI の通信は標準プロトコル（やねうら王提案）に揃える動きもある。

関連: game-theory / cdfy / _moc-algorithm