○×問題


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

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

○×ゲームの数式表現は思った以上難しく、時間ばかりが過ぎていく。
苦戦の末、>>438の知り合いが答えの書いてあるページを発見し、問題は落着する。
足カックン的な空気が流れたが、
この話題の一番大切なことは
そこから何かを学び、オセロゲームの棋譜数の数式表現へ繋げることである。

英語で書かれていますが、解析結果を書いている参考ページ
How many Tic-Tac-Toe games are possible?
日本語訳○×ゲームの計算解析

親話題→数式で表現



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

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

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

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

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

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

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

204 :名無しさん@3周年: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 
一緒になりますたw乙! 

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

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

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

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

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

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

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

217 :名無しさん@5周年:2005/09/08(木) 00:54:38 
nターン目で勝負がきまった曲面数をQnとすると 
P6=9C6-Q5×4 
;Cは場合の数の時につかうアレね。 
またQ5の話で、 
○を先手とした時に4ターン目で○がリーチになる通りは 
○を固定したとき○が2つある次元に×がない場合だから 
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 :名無しさん@5周年: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 :名無しさん@5周年:2005/10/04(火) 23:28:12 
ひさしぶりにきたらだいぶ止まってるな。 
>>217 >>219 
>>213の式の解説だよね? 
>>213の式とすこし違うな。 

427 名無しさん@5周年 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箇所のどこにおいてもOK 
逆時間(×先攻)で×が5手でビンゴする局面数はS5個 
T6=T5 * 3 
上と同様の数え方だが、残りの○をおく位置の候補4箇所のうちすでに○が2つ並んでいるラインにおくと、 
順時間では○が先にビンゴしてしまうのでそれ以外の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 名無しさん@5周年 sage New! 2006/03/25(土) 10:37:24 
>>427 
S6=S5 * 4 までは理解したけれど、T6=T5 * 3 の反例です。 
>すでに○が2つ並んでいるラインにおくと、○が先にビンゴしてしまうのでそれ以外の3箇所におかなくてはならない 
ですが、○が2個並んでいない場合は4箇所全て可能なので、単純に4-1とは出来ない。 
↓ 初手を除いた盤面の例 
○++ 
××× 
+○+

××× 
○++ 
+○+

など、この例では初手の○が空き4ヶ所のどこにあっても5手目でビンゴしない 

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 
少し前の○×ゲームの手数を数式で表現できないかと 
考えて8手目まで求めることができて喜んでいたら、 
知り合いがこんなページあるよーって、、、、、

それはwikipediaの英語版tic-tac-toeの外部リンクの最後でした。

http://www.btinternet.com/~se16/hgb/tictactoe.htm 

俺の昨日数時間は何だったんだ.....orz 

取り合えず検証する気は起きないのでだれかよろしくお願いします。 
ぱっと見、正しい感じです。 
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。