連載やねうら王miniで遊ぼう！5日目

投稿日時: 2015年12月11日投稿者: やねうらお

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

enum Piece

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

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

enum Piece : int32_t
{
  // 金の順番を飛の後ろにしておく。KINGを8にしておく。
  // こうすることで、成りを求めるときに pc |= 8;で求まり、かつ、先手の全種類の駒を列挙するときに空きが発生しない。(DRAGONが終端になる)
  NO_PIECE, PAWN/*歩*/, LANCE/*香*/, KNIGHT/*桂*/, SILVER/*銀*/, BISHOP/*角*/, ROOK/*飛*/, GOLD/*金*/ ,
  KING = 8/*玉*/, PRO_PAWN /*と*/, PRO_LANCE /*成香*/, PRO_KNIGHT /*成桂*/, PRO_SILVER /*成銀*/, HORSE/*馬*/, DRAGON/*龍*/, T_GOLD/*未使用*/,
  // 以下、先後の区別のある駒(Bがついているのは先手、Wがついているのは後手)
  B_PAWN = 1 , B_LANCE, B_KNIGHT, B_SILVER, B_BISHOP, B_ROOK, B_GOLD , B_KING, B_PRO_PAWN, B_PRO_LANCE, B_PRO_KNIGHT, B_PRO_SILVER, B_HORSE, B_DRAGON, B_T_GOLD,
  W_PAWN = 17, W_LANCE, W_KNIGHT, W_SILVER, W_BISHOP, W_ROOK, W_GOLD , W_KING, W_PRO_PAWN, W_PRO_LANCE, W_PRO_KNIGHT, W_PRO_SILVER, W_HORSE, W_DRAGON, W_T_GOLD,
  PIECE_NB, // 終端
  PIECE_ZERO = 0,

  // --- 特殊な定数

  PIECE_PROMOTE = 8, // 成り駒と非成り駒との差(この定数を足すと成り駒になる)
  PIECE_WHITE = 16, // これを先手の駒に加算すると後手の駒になる。

…

enum Piece : int32_t

{

// 金の順番を飛の後ろにしておく。KINGを8にしておく。

// こうすることで、成りを求めるときに pc |= 8;で求まり、かつ、先手の全種類の駒を列挙するときに空きが発生しない。(DRAGONが終端になる)

NO_PIECE, PAWN/*歩*/, LANCE/*香*/, KNIGHT/*桂*/, SILVER/*銀*/, BISHOP/*角*/, ROOK/*飛*/, GOLD/*金*/ ,

KING = 8/*玉*/, PRO_PAWN /*と*/, PRO_LANCE /*成香*/, PRO_KNIGHT /*成桂*/, PRO_SILVER /*成銀*/, HORSE/*馬*/, DRAGON/*龍*/, T_GOLD/*未使用*/,

// 以下、先後の区別のある駒(Bがついているのは先手、Wがついているのは後手)

B_PAWN = 1 , B_LANCE, B_KNIGHT, B_SILVER, B_BISHOP, B_ROOK, B_GOLD , B_KING, B_PRO_PAWN, B_PRO_LANCE, B_PRO_KNIGHT, B_PRO_SILVER, B_HORSE, B_DRAGON, B_T_GOLD,

W_PAWN = 17, W_LANCE, W_KNIGHT, W_SILVER, W_BISHOP, W_ROOK, W_GOLD , W_KING, W_PRO_PAWN, W_PRO_LANCE, W_PRO_KNIGHT, W_PRO_SILVER, W_HORSE, W_DRAGON, W_T_GOLD,

PIECE_NB, // 終端

PIECE_ZERO = 0,

// --- 特殊な定数

PIECE_PROMOTE = 8, // 成り駒と非成り駒との差(この定数を足すと成り駒になる)

PIECE_WHITE = 16, // これを先手の駒に加算すると後手の駒になる。

…

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

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

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

// 後手の歩→先手の歩のように、後手という属性を取り払った駒種を返す
constexpr Piece type_of(Piece pc) { return (Piece)(pc & 15); }

// 成ってない駒を返す。後手という属性も消去する。
// 例) 成銀→銀 , 後手の馬→先手の角
// ただし、pc == KINGでの呼び出しはNO_PIECEが返るものとする。
constexpr Piece raw_type_of(Piece pc) { return (Piece)(pc & 7); }

// 後手の歩→先手の歩のように、後手という属性を取り払った駒種を返す

constexpr Piece type_of(Piece pc) { return (Piece)(pc & 15); }

// 成ってない駒を返す。後手という属性も消去する。

// 例) 成銀→銀 , 後手の馬→先手の角

// ただし、pc == KINGでの呼び出しはNO_PIECEが返るものとする。

constexpr Piece raw_type_of(Piece pc) { return (Piece)(pc & 7); }

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

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

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

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

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

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

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

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

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

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

指し手生成

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

void user_test(Position& pos)
{
  cout << pos;
  for (auto m : MoveList<LEGAL>(pos))
    cout << m.move << ' ';
}

> user
^香^桂^銀^金^玉^金^銀^桂^香
 □^飛 □ □ □ □ □^角 □
^歩^歩^歩^歩^歩^歩^歩^歩^歩
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 歩 歩 歩 歩 歩 歩 歩 歩 歩
 □ 角 □ □ □ □ □ 飛 □
 香 桂 銀 金 玉 金 銀 桂 香
先手 手駒 :  , 後手 手駒 :
手番 = 先手
sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1
1g1f 2g2f 3g3f 4g4f 5g5f 6g6f 7g7f 8g8f 9g9f 1i1h 9i9h 3i3h 3i4h 7i6h 7i7h 2h1h 2h3h 2h4h 2h5h 2h6h 2h7h 4i3h 4i4h 4i5h 5i4h 5i5h 5i6h 6i5h 6i6h 6i7h

void user_test(Position& pos)

{

cout << pos;

for (auto m : MoveList(pos))

cout << m.move << ' ';

}

> user

^香^桂^銀^金^玉^金^銀^桂^香

□^飛 □ □ □ □ □^角 □

^歩^歩^歩^歩^歩^歩^歩^歩^歩

□ □ □ □ □ □ □ □ □

歩歩歩歩歩歩歩歩歩

□ 角 □ □ □ □ □ 飛 □

香桂銀金玉金銀桂香

先手手駒 : , 後手手駒 :

手番 = 先手

sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1

1g1f 2g2f 3g3f 4g4f 5g5f 6g6f 7g7f 8g8f 9g9f 1i1h 9i9h 3i3h 3i4h 7i6h 7i7h 2h1h 2h3h 2h4h 2h5h 2h6h 2h7h 4i3h 4i4h 4i5h 5i4h 5i5h 5i6h 6i5h 6i6h 6i7h

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

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

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

void user_test(Position& pos)
{
  for (auto m : MoveList<LEGAL>(pos))
    cout << pretty(m.move) << ' ';
}

> user
１七１六 ２七２六 ３七３六 ４七４六 ５七５六 ６七 ６六 ７七７六 ８七８六 ９七９六 １九１八 ９九９八 ３九３八 ３九４八 ７九６八 ７九７八 ２八１八 ２八 ３八 ２八４八 ２八５八 ２八６八 ２八７八 ４九３八 ４九４八 ４九５八 ５九４八 ５九５八 ５九６八 ６九 ５八 ６九６八 ６九７八

void user_test(Position& pos)

{

for (auto m : MoveList(pos))

cout << pretty(m.move) << ' ';

}

> user

１七１六２七２六３七３六４七４六５七５六６七６六７七７六８七８六９七９六１九１八９九９八３九３八３九４八７九６八７九７八２八１八２八３八２八４八２八５八２八６八２八７八４九３八４九４八４九５八５九４八５九５八５九６八６九５八６九６八６九７八

指し手生成の種類

LEGAL = 全合法手

の他に、

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

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

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

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

movegen.cpp

// template ExtMove* generateMoves<NON_CAPTURES      >(const Position& pos, ExtMove* mlist);
// template ExtMove* generateMoves<CAPTURES          >(const Position& pos, ExtMove* mlist);

…

// すべての合法な指し手を生成する

//template ExtMove* generateMoves<LEGAL_NON_PRO_MINUS>(const Position& pos, ExtMove* mlist);
template ExtMove* generateMoves<LEGAL              >(const Position& pos, ExtMove* mlist);

movegen.cpp

// template ExtMove* generateMoves(const Position& pos, ExtMove* mlist);

…

// すべての合法な指し手を生成する

//template ExtMove* generateMoves(const Position& pos, ExtMove* mlist);

template ExtMove* generateMoves(const Position& pos, ExtMove* 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の指し手を生成することはない。しかし、例えば、王手回避手生成のために内部的に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()関数がそれである。

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

ここまでのまとめ

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

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

次回に続く。