10
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

将棋でPerftしてみたまとめ

Last updated at Posted at 2015-05-29

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;
    }
};
10
9
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
10
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?