Help us understand the problem. What is going on with this article?

将棋でPerftしてみたまとめ

More than 5 years have passed since last update.

Perftとは

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

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

発端

結果

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

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つ前がそれだったときだけをカウントするもののようです。

まとめ(?)

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

続報

おまけ

Depth=7で詰んだ局面(Checkmates)

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

sfen ln+B1ggsnl/1r2k2b1/ppppSpppp/4p4/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w - 1
sfen ln1g1gsnl/1r1Bk2b1/ppppSpppp/4p4/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w - 1
sfen ln2Bgsnl/1rsGk2b1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1
sfen lns3snl/1rgkG+B1b1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1
sfen lnsg1g1nl/1r2kB1b1/ppppSp1pp/4p4/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1
sfen lnsg1g1nl/1r2kB1b1/ppppSpppp/4p4/9/P8/1PPPPPPPP/7R1/LNSGKGSNL w - 1
sfen lnsg1gsnl/5rkb1/ppppppp+Pp/9/9/9/PPPPPPP1P/1B5R1/LNSGKGSNL w P 1
sfen lnsg1k+Bnl/1r2gB3/pppppp1pp/6p2/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w S 1
sfen lnsgB2nl/1r2kGsb1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1
sfen lnsgg1+Bnl/1r2k2b1/ppppSpppp/4p4/9/P8/1PPPPPPPP/7R1/LNSGKGSNL w - 1
sfen lnsk2snl/1rg1G+B1b1/pppppp1pp/9/9/2P6/PP1PPPPPP/7R1/LNSGKGSNL w P 1

初期局面じゃない局面

初期局面だと色々問題になりそうな指し手が出てくるまでやるのが大変そうなので、他の局面もちょっとやってみよう、ということで、とりあえず合法手が最多(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;
    }
};
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away