うらお今回は、指し手生成器と生成される指し手の分類についての説明です。Piece前回、「駒」と「駒種」との違いについて説明した。Piece型については詳しく説明していなかった。Piece型についてはやねうら王miniでは次のように定義されている。金の順番を飛の後ろにしておく。KINGを8にしておく。8;で求まり、かつ、先手の全種類の駒を列挙するときに空きが発生しない。これを先手の駒に加算すると後手の駒になる。金の順番を飛の後ろにしておく。KINGを8にしておく。8;で求まり、かつ、先手の全種類の駒を列挙するときに空きが発生しない。これを先手の駒に加算すると後手の駒になる。・生駒に8(PIECE_PROMOTE)を足すと成り駒になる。逆に成り駒から8を引くと生駒になる。・先手の駒に16(PIECE_WHITE)を足す後手の駒になる。・駒のない升などを表す値は0(NO_PIECE)であるなどだろう。8とか16のように2の累乗にしてあるのは、bit操作で済むからである。駒pc(後手の駒かも知れないし、成駒かも知れない)が与えられたときに、その駒種(先後の区別なし)を得る関数や、その生駒を得る関数は次のように書ける。後手という属性も消去する。KINGでの呼び出しはNO_PIECEが返るものとする。後手という属性も消去する。KINGでの呼び出しはNO_PIECEが返るものとする。}そこでPieceをこのように設計するのは、将棋風に言うと「わりとよくある手筋」である。金は角より前じゃ駄目なんですか?ところが、Pieceのenumにおいて、「金」の位置はやや不自然だと思うかも知れない。上のenumでは、金が飛車のうしろとなっている。)のところはenum上、空欄となってしまう。(金の成り駒)、馬、龍となる。変なところに空欄があいているので配列の1要素が無駄になるというわけだ。(金の成り駒)のように確保することが出来て、これにより、駒種に対する配列は、龍のところまで配列を確保すれば良くて無駄がなくなるのである。これはAperyのアイデアである。本当、Aperyはこのへんよく考えてあって感心する。初期局面ですべての合法手の生成をしてみよう。6i7hMoveListが指し手生成器で、LEGALが生成する指し手の種別である。ここでは合法手すべてを生成させてみた。返ってくるのは、前回少し書いたように指し手と評価値をペアにしたもの(構造体)が返ってくるので、m.moveのようにして指し手を取り出して、ストリーム演算子で標準出力に出力してみた。次のようにpretty()関数を用いるともう少し将棋の符号っぽく表示される。王手となる指し手...みたいなものまで色々ある。これらはtemplateを駆使して書かれていて、非常に速く実行されるのだが、コード量が非常に膨らむし、コンパイルに時間がかかるようになるので、使わない指し手生成のtemplateは実体化しないでおくのが賢い。これらはmovegen.cppの末尾で実体化されている。自分の使うものだけを残して、あとはコメントアウトするのが良いと思う。逆に自分の使いたいものがコメントアウトされていれば、コメントアウトを解除すると良い。mlist);何故、指し手生成をわけるのか何故、こんな色々な種類の指し手生成を用意する必要があるのだろうか。ある局面の合法手すべてを毎回生成してくれればそれでいいのだから、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の指し手を生成することはない。合駒をする(遠方駒での王手のとき)の3通りある。両王手のときは2),3)は出来ない。3)の合駒は王手をしている遠方駒と王とを結ぶ線分上の升(王のいる升は含まない)に打つ、もしくは移動合いをする必要がある。3)の線分と2)の王手をしている駒が、to(駒の移動先)となるように指定してNON_EVASIONSを呼び出せば良いのである。このように、NON_EVASIONSは探索中にもEVASIONSの指し手生成の内部から呼び出されるのである。NON_EVASIONSという概念を理解しておかないとこの部分の処理が理解できなくなるのである。NON_CAPTURESである。LEGALの指し手は重いという話NON_EVASIONSがすべての指し手を生成するなら、LEGALとどう違うのかという話になる。LEGALは合法手であることを保証している。逆に、NON_EVASIONSに含まれていてLEGALに含まれない指し手とは何なのか。それは非合法手ではないのか。非合法手がNON_EVASIONSには含まれるのである。王を敵の利きに移動させる指し手。自殺手であり、非合法手である。それから、駒を動かして開き王手になってしまう指し手。これも非合法手である。このような指し手がNON_EVASIONSに含まれるのである。常にLEGALを用いればいいのかという話になるが、LEGALは遅いのである。NON_EVASIONSで指し手をすべて生成したあと、自殺手でないことをチェックして自殺手を取り除く処理をしているのである。これが結構時間がかかるのである。将棋の思考エンジンにおいて、通常の探索中にLEGALで指し手を生成することは決してないのである。(探索開始局面での初手をLEGALで生成することはある。)LEGALかどうかのチェックは?NON_EVASIONSで生成した指し手が合法かどうかをチェックする関数とかあるのか?という話になると思うが、もちろんある。NON_CAPTURESからわかるように、NON_EVASIONSに非合法手が含まれているなら、CAPTURESとNON_CAPTURESにも非合法手が同じように含まれていることになる。探索中に、CAPTURESやNON_CAPTURESで生成した指し手については、局面を進める前にそれが合法手であるかどうかをチェックしなければならない。Position(局面)クラスのlegal()関数がそれである。これについて詳しいことは次回に述べる。ここまでのまとめ指し手生成器と生成される指し手の種類の説明が終わった。この指し手で局面を進める/戻ることが出来るようになると、自分の詰将棋ルーチンを書いたりすることが出来るようになる。この連載のなかで、近いうちに詰将棋ルーチンを書いたり、将棋パズルを解くプログラムを書いたりするのでお楽しみに!次回に続く。bitboardとして扱うことはできませんか?SEEの時に駒の価値の低い順に並び替える必要があるときに困るかと思ったのですが、SEEは使わない?(と書いてあった気が)予定だそうなので質問させていただきました。:Bonanzaに倣い、歩、香、桂、銀の成り駒はすべて金扱いしています。SEEで価値の低い駒順に並べるときに確かに少しおかしくなる気はしますが、SEEを厳密に計算する価値ってあまりないのに計算コストが馬鹿にならないのでもっと簡略化された方法でいいかと思っています。わかりにくい聞き方だったかもしれません。Bonanzaでは成駒もすべて別々にbitboardを用意していましたよね。bitboardをbyTypeBB_[GOLD]byTypeBB_[PRO_PAWN]byTypeBB_[PRO_LANCE]byTypeBB_[PRO_KNIGHT]byTypeBB_[PRO_SILVER]として用意しているのをbyTypeBB_[GOLD]と一つで扱うことはできないのか、という意図です。goldsBB_;と、bitboardを用意しているようなので、それなら最初からすべての成駒をGOLDとして扱うことはできないのかな、と考えています。:やねうら王(2012,2013,2014)はそうしてますね。SEEが棋力に及ぼす影響は軽微だと思います。この改良(改造?)による善悪はよくわかりません。ありがとうございます。修行僧乙ちなみに>将棋において王手を回避の方法は、・・・は少し表現がかたいような・・・。王手を回避する方法は・・・としたい所です。