連載やねうら王miniで遊ぼう!6日目

今回は、指し手で局面を進めるお話です。

指し手で局面を進める/戻すには?

局面クラスはPositionというのがある。

いままで使ってきたuser_test()という関数の引数にPositionの参照が渡ってきているので、なんとなくわかっているかと思う。

指し手はもうすでに説明した。Moveというenumだ。

では、次のように書いて局面が進むかということだが…。

do_moveの部分、引数が足りなくてコンパイルが通らない。

「それおかしくない?局面を進めるのに指し手以外の何の情報が必要なんだよ?必要なものは全部、Positionクラスに持たせておいて、pos.do_move(m);と書くだけで局面を進められるようにしとけよ!」

お怒り、ごもっとも。

しかし、そうなっていないのには深い理由がある。

その理由を解説する前に、まず上のプログラム、コンパイルが通るようにしてみる。

コンパイルが通り、無事、歩がひとつ進んだ。感動である。
歩がたった一つ前に進んだだけだが、我々にとってこれは大きな前進である。(←文学的な表現のつもり)

StateInfoとは何なのか?

StateInfoみたいなものが何故必要になるのか。

この理由は少しややこしい。
いまから順番に書いていくので、落ち着いて読んでみて欲しい。

局面を戻すundo_move()

まず、局面はdo_move()で進められることがわかった。
この逆変換も出来る。すなわち、局面を元に戻せる。

確かに局面は元に戻った。

何故局面を戻す必要があるのか?

undo_move()みたいなものが何故必要なのか?局面を進めるときに局面自体を丸ごとコピーして、戻すときはそれを破棄すればundo_moveのようなものは不要になるのではないのか。そう言われるかも知れない。

これは一理あるのだが、局面クラスはBitboardなどの構造体を大量に抱えている。なので、コピーするとなると大量のメモリをコピーしないといけないことになり、1%の高速化に命を費やしているF1レーサーのような世界において、このようなコピーはご法度なのだ。

確かに探索系のアルゴリズムを紹介してある本にはいかにも局面をコピーするかのような図が載っているが、それはアルゴリズム的にはそうだというだけで、現実的なプログラムにおいてはこのように局面(Position)は指し手(Move)によって差分更新される。当然、戻すときも差分更新だ。

この理由により、局面は戻せなくてはならないことがわかる。それがundo_move()なのだ。

捕獲した駒の情報はどこにあるのか?

局面をundo_move()で戻すということは、盤上で、Moveのto(移動先)にある駒がfrom(移動元)に戻る。そのときに捕獲された駒があった場合、手駒から、toの場所に戻る。

ところが、指し手Moveの定義を見たとき、捕獲した駒の情報が欠落していた。

では局面をundo_move()するときに捕獲した駒の情報はどこからやってくるのか?

これが意外に難しい。

「そんなのPositionクラスが内部的に持っておけばいいじゃん!」

と言われるかも知れない。しかし、実はどれだけ確保すればいいかはよくわからない。何手で終局するかはわからないからである。

「なら、Piece captured_piece[MAX_PLY];のように多めに確保すれば?」と言われるかも知れない。

ところが、将棋においては連続王手の千日手という禁則があるので、連続王手ではないことを確認するためには、現在の局面にいたるまでの手順を初手から調べなくてはならない。例えば、1000手目で10手先に連続王手の千日手になる局面が現れたとしよう。

思考エンジンの思考開始局面はこの1000手目の局面であるが、GUI(例えば、将棋所)は初手(平手の初期局面(“startpos”)での1手目)から、1000手目に至るまでの指し手をすべて送ってくる。

なので、このときcaptured_pieceはこの1000手分+αを保存しておかなければならないのである。
仮にMAX_PLYを2000手分確保したとしても、やはり2000手目の局面になったときにバッファが足りなくなる。

なので終局の手数がわからない状況において、captured_pieceのバッファを固定サイズで確保するのはあまりイケてない実装なのだ。

連続王手の千日手のために遡る最大手数は10手までで、かつ、1000手以上になればゲームは終了という扱いでよければ10+1000手分のcaptured_pieceのバッファがあれば良いのだが…。

「じゃあ、std::vectorとかで確保すればいいじゃん!」

と言われそうだが、探索中にresizeが起きるようなものは困る。0.1%の高速化をしようとしている世界において、C++のnewは極めて遅いので、絶対に呼び出されることがあってはならない。(USIプロトコルで標準出力に表示するときにstd::stringが内部的にnewを呼び出す分は仕方ないものとして)

StateInfoとは何を格納しているのか?

もうおわかりかも知れない。StateInfoは、その局面で捕獲した駒の情報を格納している。その他、局面を巻き戻すときに差分更新しようとするとかえって遅くなるようなものもここに詰め込まれている。

ということは、do_moveを一回するごとにStateInfo(のインスタンス)がひとつ必要だということだ。

しかし、探索は再帰的に書くので、これはあまり問題にならない。

search関数のなかでのStateInfoの確保

すなわち、次のように書く。

search関数が再帰的に呼び出されるが、その先頭でStateInfo型の変数を一つ用意して、do_move()の引数として渡してやる。基本的に、search関数のなかで二回連続してdo_move()を呼び出すことはないので、こういう書き方で問題ない。

そこでまず、上の書き方を定型句として覚えてしまって欲しい。

search関数が呼び出されるまでのStateInfoの確保

「GUIがstartposら1000手目までの指し手を送ってきたら」というような話をさきほどした。では、この1000手目までのStateInfoは誰がどこに確保するのか。

これは、例えば、スタックとして確保する。

std::stack<StateInfo> SetupState;

に対して、do_moveするときに、最後に積まれたStateInfo(の参照)を渡してやる。これが一つの方法で、Stockfishなどはこれに近いコードが書かれている。

SetupStates->push(StateInfo());
pos.do_move(m, SetupStates->top());

undo_move()は、どうやって一つ前のStateInfoを見つけるのか

ここで不思議に思うかも知れない。

undo_move()のなかで、局面を戻すときにPositionクラスが参照しているStateInfoも一つ前のものに戻さないといけないということだ。アドレスが連続していれば戻すのは簡単だが、上の例を見る限り、途中まではstack<StateInfo>を渡しておいて、途中から関数の内部に確保したStateInfo型の変数(の参照)を渡している。アドレスはどう見ても連続していない。こんなことで一つ前のものに戻れるのかと。

実は、StateInfoは次のような構造になっている。

このpreviousで一つ前のポインタを持っているのである。do_move()のときに、これを使って数珠つなぎにしておくのである。要するに次のようになっている。

undo_move()するときは、これを辿って戻る。

将棋の開始局面からN手で到達できる局面の数を求める

指し手生成と局面のdo/undoが出来るようになったので、将棋の開始局面からN手で到達できる局面の数を求めてみよう。ただし、手順違いで同じ局面に到達する場合、重複してカウントして良いものとする。

※ user_test()関数は、ユーザーがパラメーターを指定できるように拡張しておいた。

このテストは、コンピューター将棋プログラムの指し手生成部において、指し手が過不足なく生成されているかのテストとしてよく用いられる。次のツイートと比較すると、この値は、ぴったり一致している。

ちなみに、この初期局面から7手で到達できる局面の数を調べるのにはやねうら王miniでは20分ぐらいかかった。150億局面ほどあるようだ。8手で到達できる局面の数を求めるには上のプログラムのままではたぶん数日かかる気がする。(同じ局面に合流することが多いので一度到達した局面はそこからN手で到達できる局面の数を覚えておくようにすればこの処理時間はずいぶん短縮できるが。)

次回に続く。


連載やねうら王miniで遊ぼう!6日目” への15件のコメント

  1. Windows/Mac環境用の等幅フォント指定した。盤面が崩れているのなおってちょっと気分が良い。Android + Chromeでは崩れない。iOS + Safariだと等幅フォントになってはいるが、スペースと半角文字(“^”)との幅が違うようで崩れる。css難しすぎ。

  2. >Aperyではその条件ではバグらないことにいま気づいた。・・・

    無意識の中では、平岡さんにメールを出し終えても「何か変だ」という認識があったのでしょうね。
    そうして、バックグラウンドでずうっと探索していた、、、と。
    答えが見つかってなによりです。

    • 私の場合、20年ぐらい前の会話も結構覚えていて、ときどき頭のなかから掘り返して、意味を考えなおしたりするんですけど、20年前の相手に謝りたい気持ちになることもしばしば…。

      ところでtwitterへの返信をそれだけここに書かれるとあとから見た人が何のことだかわからないので、twitter上で返信するか、ツイートのURLも貼り付けるようにお願いいたします。

  3. 最近のCPUは丸ごとコピーがかなり速くなっていると思いますが、それでもundo_move()を使ったほうがいいのでしょうか。

    http://twitter.com/merom686/status/640490155757846530
    ただし、このときは駒リストを持っていませんでした。また、必要ない部分までコピーしています。Sandy Bridgeのノートです。

    • PositionクラスにはBitboardやらPieceListやら場合によっては利きの情報などたくさんぶら下がっているので、そのへんはさすがにコピーするわけにはいかないと思いますが、コピーしたほうが速い分はコピーしてしまっていいと思います。

      StockfishのStateInfoの実装でもdo_move()のときにoffset_ofで途中のメンバまで前の局面のものをmemcpyしてあったと思います。

      あと、近年、コピー自体は速くなっているのですが、CPU cacheサイズはさほど大きくなっていないので探索のコアとなる部分でメモリをあまり無駄づかいするとCPU cacheが汚染されて評価関数のサイズを大きくして行ったときにCPU cacheのhit率が下がって遅くなります。そんなわけでして、評価関数を大きくしていくなら、同じぐらいの速度ならメモリを大切にするほうがいいかなと。

  4. >あれ? なんか多い? (自信なし)
    この感覚がよくわかりません。

    それに対してやねさんは、
    depth = 6までakiさんと合ってるから、 depth = 7は15086269607でOKだ!
    という判断でしょうか?

    • もとの会話が、isseiさんが局面数がいくつになるのが正しいのかを尋ねてきて、aki.さんがそれに答えるという流れでして、isseiさんの提示した局面数と異なるから「あれ?(自分の解答はisseiさんの局面数より)なんか多い?(自分がisseiさんより正しいという)自信なし」の意味ではないかと。

  5. YaneuraOu Ver1.40で遊ばせていただいている、プログラミング初心者です。

    ランダムプレーヤーを選択した状態でperftを行ったところ、深さ3以上で、下記エラーが発生しました。
    Run-Time Check Failure #3 – The variable ‘materialDiff’ is being used without being initialized.

    やねうら王nanoを選択していれば、問題はないようです。
    初心者なので、的はずれな内容でしたら申し訳ございませんが、念のためご報告させていただきます。

    いつも記事を楽しく拝見させていただいております。
    どうぞよろしくお願いいたします。

    • あー、思い出しました。以前はLEGALで全合法手を生成していたのが、その仕様は変更して、LEGAL_ALLで全合法手を生成するようにしたからです。本文中のサンプル、そのように書き換えておけば良いのですけど、書き換えて回るの面倒だったので変更してなかったのです。本記事のサンプルは書き換えておきますね。(他の記事も旧仕様のものがあると思いますけども、まあ、そういうことで…)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です