Perft

math26 @math26

（緩募） この数列（Number of possible chess games at the end of the n-th ply）の将棋版（30,900,...）をどなたかご存じでしたらご教示ください（できればn=10まで） oeis.org/A048987

math26 @math26

>Chess Problems by Computer wismuth.com/chess/chess.ht…

いがときしん（いが） @igatoxin

@math26 興味本位で横から失礼します。どういう定義かよくわからなかったので教えていただけますでしょうか。

math26 @math26

@igatoxin n手目の局面までの指し手列が何通りあるか、です。将棋だと初手が30通りあるのでX(1)＝30、2手目も30通りあるのでX(2)=30×30＝900です（n=0のときはX(0)=1と定義するようです）。もっと厳密な定義をお尋ねでしょうか？

いがときしん（いが） @igatoxin

@math26 ありがとうございます。終局に絡むのかと思いちょっと悩んでしまいました。 このような問題に関してはもしかしたら篠田正人教授が詳しいかもしれないですね。

math26 @math26

@igatoxin あ、本人です（笑） チェスだと「n手目でcheckmate」の数も数えられているようですね。 wismuth.com/chess/statisti…

math26 @math26

@math26 n手目までの合法指し手が何通りあるかがまとめてあると、コンピュータ将棋のプログラムチェックとかに役に立ちそうな気がして（終局判定もチェックするためにn>7がいいかなと）

いがときしん（いが） @igatoxin

@math26 もしかしたらとは思ってはいたんですが、失礼しました（笑）あと心当たりは大槻先生くらいですが多分やってないですね……いまなら将棋ソフトの作者の方々に計算をお願いしたらすぐにできてしまいそうですね。

math26 @math26

@igatoxin いえいえ（笑）自分でプログラムいじるより、将棋ソフト開発されている方にお聞きしたほうが早いかなと思って手を抜きました。ただ、チェスでn=13まで、となると将棋ではn=11,12くらいで大変なのかもしれません

山本一成🚗自動運転TURINGのCEO🌖 @issei_y

@math26 Perftですね。 chessprogramming.wikispaces.com/Perft?response… CraftyやStockFishに実装もあります。Ponanzaでは・・飛車角とかの不成を作成してないのでわからないです・・

山本一成🚗自動運転TURINGのCEO🌖 @issei_y

GPS将棋に実装がありますね。ちょっと実行してみます（モニョモニョ

山本一成🚗自動運転TURINGのCEO🌖 @issei_y

[0 1] [1 30] [2 900] [3 25440] [4 718565] [5 19778301] [6 544123956]

山本一成🚗自動運転TURINGのCEO🌖 @issei_y

GPS将棋でコマンド入力すれば出るみたいですね。 $usi $perft [depth] ここから先は時間がかかりそうなので@math26 さんにお願いします

math26 @math26

@issei_y うお、ありがとうございます！！！

math26 @math26

X(0)=1,X(1)=30,X(2)=900,X(3)=25440,X(4)=718565,X(5)=19778301,X(6)=544123956,X(7)=14906093373ですか。nを1増やすと時間が約30倍かかるとすると、うちの環境ではn=10までは無理っぽい

math26 @math26

n=3以降でnを1増やしても30倍を少し切ってて「？」と思ったけど、玉を立ったり金上がったりすると飛車の可動域が減っちゃうから、ですね

ak11 @ak11

30 900 25470 719731 19861490 547581517 あれ？ なんか多い？ (自信なし)

山本一成🚗自動運転TURINGのCEO🌖 @issei_y

@ak11 Blunderの結果？

ak11 @ak11

@issei_y うん、Blunder。今飛車・角・歩の不成を除外したやつでやってみたら19778301とかになったから、GPSのも不成は入ってないみたい。

山本一成🚗自動運転TURINGのCEO🌖 @issei_y

@ak11 @math26 すいません間違ってました・・

山本一成🚗自動運転TURINGのCEO🌖 @issei_y

@ak11 ありがとう。

math26 @math26

@issei_y @ak11 あらそうなんですか。わざわざありがとうございます。n=3は人力で確認します

math26 @math26

@math26 飛角歩の不成が抜けてて（？）ちょっと値が違う模様

math26 @math26

@issei_y @ak11 n=3だと「▲76歩（△44歩以外）▲33角不成」の29通り、「▲76歩△34歩▲22角不成」の1通りが除外されて25470-30＝25440のようですね。ありがとうございました

merom686 @merom686

Perft、n=7,8は15086269680,416062446939であってますかね（置換表使用）。