Perftとは

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

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

発端

（緩募）この数列（Number of possible chess games at the end of the n-th ply）の将棋版（30,900,...）をどなたかご存じでしたらご教示ください（できればn=10まで） https://t.co/M66hCKEMrn
— math26 (@math26) 2015, 5月 27

結果

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

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さんの結果と一致したそうです。

おまけ

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

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

初期局面じゃない局面

初期局面だと色々問題になりそうな指し手が出てくるまでやるのが大変そうなので、他の局面もちょっとやってみよう、ということで、とりあえず合法手が最多(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

実装例(抜粋)

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

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;
    }
};

将棋でPerftしてみたまとめ

Perftとは

発端

結果

まとめ(?)

続報

おまけ

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

初期局面じゃない局面

実装例(抜粋)