読み方 ： ミニマックスげんり

概要

二者が交互に自分の行動を選択するようなゲームで、自分の手番では自分の利得が最も大きくなるように、相手の手番では自分の利得が最も小さくなるような選択肢を選んだとき、自分の利得が最も大きくなる選択肢がどれになるか探索する。

ゲームの展開は手番ごとに選択肢の数だけ枝分かれしていく木構造で表すことができ、これを「ゲーム木」という。頂点は自分の手番、2段目は相手の手番、3段目は自分の手番…というように、自分と相手の手番が交互に現れる。

何手か先までのミニマックス原理を構築し、末端には頂点からその経路をたどったときの結果（自分の利得）を書き入れる。末端の値から順に木を遡り、自分の手番では自分の利得が最大（max）になる選択肢を、相手の手番では自分の利得が最小（mini）になる手番を打つと仮定し、各手番の打ち手を決定していく。

木をすべてなぞると、頂点の現在の手番で打つべき手が一つに確定する。何手先まで読むかによって結果は変わり、先々まで読むほど精度の高い結果が得られるが、末端のノードの数は手数に対して指数的に増大していくため、実際には記憶容量や計算時間などで手数が制約される。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。