○×問題

○×問題

○×ゲームの棋譜数を数式で表現する試み

棋譜数をカウントするには、棋譜数の多さから
超天文学的に時間がかかる。
次に棋譜数を数式で表現できないかという発想が出てくるが、
これもなかなか難しい。
そこで、オセロゲームよりも数式表現が簡単そうな
○×ゲームを扱うのだが、、、
これもまだ解かれていない

---

194 ：名無しさん＠３周年：2005/08/29(月) 00:14:22 
要は｢カウント｣の限界だよね。正確に数を数えるには｢カウント｣以外ないのだが… 

196 ：名無しさん＠３周年：2005/08/29(月) 11:12:41 
>>194 
たしかに。 
オセロは 
ある局面の次の局面数はその盤面の状態に依存してしまう。 
○×ゲームみたいに次の局面数がみんな同じじゃないからなぁ。 
○×ゲームも正確には　9! ではなくて、途中で終わることも 
考慮しなければならないが。 

197 ：名無しさん＠３周年：2005/08/29(月) 16:47:21 
○×ゲームの試合結果の通り。 
カウントではなく数式で答えを出すのはこの問題でさえむずかくね？ 
やべー 

198 ：名無しさん＠３周年：2005/08/29(月) 23:23:58 
○×ゲーム程度のサイズなら全探索でOKじゃね？ 

199 ：名無しさん＠３周年：2005/08/29(月) 23:41:11 
>>197 
○×ゲームでは 
理論上、最も早く勝負がつくのは5手目だから 
それまでの9*8*7*6*5までは正確に分かる。 
問題は残りの4ターンがどういう振る舞いをするかだな。 
これをカウントせずに正確に算出できれば、 
オセロの総手数算出の足掛かりになるかもしれないな。

200 ：名無しさん＠３周年：2005/08/30(火) 00:22:18 
○×ゲームの全探索してみた。 
数式での計算の答えあわせに利用してくれ。 
引き分けは問題を簡単にするために全部埋まった時点でということにしておく。 
つまり勝負が決まる以外での枝刈りはなし。 
1ターン目の局面数: 9 
2ターン目の局面数: 72 
3ターン目の局面数: 504 
4ターン目の局面数: 3024 
5ターン目の局面数: 15120 
6ターン目の局面数: 54720 
7ターン目の局面数:148176 
8ターン目の局面数:200448 
9ターン目の局面数:127872 
全ての局面数： 549946 
先手の勝ち数： 131184 
後手の勝ち数： 77904 
バクの可能性もあるだろうから 
信頼性向上のため誰か他にも作って確認してくれ。 

201 ：名無しさん＠３周年：2005/08/30(火) 05:07:27 
>>198 
うん。でも探索はオセロでは使えないことが 
今までのﾚｽでほぼきまったと俺は思うのよ。 
方法としてあとは計算で出すしかないかと。 
>>199が言ってくれたように○×はその練習問題として 
いいんじゃない？ 
>>200 
おつかれどす。 
これで正解はでた。この数字に行き着く計算式を考えよっと。 
つーかやっぱり後手超不利だなw 

202 ：名無しさん＠３周年：2005/08/30(火) 19:29:43 
6ターン目以降が全て144で割り切れるのは偶然? 

204 ：名無しさん＠３周年：2005/09/02(金) 21:36:36 
>>200 
1ターン目: 9 
2ターン目: 72 
3ターン目: 504 
4ターン目: 3024 
5ターン目: 15120 
6ターン目: 54720 
7ターン目:148176 
8ターン目:200448 
9ターン目:127872 
一緒になりますたｗ乙！ 

205 ：名無しさん＠５周年：2005/09/03(土) 10:22:37 
>>204 
計算式を載せてくれ！！！！ 

206 ：名無しさん＠３周年：2005/09/03(土) 14:43:46 
>>205 
>>204と>>200はプログラムだと思われ。 

210 ：名無しさん＠５周年：2005/09/07(水) 23:01:26 
>>202 
必然。 
ｎターン目の局面数をPnとおくと 
P2＝P1ｘ8 
P3＝P2ｘ7 
P4＝P3ｘ6 
P5＝P4ｘ5 
このようある局面はそれまでの局面から派生したものであるから 
共通の局面というものが局面数の因子として数え上げられる。 

211 ：名無しさん＠５周年：2005/09/07(水) 23:34:58 
>>210 
よくわからんのだけど、 
それってP5の総盤面数は9,8,7,6,5を約数に持つって事? 
でも、あるターン以降は勝敗を決しているから 
そんなに単純にいかないのでは？ 
見当違いな意見だったらごめん 
もちっと詳しく教えて 

212 ：名無しさん＠５周年：2005/09/07(水) 23:57:11 
>>210 
6ターン目からは前のターンから掛け算的に派生したわけじゃないから、必然とはいい難くね？ 

213 ：名無しさん＠５周年：2005/09/08(木) 00:13:51 
６ターン目の総ノード数が 
9*8*7*6*5*4 - 5*4*3*2*1 * ((11*10*9*8)/(4*3*2*1)) 
になった。 
だれか理由を考えてくれ。 

215 ：名無しさん＠３周年：2005/09/08(木) 00:29:04 
ん？今更だが>>200,204は棋譜（というのか知らんが）が異なれば別、という探索？ 
てっきり盤面のパターン数を数えているのかとばかり…orz 
～5手は計算で分かるジャマイカ…orz 

217 ：名無しさん＠５周年：2005/09/08(木) 00:54:38 
nターン目で勝負がきまった曲面数をQnとすると 
P6=9C6-Q5×4 
;Cは場合の数の時につかうアレね。 
またQ5の話で、 
○を先手とした時に４ターン目で○がリーチになる通りは 
○を固定したとき○が２つある次元に×がない場合だから 
6C2=15通り 
非リーチの場合は同じく○を固定したとき 
6通り 
そしてリーチ状態から5ターン目でビンゴになる通りは 
1通り 
リーチ状態から非ビンゴの場合は 
4通り 
よって 
Q5=P4×15/(6+15)×1/(1+4) 
っつー等式ぐらいしか思い浮かばん。 

218 ：200：2005/09/08(木) 01:07:09 
>>215 
そう、単純にすべての盤面を並べただけ 
だから言うとおり5手までは単純な掛け算で算出可能さ 
まとめると総盤面数はだいぶ減るけど、計算式を出すのが 
その分大変になるんよ 

219 ：名無しさん＠５周年：2005/09/08(木) 01:23:07 
あまちごーた 
誤　P6=9C6-Q5×4 
正 P6=9×8×7×6×5×4-Q5×4 
因みに 
9!=Q5×4!+Q6×3!+Q7×2!+Q8+Q9 
も成り立つよね。 

223 ：名無しさん＠５周年：2005/10/04(火) 23:28:12 
ひさしぶりにきたらだいぶ止まってるな。 
>>217 >>219 
>>213の式の解説だよね? 
>>213の式とすこし違うな。