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

このエントリーをはてなブックマークに追加
821名無しさん@5周年:2009/10/14(水) 11:36:44
いつ終わるんだろうこれ・・・・
822名無しさん@5周年:2009/10/25(日) 15:27:08
どっかに全探索データベース作って分散コンピューティングとやらで作業分担して完成を目指すってのはできないもんだろうか

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

   この手へリンクしている次の手へのリンクn
}

こんな感じで1手毎の検索結果を貯めていけないだろうか
823名無しさん@5周年:2009/10/25(日) 15:29:25
データベースと検索プログラムを分ければ検索プログラムを逐次改良しながらデータベースを補完していけるんじゃないかな
824名無しさん@5周年:2009/10/27(火) 16:25:12
にしたってすごいリソースが必要ですよね・・・
825名無しさん@5周年:2009/11/23(月) 23:43:08
>>822
はいよ↓
http://www9.atwiki.jp/othello/pages/40.html

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

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

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

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

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

でしょうか。
幾何学的な対称性の枝狩りは、初期配置で既にカットしてるからやる意味ない?
どうなんでしょう?
非対称から始まって途中から対称形出てきたりもしますけど。
826名無しさん@5周年:2009/11/27(金) 14:04:57
もう5年も経ったのか・・・
827名無しさん@5周年:2009/11/27(金) 19:54:21
wiki に「最大着手可能数」のページを作った。
http://www9.atwiki.jp/othello/pages/50.html
828名無しさん@5周年:2009/11/27(金) 20:16:57
829784:2009/11/27(金) 22:02:59
>>770->>784 の流れで
++++++++
+○????○+
+?●??●?+
+??!!??+
+??!!??+
+?●????+ ?={●,○,+}、!={●,○}
+○????○+ ●は10個、○は19個、+は35個
++++++++

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

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

誰かこの「真ん中4つは空白禁止」のときの
厳密な全探索数の計算の仕方を考えてくれない?
終了時間に数倍の幅が残ってるとシミュレーション上ちょっと辛いので。
830784:2009/11/27(金) 22:13:30
>>784
>誰かこの「真ん中4つは空白禁止」のときの
>厳密な全探索数の計算の仕方を考えてくれない?
これをブレークダウンすると↓

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

ちなみに
●X個、○Y個、+Z個を1列に並べる並べ方は全部で何通りあるか?の解は、
(X+Y+Z)_C_(X) * (Y+Z)_C_(Y)。
831test:2009/11/27(金) 22:24:21
書き込み test
832784:2009/11/27(金) 23:33:42
あ、結局真ん中の 16 パターンで分岐して探索して最後加算することで解決しました。
それで計算した結果 >>784 は 12時間半の探索であることが判明(speed=4.0Mboards/sec C2Q 2.4GHz)
833784:2009/11/28(土) 23:44:07
>>829 全探索完了
...
33 1562 boards
34 20 boards
35 0 boards
何故か5.6時間くらいで答えが出た。
(4Mboards/s のスピードから計算するとそっちが正しかった)
35手は無理なんじゃ…?
しかし確信をもって言えるほど広い探索でもないのは確か。
++++!+++
+○??+?○+
+??????+ >>775 の弱いところは、
+??????+ ←のような拘束条件が、>>775 の拘束条件よりも
+??????+ 大きな着手可能を持って実棋譜上に表れることを
+??????+ 必ずしも否定できないところかな。
+○????○+ 定性的には >>775 拘束の方がそりゃあ実棋譜上に載り易いだろうけど、
++++++++ それは証明された確信じゃないしね。

方向転換して、
初期配置と石数拘束を証明できる範囲にまで広げて、
逆にアルゴリズム的に着手可能手数拘束枝刈りを入れた方がいいかな。
35 手以上にどうしてもならない枝を刈るみたいな。
834名無しさん@5周年:2009/12/02(水) 18:46:32
途中で試合放棄っていうのは?
835名無しさん@5周年:2009/12/02(水) 21:06:53
当然考慮すべき
836名無しさん@5周年:2009/12/19(土) 17:30:48
私も着手数の探索をやってみました。
>829で気になったのは黒●を10に固定しているのと、
空白を35に固定している事の2点。
なので私は以下の条件でやってみた。
++++++++
+○????○+
+?!??!?+
+??!!??+
+??!!??+
+?!??!?+ ?={●,○,+}、!={●,○}
+○????○+ ●は9〜14個、+は35か36個、残りが○
++++++++

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

★★★★★★★★   ★★★★★★★★
★○○●○○○★   ★○○●○○○★
★○●★★●●★   ★○●★★●●★
★●★●○★○+   ★●★●○★○+
★○★○●●★★   ★○★○●●★★
★○●★●○○★   ★○●★●○○★
★○●○★○○★   ★○●○★○★★
★★★+★★★★   ★★★+★★★+
(左図)着手可能数=34 黒=11 白=17 空白=36
(右図)着手可能数=34 黒=11 白=16 空白=37

星の白○4箇所縛りも外したほうが良いんだろうか。
837名無しさん@5周年:2009/12/24(木) 23:08:02
デッドロックの直前の手は必ず1通り?
それとも複数あってその内これを選べばデッドロックって事あるだろうか?
838名無しさん@5周年:2009/12/26(土) 02:51:59
最大着手数 46 の存在を翻しておこう。

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

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

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

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

ABC 結局同じ論法で、○は
D○E ←のうちの「E、G、H」の方向にしか相方●が持てず、
FGH 高々3方向しか繋げないということが分かる。

(つづく)
839名無しさん@5周年:2009/12/26(土) 02:52:55
>>383 のつづき)

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

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

ABC 例えば「最北の○」は、このうちの「F、G、H」の高々3方向にしか繋げない。
D○E もし「A、B、C、D、E」に相方●がいると仮定すると、
FGH さっきと同じようにそいつの愛人が足りなくなるのだ。

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

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

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

さて、「最南かつ最南東」とか、ひとつの○が
「複数の最果て者」を兼ねている場合も考えられるだろうが、
12個もの○を包括するためには、最低でも「3人の異なる最果て者」が必要だ。
彼らが多角形をなして初めて内部が生まれ、全12人が収容できる。
しかしやはり「さぼれる○」は最高で2つまで。
2人までしか最果て者には成り得ない。
ここで矛盾が生まれ、題意「最大着手数 46」が否定される。
840名無しさん@5周年:2009/12/26(土) 16:27:35
4×4の結果
全60060通り
黒勝ち24632通り
白勝ち30116通り
分5312通り
3時間18分36秒

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

今やってる6×6は1/4で解析しています
841名無しさん@5周年:2009/12/26(土) 17:27:27
プログラムが遅すぎるというかゲーム木が大きすぎるというか
6x6でも君が生きてるうちには決して終わらないから今すぐやめたほうが。
842名無しさん@5周年:2009/12/26(土) 22:45:09
ウィキペディア見たら6×6までは完全解析されているみたいだけど
調べても何通りあるか見当たらない。
843名無しさん@5周年:2009/12/26(土) 23:00:10
割りとかなりおそくないか
一試合1.5秒くらいかかってる計算になるね。
しかも4x4なら12手しかないわけで…

誰か彼の4x4の結果から6x6ならどれくらいかかりそうか概算してやってくれ
844840:2009/12/26(土) 23:33:36
4×4の時間なのですが
最初のプログラムは色々と機能を実装してまして
また、ぐるぐる回してるのですが途中で休憩しないと
CPUが100%になるので0.05秒お休みさせてました。

そんなのを改良して4×4をやりましたら
10分27秒で終わりました。
845名無しさん@5周年:2009/12/26(土) 23:42:50
>>844
1試合 0.01秒くらいに落ちたね。おめでとう

だがしかし
4x4 の 12 手が全部埋まってから外側の 16 手を埋める変則ルールで考えても
改良後のプログラムで 416.6667 日はかかる計算になるよ。
あと千倍くらいはスピードアップしたいね。
ドラゴンボールみたいな世界だな…ここは。
846名無しさん@5周年:2009/12/27(日) 00:53:36
さて、最大着手数 45 をやっつけてみよう。
その前に、ある最大着手数を考えたときに
●と○の数の範囲が限られるので、
それについて整理しておく。

最大着手数★を固定すると、
●と○の範囲が限定される。
大本が >>331 で、こうなる↓
ceil(★/8) <= ●
ceil(★/4) <= ○
ceilは小数点以下繰り上げの意味。
そして元々の ●+○+★<64 より、
ceil(★/8) <= ● <= 64-★-○ ...(1)
ceil(★/4) <= ○ <= 64-★-● ...(2)
となる。
847名無しさん@5周年:2009/12/27(日) 00:57:59
もうひとつ、良く使う用語の定義を。
盤面に現れる●と○について、
それがないと消えちゃう着手数というものがある。
寄与している着手数とも言ったりしてる。
それの最大は >>331
● については最大8個、○については最大4個と説明されている。
そこで、ある●や○について、
その●の余腕数 = 8-その●の寄与している着手数
その○の余腕数 = 4-その○の寄与している着手数
と定義する。
●は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)を満たさないものと、
総余腕数が負になるものは、その時点でアウトとして省いてある。
848838:2009/12/27(日) 00:59:16
では最大着手数 45 の否定を。
「最果ての○は自分の余碗を消耗してしまう」という原理を応用する。
○の最果ては8つあり、その最果ての「内部」にしか●がない場合は
○はそこでそれぞれ1つ○余碗を消費してしまう。
内部は3方向だけであり、腕の総数4に満たないからだ。
複数の最果てを○が兼ねたら、その兼ねた数だけ○余碗を消費する。
結局●がライン上かもしくは最果ての外にない限り、
○は計8余碗の消費を免れない。

ex最北 最北西 
555 754 最果ての○の余碗を消すには、
4○4 5○1 最果てライン上か、最果ての外に相棒●を追加せざるを得なくなる。
000 410 そのとき、相棒●の位置と消費してしまう●の余碗数は次のようになる。

つまり、ひとつの最果ての○の余碗1つの消去につき最低でも4の●余碗を消費する。
つまり、○余碗の回復のための「●の外打ち」数をNとすると、
○の総余碗数 >= 8-N
●の総余碗数 >= 4N
となる。これを連立させて解くと、
32 <= ●の総余碗数 + 4○の総余碗数
が必要になる。
849838:2009/12/27(日) 01:00:06
これを満たす ★=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 は否定される。

ちなみに、この話を実際のオセロ盤の広さで考えてみると、
最果てを兼ねるなんて言ってる場合ではなくて、
できるだけ「内部」を広く取って
できるだけたくさんそこに石を詰めれるように
最果て○をいっぱい作らなくといけなくなって、
そのために着手数をもっと削らないといけないことがよく分かる。
今日は以上です。
850名無しさん@5周年 ◆ZTZ.ji25iA :2009/12/27(日) 09:22:34
長き解析お疲れ様です。5年分のレス見てみたけど 素人の私でも感動・・・
どうか、初見の方は、応援するだけしてゆっくりと見守ってほしいですな。
851名無しさん@5周年:2009/12/27(日) 16:53:19
分散型のソフトを開発したら皆さん参加しますか?
作ろうかどうか皆さんの反応で決めたいと思います。
852名無しさん@5周年:2009/12/27(日) 18:40:20
>>851
まず分散型じゃないソフトをつくるんだ!
853名無しさん@5周年:2009/12/27(日) 19:09:43
>>852
もう作って解析しております
854名無しさん@5周年:2009/12/27(日) 19:27:38
どれくらいの速度?
855名無しさん@5周年:2009/12/27(日) 21:18:30
解析って全探索?
856名無しさん@5周年:2009/12/28(月) 04:42:02
8×8のオセロが解析出来たら、
次は10×10のグランドオセロもおながいします
857名無しさん@5周年:2009/12/28(月) 23:37:24
てか 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;
858857:2009/12/28(月) 23:39:02
これをこんな風に最適化して stuck, pop, goto BEGIN, halt が生じる間の計算を全部1クロックで実現可能。
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 ビットのスタックメモリさえあればOK
859857:2009/12/28(月) 23:59:32
stuck ってなんだよ。stack だよ
860名無しさん@5周年:2009/12/30(水) 03:32:58
>>650
四隅空いた状態で勝ったことあるよ
珍しいから写メ撮った
861名無しさん@5周年:2009/12/30(水) 05:29:53
ああ、あのときね
なんで盤面撮らずに俺撮るんだろうと思ったけど
四隅空いた盤面よりそんな俺の顔の方が珍しいってか、あはは

お前馬鹿にしてんのか
862名無しさん@5周年:2010/01/05(火) 20:30:40
>>858 の感じで Verilog-HDL で記述した。
>>858 は結構間違い入ってるのが判明したけど。
4x4 のシミュレーションでちゃんと 60060 通りって出たから合ってると思う。

着手可能手探索+石反転+深化 or バックトラックを合わせて 1clk、
そのあとにメモリリードライトで 1clk という設計。
ほんとはこの2つをパイプラインにすればさらに半分になるんだけど。
探索完了まで 191,375 clk でした。
FPGA ってだいたい何 MHz までいけるんだっけ。
メモリを外付けにするならそこの I/O の時間も気になってくる。
ちなみに 4x4 の CPU シミュレーションだと 18 分かかります
863名無しさん@5周年:2010/02/01(月) 19:16:05
864名無しさん@5周年:2010/02/26(金) 11:12:45
あげるよ
865名無しさん@5周年:2010/03/04(木) 00:52:02
まだ発表されてないが8x8オセロも後手必勝。
これは検証プロセスと論文準備の段階。
もうすぐパブリックレポート。

ちなみに6x6も後手必勝。
これは結構前に発表されている。
866名無しさん@5周年:2010/03/04(木) 01:31:41
デタラメは要らないから。
867名無しさん@5周年:2010/05/20(木) 19:17:53
なんか話題ないの?
868名無しさん@5周年:2010/05/20(木) 22:44:58
試合結果は「勝」「負」「引き分け」の三通りしかないだろ。
試合経過はたくさんあるけど・・・
869名無しさん@5周年:2010/08/09(月) 17:21:08
保守
870名無しさん@5周年
本日 小林哲夫 愛知県半田市在住 
東京三菱UFJ銀行を相手取りいじめ問題の訴訟を起こした

受付日 平成22年8月9日 名古屋地方裁判所受付
番号 (ワ)第5529号

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