単純な状態空間なら>>63より遥かに小さいのだが、
プランニングを考えるとなると打つ場所の履歴を保存しなきゃならんわけで、
その場合の数はめちゃくちゃに膨れ上がる。
オセロだと10^60通り程度、チェスだと10^120通り程度、
将棋だと10^220通り程度、囲碁だと10^360通り程度、
と、この手の研究をやってる人は言ってる。

ちなみに今のコンピュータではオセロでも完全解析は全然無理。
それでもオセロに関してはコンピュータは人間より遥かに強い。
チェスは、有名だと思うけど、
IBMがdeep blueっていうそれ専用のコンピュータを作ってようやくチャンピオンに勝った。
（但し、他の人には対応できないし、数回の対局の合間にプログラマが手を入れたりしていた。
短時間で完璧にアルゴリズムを弄る腕は素晴しいが・・・。）
将棋はやっとアマチュア5段に達するかどうかというところ。
囲碁は・・・だめぽ。