立体４目並べの局面数の上限

質問

縦６マス×横７マスの立体４目並べが先手必勝か
どうか調べようとしています。
どれぐらいの局面を調べなければならないでしょうか。
正確な数値を出すのは難しそうなので最悪でもこれ以下になるという数値を出してください。
よろしくお願いします。

立体４目並べ
http://www.gandom-aids.co.jp/ConnectFour.htm

回答No.3

eatern27 · ベストアンサー

たまたま、２ちゃんねるで、こんなの見つけました。

http://science3.2ch.net/test/read.cgi/math/1032447973/422-431
(将棋・囲碁の話題なのは気にしないで下さい)

これによると、state-space complexity(可能な局面の数)
は、～10^14以下らしいです。
これでは、nagata20000さんより精度が悪いですが。

そんなことより、気になるのは、#423の
＞コネクトフォー　　～10^21通り (1988年Victor Allisが必勝法報告)

という「必勝法報告」の記述です。

これの情報もととみられる#422で紹介されているサイトが確認できず、
「先手の必勝」or「後手の必勝」とか、
どの大きさでやっているのか(縦６マス×横７マスの大きさなのか)
という情報が全く分からない事が残念でなりません。(確認できても載っている保証はありませんが)

同じサイトを情報源としていると見られる#429によると、可能な局面の数の上限が10^14で、nagata20000さんの仰る68,796,803,560,332に近いので(むしろ、四捨五入すれば10^14になるので)、縦６マス×横７マスでの議論である可能性は十分にあると思います。なので、「先手必勝か否か」を知るのが目的なら、Victor Allis氏が発見した必勝法を探す方が早いかもしれませんね。

参考になる情報なのかは私にはわかりませんが。。。

参考URL：

http://science3.2ch.net/test/read.cgi/math/1032447973/422-431

お礼

回答ありがとうございます。
もう必勝法がわかっているんですか。
ちょっと残念。Victor Allisの必勝法探してみます。

回答No.2

ryn

> 最終局面の数はそれでよいと思うのですが
> 最終局面に至るまでの途中の局面が数えられていない
> ので42C21が上限ということはいえないと思います。
確かにおっしゃる通りです．
失礼いたしました．

とすると，質問者さんの
　68,796,803,560,332 通り
というのはかなり抑えられていますね．

もう少し考えてみます．

回答No.1

ryn

少なくとも
　〇●〇●〇●〇
　〇●〇●〇●〇
　〇●〇●〇●〇
　●〇●〇●〇●
　●〇●〇●〇●
　●〇●〇●〇●
という勝負がつかずに最後までいく例があるので
上限を考えてみます．

42ヶ所のうち21ヶ所に黒(or 赤)を埋める方法は
　42C21 = 538257874440 通り
あります．

あと，左右対称なのでもう少し減らすことができます．
といっても単純に２で割るというわけにはいかないですが．

お礼

回答ありがとうございます。
最終局面の数はそれでよいと思うのですが
最終局面に至るまでの途中の局面が数えられていない
ので42C21が上限ということはいえないと思います。

補足

ちなみに私が計算した上限は
68,796,803,560,332
でした。これではちょっと大きすぎて計算機で計算できそうにありませんね。