perft 9できました。

いまperft 9が終わった。将棋の初期局面から9手で到達できる局面の数がわかった。(手順前後込み) 11.6兆局面あるようだ。正確な数字は次のツイートで書く。次はperft 10だ。俺は将棋のperftの世界記録を更新する。(たぶんperft 9以降まだ誰もやってなかったはず)

— やねうら王 (@yaneuraou) December 14, 2015

perft depth = 9 nodes = 11661472222632 , captures = 192307327995 , promotion = 96264455880 , checks = 83245184398 checkmates = 657904

— やねうら王 (@yaneuraou) December 14, 2015

いまperft10に挑戦中です。

ちなみにチェスの世界ではperftはこんな感じになっているそうです。
http://wismuth.com/chess/statistics-games.html

チェスのほうも1手ごとに20～30倍ぐらいの局面数になるようです。

チェスのほうは駒打ちがないので将棋よりはある局面での平均的な指し手の数は少ない傾向にありますが、それでも、チェスのほうは将棋で言う大駒が多いので(移動できる升は多いので)それほど大差ではないようです。

将棋のperft 9がチェスのperft10ぐらいに相当するようで、チェスではperft13か14あたりまで達成しているようです。

ということは将棋のほうも本気でやればperft12ぐらいまでは行けるのだと思います。

まあ、本気でやってる人がいない状況なんですけどね…。

私も、自分の書いたプログラムだとperft11は数ヶ月程度かかる見込みなので、perft11はやりたくないです…。node数だけでよければ、(頑張れば)その1/10ぐらいの時間で求まると思いますけども。

チェスのperft関連のフォーラムの書き込みを見てると、perftを高速化するの、アルゴリズム的には色々やりようがあるみたいなんですけど、私が書いたのはあるnodeでの結果(残り探索深さ + Result)を置換表にそのまま突っ込んでおくだけという超簡単実装です。またhash keyは衝突すると怖いので128bitにしてあります。そのソースコードは近々公開します。