昨日の記事で、やねうら王miniのサンプルコードとして、将棋の初期局面から決まった深さまでの全合法手の組み合わせがいくつあるかを数えるプログラムを書きました。
以前、Stockfishのperft、ちらっと見て、「パフォーマンステスト？何やってるかよくわからん、探索と関係ないからまあいいや」と思って放置してたんですけど、、私は自力で同じ概念を発明して、「これを使えば簡単に合法手生成のテストが出来るな！このアイデア、すげーや！さすが俺や！」と思っていたら、それこそがperftであったという、アハ体験というかアホ(阿呆)体験というか、なんかそういう体験を昨日まさにしました。
そしてすでにaki.さんが将棋におけるperftをされてて記事までありました。
将棋でPerftしてみたまとめ
http://qiita.com/ak11/items/8bd5f2bb0f5b014143c8
やねうら王miniでも同じ計測が出来るように上の記事のコードを参考に、元コードと等価な動作になるようにしてみました。
|
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 |
struct PerftSolver { struct Result { uint64_t nodes, captures, promotions, checks, mates; void operator+=(const Result& other) { nodes += other.nodes; captures += other.captures; promotions += other.promotions; checks += other.checks; mates += other.mates; } }; Result Perft(Position& pos, int depth) { StateInfo st; Result result = {}; if (depth == 0) { result.nodes++; if (pos.state()->capturedType != NO_PIECE) result.captures++; if (is_promote(pos.state()->lastMove)) result.promotions++; if (pos.checkers()) { result.checks++; if (pos.is_mated()) result.mates++; } } else { for (auto m : MoveList pos.do_move(m.move,st); result += Perft(pos, depth - 1); pos.undo_move(m.move); } } return result; } }; // N手で到達できる局面数を計算する。成る手、取る手、詰んだ局面がどれくらい含まれているかも計算する。 void perft(Position& pos, istringstream& is) { int depth = 5; is >> depth; cout << "perft depth = " << depth << endl; PerftSolver solver; auto result = solver.Perft(pos,depth); cout << "nodes = " << result.nodes << " , captures = " << result.captures << " , promotion = " << result.promotions << " , checks = " << result.checks << " checkmates = " << result.mates << endl; } |
このコードはやねうら王miniにperftコマンドとして追加しておきます。時間がとてもかかるので、depth = 7まででやめましたが、そこまでの結果はaki.さんの記事の数値とぴたり一致しました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
> perft 1 perft depth = 1 nodes = 30 , captures = 0 , promotion = 0 , checks = 0 checkmates = 0 > perft 2 perft depth = 2 nodes = 900 , captures = 0 , promotion = 0 , checks = 0 checkmates = 0 > perft 3 perft depth = 3 nodes = 25470 , captures = 59 , promotion = 30 , checks = 48 checkmates = 0 > perft 4 perft depth = 4 nodes = 719731 , captures = 1803 , promotion = 842 , checks = 1121 checkmates = 0 > perft 5 perft depth = 5 nodes = 19861490 , captures = 113680 , promotion = 57214 , checks = 71434 checkmates = 0 > perft 6 perft depth = 6 nodes = 547581517 , captures = 3387051 , promotion = 1588324 , checks = 1730177 checkmates = 0 > perft 7 perft depth = 7 nodes = 15086269607 , captures = 156289904 , promotion = 78496954 , checks = 79636812 checkmates = 29 |
＞そこまでの結果はaki.さんの記事の数値とぴたり一致しました。
なるほど、merom686さんを含め、3人の専門家の方の見解が一致したと。
それならばこの数値の信頼性は６σぐらいはありそうですね。
ちなみに、ニュートリノに質量があるという観測結果もその程度の信頼性だったはずです。
スタックが尽きるまでに何局面位読めて何時間かかるんでしょうかね。
この応用でゲームツリー構築して、巡回も処理して一本のグラフにできたりしないですかねぇ。
相当ひねくれたグラフになると思いますが、ちょっと面白そうです。
最近では、シェアードポインタもありますし、C++のコンテナを使った不完全型定義も常套化されそうですし、ゲーム系の開発がはかどりそうでワクワクしています。
ただしC++17がVCに入るのは常に未定なため絶望しています。Orz
> スタックが尽きるまでに何局面位読めて何時間かかるんでしょうかね。
undo_move()のときにStateInfo等は巻き戻すので、探索深さに比例した分しか必要ではなく、perftは何千億時間かけても消費するスタックはたかだか知れてます。
ちょっ！
たかだか9手で11兆局面ってゲーム全体をグラフにしたらメモリ足りないですよね。
巡回処理したら小さくなるにせよ、メモリに乗らないですよね。
仰天しました。
うむ、甘かったなぁ。
今回の電王トーナメントの決勝トーナメント。
持ち時間各2時間だったと思うのですが、やねうら王の平均的な探索深さはどれくらいだったのでしょうか？
それから、だいたいで結構です、最大探索深さも教えていただけるとありがたい所です。
そんなところ実は全然見てなかったり…。
連載、お疲れ様です。
実行時間を表示する様にしておくと、何らかの改良をした時に、速度面で効果があったかどうかの確認ができますね。
時間のかかる動作確認専用のコマンドが他にもあるなら、実行時間の表示が欲しいと思いました。
benchコマンドは実行時間を表示するので、速度面では、これだけでいいような…。
> 合法手生成のテスト
適当な局面を１０００局選んで、それぞれのperft depth = 4を複数のソフトで突き合わせるとか。
適当な局面を１０００局選ぶのは、やねうらおさんがやって、その局面を公表するのがいいと思う
面白いアイデアですが、まあ、初期局面から8手ぐらいでたいていの指し手は出現するのでだいたいオッケーかと思います。
対数とると綺麗に直線ですね。ずっと候補手が27-30くらいですが9手じゃ広がらないのですなぁ。
持ち駒がほぼ無いからと言う事になりますが、合法手チェックに関しては金銀香を打ったり成ったりは出てこないということですね。
> 金銀香を打ったり成ったりは出てこない
76歩34歩22角成XXX11馬として5手目で香は取れますから7手目には香打ちが出てくるのでは？
あ、何ボケかましてるんでしょうか私は
たびたび済みません。高速化でどの程度の効果があるか（重複局面を）考えていたのですが、計算が合わなくて質問します。
合法手生成時に、一部の不成を省略してたりはしないでしょうか？
n=3でcaptures = 59とありますが、
・76歩→（34歩以外29候補手）→33角成or33角不成で58局面
・76歩→34歩→22角成or22角不成で2局面
あわせて60局面にならないでしょうか？
成りも34歩以外で29局面に、34歩では33と22の2局面ありそうに思えます。
何か盛大に勘違いしているかな……？
> 合法手生成時に、一部の不成を省略してたりはしないでしょうか？
してないです。
> あわせて60局面にならないでしょうか？
後手の2手目が44歩のときに角の利きが遮断されて33に成れないです。
あー、そうか。迂闊