オセロの試合結果は全部で何通りか

白黒それぞれが先攻の場合を合計して
何通りあるのだろうか。

親不孝通り

6*6=36
2の36乗=68719476736
68719476736＊２(黒白)=137438953472

∴137438953472通り


かな？

訂正)
8*8=64
2の64乗=18446744073709551616
18446744073709551616＊２=36893488147419103232

∴36893488147419103232通り

>>4
話はそう簡単じゃない。
まず、打てる場所は8*8-4=60だし（最初の4個はゲームの前から置かれている）、
最初から隅に打てるわけではないので、盤を回転させていいなら最初の1手目は
一通りしかない。

ひゃくおくまん

>>5
意外に少なくて済みそうだな。最初の１手目は２通りだろ？盤には
裏表が存在するんだから。

たかだか６０回の再帰呼び出しならなんとかなりそうな気がしてしまう

>>5
試合の経過を考えるとそうだけど、ここで考えているのは試合結果なので
4の考え方でも良いような気がする。
ただ、5の言うルールとかから推測されるあり得ない試合結果を排除したり
とか、ゲーム途中でパーフェクトになるパターンとかも考えなくてはなら
ないので、実は場合分けは結構難しいと思われ。

そうすると8の言うように60回の再帰呼び出しが一番効率良いアルゴリズム
というのに漏れも一票。

1手目は1通り、2手目は3通り、3手目は14通り、4手目は・・・もうだめ。

ランダムに打ったとき、手数ごとの「打てる場所」の積が、
「全部で何通りか」の近似値になると仮定すると、
だいたい10の45乗から10の55乗の範囲になるようです。
正確に出すのは不可能に近い。白と黒どちらが先手かは関係ない。

あっ、でも4の結果より小さくなければいけないのだから、おかしいな。
俺はアホか。

試合の結果は３通りです。
黒から見た場合、勝 負け 引き分け の３通り。
駒の数から考えると、６４対０から始まり、０対６４まで ６４通り？
ここでは盤面がいくつあるかは問うてる、様なので自分には計算できません。
申し訳無い。さらばです。

?

横スレ悪いのだが、オセロの全検索は為されていなかったと記憶にあります。
３の36893488147419103232通りより少ないと考えただけでも、
さほど大きな数では無いと思われるのだが。
どなたかご説明して頂けませんか？

試合結果だけなら少ないけど、結果に至るプロセスはそれよりも遥かに多い。
それに、何通りか判断するにはカウントしなければわからない。
1秒間に1000通り検索できるコンピュータがあったとしても、1年間かけて300億通りしか
カウントできないので>>4の結果を確認することさえできないのでは。

もし、どこにでも置けるとしたならば、
(8*8-4)!通りなのだから、これ以下なのは間違いない。

おける場所の検索の式が難しいんだよね。
必ず、他の色をはさむように置かないといけないし…
割と少ないとは思うんだけど…

http://science3.2ch.net/test/read.cgi/sim/1022681095/l50

>>19
そっちのスレの趣旨が違ってきてるから良いんじゃないの。

hosyu

試合が終わったとき64マス全部埋まるとは限らないが・・・
そのへんはどうよ

「打てる手が何通りあるか」ではなく、
「最後の盤面が何通りあるか」ということでしょ？
盤面全体に白か黒が埋まっているはずだけど
(それぞれのマスに白か黒かどちらがあるかを考えれば最大2^(8*8)通り？)、
そのうちありえない場合があるのかどうかをかんがえると
どうだろうか？

>>23
だーかーらー

＞「最後の盤面が何通りあるか」ということでしょ？
＞盤面全体に白か黒が埋まっているはずだけど

６４ます埋まる前に白か黒がパーフェクトして
埋まらないパターンもありうるんだよ。
それを考えると難しいだろ？

TAXAN

>>1
>白黒それぞれが先攻の場合を合計して

オセロは黒が先手と決まっています。

まずオセロのルールを勉強汁
ttp://www.othello.org/nakaji/lesson/lesson/rulej.html

おれはインターネットリバーシじゃないとあまり強くない。
図形として頭に入ってるらしく　緑色の板ではどうにもならん・・・・・・・

勝ち、負け、引き分け
3通り

勝ち、負け、引き分け、途中でぐちゃぐちゃにしてやる
４通り

オセロの黒い方が先にナンパされる青山通り

いっぱい

みなさん。これを見てください。
http://storm.prohosting.com/tprv/huse.exe
(リンク後もう一回、
http://storm.prohosting.com/tprv/huse.exe
をクリックしなければいけません。)

皆さんはどう思いますか？

貴方もオセロを
　　　　　　　　　　　　　　や　ら　な　い　か

わたしはまいこちゃん
こまったまいこちゃん
わたしはくびつりまいこちゃん
あなたのせなか　おににふす
くろくにくさって　ちだらけよ
いおりあと　うしろをむかないで

┏━━━━━━━━━━━━━━━━━┓　　 　 ＿ 　
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃ ,.^〈〉'´ 　ヽ〈〉ヽ.
┃│●│●│●│●│●│●│★│ 　│┃( （〈〉.ﾉ从）)〈〉） ）
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃ ） ）(li.ﾟ ヮﾟﾉ! （ (　
┃│○│○│○│●│●│●│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃いくみん　●　３１
┃│●│○│●│○│●│○│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│●│●│○│○│○│○│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│●│●│●│○│○│○│ 　│ 　│┃　_＿__
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃ / 　　 `ミ
┃│●│○│●│●│○│○│ 　│ 　│┃i´ 从从ミ
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃` ﾘ;ﾟ -ﾟﾉ 　
┃│●│●│○│●│●│○│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃ Ｕ - １　○　１８
┃│●│●│●│●│●│●│ 　│ 　│┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛

>>23 >>24
さらに言えば、ありえない形もありうる。
たとえ白黒すべてが盤面にあっても、その形で終わることは絶対にありえない形があるかもしれない。
やはり、最終形のみを考えて通り数を出すより、１手目から順に計算すべきだと思う。

現実にまだ必勝法が見つかっていないくらいだから、
可能な盤面の数・最終盤面の形とかを厳密に確定するのは
まだまだ先のことだろうな。

60! ≒ 8.32 x 10^81よりも少ないことは、素人考えでも分かるが、
そこから更に絞るとなると...
第5手目は一通りだから 1*59! ≒ 1.37 x 10^80以下
第6手目は三通りだから 3*58! ≒ 7.05 x 10^78以下
第7手目は縦取りだと5通り　斜め取りだと4通り　並び取りだと5通り
よって14*57! = 5.67*10^77以下
もう飽きた...

珠型ルールと禁じ手のない15x15五目並べの必勝法を確立した
ヴィクター=アリスという人の博士論文によると
オセロには可能な盤面の数が10^58通りあるそうな。
ttp://www.cs.vu.nl/~victor/thesis.html

保守

円周率は決して正確に求めることはできないが、
何桁まで求めたかで一つの成果として認められている。

オセロならば「最高でも何通り以下になる」というのが
一つの指標になる予感。

39の前提で最大の答えを上げておく。

「64マスにおいて、黒or白or無地であるので

　　　　　　　　3^64通り以下である。　　　　　　　　　　　」

>>40
おいおい>>37の博士論文より大分少ないじゃないか。

>>41
>>37の論文での10＾58通りというのは可能な盤面の数だ。
>>40とは別のもの

オセロないけどおもしろいよ。
http://www2.ic-net.or.jp/~takaken/auto/guest/index.html

>>42
オセロ譜ってこと？同じ盤面に複数の到達ルートがある場合を考えて。

盤面だったらあくまで>>40の個数以下しかないと思うんだけど。

結局、試してみるのが早そうだ。
じゃあ俺から

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋●○＋＋＋
＋＋＋●●＋＋＋
＋＋＋●＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
次○

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋●○＋＋＋
＋＋＋●●＋＋＋
＋＋＋●＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋○<ﾜﾚﾜﾚﾊﾄﾞｸﾘﾂｦｾﾝｹﾞﾝｽﾙ!!
次●

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ 　　　　　●　＜２Ｄオセロは時代遅れ。これからは４Ｄだ。
＋＋＋●○＋＋＋
＋＋＋●●＋＋＋
＋＋＋●＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋○
次○









ﾓｳﾔﾒﾖｳﾖ

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋角＜異種格闘試合ってのはどうだい？
＋＋＋＋＋＋＋＋ 　　　　　●
＋＋＋●○＋＋＋
＋＋＋●●＋＋＋
＋＋＋●＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋○
次�j

>>40-42

>>37のサイトの文章によると、オセロは、

state space complexityが、3^64 ≒ 10^30
game-tree complexityが、10^58

と書いており、正に>>40が示した通りのことが書かれている。

「可能な盤面の数」という言葉が適切かどうかは知らないが。

ホッシュ

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋角
＋＋＋＋＋＋＋＋ 　　　　　●
＋＋＋●○＋＋＋
＋＋＋●●＋＋＋
＋＋＋●＋＋＋＋ 朝＜一手だけなら誤手かもしれない
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋○
次◎

ほっしゅ

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ 　　　持ち駒● ●
＋＋＋●○＋＋＋
＋＋＋●馬＋＋＋ ＜ｶｰﾁｬﾝｵﾗ昇進ｼﾀﾀﾞ！
＋＋＋●＋＋＋＋ 朝
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋○
次葱

ほっしゅ

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ 　　　持ち駒● ●
＋＋＋●○＋＋＋
＋＋＋●馬＋＋＋
＋＋＋●＋＋＋＋ 朝
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋●＜明日は雨でしょう。
次でボケて！

ぼっしゅ

めりーくりすます

もう年の瀬ですが、保守

あけおめ

4x4オセロ
6x6オセロ
あたりならできそう？

まぁ、60!以下だ

QNYqzJfs
　　　　　　　　　　　　　　　　　＿　 ＿
　　　　　　　　　　　　　　ｒ〜ｆ⌒ｉ　 しj__ ﾄ√¨ﾄー､
　　　　　　　　　　　 _ 厂ﾉ,.．-ｰｔ´¨ｉ´:::::|⌒ｉ;¬…tｸ-、
　　　　　　　　　　r〈 ,>ｲ:::|:::::|:::::|:::::|:::::::|::::::|::::::|:::::ｉ¬ん、
　　　　　　　　　　>/l::::|:::⊥亠¬冖⌒ ｉ冖ﾊ¬ﾄ､,|::::|:::ヽ〉､
　　　　　　　　　 {ｼ,.:!ｰ'' ｒ´/(⌒て_厂¬ｒ⌒ﾋ_ト､ゝ､ｉ_::|:||:i:}
　　　　　　　　　∠/ｒｰtﾉ⌒ｰ’....................../.ﾄ､ﾞｉ　ゝr-、|:||:;ﾄ、
　　　　　　　　　ｿー' ｉ.............................../...〃.j＼ｉ........... しﾍ::|（
　　　　　　　　　{　......|............./..　　　/..// /　　V.........　しうノ
　　　　　　　　　 l　.....ｌ.|　　/...　　／／ //─ -　､..........}Σﾄ､ヽ、　 ちゅぱちゅぱ美味しい
　　　　　　　　　 ﾞｉ　　ｉ|　../　_≦.／　　　＝ｰ- ､|..　..　|⌒）　＼ヽ
　　　　　　　　　　ﾞｉ.....::ﾞi../,r):::;:d　　　　　|ﾄﾞく;;d |...........|.:::} ｌ 　　ヽﾞi
　　　　　　　　　 /∧　...}〈ﾍ{qﾄｊ｣　　　　 └-''､⊥!........レ´ ﾞi.ｉ　　ｉ‖
　　　　　　　　　// ∧...::ﾄヽ￣　　　､　　　　　　ｊ!.........,il'　　ゝｉ　　||
　　　　　　　　 〃〃　ｉ..::ト-ヽ、　　　ｒｉ、　　　ｨ´|.....　,'|　　　ヽｉ､
　　　　　　　　 《 《　　i、:|_　　 ｀ ｰ,- | ├＜´ ﾄ､|....../..|__,．-､ ||j 　　
　　　　　　　　　　　　　　　　　　　 ／⌒＼　　
　　　　　　　　　　　　　　　　　　　（　　　　)　
　　　　　　　　　　　　　　　　　　　｜　　 ｜ 　
　　　　　　　　　　　　　　　　　　　｜　　 ｜
　　　　　　　　　　　　　　　　　　　│ 　　│
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
このスレを見た人は、10年以内にかならず氏にます。
でも、逃れる方法はあります、
※10日以内に20箇所のスレにこれをはるのです。

3^(8*8)通りです

保守

>>63
もっと小さい。

喪主

単純な状態空間なら>>63より遥かに小さいのだが、
プランニングを考えるとなると打つ場所の履歴を保存しなきゃならんわけで、
その場合の数はめちゃくちゃに膨れ上がる。
オセロだと10^60通り程度、チェスだと10^120通り程度、
将棋だと10^220通り程度、囲碁だと10^360通り程度、
と、この手の研究をやってる人は言ってる。

ちなみに今のコンピュータではオセロでも完全解析は全然無理。
それでもオセロに関してはコンピュータは人間より遥かに強い。
チェスは、有名だと思うけど、
IBMがdeep blueっていうそれ専用のコンピュータを作ってようやくチャンピオンに勝った。
（但し、他の人には対応できないし、数回の対局の合間にプログラマが手を入れたりしていた。
短時間で完璧にアルゴリズムを弄る腕は素晴しいが・・・。）
将棋はやっとアマチュア5段に達するかどうかというところ。
囲碁は・・・だめぽ。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　 　∧＿∧　 ∧＿∧　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
ﾋﾟｭ.ｰ　（　 ・３・） (　　＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕 　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

...これからも僕を応援して下さいね（＾＾）。　　　
　　
━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―
　　　　　　　　　
　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。　　　　　　　　　　　　　　　　　　　　　　　　　
　　＝〔~∪￣￣〕　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　__∧＿∧_　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　|（　　＾＾ ）|　＜寝るぽ（＾＾）　　　　　　
　|＼⌒⌒⌒＼　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉　　　　　　　　　　　　　
　　 ~￣￣￣￣　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　 ∧＿∧　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　（　　＾＾ ）＜ ぬるぽ（＾＾）　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　 (⌒V⌒)　　　　　　　　　　　　　　　　　　　　
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。　　　
　　⊂|　　　　|つ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　 　∧＿∧　 ∧＿∧
ﾋﾟｭ.ｰ　（　 ・３・） (　　＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕　　　　　　　　　　　　　　　　　　　　　　　　　　
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ

hossshu

>>53
二歩だこのやろ！

やっと計算終わった。
８９４７５６９２４７８９３１２通りだったよ。ああ、つかれた

>>72
Ｚカレー

ところで、手計算ですか？
計算方法示してぷりーず

廃れてしもうた…

>>74
巡回はしてるんだけどねぇ・・・

どっちにしても人間じゃコンピュータオセロに勝てない時代になったわけでな

少なくとも、中央の４マスにコマが無いという局面と、
隣接するマスに他のコマが一つも無い（一個に限らず、
島状態でも同じ）という局面は除外できますね。

盤面に置かれている一つのコマに対して、
隣接したマスに新たにコマの置く場合、
置けるマスは７個所以下。

ゲームの開始状態（白黒２枚ずつ計４枚が配置された状態）から可能な盤面の状態を数え上げる計算はどれくらい時間かかるんだろう？

QNYqzJfs
　　　　　　　　　　　　　　　　　＿　 ＿
　　　　　　　　　　　　　　ｒ〜ｆ⌒ｉ　 しj__ ﾄ√¨ﾄー､
　　　　　　　　　　　 _ 厂ﾉ,.．-ｰｔ´¨ｉ´:::::|⌒ｉ;¬…tｸ-、
　　　　　　　　　　r〈 ,>ｲ:::|:::::|:::::|:::::|:::::::|::::::|::::::|:::::ｉ¬ん、
　　　　　　　　　　>/l::::|:::⊥亠¬冖⌒ ｉ冖ﾊ¬ﾄ､,|::::|:::ヽ〉､
　　　　　　　　　 {ｼ,.:!ｰ'' ｒ´/(⌒て_厂¬ｒ⌒ﾋ_ト､ゝ､ｉ_::|:||:i:}
　　　　　　　　　∠/ｒｰtﾉ⌒ｰ’....................../.ﾄ､ﾞｉ　ゝr-、|:||:;ﾄ、
　　　　　　　　　ｿー' ｉ.............................../...〃.j＼ｉ........... しﾍ::|（
　　　　　　　　　{　......|............./..　　　/..// /　　V.........　しうノ
　　　　　　　　　 l　.....ｌ.|　　/...　　／／ //─ -　､..........}Σﾄ､ヽ、　 ちゅぱちゅぱ美味しい
　　　　　　　　　 ﾞｉ　　ｉ|　../　_≦.／　　　＝ｰ- ､|..　..　|⌒）　＼ヽ
　　　　　　　　　　ﾞｉ.....::ﾞi../,r):::;:d　　　　　|ﾄﾞく;;d |...........|.:::} ｌ 　　ヽﾞi
　　　　　　　　　 /∧　...}〈ﾍ{qﾄｊ｣　　　　 └-''､⊥!........レ´ ﾞi.ｉ　　ｉ‖
　　　　　　　　　// ∧...::ﾄヽ￣　　　､　　　　　　ｊ!.........,il'　　ゝｉ　　||
　　　　　　　　 〃〃　ｉ..::ト-ヽ、　　　ｒｉ、　　　ｨ´|.....　,'|　　　ヽｉ､
　　　　　　　　 《 《　　i、:|_　　 ｀ ｰ,- | ├＜´ ﾄ､|....../..|__,．-､ ||j 　　
　　　　　　　　　　　　　　　　　　　 ／⌒＼　　
　　　　　　　　　　　　　　　　　　　（　　　　)　
　　　　　　　　　　　　　　　　　　　｜　　 ｜ 　
　　　　　　　　　　　　　　　　　　　｜　　 ｜
　　　　　　　　　　　　　　　　　　　│ 　　│
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
このスレを見た人は、10年以内にかならず氏にます。
でも、逃れる方法はあります、
※10日以内に20箇所のスレにこれをはるのです。

年号チェッ９

あがれぇぇぇぇ

>>13でこの議論は終わってるべ。
試合結果は

黒勝ち
白勝ち
引き分け

の３通りだろ。

60 ! = 8.32098711 × 10^81
2^64 = 1.84467441 × 10^19
3^64 = 3.43368382 × 10^30

>>83頭は大丈夫？

3通りでいいんじゃ？

>>86
　>>85

sage

経路積分

盤面は６４マスあるので２＾６４個の６４次元ベクトルの
可能な時系列展開をすべて数え上げればいいんじゃないの？

>>90それは、
チェスで人間に勝ったスパコン（ディープブルー）がやっていた方法で、
いわゆるブルドーザー方式とか言うやつだね。
パワープレイで計算するのも一つの方法かもしれないが、頭の悪いやり方だね。
よって、ゲームを効率的に考えるにはどうする？

sage

>>90
せめて初期配置の４マスを省くくらいは言ってもらわないと

>>91
代案も出さずに批判だけするのは頭の悪いやり方だね。

sage

勝つか負けるか

2通り

VIPにスタア錦野旦降臨中！記念カキコしる！
http://ex10.2ch.net/test/read.cgi/news4vip/1113134788/l50

俺はオナニーをした、別に楽しくもない。
俺は一ヶ月ほどオナニーをしていなかった。というよりオナニーをすること
を忘れていた。
俺は女には興味はない、もちろん男にもない。ただし仲間の前では女に
興味のあるふりはしている。
俺は一言で言うと病気なのだ。オナニーをまったくしないのは健康上
悪いらしい、それでしかたなくやっている。通常は２週間に一度くらいは
しているが、ときどき面倒になり、数ヶ月忘れたこともある。
まあ別に自分では困ったと思ったこともないし、これからもそうだろう。

>>93自己矛盾。

sage

>95
正解
流石95だ　他のものと考え方が違う

>>93
ププッ

>>97
ここで、人生相談するな！！！

sage

>>98
>>93では「代案を出せばよい」という解決策も提示している。
恥の上塗り乙。

１は「試合結果」じゃなく「可能な試合展開の数」が知りたいわけだよね？
試合結果なら勝ち負け引き分けの３通りしかないのは自明。
そんなこと聞きたいわけじゃないことぐらい余程馬鹿じゃない限りわかるよね？ｗ
＃　まぁ馬鹿も何匹か混じってるようですがｗ

>>93
初めの４マスを何で省くわけ？ｗ　ってかあんた素人？ｗｗｗ
この４マスは可変量だろが！単に６４次元ベクトルの初期値なだけだろ！
例えば、白を１、黒を−１、何もなしを０としてこれら３値をとる変数が
６４個集まったベクトルを考えることがまずは出発点になるわけね。
で、初期ベクトルから展開可能な次のベクトルが４つしかないことは自明。
この４つの分岐からさらにそれぞれ分岐させてたものをコンピュータか何かで
しらみつぶしに調べれば原理的には数えることはできます。
しらみつぶしと言ってもオセロ盤には対称性があるので実際には初期分岐のうち
１つだけ調べて４倍すれば良いわけだけど。
まずは６４次元でなくもっと小さい盤面、例えば４×４、６×６でやってみて
様子をみて８×８でやってみたら？

３通りじゃね？

>>105
なんか必死な奴がいるなｗ

>>105
もっともらしく書き並べてあるが内容は既出だな

3ge

すげーなおまえら！！
天才の集合体だ！
オレ数学とか本気でさっぱりだから言ってること
理解不能だが、おまえらのカッコよさを
びんびんに感じるぜ！
この板の言葉の羅列を理解できる人間が
いったいどれくらいいるんだろうか
大学院クラスだよな？サイテーでも

sage

GWage

今のパソコンなら終盤残り２０手なら完全読みできているんじゃあ？
昔のアスキーマイクロオセロリーグではZ80マシン語で終盤１２手
完全読みだったような記憶が。

序盤は膨大な定石データベース（初手から３０手以上）終盤は
２０カ所空きがある状態で完全読みされたらα−β法だの評価
関数だのを使うのは中盤の数手のみになって人間が勝てる見込み
はない。実際に世界チャンプでも完膚なきまでにやられている。

sage

あげ

ケータイ初！音声通話完全定額！

・旧DDIポケットのWILLCOMが月額2900円で、WILLCOM(エッジ)同士の通話が完全定額！
　しかも、2台目以降の基本料金は2200円！
　音質も固定電話並！北海道から沖縄にかけても無料！

プラン：定額プラン
通話：エッジ同士の通話が完全無料
Ｅメール：完全無料

http://www.willcom-inc.com/cp/teigaku/index.html

結局どうなんよ？

計算始めました。

死ぬまでに結果が出たらいいのだが。

>>118
まさかとは思うが全通り計算してるのか？

４×４
＋＋＋＋
＋●○＋
＋○●＋
＋＋＋＋

初手 1通り
＋＋＋＋
＋●○＋
＋●●＋
＋●＋＋

二手 3通り
＋＋＋＋　＋＋＋＋　＋＋＋＋
○○○＋　＋●○＋　＋●○＋
＋●●＋　＋○●＋　＋●○＋
＋●＋＋　○●＋＋　＋●○＋

三手 11通り
●＋＋＋　＋●＋＋　＋＋●＋　＋＋＋●　　＋＋＋＋　＋＋●＋　＋＋＋＋
○●○＋　○●○＋　○○●＋　○○●＋　　＋●○＋　＋●●＋　＋●●●
＋●●＋　＋●●＋　＋●●＋　＋●●＋　　●●●＋　＋○●＋　＋○●＋
＋●＋＋　＋●＋＋　＋●＋＋　＋●＋＋　　○●＋＋　○●＋＋　○●＋＋

＋＋＋●　＋＋＋＋　＋＋＋＋　＋＋＋＋
＋●●＋　＋●●●　＋●○＋　＋●○＋
＋●○＋　＋●●＋　＋●●●　＋●●＋
＋●○＋　＋●○＋　＋●○＋　＋●●●

四手　31通り
●＋＋＋　●＋＋＋　　＋●＋＋　＋●＋＋　　＋＋●＋　＋＋●＋　＋＋●＋
○●○＋　○●○＋　　○●○＋　○●○＋　　○○●＋　○○○○　○○●＋
＋○●＋　＋○○＋　　＋○●＋　＋○○＋　　＋○●＋　＋●●＋　＋●○＋
○●＋＋　＋●○＋　　○●＋＋　＋●○＋　　＋●○＋　＋●＋＋　＋●＋○

＋＋＋●　＋＋＋●　＋＋＋●　　　＋＋＋＋　　＋○●＋　＋＋●＋　＋＋●○　＋＋●＋
○○●＋　○○○○　○○●＋　　　○○○＋　　＋○●＋　＋●●＋　＋●○＋　＋●●＋
＋○●＋　＋●●＋　＋●○＋　　　○●●＋　　＋○●＋　＋○●＋　＋○●＋　＋○○○
＋●○＋　＋●＋＋　＋●＋○　　　○●＋＋　　○●＋＋　○○○＋　○●＋＋　○●＋＋

＋○＋＋　＋＋＋＋　＋＋＋○　＋＋＋＋　　　○＋＋●　＋＋＋●　＋＋＋●　＋＋＋●　＋＋○●
＋○●●　＋●●●　＋●○●　＋●●●　　　＋○●＋　○●●＋　＋●●＋　＋●●＋　＋●○＋
＋○●＋　＋○●＋　＋○●＋　＋○○○　　　＋●○＋　＋○○＋　○○○＋　＋●○＋　＋●○＋
○●＋＋　○○○＋　○●＋＋　○●＋＋　　　＋●○＋　＋●○＋　＋●○＋　○○○＋　＋●○＋

＋＋＋＋　＋＋＋＋　＋＋○＋　　＋＋＋＋　＋＋＋＋　　＋＋＋＋　＋＋＋＋
○●●●　＋●●●　＋●○●　　○○○＋　＋●○＋　　○○○＋　＋●○＋
＋○●＋　＋●●＋　＋●○＋　　＋○●●　＋○●●　　＋●●＋　＋○●＋
＋●○＋　○○○＋　＋●○＋　　＋●○＋　○○○＋　　＋●●●　○●●●

>>118
おまいが死ぬ前にパソコムが昇天するに３０００ガバス

升の数等で、法則を見つけ出すのは至難の技ですかね。
良スレage

>>67
オセロでも地球上の全ての物質を素粒子メモリーに変換したとしても間に合わんのね。
チェス以降だと宇宙の全素粒子を使用しても記録できない、と。

>>121
の続きキボンヌ

>>29
正確には５通りじゃないか？　
「勝ち、負け、引き分け、途中でぐちゃぐちゃにしてやる」
それプラスほったらかし。

>>125
終局までやると100レス以上必要になるだろうから自分でガンガレ！

トリビアの種に送って計算してもらおうぜ。そうすれば、きっと答えは出るよ。

>>121
回転対称性まで考慮してる？

前は囲碁・将棋板の中で細々とやってたけど、板分割で正式にオセロ板が！
まだ人口が少なくあまり盛り上がってないので、みんな ｷﾃ━━━(ﾟ∀ﾟ)V━━━ !!

囲碁・オセロ
http://game9.2ch.net/gamestones/
オセロ　雑談・雑学・質問総合スレッド　第8局
http://game9.2ch.net/test/read.cgi/gamestones/1111765962/

>>128
たのんだぞ

>>128
取り合えず、分かり易いようにペンネームは「名無しさん＠３周年」
で投稿して下さいです。

投稿してきたぜ

>>133
ﾜｸﾜｸﾃｶﾃｶ（AA(ry

age

3通り

試合結果だけなら。
勝つか、負けるか、引き分けの3通り。

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋●○＋＋＋
＋＋＋○●＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋

初手は1手、以降2手づつ打っていくとどうなるだろう。

>>139
もうすこし判り易く詳しく説明してクレマイカ

で、結局全局面は何通りあるの？
>>124
1局面100バイトとして、89,475,692,478,931,200バイト
1000で考えて89ペタ。
1テラ=1000円レベルでコスト的にも不可能じゃなくなる

>>141
その89ペタはどこから沸いた。

>>72から。
で、結局何通りなの？

>>4により、最大36893488147419103232通り。
>>141と同様に1局面につき100バイトかかるとする。

3,689,348,814,741,910,323,200バイトとなる。
Z　E　　P　 T　　G　 M　 K　　　　
これが何割かに減っても無理だべ

試合結果って決着のついた盤面図のことなの？

普通は初手からの総手順のことだと思うんだけど。

>>145
１）「試合結果」そのもの→3通り
２）終了盤面の状態→2^64未満
３）終了までの手順→60!未満
それぞれの結論を導き出してみては？

141の論点が124の想定している状況とずれているという
流れになってたと思うんだけど違ったみたいね。

ねえ何か思いついたから聞いて。プログラミングの素人ですが。。

まず、一局目から始まり、最後まで勝負つくまでの全通りはツリー状でイメージできるよね。
んで全通りの計算方法なんだけど
まず適当に勝負つくまで局を進ませる。一局一局の手は記憶させておく。
んで次に最後の一手が他に無いか探す(特殊な場合以外最後は一通りだけど)。
最後の一手が他に無かったら、最後の一手の情報を消す。
最後の一手の情報を消すごとにカウントを一つ増やす。
一手戻り最後から二手目が他に手がないか探す。
あったら、局を進ませる。
以下つづける。。。

この方法だと今カウントしている属のみの手を記憶してればいいから容量がなくてもいいんじゃない？

深さ優先探索だね。まぁ確かに容量は無くてもいけるかも知れんが、やってみ？
先に結論を言っておくと時間が足りない。4×4で実験してみてどれくらい時間がかかるか報告よろしく

でもこれで容量の問題は解決するよね？
かなり説明は省いたけど。

時間短縮は途中十局目ぐらいまで横ローラー探索をして、そのあとその結果をネットに載っける。
んで個々のPCがそれぞれの通りから縦探索をすればかなり時間短縮になるのでは？

これは面白くなってきたな。
呼びかけるか？

へへーん。もしかして俺凄い？(・∀・)
世界的にもまだ算出されていないんでしょ？
数年掛かりでもヤる価値はあると思うよね。。

第一手目を固定したとき。
証明1
違う手順で全く同じ局面になる２組の局面は存在しない。
証明2
証明1が真のとき、点対照、線対照となる関係の2組の局面は存在しない。

証明2はできた。けど証明1ができない。

これらが証明できたとき、全て埋まっている状態での全終局は
3^60より少ない
3^60÷4÷2÷2以下

となるorz
こうやって削ってけばどんどん少なくなるんじゃん？

>>148-149
ものすごいプリミティブな発想が出てきたことに（良い意味で）感銘を受けた

プリミティブ？原始的なってこと？
どうせ俺は素人だよ！！(｀ε´)

>>153
を訂正。２組→１組。3^60→2^60。


また閃いた。
全て埋まっている状態の終局面の全通りの予想値なんだけど
まずランダムに面を白黒埋める。んで開始の四マス白黒の状態になるように逆に局を進める。この方法は縦探索でね。
おそらく探索をかけても最初の状態にならないのが存在する。
んで例えば10パターン実行して１パターン…

ん？まてよ…
ごめん何でもなかった。。

あるソフトをネットを通してバラまく。このソフトは、一つの局面から一手すすんだ全ての局面を計算する簡単なソフト。
まず１台のPCからスタートする。一手目はルール上黒f5と決まっているらしいから。一局目は初期状態からf5に黒をおいた一通りの棋譜となる。
んでこの棋譜を同じソフトが入っている別の任意の一台のPCに送る。
棋譜を送ったら棋譜の情報を消す。
受け取ったPCは受け取った棋譜から二局目を弾きだす。
実際二局目は三通りある。
んでこの三通りの棋譜を今度は三台のPCに一通りづつ送る。
送ったら、棋譜の情報を消す。
以下続ける。

終局の棋譜を受け取ったPCは、この終局の棋譜はソフトネットワーク上唯一無二なので、「終局の棋譜が来た」という情報だけで棋譜の情報を消してもいい。

んで何回終局の棋譜が来たかを
代表のサーバーに送って
それを足していけば答えがでるんじゃん？

>156
既に指摘されているようだが、やっぱり時間が足りないと思われ。適当に概算してみよう。
この場合、木をそのまま辿っていくから可能な状態は >37 によると 10^58。
超大雑把に IPv4 アドレス全域に属するノードが使えるとして 2^32 ≒ 4*10^9。
どんどんノードが増加していくから処理が進む、というのは典型的なネズミ講発想で残念ながら頭打ちする。
つまりノード全域に盤面が行き渡ってしまえば他に渡せるやつがいなくなるので単位処理あたりに進む
手数はノード数と等しくなると考えて良かろう。結局、探索空間をノード数で分割しただけと考えて良い。
1ノードで 1μs で1手進むとして、1年間に 60*60*24*365*1000*1000 ≒ 3*10^13 進む。
結局全体で 1 年間で 4*10^9 * 3*10^13 = 12 * 10^22。
10^58 を割ってやると 8 * 10^34 年程度ということになる。

ttp://ja.wikipedia.org/wiki/宇宙の終焉
によると
> 10^14 年 -- すべての恒星が燃え尽きるまでの時間
だそうです。

レス有難う。
そっかあ。駄目かあ。うーんどうしょう。
感情的にだが10^58は予測値として多すぎると思う。
よし減らそう

漁師アルゴリズムを考えたらどうだろう？
んで漁師コンピューター開発までスレ保存

漁港の人にがんばってもらうしか

自分は素人ですが、真ん中に線を引いて対象的に動かしたら(鏡に写す様に)、もう一通りの結果がわかりますよね？これってみなさんの計算のプラスになりませんでしょうか？
無知の自分がレスってすみませんです。。。

最終盤面のみを考えて、
絶対にありえない形のパターン化ができれば
ありえない形の数を計算できて、最終盤面の通り数がでるのではないでしょうか。
（ただし投了の場合除く）

ありえないパターン�@
真ん中らへんの４つのどれかが無地　

あーーつかれた。あとは他の人に任せよう

>>160
そうすれば探索範囲が半分になりますね
ほかにも盤面を回転させると同じになる分を省いたりします。
殆どの人が割りとすぐ思いつくようなアイデアだけど
貴方が自分で思いついたならそれは貴方のアイデアです。
どうせみんなもう知ってるんだ、と考えるのをやめるのはもったいない。
めげずにアイデアを考えつづけていれば、
その内まだ誰も思いついてないアイデアが浮かぶかも知れません。

hosyu

補習

予測値の出し方なんだけど
まず何本か(多ければ多いほどいい)終局までの棋譜を適当につくる。
つぎに一本一本に対して局ごとの手の数を出す。
そして局ごとに何通りあるかの平均を出す。
その値を掛けて予測値を出す。
っていうのはどう？

いいサイトない？
って、Ａちゃんに・・・・。（：：：）

反応がない。。
とりあえずこの方法で計算した予測値を近々載っけますね。

ﾜｸﾜｸﾃｶﾃｶ(AA略

試しに動かしたら
7.29E+53
とか出た。頼むから論理エラーであってくれ

百本、千本の棋譜で試した所、共に予測値の桁が48桁になりました

やっぱだみだこりゃ

>>167
Ｋ３乙
４８桁という目星がついただけでも（少なくとも俺は）すごいと思うよ

>>170
GJ!
これはまったく新しいアプローチでしたね。

すんません。間違えました。
10＾52ぐらいです。
個人的にこれでほぼ確定と思っています。
調べる棋譜数としてはあまりにも貧弱ですが。。。

ttp://49uper.com:8080/html/img-s/72569.zip
↑結果です。説明が全くなくてすみません。

>>173
Page Not Found って出るのは
俺だけ？

あ〜!!!!!!!!!!!
時間さえあれば!!!!!!!!!!!!

UDみたいに分散コンピューティングは使う事は出来ないの？

分散コンピューティングでの予想経過時間
仮定1　コンピュータの速さは平均3GHzとする
仮定2　1クロックで1手探索できるとする
仮定3　>>173 の慨算が正しいとする
仮定4　コンピュータは常時100億台使えるものとする

結構非現実的な仮定もあるけど、これで計算すると
10^52 / (3*10^9 * 10^10) ≒ 3.3*10^32 [sec] ≒ 1.05*10^25 [年]
(´･ω･`)ﾑﾘﾎﾟ

>>176
オセロの勝敗を計算する事って
たんぱく質とかガンの特効薬の開発よりも時間がかかる事tなんだ･･･

すごい事にチャレンジしているな･･･

このままではどんなにコンピュータが発達しても答えが出ないことになってしまう。
目玉が飛び出るぐらい画期的な計算方法を発案しないと…

52桁まで有効な予測値を出すとかw

いつの間にかオセロの総手数を求めることが、
必勝解を求めることになっている気がするが...

こんなんあるよ。
分散すれば何とかなるかも。

ttp://oshiete1.goo.ne.jp/kotaeru.php3?q=1091338

6000 (年) * 365　= 2190000 (日)
約200000台のPCが集まれば、10日か...

この専門家の根拠は不明だが。
既出だったらごめんよ。

原始的な方法かもしれないけれど、
現在あるアルゴリズムと、分散コンピューティングを使って、
それぞれのPCでオセロを1試合ずつやらせる。
その試合結果をひたすら中央のサーバに集積していって
かぶらないものだけを抽出していく。
こうすることによって、過去の戦いの経験値を増やしていくと同時に
計算する事ではなくて実際的なカウントをしていく事ができるのでは？

でも時間もかかるし、実際的じゃないか･･･
素人考えでｺﾞﾒﾝ･･･

>>180
計算する事ではない実際的なカウント

って何？
詳細キボンヌ

>>180がいいたかった事って
一つ一つ実際の戦局を打ち出すことによってありえない盤面を省く事が出来るってことでは？

人間の脳ってすごいよな

>>180
>>182

なるほど、もすこし具体的に言うと
盤面をデータベースに蓄えていって、
そのデータベースからコンピュータが自動的に
法則性を見つけ出し、
あらゆる盤面の可能性(3^64)の中から
ありえない盤面を削ってゆく。

そしてしばらくして盤面が減らなくなったら
のこった盤面数がオセロの試合結果ということになる。

ってことか。なるほど。
ルールを覚えるのなら記憶容量そんなに増えないかもしれないしな。

問題はルールの自動抽出の部分か...

>>183

記憶容量そんなに増えない　-> 記憶容量そんなに食わない

すまん

いっちょやってみっか
┏━━━━━━━━━━━━━━━━━┓
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│○│●│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│●│○│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛

↑もうええっちゅに

>>183
そこんところ、自分素人なんでわからんのだけどでかくなっちゃうの？

>>187
覚えなければならない量のこと？
覚えなくてもいいけど、覚えたほうがいいってこと。

すべての盤面を一つ一つ数えるときに
何も覚えないと10^52すべてを数えないといけない。
もし仮にメモリが無尽蔵にあるとすれば、
一度出現したことのある盤面を覚えておくことができ、
最大でも3^64(= 約10^30)回数えればいいってことになる。

ただしそんな馬鹿でかい記憶装置はないんだよね。
1 テラ = 10^12
だからもっと効率のよい方法はないかなってなっちゃうのよ。

┏━━━━━━━━━━━━━━━━━┓
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│○│●│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│●│●│●│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛

↑そやからもうええっちゅうねん

┏━━━━━━━━━━━━━━━━━┓
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│●│●│●│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│●│●│●│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│ 　│ 　│ 　│ 　│ 　│ 　│ 　│ 　│┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛

問題を簡単にしようぜ。

黒ゴマ白ゴマあわせて10^52個ほどある。
効率よく何粒あるか数えるにはどの様な手法がいいでしょう？

>>192
ゴマで惑星がいくつかできそうな気がするが...

ゴマを一面にまいて、遠くから見て何色に見えるか
白→白ゴマ多い。
黒→黒ゴマ多い。
灰色→明度によって判断。
とか。

それだけの数のゴマを一面にまける平面がこの宇宙にあるのかは
知らないが。

要は｢カウント｣の限界だよね。正確に数を数えるには｢カウント｣以外ないのだが…

カウントしなければいい方法かぁ･･･

逆転の発想！
演算時間や計算結果のメモリ消費量からカウント数を割り出す

ﾅﾆ言ってんだ･･･俺･･･

>>194
たしかに。

オセロは
ある局面の次の局面数はその盤面の状態に依存してしまう。
○×ゲームみたいに次の局面数がみんな同じじゃないからなぁ。

○×ゲームも正確には　9! ではなくて、途中で終わることも
考慮しなければならないが。

○×ゲームの試合結果の通り。
カウントではなく数式で答えを出すのはこの問題でさえむずかくね？
やべー

○×ゲーム程度のサイズなら全探索でOKじゃね？

>>197
○×ゲームでは
理論上、最も早く勝負がつくのは5手目だから
それまでの9*8*7*6*5までは正確に分かる。
問題は残りの4ターンがどういう振る舞いをするかだな。

これをカウントせずに正確に算出できれば、
オセロの総手数算出の足掛かりになるかもしれないな。

○×ゲームの全探索してみた。
数式での計算の答えあわせに利用してくれ。

引き分けは問題を簡単にするために全部埋まった時点でということにしておく。
つまり勝負が決まる以外での枝刈りはなし。

1ターン目の局面数: 9
2ターン目の局面数: 72
3ターン目の局面数: 504
4ターン目の局面数: 3024
5ターン目の局面数: 15120
6ターン目の局面数: 54720
7ターン目の局面数:148176
8ターン目の局面数:200448
9ターン目の局面数:127872

全ての局面数： 549946
先手の勝ち数： 131184
後手の勝ち数： 77904

バクの可能性もあるだろうから
信頼性向上のため誰か他にも作って確認してくれ。

>>198
うん。でも探索はオセロでは使えないことが
今までのﾚｽでほぼきまったと俺は思うのよ。
方法としてあとは計算で出すしかないかと。
>>199が言ってくれたように○×はその練習問題として
いいんじゃない？

>>200
おつかれどす。
これで正解はでた。この数字に行き着く計算式を考えよっと。
つーかやっぱり後手超不利だなw

6ターン目以降が全て144で割り切れるのは偶然?

age

>>200
1ターン目: 9
2ターン目: 72
3ターン目: 504
4ターン目: 3024
5ターン目: 15120
6ターン目: 54720
7ターン目:148176
8ターン目:200448
9ターン目:127872
一緒になりますたｗ乙！

>>204
計算式を載せてくれ！！！！

>>205
>>204と>>200はプログラムだと思われ。

＞＞205
？

>>206
そうだったのか...

すまん。

>>204

そして乙

>>202
必然。
ｎターン目の局面数をPnとおくと

P2＝P1ｘ8
P3＝P2ｘ7
P4＝P3ｘ6
P5＝P4ｘ5

このようある局面はそれまでの局面から派生したものであるから
共通の局面というものが局面数の因子として数え上げられる。

>>210
よくわからんのだけど、
それってP5の総盤面数は9,8,7,6,5を約数に持つって事?

でも、あるターン以降は勝敗を決しているから
そんなに単純にいかないのでは？
見当違いな意見だったらごめん

もちっと詳しく教えて

>>210
6ターン目からは前のターンから掛け算的に派生したわけじゃないから、必然とはいい難くね？

６ターン目の総ノード数が

9*8*7*6*5*4 - 5*4*3*2*1 * ((11*10*9*8)/(4*3*2*1))

になった。
だれか理由を考えてくれ。

ソースは忘れたが
「オセロは後手必勝が証明された」
みたいなのを　どこかで読んだような…
スレ違いすまん

ん？今更だが>>200,204は棋譜（というのか知らんが）が異なれば別、という探索？
てっきり盤面のパターン数を数えているのかとばかり…orz
〜5手は計算で分かるジャマイカ…orz

>>214
４×４はプログラム作ると一瞬で出る
６×６は1993年にイギリスの学者がコンピュータで算出した。
ttp://www.maths.nott.ac.uk/personal/jff/othello/6x6sol.html　参照。

ちなみにどちらも後手必勝

でも８×８は　>>179の参照先 によると去年の時点で６０００年かかるらしい。
俺も８×８は聞いたことがない。

nターン目で勝負がきまった曲面数をQnとすると
P6=9C6-Q5×4
;Cは場合の数の時につかうアレね。


またQ5の話で、
○を先手とした時に４ターン目で○がリーチになる通りは
○を固定したとき○が２つある次元に×がない場合だから
6C2=15通り
非リーチの場合は同じく○を固定したとき
6通り

そしてリーチ状態から5ターン目でビンゴになる通りは
1通り
リーチ状態から非ビンゴの場合は
4通り
よって
Q5=P4×15/(6+15)×1/(1+4)

っつー等式ぐらいしか思い浮かばん。

>>215
そう、単純にすべての盤面を並べただけ
だから言うとおり5手までは単純な掛け算で算出可能さ

まとめると総盤面数はだいぶ減るけど、計算式を出すのが
その分大変になるんよ

あまちごーた
誤　P6=9C6-Q5×4
正 P6=9×8×7×6×5×4-Q5×4

因みに
9!=Q5×4!+Q6×3!+Q7×2!+Q8+Q9
も成り立つよね。

hosyu

ほしゅあげ

あたいこそが222ｹﾞﾄｰ

ひさしぶりにきたらだいぶ止まってるな。

>>217 >>219
>>213の式の解説だよね?
>>213の式とすこし違うな。

ちょこっとプログラムを作ってオセロの概数出してみたので報告。>>167=173とは違う方針2種類で。
データは同様に「ランダムに配置して置けるマス数を数える」を10000試合行った。
取り合えず今回は結果だけ。詳細なデータは纏めるまで待って。

1)
1手ずつの相加平均を出して掛け合わせる。1手目は4、2手目は3，3手目は4.67…という感じ。
60手目の平均選択肢数が0.9056だったのでここまで掛け合わせた結果、1.21e+52 通りくらい。

2)
>>167に近い方針かも。選択肢の数ということで、1回1回のシミュレーションで1)のように掛け合わせた結果を出す。
選択肢の数なのでパスの場合も1通りと数える。で、その10000試合分平均を取るわけだが…
A.普通に相加平均取ってみた。1.8e+54 通り。
B.どうせなら最後まで掛け算だろ、相乗平均。1.0e+51通り。

さて、どれが近いのやら。

>>224
乙。計算の仕方によって結構結果が変わるんだな。
でもこうなってくると、
真の値にどれが一番近いのか判別する手段ってあるのかな。

hosyu

>>226
きみにmuchu

( ´･ω･)ﾑｽﾞｶｼｽ

>>228
順を追って考えればそうでもないよ

でも最近、滞ってんだよね　(´д｀ )

解析的アプローチを取ってみたらどうだろう。
いや、具体的な手法は思いつかないんだけど。

解析的アプローチってどんな感じ？
具体的でなくていいからおせえて

（可能な局面の）全探索ってことか？違うかな？よくわかんないや

数値解析じゃなくて解析学の解析ね。
例えばサイズがnに近づくような極限をとってやると答えが出るような式を探索するとか・・・
サイズっていうのは石の数なのか手数なのか升目の数なのか、どれがいいのかはわからんけど。

あとはスケーリングの議論ができると面白い「かも」しれない。

agege

4×4なら全探索できたから載せようか?

>>235
うｐよろりんごりらっぱんだちょうしくまんとヒヒーン！

期待保守上げ

将棋だともっと大変だろうな

ちなみにオセロは10＾60通りだとか
囲碁は10^300通りって本に書いてあった。

「大体」は分かるけど「正確」には難しいな。

>>239
オセロは必ず６０手以下でゲームが終わる
で単純に盤面の可能な着手数を平均１０としただけなのが１０＾６０
まあそれぐらいのオーダーだろうと言うくらいの概算

概算は既に色々出ているけど、どうなんだろね。

概算はいいからこれは絶対に超えないというラインを攻めていこうよ。
まずは (64-4)!<=10^81.9202 だな。
これは絶対に超えない。

(64-4)!っていうのは分かりやすくていいんだけど、
はじめの方の60*59*58…とかが現実的じゃないんだよね。
後ろのほうの…3*2*1とかはある程度絞れている感じがする。
なぜはじめの分岐が60パターンもないかというと
石が少なくて置ける場所が少ないからなんだよね。
例えば置ける場所っていうのは多くても
現在置かれている石についてその周り７つ（１箇所は必ず既に置いてある）だけだから、
5手目までは 既にある石の数*7 という絞り方ができる。これで
28*35*42*49*56*55*54*...*3*2*1 < 10^79.6125
ここまで絞れた。うーん。>>243から1/100しか絞れなかったな…道のりは長い…

>>244
なぜ5手目までなの？

六手目からは
(64-4)! のルールの方が 少ない値で掛けられるからだとおもう。。

この世の中の勝負ごとには『勝ち』か『負け』の２通りのみだよ








ちなみに俺は負け組

http://page5.auctions.yahoo.co.jp/jp/auction/e51957354

毎日ここ見てる人いんのかな。

>>249 ﾉｼ

>>247
まだ試合中でしょう？

これからもよろしく

毎日ではないけど、見てますよ

いいスレですよね。濃くて。

でも最近更新が無くて寂しい

オセロで打てる箇所の数は最大で２８かな？
例えばこういう↓局面。
＋＋＋＋＋＋＋＋
＋○○○○○○＋
＋○●●●●○＋
＋○●●●●○＋
＋○●●●●○＋
＋○●●●●○＋
＋○○○○○○＋
＋＋＋＋＋＋＋＋
「２８」なのかは証明したわけじゃないけど、
この局面より打てる場所が多いのは思い浮かばなかった。
もし２８で正しいなら２８より大きいのは２８にしてしまえるから
28*28*28*28*...*28*27*...*3*2*1=6.21e+75ってできると思う。
これだと>>244より4桁くらいしぼれるかな
誰か「２８」の証明か反例探しお願い。

>>256
もっと多いの見付けた・・。
これで打てる場所は３２個。
＋＋＋＋＋＋＋＋
＋○○＋○○○＋
＋○●○○●○＋
＋○○●●○＋＋
＋＋○●●○○＋
＋○●○○●○＋
＋○○○＋○○＋
＋＋＋＋＋＋＋＋
32*32*32*32*...*32*31*...*3*2*1=3.67e+77
増えていく・・（泣

ちょっと試してみたがオレも32ヶ所以上はできなかった

33個見つけました。
＋＋＋＋＋＋＋＋
＋○○●○○○＋
＋○●＋○●○＋
＋●＋●●＋○＋
＋○○●○●○＋
＋○●＋○●○＋
＋○○＋○○○＋
＋＋＋＋＋＋＋＋
33*33*33...*33*32*...*3*2*1=8.68e+77

プログラムを作って実際の数を調べてみた。
1・・・4
2・・・12
3・・・56
4・・・244
5・・・1396
6・・・8200
7・・・55092
8・・・390216
9・・・3005320
10・・・24571192
24571192*33*33*...*33*32*...*3*2*1=1.39e+70
急ごしらえなのであんまり速くないからとりあえず10手まで。
あと、まだバグがあるかも知れないから誰か検証お願い。

>>259お疲れ様です。
よくみつけたなあ
一万本適当に棋譜作ったとき最高25手という棋譜が一本だけあった。
30手〜はほとんど無視していいぐらいに少数になると思う。
>>260
それにしても計算早くないですか？

>>261
＞一万本適当に棋譜作ったとき最高25手という棋譜が一本だけあった。
＞30手〜はほとんど無視していいぐらいに少数になると思う。
僕もそう思います。
ちなみに>>256の局面とは違いますが、28箇所置ける局面まで辿りつく棋譜は作れました。
F5D6C3D3C4F4F6G6E6E7F7G5E3C5F3B3B4B5B6B7C7G2G3G4D7G7C6B2C2D2F2E2
もっと多いのも探してみますが、
>>257とか>>259みたいな局面を実際に並べて作れるかは疑問に感じてます。
＞それにしても計算早くないですか？
プログラムの計算はあんまり速くないと思います。
今のプログラムのノード展開速度は220kn/s(@Pentium4 2.4GHz)くらいでした。
WZebraとかだとこの20倍くらいは速度が出てますし。
でも速くするアイディアはいくつかあるのでそのうち改良してみます。

＋＋＋＋＋＋＋＋
＋○○○＋○○＋
＋○●○＋●○＋
＋○○○○○○＋
＋＋＋○○＋＋＋
＋○●○＋●○＋
＋○○○＋○○＋
＋＋＋＋＋＋＋＋

こーいうの(３６箇所)はダメなん？

>>263
僕は空きの数ではなく返せる場所の数を数えてました。
その局面だと空きは36箇所で打てるのは20箇所ですね。

よく分かっていない >>263 がいるスレはここですかw

>>262
きみの研究に注目しているよ

返せる場所の数?

全試合数の話題をしているわけだから着手可能数だろがボケ

>>267
解ってねーm9(^Д^)ﾌﾟｷﾞｬｰ

>>264
打てるのが20箇所ってどういう意味ですか？

256っちの流れいいね。
まだ最大分岐数33と決まったわけじゃないけど。

一方試合数絞りの方は
>>260の10手目=24571192を信じるとすると
全試合数 <= 24571192*50*49*...*1 < 7.4732e+71 (= 10^71.8736)
これは確実。

混乱してるみたいなので一応解説。

＞僕は空き(☆ & ＋)の数ではなく返せる場所(☆)の数を数えてました。
＞その局面だと空き(☆ & ＋)は36箇所で打てる(☆)のは20箇所ですね。

☆＋☆＋☆☆＋☆
＋○○○＋○○＋
☆○●○☆●○☆
＋○○○○○○＋
☆＋☆○○☆＋☆
☆○●○☆●○☆
＋○○○＋○○＋
☆＋☆＋☆☆＋☆

今回の論点は「打てる場所」です。

スレ始まって以来の有意義な盛り上がりが。

違う手順で同じ局面になる事があるんだけど、
この扱いはどうすればいいかな？(transposition)
例えば次のような局面。
F5D6C3D3C4とF5D6C4D3C3
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●○＋＋＋＋
＋＋●●●＋＋＋
＋＋＋○●●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
F5F6E6F4E3とF5F4E3F6E6
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋●＋＋＋
＋＋＋○●○＋＋
＋＋＋●●○＋＋
＋＋＋＋●○＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
F5F6E6F4G5D6E7G6とF5F6E6F4G5D6E7F7
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋○○○＋＋　＋＋＋○○○＋＋
＋＋＋○○○●＋　＋＋＋○○○●＋
＋＋＋○○○○＋　＋＋＋○○○＋＋
＋＋＋＋●＋＋＋　＋＋＋＋●○＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
>>260ではこれらを別物としてカウントしてます。

あー、あれですよ。「オセロの試合結果」というものをどう取るか次第。
1）勝ち・負け・引き分け派　→　3通りということでFinal answer
2）決着時の盤面が何種類あるか派　→　回転・対称な盤面は1つに
3）棋譜？が何通りあり得るか派　→　全部別物ということで

プログラムとか組みやすいのは3）だろうね。自分は2）派。

>>262
＞>>259みたいな局面を実際に並べて作れるかは疑問に感じてます。
このことに関してちょっと考えてみました。

ランダムに作った盤面の総通りaは、
a = 3^64 = 4.23912E+28
これはオセロの総棋譜数の予測値より格段に少ない値です。
だから、ランダムに作った盤面は棋譜で表現できるんじゃないかと。

しかしランダムで作った盤面の中には囲碁みたいに離れた石が存在するような盤面もありますし、
試合開始前からある真ん中の四つの石がない盤面もあります（3^60で済みますが)。
つまり置石の形からしてオセロでは表現できない盤面があります。
またさらに、存在してそうな形をしていてもオセロ棋譜で表現できないものもあります。
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋○●＋＋＋
＋＋＋●○●＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋とか。
すみません当たり前ですね。


ですがここで別の疑問が出てきます。
オセロで作られる局面は、aよりはるかに少ないです（おそらく桁ちがいに）。
オセロの棋譜数は、aよりはるかに多いです（おそらく桁ちがいに）。
ですから、>>275のような異棋譜同局面はものすごく多いのでは？
下手したら他の棋譜と局面上交わらない棋譜はないのでは？
という疑問がでてきます。

訂正 >>275→>>274

>>276
60展開後の局面数がもうめちゃくちゃ多く見積もって < 2^64 = 10^19 だから
かなり縮退してそうだね。

あと奇遇性とか連結性（離れ小島は発生しない）とかで絞ったらどうかな。
連結性でいえば、
2x2 の黒石で始まって隣８箇所のどこかに黒石がありさえすれば
黒石が置けるようなゲームを考えると、
必ずそのゲームの棋譜数（局面数）はオセロのそれらを下回るし
解析もやりやすいと思う。

まあオセロより解析が簡単と言えど
その局面数を数え上げるのも結構むつかしいんだが…。

>>275
終盤60手完全読み！をする計算量を求めたいんだと思ったから
3) でどうでしょう？

スレタイが変な気がしてきたｗ

完全先読みでしたら、2）と3）の混合（>>274を一緒とする）が現実的かと思います。
というより2）寄りなのでは？

>>274
局面数と棋譜数の違いをとるかとらないかですね。
これらを同じにすると棋譜数＝終局の局面数となると思う。

でもどっちにしろ、F5〜G6とF5〜F7を同じにするのはちょっと抵抗があります。
理由は、そもそも同じ局面なのか？ということです。たしかにその後の振る舞いは対称的に同じですが…
なんだろ…うーん。
感覚の問題なんですかね。

>>275
>>260のプログラムを作るときに2)で数えるか3)で数えるか迷いましたが、
作るのが簡単な3)でやってみました。
プログラムの改良にと思ってTransposition Tableをハッシュ法で実装してみたら、
ごく一部でハッシュ値の衝突（全く違う局面から同じハッシュ値が生成）が起きたようで、
値が少し違う結果が出てきてしまいました。（速くはなりましたが）
もうちょっとよく考えてみます。
>>278
石有り/空きの2値のみの局面をランダムに発生させて、
中央の2x2マスが埋まっている割合とそのうち全ての石が繋がっている割合を
モンテカルロ法で調べてみました。
その結果、10億回の試行で、
�@　中央の2x2マスが埋まっているもの：62503304(6.2503%)(1/15.999232≒1/16)
�A　�@のうち全ての石が繋がっているもの：18267113(1.8267%)(1/54.743188)
�@は予想通りでした。
�Aは見当もつきませんでしたが、、、こんなもんなのかぁ。

>>282
256氏お疲れ様です。仕事の早さに感動した

>>282
ランダムに作った盤面 a=3^64=3.43368E+30 通り
そのうち中央４マスは空にならないとすると　b=(3^60)*(2^4)=6.78259E+29
確率はb/a=(2^4)/(3^4)=1/5.06≒19.75％

＞石有り/空きの2値のみの局面をランダムに発生させて

出来るなら石有りの発生確率を空きの２倍の確率にしたらどうだろう？
そうすれば�@の確率は19.75％に近づくだろうし�Aの確率も変わるはず。

こんにちは

激安!大人気&バッグ.送料は無料になりました！価格は特恵を与える！


新しいデザインの腕時計とブランド、多くの種類のバッグ、財布、 新品かばん,流行かばん,本皮財布 かばん 財布
新型の腕時計、ローレックスの腕時計、

品質はよくて、価格は合理的だ!

お客さんのメールに 迅速返信します。
入金を確認して、 一日 の以内は出荷できます。

ご注文を期待しています

お世話になります

当店URL：http://www.chaneljp.com/

[email protected]



以上
宜しくお願いします

>>284
それはオセロゲームの確率。
黒石ゲーム(>>278)は
a = 2^64
b = 2^60
で b/a = 1/16
ですよ

>>282のプログラムを改造して石の数毎に分布を調べてみました。
（待つのがめんどくさかったので１億回の試行。ちょっと精度は落ちますが。）
局面発生数のピークは石数が３１・３２個の付近にありました。（約9.77%）
中央の2x2が埋まったり石が繋がっている割合は石数が増えるほど多くなってました。
一部抜き出します。
石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合
40----1079403----161591----103285----0.149704----0.095687
41----616058----102065----70461----0.165674----0.1143740
42----328628----60178----44581----0.183119----0.135658
43----163666----33264----25916----0.203243----0.158347
44----76032----16754----13726----0.220355----0.180530
45----32723----7869----6692----0.240473----0.204504
46----13226----3490----3093----0.263874----0.233858
>>284
＞出来るなら石有りの発生確率を空きの２倍の確率にしたらどうだろう？
2倍の確率ってのは黒/白/空きの3値の盤面から石有/空きの2値の盤面に変換すると
石の存在確率が空きの2倍であるといったような事からですか？
上の表で石の存在割合が空きの2倍である42石や43石（64*2/3≒42.667）の辺りを見ると、
0.183119〜(19.75)〜0.203243となってますが、、。
2値の盤面は32ビットの乱数を2個発生させてつなげて作ってました。
各マス毎に乱数を発生させると発生確率を変えられそうですがちょと遅くなりそうな気が。
何かうまい方法はありませんか？

＞局面発生数のピークは石数が３１・３２個の付近にありました
中心極限定理ってことかな。

0〜60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で
黒石ｎ個であるときの一様な試行が得られるよ。

>>286
はい、それは了解しています。
>>284は黒石ゲームからオセロゲームへのアプローチのつもりでした。

>>287
お疲れ様です。
石数が４５の時任意のマスが埋まってる確率は45/64=0.703
中央４マスが埋まってる確率は0.703^4=0.244≒0.240473なので正解に近いでしょう。

石の発生確率２倍というのは仰るとおり黒/白/空き３値の盤面を想定してのことでした。
前出 b=(3^60)*(2^4)=6.78259E+29 に３値での発生確率を掛ければ概算の有効盤面数が割り出せるかと考えました。

乱数発生ですが、１マス３ビットで5/8=0.625の乱数は作れますが
乱数発生を３倍にしたにしては精度が低いですね。
８ビット乱数(2^8=256)で５マス(3^5=243)を作るのが効率良いのかな？
それより前出 b の式自体を変えたほうが良さそうですね。

>>288
＞0〜60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で
＞黒石ｎ個であるときの一様な試行が得られるよ。
よくわからなかったのですが、気になるのでもうちょっと詳しく教えてもらえますか？
n個の１をばらまくほうが簡単そうですが、、、これではだめでしょうか？
石数が14個くらいまでならオセロ盤で実際に10手以下の全探索をした盤面と比較できると思ったのですが、
今の方法だと石数が20個くらいまでの局面発生数はほとんどゼロにしかならなかったので、
一様な試行もできればいいなと思ってました。
>>289
石の発生確率を2倍にしてみました。（1億回試行）
乱数は、16個発生させて１マスあたり８ビット使い、
3で割った余りによって石有/空きを決めました。（遅い）
石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合
34----810312----59684----14553----0.07366----0.01796
35----1391979----114885----33877----0.08253----0.02434
36----2237616----207915----73092----0.09292----0.03267
37----3388840----353598----144910----0.10434----0.04276
38----4814954----558985----260877----0.11609----0.05418
39----6420635----830327----436917----0.12932----0.06805
40----8024164----1153300----673413----0.14373----0.08392
41----9401529----1500247----959482----0.15957----0.10206
42----10292005----1814899----1251133----0.17634----0.12156
43----10535592----2045606----1508248----0.19416----0.14316
44----10053709----2147383----1673889----0.21359----0.16649
45----8931797----2095020----1712559----0.23456----0.19174
46----7381673----1897347----1613363----0.25703----0.21856
47----5646603----1586556----1394172----0.28098----0.24690
48----4002903----1227091----1109087----0.30655----0.27707
49----2617925----874116----807797----0.33390----0.30856
50----1568075----568807----535577----0.36274----0.34155
51----861444----339229----324220----0.39379----0.37637

ん〜、8ビット使って3の剰余で分ける…0が1と2より1/85だけ多い割合で出るからこの数のシミュには向かないのでは？
剰余にかかる時間 >> 乱数1個発生時間 だろうし、32ビットのまま行ってみては？

今32ビットで、１億回試行中ですが、
さっき１０００万回で比較したら処理時間が2倍ちょっとになっちゃいました。

お疲れ様です。
こっちは後発なので2）の方針でいこうと思います。（対称解は1つ扱い）
>>120が正確ではない（4×4だから）けど参考になる、と自分用リンク。

８ビットだと確かに精度が悪くなっているようです。
>>290と同じ範囲でもだいたい１‰以上の誤差が出てきてます。
５０〜５８石あたりでは数％も誤差がありました。
石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合
34----819799----59304----14654----0.07234----0.01788
35----1394987----113825----33552----0.08160----0.02405
36----2239644----206965----72737----0.09241----0.03248
37----3370795----349045----142996----0.10355----0.04242
38----4786955----553633----258442----0.11565----0.05399
39----6383626----825334----434910----0.12929----0.06813
40----7979411----1147014----670576----0.14375----0.08404
41----9371145----1492668----953573----0.15928----0.10176
42----10279583----1811139----1249041----0.17619----0.12151
43----10544519----2046793----1506964----0.19411----0.14291
44----10086594----2156237----1680278----0.21377----0.16659
45----8979083----2107749----1723086----0.23474----0.19190
46----7424025----1909494----1623887----0.25720----0.21873
47----5688036----1597364----1403921----0.28083----0.24682
48----4014876----1231054----1111899----0.30662----0.27694
49----2609923----870280----803689----0.33345----0.30794
50----1558130----564842----531864----0.36251----0.34135
51----847121----332688----317532----0.39273----0.37484

そろそろ難しくてついていけなくなりましたが、一生懸命レスさせていただきますｗ
僕はプログラムのプもかけません。もしかしたら勘違いしているのかもしれません。


空きの発生確率を　Og　。石の発生確率を　Ob　。（つまり　Og　+　Ob　＝　1　）
とする。
石数が　n　の時の局面発生率は、
64Pn * Og^(64-n) * Ob^n
です。
---Og-----Ob
A--0.3329--0.6671
B--0.3330--0.6670
C--0.3331--0.6669
D--0.3332--0.6668
E--0.3333--0.6667
F--0.3334--0.6666
G--0.3335--0.6665
H--0.3336--0.6664
I--0.3337--0.6663
と石空き発生率A〜Jに振り分ける。
例えばＥで石数が40の局面発生率は、
64P40 * 0.3333＾24 * 0.6667^40
= 0.080229095

続き
次にEを基準として次の表を作成する。
石数--A/Ｅ---B/Ｅ----C/Ｅ---D/Ｅ----E/Ｅ----F/Ｅ---G/Ｅ----H/Ｅ----I/Ｅ
3-----0.9310--0.9478--0.9649--0.9823--1.0000--1.0180--1.0363--1.0550--1.0740-
6-----0.9361--0.9517--0.9675--0.9836--1.0000--1.0166--1.0335--1.0507--1.0682-
9-----0.9412--0.9555--0.9701--0.9850--1.0000--1.0153--1.0308--1.0465--1.0624-
12----0.9463--0.9594--0.9728--0.9863--1.0000--1.0139--1.0280--1.0423--1.0567-
15----0.9514--0.9633--0.9754--0.9876--1.0000--1.0125--1.0252--1.0380--1.0510-
18----0.9565--0.9672--0.9780--0.9890--1.0000--1.0112--1.0224--1.0338--1.0454-
21----0.9617--0.9712--0.9807--0.9903--1.0000--1.0098--1.0197--1.0297--1.0397-
24----0.9669--0.9751--0.9833--0.9916--1.0000--1.0084--1.0169--1.0255--1.0341-
25----0.9722--0.9791--0.9860--0.9930--1.0000--1.0071--1.0142--1.0214--1.0286-
30----0.9774--0.9830--0.9887--0.9943--1.0000--1.0057--1.0115--1.0172--1.0230-
33----0.9827--0.9870--0.9913--0.9957--1.0000--1.0044--1.0087--1.0131--1.0175-
36----0.9880--0.9910--0.9940--0.9970--1.0000--1.0030--1.0060--1.0090--1.0120-
39----0.9934--0.9950--0.9967--0.9983--1.0000--1.0017--1.0033--1.0050--1.0066-
42----0.9988--0.9991--0.9994--0.9997--1.0000--1.0003--1.0006--1.0009--1.0012-
45----1.0042--1.0031--1.0021--1.0010--1.0000--0.9990--0.9979--0.9968--0.9958-
48----1.0096--1.0072--1.0048--1.0024--1.0000--0.9976--0.9952--0.9928--0.9904-
51----1.0151--1.0113--1.0075--1.0038--1.0000--0.9963--0.9925--0.9888--0.9851-
54----1.0206--1.0154--1.0102--1.0051--1.0000--0.9949--0.9898--0.9848--0.9798-
57----1.0261--1.0195--1.0130--1.0065--1.0000--0.9936--0.9872--0.9808--0.9745-
60----1.0317--1.0237--1.0157--1.0078--1.0000--0.9922--0.9845--0.9769--0.9693-
63----1.0373--1.0278--1.0185--1.0092--1.0000--0.9909--0.9819--0.9729--0.9641-
※A/Eは　Ａ割るＥ　という意。少数5桁目を四捨五入しました。

続き
つまりなにが言いたいかといいますと、石数42個らへんが一番コンピューター乱数の仕様誤差（？）の影響を受けにくく、石数４２個らへんから、上にも下にも影響を受けやすくなる。ということです。

と思います。

http://www.geocities.jp/trait1980
http://www.geocities.jp/unirankrank/

前言撤回。複数がやるにしても同じ結果に到達しなきゃ確証得られませんし
自分も3）方向で行きます。取りあえずは>>260と同じ物が出るかを確認し、
もう少し先の手まで進めて上から押さえるつもりです。

石の発生確立を２倍にするのは難しいようですね。
発生確率をRとし　0<R<1　とすると
64マスで石の個数 n となる確率は R^n*(1-R)^(64-n) となります。
（実際はこれに組み合わせ数を掛けないといけないが補正係数の算出には不要なので省略）
発生確率2/3と1/2の差を２値での個数ごとの結果に掛け合わせたらどうでしょうか。
石の個数nの時の補正係数は{(2/3)^n*(1-2/3)^(64-n)}/{(1/2)^n*(1-1/2)^(64-n)}

>>287のデータに補正係数を掛けると
石数--補正係数------局面発生数----埋まてる数----繋がてる数
40----5.906894946---6375920.125---954501.0612---610093.6445
41----11.81378989---7277979.773---1205774.465---832411.4496
42----23.62757978---7764684.289---1421860.496---1053341.134
43----47.25515957---7734062.946---1571895.628---1224664.715
44----94.51031913---7185808.584---1583425.887---1297248.64
45----189.0206383---6185322.346---1487403.403---1264926.111
46----378.0412765---4999973.923---1319364.055---1169281.668

石数0〜64のすべてに補正係数を掛けて埋まってる数、繋がってる数のトータルを
出せれば石の発生確率2/3のときのデータになるはずです。
補正係数を掛けると局面発生数のピークも42〜43になるようです。

>>287
＞局面発生数のピークは石数が３１・３２個の付近にありました。（約9.77%）
見直してて気づいたのですが、このようになるのはおかしいですね。
０以上のの乱数を発生させてたようで常に０のビットが１箇所あります。
初歩的なミスですみません。石の発生確率が1/2のはやり直します。

>>301
あ、よかった。試しに真ん中4つが埋まってるプログラムを作ったら
10億回のテストで約2倍（発生回数も、埋まってる回数もなので割合はほぼ一緒）
だったのでちょいと不安だったのですよ。

ついでにちょいと訪ねてみます。繋がりチェックはどううやってます？

作った、ていうだけだと無意味なので一応結果。
1/2の割合で石を置いた場合、真ん中4つが埋まってるかどうかのチェック

石数-埋まる盤数/発生盤数-埋まる割合
26---1218966/-45486584---2.680%
27---1907062/-60649877---3.144%
28---2785026/-75805416---3.674%
29---3779166/-88870059---4.252%
30---4802368/-97776964---4.912%
31---5689156/100905325---5.638%
32---6306276/-97783629---6.449%
33---6517819/-88887714---7.333%
34---6304380/-75812328---8.316%
35---5693658/-60654246---9.387%
36---4801615/-45477307--10.558%
37---3783263/-31960276--11.837%
38---2779478/-21035323--13.213%
39---1907262/-12943552--14.735%
40---1217947/--7439856--16.371%
41----725024/--3994642--18.150%
42----400816/--1995761--20.083%
43----205262/---929754--22.077%
44-----97770/---401131--24.374%
45-----42627/---160050--26.634%

>>302
繋がりチェックは画像の領域塗りつぶしをするときのような再帰関数でやってます。
http://www.sm.rim.or.jp/~shishido/fill.html

>>256っちにひとつ質問。
パスは１手と数える？
>>260と同じ結果を求めてるんだが９個目から答えが合わないんだ。

ごめんあげちゃった

>>256
>>260ではパスは１手として数えてません。
＞>>260と同じ結果を求めてるんだが９個目から答えが合わないんだ。
うーん・・自分の方が正しいという自信が無いので見直してみます・・。

9手までの試合数は
passを1手と数えると 3005288
passを0手と数えると 3005320 (= >>260)
となりました。
まあどっちでもいいんじゃないでしょうか。ありがとう。

wikiとか作っちゃていいすかね

石の発生確率が1/2のをやり直しました。（1億回試行）
乱数はメルセンヌ・ツイスタを実装して使いました。
石数--局面発生数---埋数-----繋数----埋割合(%)--繋割合(%)
26-----3259193-----76287-----2155-----2.341-----0.066
27-----4590786----127177-----4935-----2.770-----0.107
28-----6062081----193814----10284-----3.197-----0.170
29-----7532330----280764----19920-----3.727-----0.264
30-----8780535----378290----35483-----4.308-----0.404
31-----9634737----476656----58036-----4.947-----0.602
32-----9935619----560162----88116-----5.638-----0.887
33-----9634648----620294---121801-----6.438-----1.264
34-----8783902----641192---156250-----7.300-----1.779
35-----7533047----620987---182592-----8.244-----2.424
36-----6066048----562048---196924-----9.265-----3.246
37-----4592260----477504---195003----10.398-----4.246
38-----3262028----379078---177332----11.621-----5.436
39-----2172546----281015---148555----12.935-----6.838
40-----1355366----195240---114113----14.405-----8.419
41------794734----127204----81540----16.006-----10.260
42------435867-----76380----52814----17.524-----12.117
43------222876-----43355----32009----19.453-----14.362
44------106482-----22713----17578----21.330-----16.508
45-------47634-----11304-----9285----23.731-----19.492
局面発生数のピークが３２に来ましたけど、
０〜６４のちょうど真ん中だからこれでいいですよね？
>>309
どんなWikiですか？

>>310
話題の専門化が進むと、筋がみえなくなってくると思うんですよ。
Aの問題を解こうとするとBという問題にぶちあたる
↓
Bの問題を解こうとするとCという問題にぶちあたる
↓
…

みたいに。
この辺をどこかに提示するしないとではスッキリさが違うと思います。あとから来る技術者にもとっかかりやすくていいかと。

一番の目的はこれですね。
あとは自分のデータを載っけたり理論を載っけたり、討論用のホワイトボードとして使うのもいいと思います

でも僕はコテをつけてしまったので他の名無しさんが立ち上げるのがいいかもしれません

>>311
便利そうですね。
他の皆さんの意見も聞いてみたいです。
>>308
あ、合ってましたか。
うれしいです。ありがとうございます。

>>311 Wikiｷﾎﾞﾝﾇ。実は誰かが纏めサイト作ってくれるのを待ってた。待ってただけで自分から行動してなかった訳ですが…orz

ある石の周囲にある石の数をとりあえず接続数と呼ぶことにします。
接続数について考えてみました。
オセロで実際に存在する盤面は、（当たり前のもありますが、、）
・全ての石の接続数は１以上。
・接続数が１の石に接続している石の接続数は２以上。
・接続数が１の石とそれに接続している石は同じ色。
↓こういうのは存在しない。
●＋＋＋＋＋＋＋
＋○＋＋＋＋＋＋
＋＋●●○○＋＋
＋＋●○●○○＋
＋＋○●○○＋＋
＋＋○●●○＋＋
＋＋●●●●＋＋
＋●●●●●＋＋
・接続数が１の石から３個以下石を辿ると接続数が３以上の石がある。
↓こういう細長いのは存在しない
＋＋＋＋＋＋＋＋
＋●●●＋●●＋
＋●＋●＋＋●＋
＋●＋●●＋●＋
＋●＋●●＋●＋
＋●＋＋＋＋●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋
最後のは証明してませんが反例はまだ見つかってません。
どなたか検証お願いします。

>>314
＞・接続数が１の石とそれに接続している石は同じ色。
に対しては反例を挙げておきます。もう少し限定をかければ成立するかもしれませんが。
↓の石に関して。
●＋＋＋＋＋＋＋　→　●＋☆＋＋＋＋＋
＋●＋＋＋＋＋＋　→　＋○＋＋＋＋＋＋　
○○○○○○＋＋　→　○○○○○○＋＋
＋＋●○●○○＋　→　＋＋●○●○○＋
＋＋○●○○＋＋　→　＋＋○●○○＋＋
＋＋○●●○＋＋　→　＋＋○●●○＋＋
＋＋●●●●＋＋　→　＋＋●●●●＋＋
＋●●●●●＋＋　→　＋●●●●●＋＋
＞・接続数が１の石から３個以下石を辿ると接続数が３以上の石がある。
の具体例に関しては（極端な例だからかもしれないけど）他の点からも指摘できます。
＋＋＋＋＋＋＋＋
＋�C�B�A＋●●＋
＋�D＋�@＋＋●＋
＋●＋●●＋●＋
＋●＋●●＋●＋
＋●＋＋＋＋●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋
2と3の順番は逆になるかもしれませんが…とりあえず5は挟む物がないので置けません。
ついでに、最後のは分かりにくい気がするので言い換えを提案します。
・接続数が１の石から接続数が２以下の石だけを辿ると２個分までしか辿れない。

>>315
ああ、なるほど。
もうちょっとよく考えて色んなふるいを作りたいと思います。

反復深化で黒石ゲーム全探索してみました。
黒石ゲーム 7手目 679,519,480パターン, 最大36分岐
オセロ 7手目 55,092パターン, 最大12分岐
オセロ 11手目 212,260,880パターン, 最大18分岐
はい。

黒石ゲームで石数が４〜６４の範囲の一様な試行もやってみました。
データとかグラフを載せるとこが欲しいですね・・。

>>318
まだ形にもなっていませんが・・
よかったらお使いください。
誰もが編集者のwikiです
ttp://www9.atwiki.jp/othello/

Wikiｷﾀ━━━━(ﾟ∀ﾟ)━━━━ｯ!!

>>319
すばらしい。うれしいです。感謝です。ﾊﾟﾁﾊﾟﾁ
318のは今試行の数を増やしているところです。
終わってまとめたらアップします。

>>319
すません文字が小さくて読みずらいんですけど

さっき、Iリばーしで、63-0を達成。相手はわざとやってだ訳ではないだろうけど？。
ちなみに64-0って可能なのかな？

可能です。
昔やられた事があります

>>320
>>321
どもです。早速使ってくれた。
ありがとうございます。
>>322
ちょと直しました。

>>319 wikiいいね。乙です

>>314-315あたりを読んでて気が付いたが、
オセロの場合石を置くには最低挟める石と挟む為の石が必要なので、可能盤面は
「初期配置の中央４石を除き、全ての石は３個以上の列に含まれる」と言える。
なので>>314の下の図は、オセロでは有り得ないことが証明出来る。
（>>315の反例を一般化してみた）

黒石ゲームのルール、「隣８箇所のどこかに黒石がありさえすれば黒石が置ける」
というのを「２連続（以上）の黒石の延長上に置ける」とすればどうだろう？
そうすれば、黒石ゲームでも同様のことが言えるようになる。

10万回ランダムに棋譜を発生させてみた。パスは１手としない（必ず60手以内で終わる）
平均手数の積は1.4E+53
標準偏差も出して確からしさも出そうかと思ったが１手99%として0.99^60=54%なのでやめた。
パス、連パスによるゲーム終了は10〜16手目あたりと終盤に多く中盤は少ない。

手番---回数----最大--最小---総手数---Σ(総手数^2)--平均---標準偏差---パス--ゲーム終了
--1---100000-----4-----4-----400000----1600000----4.0000----0.0000------0-----0
--2---100000-----3-----3-----300000-----900000----3.0000----0.0000------0-----0
--3---100000-----5-----4-----466503----2198527----4.6650----0.8732------0-----0

--9---100000----15-----1-----755769----6092271----7.5577----1.6974-----72-----0
-10----99981----16-----1-----789548----6684874----7.8970----1.9073-----19----19
-11----99977----17-----1-----834035----7433175----8.3423----2.0992-----29-----4

-30----99952----24-----1----1202014---15378396---12.0259----2.8944------1-----0
-31----99951----25-----1----1185681---14989101---11.8626----2.8772------9-----1
-32----99951----23-----1----1192029---15133605---11.9261----2.9610------2-----0

-57----99950-----4-----1-----295764-----967274----2.9591----0.4936---2248-----1
-58----99948-----3-----1-----232387-----594419----2.3251----0.6372---4422-----2
-59----99916-----2-----1-----167192-----301744----1.6733----0.4472---9845----32
-60----98996-----1-----1------98996------98996----1.0000----0.0000--25951---920

>>326
＞黒石ゲームのルール、「隣８箇所のどこかに黒石がありさえすれば黒石が置ける」
＞というのを「２連続（以上）の黒石の延長上に置ける」とすればどうだろう？

それいいね。ずいぶん絞れました。

7手後の全棋譜数
オセロ / 黒石ゲーム / 黒石ゲーム２(>>326)
55,092 / 679,519,480 / 126,786,952

うーん。完全探索(反復深化)派としては、
黒石ゲームのようにゲームの一般化をしても
ノード数が増えて計算時間が増えるだけで、
(>>271式)の全棋譜数の上界設定に使うにしても
結局オセロの探索結果が12手まで求められるっていうことが
一番上界設定に寄与している気がする。。あたりまえか。

純粋な理論による上界設定には使えそうだけどね。

オセロ12手後 の棋譜数 1,939,899,208 譜 、最大着手数 20手 でした。
オセロ棋譜数上界更新。
1,939,899,208 * 48! < 2.4082 * 10^70

10手後から考えて1桁しか落ちてないなぁ…。
>>256の最大着手数の流れはもう終わったの？
これで最大着手数 33手って分かれば 順列計算のなかの
48*47*...*34*33 が全部 33 に落ちてさらに１、２桁上界、落ちるんですが。

>>329
最大着手可能数について考えてみました。

オセロに着手可能数47の盤面がある、と仮定する。
仮定条件、黒番とし、黒石は挟む石、白石は挟まれる石とする。
�@盤面にある石は17個以下である（64-47=17)
�A黒石（挟む石）１個に対し着手可能数は８（８方向）なので
47/8=5.875→盤上に６個以上の黒石がある。
�B白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので
47/4=11.75→盤上に１２個以上の白石がある。

�@の１７個以下と�A＋�Bの１８個以上は矛盾する。
故に仮定の「オセロに着手可能数47の盤面がある」は間違いなので
オセロの最大着手可能数は46以下である（証明終了）

もう少し条件を加えられればさらに減らせると思うのですが。

>>330は、もっと単純に出来ましたね。
330の条件�Aと�Bにより、着手可能数は
int(盤上の石数/3)*8以下になる（intは切捨ての意）
１２手目、１３手目は石数が16,17なのでint(17/3)*8=40
>>329の１２手目までを使わせてもらって
1,939,899,208 * 40 * 40 * 46! = 1.708E+70
１２手目の最大着手数20も入れて
1,939,899,208 * 20 * 40 * 46! = 8.540E+69

全探索（11手まで）してみたら>>260と微妙に違ってた。
[ 0] -> 1( 0)
[ 1] -> 4( 0)
[ 2] -> 12( 0)
[ 3] -> 56( 0)
[ 4] -> 244( 0)
[ 5] -> 1396( 0)
[ 6] -> 8200( 0)
[ 7] -> 55092( 0)
[ 8] -> 390216( 0)
[ 9] -> 3005320(228)
[10] -> 24571192(356)
[11] -> 212260296(6384)
括弧内はゲーム終了数（内数）。9手目でのゲーム終了数分を足すと10手目も同じなんだけど…
Wikiにある11手目のデータも9手目・10手目での終了分を足せば同じ結果に。

…私が悪いの？

12手まで出したついでによんけたﾀﾝの分岐平均（どうやって出したの？）と比較してみた
手数平均分岐←の積実際の数誤差[%]
11440
2312120
34.664555561.785714286
44.36062392442.049180328
55.8582140013960.286532951
65.8361817082000.365853659
76.723554930550920.294053583
86.94363814113902162.256442586
97.5566288217030053204.097733353
107.900522770584245711927.328126368
118.376819074462821226029610.13645435
128.7781674356344193989224013.68817765
平均分岐数を単純に掛け合わせるのは危険っぽい。

ごめん>>333じゃ読めないね。Wikiに入れておく。

>>333
方法は>>165で、一万本試した結果すね。もっとちゃんと書こうとおもってます。
比べるならメモ04（284さん)のほうがいいと思いますよ。
12手目で86％ですか。。うーんやっぱきびしーですね。


メモ04の１２局目までの積は1696356961でした。
僕のと同じくらい誤差がありますね。
これは一体・・
あと24局から32局にかけて手数平均がギザギザです。面白いですね。

12手の全検索、というか1/4検索です。
初手は１手固定にして、全棋譜数、パス、終了数は結果を４倍しています。

|手|最大手数|　　全棋譜数　　|パス　　|終了　|
|-1|-------0|---------------4|-------0|-----0|
|-2|-------3|--------------12|-------0|-----0|
|-3|-------5|--------------56|-------8|-----0|
|-4|-------6|-------------244|-------0|-----0|
|-5|-------9|------------1396|-------0|-----0|
|-6|------11|------------8200|-------0|-----0|
|-7|------12|-----------55092|-------0|-----0|
|-8|------14|----------390216|-------0|-----0|
|-9|------15|---------3005320|------24|-----0|
|10|------16|--------24571192|-----228|---228|
|11|------18|-------212260296|-----932|---356|
|12|------20|------1939892240|----7396|--6384|
ゲーム終了の考え方は>>332に近いですが
10手目が打てない場合に10手目の終了としています。
(332とは１手ずれる）

実は一晩かけて13手目までやったんですが結果がおかしいです。
変数は８バイト用意しておいたんですが、出力をミスったかもしれない。
|13|------21|------1249899332|---35588|-16384|

ちょっと遅れたかな。一応こちらも13手探索終了
64bit整数を使ったつもりなので出力は大丈夫なはずです。

|手|　　全棋譜数　　|終了　　|
|-1|---------------4|-------0|
|-2|--------------12|-------0|
|-3|--------------56|-------8|
|-4|-------------244|-------0|
|-5|------------1396|-------0|
|-6|------------8200|-------0|
|-7|-----------55092|-------0|
|-8|----------390216|-------0|
|-9|---------3005320|-----228|
|10|--------24571192|-----356|
|11|-------212260296|----6384|
|12|------1939892240|---16384|
|13|-----18429768516|--299624|

ゲーム終了の考え方は10手目を打った後に両者が置けなくなったら10手目の終了としています。
確かに変ですね。改良します。

>>337
乙です。12手目まで一致してますので安心しました。
ゲーム終了の考え方は336と337(332初出)のどちらが良いでしょう？
私の場合(336)はプログラミングの都合だけだったので、他の皆さんの意見も聞きたいです。

>>333-335手数平均の積と実数の誤差ですが
これは平均の算出誤差というより手法としての誤差でしょうね。
全検索で手数平均を算出しても同じくらいの誤差があるでしょう。
１２手で１４％の誤差で、手が進むにつれて誤差は大きくなるでしょうし
平均１０手で２０％の誤差があるとして0.8^(60/10)=0.26
６０手目で９９％（実数との割合が１００倍違う）としても
10^51〜10^56くらいではないでしょうか。（もう少し大きくなるかもしれないが）
まあ、これくらいざっくりした数値でしかないのは確かですが、無意味な値ではないと思います。

ごめん。>>336の表の３手目のパスの値 8 は 0 が正解です。
（動作チェックルーチンの消し忘れ）
>>337も表はコピペみたいだから３手目の終了は0ですね。
すみませんでした。

さらに進めて14手探索しました。>>336と同じく1/4探索ですが。
|手|分|--全棋譜数--|--パス-|--終了-|
|-1|-0|-----------4|------0|------0|
|-2|-3|----------12|------0|------0|
|-3|-5|----------56|------0|------0|
|-4|-6|---------244|------0|------0|
|-5|-9|--------1396|------0|------0|
|-6|11|--------8200|------0|------0|
|-7|12|-------55092|------0|------0|
|-8|14|------390216|------0|------0|
|-9|15|-----3005320|-----24|------0|
|10|16|----24571192|------0|----228|
|11|18|---212260296|----576|----356|
|12|20|--1939892240|---1012|---6384|
|13|21|-18429768516|--19204|--16384|
|14|22|184042835408|--67536|-299624|
私は全探索は一旦この状態で手を引こうと思います。
時間がかかる（↑で200分弱）割になかなか前へ進めないので。
n手目のパス数と終了数はn-1手目を打った後の状態で
パスをする必要がある局面数と終わった局面数です。
これらは全棋譜数には内数として含まれてますが
パス数と終了数とは排他的に数えてます。

>>336
４バイト符号付き整数でカウントしちゃってるんじゃないかな。
ちょうど 2,147,483,647 が４バイト符号付き整数の最高値だよ。
俺も同じところで負の値が出ちゃったことがある。

>>284
すごーい。数学スレっぽくてかっこいいな。
wiki追加しとこ。

アンカー間違えた。>>330>>331 の話です

「手」を n=(盤上の石の数)-4 と逆に定義して、
１つパスが起きたらパス数p[n]を１つ増やし、
終局が起きたら終了数e[n]を１つ増やし、
棋譜数f[n]を求める >>293 の数え方がわかりやすいんじゃない？
「手」と盤上の石の数の対応が簡単につくし。
俺も >>293 と同じ結果の出るアルゴリズムが組めたよ。

>>331
＞>>330は、もっと単純に出来ましたね。
＞330の条件�Aと�Bにより、着手可能数は
＞int(盤上の石数/3)*8以下になる（intは切捨ての意）

うーん、この最後の int(盤上の石数/3)*8 が分からないや…。
>>330は理解できたんだけど。

13手1/4検索です。112分かかりました。
このまま14手をやると10倍くらいとしてほぼ１日かかるorz
>>340の14手200分は早いですね。すばらしいです。

|手|最大手数|-全棋譜数----|-パス-|-終了-|
|-1|-------4|------------4|-----0|-----0|
|-2|-------3|-----------12|-----0|-----0|
|-3|-------5|-----------56|-----0|-----0|
|-4|-------6|----------244|-----0|-----0|
|-5|-------9|---------1396|-----0|-----0|
|-6|------11|---------8200|-----0|-----0|
|-7|------12|--------55092|-----0|-----0|
|-8|------14|-------390216|-----0|-----0|
|-9|------15|------3005320|----24|-----0|
|10|------16|-----24571192|---228|---228|
|11|------18|----212260296|---932|---356|
|12|------20|---1939892240|--7396|--6384|
|13|------21|--18429768516|-35588|-16384|
パス数に終了数は含まれてます。
全棋譜数にパス数は含まれてます。

>>341
カウントは８バイト整数でやってたんだけど、出力が４バイトだったorz
修正したものが>>345です。

>>344
＞うーん、この最後の int(盤上の石数/3)*8 が分からないや…。
330の条件�A黒石（挟む石）１個に対し着手可能数は８（８方向）から、
�A’着手可能数８の時、黒石は最低１個必要。
�B白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので
�B’着手可能数４の時、白石は最低１個必要。
よって着手可能数８の為には最低限、黒石が１個白石が２個の計３個必要。
なので盤面の石で３個セットがいくつとれるか（int(盤上の石数/3)）に
着手可能数８をかけました。

>>341
なるほどー。理解しました。ありがとう。
あ、1/4探索って対称性使ってるから正確だったりする？
１手目４着手できるけど１つしか探索しないっていう方法かな？

とりあえず週末出かけるので13手目の探索かけっぱなしにしときます〜

>>347
1/4探索は、初手４手のうち１手を決め打ちして以下を探索してます。
第１手を打った形は対象形であり、盤の６４枡すべてが１枡対１枡に対応するので対象性が証明出来ますね。

>>338の平均手数の積と実数の誤差について考えてみました。
参考データをWikiにＵＰしました。５手目まで全349棋譜です。
ttp://www9.atwiki.jp/othello/pages/29.html
この棋譜がすべて同確率で発生するとすれば発生確率は1/349です。
しかし実際は違います。
初手F5に対してF4、D6、F6の選択肢は各々1/3です。
これはコンピュータで乱数打ちする場合はもちろん、
人が打つ場合も選択肢は３つですから、1/3です。
（もちろん人それぞれ有利な手を考えて打ちますが、選択肢が３であるのは変わりません）

それを踏まえて棋譜�@F5(3)F4(5)C3(6)C4(6)B3と�AF5(3)F6(4)D3(5)C3(4)B3の発生確率を比べてみます。
()内数値は選択肢の数（着手可能数）です。
�@の発生確率は1/3*1/5*1/6*1/6=1/540
�Aの発生確率は1/3*1/4*1/5*1/4=1/240

発生確率が２倍以上違いますね。
こう考えると着手可能数の多い棋譜の発生確率は棋譜数の割合より少なくなりますね。

ということは「平均手数の積」は棋譜実数より少なくなる、ということでいいのかな？

>>348
そのことの間違いはわかりません。
ですが別の見方ができます。
全ての棋譜はおのおの、始点から一本道です。局面みたいに途中で合流するみたいなことはありません。
始点から見た場合、同じ局数の棋譜は同じように平等であるので、その道が選ばれる確率は平等のはずです。

ということが成り立つと思います。

>>349あ なんかすごい間違ってるかも。

分岐数だから相加平均（算術平均；一般的な「平均」のことで、足し合わせてnで割る）よりも
相乗平均（幾何平均；掛け合わせてn乗根を取る）の方が良いのでは？と思って試した結果を
5手検索２に書いたけど、ランダム棋譜からの推測の正確性を計るという意味だと
5手検索の方が良かったかもね。

「平均手数の積」の問題点を整理してみます。
(1)ランダム棋譜の発生確率が全て同じではない事>>348
(2)全棋譜の平均手数を出しても誤差があること>>Wiki５手検索２
>>333-335の指摘での誤差は、この両方が入ってると思われます。他にもあるかも。

>>349 これは(1)の話しですね。
私も最初、同じような誤解をしてました。333の指摘で考えていて348に気が付きました。
多分、乱数によらず過去の棋譜を集めてもこの問題の解決にはならないと思われます。
むしろこのあたりを考慮したプログラムを組むか、ですね。
その着手以後の手数を数えて乱数発生確率を変えるか、ですが全検索と同じことになってしまいます。
せめて数手先までの着手可能数で乱数発生確率を使うかですかね。

>>351 これは(2)の話しですね。
＞5手検索２に書いたけど、ランダム棋譜からの推測の正確性を計るという意味だと
＞5手検索の方が良かったかもね。
いえ、ランダム棋譜からの推測だからこそ5手検索２で良いと思いますよ。

なるほど５手目着手可能数の誤差が一般平均1.129(12.9%)、幾何平均1.0570(5.7%)。
一般平均よりは誤差が少なくなってますね。

ただ千回も試行すれば相乗の数値がオーバーフローします。これはプログラミングの問題？

>>352
解釈ありがとうございます。私は考えるのが苦手なもんで。

プログラム中で平均とっているなら、log(分岐数)の総和を取って
1/n掛けた後にexp(その結果)でいかがでしょ？
単純にかけ算してたら6手全探索でもオーバーフロー起こしましたし。

>>352 の続き、５手検索２で調和平均もやってみました。
５手目までは良い感じですが６手目で0.8923(-10.8%)
うーむ・・・

>>353
＞log(分岐数)の総和を取って1/n掛けた後にexp(その結果)
エクセルで試したんですが、答えが合いません。。
logとかexpが、あんまり解ってないので・・・orz

>>354
説明不足で申し訳ない。エクセルでやるならlogはln()を使って下さい。Cのプログラム中ならlog()でOKです。
それ使ってやった結果を、普通に掛けてn上根取った結果（≦5手目）と比較したら
1手目：4.88498E-15
2手目：5.32907E-15
3手目：1.77636E-15
4手目：8.88178E-16
5手目：8.88178E-16
と、十分小さいと思われますんで。

更に説明不足。↑の数は「普通に掛けて…」と「log()の総和を…」とで出た結果の差の絶対値

完全探索の話
>>348の話を踏まえて対称形による枝刈りを一般化したらいいかな。
対称形の盤面をみつけたときは対称形の中のひとつだけ深化して
あとで k 倍すれば探索空間が減らせて探索がより高速になりますね。
対称形（とその復元のための倍率 k）は
90°回転対称(k=4), 180°回転対称/鏡面対称(k=2)、非対称(k=1)
ですね。
ちょっと入れてみましょう。分岐が減って速くなるか、
あまり対称形が発生せず対称形の判定に時間がかかって逆に遅くなるか見ものです。

っていうかもうみんなやってるのかもしれない。。

>>357
重複チェックと似てますね。ただk倍ってのは簡単にはいかない気がしますが。
１．探索した盤面が初めてなら、探索後に分岐数と一緒にDataBaseに登録する。
２．これから探索しようとするものと(対称形で)同じ盤面がDBにあれば、その分岐数を使う。
ってのが実際的かな？正確には盤面の状態と黒番・白番って情報もいるけど。

>>358
重複チェックってやってます？
盤面多いんで結局10手以上になるとメモリ的にDBの実装が難しいと思うんですが。

０．深化の際に累計対称倍率Kというものを再帰関数の引数として与えることにする。
１．0手目、K=4を引数に与えて深化開始。
２．再帰関数中、対称形チェック。形によってその盤面の倍率 k を求める。
３．K*k を次の再帰関数の引数に与えて深化。
４．試合終了または深度最大になったらKの値を棋譜数カウントに加える。
５．バックトラックの際には既に深化した分岐の対称形には手を出さない
（たとえば、x軸鏡面対称なら盤面の半分より以東の探索をカットする）

これでどれだけ深い階層の探索にもメモリを使わなくて済みます。
（直系の盤面データ(最大60個)と対称倍率とバックトラック位置だけスタック領域として持てばいいので）

>>352
(1)について
今までずっと>>349が正しいと思ってました(´Д｀ｌｌｌ)
やだわもう。

これから
一つの棋譜からなる手数の積の分布を把握し、
そこから棋譜のツリーがどうなっているのかを調べたいと思います。
なにかヒントがあるかもしれません。

>>355-356
解説ありがとう。エクセルで結果が同一となるのを確認できました。
プログラムのほうは、まだですがその内やってみます。

>>359
なるほど、とある盤面の対称形を使うわけですね。
０手目（初期配置）で言えばｕ軸対称(k=2)、ｖ軸対称(k=2)、180°対称(k=2)ですがk=4ですよね。
ｖ　　　|
　＼＋＋＋＋／
　＋＋＋＋＋＋
＿＋＋○●＋＋＿ｘ
　＋＋●○＋＋
　＋＋＋＋＋＋
　／＋＋＋＋＼
ｕ　　　|ｙ
ｕ軸＆ｖ軸　あるいは　ｘ軸＆ｙ軸　が成立する時は180°対称は無視する必要があります。
また、ｕ軸対称の時、ｕ軸上に打てる場合もk=1になります。（ｖ軸も同様）

>>360
＞一つの棋譜からなる手数の積の分布を把握
おお！実は同じようなことを考えてました。
「平均手数の積」ではなく「ある棋譜の手数の積の平均」のほうが、
実際の数に近いのではないか、と思い始めてた所です。

>>361
ttp://www9.atwiki.jp/othello/?cmd=upload&act=open&pageid=24&file=seki-honsu_1.jpg
どう分析したらいいのやら。。

比べるものとして次のものも作ってみましたが。。
どうしましょう。
ttp://www9.atwiki.jp/othello/?cmd=upload&act=open&pageid=24&file=%E3%83%9C%E3%83%BC%E3%83%AB.jpg

いろいろな形のツリーがありますが、棋譜のツリーはどんな形をしているんでしょうね。

昔のプログラムで、今その結果が残ってる訳じゃないんだけど、
>>224（これ、私です）の2)の方針ですかね？

>>363
そです。
ただ今回は平均はとりません。
仕上がった一本の棋譜のそれまでの手数の積を一つのデータとしてグラフを作りました。

842さんがいっていた手数の積が小さい棋譜ほどランダムに棋譜を作ったときに生成されやすい。
という理論にもとづいて
さらに実際は手数の積が大きくても、そういった棋譜が多く存在していればそれだけ手数の積が大きい棋譜が選ばれ、それだけ理論とズレた結果になるのではないか。
と思いました。

そこから
こんどは棋譜のツリーはどんな形をしているのか。という分析をしてみようとおもいました。

けどわかんなす。
f^_^;

>>363
224の2)はまさにそうですね。既出でしたか。

>>364
ある棋譜の発生確率＝1/(手数の積)と置くと棋譜数は結果の相加平均で良いと思われます。
以下、その理由です。

全棋譜数がｍとして各々の(手数の積)をA1〜Amと置きます。
ランダムに発生した棋譜がA1である確率は1/A1。
試行回数をＸと置くとA1の発生回数はＸ*(1/A1)。
またA1が発生した(手数の積)のトータルはA1*(Ｘ/A1)=1*Ｘ。
A2〜Amまでも同様なことが言えるので総トータルはm*Ｘ
よって全棋譜数ｍ＝総トータル/Ｘ（相加平均）

いかがでしょう？　>>362の画像を参考にさせていただきました。
ただしサンプルをとる場合は、選択肢の分岐を一様な乱数にしたほうがいいでしょうね。

棋譜のツリーの形は５手検索が参考にならないでしょうか？

対称性の話
手数tに対して対称形がいくつ出てくるかを調べてみました。
t=1 x= 0 y= 0 u= 1 v= 1
t=2 x= 0 y= 0 u= 0 v= 0
t=3 x= 0 y= 0 u= 0 v= 0
t=4 x= 0 y= 0 u= 0 v= 4
t=5 x= 0 y= 0 u= 4 v= 0
t=6 x= 0 y= 0 u= 0 v= 0
t=7 x= 0 y= 0 u= 0 v= 0
t=8 x= 0 y= 0 u= 0 v= 60
t=9 x= 4 y=14 u=88 v=152
注:実装上の関係からv軸u軸に関しては>>361と比べて逆になっています。

8手目から結構でてきます。
またこのチェックを入れたコストは9手全探索で0.2秒でした。
入れた方がいいかもしれません。

>>356
全く同じことを書かせて下さい。

値Ａにその発生確率をかけ、それらをすべて足したものを　Aex とします。
この　Aex というのは、手数の積の期待値です。
(exはexpectationからとったもので、正しい表記ではないとおもいます)

Aex =
A1*(1/A1) + A2*(1/A2) + A2*(1/A2) + ・・・ + Am*(1/Am) = m

です。つまり Aex は　棋譜数m そのものです。

一回のランダム選棋譜で選出される棋譜の手数の期待値の和は、　Aex です。
二回のランダム選棋譜で選出される棋譜の手数の期待値の和は、　2*Aex です。
Ｘ回のランダム選棋譜で選出される棋譜の手数の期待値の和は、　Ｘ*Aex です。

Ｘ回のランダム選棋譜で選出せれる棋譜の手数の期待値の和とは、総トータルのことです。
つまり、
　総トータル/Ｘ　= m

>>365
でもこれでは誤差の説明がつかなくなります。
見直すべきところは
手数の積Ａ１の発生確率が　（1/Ａ１）　であるといったとこでしょうか。。

>>366
おつです。対称性局面は後々手分けして探索するとき、大切になってくるとおもいます。
げっへっへ〜

>>368
>>348での誤差の話しは「平均手数の積」の時の話しです。
今回「手数の積」の相加平均を採れば誤差が無くなるのではないか、ということです。
＃もちろん乱数発生による誤差は残りますが。
100万回で試した結果をWiki「メモ05」に入れておきました。
全検索で出ている14手目まで、かなり良い結果になってると思います。
最終（60手目）結果が6.5E+54と、>>224とは少し違いますね。。

293氏に折角、相乗平均の方法を教えて貰ったのに使わなくなってしまいました。すみません。

>>365 >>367 にある相加平均を取る証明はその通りだと思います。
考えなく相乗平均とか言い出して申し訳ないです。

敢えて100万回程度（10の54乗からすれば「たかが」程度）のシミュレーションで
誤差が出そうな点を挙げれば

＞ランダムに発生した棋譜がA1である確率は1/A1。
＞試行回数をＸと置くとA1の発生回数はＸ*(1/A1)。

この 1/A1 が本来 1e-50 程度のはずなので X*(1/A1) も 1e-40 を上回る棋譜が
そうそうあるとは思えません。それが 1 （ものによっては2以上） まで格上げ
されることによる誤差が無視できない程度までに大きいということでしょうか。

>>224 との差異もその辺りが原因かと思います。本当は時系列でグラフを出すなり
定期的に中間結果をアウトプットして平均値の収束状況を見る必要があると思いますが。

まずは一定回数毎に平均値を出して、グラフプロットしてみます。

>>369>>370
毎回後進的レスすまんす。
やとわかった！
平均手数の積では、>>352の(1),(2)が問題となってくんですが、
手数の積の平均は、>>352の(1)が消えて(2)みたいな計算誤差・理論と事象の確率誤差だけが問題となるんですね。

期待値という言葉をつかって平均手数の積を正確に説明するのはややこしいですが。。

僕はこの二つほとんど同じ結果が得られるものだと思ってました。
全然ちがうんですね。

>>224
293さんごめんなさい。
いまさら訂正させてください。
>>167は　1) の方（手数平均の積の方）です。
僕本人なので間違いありません。
あのときは「同じようなもんだからいいか。。」と思って言いませんでした。

10時間をかけて取った6億回実験分の平均推移を表すグラフやデータをWikiにうｐしたいんですが、どうしたらいいですかね？＞よんけた

>>373
ファイルをアップロードするのは、ページに添付するという形をとります。

まずファイルを添付したいページを開きます。
一番下に　|新規作成|編集|差分|バックアップ…　とあるのでその中のアップロードを
クリックして下さい。
参照ボタンをクリックし、ファイルを選択後、submitボタンをクリック。
これでファイルをアップしたこととなります。

そしてページに、アップしたファイルのアドレスを書き加えればＯＫ。
メモのアップロード練習のページを参考にして下さい。

何か質問があればまたお聞きくだせえ。
アップロードする一つのファイルは１Ｍｂまでなので、気をつけて下さい。

対称性の盤面数、ちょっと計算方法が間違っていたので訂正。
t,u, v, n
1,1, 1, 4
2,0, 0, 12
3,0, 0, 56
4,0, 1, 244
5,1, 0, 1396
6,0, 0, 8200
7,0, 0, 55092
8,0,12,390216
t=手数、v(,u)=v(,u)軸対称な盤面数、n=全棋譜数

これなんですが、対称性を用いた枝刈りのコスト削減が
どれだけ深い手数まで調べても1/4にしかならなかったんですよね。
よく考えてみると、4手目にひとつ対称な盤面がでてきて、
これ以降のこのノードの探索範囲は1/2になるんですが、
すでに棋譜数が244もあるので、ひと枝だけがコスト1/2になっても
全体の計算量は243/244にしかならないんですよね。
結局うまくコスト削減できてるのは１手目のuv対称の1/4だけで、
それ以降のはほとんど無視できちゃうんです。
ってことで「対称性による計算量削減は１手目しか意味がない」
というのが今日の私の結論でした。

>>371
後進的なんてとんでもないです。疑問点はどんどん言ってください。
それに対してまた、色々考えることが大切ですから。
その結果「手数（分岐数）の積の平均」を思いつくきっかけにもなっています。

>>373
Wiki見ました。３億６千万回ですか！しかも10時間で！すばらしいです。
私は100万回で40分掛かったのにｗ（私のプログラミングが下手ですね）
概算値としての6.449E+54は１つの答えですね。

>>375
対称性を用いた枝狩りの有効性は低いですか。実は期待していただけに残念。
今、黒石ゲーム２で対称性の枝狩りをやってみようかと考えてます。
オセロの全(1/4)探索よりノードを減らせれば、各手数での最大着手可能数を探索できるかな、と考えてます。
まあ、既に全探索で14手目最大22着手が出てるので、無駄になる可能性大、ですが。

３０個空きにおける局面数って最大何通りくらいあるんでしょうか？
６４個のマスの中に白、黒、空きマスを
白＋黒＝３４個、空きマス＝３０個を満たすように
それらを配置すると考えるといったい何通りくらいなんでしょうか。

>>377
中央４個は確定として、６０マスにｎ個の石を置く場合は60!/(60-n)!/n!
n=30の時60!/(60-30)!/30!=1.18E+17
３４個の石の白、黒のパターンは2^34=1.72E+10
これらを掛け合わせて2.03E+27通りくらい

最大は石４４個の時の7.37E+28通り

>>378
ありがとうございます。
2.03E+27通りとは自分の予想を遥かに超えた数でした…。
コンピュータリバーシでは最善と思われる進行で進んだ場合、
結果がほぼ引き分けに近い状態になるわけですが
このときの３０個空き時では経験上、白と黒の数の割合が
２：３〜３：２付近になるっぽいので、そのくらいの割合のときの
３０個空き時の勝ち負け判定ソフトを別途作成しようかと思ったのですが
あまりの数字にこれは断念したいと思います。
無謀でした…。

>>376 秘密にする必要は全くないので、プログラムをWikiにうｐしました。
分岐数の積の平均からどーぞ。何かしら、参考になれば。

>>380おお！すげい！ つ遂にッ！！！

>>379
正解率がどんなもんになるか知りませんが、
SVMなんて使ってはいかがでしょう？
教師役になる棋譜が山のように必要ですが。
SVM=Support Vector Machineです。細かくはググって。

このスレ面白そうですね。
まだ全レス読んでないので、後で見てみようと思います。

スレ内容に相応しい話題かどうかはわかりませんが、
前にランダムに対戦させて勝率を調べるプログラム書いて動かしてみたら、

先手勝ち46%
後手勝ち50%
引き分け4%

くらいで後手の方が有利だったと思うのですが、
人間同士ではどうなんでしょうかね？
戦歴の統計みたいなものがどこかにあると良いのですが…

>>380
ありがとうございます！
見せていただきました。目から鱗がいっぱいですｗ
他人のソースを見せてもらうことはなかなか無いのでとても勉強になります。
とくに私、盤面は素直に２次元配列使ってました。
これをすると処理が全て２重ループになるんですよねorz

>>383
1977年〜2005年に行われた人間同士の対戦の棋譜54049個で調べてみました。
先手(黒)勝ち47.6%
後手(白)勝ち49.7%
引き分け2.7%
平均32.0-32.0
WTHORフォーマットの棋譜を↓からダウンロードして使いました。
http://www.ffothello.org/info/base.php

>>385
人対人だと先手勝ちが少し多いのですね。

棋譜のサイトがあるとは知らなかった。
何かしらの参考に出来そうです。

なんとなく参考になりそうなページをみつけました
http://dais.main.jp/reversi/
既出かな？

空いてるマシーンを見つけたので、タラタラと15手探索やらせました。
余分な計算を色々削除することでそこそこの高速化を図りましたが、34時間50分かかってます。
（ちなみに全く同じプログラムで（手違いで計算させた）14手探索が3時間36分でした。）

15手探索結果だけ。16手探索は予想時間が10日以上かかるので流石に無理です。
15手目の最大分岐数：23
15手目の盤面数：1891844432704
15手目でパスが起こる盤面数：1092168
15手目を打てずに終わる盤面数：887364

>>388
お疲れです。うちのより１０倍速いですねｗ
さっき14手の結果が上がってきたのですが40時間かかってました。
計算しながら普通にパソコン使ってますが。
12手までは同じ速度だったのにねぇ

フフフ、あの12手検索から微妙にプログラムを変更してるんですよ。

n手目の着手可能数をe(n)とすると
e(n+1) <= e(n) + 5
なぜなら、着手可能数が一番増えるケースは、

□□□
□★□
□□●

の★のところに打ったときであり、●の隣を除去した５つの□マスであるから。

これから、15手の最大分岐数=23より、
e(16) <= 23+5*1 = 28
e(17) <= 23+5*2 = 33
e(18) <= 23+5*2 = 38
e(19) <= 23+5*2 = 42
e(20) <= 23+5*2 = 41
これ以上は単純な空マスの数の方が小さくなるので
1891844432704 * 28 * 33 * 38 * 42 * 41! = 9.3333 * 10^67

Allisによる概算上界 10^58 まであと9桁です。
http://dais.main.jp/reversi/solve-reversi.html

>>391
Allisの論文を探して見てみましたが、オセロについて書かれている内容は大石さんの書かれていることとほぼ同じです。
（あとは世界チャンピオンに勝ったのがいつ頃とか、今ではプログラムに勝てる人間はいないだとか）
というより大石さんはAllisの論文のオセロ部分を翻訳されたのでは？

で、何を言いたかったかといえば、その中で棋譜数（ゲーム木の大きさ）に関してはあくまでも予測の概数で、根拠のある
上界は示されていないということでした。
状態数に関する研究も、方法としてはこのスレの方が上っぽい(2マス連続の先にしか置けないという考慮が書かれていない)ですし。
こっちは概数出していませんけどね （ﾉ∀｀）ｱﾊﾊ

黒石ゲーム２の完全探索を盤面対称性を考慮してやってみました。
９手までで47分。
|手|最大手数|手数--------|xyuv|xy---|90r--|uv---|x-----|y-----|u-----|v-----|180r--|Non------|
|-1|------12|----------12|---1|----0|----0|----0|-----0|-----0|-----0|-----0|-----0|--------0|
|-2|------13|---------152|---0|----0|----0|----0|-----0|-----0|-----1|-----0|-----0|--------1|
|-3|------16|--------2048|---0|----0|----0|----1|-----2|-----1|-----2|-----1|-----1|-------12|
|-4|------17|-------29444|---0|----0|----0|----0|-----0|-----0|----12|-----5|-----0|------198|
|-5|------20|------451376|---2|----3|----5|----5|----38|----28|----60|----38|----24|-----2765|
|-6|------20|-----7354680|---0|----0|----0|----0|-----0|-----0|---439|---267|-----0|----43038|
|-7|------22|---126786952|---0|----0|----0|--221|--2143|--1779|--3196|--2307|--1692|---693109|
|-8|------24|--2300515224|---0|----0|----0|----0|-----0|-----0|-30214|-20625|-----0|-11954263|
|-9|------24|-43708282280|1779|-5871|-8399|-8410|164331|139821|280193|210498|128439|215800673|
|10|------26|865297962824|----|-----|-----|-----|------|------|------|------|------|---------|
xyuv：Ｘ軸、Ｙ軸、Ｕ軸、Ｖ軸の４軸に同時に対称な盤面数
xy：Ｘ軸、Ｙ軸の２軸に対称
90r：90度回転に対称（表現がおかしい？90度回転しても同じという意味）
uv：Ｕ軸、Ｖ軸の２軸に対象
x： y： u： v： 各々１つの軸にのみ対象
180r：180度回転に対称
Non：対称性無し
以上は全て、排他です。

>>391
着手可能数の増加が最大５というのは黒石ゲームの場合ですね。
その値とオセロゲームでの15手目最大23を単純に足すのはマズいのでは？
オセロには黒番・白番があるので。
通常のオセロでも黒番の着手可能数が１〜２でも、白番は＋６（７〜８）以上になることは十分ありえますし。

全探索プログラムをC言語で書き直しました。
今15手やってます。
ぼくも13手までは確認しました。

気分転換に幅優先の全探索してみました。
手---棋譜数--盤面数-計算時間[s]
1--------4------4----0.00
2-------12-----12----0.00
3-------56-----56----0.02
4------244----240----0.02
5-----1396---1344----0.23
6-----8200---7572----3.31
7----55092--47624--261.99
データベースが１本リストなので遅いです。

t=手数,m=最大着手数,b=盤面数,ti=処理時間[s]
t= 1, m= 4, b= 4, ti=0.02
t= 2, m= 3, b= 12, ti=0.00
t= 3, m= 5, b= 56, ti=0.00
t= 4, m= 6, b= 240, ti=0.03
t= 5, m= 9, b= 1344, ti=0.06
t= 6, m=11, b= 7572, ti=0.31
t= 7, m=12, b= 47624, ti=1.53
t= 8, m=14, b= 302418, ti=15.45
幅探索ずいぶん速くなった。
パスのない8手までの完全な盤面。

15手全探索終わりました。
計算時間は32時間53分くらいでした。
Wiki更新しときます。

>>396
おつどす。
トランスポジションがなかなかの勢いで増えてますね。

終盤のほうで、「空き数＝最大着手可能箇所数」の局面が実際にあるか探してみました。
１〜２８個空きでは見つけましたが２９個空きからなかなか見つかりませんでした。
２９個空きで２８箇所の着手可能箇所がある局面に至る棋譜は見つけましたが・・。
N手--空数---棋譜
32----28----F5D6C3D3C4F4F6G6E6E7F7G5E3C5F3B3B4B5B6B7C7G2G3G4D7G7C6B2C2D2F2E2
33----27----F5D6C3D3C4F4F6G6E6E7F7G5E3C5G7F8D7C7B7B4B6B5B3C6G4G3G2C2B2D2F3F2E2
34----26----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8
35----25----F5D6C3D3C4F4F6G6E6E7F7G5E3C5F3B3B4B5B6B7C7G2G3G4D7G7C6B2C2D2F2E2A5A4A3
36----24----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8
37----23----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6A5A8G2B8A7A6
38----22----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8
39----21----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8G8
40----20----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1
41----19----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1G8
42----18----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1
43----17----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1G8
44----16----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1

45----15----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1G8
46----14----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3
47----13----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3G8
48----12----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5
49----11----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3G8H8H7
50----10----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7
51-----9----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5G8H8H7
52-----8----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7
53-----7----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7G8H8H7
54-----6----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5
55-----5----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5G1
56-----4----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5H1H2
57-----3----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5G1H1H2
58-----2----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5H1H2H3H4
59-----1----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5G1H1H2H3H4

２９個見つかりました。
N手--空数---棋譜
31----29----F5D6C4F4F6F3D3F7E6C5D7E3E2F2G7E7C3G6G5C7D2B4G3C2B2B3B5B6B7C6G2

盤面はどんな感じっすか？

>>403
>>402の29個のはこんな感じです。
F5D6C4F4F6F3D3F7E6C5D7E3E2F2G7E7C3G6G5C7D2B4G3C2B2B3B5B6B7C6G2
＋＋＋＋＋＋＋＋
＋●●●●●◆＋
＋●○○○●●＋
＋●○○○●＋＋
＋●○○●●●＋
＋●○○○○●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋
ちなみに僕が棋譜を並べたり盤面を作ったりする時はいつもこれ↓使ってます。
http://www2.next.ne.jp/~runoth/runoth.html

>>396
幅優先ではないんだけど、盤面数を出してみたら396と少し違いました？？
手---棋譜数--盤面数
1--------4------4-(100%)
2-------12-----12-(100%)
3-------56-----56-(100%)
4------244----236-(96.7%)
5-----1396---1288-(92.3%)
6-----8200---7092-(86.5%)
盤面の反転・回転による対称性は考慮していません。
つまり、>>274での上２つは同一、一番下は別物としてカウントしてます。
演算量を減らすには対称性も考慮したほうがいいね。

某数学に関する研究室所属の者です。
当研究室にてこのスレの話が話題となっています。
確定では無いのですが、新年度よりオセロの譜面数計算の本格研究が始まるかもです。
研究予算や研究に費やす時間などが関わりますので、最終段階での計画破棄の可能性もありますが、
仮に正式研究の許可が下されますと、大型コンピュータの使用などが可能となります。
また正式に決定したら詳しくご報告します。

おおっ

>>405に対称性を追加しました。あんまり自信ないので誰か検証お願いします。
手--A棋譜数-B盤面数-(B/A)
1--------4------1-(25.0%)
2-------12------3-(25.0%)
3-------56-----14-(25.0%)
4------244-----60-(24.6%)
5-----1396----322-(23.1%)
6-----8200---1773-(21.6%)

対称性の考慮は次の８パターン。
1)オリジナル盤面
2)Ｘ軸反転＝上下反転
3)Ｙ軸反転＝左右反転
4)ＸＹ軸反転＝180度回転
4)Ｕ軸反転（右下がりをＵ軸としてます。>>361とはu,vが逆）
6)Ｖ軸反転（右上がりをＶ軸としてます）
7)Ｕ→Ｘ反転（Ｕ軸反転したものをＸ軸反転）＝左90度回転
8)Ｕ→Ｙ反転＝右90度回転
発生した盤面が以前に出た盤面の上記８パターンのどれかに該当すれば同一、とします。

実際にそうするとデータベースが大きくなるので
過去の盤面の上記８パターンのハッシュ値を発生させ、その中の最小値（最大値でもいいけど）を記憶。
発生した盤面の８パターンのハッシュ値の最小値（あるいは最大値）と以前のを比べて同一性を確認してます。

プログラムでは各盤面のminhushだけ出して、エクセルでカウントしました。

忙しくてのぞいていなかった一ヶ月ちょっとの間に
なんだかすごいことに...

回転と裏返しで最大8つの盤面を
1つにまとめられることから思い付いたけど、
白と黒が反対の盤面もまとめることができるよね？

例えば、
＋＋＋＋＋＋＋＋
＋●●●●●●＋
＋●○○○●●＋
＋●○○○●＋＋
＋●○○●●●＋
＋●○○○○●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋ 次○が置く
と
＋＋＋＋＋＋＋＋
＋○○○○○○＋
＋○●●●○○＋
＋○●●●○＋＋
＋○●●○○○＋
＋○●●●●○＋
＋○○○○○○＋
＋＋＋＋＋＋＋＋ 次●が置く

は、最後の勝ち負けを反転させれば等価な局面といえる。
これは、データベースのメモリの節約に使えないかな？

これで最大16の盤面を1つにまとめることができる。

既出だったらごめん

業界最安値、激安特価のオトナのおもちゃ♪
ラブラブカップルに熟年夫婦、ＳＭ道具から勿論一人で楽しむアイテムまで大満足！
さらに女の子をオトせる必殺アイテムも多数あり☆（←これが超強力。悪用厳禁!!）

http://www.acport.com/index.cgi?id=1107601834

　マターリ光線！！
￣￣￣∨￣￣￣￣￣
　　 ∧_A_∧　　ｼﾋﾞﾋﾞﾋﾞ
　　（　・∀・）　/／＿＿＿∧＿＿＿∧＿＿
　　（ つ ｏ/つ。　ﾏ　　ﾀ　　〜　　ﾘ　　♪
　　ノ∧)∧）　＼￣￣∨￣￣￣∨￣∨￣
　（_＿）（＿）

http://etc3.2ch.net/test/read.cgi/denpa/1141996072/

>>409
石数が同じで手番が違うのでパスが関与しなければなりません。
その上で色違いの同局面になるということなので、
>>274のような例よりも存在割合は格段に低いと思います。
たしかに、わずかなメモリの節約にはなりそうです。

対称性はうまくいっても恩恵が1/4だし気休めにしかならないような。

>>412
確かに・・・
気休め程度ですね。

>>413
俺も基本はtrancepositionだと思います。
対象性も白黒の反転もささやかな後押しです。

7手までの全棋譜画像up
http://www9.atwiki.jp/othello/?cmd=upload&act=open&pageid=35&file=othello-7.PNG
アップロードするぺーじをまちがえました。。。

すいません。全然全部じゃないっすねｗ
printscreenじゃ画面に入りきらないの。

>>409
なるほど、白黒反転は面白いですね。>>412で言われてるように存在割合は少ないと思いますが、
例えば、パスがあったときに手番を替えるのではなく盤面の白黒を反転させれば
奇数手番は黒番、偶数手番は白番、と固定出来ますね。
これで手番情報を残す必要がなくなるのでその分ＤＢを減らせると思います。

・・・と、思ったけどこれだと勝ち負け情報がなくなりますね。棋譜数を数えるだけなら問題はないですが。

>>413>>414　「対称性」について私の考えを述べます。
「対称性」には２つあります。（と言っても２つ目を「対称性」と言えるかどうか・・・）
1)「ある盤面の対称性」
盤面自体が線対称、回転対称に当たる場合。
初期盤面などはこれに当たるので1/4探索などが有効ですね。
しかし初期盤面以降はあまり発生しないようです。(>>375)

2)「ある盤面と別のある盤面の反転、回転による同一性」
盤面Ａを反転、あるいは回転すれば盤面Ｂになる。
transpositionを考える時に>>274の３つめのような盤面を同一と考えるのに
>>408のような方法でどうか、ということです。

2)の方はあくまでtranspositionを考える為ですので恩恵が1/4に固定されるものではないと思います。
また手数が増えればtransposition自体増えて行くでしょう。
また2)の考えを入れれば1)の盤面は次の手で2)に吸収されるので1)は考慮しなくても良いと考えます。

2)の考え方のことを>>408で「対称性」と言ってしまったことで誤解を与えてしまったかもしれない。
すみません。

オセロって全部解析済みだったんじゃなかったの？
ってああ、試合結果数、か。

お邪魔様。

>>418
「全部解析」がどのようなものかはわかりませんが、
「最善の手」はわかっていませんよ。(終盤は別ですが)
試合結果の総数、試合途中の盤面の総数もわかっていません。

勝ち、負け、引き分けの３つしかない
ということくらいじゃないのかな。
わかっているのって。

sage方やっと知りました。ごめんなさい。

>>408
対称性の処理は私もほとんど同じことを行っています。

あと、この方法の問題は
８つのハッシュ値を作る計算時間、
８つのハッシュ値の中から最小値を見つけ出す計算時間が
大きいことかなと考えています。
高速化の方法を模索中です。

たかだかにしとけ！
たかだか64*63*62*61*・・・だ！
終了。
こんなことやるより最強のオセロ、将棋、囲碁の研究汁！

軟骨

>>417
それ自体が全く非対称な盤面がほとんどを占めているとして、
それの合同形は１面につき全部で８面あるとしよう。(x/y/v/u軸/0°/90°/180°/270°みたいな)
簡単化のために着手数はいつも N だとすると、
単純なT手の全棋譜カウントには Σ[t=1--T](N^t)*(着手判定) のコストがかかる。
そこで、この８倍の対称重複性を使うと、全棋譜カウントのコストはいくつになるのだろうか？
１手目でNのノードができ、対称重複性を考えると２手目のノードはN/8になる。
２手目ではN/8*Nのノードができ、対称重複性を考えると２手目のノードはN/8*N/8になる。
ってことはT手目までの総和は Σ[t=1--T](N/8)^t となって
全体で (1/8)^T くらいの削減率はでるのだろうか？
対称重複な面から出た対称重複面のことを考えると削減率も単純に1/8のべき乗で考えていいのだろうか？

>>420
確かに演算速度は問題ですね。
まあこの方法で探索ノードが減らせれば多少時間がかかっても価値はあるとは思いますが。
実際に効果が出るのは十数手以降かな、と思います。

>>423
あー、なんとなくですが分かった気がします。上手く説明出来ないけど、
＞２手目ではN/8*Nのノードができ、対称重複性を考えると２手目のノードはN/8*N/8になる。
この時点で２手目のノードはN^2/64ですが、これは全探索N^2の1/64になっています。
と言うことは、少なくとも1/8のtranspositionが発生していることになります。
つまり、全探索→同一盤面(transposition)の効果は未知数ですが
同一盤面(transposition)→合同盤面（反転・回転考慮）の効果は全体で1/8に限られる、
ということになるでしょうか？

とりあえず６０手後の盤面可能数は2^64=1.84E+19。
全棋譜予想が6.45E+54なのでtranspositionの効果は1/(3.5E+35)くらいはあるかと思われます。
それに合同盤面（反転・回転考慮）を入れても更なる効果は1/8にしかならない、と言う事かな？

話の流れとは関係ありませんが
棋譜数と盤面数と局面数の関係はこんな感じになると思います。
ttp://www9.atwiki.jp/othello/?cmd=upload&act=open&pageid=39&file=kihu_banmen_kyokumen.jpeg
局面数は最初棋譜数に沿ってますが、だんだん顕著に離れていき、
終盤は盤面数にくっつくような形になるとおもいます。

http://boinc.oocp.org/indexj.php
以前↑こんなのを見つけたんですが、誰か知ってる人居ます？
前からこれで何かの分散処理やってみたいなと思ってたんですけど、
苦手なのでまだよく理解してなくて。
こっち方面の得意な方居ますか？

よんけた氏
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の表現で困ったから。

>>427
S6=S5 * 4 までは理解したけれど、T6=T5 * 3 の反例です。
＞すでに○が２つ並んでいるラインにおくと、○が先にビンゴしてしまうのでそれ以外の3箇所におかなくてはならない
ですが、○が２個並んでいない場合は4箇所全て可能なので、単純に4-1とは出来ない。
↓　初手を除いた盤面の例
○＋＋
×××
＋○＋

×××
○＋＋
＋○＋

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

>>426
分散処理って全探索の場合はN台でやってもコストが1/Nにしかならないのよね。
全探索はいまの段階では使ってもまだまだ無理かなぁ。
あともうちょっと！ってところ、つまりあと10000倍くらい計算機が速いと
何かが解けるんだけどなぁという段階になったらいいかもね。
確率的概算値を求めるんなら、確率的分散がいまよりどれくらい抑えられるかな？

>>429
ふむふむ。参考になります。
僕は序盤の全探索があと4手くらいは多くできるかなくらいで考えてました。
>>406では大型コンピュータを使って何をするつもりなのかも気になりますね。

ところで16手全探索終わりました。
１８３時間５２分くらいかかりました。(Pentium4 2.4GHz)
今朝は終了直前でコンピュータがクラッシュする夢を見ました。
正夢にならなくてよかった〜
手数----棋譜数----最大着手可能数----ゲームオーバー----パス
01-----------------4-----4-----------0-----------0
02----------------12-----3-----------0-----------0
03----------------56-----5-----------0-----------0
04---------------244-----6-----------0-----------0
05--------------1396-----9-----------0-----------0
06--------------8200----11-----------0-----------0
07-------------55092----12-----------0-----------0
08------------390216----14-----------0-----------0
09-----------3005320----15-----------0----------24
10----------24571192----16---------228---------228
11---------212260296----18---------356---------932
12--------1939892240----20--------6384--------7396
13-------18429768516----21-------16384-------35588
14------184042835408----22------299624------367160
15-----1891844432704----23------887364-----1979532
16----20301281202588----25----13560800----18920488

>>430
最短１０手で完全勝ちっていうことですね！
棋譜の一例でも教えていただきたい

有名なところだと↓このあたりですかね。
F5F6F7F4D3E3F3G5H5
F5D6C5F4E3F6G5E6E7

エクセルをいじって、x手までの棋譜数（の予測）の近似値yを求める式を作ってみました。
教師信号には↓の「終了込みの平均」と、序盤の16手までは全探索の結果を使いました。
http://www9.atwiki.jp/othello/pages/32.html
x:手数 (1≦x≦60)
y:棋譜数
Sx=(8-SQRT(x+3))/2
Tx=(0.1222*(Sx^6)-1.1651*(Sx^5)+4.1648*(Sx^4)-4.4983*(Sx^3)-10.087*(Sx^2)+24.232*Sx+0.1977)*(1+(-1)^(x-1))/2
+(0.2029*(Sx^6)-1.8808*(Sx^5)+6.4413*(Sx^4)-7.8202*(Sx^3)-7.8104*(Sx^2)+23.641*Sx+0.25)*(1+(-1)^(x))/2
y=PRODUCT(T1:Tx)
xをが偶数と奇数の場合に分けてSxと教師信号の分布図を描いて、
それぞれの近似曲線を計算させてその式を使いました。
Txでは偶数手と奇数手でどっちかの項がゼロになるようにしてます。
xを直接代入するような高次式Txを作るよりも、
Sxみたいに何かをかませるほうが精度はいいみたいでした。
これの誤差は最大で2%くらいでした。

>>432
最短は9手で黒勝ちなんですね
表の見方は10手め打とうしたらゲームオーバーだったのが228局面
あったという事ですか

自分も参戦しようと、何も考えずに全探索書いたら13手までのが5時間かかりました。
このままだと14手の場合は2日がかりになりそうなので、簡単な枝狩りなんかを考えるかな。

このスレってレス数の割に内容が濃いので、まだ読みきれてません。
というか理解がorzという状況ですが…

>>430
丸一週間はすさまじい。。

>>428
がーん。そうですね。
もうちっと精進します。

代案
Tn、Snの定義を変えて、
Tn:×縦横ビンゴ、○は×と平行にリーチ
Sn:それ以外
とすれば続きの議論につながるけど、複雑だなー。

とりあえず、「Q6はQ5だけで表現可能か」を知るためには、
Tn と Sn の関係が必要。
まあ、オセロだと時間に対して可逆じゃなさそうなので、この手は使えないかも

>>256>>432
すごいね。
知り合いの学生さんがだした結果をgnuplotで近似したら、
2次関数（上に凸のね）で綺麗にfittingできたと喜んでいたけど、
（4x4,6x6と盤面を広げるとスケールが規則的に変化）

真値は係数が (log 2)/(log 3)=0.631 の倍数だったりしないかな？
10.087は大体2^4=16倍なんだよね。
根拠はかなりあてずっぽなんだけど、黒白空白の3進数で桁が8x8の数と
考えると底が3のlog2みたいな量が関係していると思うので

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

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

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

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

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

中島と松島じゃ中島ｼﾞｬﾈ？

>>438 のページ、日本語訳とかをWikiに書いてもいいんでしょうか。
まだ全く手をつけてないですが。

>>440
是非宜しくお願いです

まだ途中ですが、「○×ゲームの数値解析」みたいな名前で上げました。
意図的に、出来る限り意訳しています。醜い所・見にくい所があれば
適当に訂正なり要望なり言って下さい。

白が勝つ
黒が勝つ

で２通り

翻訳完了です。誤訳、解釈が分かりにくいところがあれば、指摘するか勝手に直すかしてください。

そういえば○×ゲームをマッチ箱でやらせる記事を読んだ気がする
学習していってだんだん強くなるっていうやつだった

>>445
これですか？
http://www.atarimagazines.com/v3n1/matchboxttt.html

確か日経サイエンスの別冊の記事じゃなかったかと記憶している
数学やパズル関係の

アタリのベーシックソフトが昔読んだ記事と同じかどうかは記事の
中身はすっかりアウト オブ メモリーなので判断できない

新年度の幕開けと同時にレスがつかなくなりましたね。

>>448
すみません。ネタ切れ中なので。
オセロの1手目で4箇所打てるのを数式で表現できないか考えたりしてます。

>>449
１つ思いつきました。
着手可能の為には挟む石と挟まれる石が必要なので
最大着手可能数は（挟む石）×（挟まれる石）。
初手は挟む石（黒石）＝２、挟まれる石（白石）＝２なので
最大着手可能数＝２×２＝４となる。

でもこれって、初手着手数４の証明じゃなくて初手着手可能数の上界の証明ですよね。
それにこれを一般化しても>>330の「46以下」は超えられないし。う〜む・・・

完全についていけなくなってきた馬鹿野郎に慈悲を･･･
現在、総出で行われている作業は全探索ととっていいのでしょうか？

>>451
このスレは全ての話題が現在進行で、
何時でもどの話題にレスしてもいいと僕は思います。
それをカバーするためにもwikiがあります。
人が少ないからこういうことが言えるのですが。。

以前話されていたグリッドコンピューティングなんだけど、
総手数を「数える」のは１００万台マシンをそろえても本質的な解決にならないよね
ってうちの分散処理の教授がいってました(泣

理由は１００万台では１００万倍にしかならないからです(結果をまとめない限り)
１００万倍位じゃ数え上げるの無理ですね

こんなスレが‥
オセロ有段、プログラム知識なしの俺だけど手伝える？

＋＋＋＋＋＋＋＋
＋○＋○＋○○＋
＋○●○●●○＋
＋○●○●●○＋
＋○＋●○＋○＋
＋●●＋＋●●＋
＋○○●●○○＋
＋＋＋＋＋＋＋＋
ランダムに局面発生させて、34箇所打てる局面発見
１手目から作れそうにないけど

○×ゲームを数式表現できたことで味をしめて、
4x4のオセロを数式表現しようと思う。

取り合えず4x4なら総手数数え上げられそうだから
プログラム作ってみます。

そこで聞きたいんだけど、両方パスが行われたときって
二回目のパスが起こったターンで終わりなの？
それとも、先にパスを行ったときに終わるとするの？
おせえて>>454さん達！

プログラム作る側から言えば、
後者の方がちょっとめんどい

過去のプログラム作った人達（私も含む）の間では
パスをターンに数えない形でやってました。参考までに。

>>454さん
大雑把なルールはみんな知ってるはずですが、↑のような
ちょっと深くなると明記しているサイトも見つけられません。
まずはルール説明をお願いできますか？

了解です。

　＋＋＋＋＋＋＋＋
　＋＋＋＋＋＋＋＋
　＋＋＋＋＋＋＋＋
　＋＋＋○●＋＋＋
　＋＋＋●○＋＋＋まず初期配置はこれで、先番は黒。
　＋＋＋＋＋＋＋＋ 打てる個所がある限り打たなくてはいけず、打てない場合はパス。
　＋＋＋＋＋＋＋＋ パスは何回してもよいし、打てるようになった再び打つ。
　＋＋＋＋＋＋＋＋64マス埋まるか双方が打てない状態（どっちもパス）の時に終局となる。

>>456
厳密には2人が互いに「パスです」と発言した時に終局だと思うけど、実戦では
どっちからともなく「終わりですね」みたいな会話で確認して終局になるから
楽な方で良いかと。

あとパスは慣例的には１手とカウントしないで必ず６０手以下で終わるようにしてます。

それから既出かもしれない情報だけど、オセロは終盤２４〜３０手は
読み切り可能です。つまり、PCは全ての枝を探索します。

>>459
一般的にWZebraなどの強いオセロプログラムでは、
中盤探索ではMPC(Multi Prob Cut)という枝刈りをしていますが、
終盤読みきりではαβ法で言われるαカットやβカットをしています。
つまり終盤の完全読みや必勝読みでも探索しない枝はあります。

>>457-458
ありがとうございます。
今僕個人が忙しいのですが、
時間を見つけて(パスを一手と数えない方式で)
作ってみようと思います。

しかし既に作っている方のプログラムの
変数を変えた方が早いと思いますので
僕は検証における信頼性向上の為に作ろうかなと思います。

256氏にお願いなんだけどいいかな？
>>310のソースまだある？もしあるならそれに中央４マスは常に石があるとして繋り割合出せないかな。
乱数発生後に中央４マスは石有りでマスクして１島状の確認をする。
これが出ればｎ手目の局面数の概算が出せると思うんだけど。
ｎ手目の盤面数(60!/(60-n)!/n!)に繋り割合を掛けて、それに白黒分布(2^(4+n))を掛ければ局面数になる。
各ｎ手目の局面数の累加がトランスポジションを考慮した時の計算量になると思う。

本当は繋り以外にもありえない局面を除外出来ればいいんだけどね。
あと、一様な試行が出来れば良いかな、と思って>>288の方法も考えてるんだけど上手いハッシュ関数が思いつかないorz

>>461
４×４オセロの棋譜数をだしてみました。
|手|最大手数|全棋譜数|--パス|終了|-黒勝|-白勝|引分|
|-1|-------4|-------4|-----0|---0|----0|----0|---0|
|-2|-------3|------12|-----0|---0|----0|----0|---0|
|-3|-------4|------44|-----0|---0|----0|----0|---0|
|-4|-------5|-----128|-----0|---0|----0|----0|---0|
|-5|-------5|-----436|-----4|---0|----0|----0|---0|
|-6|-------5|----1296|-----8|---0|----0|----0|---0|
|-7|-------6|----3784|----40|---4|----4|----0|---0|
|-8|-------5|----9756|---144|---8|----0|----8|---0|
|-9|-------4|---22152|---828|--20|---20|----0|---0|
|10|-------3|---41296|--2892|-308|--160|--148|---0|
|11|-------2|---58912|-10732|-808|--440|--356|--12|
|12|-------1|---53580|-25252|5332|-3260|-2072|---0|
|13|--------|--------|------|----|20748|27532|5300|
パス数に終了数は含まれています（内数）
ｎ手目が打てない時にｎ手目のパス、及び終了としています。
ですので13手目は12手まで打てたときの勝敗数です。
どなたか検証よろしくお願いします。

んー
数式表現ってなんだかなぁ。
○×でさえもあれだけ複雑じゃ数式で解く意味がないような気がする。
タカラのライツアウトを行列演算で解いたくらいの鮮やかさがほしいなぁ

>>464
確かにね
でもまぁ、やるだけやってみようかと。
盤面数は深さにあわせて指数関数的に増大しているから
数式の場合分けが深さに応じて指数関数的に
増大するようなら本質的には解決してないよね。

例えば深さが1増えるごとにそれぞれ場合を二つにわけなきゃならないなら、
単純計算で数式の数が2^60 = 1152921504606846976個となるので、
計算機に自動で推論させてもきついよね。
僕は計算機の推論が専門じゃないんでよくわからんけど。

ちょっと疑問に思ったことがあるんだけど
仮に、双方最善進行が見つかったとして最後までパスがなかった場合
第ｎ手目（ｎ=1,2,…,59,60）における局面において打つことが出来る
すべての場所を完全読みしたときの結果の和、又は平均をk(n)とおくと
Σk(n)=k(1)-k(2)+k(3)-k(4)+…+k(59)-k(60)≒0
が成り立つような気がするのですが実際はどうなんでしょうか。

例えばk(30)：第３０手目における局面において打つことが出来る場所を
完全読み（石差）したとき、０が１箇所、−２が２箇所、−４が３箇所…
あったとするとk(30)=０×１＋（−２）×２＋（−４）×３＋…
と一応定義してみたつもりです。

現段階ではｎの数が小さいときのk(n)を求めることは不可能ですが
ｎが大きいときのk(n)を求めることは可能です。
どなたか-k(60)+k(59)-k(58)+…を考察していただけないでしょうか。

あくまで疑問に思っただけなのでお門違いなことを言っていたら申し訳ない

最善ってこの場合なんだっけ

最善ってこの場合なんだっけ

やってしまった!

最善ってこの場合引き分けになることを想定した手順かと

勝てる場合は少なくともこれくらいの石差を保証できる、
負けるにしてもこれくらいに抑えられる、ということだと思う。
αβの結果でしょう。

>>462
遅くなってすみません。
中央４マスは常に石があるとして繋り割合を出してみました。
結果はWikiに置いときました。
http://www9.atwiki.jp/othello/pages/43.html

>>472
私の勝手なお願いでお手数をおかけしました。
すみませんでした。そしてありがとうございます。
早速、繋り割合を使って概算の局面数を出してみました。
http://www9.atwiki.jp/othello/pages/44.html

結果は5.10E29でした。これは推定の棋譜数6.45E54に比べると格段に小さい数値ですが
カウントするにはまだまだ大きすぎる数値ですねorz
>>430の16手検索は、ノード数2.03E13で183.8時間ですから4.62E18時間＝5.3E14年・・・。
しかも１手につき最大 5.9E28の盤面を保持しないといけない。
一体どのくらいの記憶容量が必要になるんでしょう。

６０手目の局面数の確認方法

６４個のセルすべて埋まっている状態にし、
そこから初期状態になるよう、うまい具合に逆に試合を進めていく。
初期状態にできる盤面だったらカウント数を一つ増やす。

おそらく６０手目の局面数は、
２＾64＝1.84467E+19
ぴったりになると思われる。

１ｈにつき1E+11面の局面をカウントし、それを十万台のｐｃで行えば、
2ヶ月で完遂する。

この場合記憶容量は関係ない。
盤面を数値化し、数が少ないほうから行うなどルールをきめればいい。
分散処理も、要は十万個のデータを管理すればいいのでさほど非現実的ではない。
（終局局面数のカウントを分散処理する場合、膨大な局面のデータを
一つ一つのＰＣに記憶しなくてはいけないという問題がある。）

主な問題点
初期状態になるよう、うまい具合に逆に試合を進めていく。
と書いたが、そのようなプログラミングは非常に難しいと思われる。

さらに早さを求められるので鬼のような難しさとおもわれる。

すまんす(ﾟρ`)

>>474
2^64にはならないと思います。
例えば↓のような局面は無理です。
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●○●○●○●○
下辺に7個の白や黒の石があるどのような状態からも、
8個目を打って●○●○●○●○とする事は出来ません。
必ず辺の石を返してしまいます。

>>457
(ﾟ◇ﾟ)ｶﾞｰﾝ

60手目、棋譜数は可能盤面数の何兆倍以上あるというのに
棋譜で表現できない盤面があるとは…

いやはや何とも…

辺のどこかに一箇所でも●○●○の４つの並びがあったら
その局面は実現不可能だと思う

こういう終局図もある

●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
　●●●●●●

>>475>>477
なるほど、辺の条件によっては無理なものがありますね。
辺の条件はＯＫでも不可能な盤面を思いついた。
●●●●●●●○
●○●○●○●●
●●○●○●○●
●○●○●○●●
●●○●○●○●
●○●○●○●●
●●○●○●○●
○●●●●●●●

少なくとも一つの方向に３つ以上の同じ色の石が連続していて
なおかつ、どの方向にも相手の石を挟んでいない石が存在しなければ
直前に打った石がないということで、その局面には到達できないってことかな

>>479
不可能っぽく見えますけど、なぜ不可能ですか？

プログラムを作って存在できる辺と存在できない辺の形を調べてみました。
辺の８マス3^8=6561通りのうち、
・存在できるもの：5935通り
・存在できないもの：626通り
どなたか検証お願いします。

>>481
int p, i, j;
int c = 0;
int a[8];

for (p = 0; p < 6561; p++) {
j = p;
for (i = 0; i < 8; i++) {
a[i] = j % 3;
j /= 3;
}
for (i = 0; i < 5; i++) {
if (a[i] == 1 && a[i + 1] == 2 && a[i + 2] == 1 && a[i + 3] == 2) {
c++;
break;
}
if (a[i] == 2 && a[i + 1] == 1 && a[i + 2] == 2 && a[i + 3] == 1) {
c++;
break;
}
}
}
printf ("%d %d\n", 6561 - c, c);

5969 592

ちょっと違った

>>480>>481
475や477と同じ理屈で、最終着手が盤面のどの石でも必ずどれかの石を返します。

>>479
すべての石が8方向のうちどれか１方向へ
◆○●（◆はそのマスに置かれているもの
そのマスに置かれている石が白の場合は◇●○となる）
という形をとっている場合、
すべての石が直前の一手となりえないので
その局面は存在しないこととなる。

◆○●は、　◆○○●　◆○○●　◆○○○●　でも可

>>480とちょっと違うな。。どうなんだろ。。
６４マス全部埋まっていなくとも、通用する理論？

>>484
基本的には同じことを書いたつもり。
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋●●＋＋＋
＋＋●○○●＋＋
＋＋●○○●＋＋
＋＋＋●●＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
この局面はどの石も３つ以上連続したつながりを持っていないので
直前に打った石がないことになり作れない。
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●●●＋＋＋
＋＋●○○●＋＋
＋＋●○○●＋＋
＋＋＋●●＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
これは左上隅の黒石が右と下方向に３つ連続していて、隣接した白を挟んでいないので
少なくとも１手前からは作れる。
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●●●＋＋＋
＋＋●○○●＋＋
＋＋●○○●＋＋
＋＋＋●●●＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
これは全ての黒石が白を挟んでしまっているので、作れない。

>>483
なるほど。ありがとうございます。

僕の作った不可能な辺の形を調べるプログラムの出力です。
一番右の数字がゼロのものがありえない形です。
Wikiにアップしました。170KBくらいあります。
http://www9.atwiki.jp/othello/?cmd=upload&act=open&pageid=39&file=impossibleedge.txt

>>486
機械的に黒白黒白が含まれる数を数えただけなので
●○●●○●
○●○○●○
の６個の並びと
●○●●○○●○
○●○○●●○●
を数え漏らしてたようでした。
すみません。

今石を置いていくプログラムを書いたら同じ数になりました。

>>485
「辺」の定義を広くして次の盤面も
棋譜で表現不可能かと。

＼ＡＢＣＤＥＦＧＨ
１＋＋＋＋＋＋＋＋
２＋＋＋●○●○＋
３＋＋＋●○●○●
４＋＋●●○●○●
５＋○○○○○○●
６＋＋●●○○●＋
７＋●●●●○＋＋
８＋＋＋＋＋＋＋＋
Ｄ2からＧ2が●○●○となっているため。


＼ＡＢＣＤＥＦＧＨ
１＋＋＋●●○○○
２＋＋＋●○●○○
３＋＋＋○●●○○
４＋＋＋●●●○○
５＋＋＋●○○○○
６＋＋＋○●○○○
７＋＋＋●●●○○
８＋＋＋●●●●○
Ｄ2からＤ7まで●○●●○●となっているため。

これは正しい？

>>489
ある連続した石の列をとったとき
その列に属する全ての石が、その列を構成する石からしか挟まれていないか
どの方向にも挟まれていなかった場合

その列に辺の打てないパターンが含まれていたら
その局面は棋譜で表現不能。

ってことでいいのかな？

＼ＡＢＣＤＥＦＧＨ
１＋＋＋＋＋＋＋＋
２＋＋＋＋＋＋＋＋
３＋○○○○＋＋＋
４●●○○●●＋＋
５●●●○●●＋＋
６＋○●●●●●●
７＋＋●●○○＋＋
８＋＋＋○○○＋＋

これのＡ５からＤ８までの斜めのラインとかも？

辺の全でに石があるときの、辺の有り得ない形を調べたら
2^8=256のうち106が有り得ない形で、150が可能な配置でした。

と、いうことは６０手後の終局盤面 2^64のうち、少なくとも1-(150/256)^4=0.88くらいは
有り得ない局面だということですね。
隅石の重複を考慮してないので正確ではないですが大体このくらいかと。
さらに、辺は可能でも全体としては不可能な盤面もあるので終局局面数はさらに減るのかな。

>>490
ですね。かなり削られますねこれで。
タブーの形が一次元なパターンですが、二次元のパターンはないのかなぁと思ったりもします。

>>491
場合わけをして計算したら、
64マス全て埋まっている状態で
全ての四辺の通り
2＾28　= 268435456
のうち、>>486に引っかからない四辺は、
31640626　でした。（>>486のデータを使わせていただきました。）

６４マス全て埋まっている状態のうち、オセロ到達可能局面は、
12％未満というのはすごく驚きです。
ここらへんの感覚は今まで認知されてたんでしょうか。。

>>493
タブーというのは
間違った表記ですね
語彙がいいかげんですみません

60個埋まっている最終局面をランダムに発生させて
ありえない局面を除いた割合を調べてみました。

ありえない辺だけを除いた局面の割合
100000000 11788619 0.117886

計算では31640626/2^28=0.117871

辺のパターンは考慮せず白も黒も1手も戻せない局面だけを除いた割合
10000000 9492871 0.949287

ありえない辺と白も黒も1手も戻せない局面を除いた割合
100000000 11447828 0.114478

この100000000回のうち辺のチェックは通った数 11785752
11785752 11447828 0.971328


辺がありうる並びだったとき3％弱程度が1手戻せなかったみたいです。

>>492
二次元は私も考えてましたがなかなか難しいですね。
唯一思いついたのがこれです。
盤面は２つとも左上隅とします。
●○●＋＋　　　|●○●＋＋
＋※※＋＋　　　|○※※＋＋
＋＋＋＋＋　　　|●※＋＋＋
＋＋＋＋＋　　　|＋＋＋＋＋

＋は石の有無は問わないとして※の箇所が全て空白は不可能。
理由：白石は、隅と辺の黒石に挟まれてるので、黒石より後から打たなければならない。
　　そのとき、※の箇所が全て空白だと打てない。

疑問に思ったんだけど、中央４×４のボックスから初期配置４石を除いた１２マスが
全て埋まる最長手数は何手なんでしょう？
最短手数は１２ですよね。
感覚的には５９手までボックスのうちの１マスを開けておくのは不可能に思えるのですが。
これが不可能であれば６４マス埋まった盤面から１手戻すときもボックスは除外できます。

さらに言えば終局前の数手はほとんど隅の近くしか空いてないと思うのですが、
これも証明は難しいですよね。

f5d6c3d3c4f4c5b3c2b4e3e6c6f6a5a4b4a6d7c7e7e8b6d8
g3f7g5d1c1b1g6a7g8h6h5f8c8h4g4b2a1b7e1h3a2h7a3g2
a8b8g7h8h2h1g1f1f2e2d2f3

最後まで開けられる模様。

どうやって見つけたんだ！

一ヶ所バグがあったので直した
f5d6c3d3c4f4c5b3c2b4e3e6c6f6a5a4b5a6d7c7e7e8b6d8
g3f7g5d1c1b1g6a7g8h6h5f8c8h4g4b2a1b7e1h3a2h7a3g2
a8b8g7h8h2h1g1f1f2e2d2f3

17手めb4→b5

496です。
そうですか、可能でしたか！でも早速の反例ありがとうございます。

>>463
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

>>500
確認、ありがとうございます。同じ結果でほっとしました。

あと>>474- からの流れの、直前手が可能かどうかでの不可能盤面についてですが以下のことを考えました。
例として>>455の盤面を使わせてもらいます。

455の盤面で480の条件を使い直前手を選びます。（私なりに表現を変えていますが同じ意味です）
条件１：その石と同色で３石以上並んでいなければならない。（ただし３石並びの真ん中は除く）
下図の星の位置
＋＋＋＋＋＋＋＋
＋☆＋☆＋○☆＋
＋☆●○●★☆＋
＋☆●☆★●☆＋
＋☆＋★○＋☆＋
＋●★＋＋●●＋
＋○○●●○○＋
＋＋＋＋＋＋＋＋

条件２：どの方向にも相手の石を挟んでいない。
条件２を加えると黒の３石が残る。
＋＋＋＋＋＋＋＋
＋○＋○＋○○＋
＋○●○●★○＋
＋○●○●●○＋
＋○＋★○＋○＋
＋●★＋＋●●＋
＋○○●●○○＋
＋＋＋＋＋＋＋＋

黒★の１つは初期配置なので、それも除き直前可能位置は２つですね。
（続く）

（続き）
この２石を着手する前の盤面は次の４つ。
＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋
＋○＋○＋○○＋　｜　＋○＋○＋○○＋
＋○●○●※○＋　｜　＋○●○●※○＋
＋○●○○●○＋　｜　＋○●○○●○＋
＋○＋●○＋○＋　｜　＋○＋○○＋○＋
＋●●＋＋●●＋　｜　＋●●＋＋●●＋
＋○○●●○○＋　｜　＋○○●●○○＋
＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋

＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋
＋○＋○＋○○＋　｜　＋○＋○＋○○＋
＋○●○●●○＋　｜　＋○●○●●○＋
＋○●○●●○＋　｜　＋○●○○●○＋
＋○＋○○＋○＋　｜　＋○＋○○＋○＋
＋●※＋＋●●＋　｜　＋●※＋＋●●＋
＋○○●●○○＋　｜　＋○○●●○○＋
＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋
この４つの盤面も同じように遡っていけば元の盤面が可能かどうか分かります。

と、ここまでは理論ですが、私が考えたのは455の３０石ある盤面で直前可能手が２手、
直前可能盤面は４つ、というのは少ない気がします。
（直前可能手、直前可能盤面が少ないので不可能盤面ではないか、ということです）
例えば、>>494で
＞辺がありうる並びだったとき3％弱程度が1手戻せなかった
とされていますが、残り97％の直前手可能数と
ランダム棋譜で６０手進めた時の直前手可能数を比べてみてはどうでしょう。
感覚的には後者のほうが直前手可能数が多いように思います。

本の紹介
リバーシのアルゴリズム
著者Seal Software（工学社）

C++とJavaで書かれている

>>503
以前本屋でちょっと立ち読みしたことがあります。
>>501-502
初期配置まで盤面を戻すプログラムを作ってみました。
全部埋まった状態から初期配置まで戻すのは難しいようです。
多くのありえる局面を戻すのは今のところ１５〜２５手くらいが限度のようで、
それ以上はいつ終わるか分からないような状態です。
>>257、>>263、>>314の２個目、>>455、>>479などは、
ありえない局面で、数秒以内に結果が出ました。
その他は259、314の１個目、475、489、490などは、
なかなか終わらなかったので途中でやめました。
戻すのに掛かる時間は局面依存がかなり強いようです。
例えば、１６手打ったある局面は１分くらいで解けたのに、
そこから１手進めた１７手の局面は３時間４０分くらい掛かったり。
多分パスがあると急激に処理時間が多くなるようです。

６４マス埋まっている盤面の話で
>>501-502みたいに
直前可能盤面数を算出したんですが
すべてオール黒の場合　153705 通りありました。

オール黒、オール白は実戦的に凄いというイメージがありますが、
数ある盤面の中で一番多く棋譜を含んでいる盤面なのかもしれません。
つまり、それだけ到達しやすい盤面なのかもしれません。

>>すべてオール黒。。。。orz

>>505
＞すべてオール黒の場合　153705 通りありました。
これどうやって求めました？
プログラムを作って数えてみたんですけど、
91648とかって数字がでてきました。
実装が間違ってるのかな・・・。

>>504
ありえない局面でなかなか結果が出なかったものは盤面の一部がありえない配置のものが多いですね。
ありえない配置以外の石は局面を遡れてしまうのでなかなか結果が出ないのだと思われます。
それと、速度ＵＰには最善手探索のときのαβ法のような上手い枝狩りを考える必要があるでしょうね。

>>505-507
オール黒の直前可能盤面数を計算で出して見ました。
直前手がA1（隅）の場合、右、下、右下方向それぞれ返せる石の数は０〜６の７通り。
全て返さない場合は直前盤面にならないので総数は「７×７×７−１」となる。
A1＝(7×7×7-1)×4＝1368
隅は４箇所あるので４倍しています。以下同様に
B1＝(6×6×7-1)×8＝2008
C1＝(5×5×7×2×2-1)×8＝5592
D1＝(4×4×7×3×3-1)×8＝8056
B2＝(6×6×6-1)×4＝860
C2＝(5×5×6×2×2-1)×8＝4792
D2＝(4×4×6×3×3-1)×8＝6904
C3＝(5×5×5×2×2×2×2×2-1)×4＝15996
D3＝(4×4×5×3×3×2×2×2-1)×8＝46072
トータルは91,648になりました。

>>508
やっと　91648　に会いました。真ん中４つを入れたり、符号が抜けてたりしてました。精進。

>>505
＞オール黒、オール白は実戦的に凄いというイメージがありますが、
＞数ある盤面の中で一番多く棋譜を含んでいる盤面なのかもしれません。
一番多く棋譜を含んでる、かどうかは現時点で証明出来ませんが508で書いた式を考えると
「91,648は、ある盤面の直前可能盤面数の上界」であり、また
「直前可能盤面数が最大(91,648)となるのはオール黒とオール白の２盤面のみ」
という事は言えますね。

>>495
その２つをまとめて一つの条件にしました。
（※は緑、または外界。○と○は同じ色の石。●と●は同じ色の石。○と●は違う色の石。＋は全て。）

＋＋＋※
※※＋＋
●○●＋
※※※＋

ありえないパーツ（←何て名前にしましょう？）は今のとこ上の一つと下の四つを加えた５種類ですかね。。

＋●○●○＋
※※※※※※

＋●○●●○●○＋
※※※※※※※※※

＋●○●●○○●○＋
※※※※※※※※※※

＋＋＋＋
※※※＋
●○●＋
※※※＋

氷河期です。保守。

結果って
勝ち、負け、引き分け、の三つじゃないの？

>>513
そうとも答えられます。
ttp://www9.atwiki.jp/othello/
よろすく

>513　お前はブロンドか。

とあるバーにて、男がブロンドに言った。
「ここに一組のトランプがある。
　ここから一枚カードを取り出して、ジョーカーが出たらキミに100ドルやろう。
　それ以外が出たら、キミは今晩ボクと一緒に過ごす。　こんな賭けをやらないか？」
ブロンドは
「いいわ。」といって、カードを一枚抜いた。　みごとジョーカーを引き出した。
男はブロンドに100ドルを渡して、去っていった。

それを見ていたバーテンダーはブロンドに言った。
「お嬢さんすごいな、あんな無茶で不利な賭けを受けるなんて。」

ブロンドは答えた。
「あら、全然無茶じゃないわ。」
「だって、ジョーカーが出るか出ないか、50％の賭けよ。」

>>515
ブロンドってコロンボよりも賢いんだなー感心したぜ

「試合結果」の考え方として、
(1)勝ち、負け、引き分けの３通り。
(2)棋譜数を数える。
(3)局面数を数える。
などの考え方が出ていますが（→ ttp://www9.atwiki.jp/othello/pages/5.html ）
黒38-白26 とかの終局時駒数で表現する方法もありますね。（既出だったらスマソ）
これは数えられないでしょうか？
とりあえず全枡埋まった場合は黒64-白0 〜 黒0-白64 の65通りですね。
黒ｍ-白ｎと考えるとｍ＋ｎ≦64が成り立つので最大2145通り、かな。

前最強オセロでコンピューター同士を最強レベルで戦わせようとしたら
コンピューターが悲鳴上げてて二日間くらいの試合になったから相当
な数だと思うぞ。

あげ

２週間ほど前にこのスレ見つけて、面白そうだったので自分も全探索にチャレンジ。
自己満足な意味合いが強いけれど何とか高速化を行い、初手固定の14手目までの探索で
60分強と言うところまで来ました。
環境はWIN2k、XP1800+、VC2005Express。一応cygwin上のgccでもコンパイルできることを確認。
15手目までやってみたかったけど、家のマシンは負荷を掛け続けるとなぜか落ちるようなので
断念しました。
MMXやら64ビット専用やらと、まだ高速化はいろいろ出来そうですし、実際そういうソースも
公開されてるようですが、ソースレベルの高速化はとりあえず一旦ここでお終いにしようかと
思います。
次の手としては、同じ局面が発生した時の対処となりますでしょうか。
ちょっと試してみたいと思います。

【友達】小学校の旧友を2chで探そ【仲間】3校目
http://life7.2ch.net/test/read.cgi/kankon/1151820309/l50

自分の生年と過ごした学校の名前と都道府県を書き込み、
同年代かつ同じ学校で過ごした仲間を探すスレです。
まとめサイトもあります。
現在コピペで存在を知らしめ、参加者を募っています。
参加者が多ければ多い程同級生が見つかる確立も上がります。
興味を持った方はご協力宜しくお願いします。

>>520
か、かっかかっかかかか歓迎しゅるっ！！！１

>>520　乙です。
＞同じ局面が発生した時の対処
これが意外と難しいんだよね。
同じ局面を判断するためのデータベースが必要になるし回転や反転をどこまで考慮するかも悩み所。
このスレでも全探索は大勢チャレンジしてるけど、その次の一歩が踏み出せない感じだね。

どもです。
あれからも細々とやっておりますが、難しいですね。
局面データの保持がやはり厳しいです。
検索速度は無視してでも、何とかできないかと考えております。
高速化の方は成果がありまして、初手固定14手まで50分弱となりました。
今のところそんな感じです。

>>524
14手まで50分弱とはかなり速いですね。このスレでもトップクラスじゃないかな？
私は13手で数時間掛かってそこで挫折ですorz

局面データを保持するためのメモリ量を考えてみました。
６４枡のそれぞれに黒の有無、白の有無、と考えると、１盤面あたりに128ビット＝16バイトのデータ量が必要。
６４枡に空き、黒、白の３値を保持して最小完全ハッシュ関数を作ったとして、3^64通り＝13バイト。

ここで考えたのがx手目が決まれば盤上の駒数ｎはn=x+4個に決まるのでこれを使えないだろうか。
６４枡にｎ個の石を配置出来るパターンは64!/(64-n)!/n!
ｎ個の石が黒か白かは2^n
これらを最小完全ハッシュ関数で表現出来れば
ｎ＝10の時配置は５バイト、黒白情報は２バイト。計７バイト
ｎ＝15の時配置は６バイト、黒白情報は２バイト。計８バイト
これを使えば初期十数手まではメモリ節約出来ると思う。

ただしハッシュ関数、逆ハッシュ関数を使うので速度的にはかなり不利だと思う。
それと上手い最小完全ハッシュ関数と逆関数が作れるか、というのも問題ですね。

>>525
コンパイラの吐くソースを見ながら、ビット演算と場合分けをちまちまとやった成果です。

局面データについてですが、配置情報と黒白情報が分かれてるのが良いですね。
片方（この場合は黒白情報か？）をくくり出すというか、indexにすれば実際の保持量を減らすことが
出来ますし。自分の場合は算術圧縮の頻度表（石の数）で試してみました。

とはいえ結局のところ局面数そのものが多いため、1局面を１ビットとしても持ち切れなくなると
思われるので、重複チェックは適当な所で妥協した方が良い気がしてきました。
つまり、一定数を超えたら適当にデータを捨てていくのはどうだろうかと。
探索数と保持数で上手くバランスが取れて成果が出るか、どっちつかずで意味が無かった
という結果になるか分かりませんけど。

しかしいずれにしろ局面を少ないデータで表現できるに越したことは無いので、何とかならないかと
引き続き思案中であります。
次に試そうと思っているのが、外周の空きマスをランレングスで圧縮してから算術圧縮というものです。

あげてみよう

>>526
実力不足でコメントできないのが悔しいです。
応援してます。

>>528
お、よんけた氏からレスが。
応援ありがとうございます。といっても今忙しくて何も進んでおりません。
ですので、ネタとしてwikiの方にソース(othello_count.cpp)をアップさせてもらいました。
高速化の理由がバグのせいだったと言うこともあるかもしれませんので、
検証や更なる高速化をどなたかお願い致します。
（バグ入りじゃないと良いナァ…）

>>529
すみません、ちょっと見てみたいと思ってWikiを漁ったんですが見つかりませんでした。
リンク貼っていただけますか？

>>530
どもです。
棋譜数のカウント http://www9.atwiki.jp/othello/pages/28.html
に添付しております。
局面の保持などが入っていない、ただの全探索バージョンです。
vc2005expressで開発、Cygwinのgccでも確認しておりますが、それ以外の
環境では試しておりませんので、何かまだ問題はあるかもしれません。
よろしくお願い致します。

みなさんお久しぶりです。
520氏のプログラムのソースをいじってみました。
最終1手を最適化しただけですが、僕のマシン上（CeleronD3.06GHz）で、
処理時間を５９％くらい削減できました。（12手：27.44秒->11.28秒）
僕がちらっと見た限りでは520氏オリジナル版にバグは見当たりませんでしたが、
ぼくの変更により新しくバグが入ってしまったかもしれません。
ぼくはC++があんまりわかってませんし。
ソースは>>531と同じ場所にアップしときました。（othello_counter2.cpp）
こういう事ができる余地を残しておきながらあれだけ速いのは驚きました。

以前挑戦した時は13手で数時間かかっていたのですが、
久しぶりに書き直して、ちまちま改良を重ねたら13手で70分程というところまできました。
>>532のと比べると、まだまだ大きな差がありますが、もう少し頑張ってみようと思います。

スレ復活の兆しが見えてきたので活力剤を投入してみます。
ご存じの方もいらっしゃるでしょうが、とある行きつけのスレでここ向きな話題を見つけたので
纏めておきました
ttp://www9.atwiki.jp/othello/pages/48.html

>>520氏のプログラムに近い感じの流れだと思いますがどうでしょう？
ちなみに後半の回転に関しては、ユニークな盤面数を出すときに必要だろうということで。

6x6オセロの全探索をしてみました。
誰かやってましたっけ？
|手|空|最大| 棋譜数 | パス | 終了 |
| 1|32| 4| 4| 0| 0|
| 2|31| 3| 12| 0| 0|
| 3|30| 5| 56| 0| 0|
| 4|29| 6| 244| 0| 0|
| 5|28| 9| 1364| 0| 0|
| 6|27| 11| 7604| 0| 0|
| 7|26| 12| 47740| 0| 0|
| 8|25| 14| 308716| 0| 0|
| 9|24| 15| 2115128| 112| 0|
|10|23| 16| 14978496| 156| 108|
|11|22| 17| 108843480| 3292| 112|
|12|21| 19| 811367624| 11548| 2092|
|13|20| 19| 6080743752| 141700| 4380|
|14|19| 19| 46261636540| 802508| 58512|
|15|18| 18| 348409244516| 9116028| 138548|
|16|17| 17|2632834266064| 63962184| 1500172|
最大着手可能箇所数はこれ以降も空きの数と一致しそうな気がします。

もうそんなことはどうでもいいから、

みんなでオセロしようぜ！

ドコモで無料ドリンク技公開中です☆
是非着てみてください！
http://id24.fm-p.jp/gamen/s_scr.php?num=1&uid=cmode0&dir=35

只今おまけイベント公開中です！

＼＼＼　　　　　 ／⌒＼　　　 , ─ ､
　　　　　　　　　/＿＿＿ヽ　／　　　ヽ＼＼＼
　　　　　　／ ￣　　　　　￣　ヽ.　　　 i
＼＼　 ／　￣￣￣￣　＼ 　 　 ＼ 　 | 　サ　ト　タ　や！！
　　　 /　へ　　　 ／ヽ　　 ヽ　　 　 ヽﾉ
　　　/　/＾ヽ　　　 /＾ヽ　　　ヽ 　 　 ヽ　＼＼＼
　　　|.　|　0 |　　　| 0　| 　　　 |　　 　 i
＼＼|　 `− ６　　 `−′　　　 |. 　　　|
　　　!　　　　　　　　　　　　　　 !　　　 !
　　　 ヽ　　 / ￣￣￣ ＼　　　/　　 /
　　　　 ＼　＼＿ （⌒ヽ丿　　/　　/
　　　　　　　━━━６━━━━━ヽ、

>>535
乙です。
そして次からはsageでお願いします。

ホ

今度はアタック25の試合結果について考えようぜ。

保守がてら…

自分独自のやり方では限界が見えてたので>>534を参考にしたら
11手12秒まで到達

>>541
クイズ全部正解すればいいんじゃね

＞局面数メモリ節約
>>525 はハッシュ法みたいだけど、
ハッシュまでは使わずに配置情報と白黒情報の分離だけ実施してみたらどうだろう？
手数 n のときに、配置情報 64 bit、白黒情報 n bit、合計 64+n bit
とすれば、16手付近で 80% くらいのメモリ節約になりますね。

１手で局面が１０倍になることを考えると 80% じゃ足りないっすか。。。

元が128bit以下だし、ハッシュの有効性については疑問

┏━━━━━━━━━━━━━━━━━━━┓ ┌──┐
┃ 中川翔子 盗撮 おっぱい 動画 特設ページ　 ┃ │検索│
┗━━━━━━━━━━━━━━━━━━━┛ └──┘

　　　　　　　　　 _ 　∩
　　　　　　　　(　ﾟ∀ﾟ)彡　おっぱい！おっぱい！
　　　　　　　　　⊂彡

最近このスレを発見して自分もこの話題に興味あるのですが、
如何せんプログラムに対しては素人なのです。
ひどく低レベルなことを言ってるのは重々承知してるのですが、
もし差し支えなければ、4×4の場合のソースを頂けないでしょうか？

>>547
>>531のプログラムは8x8用ですけど、
これを中心の4x4部分に限定して打つように改造すれば4x4も計算できます。

64ｘ64とかやって見ると法則が見えてきたり・・・しないか

で、結論は？

難しい

おまいら最強のリバーシプログラムしてみろよ
http://pc8.2ch.net/test/read.cgi/tech/1166749119/

たたき台になるかわからんが、
例えばこのような局面（白手番）から決着がつくまで何通りあるかを数え上げることを考えてみよう。
計算効率をあげるためにはどうすればよいか？
＿＿＿＿＿＿＿＿
l＋＋●●＋○＋＋l
l＋＋●●●●●＋l
l○○○○○●●○l
l○○●○●●●○l
l○●○○●○●○l
l○○●●○●○○l
l○＋●●●○＋＋l
l＋＋○○○○○＋l

↓どうぞ

上界は14! = 87,178,291,200

114682079

>>554,>>555
どのような思考の流れがあったかとか良いスキームとか思いついたら報告、或いは紹介してくれ
俺の場合、上界は察したが、下限はしらみつぶししか思いつかなかった。

だが、一つの”気づき”というか、誰でも思いつくような考えではあるのかもしれないけれども
その二つは思考のベクトルがまったく逆で、プログラム的なことを考えた場合
＿＿＿＿＿＿＿＿
l×◎●●◎○◎◎l
l×△●●●●●△l
l○○○○○●●○l
l○○●○●●●○l
l○●○○●○●○l
l○○●●○●○○l
l○◎●●●○◎×l
×◎○○○○○×l


◎(おける)が△（黒がそばにあるがはさめない）と×（そばに黒がない）いう違いでも、
有意味であることくらいには気がついた。
この状態に至る前の過程が何通りあるのかわからなくても関係ないこともわかった。

要するにその前の状況に左右されないということではあるのだけれども、
逆に戻るというアプローチも取れることを考えると何か意味があるかもしれない、ないかもしれない。

反応アリガトウ、メリークリスマス。

数字だけ載せて不親切だったな

残り14手だったので全探索しただけだよ
合ってるか保証はないけど

効率的に求めるにはどうしたら良いだろうね
同一局面を探索しないという方法も取れるけど、
同一かどうかを調べるのに時間を食って意味がなくなりそう

３の６０乗+２の４乗は違うんですかね？ひとつのマスに白、黒、んで完封した時の無しって３っつの選択肢があって、真ん中だけ初期からあるから
数学はあんま得意ぢゃないんで素人な意見で申し訳ない

同一局面のチェックはノードが割合少ないルート付近だけやるのが効率的だと思う。

>>557
ローラー&ツリー的なしらみつぶしに、同一局面、あるいは回転対称性をどうすべりこませるか
もしくはまったく別のアプローチがあるかって考えてるけど、なかなか思いつかないね。

>>558
＿＿＿＿＿＿＿＿
l●●●●●●●●l
l●＋＋●●＋＋●l
l●＋＋●●＋＋●l
l●＋＋●●＋＋●l
l●＋＋●●＋＋●l
l●＋＋●●＋＋●l
l●＋＋●●＋＋●l
l●●●●●●●●l はありえるか、考えてみよう

>>559
俺もそう思う。
さらに同一局面とそれに似た局面（例えば一枚だけ違う）の違いが
どのような意味を持ち有意差として認められるかってのには多少興味がある

>>556
全探索プログラムで556と少し違うが似たようなことを組み込んだ事がある。
盤面データに「石の隣である」という情報を組み込んでみた。
例えば初期配置だと
00000000
00000000
00333300
00321300　0:空白
00312300　1:黒石
00333300　2:白石
00000000　3:空白で石の隣
00000000
というデータとした。
これだと石を打てるかどうかの判定は「3」のところだけチェックすればよいので
初期配置で12/60のチェックで済む。
実際初期十数手までのチェックでは計算時間は短縮できた。
しかし556の図のような終盤になると空白はほぼ石の隣になるので余計な処理の分
かえって遅くなるかもしれない。

>>558
560の指摘どおり存在しない盤面があるので単純にその計算式にはならない。
あと「３の６０乗」と「２の４乗」は足すのではなくかける必要があります。

ありえない局面については>>474-495あたりを参照。

>>553
553の局面から同一局面の可能性について考えてみました。
＿＿＿＿＿＿＿＿
l�A�@●●＋○＋＋l
l＋＋●●●●●＋l
l○○○○○●●○l
l○○●○●●●○l
l○●○○●○●○l
l○○●●○●○○l
l○�B●●●○＋Ａl
l＋�C○○○○○Ｂl

上図で白�@黒�A白�B黒�C と、白�B黒�C白�@黒�A は同一局面となる（４手後）
また黒Ａ白Ｂに打つと考えると例えば
白�@黒Ａ白Ｂ黒�A白�B黒�C
白�@黒�A白�B黒Ａ白Ｂ黒�C
白�@黒Ａ白�B黒�A白Ｂ黒�C
と、上記�@と�B、�Aと�Cを入れ替えた場合の６通りで同一局面となる（６手後）

白先�@�Aと�B�C、黒先ＡＢがそれぞれ干渉しないのでこういうことが起るのですが
ある局面から数手後での同一局面は多いのかもしれません。
それと考えると当たり前なんですが、その数手の間に打った石の位置は同じです。
つまり上記６手後の例では�@�A�B�CＡＢの６箇所にどの順で打つかが問題であって
それ以外の場所に打った時点で同一局面にはならない、ということです。

>>563
そうそう！異なる経過から同一の結果になるパターン。
干渉する場合で同じになるときもあるだろうし、俺は考察する価値があると思っているんだけど、
まだ方向性が見えてない感じ。

相方スレが盛り上がってるみたいなのでそっちを紹介します。
http://pc8.2ch.net/test/read.cgi/tech/1166749119/l50

＞干渉する場合で同じになるとき
これってこういう経過の同一局面の事ですか？
F5D6C3D3C4
F5D6C4D3C3
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋●○＋＋＋＋
＋＋＋○●＋＋＋→＋＋●●●＋＋＋
＋＋＋○●●＋＋　＋＋＋○●●＋＋
＋＋＋○＋＋＋＋　＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋

>>565
まさにそういう経過のことです。
あまり考える意味はないかなぁ？

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●○＋＋＋＋
＋＋●●●○＋＋
＋＋＋○○●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●○＋＋＋＋
＋＋●●●○＋＋
＋＋●●●●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋○○○＋＋＋＋
＋＋●●●○＋＋
＋＋●●●●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋

>>566
意味あるのは>>559にもあるけど探索深さが浅い段階のときくらいかな

>>565>>566
565を一般化すると

Ａ Ｂ ＋　→　●○＋
Ｃ ◎●　→　●●●
＋○●　→　＋○●

白石（◎）を挟む黒の手ＡとＣがあり、それを返す白の手Ｂがあると
●Ａ→○Ｂ→●Ｃ　と　●Ｃ→○Ｂ→●Ａ　は３手後で同一局面になる、ということですね。
Ａ，Ｂ，Ｃの手は挟む石が複数になっても成り立ちます。

>>570
確かに563のような終盤では同一局面を探すより全探索してしまったほうが
効率的だとは思いますが中盤くらいでは効果が出ないでしょうか？

>>571
中盤か終盤かというわけではなくて、あくまで探索深さの問題だと思うよ。

同一局面が現れるのは三手先から。
一手につき候補手が5つあると仮定すると、三手先は125通り。
同一局面が12個あっても一割にも満たない。
これが四手五手と増えるにつれ同一局面が現れても、ほとんど意味がなくなる。
局面を保持すればするほどメモリを食うし、
局面の一致をチェックするためのメモリアクセスがボトルネックになる可能性が大きいと思う。

あくまで上で述べたのは予想だから具体的にプログラム書いて確かめるのが一番だよね。

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
○○○○●●●○
○○●○●●●●
○○●○●●●○
○○○○●●○○
＋＋○○○○＋＋
＋＋○ＡＢ○＋＋

細かいことだけど２手先でも同じになることはありそう。
例えばここでABと進んでもBAと進んでも。

>>573
ほんとだ
おもしろいね

ロジステロの再発明について議論するスレはここですか？

>>575
そうです…ｗ

本当はスレ通り、”結果数を数え上げる”スレです。
勝ち負けにすら関心はありません

>>575
それはこちらになります
ttp://pc8.2ch.net/test/read.cgi/tech/1166749119/

>>576
ありがとう

>>577
いや、ロジステロならここで合ってる

>>578
最善手だとか定石、どちらが優勢かとか場の評価は置いておくって感じで。
たしかロジステロにはそういう要素があったような気がします。

・

明けましておめでとうございます。
スレの流れでデータベースを持たない（局面の保持をしない）で重複チェックする方法を思いつきました。

探索中の棋譜を保持しておいて最後の３手ないしは４手を総当りでチェックする。
もちろん再現不可の棋譜も出るがそれは除外して問題ない。
３手の総当りで６面、４手の総当りで２４面の局面が発生するがその中で
本手との同一局面をチェックする。
もし同一局面が発生すればその３手（または４手）の手順で唯一となる手を
決めるルールを設定しておき、その手ならば同一局面の数倍のカウントをし、
それ以外の手で同一局面なら以降の探索をしない。

例えば>565の棋譜では
F5D6C3D3C4の時最後の３手(盤の左上からC3,C4,D3)を並べて出来る盤面はF5D6に続く
C3C4D3,C3D3C4(*),C4C3D3,C4D3C3(*),D3C3C4,D3C4C3 の６面で(*)の２面が同一局面となる。
この時最初に出てきたC3D3C4をユニークとして以降の探索を２（同一局面の数）倍とする。
そしてF5D6C4D3C3の時にも同様の処理をしてC4D3C3は同一局面はあるがユニークでないので
以降の探索を打ち切る。

この方法は、演算量が増えるので重複処理による演算の減少に見合うかどうかが問題ですね。
それと決めた手数以降に発生する同一局面には対処出来ません。

http://www.amy.hi-ho.ne.jp/okuhara/howtoj.htm

＞置換表 (Transposition table)
＞数手先で同じ局面が生じることがしばしばある。 たとえば虎定石の初手から f5-d6-c3-d3-c4 と f5-d6-c4-d3-c3 の手順は、同じ局面になる。
＞これは置換 (transposition) と呼ばれる。 同じ局面を複数回探索するのを防ぐため、
＞プログラムは探索中に遭遇した局面のすべて （あるいは大部分）を置換表（通常はハッシュ表のデータ構造を用いる）に保存する。
＞オセロの中盤においては、深い読みでは20%〜50%（概算）の時間を節約できる。
＞終盤においては、置換が生じる確率はさらに高くなり、節約できる時間も大きくなる。

保守

保守

>>582
オセロプログラムを作る事と、全棋譜をカウントする（全探索）のは手法が違う。
全探索にはminmaxやαβの枝狩りが使えない。
全探索に使える枝狩りは今のところ Transposition のみだと思うが
Transposition table を使うと全ての局面を保持する必要がある。
オセロプログラムの場合、悪手は枝狩り出来るし現在の局面から手を進めれば良いが、
全探索の場合は初手から全て保持しなければならない為メモリ不足が問題となる。

>>585
じゃあ、
オセロの全探索数をみつける>>(計算量的に超えられない壁)>>オセロで理論上最強の手を見つける

でおk?

>>586
おｋです。

ついでに言えばさらにその右側に
オセロで理論上最強の手を見つける>>(計算量的に超えられない壁)>>現在の強豪オセロプログラム
こんなのがあるんですけどね

ﾔｽﾓﾘ

保守

F5D6C3D3C4F4F6G5E6D7F3E7E3G4G6G3H4H3H5H6C7C6C5B6F8E8C8G8B5A5F7B4A6E2A3A7F2E1D2C1D1G7H8D8H7B7H2G2F1H1G1B8A8A4B1A1A2
＼ＡＢＣＤＥＦＧＨ
１○○○○○○○○
２◇＋＋●●●●●
３○＋●●○●●●
４○●●●●●●●
５○○○●●●●●
６○○○○●○●●
７○●○○○●●●
８●●●●●●●●

こんな形って過去に存在しないとか言われてたっけ。

>>590
そういう形が存在しないとは言われてなかったと思うけど。
どこら辺で言われてたと思うの？>>314-315あたり？

しばらく人大杉だった・・・
保守

保守

保守

保守

試合結果を求めることに直接結びつかないと思うのだけれど
少し気になったことがあります。

ある局面Ａがあって、Ａの石の並びを左右対称、上下対象にしても
最終石差は変わりませんよね。
また、対角線に対して石を対象に並び替えても同じ結果。
それをした後で更に左右対称、上下対象にしても同じ結果になります。

こんな感じで石をある特殊な条件下において並び替えても
同じ結果になるような石の並び変えの仕方って他に何かありますかね？

>>596
反転や回転で同一盤面になるのは８種類ですね。
>>408の中段が参考になると思います。

>>596
どうなんだろうね

その8種類の共通点って後の展開(分岐の仕方)が全く同じってことだよね？
だとしたら
分岐の仕方が同じ盤面の組を
自動的に発見するプログラムってのは作れそうだね

人間がウンウン考えるよりも目からうろこの並び替えが見つかる「かも」

手番を黒番、白番のどちらから打ち始めても双方最善手順で引き分けに
なり、かつ白石黒石を入れ替えても引き分けになるような黄金局面が
いくつか存在すると思うのだけれどその中で黒石の数と白石の数が
等しい局面をいくつか抽出してみると何か法則が見えてくるかもしれないね。

オセロは黒先手です

>>600
>>599はそういう意味ではなく、パスを考慮して手番が入れかわっても
同じ局面になった場合を想定して打ち始めるという意味です。
誤解を招いてしまいましたね・・・。
すいません。

>>601
オセロのパスは最終盤しか発生しないのでは？

いや、普通に打てなくなる場面があると思う。

>>601
あ、パスを考慮してか、そこまで考えてなかった、すまぬ

私には、彼氏がいます。彼とわたしは、デートの時、どちらかの家に行き、だれもいないとき
、部屋で横になって裸でだきあいます。それがだんだんエスカレートしていって、学校の体育倉庫で
服をぬがされ、まだ３年生ですが学年で１番大きいおっぱいを、つかむように触られたり、しゃぶった
りされます。最初は、苦手だったんだけどだんだん気持ちよくなりサイコーです。しかも、わたしは
、学年１美人でもてます。彼も同じで、美男美女でよくみんなにうらやましく、思われます。
: : このカキコ見たあなたは4日後に不幸がおとづれ44日後に死にます。それがイヤならコレをコピ
ペして5ケ所にカキコして下さい。私の友達はこれを信じず4日後に親が死にました。44日後友達は
行方不明・・・・。いまだに手がかりもなく私はこのコピペを5ケ所に貼り付けました。すると7日後
に彼氏ができ10日後に大嫌いな人が事故で入院しました。
: : 　　　　信じる信じないは勝ってです

　　　　　　　　ﾊ,,ﾊ　　
　　　　　 　 ('(ﾟ∀ﾟ∩_　おいらをどこかのスレに送って！
　　　　　　／ヽ 　 〈／＼　お別れの時にはお土産を持たせてね！
　　　　 ／|￣￣￣|.＼／
　　　 　 　| .ﾓﾂ煮..|／
　　　　　　 ￣￣￣
現在の所持品：たばこ・ライター・コーヒー・ブラックブラック・枕・ケータイ電話
睡眠薬・聖教新聞 ・ダッチワイフ・外付けSCSI340MHDD・ネットランナー4月号
TYG02・小嶋進社長・ゲルトモ・ディプスファンタジア・抵抗1kΩ(黄紫橙金)・媚薬
バーボン・メシマズ嫁のお手製弁当・吉牛の割引券・銀魂１巻・将棋の駒(角行)・オナホール
ｼﾞﾝｷﾞｽｶﾝｷｬﾗﾒﾙ・ﾎｯﾄｶｰﾍﾟｯﾄ・第三のビール・笛・nintendoDS・執刀用メス・長ラン・74HC00
Vodafone902SH・たまねぎ・タケコプター・Celeron800MHz・ほしのあき等身大抱き枕・鳥肌実ポスター・経典・正露丸
17歳の心　

６ｘ６の盤では完全手順が見つかる計算を誰かがしていると聞いたが、
結局完全手順を決定出来たんだろうか？

>>607
1993年にイギリスの人が見つけたよ。
具体的な手順は以下を参照
ttp://uguisu.skr.jp/othello/6x6.html

でもこれはalpha-beta探索法っていう枝刈り手法を使っているから
いまだに6x6の総手数は不明

それはすごい

なるほど

hoshu

あげ

ほしゅ

チェッカーは解かれたそうですね。
総通り数ではありませんけど。
引き分けだそうです。
http://en.wikipedia.org/wiki/Draughts
http://www.nature.com/news/2007/070716/full/070716-13.html
http://www.nikkei.co.jp/news/shakai/20070720STXKE037619072007.html

チェッカーってよく知らなくてwikipedia（日本のやつ）を読んだんだけど
ttp://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%83%83%E3%82%AB%E3%83%BC
＞以下のふたつの状況で勝敗が決定する。
＞相手の駒が全滅した場合、全滅させた側の勝利となる。
＞次に動かせる駒がなくなった場合、動かせなくなった側が敗北となる。

引き分け、ということは千日手になった、ということかな。

俺もよく知らないけど、ルールから察するに、お互いのコマが少なくなって追い込む事が
出来なくなるんじゃないの？
普通に考えるとそれが当り前な気がするんだけど、証明大変そうだな

214←確かに全通り解析されて、超超高性能なPC出る時代になったら「オセロは後手(or前手)が100%勝つ」が証明されるだろうね。
パターンには限りがあるし、(約50%の)終局が自分の色のほうが多くなる手順に誘導するように打っていけば。

６ｘ６が１９９３年に解決したのなら、８ｘ８ももうそろそろ出来てきても
よいころじゃないのかな。

>>618
順列・組合せを勉強しましょう

組み合わせはＢＡ☆ＫＵ☆ＨＡ☆ＴＳＵだー

お盆中はカキコなかったね

もう3年か……

これは合ってる？
http://vista.crap.jp/img/vi8751991784.jpg

>>596
亀レスで悪いが、違う手順から同局面になったりはする。
２手目を縦に打っても斜めに打っても同形になる手順がある。
それとパーフェクトになった場合、同じ形でも相当違う手順から同形になる。

石を並び替える事と手順は無関係だった。
でも左右対称や上下対称は石の配置が異なるので違う局面になるはず。
／や＼や180度に回転するのは良いけど、│や─の回転は駄目ですね。

○●
●○
の形で始めると決めておくとしたら
対称の形は4種類だな。

強いオセロソフトは
探索を高速にするのとより多くの定石を調査できるように
置換表を持ってると聞く。

石の上にも三年

８×８オセロの試合結果って黒＋６４〜白＋６４まで幅があるけれど
全体的にみて、それぞれの割合ってどうなってるのかな？
黒＋64：0.13％、黒＋62：0.26％、･･･、引き分け：30%　とか
上の割合は適当に書いたけど。

特に自分は黒＋64と白＋64はどちらのほうが多いのか気になるなぁ
それと引き分けより+64の進行の方が多いのか少ないのかも気になる。

自分は４×４、６×６の場合の割合と類似してくるんじゃないかと予想。
一番少ない割合の試合結果をすべて調べあげて（机上の計算になるかも）
その割合を全体の割合と比較して逆算して積分すれば
全試合結果に近似しそうじゃない？

対称形があるからすべての局面数は減らせるって意見があるんだけど
ある盤面があったときにその回転、鏡像は8パターン考えられる。
8パターンを1パターンに持っていけるとしても全体の計算量は1/8になる程度。

探索空間中に同じ局面が発生するという意見もあるけど
3パターン(白、黒、空き)の64マスの先手後手で
(3^64)*2≒6＊10^30だから仮にメモリが十分にあったとしても
まだ計算できる量じゃない。

局面数をまとめるって話はおもしろいんだけど後何歩か足りないね。
10^12(1T)程度になれば計算できるんだけど。

>>628
オセロは後手有利だから白の方が勝数多そう

一番少ない結果が全体の100万分の1(1/10^6)だったとしても
その個数は10^45以上はあると考えられるからそれすら数を数えるのは難しいんじゃないかな？

試合結果の分布はなかったなぁ、暇な時にでもやってみるかな。

そういう目的ならモンテカルロ法で十分じゃない？

>>630
オセロは世界の強豪プログラムが最善候補のゲーム木（ブック）を構築すると高い確率で引き分けに落ち着きます。
もはや後手有利の可能性はほぼ無いと言われています。

そうだったのか。
知らんかった。

あげ

あきらめて、ありうる手順全部数えるプログラム作れよ

>>635
作ってどうすんだよ？

手順を数える目盛りが足らんだろ

　

>>638
なんか書こうぜ

馬鹿には見えません

>>638
GJ！！！ よくやった！！！
この研究成果でオセロ解析が大きく前進しそうだな。
解けるのも時間の問題か…。wktkすぎる！

>>641
馬鹿にしか見えません

〇×ゲーム知ってる？
あれって、永遠に引き分けに出来るよね。
数が増えたのがｵｾﾛだろ。

五目並べって知ってる？

七並べって知ってる？

七並べと五目並べって何ですか？

貴方の心です

結局オセロについてわかる人っていないのかな・・・

《ｵﾊﾟｰｲ》娘の乳房観察日記《成長中》
自分の娘の胸を8歳から現在の13歳まで一ヶ月おきに撮影・定点観測
し続ける変なオヤジが主宰?するスレ。オヤジのサイトはpassが無いと
入れませんが、簡単なので皆さんも是非どうぞw
それにしても女の子の乳房と乳首がこんな風に成長していくなんて
まるでパラパラ漫画みたい。娘も可愛いけど勉強にもなるサイトです。

http://hobby10.2ch.net/test/read.cgi/auto/1190506874/

オセロは各角の4マスを取り合うゲーム
パスを有効に使うといい

>>650
オマエさんは翼崩しでやられる

以後のような飛び石の攻め方をすると負けるね
真ん中に詰めるような攻めが一般的だが
わざと翼を伸ばして相手を辺のところへ誘い込む戦略も使える
歴史が浅そうに見えるけどなかなか奥の深いゲームだよね

全部見ないで書くけど、

最大は、

3(白黒無地)の60乗　×　2(白黒)の4乗
÷　２（鏡像）

−　鏡像でなく、且つ180度回転対称、且つ90度回転対称でない場合の分

−　鏡像でなく、且つ90度回転対称の分

では？

PCオセロで最強はどれ？

過去において、どれ一つとして勝ち越したものは無いが、
どれ一つとして一度も勝てなかったものは無い。

是非、巷で最高と噂されるもので試してみたい。

>>653
http://www9.atwiki.jp/othello/pages/17.html

>>654
とりあえずzebra24手読みオススメ

>>656
ありがとうございます。

3戦目で勝ちました。
Move sequence:
e6f4e3d6g5f3f2f6c7f5c6d3c5e2c3c2d1g4d2c1b1g1e1c4h5d7g3g2f7h4h3h6c8g6b3g7e7f8h8h7g8e8d8b7b8f1h1h2a8b2a1a3a2a4a5a7b4b5a6b6

黒番で45-19でﾊﾂｼｮ〜〜〜ﾘ！

インストールしてそのままやってたけど、
settingが最強になってなかったみたいです。

search depth 1move orz

Time No time limit

Book
Use opening book ?
Play human-style openings ?
Medium randomness ?

Midgame Small randomness ?

Posistion table 4MB orz


ｻｲﾁｮ〜〜〜ｾ〜〜〜ﾝ

>>657
明らかに白番の終盤の読みが浅くなってるし。
強いソフトでも設定弱くして勝てればいいって話か？

>>657
WZebraは、ますOption→Languageを「日本語」にすれ。
話はそれからだw

てか、よく今のPCオセロに勝てるって奴がいるけどホント？
終盤３０手読みなんてされたらまず無理だと思うんだけど。

・Book（定石表）が充実していて（＝序盤の正確さ、中盤/終盤探索への移行の遅さ）、
・評価関数も割と正確で（＝中盤の正確さ、中盤/終盤の必要探索数の少なさ）、
・探索も速い（＝中盤/終盤の時間当たりの探索量の多さ）。

と3点揃っているようだと、ひたすら敗着待ちの勝負になるね。
強いソフト同士の対戦ではBookの知識量の勝負になり、
双方がミスを犯さない限り32-32の引き分けに落ち着く、という事からも。

・実は強くないソフト
・実は強くない設定（探索深度の浅さ、ランダム性の強さ等）
・未熟なBookを使用
・既知の対局結果をBookにフィードバック（学習）させていない
　（Book・評価関数の瑕疵をプレイヤーがあらかじめ把握している）

みたいな条件で「勝てる」と言ってる人もいるけど、
上の条件抜きで「勝つ」としたら、不可能とは言わないまでも
（完璧なBookや評価関数の作成はゲーム木の大きさの都合上、現状では極めて困難）
かなりストイックな作業になるのは確かだと思う。

んで、
>>657は最強設定のWZebraに勝てたのだろうか・・・・

WZebraの最強設定は時間制限無しの60手完全読み。
もし試合開始してたらまだWZebraが一手も打たずに試合中。

そのことをすっかり忘れていたよ・・・・

とりあえず必勝読みでも完全読みでもない中での最強設定ということで。

>>663
ﾜﾛｽ

○○○○○○○●
○○○○○○○○
○○○○○○○○
○○○○○○○○
○○○○○○○○
○○○○○○○○
○○○○○○○○
○○○○○○○○
こういう終わり方をしたことがある

>>666
洗濯洗剤のＣＭみたい

ほしゅ

たかだか64ますの勝敗２通り
これの全パターンが解析できない。
更にパターン数の多い囲碁将棋なんてもう絶対無理。

ただ逆に考えるとそんなゲームを考える人間は凄いな…
最近ではルービックキューブあたり。

面白そうだったので、全局面探索やってみた。
現在、12手で23秒前後。（CPU 1.6GHz）
>>532さんの約半分くらいの速度。
CPUパワーだ！って言いたいけど、
お正月、実家で暇なんでもうちょっと頑張る。
皆様、よいお年を。

実家でコチョコチョやってみたところ、
実家のPCでは12手で10.7秒くらいまで行った。
でも自分のノートPC（CPU　1.6GHz）だと12手で13秒強。
なんか気に食わないなあ。

実家のPC = 2.54GHz

極座標の覚書

＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋●○＋＋＋
＋＋＋○●＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋

1層: 10 11 10 11

2層: 00 00 00 00 00 00 00 00
00 00 00 00

3層: 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00

4層: 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00

>たかだか64ますの勝敗２通り

開始位置も決まってるし
配置場所も飛び石は置けないし
さらに対称性があるから
「たかだか64ますの勝敗２通り 」
よりは相当少ないっす

ご無沙汰です。
正月から本日まで、othello_counter2.cppに手を入れておりました。
http://www9.atwiki.jp/othello/pages/28.html　に、othello_counter3.cppを
アップロードしましたので、どなたか検証よろしくお願いします。

|手|多| 棋譜数 | パス | 終了 |
| 1| 4| 4| 0| 0|
| 2| 3| 12| 0| 0|
| 3| 5| 56| 0| 0|
| 4| 6| 244| 0| 0|
| 5| 9| 1396| 0| 0|
| 6|11| 8200| 0| 0|
| 7|12| 55092| 0| 0|
| 8|14| 390216| 0| 0|
| 9|15| 3005320| 24| 0|
|10|16| 24571192| 0| 228|
|11|18| 212260296| 576| 356|
|12|20| 1939892240| 1012| 6384|
|13|21| 18429768516| 19204| 16384|
|14|22| 184042835408| 67536| 299624|
|15|23| 1891844432704| 1092168| 887364|
time : 7147.49秒 : 119.12分 : 1.99時間

環境はWIN2k、E6600、VC2005Expressです。
自分のマシンで何とか２時間を切ることができました。

もしゅ

>>676
ご愁傷様

１０＾１８

過程が違う場合でも結果が一緒なら、それは分母に加えるの？？

全部埋める前に、全部黒になって勝てる確率はある？あるならどれくらい？

また同じ様に空きスペースを残して全部白になって勝てる確率はある？あるならどれくらい？

＞過程が違う場合でも結果が一緒なら、それは分母に加えるの？？
このスレのログを全部読むといいよ
＞全部埋める前に、全部黒になって勝てる確率はある？
あるよ
＞あるならどれくらい？
さぁ？
＞また同じ様に空きスペースを残して全部白になって勝てる確率はある？
あるよ
＞あるならどれくらい？
さぁ？

>>675
終了って終局する棋譜の数の事？
だとすると10手で終了する棋譜の数は9手の間違いじゃない？

F5F6F7F4F3E3D3G5H5
＼ＡＢＣＤＥＦＧＨ
１＋＋＋＋＋＋＋＋
２＋＋＋＋＋＋＋＋
３＋＋＋●●●＋＋
４＋＋＋●●●＋＋
５＋＋＋●●●●◆
６＋＋＋＋＋●＋＋
７＋＋＋＋＋●＋＋
８＋＋＋＋＋＋＋＋

これや有名なダイヤモンド型は9手目のはず。

F5D6C5F4E7F6G5E6E3
＼ＡＢＣＤＥＦＧＨ
１＋＋＋＋＋＋＋＋
２＋＋＋＋＋＋＋＋
３＋＋＋＋◆＋＋＋
４＋＋＋●●●＋＋
５＋＋●●●●●＋
６＋＋＋●●●＋＋
７＋＋＋＋●＋＋＋
８＋＋＋＋＋＋＋＋

>>681
>>431以降でも少し出ていた事だけどこれは間違いじゃなくて意図的なものだよ。
プログラムは9手目打ち終えた時点で終局かどうかを判定する事はしないように設計されてる。
終局の判定は10手目で双方の打てる場所の数がゼロと言うことだから
終局かどうかというのは10手目を調べているときに副次的に判明する事。
9手目を打ち終える度に10手目の打てる場所の数を調べて、
これがゼロかどうかだけを見て、そうでなければその数を捨てる、というのは無駄だしね。

あげ

あげるならスレタイの話題で頼む

話題が無いようなので書き込んでみる。かぶってたらごめん。

プログラムに、ランダム(手番ごとに、打てる手の中から等確率で一つを選ぶ)に10億局ほど対局させてみた。
奇数の石差があると分布がガタガタになったり色々面倒そうだったから、空きマスは折半じゃなくて海外ルールみたいに勝者のものにしたけど。

それで、結果。
黒から見た石差の平均が-0.86くらいになった。あと、引き分けより白２石勝ち局面の方が多かった。
やっぱり何も考えずに打つと偶数理論で白が若干有利ってことなのか。

まあ、最善進行が引き分けかどうかとは全く関係のない話ではあるけど、参考までに。

>>685
とても面白い！
定石開始（10手程度）で、
最終盤（50手以降）完全読みにするとどうだろう？

どうにもならない。

>>685
手止まりが強いって象徴だな
有段者の中でもその説は多少なりともある

16〜17手目の結果です。

|手|多|-------棋譜数-------|---パス---|---終了---|
|16|25|------20301281202588|---5359688|--13560800|
|17|26|-----222743917275036|--77407768|--50409280|
time : 804516.91秒 : 13408.62分 : 223.48時間

>>689
お疲れ様です。
ずいぶん速くなりましたね〜。
ソフトとハード共に進化してるようですね。
この先は並列化したほうがよさそうですね。
サーバが７手目か８手目の局面を発行してクライアントに枝を数えさせて纏め上げるとか。

４×４のオセロで起こりうるあらゆる局面を整理して
それを視覚的にわかりやすく表示するってこと誰かできますか？

４×４なら起こりうるあらゆる局面を整理することは可能。
ただ、視覚的にわかりやすく表示するというのが
どういったものを指すのかがよくわからない。

ゼブラの研究モードのようなものを指すのか
いくつかの予想進行をビデオ再生するようにするのか
考えられることはいろいろあるけど。

理想は一枚の静止画です。
ただそれはあくまで理想で、
棋譜の列挙でも十分有り難いです

>>693
それなら、SAIOのデモ版を使うといいと思う。
棋譜の列挙ならゼブラでもできたはず。

多少スレチな話題なんでそれ以上は他で聞いたほうがいいかも。

しらみつぶし以外に解を出す方法あるの?

勝ち負け引き分けの3通りじゃないのか

いや、余裕勝ちとか惜敗とか、いろいろあるだろうが

>>697
逆転勝ちもいれようか

オセロで逆転を定義するのはかなり難しい

逆転とは相手又は自分の悪手により引き分けラインを跨ぐ事。
某プログラムでは非引き分けから引き分けになる事やその逆も逆転として扱っていたが。

>>13
６４対０から始まり、０対６４まで だと65通りだぞ

盤面全部埋まる保証はない

>>702
全滅は64対0扱いになるそうな。62対2の終局図ってｗ

オセロのルールで試合結果は石差で表現する
石差は基本的に｛自分の石数−相手の石数｝
但し一方の石が0になった場合は日本でも外国でも64石差扱い
残った空きの数は日本ルールでは両者で折半するが外国ルールでは勝者の石として加算

62:2は60石差
64:0は64石差
62:0は64石差扱い
62:1は日本では61石差で外国では62石差扱い

オセロ有段者だけど試合結果は64石差、62石差〜0石差(引き分け)の64パターンですよ
おもしろそうだから頑張ってね

試合に負けて、勝負に勝つ、とかはどうカウントするの？

私が無知でした

>>707みたいなのは無知の知だったっけ？

誤りを指摘されてからじゃダメだろ

62:1が日本ルールでは考慮されるってことは
厳密には間違いではないのでは？

>>709
まず言葉の意味を調べような

「自分の知識が完全ではない事に気がついている」ってことだろ？
指摘されて初めて無知であることに気づいたんじゃ該当しないだろ

>>1

簡単なことだよ

>>2->>712 はもう一回小学校の算数からやり直したほうがいい。

(1)俺が勝つ
(2)俺が負ける
(3)引き分け

の3通りだ

>>713
俺が勝つ、お前が負けるの二通り

┏━━━━━━━━━━━━━━━━━┓　　 　 ＿ 　
┃┌─┬─┬─┬─┬─┬─┬─┬─┐┃ ,.^〈〉'´ 　ヽ〈〉ヽ.
┃│●│●│●│●│●│●│★│ 　│┃( （〈〉.ﾉ从）)〈〉） ）
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃ ） ）(li.ﾟ ヮﾟﾉ! （ (　
┃│○│○│○│●│●│●│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃いくみん　●　３１
┃│●│○│●│○│●│○│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│●│●│○│○│○│○│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃
┃│●│●│●│○│○│○│ 　│ 　│┃　_＿__
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃ / 　　 `ミ
┃│●│○│●│●│○│○│ 　│ 　│┃i´ 从从ミ
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃` ﾘ;ﾟ -ﾟﾉ 　
┃│●│●│○│●│●│○│ 　│ 　│┃
┃├─┼─┼─┼─┼─┼─┼─┼─┤┃ Ｕ - １　○　１８
┃│●│●│●│●│●│●│ 　│ 　│┃
┃└─┴─┴─┴─┴─┴─┴─┴─┘┃
┗━━━━━━━━━━━━━━━━━┛