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

SilverBulletの作者も大絶賛のこの連載、今回は、指し手とその合成についての説明でございます。

色々わかりやすい。復習した気分になりました。
一度何でもいいので将棋ソフトのソースを流し見した人にとってはこの解説を読むと早く理解できそう。多分。 https://t.co/6TSeTnYoq7

— SilverBullet (@silverbullet_0) December 9, 2015

指し手のenum

指し手は、ソースコード上ではMoveとなっている。例によってStockfishに倣っている。

Moveもenumであり、前回説明したFile、Rank、Square同様に加減算のoperatorが定義されていたり、operator << ()で標準出力に表示させたり、pretty()で表示させたり出来る。

指し手の構造

指し手は次のように2バイトからなる。基本的には移動元と移動先の升があればいいのである。あとは、「成り」と「打ち」用のフラグがあれば良い。これはbit14とbit15を用いている。

// 指し手 bit0..6 = 移動先のSquare、bit7..13 = 移動元のSquare(駒打ちのときは駒種)、bit14..駒打ちか、bit15..成りか
enum Move : uint16_t
{
  MOVE_NONE = 0 , // 無効な移動
  MOVE_NULL = (1 << 7) + 1, // NULL MOVEを意味する指し手。Square(1)からSquare(1)への移動は存在しないのでここを特殊な記号として使う。
  MOVE_DROP = 1 << 14, // 駒打ちフラグ
  MOVE_PROMOTE = 1 << 15, // 駒成りフラグ
};

// 指し手 bit0..6 = 移動先のSquare、bit7..13 = 移動元のSquare(駒打ちのときは駒種)、bit14..駒打ちか、bit15..成りか

enum Move : uint16_t

{

MOVE_NONE = 0 , // 無効な移動

MOVE_NULL = (1 << 7) + 1, // NULL MOVEを意味する指し手。Square(1)からSquare(1)への移動は存在しないのでここを特殊な記号として使う。

MOVE_DROP = 1 << 14, // 駒打ちフラグ

MOVE_PROMOTE = 1 << 15, // 駒成りフラグ

};

ソースコードを見てわかるように、

DROP …　駒打ち(の指し手)
PROMOTE … 駒成り(の指し手)

である。この用語、頻繁に出てくるので覚えておいて欲しい。

特殊な定数としてMOVE_NONEとかMOVE_NULLがある。これらは特殊な定数として使う。
指し手の移動先がbit0..6で、移動元がbit7..13ということは、

移動元 = 移動先 = 0(SQ_11)のときMOVE_NONE
移動元 = 移動先 = 1(SQ_12)のときMOVE_NULL

ということである。移動元と移動先が合致することは将棋の合法手ではありえないので、これらを特殊な定数に使うということである。これはStockfishのアイデアである。

こうしてあれば、次のようにして、指し手が特殊な指し手であるかどうかが判定できる。

// 指し手がおかしくないかをテストする
// ただし、盤面のことは考慮していない。MOVE_NULLとMOVE_NONEであるとfalseが返る。
// これら２つの定数は、移動元と移動先が等しい値になっている。このテストだけをする。
inline bool is_ok(Move m) {
  // return move_from(m)!=move_to(m);
  // とやりたいところだが、駒打ちでfromのbitを使ってしまっているのでそれだとまずい。
  // 駒打ちのbitも考慮に入れるために次のように書く。
  return (m >> 7) != (m & 0x7f);
}

// 指し手がおかしくないかをテストする

// ただし、盤面のことは考慮していない。MOVE_NULLとMOVE_NONEであるとfalseが返る。

// これら２つの定数は、移動元と移動先が等しい値になっている。このテストだけをする。

inline bool is_ok(Move m) {

// return move_from(m)!=move_to(m);

// とやりたいところだが、駒打ちでfromのbitを使ってしまっているのでそれだとまずい。

// 駒打ちのbitも考慮に入れるために次のように書く。

return (m >> 7) != (m & 0x7f);

}

is_ok()について

いま、is_ok(Move m)という関数が出てきたが、やねうら王miniではほとんどすべてのenumに対して、このis_ok()という関数が用意されている。この関数は、その値がおかしくないか簡単なテストを行なう。速度的な理由により、あまり厳密なテストは行わないが、assert(is_ok(XXX));などとassertで使う分にはこれで十分である。

fromとto

指し手(Move)のenumの定義を見ると、移動先の升(bit0..6)と移動元の升(bit7..13)となっている。

(指し手の)移動先の升 = to
(指し手の)移動元の升 = from

という呼び方(や変数名)も、やねうら王miniのソースコードでよく出てくる。これもご多分に漏れず、Stockfishに倣っている。

Moveは何故16bitに収めないといけないのか？

Moveのtoとfromをどのbitに割り当てるかについては自由のように思える。例えば

struct Move
{
	Square from;
	Square to;
	bool promote;
	bool drop;
};

struct Move

{

Square from;

Square to;

bool promote;

bool drop;

};

のようにしておけば値を取り出すときにbit shiftが不要になるのではないか？と思われるかも知れない。過去にはそういう設計の将棋ソフトも多数あった。

しかし、指し手は評価値(16bit整数)とペアにして32bitの値として管理する。こうすることで評価値に基いて指し手を並び替えるときに32bit変数のコピーで済んだりして都合が良いのだ。また置換表に格納するときも指し手がこじんまりと収まっていると都合が良いという意味もある。

なので指し手が16bitというのは絶対に譲れないのだ。絶対にだ！

Moveの下位は何故fromではなくtoなのか

指し手(Move)を16bitに収めないといけないというのはわかった。

では、下位(bit0..6)をfromではなくtoにしなければならないのには必然性はあるのか？

ある。

指し手生成のことを想像して欲しい。

いま、銀を動かすとする。
from(移動元の升)は固定である。

ところが移動先の升(to)は複数ある。

つまり、このとき次のようなコードになる。

from = 銀のある升
target = fromに銀をおいたときの利きで、自駒のない場所
while (target)
{
	Square to = target.pop();
	*mlist++ = make_move(from,to);
}

from = 銀のある升

target = fromに銀をおいたときの利きで、自駒のない場所

while (target)

{

Square to = target.pop();

*mlist++ = make_move(from,to);

}

make_moveは、もう想像がつくだろう。やねうら王miniでは次のように書いてある。

// fromからtoに移動する指し手を生成して返す
constexpr Move make_move(Square from, Square to) { return (Move)(to + (from << 7)); }

fromは上記のループ内では不変であるから、このbit shiftは実際は一度しか行われない。toだけが異なるが、ここにはbit shiftは不要なのである。

このように、指し手生成のループの内部においてbit shiftをしたくないので、Moveのtoは下位にしておく必要があるのだ。

Moveひとつとってもこのように熟考された上でビットレイアウトが決められているわけである。

「やねうら王miniで遊ぼう！」などととっつきやすそうな入門記事っぽいタイトルをつけておいて、こんな専門的かつセコい話を延々とするのは恐縮だが、これもまた教育だと思うので、お付き合い願いたい。

指し手の合成

28の飛車を23に成ることを想定して、指し手を合成してみよう。

void user_test(Position& pos)
{
  Move m = make_move(SQ_28, SQ_23);
  cout << m;
}

> user
2h2c

void user_test(Position& pos)

{

Move m = make_move(SQ_28, SQ_23);

cout << m;

}

> user

2h2c

2h2cと表示された。hはで8段目、cは3段目なので、これで合っている。
しかし、これは成りの指し手ではない。不成の指し手だ。

成る指し手の合成

成りの指し手の合成には、make_move_promote()のほうを使う。
こちらは次のように定義されている。

void user_test(Position& pos)
{
  Move m = make_move_promote(SQ_28, SQ_23);
  cout << m;
}

> user
2h2c+

void user_test(Position& pos)

{

Move m = make_move_promote(SQ_28, SQ_23);

cout << m;

}

> user

2h2c+

成る指し手を表示させたときは”+”記号がつく。これは、USIプロンプトに準拠している。USIプロトコルについてはggrksである。

打つ指し手の合成

せっかくなので打つ指し手も合成してみよう。
打つ指し手はmake_move_drop()を用いる。これは次のように定義されている。

// Pieceをtoに打つ指し手を生成して返す
constexpr Move make_move_drop(Piece pr, Square to) { return (Move)(to + (pr << 7) + MOVE_DROP); }

駒種ptを7回左シフトしているので要するにfromが格納されていたところにそのまま持ってきてある。チェスには駒打ちはないのでStockfishにはないコードであり、このへんの設計は自由である。やねうら王miniで上のようにした理由は、打つ駒を指し手Move mから取り出すのに、Piece p = (Piece)move_from(m);のように書けるのでわりとわかりやすいかと思ってのことである。他にもやりようはあるので色々考えてみて欲しい。

ともかく、これを使って52に金を打つ指し手を生成してみよう。

void user_test(Position& pos)
{
  Move m = make_move_drop(GOLD, SQ_52);
  cout << m;
}

> user
G*5b

void user_test(Position& pos)

{

Move m = make_move_drop(GOLD, SQ_52);

cout << m;

}

> user

G*5b

5bは、52のことだ。GはGold(金)、*は駒打ちを表す。これはUSIプロトコルに準じている。将棋所のデバッグ表示を用いて、思考エンジンと将棋所とがやりとりしているメッセージを観察しているとこのような文字が使われている。わかってくると楽しいと思う。

dropの指し手のpretty()表示

Moveもまたpretty()に対応している。

void user_test(Position& pos)
{
  Move m = make_move_drop(GOLD, SQ_52);
  cout << pretty(m);
}

> user
５二金打

void user_test(Position& pos)

{

Move m = make_move_drop(GOLD, SQ_52);

cout << pretty(m);

}

> user

５二金打

格段に読みやすくなった。

promoteの指し手のpretty()表示

さきほどの成る指し手もpretty()で表示させてみよう。

void user_test(Position& pos)
{
  Move m = make_move_promote(SQ_28, SQ_23);
  cout << pretty(m);
}

> user
２八２三成

void user_test(Position& pos)

{

Move m = make_move_promote(SQ_28, SQ_23);

cout << pretty(m);

}

> user

２八２三成

成る駒名が表示されないのでいまひとつである。

指し手(Move)にない情報

成る駒名が表示されない原因について考えてみよう。

Moveのenumの定義を思い出して欲しい。

指し手(Move)において、移動させる駒の情報がないのである。駒を打つ場合には打つ駒の情報が入っている。だから打つ駒名は表示できる。

捕獲される駒についての情報もMoveにはない。Moveを16bitに収めたいので入れることが出来なかったのである。(無理に入れようと思うと入れれないこともないが…。)

また、手番に関する情報もない。

このように指し手(Move)には色々と情報が欠落しているので、盤面情報と突き合わせないかぎり、移動させる駒名や捕獲される駒についてはわからないのである。

しかし、このように指し手についてわざと色々な情報をそぎ落としておくことで、指し手生成を高速にして、かつ、16bitに収めることが出来るわけである。これには、不便なところもあるが、上位ソフトにおいては「速度こそ正義！」なので、上位ソフトに位置しているような思考エンジンの現実的な仕様としてはこのへんが落とし所なのである。

汎用的な将棋プログラミングフレームワークとしてはやや使いにくい気がしなくもないが、このやねうら王miniを土台として世界最強の将棋ソフトを作らないといけないので(?)、譲れない部分は譲れないのである。

駒と駒種の違い

さきほど、make_move_drop()でPieceの変数名がprになっていることが気になった人もいるだろう。

// Pieceをtoに打つ指し手を生成して返す
constexpr Move make_move_drop(Piece pr, Square to) { return (Move)(to + (pr << 7) + MOVE_DROP); }

pieceをどう略せばprになるのか。

まず、Pieceというenumは先後の区別があった。
先後の区別のある駒のことは変数名としてpcとつける。これはPieceをそのまま略している。

それに対して、先後の区別のないもの。StockfishではこれをPieceTypeと呼んでいるが、やねうら王ではこのenumは不要だと思っていてすべてPieceで統一してある。それというのもPieceとPieceTypeとの相互変換等においてソースコードが複雑になるからである。

その代わり、駒種(先後の区別がない場合)は、変数名としてpt、先後の区別がある場合は(pieceの略で)pcと表記するようにしてある。

じゃあ、変数名のprとは何なのか。

実は、これはRaw Piece(生駒)の略である。(例 : 角は生駒。馬は成駒。)

打つ駒には「馬」のような成り駒は含まれない。そこで、そのことを明示しなくてはならない。RawPieceTypeのような別のenumを用意してもいいのだが、これもソースコードが複雑になるのでやりたくない。Piece型をそのまま援用するわけであるが、どこかにこの変数は生駒ですよと明示しておきたい。そのため、関数の仮引数の変数名で示してあるということだ。

また、ソースコード上のコメントには先後の区別がない駒のことを「駒種」、先後の区別がある駒のことを単に「駒」と使い分けて書いてあることもある。(前後の文脈からわかる場合は「駒種」の意味で「駒」と書いていることもあるし、また、「生駒」のことを「駒種」と書いてあることもある。)

細かいことではあるが、このへんを意識してソースコードを読むと、より理解が深まると思う。

make_move_drop()にassertを何故入れないのか

make_move_drop()に渡すのは生駒であって、駒種(成駒含む)でも駒(先後の区別あり)でもない。後手の歩(W_PAWN)などを渡してはならない。

なら、次のようなassertを何故make_move_drop()のなかに書かないのかと言われるかも知れない。

assert(color_of(pr) == BLACK && raw_piece_of(pr) == pr);

確かにこう書いておけば間違ってW_PAWN(後手の歩)やHORSE(馬)を渡しているようなコードはassertに引っかかるだろう。

しかしこれはしたくない。

というのも、make_move()やmake_move_drop()は1秒間に何百万回と呼び出されるため、こういう非常にたくさん呼び出される部分にassertを入れるとデバッグ時に速度がでなくなってしまうからである。

そこで呼び出し頻度が極めて高い関数にはassertをあえて入れない。「assertがないのは教育的ではない」という批判に対しては、「デバッグ時の速度がリリース時の1/100しか出ないことのほうが、はるかに教育的ではない」と言わせてもらおう。

このように細部まで非常に突き詰めて考えられた将棋の思考エンジンフレームワークがやねうら王miniなのだ。

なんだ？「文章のところどころ自慢を挟んでくるな」って？わかった。次回から極力控えよう。

ここまでのまとめ

今回は指し手とその合成について解説した。

指し手自体は普通は指し手生成ルーチンで一括して行なうので、自分で指し手の合成を行なう機会はほとんどないかも知れないが、このへんのデータ構造を理解していると、詰将棋ルーチンを自作したり、55将棋の思考エンジンに改造したり、将棋パズル(将棋の指し手のルールを用いたパズル)を解くプログラムを作ったりするのに便利であるから、詳しく解説した。

次回に続く。