オセロでは8×8 = 64升あり、最初に4石置いてあるので残り60升しかありません。すなわち最長でも60手で終局します。
将棋の場合、何手で終局というのは決められていませんが、電王トーナメントルールでは256手ですし、普通の将棋では、平均的には140手ぐらい(?)で終局します。
では、普通の将棋のルールで、ゲーム木は無限の深さを持つのでしょうか？
いいえ。
あまり知られていない事実だと思うので、いまから、これを証明します。
まず用語の定義から。
盤面 : 9×9 = 81升のどの位置にどの駒があるか(あるいは駒がないか)
局面 : 盤面 + 手駒(先手・後手) + 手番
千日手 : 同一局面が4回出現すると千日手で終局となります。
合法な局面 : 二歩になっていない、王手放置で他の手を指していないetc..。
また、合法な局面は有限です。これは、自明なので証明はいいでしょう。
将棋は、合法な局面から1手指すことで次の合法な局面に遷移します。
これが無限に遷移できるかというのがいま与えられた命題です。
ところが千日手ルールがありますから、終局時以外で同一局面は4回出現しないです。合法な局面が有限であるので、合法な局面から合法な局面に遷移していこうにも、合法な局面の数×3回以上の遷移は出来ないことになります。
証明終わり。
※ なお、「合法な局面の数」(≒探索空間の広さ)は、将棋の場合、10^220程度ではないかと言われています。詳細はよく知りませんが。
「合法な局面の数×3回」がゲーム木の深さの上界(実際の値はもっと小さな値)です。ゲーム木の深さの上限(本当の値)を仮にDだとすると(Dは10^80とかそのぐらいのオーダーだと思う)、min-max法でも探索深さdepthをDまで持っていけば、最善手(神の指し手)が得られることになります。
まあ、適切な評価関数を設定してやれば、実際Dに持っていくよりずっと早い段階で最善手が得られます。私見ですが、いまの最強の将棋ソフトの評価関数であればたぶん(min-maxの)探索深さで言うと120〜160ぐらいで神の指し手と一致するのではないでしょうか。
また、depthを1から大きくしていくと神の指し手との指し手一致率は(単調増加ではないですが)上がっていきます。
このことの証明は容易ではありませんが(将棋ではこの数学的な証明はまだなされていないし、当分されることもないでしょう)、depthを増やすと指し手が棋力が上がるであろうこと自体は「人間でも(同じぐらいの大局観であれば)3手読む人よりは5手読む人のほうが強い」ので、深くまで読むほうがトータルでは強いであろうと考えるのが自然です。よほど大局観がボロボロでない限りは。
「合法な局面の数」は将棋の場合10^70～10^80と言われてます。
10^220は探索木を作ったとき[分岐数80(平均合法手数)で深さ115(平均終局手数)]の末端ノードの概数だったはずです。
あ、そうなんですね。「10^220」は、Bonanzaの発表スライドで見ただけなので意味はよくわかってませんでした。ご指摘ありがとうございます。
こういうものがありますよー。
「将棋における実現可能局面数について」
http://www.nara-wu.ac.jp/math/personal/shinoda/shogi.html
593通り！しかもこれ篠田先生の発表なんですね。奈良女子大、また遊びに行きます。(女の子見に…)
５９３通りは最大分枝数（ある局面の合法手の最大数）ですね。
さっきのコメントのページにPDFが２つあって、上のPDFが最大分枝数について、下が実現可能局面数についてです。説明不足ですみません。
下のPDFによると実現可能局面数（合法な局面の数）は10^60以上10^70未満ということで、無限の大きさの置換表があれば、探索空間はそれと同じになる。ということでいいのでしょうか。（自信なし）
女子大…行ったことないのですが、現実はどうなんでしょう…。
> 下のPDFによると実現可能局面数（合法な局面の数）は10^60以上10^70未満
なるほろ。篠田先生らしく、かなり低めの数値ですね。
地球上の原子の数が10^50ぐらいでしょうから、地球上の原子ひとつひとつに1bitずつ記憶させたとしてもまだ足りないですが…。
逆にプロの棋譜に出現しそうな局面の99.9%を網羅できるだけでいいなら(あと、即詰みが発生したときはその時点で打ち切る)、10^40ぐらいに減らせられそうではありますが…。それでも多いですなー。
囲碁の方は、つい先日18*18盤の合法局面数が正確に求められたみたいです。19*19も力技でいけそうですね。
ちなみに19*19の近似値は乱択アルゴリズムで2.08168199381982*10^170となっています。
電王戦、やれることは無いのでしょうが、頑張ってください！
ではでは
http://oeis.org/A094777
http://tromp.github.io/go/legal.html
す、、すごい！！> 囲碁の合法局面数
これまた面白い情報、ありがとうございます。
将棋の終局までの手数が有限なのは千日手ルールがあるので仰るとおりで。
ただ本題と外れますが、局面数が10^60オーダーなのと、終局までの手数がそれに近いのかは別問題ではないでしょうか。駒の動きに制限があるので最大限に1局を引き延ばしても10^20オーダーで終局してしまう可能性もあるのかなと。
そっち方面の研究をやってもあまりウケなそうですが、やってみたらやたら応用がきく研究になる可能性も
> 10^20オーダーで終局してしまう可能性もあるのかなと。
はい、そうですね。自由にnode(局面)間の状態遷移が出来るわけではないですしね。
500手ルール(＋王手延長ルール)のもとでは、
最大何手になるのかが気になります。