アルファベータ探索（読み）あるふぁべーたたんさく

日本大百科全書(ニッポニカ)

アルファベータ探索
あるふぁべーたたんさく

ゲームで次の一手を決めるための探索手法であるミニマックス法を高速化するための手法。

　ミニマックス法はゲームで次の手を決めるよい方法であるが、そのまま使うと膨大な局面の形勢を評価関数によってすべて点数化しなくてはならず、解を求めるのに時間を要してしまう。ミニマックス法と同じ結果を出すことを保証しながら評価関数で点数化する局面の数を大幅に減らすことに成功したのがアルファベータ探索である。アメリカの数学者、コンピュータ科学者のクヌースDonald E. Knuth（1938―　）の分析により、点数化すべき局面の数がミニマックス法でN個あったとするとアルファベータ探索ではもっともうまくいった場合で個まで減らすことができる。ゲームの実際のプログラムではミニマックス法をそのまま使うことはなく、このアルファベータ探索が用いられている。

［松原　仁　2020年1月21日］

出典　小学館　日本大百科全書(ニッポニカ)