*○×問題 ○×ゲームの棋譜数を数式で表現する試み [[棋譜数をカウント>棋譜数のカウント]]するには、棋譜数の多さから 超天文学的に時間がかかる。 次に棋譜数を数式で表現できないかという発想が出てくるが、 これもなかなか難しい。 そこで、オセロゲームよりも数式表現が簡単そうな ○×ゲームを扱うのだが、、、 これもまだ解かれていない 親話題→[[数式で表現]] ---- 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の式とすこし違うな。 427 名無しさん＠５周年 sage New! 2006/03/25(土) 00:25:20 よんけた氏 Wikiを拝見させてもらっています。 ○×問題の考察を書きます。 Q5:5手目に決着がつく（○の勝利）局面数 Q6:6手目に決着がつく（×の勝利）局面数 を次のように分解します。 Q5=S5+T5、Q6=S6+T6 Sn:斜めでビンゴ Tn:縦または横でビンゴ S6=S5 * 4 なぜならば、×が斜めでビンゴしてなくてはならない。 時間を逆にして考えると×先行で5手決着のケースに残りの○（順時間では初手）を ○がビンゴしないようにおく必要があるが、×が斜めで揃っているので空いている4箇所のどこにおいてもＯＫ 逆時間（×先攻）で×が5手でビンゴする局面数はS5個 T6=T5 * 3 上と同様の数え方だが、残りの○をおく位置の候補4箇所のうちすでに○が２つ並んでいるラインにおくと、 順時間では○が先にビンゴしてしまうのでそれ以外の3箇所におかなくてはならない。 同様にして Q8=S8+T8, S8=2 * S7, T8=2 *T7, ---> Q8=2*Q7 従って、(Q4=Q3=Q2=Q1=Q0=0に注意） 9!=4! * Q5 + 3! * Q6 + 2! * Q7 + 1! * Q8 + 0! * Q9 = 7*(3!)*S5 + 2* (4!) *T5 + 4 * Q7 + Q9 = 42 * Q5 + 6 * T5 + 4 *Q7 + Q9 が成立する。（本当？） T5 の評価が面倒なのと、T7,S7を T6,S6 などで表現するうまい方法が見つからない。 なんでQ5を使わずにT5,S5を導入したのかというと、Q6の表現で困ったから。 428 名無しさん＠５周年 sage New! 2006/03/25(土) 10:37:24 >>427 S6=S5 * 4 までは理解したけれど、T6=T5 * 3 の反例です。 ＞すでに○が２つ並んでいるラインにおくと、○が先にビンゴしてしまうのでそれ以外の3箇所におかなくてはならない ですが、○が２個並んでいない場合は4箇所全て可能なので、単純に4-1とは出来ない。 ↓ 初手を除いた盤面の例 ○＋＋ ××× ＋○＋ ××× ○＋＋ ＋○＋ など、この例では初手の○が空き４ヶ所のどこにあっても５手目でビンゴしない
下から選んでください:
