完全情報ゲームとは、ゲームにおける全ての情報が公開されており、かつ運の要素が一切無いゲームのことである。これに該当するゲームは、将棋、オセロ、チェスなどである。

我々は将棋やオセロの盤面を見て、それが自分にとって有利な 状況であるか不利な状況であるかをだいたい判断することができる。 だがコンピューターがそれを判断するにはどうすれば良いのであろうか。

例えば、オセロであれば単純に盤面にある自分の色の駒の数を 評価値Ｅとする。さらに、角に自分の色の駒がある場合、角に ある駒の数×10をＥに足す。以上のような評価値Ｅが コンピューターの場合の有利、不利を判断する材料となる。

我々がチェスや将棋をする時、現在の盤の状況だけでなく、 この先自分や敵がどのような手を打つかを考えてから駒を動かす。 この思考をコンピューターにやらせるためには以下のようにすれば良い。

コンピューターはどれが有効な手であるかの判断ができないので、とりあえず全ての手を試す。本来ならばゲーム終了までの全ての手を 調べられればよいのだが、コンピューターの処理能力の限界のため、 それは無理である。よって、「３手先まで」などと決めて 先の手を考えることにする。Ｎターン目に３手先まで考えた場合の図は以下の通り。

さて、あなたならＮターン目に右と左、どちらの手を打つだろうか。 「10があるから右だ」と思ったならば、残念ながら不正解である。 この場合、Ｎターン目には左の手を打つのが良い。なぜなら、 右の手を打った場合、敵はＮ＋１ターン目に10へ向かう右の手ではなく、（敵にとって）最悪でも5になる左の手を打つからである。よって、Ｎ＋１ターン目にどちらを選ばれても最低7になる左の手を打つのが良いわけである。

ちなみに、このように自分のターンでは最良の手を、敵のターンでは 最悪の手を選ぶような探索法をミニマックス法と呼ぶ。方法自体は大して難しくも無いが、この呼称を使うといかにも知識がありそうに見えるので覚えておいて損は無い。

先ほどの章ではいきなり答えを出してしまったが、コンピューターが 探索をする場合はそう簡単に結論を出すことは出来ない。この章では コンピューターの場合にはどうやって結論を出すのかを示すことにする。

簡潔に言うと、３手先の盤面の評価値を持ってきて、他の３手先の 評価値と比較し、自分のターンの時には最大のものを、敵のターンの 時には最小のものを選んでいけばよい。図にすると以下のようになる。

まず左端から探索する。4 < 7なので、7を上のターンの評価値とする。

1 < 8なので、8を上のターンの評価値とする。

敵のターンなので、より小さい7のほうを上のターンの評価値とする。

2 < 5なので、5を上のターンの評価値とする。

6 < 10なので、10を上のターンの評価値とする。

敵のターンなので、より小さい5のほうを上のターンの評価値とする。

最後に、自分のターンなので、より大きい7のほうを選択する。 このようにして、7の評価値へたどりつく手が最良であると判断する。

今回は決まった深さまでの全ての手を探索するミニマックス法のみ 紹介したが、探索する手を削減するアルファベータ法や、ハッシュに よる盤面記憶を用いて同じ盤面の探索を防ぐ方法など、より良い 探索法があるので興味を持った方はぜひ調べてみてもらいたい。