概要

更新日時:

多くの将棋プログラムの探索アルゴリズムでは、現在の局面から ある一定の深さの局面まで展開し、Min-max法により最善手と評 価値を求めるという方法をとる(実際には、深くなるほど展開す る手を絞ることや、部分的に探索を延長するなどの工夫がなさ れている)。

しかし、将棋を指す人でそのように手を読む人はいないだろう。 人間の場合は、現在の局面から「ありそうな展開」だけを考え て、その中で、もっとも自分が有利な展開になる手を選ぶ。 特に、上級者になればなるほど、「ありそうな展開」 は非常に絞られたものになってくる。そのような思考法をコン ピュータでも実現できないかと考えたのが激指のアルゴリズムの発想 の大本である。

ここで、「ありそうな展開」ということをもう少し具体的に 表現してみると、
「現在の局面から変化して実際に実現する確率が大きい局面」
というように考えることができる。

いま、 「遷移確率(ある局面が変化して別の局面になる確率)」が与 えられたとすると、局面が実現する確率は、次のように再帰的 に計算することができる。

(局面の実現確率)= (直前の局面の実現確率) x (遷移確率)

そうすると、ルート局面の実現確率100%から出発して、局面の 実現確率が、ある閾値以下になるまで展開すれば、「ありそう な展開」だけを読むことができそうである。

ここで問題になるのが、「遷移確率」をどのようにして求める かであるが、プレイヤーが合理的であれば、「最善手」がわかっ ていれば必ずその手を指すのだから、一般に、 「遷移確率」は「指し手が最善手である確率」といいか えることができる。

もちろん、多くの場合、「指し手が最善手である確率」を厳密 に求めることはできない(厳密にもとめることができたら、 そもそも探索をする必要すらないかもしれない)。しかし、 指し手の表面的な性質によって、その指し手が最善手である確 率の上限値を求めることはできる。 将棋をやったことのある人なら、 「直前に動いた駒を取る手」や「あたりになっている駒が 逃げる手」などが、最善手の確率が高いことはなんとなく感 じていることだろう。

その確率を実際に測定するために、プロの棋譜(「羽生善治実戦集」 に含まれている約600局)から指し手の 統計情報を抽出するということを行った。プロの指し手は、 統計的にみればほとんど最善手に近いと考えられるからである。 その結果、確率の高い手には、例えば、
「直前に動いた駒を駒得でとる手」.. 50 ~ 100%
「駒得をしながらの王手」 .. 43%
などがあった。

このようなアルゴリズムを用いることで、激指はより人間の上 級者の思考法に近い読みが可能になり、 特に、駒の激しい取り合いが続くような局面や、 王手が続いて敵玉を寄せていくような 局面で、コンピュータらしくない思いきりのよい手が 指せるようになっているようである。


激指のアルゴリズムへ戻る
ご感想・ご質問等がありましたら まで、お気軽にどうぞ。