今回は、指し手生成器と生成される指し手の分類についての説明です。

enum Piece

前回、「駒」と「駒種」との違いについて説明した。

しかし、まだPiece型については詳しく説明していなかった。Piece型についてはやねうら王miniでは次のように定義されている。

ぱっと見てわかることは、
・生駒に8(PIECE_PROMOTE)を足すと成り駒になる。逆に成り駒から8を引くと生駒になる。
・先手の駒に16(PIECE_WHITE)を足す後手の駒になる。
・駒のない升などを表す値は0(NO_PIECE)である
などだろう。

もちろん、8とか16のように2の累乗にしてあるのは、bit操作で済むからである。

例えば、駒pc(後手の駒かも知れないし、成駒かも知れない)が与えられたときに、その駒種(先後の区別なし)を得る関数や、その生駒を得る関数は次のように書ける。

そこでPieceをこのように設計するのは、将棋風に言うと「わりとよくある手筋」である。

金は角より前じゃ駄目なんですか？

ところが、Pieceのenumにおいて、「金」の位置はやや不自然だと思うかも知れない。普通、将棋では金より角、飛車のほうが価値が高いので、素直に並べるとしたら歩、香、桂、銀、金、角、飛、王のようになる。

上のenumでは、金が飛車のうしろとなっている。金の成り駒はないので、( 金の値 + 8 )のところはenum上、空欄となってしまう。駒種の分だけ配列を確保しようとしたときに、ここが空欄だと、

成歩、成香、成桂、成銀、空欄(金の成り駒)、馬、龍

となる。変なところに空欄があいているので配列の1要素が無駄になるというわけだ。

だから、金の位置を入れ替えておくことで、

成歩、成香、成桂、成銀、馬、龍、空欄(金の成り駒)

のように確保することが出来て、これにより、駒種に対する配列は、龍のところまで配列を確保すれば良くて無駄がなくなるのである。

これはAperyのアイデアである。本当、Aperyはこのへんよく考えてあって感心する。

指し手生成

初期局面ですべての合法手の生成をしてみよう。

MoveListが指し手生成器で、LEGALが生成する指し手の種別である。ここでは合法手すべてを生成させてみた。

返ってくるのは、前回少し書いたように指し手と評価値をペアにしたもの(構造体)が返ってくるので、m.moveのようにして指し手を取り出して、ストリーム演算子で標準出力に出力してみた。

次のようにpretty()関数を用いるともう少し将棋の符号っぽく表示される。

指し手生成の種類

LEGAL = 全合法手

の他に、

CAPTURES = 捕獲する指し手
NON_CAPTURES = 捕獲しない指し手
EVASIONS = 玉を逃げる手
NON_EVASIONS = 玉を逃げない指し手
CHECKS = 王手となる指し手
…

みたいなものまで色々ある。

これらはtemplateを駆使して書かれていて、非常に速く実行されるのだが、コード量が非常に膨らむし、コンパイルに時間がかかるようになるので、使わない指し手生成のtemplateは実体化しないでおくのが賢い。

これらはmovegen.cppの末尾で実体化されている。自分の使うものだけを残して、あとはコメントアウトするのが良いと思う。逆に自分の使いたいものがコメントアウトされていれば、コメントアウトを解除すると良い。

何故、指し手生成をわけるのか

何故、こんな色々な種類の指し手生成を用意する必要があるのだろうか。ある局面の合法手すべてを毎回生成してくれればそれでいいのだから、LEGAL以外は不要ではないかと言われるかも知れない。

しかし、将棋の思考エンジンの探索において大半は駒を捕獲する指し手(CAPTURES)の時点で枝刈りされてしまうのである。そこで、CAPTURESとそうでない指し手(NON_CAPTURES)とを分けて生成したいという要望が探索部から出てくるのである。

本当はもっと効果的に細かく分けたほうがさらに効率は上がるのかも知れないが、指し手生成を分割するコストも馬鹿にならなくて、また、効果的に分割する手法もなかなか難しいので、そんなことをしている開発者はほとんどいないのである。

ともかく、探索部においてはCAPTURESとNON_CAPTURESというように二段階で分けると効果的、というところまで理解していただけただろうか。

CAPTURESに何を含めるか

CAPTURESとして何を含めるかというのは結構微妙な問題である。明らかに、歩を成る指し手は含めたほうがいい。歩を成る指し手は非常に価値の高い指し手なので、この指し手によって枝刈りが発生する確率は非常に高いからである。

それ以外の成りはなかなか微妙である。古いタイプの将棋ソフトでは成る指し手をすべてCAPTURESに入れていた。しかし、銀などは成ったところでそれほど価値があがらないのではないか、みたいな問題もある。

近年は、指し手のオーダリング(よさげな手を優先して調べる)の技術が上がってきたため、下手な指し手をCAPTURESに入れると探索性能が低下するのである。

そのためAperyでは歩の成る指し手以外はCAPTURESに含めていない。こうすることでオーダリング性能が改善して勝率が数%上がったとのことである。

やねうら王miniでも、歩の成る指し手をCAPTURESに含める指し手生成も用意してある。そのへんはユーザーが自由に選べるようになっている。

歩の成る指し手をCAPTURESに入れる場合は、NON_CAPTURESには歩の成る指し手は含まれない。そうしないと同じ指し手を重複して調べてしまうことになるからである。

つまり、CAPTURESとNON_CAPTURESの(指し手の)集合は被覆しない。二段階の指し手生成において、このことはとても重要な性質である。

EVASIONS

王手がかかっているときに生成される指し手は明らかに少ない。王手回避になっていないといけないからである。これ専用の指し手生成ルーチンがある。それがEVASIONSである。

つまり、現局面に王手がかかっているなら、CAPTURESの指し手生成をしてはならない。(してもいいけど、王手回避になっていない指し手も含まれてしまう) EVASIONSを呼びださなければならない。(呼び出したほうが生成される指し手が少なくて無駄が省ける)

NON_EVASIONS

では、NON_EVASIONSとは何なのか。王手されている局面で王手回避になっていない指し手を生成するのか。それはすべて非合法手であるから、そんな指し手生成をしても無駄ではないのか。

その通り。そんな指し手は生成しない。

NON_EVASIONSは、王手がかかっていない局面ですべての指し手を生成する指し手生成のことを言う。このへん、何かの将棋プログラムに最初に触れるときに必ずつまずくところなのでよく覚えておいて欲しい。

さっき、探索においてはCAPTURESとNON_CAPTURESの二段階生成になると言った。

NON_EVASIONSがすべての指し手を生成するなら、探索中には使わない(使えない)ことになるのではないだろうか。

実際、探索のなかでは直接NON_EVASIONSの指し手を生成することはない。しかし、例えば、王手回避手生成のために内部的にNON_EVASIONSを呼び出すことはある。

王手回避手

将棋において王手を回避する方法は、
1) 王を逃げる
2) 王手している駒を取る
3) 合駒をする(遠方駒での王手のとき)
の3通りある。両王手のときは2),3)は出来ない。1)のみとなる。

3)の合駒は王手をしている遠方駒と王とを結ぶ線分上の升(王のいる升は含まない)に打つ、もしくは移動合いをする必要がある。

つまり、2)+3)の指し手を生成しようと思ったときに、
駒打ちによる指し手 → 駒打ちで駒は取れないから2)はなくて、3)の線分上がto(駒の打つ先の升)
駒の移動による指し手 → 3)の線分と2)の王手をしている駒が、to(駒の移動先)
となるように指定してNON_EVASIONSを呼び出せば良いのである。

このように、NON_EVASIONSは探索中にもEVASIONSの指し手生成の内部から呼び出されるのである。

だから、NON_EVASIONSという概念を理解しておかないとこの部分の処理が理解できなくなるのである。

結局、NON_EVASIONSとは？

一言で要約すると NON_EVASIONS = CAPTURES + NON_CAPTURESである。

LEGALの指し手は重いという話

NON_EVASIONSがすべての指し手を生成するなら、LEGALとどう違うのかという話になる。
LEGALは合法手であることを保証している。

逆に、NON_EVASIONSに含まれていてLEGALに含まれない指し手とは何なのか。それは非合法手ではないのか。

その通り。非合法手がNON_EVASIONSには含まれるのである。

例えば、王を敵の利きに移動させる指し手。自殺手であり、非合法手である。それから、駒を動かして開き王手になってしまう指し手。これも非合法手である。

このような指し手がNON_EVASIONSに含まれるのである。

じゃあ、常にLEGALを用いればいいのかという話になるが、LEGALは遅いのである。いったんNON_EVASIONSで指し手をすべて生成したあと、自殺手でないことをチェックして自殺手を取り除く処理をしているのである。これが結構時間がかかるのである。

だから将棋の思考エンジンにおいて、通常の探索中にLEGALで指し手を生成することは決してないのである。(探索開始局面での初手をLEGALで生成することはある。)

LEGALかどうかのチェックは？

NON_EVASIONSで生成した指し手が合法かどうかをチェックする関数とかあるのか？という話になると思うが、もちろんある。

さきほどの等式
NON_EVASIONS = CAPTURES + NON_CAPTURES
からわかるように、NON_EVASIONSに非合法手が含まれているなら、CAPTURESとNON_CAPTURESにも非合法手が同じように含まれていることになる。それは、正しい。

なので、探索中に、CAPTURESやNON_CAPTURESで生成した指し手については、局面を進める前にそれが合法手であるかどうかをチェックしなければならない。

Position(局面)クラスのlegal()関数がそれである。

これについて詳しいことは次回に述べる。

ここまでのまとめ

指し手生成器と生成される指し手の種類の説明が終わった。

この指し手で局面を進める/戻ることが出来るようになると、自分の詰将棋ルーチンを書いたりすることが出来るようになる。この連載のなかで、近いうちに詰将棋ルーチンを書いたり、将棋パズルを解くプログラムを書いたりするのでお楽しみに！

次回に続く。