オセロの対局パターンって何通りあるの？

おせーろ

出落ち

落ちてもない

（６４−４）！　よりは少ないんじゃない？？

そうだな
全オセロ競技人口をn人としたら
n(n-1)/2通りかな

中島　対　松嶋
１通り

king氏ねスレにすんなよ
終わり

　　　　　　　　　　　　/ 　ヽ　 　　　 / 　ヽ
　　＿＿＿＿＿＿ / 　 　 ヽ＿＿/　 　 　ヽ
　　|　＿＿＿＿　／　　　 　 　 　　　:::::::::::::::＼
　　| |　　　　　　 /／　　　　　　　＼　　:::::::::::::::|　　　>>7　えー終わりなのにしたらだめなの…
　　| |King市ね |　 ●　　　 　　● 　　 ::::::::::::::| 　　　じゃここは数板1番人気の
　　| |　　　　　　.|　　　　　　　　　　　　　:::::::::::::|　　　　King市ねスレにしよっと
　　| |　　　　　　 |　 　（__人__丿 　.....:::::::::::::::::::/
　　| |＿＿＿＿　ヽ　　　　　　.....:::::::::::::::::::::::<
　 └＿＿＿／￣￣　　　　　　　:::::::::::::::::::::::::|
　　|＼　　　 |　　　　　　　　　　　　:::::::::::::::::::::::|
　　＼ ＼　　＼＿＿＿　　　　　　 ::::::::::::::::::::::::|

Reply:>>7-8 何をしている。

盤面なら(2^4)*(3^60)よりは少ない

8x8だと難しいから2x3で考えてみたぜ

　Ｄ Ｅ
４○●
５●○
６＋＋

　Ｄ Ｅ
４○●
５●●
６＋★

　Ｄ Ｅ
４○●
５○●
６☆●


対局パターン・・１通り
盤面パターン・・３通り

そうか、対局パターンは、局面の数という意味ではなかったのか。混乱してた。

オセロの場合、一般には「パス」があるので、
盤面パターン＝局面の数とは言えないようだな。

パスは任意じゃない（完全に着手不可能でなければパスはできない）ので
そんなことはないんじゃないか？

対局パターン数はいわゆるゲームの枝の数と思う。
盤面数はゲームの中で理論上実現し得る盤面の数。

＞＞1
“おせーろ”　ちゅー洒落を言いたかったのだ。 ねっ

数式で計算できるような類の問題じゃないよね。
○以上△未満みたいな範囲を調べるくらいならちょっとやれば出来るけど。

>>13
パスをしたあと、
盤面に偶数個→次は黒
盤面に奇数個→次は白
の規則が崩れるから、
双方が次置けるような盤面において、
それ以前にパスがあって偶奇が反転しているかどうかが判断できない、ということ。

組み合わせ論で有名な難問だな

>>17
パスが無くたって同じ盤面に同じ手順で到達するとは限らないんだからさあ

無知ですいません。
この分野では、
すでにコンピュータに負けているんじゃないんですか？
違うの？

何年も前にプログラムがオセロのチャンピオンに勝って以来、
コンピュータは人間よりはるかに強くなってしまった。
でも対局パターン数を求める話とは無関係なのでは？

じゃあこうしよう、
実際にコンピュータであり得る全ての手を再現してみて数え上げる。

6×6ならもう済んでいる

じゃあその調子で8×8も数えよう。

さっきじいちゃんと一緒に数えたけど、ここに書くには空きが狭すぎる

オセロの試合結果は全部で何通りか
http://science6.2ch.net/test/read.cgi/sim/1090548999/

将棋だとどうなる？

将棋は無限に長く続くことがあり得るんじゃないかな

>>19
パスがなければ、途中経過が違っても考慮すべき局面としては区別する必要はないだろう。

>>29
局面数をゲームの枝の数と解釈するなら区別が必要。局面=盤面と解釈するなら区別しない。

>>27

■■■囲碁・将棋と数学■■■

http://orz.2ch.io/p/-/science6.2ch.net/math/1053038715/

http://science6.2ch.net/test/read.cgi/math/1053038715/

>>28
ルール上有り得ない

なるほど。千日手って「同一局面4回」だったのか。
とすれば将棋の対局パターンも有限だね。
だとしても将棋の場合「入玉」のルールが曖昧だから数学モデルとして適当じゃないと思うけど。
その点オセロは白黒ハッキリしてるからね。

オセロではコンピューターが人間を圧倒

アタック２５の盤面パターンは何通りあるか？

>34
最終的にはすべてのパネルが埋まるから、
赤、緑、青、白の２５枚ぶん ＝ 4＾25 ≒ 1000兆通り

>>30
もちろん、ちゃんと定義しないといかんが、
普通「局面」と言えば、過去の経緯を全てひきずるのではなく、
未来に影響を与える要因のみで区別するだろう。
オセロだと、同じ盤面でなおかつ次に打つのが同じ人なら同じ局面
同じ盤面でも次に打つのが白と黒では違う局面。
過去の経緯は関係ないが、パスのルールの存在により盤面と局面が
１対１対応にはならないというそれだけの話。

将棋とかだと、千日手の存在により、盤面と手番だけでなく、
過去の経緯もひきずることになる。したがって、将棋では局面の数と枝の数は
同一視される。

>>36
その定義なら将棋は

局面数≠ゲームの枝

だな

>>35
空きもありうるから

ところで6×6オセロのゲームの枝数と局面数が書いてあるHPとか誰か知らない？

シミュレート板のオセロスレはwikiあるけど6x6は出てないね
８ｘ８オセロは15手で1000億超えてるから
６ｘ６オセロにしても全部では相当な局面数になってると思う

一応6×6は完全に解析済みだから枝は最低でもわかってる事になるんだけどね。

>>35
おめー
アタックチャンス忘れてんだろ

アタック25のルールは、最初は真ん中指定なので4通り
次は（離れ小島にはパネル選べないので）8個×4色の32通り
その後は、形が変わると周辺部のパネル数も変化していくので
複雑な場合分けが必要

アタック25はオセロと違って最後25マス全部埋まるんじゃ無かった？
途中の枝はかなり複雑だけど、最終盤面数は4^25かなと。
もしかしたら「アタックチャンスを考慮してもあり得ない最終盤面」があるかもだが。

時間切れで埋んないことは度々あるよ

>>44
baka

>>44
最終盤面数なんぞと対局パターンに
なんの関係があるんだ？
んなもん頗るトリビアルだろｗ

（１）ランダムに手を選ぶ対局プログラムを用意する。
（２）n手目における可能手の個数を記録してX_nとおく。
（３）m手で終局したとして、X_1からX_mまでの積を計算し、Yとする。
（４）（１）から（３）をくりかえしてYの値を何度も求める。
（５）このとき、Yの平均値は実際の分岐の個数に収束する。

なるほどー　いい感じに近似できそうだねそれなら

ただし、例えば1手目の黒のあと、白は3通り。
「完全なランダム」なら2手目の白はそれぞれ３分の１の確率で選択されるだろうけど、
実際の枝の”重み”は多分3通りそれぞれの先で手数の違いがあるだろうから
多少の誤差はあるかもね。
でもその誤差を考慮してもかなり近い手数になるかもね。

数陣タイセン＆ポケモンバトルは有限手以内に終わる

ただ運が絡むからゲームの木はひどいことになる

数陣タイセン
　（（（72通り？のタイルの置き方）＋（アイテム13種×そのあとのタイルの置き方）×配置制限を考慮した上で今置けるマス数）^全マス数^参加人数^置く順番？）÷マスが全部埋まる前に目標点数達成の確率÷１回の順番に選べる手札＆アイテムは５通りずつ
＝100桁よりかなり大きい？÷途中決着の確率？÷30？

ポケモンバトル
ポケモン１体だけで
　ポケモンの種類493体×個体値が32^6×努力値×技４個の組み合わせ×持ち物
＝40桁以上？
さらにフルバトル（シングル）
　（ポケモン１体のとる可能性）^6（6体の選び方で同じポケモンや道具がかぶってもよい）^2（相手も）^（ターン数^16）
＝100桁以上？

PS 私の関数電卓は100桁越えは無料ですOTL

↑
×無料
○無理

数陣ってなんだよ？ポケモンてことはゲームか？
そんな一般的じゃないもの出されても誰も付いて来れないだろ

>>50
ヒント：100桁越えが無理ならlogでやってみよう

4x4オセロは何通りでどっちが勝つの？

>>54
4x4オセロの結果
ply--maxmob--kifu--pass--gameover--bw-----ww----draw
00-----4-------4------0------0------0------0------0
01-----3------12------0------0------0------0------0
02-----4------44------0------0------0------0------0
03-----5-----128------0------0------0------0------0
04-----5-----436------4------0------0------0------0
05-----5----1296------8------0------0------0------0
06-----6----3784-----40------4------4------0------0
07-----5----9756----144------8------0------8------0
08-----4---22152----828-----20-----20------0------0
09-----3---41296---2892----308----160----148------0
10-----2---58912--10732----808----440----356-----12
11-----1---53580--25252---5332---3260---2072------0
12------------------------------20748--27532---5300

>>54
4x4オセロをプログラムでシミュレートしてみたけど、お互いベストな手を尽くせば白が勝つみたい。
盤面パターンはたぶん>55の通り。

4×4と6×6は双方最善で白二石勝ちだったと思う

>>1の書込みを見て欲しい。
なんとつまらない書込みだろうか。
義務教育を終えていない小学生であったとしても
多少のヒネリを加えて書き込む事は容易いはずである。
しかしこの書込み内容からはその形跡は微塵も感じられない。

彼の脳に重大な障害が発生している事は誰の目にも明らかだろう。
恐らく彼は経済的な事情で十分な治療を受ける事が困難な状況に陥っているに違いない。
この一見無意味としか思えない彼の書込みは、
現在の医療システムの見直しを訴えたメッセージなのではなかろうか。

オセロは中嶋の方が好きだな

プログラム作って6x6オセロ全手数カウントに挑戦したけど、どうやら無理っぽいことがわかった。

32手目が50億通りになるまでうちのPCで3時間。
その時点でまだ15手目は6通りにしか進んでいない（6x6の15手目は最終的に800億以上ある）。
多分最終的な6x6の手数は8×10^22くらい。
6000万台のPCで1年間計算すれば全手数が出るくらいと思う。

6x6の全手数が未解明にもかかわらず6x6の「双方最善手」がわかってるってことは、
「明らかな悪手」をカットしてくことが相当の計算節約になってるってことなんだろうな。

全探索してないのに最善手というのはおかしいんじゃないか？

>>60
4*4を辺と辺を繋げてトーラスにするとどうなる？

対象性がなんとかかんとかって言ってるけど
4x4でやるんじゃなくて
1x16の横一辺の升目(1~16)にして、最初の状態を6白、7黒、10白、11黒と見て、
どこに何がくればどうなる、っていうそれぞれの升目の法則性を見つけ出す方法でやれば解決すると思う。

>>62
どうなるというのは？
4x4で左右同士と上下同士がつながってるとして、
その法則の盤面で手数をカウントするってこと？
いまいち意図がわからなかった。
>>63
プログラムの効率化のこと？
升目の管理はメモリアクセス量を減らして出来るだけレジスタでやらせるために、
2次元配列じゃなくてすべてビット演算でやってるよ。

すげえｗ
よければコード晒して

　Ｃ Ｄ Ｅ Ｆ
２┌┬┬┐
３├┼┼┤
４├○●┤
５├●○┤
６├┼┼┤
７└┴┴┘
なんとなく4x6オセロをカウントしてみた。
参考までに。
**＿＿*****初手F5 *****初手E6 **(F5+E6)x2
*1手目**********1 **********1 **********4
*2手目**********3 **********3 *********12
*3手目*********13 *********12 *********50
*4手目*********42 *********48 ********180
*5手目********194 ********209 ********806
*6手目********723 ********954 *******3354
*7手目*******3413 *******4377 ******15580
*8手目******13940 ******20754 ******69388
*9手目******65061 ******95783 *****321688
10手目*****271855 *****440053 ****1423816
11手目****1201138 ****1964644 ****6331564
12手目****4815734 ****8346692 ***26324852
13手目***19216871 ***33988824 **106411390
14手目***68718362 **125867426 **389171576
15手目**230791874 **431202936 *1323989620
16手目**669261695 *1278860905 *3896245200
17手目*1695966078 *3281058230 *9954048616
18手目*3442587144 *6752417334 20390008956
19手目*5297094661 10463298113 31520785548
20手目*4982581809 *9939224253 29843612124

>>65
縦横の数と探索の深さを変えられるようにしたバージョン。
http://2nd.geocities.jp/suret9876/ot/oth.cpp
結果ファイルは c:\ocount.txt に出力。0x1000000手カウントするごとに途中経過が書かれる。
実行ファイルの引数に例えば F5D6C4 などと手順を文字列で渡すと、続きの4手目以降をカウントします。
c++よりcでコンパイルした方がちょっと早かったのですべてc関数になってます。

>>67
おつー
囲碁も小さい盤面なら計算できるのかな？
それとも囲碁は終局の判定が難しいんだっけ？

小さい盤面だと終局の判定自体が楽になる。
（自陣の目をつぶしてしまうか、あいてに囲まれているかの
どちらかで、置けない場所がほとんどになるから）

で結局アタック25のパターン数は？

732

先手必勝かな？

いや後手でしょう

age

>>61
おかしくないよ
枝刈り（カット）には後ろ向き枝刈りと前向き枝刈りというのがあって
後ろ向き枝刈りは最善手の証明に影響がない
影響があるのは前向き枝刈りの方

281