役割と仕組み

 今の局面ではなく、将来現れる可能性のある局面を考える対象にする役割を持ったのが探索です。
究極的には評価関数だけで次の指し手は決定できるのですが、現状はそこまで高性能な評価関数がないため
合法手の中から手を選んで局面を進め、その局面を評価関数に渡して評価させています。

 仕組みについてですが、現在の局面から合法手を生成し、各合法手に対しその手を指した局面を新たに生成、
そこで得られた各局面に対して合法手を生成し・・・、ということを繰り返すのが基本的な部分です。
そしてどこかのタイミングでその局面からの合法手の生成をやめて、代わりに局面を評価関数に渡し、評価値を得ます。
当然評価値を得た局面は沢山ありますが、自分は自分にとって評価値が最も高くなる手を選び、
相手は相手にとって評価値が最も高くなる手(=自分にとって評価値が最も低くなる手)を選ぶという前提のもと、最も自分の評価値が高くなる局面に繋がる手を選びます。
この考え方はミニマックス法といいます。
一言で言うなら
 「常に最悪の事態が起こると想定して、その中で最良の結果になるものを選ぶ」
という考え方です。

具体例を挙げてみます。
右図は3手の読みを表したゲーム木の図です。ゲーム木例
棒は指し手、その下の○はその手を指した結果の局面を表していて
上から下に局面が進んで行きます。
は自分が考える番、は相手が考える番です。
考える内容は、どちらも「次にどの手を指すのが自分にとって最も都合が良いか」です。
また、一番下の○に書いてある点数は3手目を指した結果の局面の評価値で
大きいほどが良く、小さいほどが良いことを示します。
例えば一番右下のは+250の○に繋がる手を選ぶ方が都合が良いので左側の手を選びます。
これにより、ここでは必ず左側の手を選ぶのでの評価値は+250となります。
これを各で繰り返していくと、
一番上の(=現在の局面)では左側の手を選ぶのが最も都合が良く
このの評価値は+300となります。

実際のプログラムはもっと効率の良い方法を使っていますが、基本的な考え方はこの通りです。

用いられている技術

 ミニマックス法の効率を上げた手法であるαβ探索、探索の途中で指し手を返す必要が出てきたときに
現時点での最善手を返すことの出来る利点もある反復深化深さ優先探索などがあります。
また、探索部分で機械学習を用いた手法として、激指の実現確率探索があります。
これは、探索中にあまりにありえない手が続いた場合に、この探索を途中でやめてしまうという手法です。
これによって無駄な先読みを減らす事ができます。
同様にツツカナも探索部分で機械学習を用いた手法を取り入れているようですが、具体的にどう使われているかは分かりません。
また、GPSで有名なクラスタ化も主に探索の性能を向上させるための技術です。

関連するワードと意味

・stockfish
  オープンソースのチェスプログラム。多くの人が細かな改良を加えている事で探索部分が優秀らしく、
  将棋プログラムに導入しているプログラムも多いです。ちなみにGPSfishのfishはここから。

・全幅探索
  分岐する可能性のある局面を全て生成してしらみつぶしに探索する手法。初優勝時のBonanzaが採用していました。
  全ての手を探索するのにコストがかかる一方、有望そうな指し手を選択しないという点ではそれに必要なコストは一切かかりません。

・選択的探索
  全幅探索と違い、合法手の中から有望そうな手だけを選んで探索をする手法。
  探索する局面の数は全幅探索に比べて少なくて済みますが、
  有望そうかどうかの判断にコストをかけすぎると、全幅探索のほうが良かったということになってしまいます。

・水平線効果
  探索できる手数に限界があることによって起きる現象。
  探索の限界となる範囲(=水平線)の向こう側にある手は一切考える(=見る)ことができないことからこう呼ばれます。
  特にどうやっても負ける場合に、負ける局面を探索できる限界の外に追いやるために
  無駄な王手のような絶対に手数が伸びる手を選ぶという形で現れることが多いです。
  コンピュータと対局すると、最後に無駄な王手をかけてくることがあるのはこれが原因です。
  王手などの特定の条件ではそこだけ読む手数を増やす、評価関数の性能を上げるといった対処法が挙げられます。