今回は、指し手で局面を進めるお話です。
指し手で局面を進める/戻すには？
局面クラスはPositionというのがある。
いままで使ってきたuser_test()という関数の引数にPositionの参照が渡ってきているので、なんとなくわかっているかと思う。
指し手はもうすでに説明した。Moveというenumだ。
では、次のように書いて局面が進むかということだが…。
|
1 2 3 4 5 6 |
void user_test(Position& pos) { Move m = make_move(SQ_77,SQ_76); // 初期局面での76歩 pos.do_move(m); cout << pos; } |
do_moveの部分、引数が足りなくてコンパイルが通らない。
「それおかしくない？局面を進めるのに指し手以外の何の情報が必要なんだよ？必要なものは全部、Positionクラスに持たせておいて、pos.do_move(m);と書くだけで局面を進められるようにしとけよ！」
お怒り、ごもっとも。
しかし、そうなっていないのには深い理由がある。
その理由を解説する前に、まず上のプログラム、コンパイルが通るようにしてみる。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void user_test(Position& pos) { StateInfo st; Move m = make_move(SQ_77, SQ_76); // 初期局面での76歩 pos.do_move(m,st); cout << pos; } > user ^香^桂^銀^金^玉^金^銀^桂^香 □^飛 □ □ □ □ □^角 □ ^歩^歩^歩^歩^歩^歩^歩^歩^歩 □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ 歩 □ □ □ □ □ □ 歩 歩 □ 歩 歩 歩 歩 歩 歩 □ 角 □ □ □ □ □ 飛 □ 香 桂 銀 金 玉 金 銀 桂 香 先手 手駒 : , 後手 手駒 : 手番 = 後手 sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/2P6/PP1PPPPPP/1B5R1/LNSGKGSNL w - 2 |
コンパイルが通り、無事、歩がひとつ進んだ。感動である。
歩がたった一つ前に進んだだけだが、我々にとってこれは大きな前進である。(←文学的な表現のつもり)
StateInfoとは何なのか？
StateInfoみたいなものが何故必要になるのか。
この理由は少しややこしい。
いまから順番に書いていくので、落ち着いて読んでみて欲しい。
局面を戻すundo_move()
まず、局面はdo_move()で進められることがわかった。
この逆変換も出来る。すなわち、局面を元に戻せる。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void user_test(Position& pos) { StateInfo st; Move m = make_move(SQ_77, SQ_76); // 初期局面での76歩 pos.do_move(m,st); pos.undo_move(m); // 局面を元に戻してみる cout << pos; } > user ^香^桂^銀^金^玉^金^銀^桂^香 □^飛 □ □ □ □ □^角 □ ^歩^歩^歩^歩^歩^歩^歩^歩^歩 □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ 歩 歩 歩 歩 歩 歩 歩 歩 歩 □ 角 □ □ □ □ □ 飛 □ 香 桂 銀 金 玉 金 銀 桂 香 先手 手駒 : , 後手 手駒 : 手番 = 先手 sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1 |
確かに局面は元に戻った。
何故局面を戻す必要があるのか？
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の確保
すなわち、次のように書く。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// depthは探索の残り深さ Score search(Position& pos,int depth) { // depthが少なくなってきたら、評価関数を呼び出して終わり if (depth <= 0) return evaluate(pos); StateInfo st; while (move = この局面での指し手を一つ取り出す) { pos.do_move(move,st); score = search(pos,depth-1); pos.undo_move(move); // ここで枝刈り等、何らかの処理 } } |
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は次のような構造になっている。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// StateInfoは、undo_move()で局面を戻すときに情報を元の状態に戻すのが面倒なものを詰め込んでおくための構造体。 // do_move()のときは、ブロックコピーで済むのでそこそこ高速。 struct StateInfo { // この局面で捕獲された駒 // ※ 次の局面にdo_move()で進むときにこの値が設定される // 先後の区別はなし。馬とか龍など成り駒である可能性はある。 Piece capturedType; … // 一つ前の局面に遡るためのポインタ。 // NULL MOVEなどでそこより遡って欲しくないときはnullptrを設定しておく。 StateInfo* previous; }; |
このpreviousで一つ前のポインタを持っているのである。do_move()のときに、これを使って数珠つなぎにしておくのである。要するに次のようになっている。
|
1 2 3 4 5 6 7 8 9 10 11 |
// 指し手で盤面を1手進める。 void Position::do_move(Move m, StateInfo& new_st, const CheckInfo& ci, bool givesCheck) { // --- StateInfoの更新 // StateInfoを遡れるようにpreviousを設定しておいてやる。 new_st.previous = st; st = &new_st; … } |
undo_move()するときは、これを辿って戻る。
将棋の開始局面からN手で到達できる局面の数を求める
指し手生成と局面のdo/undoが出来るようになったので、将棋の開始局面からN手で到達できる局面の数を求めてみよう。ただし、手順違いで同じ局面に到達する場合、重複してカウントして良いものとする。
※ user_test()関数は、ユーザーがパラメーターを指定できるように拡張しておいた。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
// 再帰的に呼び出される uint64_t enumerate_nodes_sub(Position& pos, int depth) { // ノードの合計 uint64_t nodes = 0; StateInfo st; for (auto m : MoveList { // 残り深さがまだあるなら、それぞれの指し手で1手進めて再帰的にこの関数を呼び出す pos.do_move(m.move, st); nodes += (depth > 1) ? enumerate_nodes_sub(pos, depth - 1) : 1; pos.undo_move(m.move); } return nodes; } // USI拡張コマンド"user"が送られてくるとこの関数が呼び出される。実験に使ってください。 void user_test(Position& pos, istringstream& is) { int depth = 5; is >> depth; cout << "Enumerate Nodes , depth = " << depth << endl; cout << enumerate_nodes_sub(pos, depth) << endl; // 与えられた局面からdepth手で到達できるノード数の合計 } > user 1 Enumerate Nodes , depth = 1 30 > user 2 Enumerate Nodes , depth = 2 900 > user 3 Enumerate Nodes , depth = 3 25470 > user 4 Enumerate Nodes , depth = 4 719731 > user 5 Enumerate Nodes , depth = 5 19861490 > user 6 Enumerate Nodes , depth = 6 547581517 > user 7 Enumerate Nodes , depth = 7 15086269607 |
このテストは、コンピューター将棋プログラムの指し手生成部において、指し手が過不足なく生成されているかのテストとしてよく用いられる。次のツイートと比較すると、この値は、ぴったり一致している。
30
900
25470
719731
19861490
547581517
あれ？ なんか多い？ (自信なし)— aki. (@ak11) May 27, 2015
ちなみに、この初期局面から7手で到達できる局面の数を調べるのにはやねうら王miniでは20分ぐらいかかった。150億局面ほどあるようだ。8手で到達できる局面の数を求めるには上のプログラムのままではたぶん数日かかる気がする。(同じ局面に合流することが多いので一度到達した局面はそこからN手で到達できる局面の数を覚えておくようにすればこの処理時間はずいぶん短縮できるが。)
次回に続く。
Windows/Mac環境用の等幅フォント指定した。盤面が崩れているのなおってちょっと気分が良い。Android + Chromeでは崩れない。iOS + Safariだと等幅フォントになってはいるが、スペースと半角文字(“^”)との幅が違うようで崩れる。css難しすぎ。
＞Aperyではその条件ではバグらないことにいま気づいた。・・・
無意識の中では、平岡さんにメールを出し終えても「何か変だ」という認識があったのでしょうね。
そうして、バックグラウンドでずうっと探索していた、、、と。
答えが見つかってなによりです。
私の場合、20年ぐらい前の会話も結構覚えていて、ときどき頭のなかから掘り返して、意味を考えなおしたりするんですけど、20年前の相手に謝りたい気持ちになることもしばしば…。
ところでtwitterへの返信をそれだけここに書かれるとあとから見た人が何のことだかわからないので、twitter上で返信するか、ツイートのURLも貼り付けるようにお願いいたします。
想いが至らず失礼しました。
これでよかったでしょうか？
https://twitter.com/yaneuraou/status/675411679388151808
twitter使ってませんので、ツイートのURL、探すのに一苦労でした。
> twitter使ってませんので、ツイートのURL、探すのに一苦労でした。
このブログの右端にあるツイート欄のところの「X時間」とか書いてあるところがリンクURLになっているので右クリックしてリンクアドレスを取得すれば良かったり？
最近の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率が下がって遅くなります。そんなわけでして、評価関数を大きくしていくなら、同じぐらいの速度ならメモリを大切にするほうがいいかなと。
解説ありがとうございます！
＞あれ？ なんか多い？ (自信なし)
この感覚がよくわかりません。
それに対してやねさんは、
depth = 6までakiさんと合ってるから、 depth = 7は15086269607でOKだ！
という判断でしょうか？
もとの会話が、isseiさんが局面数がいくつになるのが正しいのかを尋ねてきて、aki.さんがそれに答えるという流れでして、isseiさんの提示した局面数と異なるから「あれ？(自分の解答はisseiさんの局面数より)なんか多い？(自分がisseiさんより正しいという)自信なし」の意味ではないかと。
YaneuraOu Ver1.40で遊ばせていただいている、プログラミング初心者です。
ランダムプレーヤーを選択した状態でperftを行ったところ、深さ3以上で、下記エラーが発生しました。
Run-Time Check Failure #3 – The variable ‘materialDiff’ is being used without being initialized.
やねうら王nanoを選択していれば、問題はないようです。
初心者なので、的はずれな内容でしたら申し訳ございませんが、念のためご報告させていただきます。
いつも記事を楽しく拝見させていただいております。
どうぞよろしくお願いいたします。
ifdefでの囲み忘れがあったようなので修正しておきました(｀･ω･´)ゞ
今試したら3以降がちょっと少ないです。
あー、長らくperftまわり見てなかったのでのちほど修正しときますね。
あー、思い出しました。以前はLEGALで全合法手を生成していたのが、その仕様は変更して、LEGAL_ALLで全合法手を生成するようにしたからです。本文中のサンプル、そのように書き換えておけば良いのですけど、書き換えて回るの面倒だったので変更してなかったのです。本記事のサンプルは書き換えておきますね。(他の記事も旧仕様のものがあると思いますけども、まあ、そういうことで…)