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

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

今回は指し手の合法性について説明します。

指し手の合法性とは？

MoveList<LEGAL>()
として合法な指し手を生成して使ってきた。

※　2016/1/1 追記。歩の不成を含むのは、LEGAL_ALL、含まないのがLEGALと命名を変更した。過去のソースコードでLEGALと書いてあるものが前者の意味になっているのは、そのためである。

しかし、LEGALな指し手以外の指し手生成、例えば、CAPTURES(＝駒を捕獲する指し手)だとか、NON_CAPTURES(＝駒を捕獲しない指し手)だとかでは、玉を相手の利きに移動させるような自殺手も含まれるという話をした。

このような自殺手を指し手生成時に除外するのはコストがかかるため、do_move()を行なう寸前までそのチェックを遅延させるということを説明した。

ということは、LEGALな指し手とCAPTURES/NON_CAPTURESとでは合法性(legality)が違うということである。

次のような4つの段階を考えてみる。

1. マジで合法
2. 合法
3. そこそこ合法
4. ちょっとだけ合法

LEGALな指し手は2.で、CAPTURES/NON_CAPTURESは3.だと言える。

なぜLEGALは1.ではないのかと言うと、LEGALには連続王手の千日手の指し手が含まれるからだ。これはそこまでの経路が問題となるため、通常、探索において除外すべき指し手である。指し手生成では局面(＝盤面＋手駒＋手番)のことだけ見て指し手を生成したい。指し手生成のときに探索のこと（＝その局面にいたる手順）まで考慮したくないので、LEGALとは言え、1.ではなく2.なのだ。

また、置換表から取ってきた指し手は、hash衝突で他の局面の指し手を取ってきてしまった場合、指し手の移動元に駒がない場合や、移動先に自駒がある場合がある。ただし、以前書いたように、先手の1段目に歩を打つ指し手とかは含まれない。(置換表上、先手と後手とでは、局面を格納する場所が異なるため)

そこで、置換表から取ってきた指し手は4.に分類される。

こうして考えると、
1. = 連続王手の千日手も含まない、本当の合法手
2. = 1.に加えて、連続王手の千日手は含む。
3. = 2.に加えて、自殺手も含む
4. = 3.に加えて、移動先に自駒がある場合などを含む
という分類をしていることになる。

コンピューター将棋では普通、2.をlegal move(合法手)と呼ぶ。3.をpseudo move(擬似合法手。合法手もどき。)と呼ぶ。ちなみにpseudoの頭文字のpは読まない(黙字)で、「すーだ」に近い発音をする。詳しくはggrks。

4.はrandom move(ランダムな指し手)と呼ぶ。実際は、将棋では、4.として先手の1段目に歩を打つ指し手とかは含まない状態にするのが普通なので、将棋ではここは完全なランダムな指し手ではないのだが、まあ、Stockfishに倣って、そう呼ぶことにする。

ちなみに、1.の呼び名はついていない。チェスでは連続王手の千日手は、禁則ではなく、引き分けになるのでそこに至る指し手は非合法手ではないからである。

せっかくなので、1.のことは私が「マジで合法(な指し手)」(genuine legal move)と名づけておく。

合法性の分類

以上のことから、指し手の合法性について整理すると、

1. マジで合法(genuine legal) = 連続王手の千日手も含まない、本当の合法手
2. 合法(legal) = 1.に加えて、連続王手の千日手は含む。
3. 擬似合法(pseudo legal) = 2.に加えて、自殺手も含む
4. ランダム(random) = 3.に加えて、移動先に自駒がある場合などを含む

こうなる。

合法性の判定関数

Stockfish/Apery/やねうら王mini、共通の話。

4.の指し手を引数に渡して、3.であるかを判定する関数 → Position::pseudo_legal()
3.の指し手を引数に渡して、2.であるかを判定する関数 → Position::legal()

である。

合法性の判定関数の使い方

LEGAL以外(例えば、CAPTURES)で指し手生成をした場合、指し手は上記の3.の集合である。そこで、Position::legal()を用いて、それが2.であるか判定してから、2.である場合のみdo_move()しなければならない、というのはおわかりだろう。

典型的には次のようなコードになる。(いまの説明に関係のない部分は省略している)

MovePicker mp(pos);
while (m = mp.next())
{
	// do_move()の直前に指し手の合法性をチェックする
	if (!pos.legal(m))
		continue;
	pos.do_move(m,...);
	...
	pos.undo_move(m);
}

MovePicker mp(pos);

while (m = mp.next())

{

// do_move()の直前に指し手の合法性をチェックする

if (!pos.legal(m))

continue;

pos.do_move(m,...);

...

pos.undo_move(m);

}

MovePickerとは？

上のソースコードに出てきたMovePickerは、その局面での指し手をCAPTURES→NON_CAPTURESのように段階的に生成しながら1手ずつ返すclassである。

具体的には、まずCAPUTRESの指し手を生成して、指し手の良さを点数化してつけて(スコアリングして)、そのスコアの高い順に、next()が呼ばれるごとに1手ずつ返していく。CAPTURESの指し手を使い切ったら、次はNON_CAPTURESの指し手を生成して、これまたよさ気な順で返していく。そういう動作をする。

指し手の合法性の分類は他にないのか？

上の例では合法性の度合いに応じて4つに分類した。

これを別に4つにしなくとも、5つでも8つでもいいのだが、あまり細かくするとrandomな指し手をlegalであることを確認するまでに何度も判定関数を呼び出さないといけないことになって、その呼び出しのオーバーヘッドなどが無視できなくなる。

また、4つのそれぞれの分類に必然性はそれほどないのだが、4.が3.であるかを判定する関数(Position::pseudo_legal() )でチェックする内容と、3.が2.であるかを判定する関数(Position::legal() )でチェックする内容とが重複していると同じ処理を二度しないといけなくて、無駄である。

なので、このような重複したチェックが要らないような分類にしておくのが合理的である。上の例での分類は、このような重複したチェックは要らないようになっている。

やねうら王(2014)の場合とAperyの場合での違い

具体的に、やねうら王(2014)とAperyとで、上の4つの分類でどんな違いがあるか確認しておこう。

1.はマジで合法なので(マジで合法な指し手は一通りしかない)、ここに違いがあろうはずがない。
4.も、ランダムな指し手なのでここにも違いはない。

問題は2.と3.である。

やねうら王(2014)では、打ち歩詰めのチェックは指し手生成のときにしていなかった。打ち歩詰めであるかをチェックするのはその歩への受け方の利きを調べたり、打たれた駒が受け方の素抜きされない駒の移動で取れるかなど結構コストがかかることがあるため、このチェックが嫌だったのだ。

よって、打ち歩詰めになる歩を打つ指し手は、やねうら王(2014)では3.に含まれる。つまり、やねうら王miniでは、4.→3.であるかを判定する関数(Position::pseudo_legal() )では、打ち歩詰めであるかはテストしない。3.→2.(Position::legal() )でその判定を行なっている。

一方、Apery(2015年12月23日現時点)では、指し手生成のときのそのチェックをしているので、打ち歩詰めになる打ち歩は3.には含まれない。つまり4.に含まれるという解釈だ。4.→3.(Position::pseudo_legal() )で、その判定を行なっている。

どちらが優れているのだろうか？

legal()チェックは生成された指し手それぞれに対してdo_move()する前に行われるのでlegal()での処理を極力軽くすることのほうが価値が高い。ただし、1つの局面で、平均的には6～10手目ぐらいの指し手で枝刈りされてしまうので、1つの局面に対して平均的にはそれぐらいの回数しかlegal()は呼び出されない。(評価関数や探索の性能によってこの平均回数は異なる。)

仮にここが10回だとしたら、指し手生成で打ち歩詰めチェックをして除外するコストと、do_move()で打ち歩詰めをチェック(平均10回)をするためのコストとではどちら少ないかということを比較して考えなくてはならない。

結局、ここが平均5回なのか、平均10回なのかで話が変わってくるわけであるが、やねうら王miniでは打ち歩詰めチェックは指し手生成のときにやったほうがわずかに得ではないかと思ってそう変更した。探索をきっちり書いてからまた比較テストをしてみたい。

自殺手をどこに分類するか

自殺手としては次の3種類がある。

a) 王手放置
b) 自殺手として玉を敵の利きに移動させる指し手
c) pinされている駒(移動させると遠方駒によって玉が素抜きにあう駒)をpinされている方向とは違う方向に移動させて(例えば敵の香で自駒Xがpinされているとき、Xを上下以外の方向に移動させて)玉を素抜きされてしまう指し手

実は、王手がかかっているかどうかはdo_move()し終わった時点でStateInfoのcheckersというのが、その局面で王手をしているBitboardであるから、これがゼロかゼロでないかを調べれば、王手がかかっているか(＝王手している駒があるか)どうかはわかるのだ。

なので、王手がかかっている局面では、EVASIONS(王手回避)の指し手を生成するようにコードを書く。

ゆえに、そうコードを書く限りにおいて、a)はありえないのだ。

※ ちなみに、やねうら王miniやAperyではEVASIONSの指し手にb)は含まれるが、c)は含まれない。逆にEVASIONSの指し手にb),c)を含めない設計もありうる。このへんは生成した王手回避手が平均いくつあって、その何%が実際にdo_move()されるのかという統計を取って総合的に判断する必要がある。

例えば、b)はある升に敵の利きがあるのかどうかを調べるのが簡単なデータ構造の将棋ソフトであれば、指し手生成のときに除外してしまったほうが、そのあとその指し手に点数をつけて(スコアリング)、そしていざdo_move()する直前にlegal()でのチェックに引っかかり、結局その指し手は使えないということはなくなるわけだから、指し手生成の時点で除外されているほうが優れた実装である。すなわち、このとき、b)は、4.に分類してしまいたい。

ついでに言えば、c)も4.に分類してしまえば、legal()自体が要らなくなる。そうしたほうが速い可能性もある。

本当にdo_move()の直前まで遅延させたほうが良いのかについては、このようにそのソフトの指し手生成器の性能と利きを簡単に調べられるデータ構造になっているかだとか、探索でどの程度枝刈りされるのかだとか、いくつも要因が相まって難しい問題なのだ。

でもまあ、やねうら王miniでは上の4つの分類を採用していて、これはこれでベストだと思っているから、変えないとは思う。
※ ただ、上記のb)は指し手生成の段階で除外するように変更する可能性はある。

ここまでのまとめ

今回で探索部を書いていくための道具はすべて揃った。
これだけあれば、あとは好きなように探索部を書いていくことは出来る。

そこで、今回でこの連載は最後として、次は探索部をごりごり書いていく連載を始める。
「探索部は自分で好きなように書く！」という人は、次回からの連載を読む必要はないだろう。