« 2011年12月 | トップページ | 2012年2月 »

2012年1月

将棋の盤面数

米長永世棋聖がボンクラーズに敗れたというニュースがきたので、将棋ネタでも書いておこうと思う。

将棋(本将棋)の盤面の正確な通り数については私は知らない。そもそも厳密にルールを理解してすらいない。
でも、以前、大まかな通り数を計算してみたことはある。一応専門的にゲーム理論も勉強したし、いろんなきっかけでいろんなゲームの解析をしていた。その一部の痕跡は私のサイトにも顕れているから知る人ぞ知るところ。

だいたい、二歩を考慮して、2.75 × 10 70 通りより少ない程度だ。
連盟公式のはもっと色々ルールがあるようなので(行き所のない駒は禁止とか)、もうすこし小さくなるだろう。

1つの盤面は単純に考えて45バイトあれば十分表現できるが、もっと小さくできる。
2.75 × 10 70 < 2 234
ということで高々234ビットにはできるはず。

検索すると 10 220 みたいな記載をみかけるが、それはおそらく指し手の通り数(しかもかなりアバウトな概算)であって、盤面の通り数ではない。

しかし、着手の通り数を考えるのは、連盟のルールに文脈(ヒストリー)に関するものが含まれているからだと思われる。そういうルールだと、手順を考慮しないと必勝プログラムは作れない。2 234でも十分大変だが、このことがさらに難度を高くしている。


これまでゲームやロボットやいろいろな「俗に言う人工知能」を作ってきた私だが、将棋のは単純に数理的な問題なので、いまのところあまり興味がない。でも将棋は好きなので、いつかやる日が来るのかな。

| | コメント (0) | トラックバック (0)

« 2011年12月 | トップページ | 2012年2月 »