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

日本大百科全書(ニッポニカ) 「アルファベータ探索」の意味・わかりやすい解説

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

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

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

松原 仁 2020年1月21日]

出典 小学館 日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について 情報 | 凡例

4月1日の午前中に、罪のないうそをついて人をかついでも許されるという風習。また、4月1日のこと。あるいは、かつがれた人のこと。四月ばか。万愚節。《季 春》[補説]西洋もしくはインドに始まる風習で、日本...

エープリルフールの用語解説を読む