Edited at

将棋でPerftしてみたまとめ

More than 3 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;
}
};