「○×問題」の編集履歴（バックアップ）一覧はこちら
「○×問題」(2009/08/20 (木) 00:00:58) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*○×問題
○×ゲームの棋譜数を数式で表現する試み
[[棋譜数をカウント>棋譜数のカウント]]するには、棋譜数の多さから
超天文学的に時間がかかる。
次に棋譜数を数式で表現できないかという発想が出てくるが、
これもなかなか難しい。
そこで、オセロゲームよりも数式表現が簡単そうな
○×ゲームを扱った。
○×ゲームの数式表現は思った以上難しく、時間ばかりが過ぎていく。
苦戦の末、>>438の知り合いが答えの書いてあるページを発見し、問題は落着する。
足カックン的な空気が流れたが、
この話題の一番大切なことは
そこから何かを学び、オセロゲームの棋譜数の数式表現へ繋げることである。
英語で書かれていますが、解析結果を書いている参考ページ
[[How many Tic-Tac-Toe games are possible?>http://www.btinternet.com/~se16/hgb/tictactoe.htm]]
日本語訳[[○×ゲームの計算解析]]
親話題→[[数式で表現]]
----
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とは出来ない。
↓ 初手を除いた盤面の例
○＋＋
×××
＋○＋
×××
○＋＋
＋○＋
など、この例では初手の○が空き４ヶ所のどこにあっても５手目でビンゴしない
437 427 sage 2006/03/27(月) 00:34:23
>>428
がーん。そうですね。
もうちっと精進します。
代案
Tn、Snの定義を変えて、
Tn:×縦横ビンゴ、○は×と平行にリーチ
Sn:それ以外
とすれば続きの議論につながるけど、複雑だなー。
とりあえず、「Q6はQ5だけで表現可能か」を知るためには、
Tn と Sn の関係が必要。
まあ、オセロだと時間に対して可逆じゃなさそうなので、この手は使えないかも
438 409 (=200) sage 2006/03/27(月) 16:17:55
少し前の○×ゲームの手数を数式で表現できないかと
考えて８手目まで求めることができて喜んでいたら、
知り合いがこんなページあるよーって、、、、、
それはwikipediaの英語版tic-tac-toeの外部リンクの最後でした。
http://www.btinternet.com/~se16/hgb/tictactoe.htm
俺の昨日数時間は何だったんだ.....orz
取り合えず検証する気は起きないのでだれかよろしくお願いします。
ぱっと見、正しい感じです。
○×ゲームの棋譜数を数式で表現する試み
[[棋譜数をカウント>棋譜数のカウント]]するには、棋譜数の多さから
超天文学的に時間がかかる。
次に棋譜数を数式で表現できないかという発想が出てくるが、
これもなかなか難しい。
そこで、オセロゲームよりも数式表現が簡単そうな
○×ゲームを扱った。
○×ゲームの数式表現は思った以上難しく、時間ばかりが過ぎていく。
苦戦の末、>>438の知り合いが答えの書いてあるページを発見し、問題は落着する。
足カックン的な空気が流れたが、
この話題の一番大切なことは
そこから何かを学び、オセロゲームの棋譜数の数式表現へ繋げることである。
英語で書かれていますが、解析結果を書いている参考ページ
[[How many Tic-Tac-Toe games are possible?>http://www.btinternet.com/~se16/hgb/tictactoe.htm]]
日本語訳[[○×ゲームの計算解析]]
親話題→[[数式で表現]]
----
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とは出来ない。
↓ 初手を除いた盤面の例
○＋＋
×××
＋○＋
×××
○＋＋
＋○＋
など、この例では初手の○が空き４ヶ所のどこにあっても５手目でビンゴしない
437 427 sage 2006/03/27(月) 00:34:23
>>428
がーん。そうですね。
もうちっと精進します。
代案
Tn、Snの定義を変えて、
Tn:×縦横ビンゴ、○は×と平行にリーチ
Sn:それ以外
とすれば続きの議論につながるけど、複雑だなー。
とりあえず、「Q6はQ5だけで表現可能か」を知るためには、
Tn と Sn の関係が必要。
まあ、オセロだと時間に対して可逆じゃなさそうなので、この手は使えないかも
438 409 (=200) sage 2006/03/27(月) 16:17:55
少し前の○×ゲームの手数を数式で表現できないかと
考えて８手目まで求めることができて喜んでいたら、
知り合いがこんなページあるよーって、、、、、
それはwikipediaの英語版tic-tac-toeの外部リンクの最後でした。
http://www.btinternet.com/~se16/hgb/tictactoe.htm
俺の昨日数時間は何だったんだ.....orz
取り合えず検証する気は起きないのでだれかよろしくお願いします。
ぱっと見、正しい感じです。
