593通り

コンピュータ将棋で先読みを行うときに、
とりあえず可能な手を全部列挙したいことがあります。
もちろん可変長配列に１手１手入れていっても良いのですが、
ムダな計算が増えて時間がもったいないです。

で、問題になるのがバッファのサイズです。
この将棋盤を動き回る手は全部で何通りあるのでしょうか。
ちょっと考えれば900通りを超えないことは容易にわかりますが、
なんとなくムダな気がします。

このことについては今まで謎だったのですが、
「コンピュータ将棋の進歩３」を見ると
593通りという数字が書いてありました。
本当に593通りなら、ちょっとだけバッファが節約できますね。

とはいえ、書いてあるのは数字だけでした。
誰かが証明した数字なのか、経験的な最大値なのか。。

結局よくわからないままです。
う〜ん。

Comments

証明済みです。

Posted by foo at 2007年07月02日 02:35

情報ありがとうございます。
証明はどこかwebにありますか？

Posted by あやまり＋ at 2007年07月02日 08:43

99年頃にCSAのMLに流れていたはずです。
あとは以下など。
http://ysu1.m78.com/mathematics/m22.html

Posted by bar at 2007年07月02日 11:37