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

いつ終わるんだろうこれ・・・・

どっかに全探索データベース作って分散コンピューティングとやらで作業分担して完成を目指すってのはできないもんだろうか

{
　　　前の手へのリンク
　　　この手で打った石の情報
　　　この手へリンクしている次の手へのリンク1
　　　この手へリンクしている次の手へのリンク2
　　　この手へリンクしている次の手へのリンク3
…
　　　この手へリンクしている次の手へのリンクn
}

こんな感じで1手毎の検索結果を貯めていけないだろうか

データベースと検索プログラムを分ければ検索プログラムを逐次改良しながらデータベースを補完していけるんじゃないかな

にしたってすごいリソースが必要ですよね・・・

>>822
はいよ↓
http://www9.atwiki.jp/othello/pages/40.html

>>757 の通り手ごろな初期配置を種に単純分散処理することになるかな。
好意的に見ても７手目の 55092/(対称性) ≒ 10000 CPU くらいか。
7〜60 は１問題でもまだ無理でしょ。
単純並列化の出番はないと思うね。

単純並列化より、例えば途中の枝狩りを相互に通信し合うとか、
アルゴリズム的なところの変革も必要かな。

もしくは othello_counterX.cpp みたいな
いつもの「深さ優先探索君」に並行して「突っ込み君」を走らせて、
「あ、その枝計算しなくていいよ」みたいな突っ込みで
大きなバックトラックをさせるとか、
ヘテロかつミクロな並列化に期待。

あり得ない盤面をカットする、ってのが上であるけど、
深さ優先探索君はもともとあり得る盤面しか追わないから意味ないよね。
考えうるのは

突っ込み君＞「あ、その枝はこっちの枝と対称だから、俺が棋譜数コピーしといてやるから君はやらなくていいよ」

でしょうか。
幾何学的な対称性の枝狩りは、初期配置で既にカットしてるからやる意味ない？
どうなんでしょう？
非対称から始まって途中から対称形出てきたりもしますけど。

もう５年も経ったのか・・・

wiki に「最大着手可能数」のページを作った。
http://www9.atwiki.jp/othello/pages/50.html

乙

>>770->>784 の流れで
＋＋＋＋＋＋＋＋
＋○？？？？○＋
＋？●？？●？＋
＋？？！！？？＋
＋？？！！？？＋
＋？●？？？？＋　？＝{●,○,＋}、！＝{●,○}
＋○？？？？○＋　●は10個、○は19個、＋は35個
＋＋＋＋＋＋＋＋

現在これ探索中。
全探索まで 3〜17※ 時間かかるもよう。

※真ん中４つの空白禁止無しで探索盤面数を計算すると
探索盤面数
＝(まだ置いていない黒の数＋まだ置いていない白の数＋まだ置いていない空の数)_C_(まだ置いていない黒の数)
×(まだ置いていない白の数＋まだ置いていない空の数)_C_(まだ置いていない白の数)
＝266181664320 となる。
これを全探索すると 17 時間かかることになるんだけど、
「真ん中４つは空白禁止」の枝狩りを入れると経験上全探索盤面数が 1/6 くらいに減って
。3時間くらいで終わる概算になる。

誰かこの「真ん中４つは空白禁止」のときの
厳密な全探索数の計算の仕方を考えてくれない？
終了時間に数倍の幅が残ってるとシミュレーション上ちょっと辛いので。

>>784
>誰かこの「真ん中４つは空白禁止」のときの
>厳密な全探索数の計算の仕方を考えてくれない？
これをブレークダウンすると↓

---
●X個、○Y個、＋Z個を１列に並べる並べ方は全部で何通りあるか？
ただし、左端４つは＋を並べてはいけない。
---

ちなみに
●X個、○Y個、＋Z個を１列に並べる並べ方は全部で何通りあるか？の解は、
(X+Y+Z)_C_(X) * (Y+Z)_C_(Y)。

書き込み test

あ、結局真ん中の 16 パターンで分岐して探索して最後加算することで解決しました。
それで計算した結果 >>784 は 12時間半の探索であることが判明(speed=4.0Mboards/sec C2Q 2.4GHz)

>>829 全探索完了
...
33 1562 boards
34 20 boards
35 0 boards
何故か5.6時間くらいで答えが出た。
（4Mboards/s のスピードから計算するとそっちが正しかった）
35手は無理なんじゃ…？
しかし確信をもって言えるほど広い探索でもないのは確か。
＋＋＋＋！＋＋＋
＋○？？＋？○＋
＋？？？？？？＋ >>775 の弱いところは、
＋？？？？？？＋ ←のような拘束条件が、>>775 の拘束条件よりも
＋？？？？？？＋ 大きな着手可能を持って実棋譜上に表れることを
＋？？？？？？＋ 必ずしも否定できないところかな。
＋○？？？？○＋ 定性的には >>775 拘束の方がそりゃあ実棋譜上に載り易いだろうけど、
＋＋＋＋＋＋＋＋ それは証明された確信じゃないしね。

方向転換して、
初期配置と石数拘束を証明できる範囲にまで広げて、
逆にアルゴリズム的に着手可能手数拘束枝刈りを入れた方がいいかな。
35 手以上にどうしてもならない枝を刈るみたいな。

途中で試合放棄っていうのは？

当然考慮すべき

私も着手数の探索をやってみました。
>829で気になったのは黒●を10に固定しているのと、
空白を35に固定している事の２点。
なので私は以下の条件でやってみた。
＋＋＋＋＋＋＋＋
＋○？？？？○＋
＋？！？？！？＋
＋？？！！？？＋
＋？？！！？？＋
＋？！？？！？＋　？＝{●,○,＋}、！＝{●,○}
＋○？？？？○＋　●は9〜14個、＋は35か36個、残りが○
＋＋＋＋＋＋＋＋

ただしこのままでは探索数が多すぎるので、少し論理的なカットはしました。
探索時間延べ３日くらい掛けた結果は、最大34着手までしか見つからずorz
見つかった中で面白そうなのが下の左図。
盤面右下を少し変更すると右図になります。

★★★★★★★★　　　★★★★★★★★
★○○●○○○★　　　★○○●○○○★
★○●★★●●★　　　★○●★★●●★
★●★●○★○＋　　　★●★●○★○＋
★○★○●●★★　　　★○★○●●★★
★○●★●○○★　　　★○●★●○○★
★○●○★○○★　　　★○●○★○★★
★★★＋★★★★　　　★★★＋★★★＋
（左図）着手可能数=34 黒=11 白=17 空白=36
（右図）着手可能数=34 黒=11 白=16 空白=37

星の白○４箇所縛りも外したほうが良いんだろうか。

デッドロックの直前の手は必ず1通り？
それとも複数あってその内これを選べばデッドロックって事あるだろうか？

最大着手数 46 の存在を翻しておこう。

最大着手数 46 を仮定する。
次のターンは●だとする。
このとき、>>331 あたりの話から
●は６個、○は12個限定となる。

●が抱えられる★のキャパは最大８つ。
よって、６つの●の総キャパは48個。
ということは★２つ分しかさぼれず、
どの●も最低「６つ」は★を持っていないといけない。

ここで一番北西にある○に注目しよう。
複数あるときはそのうちのひとつに注目する。
こいつはどの方向に相方の●を持てるか？
たとえばさらに「北西の方向に持てる」と仮定する。

？？？？！　←こんな状況だ。？には○はない。
？●？！！　するとその相方●は、他に５つの○と手を繋げるか？
？？○！！　さっきの○が最北西なのだから、最大でもあと２つ、
？！！！！ 「南、東」にしか繋げない。よってこれは無理。
！！！！！　

ＡＢＣ　結局同じ論法で、○は
Ｄ○Ｅ　←のうちの「Ｅ、Ｇ、Ｈ」の方向にしか相方●が持てず、
ＦＧＨ　高々３方向しか繋げないということが分かる。

（つづく）

（>>383 のつづき）

同じ論法で、「最北東の○、最南西の○、最南東の○」も
高々３つの相方しか持てないことが分かる。

また、この話は「最北の○、最南の○、最東の○、最西の○」にも言える。

ＡＢＣ　例えば「最北の○」は、このうちの「Ｆ、Ｇ、Ｈ」の高々３方向にしか繋げない。
Ｄ○Ｅ　もし「Ａ、Ｂ、Ｃ、Ｄ、Ｅ」に相方●がいると仮定すると、
ＦＧＨ　さっきと同じようにそいつの愛人が足りなくなるのだ。

よって、「ある最果ての地にいる８人の○」はみな３つしか相方を持てない。

ところで○が抱えられる★のキャパは最大４つ。
よって、12個の○の総キャパも48個。
ということは全体で★２つ分しかさぼれず、
「さぼっている○」は最高でも全体で２人まで。

さて、「８人の最果て者」は全員さぼっている○だ。
４つ手があるはずが高々３つなのだから。

さて、「最南かつ最南東」とか、ひとつの○が
「複数の最果て者」を兼ねている場合も考えられるだろうが、
12個もの○を包括するためには、最低でも「３人の異なる最果て者」が必要だ。
彼らが多角形をなして初めて内部が生まれ、全12人が収容できる。
しかしやはり「さぼれる○」は最高で２つまで。
２人までしか最果て者には成り得ない。
ここで矛盾が生まれ、題意「最大着手数 46」が否定される。

4×4の結果
全60060通り
黒勝ち24632通り
白勝ち30116通り
分5312通り
3時間18分36秒

今6×6を解析しています
また、上記は全パターンの解析時間ですので
1手目の対象性から1/4でやっていれば50分かからないで終わってます。

今やってる6×6は1/4で解析しています

プログラムが遅すぎるというかゲーム木が大きすぎるというか
6x6でも君が生きてるうちには決して終わらないから今すぐやめたほうが。

ウィキペディア見たら6×6までは完全解析されているみたいだけど
調べても何通りあるか見当たらない。

割りとかなりおそくないか
一試合1.5秒くらいかかってる計算になるね。
しかも4x4なら12手しかないわけで…

誰か彼の4x4の結果から6x6ならどれくらいかかりそうか概算してやってくれ

4×4の時間なのですが
最初のプログラムは色々と機能を実装してまして
また、ぐるぐる回してるのですが途中で休憩しないと
CPUが100%になるので0.05秒お休みさせてました。

そんなのを改良して4×4をやりましたら
10分27秒で終わりました。

>>844
１試合 0.01秒くらいに落ちたね。おめでとう

だがしかし
4x4 の 12 手が全部埋まってから外側の 16 手を埋める変則ルールで考えても
改良後のプログラムで 416.6667 日はかかる計算になるよ。
あと千倍くらいはスピードアップしたいね。
ドラゴンボールみたいな世界だな…ここは。

さて、最大着手数 45 をやっつけてみよう。
その前に、ある最大着手数を考えたときに
●と○の数の範囲が限られるので、
それについて整理しておく。

最大着手数★を固定すると、
●と○の範囲が限定される。
大本が >>331 で、こうなる↓
ceil(★/8) <= ●
ceil(★/4) <= ○
ceilは小数点以下繰り上げの意味。
そして元々の ●＋○＋★<64 より、
ceil(★/8) <= ● <= 64-★-○ ...(1)
ceil(★/4) <= ○ <= 64-★-● ...(2)
となる。

もうひとつ、良く使う用語の定義を。
盤面に現れる●と○について、
それがないと消えちゃう着手数というものがある。
寄与している着手数とも言ったりしてる。
それの最大は >>331 で
● については最大８個、○については最大４個と説明されている。
そこで、ある●や○について、
その●の余腕数 = 8-その●の寄与している着手数
その○の余腕数 = 4-その○の寄与している着手数
と定義する。
●は８本、○は４本「腕」を持っていると考えて、余ってる腕の数、というわけ。
ある着手数を持つ盤面において、
全ての●、○の余腕数を加算したものを●の総余腕数、○の総余腕数ということにしよう。
すると、ある着手可能数★について、
●の総余腕数の最大 = 8●-★
○の総余腕数の最大 = 4○-★

となる。これを例えば ★44〜46 で全探索で調べると
★=46, ●=6, ○=12, ●総余腕<= 2, ○総余腕<= 2
★=45, ●=6, ○=12, ●総余腕<= 2, ○総余腕<= 2
★=45, ●=6, ○=13, ●総余腕<= 2, ○総余腕<= 6
★=45, ●=7, ○=12, ●総余腕<=10, ○総余腕<= 2
★=44, ●=6, ○=12, ●総余腕<= 2, ○総余腕<= 2
★=44, ●=6, ○=13, ●総余腕<= 2, ○総余腕<= 6
★=44, ●=6, ○=14, ●総余腕<= 2, ○総余腕<=10
★=44, ●=7, ○=12, ●総余腕<=10, ○総余腕<= 2
★=44, ●=7, ○=13, ●総余腕<=10, ○総余腕<= 6
★=44, ●=8, ○=12, ●総余腕<=18, ○総余腕<= 2
となる。
>>846 の式 (1),(2)を満たさないものと、
総余腕数が負になるものは、その時点でアウトとして省いてある。

では最大着手数 45 の否定を。
「最果ての○は自分の余碗を消耗してしまう」という原理を応用する。
○の最果ては８つあり、その最果ての「内部」にしか●がない場合は
○はそこでそれぞれ１つ○余碗を消費してしまう。
内部は３方向だけであり、腕の総数４に満たないからだ。
複数の最果てを○が兼ねたら、その兼ねた数だけ○余碗を消費する。
結局●がライン上かもしくは最果ての外にない限り、
○は計８余碗の消費を免れない。

ex最北　最北西　
５５５ ７５４　最果ての○の余碗を消すには、
４○４ ５○１　最果てライン上か、最果ての外に相棒●を追加せざるを得なくなる。
０００ ４１０　そのとき、相棒●の位置と消費してしまう●の余碗数は次のようになる。

つまり、ひとつの最果ての○の余碗１つの消去につき最低でも４の●余碗を消費する。
つまり、○余碗の回復のための「●の外打ち」数をＮとすると、
○の総余碗数 >= 8-N
●の総余碗数 >= 4N
となる。これを連立させて解くと、
32 <= ●の総余碗数 + 4○の総余碗数
が必要になる。

これを満たす ★=42〜46 を全て書きだすと、
★=44, ●=7 , ○=13, ●余腕=10, ○余腕= 6

★=43, ●=6 , ○=14, ●余腕= 2, ○余腕=10
★=43, ●=6 , ○=15, ●余腕= 2, ○余腕=14
★=43, ●=7 , ○=13, ●余腕=10, ○余腕= 6
★=43, ●=7 , ○=14, ●余腕=10, ○余腕=10
★=43, ●=8 , ○=13, ●余腕=18, ○余腕= 6
★=43, ●=9 , ○=12, ●余腕=26, ○余腕= 2

★=42, ●=6 , ○=14, ●余腕= 2, ○余腕=10
★=42, ●=6 , ○=15, ●余腕= 2, ○余腕=14
★=42, ●=6 , ○=16, ●余腕= 2, ○余腕=18
★=42, ●=7 , ○=13, ●余腕=10, ○余腕= 6
★=42, ●=7 , ○=14, ●余腕=10, ○余腕=10
★=42, ●=7 , ○=15, ●余腕=10, ○余腕=14
★=42, ●=8 , ○=13, ●余腕=18, ○余腕= 6
★=42, ●=8 , ○=14, ●余腕=18, ○余腕=10
★=42, ●=9 , ○=12, ●余腕=26, ○余腕= 2
★=42, ●=9 , ○=13, ●余腕=26, ○余腕= 6
★=42, ●=10, ○=12, ●余腕=34, ○余腕= 2

である。よって最大着手 45 は否定される。

ちなみに、この話を実際のオセロ盤の広さで考えてみると、
最果てを兼ねるなんて言ってる場合ではなくて、
できるだけ「内部」を広く取って
できるだけたくさんそこに石を詰めれるように
最果て○をいっぱい作らなくといけなくなって、
そのために着手数をもっと削らないといけないことがよく分かる。
今日は以上です。

長き解析お疲れ様です。5年分のレス見てみたけど　素人の私でも感動･･･
どうか、初見の方は、応援するだけしてゆっくりと見守ってほしいですな。

分散型のソフトを開発したら皆さん参加しますか？
作ろうかどうか皆さんの反応で決めたいと思います。

>>851
まず分散型じゃないソフトをつくるんだ！

>>852
もう作って解析しております

どれくらいの速度？

解析って全探索？

8×8のオセロが解析出来たら、
次は10×10のグランドオセロもおながいします

てか VHDL とか論理回路で実装したらめっちゃはやくね？
INIT:
　own = 0x0000001000000000;
　opp = 0x0000000818080000;
　pStuck = 0;
　count = 0;
BEGIN:
　can = revchk(own,opp);
　if can goto SET;
PASS:
　{opp,own}={own,opp};
　can = revchk(own,opp);
　if can goto SET;
GAMEOVER:
　if pStuck==0 then halt;
　count++;
　{own,opp,can} = stuck[--pStuck]; //pop
　if can goto SET else BEGIN;
SET:
　set = least1(can);
　can = can & ~set;
　stuck[pStuck++] = {opp,own,can}; //stuck
　[opp,own] = setrev(own,opp,set);
　goto BEGIN;

これをこんな風に最適化して stuck, pop, goto BEGIN, halt が生じる間の計算を全部１クロックで実現可能。
BEGIN:
　}simultaneously if(!revchk(own,opp) && !revchk(opp,own) && !pStuck && stuck[pStuck-1].can){
　　{{own,opp,can}, stuck[pStuck], count} = {
　　　stuck[pStuck],
　　　{opp, own, revchk(own,opp) & ~least1(revchk(own,opp))},
　　　count+1
　　}; //pop and stuck
　}simultaneously if(!revchk(own,opp) && !revchk(opp,own) && !pStuck && !stuck[pStuck-1].can){
　　{{own,opp,can}, pStuck, count} = {stuck[pStuck], pStuck-1, count+1}; //pop
　}simultaneously if(revchk(own,opp)){
　　{{opp,own}, stuck[pStuck], pStuck} = {
　　　setrev(own,opp,~least1(revchk(own,opp))),
　　　{opp, own, revchk(own,opp) & ~least1(revchk(own,opp)),
　　　pStuck+1
　　}; //stuck
　}simultaneously if(revchk(own,opp) && !revchk(own,opp)){
　　{{own,opp}, stuck[pStuck], pStuck} = {
　　　setrev(opp,own,~least1(revchk(opp,own))),
　　　{own, opp, revchk(opp,own) & ~least1(revchk(opp,own)),
　　　pStuck+1
　　}; //stuck
　}else{
　　halt;// halt
　}
　goto BEGIN;
"simultaneously if" は同時に評価するってことね。
own(64), opp(64), can(64), stuck[pStuck](192), stuck[pStuck-1].can(64), count(233), pStuck(7) の
計 688 ビットの並列のフリップフロップと
(64+64+64)x64 = 12288 ビットのスタックメモリさえあればＯＫ

stuck ってなんだよ。stack だよ

>>650
四隅空いた状態で勝ったことあるよ
珍しいから写メ撮った

ああ、あのときね
なんで盤面撮らずに俺撮るんだろうと思ったけど
四隅空いた盤面よりそんな俺の顔の方が珍しいってか、あはは

お前馬鹿にしてんのか

>>858 の感じで Verilog-HDL で記述した。
>>858 は結構間違い入ってるのが判明したけど。
4x4 のシミュレーションでちゃんと 60060 通りって出たから合ってると思う。

着手可能手探索＋石反転＋深化 or バックトラックを合わせて 1clk、
そのあとにメモリリードライトで 1clk という設計。
ほんとはこの２つをパイプラインにすればさらに半分になるんだけど。
探索完了まで 191,375 clk でした。
FPGA ってだいたい何 MHz までいけるんだっけ。
メモリを外付けにするならそこの I/O の時間も気になってくる。
ちなみに 4x4 の CPU シミュレーションだと 18 分かかります

http://alfalia.web.fc2.com/wreversi/

あげるよ

まだ発表されてないが８ｘ８オセロも後手必勝。
これは検証プロセスと論文準備の段階。
もうすぐパブリックレポート。

ちなみに６ｘ６も後手必勝。
これは結構前に発表されている。

デタラメは要らないから。

なんか話題ないの？

試合結果は「勝」「負」「引き分け」の三通りしかないだろ。
試合経過はたくさんあるけど・・・

保守

本日　小林哲夫　愛知県半田市在住　
東京三菱ＵＦＪ銀行を相手取りいじめ問題の訴訟を起こした

受付日　平成２２年８月９日　名古屋地方裁判所受付
番号　（ワ）第５５２９号

http://kissho3.xii.jp/100/src/1kichi15880.jpg.html DLキー= 1
http://kissho3.xii.jp/100/src/1kichi15879.jpg.html DLキー= 1
http://kissho3.xii.jp/100/src/1kichi15878.jpg.html DLキー= 1