「○×問題」の編集履歴（バックアップ）一覧に戻る
○×問題 - (2006/03/15 (水) 13:41:13) のソース
*○×問題
○×ゲームの棋譜数を数式で表現する試み
[[棋譜数をカウント>棋譜数のカウント]]するには、棋譜数の多さから
超天文学的に時間がかかる。
次に棋譜数を数式で表現できないかという発想が出てくるが、
これもなかなか難しい。
そこで、オセロゲームよりも数式表現が簡単そうな
○×ゲームを扱うのだが、、、
これもまだ解かれていない
親話題→[[数式で表現]]
----
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の式とすこし違うな。
