2009-11-08

■　Bonanzaの指し手生成ルーチン完全解読(1)

Bonanzaの指し手生成ルーチンは、genXXX.cというファイルにあり、次の5つのファイルから構成される。

1) gennocap
2) gencap.c
3) gendrop
4) genchk.c
5) genevasn.c

名前からすると、
1) は駒を捕獲しない指し手(generate no captures)
2) は駒を捕獲する指し手(generate catures)
3)は駒を打つ手(generate drop)
4)は王手になる手(generate check)
5)は王手を回避する手(generate evasion)
であると予想され、それはおおむね正しい。

しかし、よくよくソースを読むと1),2)は、そうはなっていない。ここが大変重要なので、私が以下に正確な情報を記す。

1)は、
駒を取らない手だが、実際はさらに限定的である。
　歩・角・飛　→ 自陣および中段での移動。敵陣への移動は含まない。
　銀　→ 成り、不成も含む。
　金と金と同等の成り駒・王　→　すべての指し手
　香・桂　→　敵陣へ移動する指し手も含むが、成りは含まない。

2)
　歩・角・飛　→ 歩の成る手。駒を取るものも、取らないものも生成する。成れる歩の不成はBonanzaでは読まないし生成しない。
　銀　→ 駒をとるすべての手。成り、不成も含む。
　金と金と同等の成り駒・王　→　駒を取るすべての指し手を生成。
　香・桂　→　駒を取る手 + 敵陣へ移動して駒を取らない成り

である。

すなわち、1)は、nocapではなく、no cap(駒をとらない指し手)のうち局面の評価値の変動がそれほどない手である。2) はcap(駒をとる手)ではなく、局面の評価値が大きく変動する手で、歩、角、飛の(駒をとらない)成る手も含むのである。

また、1) + 2) + 3) = すべての指し手になり、1),2),3)は互いに排反であるように設計してある。

ここが重要で、排反にしておかないと重複している手を除去する計算コストが発生するので、指し手を評価値の変動の大きさ別にいくつかのグループにわけて、かつ、それぞれのグループが排反であるように設計するのはとても大切なことである。

また、複数のグループに分けるのは、一度にすべての指し手を生成しなくて済むからである。まず、2)だけ生成して、それで指し手を進めて局面を評価して、枝刈りが生じれば、1),3)を生成する必要はなくなる。

すなわち、ここでは、指し手生成に関して一種の遅延処理(lazy evaluation)が行なわれていると解釈することが出来る。(※　コンピュータ将棋ソフトで「評価」というとどうしても局面の評価を想像してしまうので、ここでは、lazy evaluationを「遅延評価」とは訳さず、「遅延処理」と訳した。)

言うまでもなく、指し手生成コストが増大しない範囲でもう少し細かくグループ分けをすれば、その分だけ余計な指し手を生成しなくて済むので全体の効率は良くなる。Bonanzaはそういう改良をしたほうがいいと私は思うが、その話は綿密な検証を要するので今回は割愛する。

■　まとめ

今回は、Bonanzaの指し手の分類を詳しく説明した。また、指し手生成はいくつかのグループに分かれ、王手/王手回避を除けば、それぞれが排反であることも説明した。

次回からは、それぞれの指し手生成ルーチンを見ていく。