将棋でPerftしてみたまとめ

# Perftとは

決まった深さまでの全合法手の組み合わせはいくつあるのかを数える試み(?)です。

https://chessprogramming.wikispaces.com/Perft
https://chessprogramming.wikispaces.com/Perft+Results

# 発端

<blockquote class="twitter-tweet" lang="ja"><p lang="ja" dir="ltr">（緩募） この数列（Number of possible chess games at the end of the n-th ply）の将棋版（30,900,...）をどなたかご存じでしたらご教示ください（できればn=10まで） <a href="https://t.co/M66hCKEMrn">https://t.co/M66hCKEMrn</a></p>&mdash; math26 (@math26) <a href="https://twitter.com/math26/status/603403192269807617">2015, 5月 27</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

# 結果

…というわけで、やってみたので結果をまとめておきます。

|Depth|         Nodes|    Captures|  Promotions|      Checks|Checkmates|
|----:|-------------:|-----------:|-----------:|-----------:|---------:|
|1|                30|           0|           0|           0|         0|
|2|               900|           0|           0|           0|         0|
|3|            25,470|          59|          30|          48|         0|
|4|           719,731|       1,803|         842|       1,121|         0|
|5|        19,861,490|     113,680|      57,214|      71,434|         0|
|6|       547,581,517|   3,387,051|   1,588,324|   1,730,177|         0|
|7|    15,086,269,607| 156,289,904|  78,496,954|  79,636,812|        29|
|8|   416,062,133,009|4,713,670,699|2,222,896,064|2,047,229,309|  3,420|

Chess Programming WikiのPerft Resultsのページには取る手とかもあったので、その辺もついでにやってみました。

merom686さんのアイディアによりStockfishのPerftの実装を使って確認したところ、末端(Depthが0になったところ。詰みは含まない)の1つ前がそれだったときだけをカウントするもののようです。

# まとめ(?)

この結果が正しいのかはそれほど自信がないので、追試結果とかの情報は大歓迎です。(一致しててもしてなくても)

## 続報

* [上記の結果とおまけの最多合法手局面の結果がmerom686さんの結果と一致したそうです。](https://twitter.com/merom686/status/604463763601768448)


# おまけ

## Depth=7で詰んだ局面（Checkmates）

Depth=7で詰んだ局面（王手がかかっていて、合法手が0個の局面）が29個だったので、局面を出力してみました。
重複を除くと11種類になりました。
リンク先は[こちらのサービス](http://sfenreader.appspot.com/)で局面の画像にしてます。

[sfen ln+B1ggsnl/1r2k2b1/ppppSpppp/4p4/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w - 1](http://sfenreader.appspot.com/sfen?sfen=ln%2BB1ggsnl%2F1r2k2b1%2FppppSpppp%2F4p4%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+-)
[sfen ln1g1gsnl/1r1Bk2b1/ppppSpppp/4p4/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w - 1](http://sfenreader.appspot.com/sfen?sfen=ln1g1gsnl%2F1r1Bk2b1%2FppppSpppp%2F4p4%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+-)
[sfen ln2Bgsnl/1rsGk2b1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1](http://sfenreader.appspot.com/sfen?sfen=ln2Bgsnl%2F1rsGk2b1%2Fpppppp1pp%2F9%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+P)
[sfen lns3snl/1rgkG+B1b1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1](http://sfenreader.appspot.com/sfen?sfen=lns3snl%2F1rgkG%2BB1b1%2Fpppppp1pp%2F9%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+P)
[sfen lnsg1g1nl/1r2kB1b1/ppppSp1pp/4p4/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1](http://sfenreader.appspot.com/sfen?sfen=lnsg1g1nl%2F1r2kB1b1%2FppppSp1pp%2F4p4%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+P)
[sfen lnsg1g1nl/1r2kB1b1/ppppSpppp/4p4/9/P8/1PPPPPPPP/7R1/LNSGKGSNL w - 1](http://sfenreader.appspot.com/sfen?sfen=lnsg1g1nl%2F1r2kB1b1%2FppppSpppp%2F4p4%2F9%2FP8%2F1PPPPPPPP%2F7R1%2FLNSGKGSNL+w+-)
[sfen lnsg1gsnl/5rkb1/ppppppp+Pp/9/9/9/PPPPPPP1P/1B5R1/LNSGKGSNL w P 1](http://sfenreader.appspot.com/sfen?sfen=lnsg1gsnl%2F5rkb1%2Fppppppp%2BPp%2F9%2F9%2F9%2FPPPPPPP1P%2F1B5R1%2FLNSGKGSNL+w+P)
[sfen lnsg1k+Bnl/1r2gB3/pppppp1pp/6p2/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w S 1](http://sfenreader.appspot.com/sfen?sfen=lnsg1k%2BBnl%2F1r2gB3%2Fpppppp1pp%2F6p2%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+S)
[sfen lnsgB2nl/1r2kGsb1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1](http://sfenreader.appspot.com/sfen?sfen=lnsgB2nl%2F1r2kGsb1%2Fpppppp1pp%2F9%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+P)
[sfen lnsgg1+Bnl/1r2k2b1/ppppSpppp/4p4/9/P8/1PPPPPPPP/7R1/LNSGKGSNL w - 1](http://sfenreader.appspot.com/sfen?sfen=lnsgg1%2BBnl%2F1r2k2b1%2FppppSpppp%2F4p4%2F9%2FP8%2F1PPPPPPPP%2F7R1%2FLNSGKGSNL+w+-)
[sfen lnsk2snl/1rg1G+B1b1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1](http://sfenreader.appspot.com/sfen?sfen=lnsk2snl%2F1rg1G%2BB1b1%2Fpppppp1pp%2F9%2F9%2F2P6%2FPP1PPPPPP%2F7R1%2FLNSGKGSNL+w+P)

## 初期局面じゃない局面

初期局面だと色々問題になりそうな指し手が出てくるまでやるのが大変そうなので、他の局面もちょっとやってみよう、ということで、とりあえず合法手が最多(593手)な局面からもやってみました。

sfen R8/2K1S1SSk/4B4/9/9/9/9/9/1L1L1L3 b RBGSNLP3g3n17p 1

|Depth|         Nodes|    Captures|  Promotions|      Checks|Checkmates|
|----:|-------------:|-----------:|-----------:|-----------:|---------:|
|1|               593|           0|          52|          40|         6|
|2|           105,677|         538|           0|       3,802|         0|
|3|        53,393,368|     197,899|   4,875,102|   3,493,971|   566,203|
|4|     9,342,410,965|  60,043,133|  19,957,096| 335,329,926|        52|


## 実装例(抜粋)

取る手とかのカウントはこんな感じにしてますということで適当に抜粋。

```cpp
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) {
        Result result = {};
        if (depth == 0) {
            result.nodes++;
            BOOST_ASSERT(!pos.states.empty());
            if (pos.states.back().captured != Piece::None) result.captures++;
            if (pos.states.back().move.IsPromotion()) result.promotions++;
            if (pos.IsChecked()) {
                result.checks++;
                if (pos.IsMate()) result.mates++;
            }
        } else {
            for (auto move : pos.GetMoves<Position::MovesType::Legal>()) {
                pos.DoMove(move);
                result += Perft(pos, depth - 1);
                pos.UndoMove();
            }
        }
        return result;
    }
};
```