791 :
757 :
2009/05/17(日) 04:51:42 逆に今見てすげーと思ったのは othello_counter の revchk_right()。 move = white + (white & (black << 1)); 以上。全部込みで3命令だ。 可算命令が連続チェックまで全部してくれてるんだ。 これかっこいい これさ、ビット回転使って他の方向も可算命令一発でできないの? >othello_counter の作者さん
793 :
757 :2009/05/20(水) 00:54:14
>>792 あ、それはビット演算スレに載ってたし
othello_counter4.cpp の中の別演算にも使われてるよ。
知ってて使ってないってことはやってみて結局経済的じゃなかったってことかな?
と思って
>>791 を書きこんだんだけど。
>回転して計算した後に逆回転して戻すの?
その必要があると思ったけど、
今考えると棋譜数の集計に使うだけなら
着手可能手判定の前だけ回転してそのまま深化して、
そのあとは別に放置でもいいんじゃないかな?
反転する石の判定(次手の盤面の生成)時には
逆回転もしくは回転を使わない逆方向の挟み判定も必要だけど。
着手可能手の発見→深化だけのとこだと戻す必要はなさそう。
盤面の同一性 or 対称同一性は見てないからね。
今着手可能手の発見と挟み判定は別処理してるよね?
着手可能手の発見と同時に挟み判定フラグもついでに立ててるならアウトだけど。
そうはなってないように見える
794 :
757 :2009/05/20(水) 01:07:26
move = revcheck_left(own,opp); while(move.f){ reverse=set_rev_left(own,opp); reverse=set_rev_right(own,opp)... nextopp=... SearchMove(nextopp, nextown, turn); } move = revcheck_left(rotate180(own),rotate180(opp)); while(move.f){ reverse=set_rev_left(own,opp); reverse=set_rev_right(own,opp)... nextopp=... SearchMove(nextopp, nextown, turn); } move = revcheck_left(rotate90(own),rotate90(opp))... みたいな感じでどうでしょ。 終了面カウントとパスカウントだけはできなくなりそうだけど。
revchk_left(own, opp) :17 step total:17 step rotateLR(own) :30 step rotateLR(opp) :30 step revchk_right(own, opp):6 step total:66 step でダメ。戻しなしとしても普通に rotateLR() が高価過ぎる
796 :
名無しさん@5周年 :2009/07/05(日) 20:48:50
あげ
797 :
名無しさん@5周年 :2009/07/17(金) 18:37:24
稀に見る良スレ
799 :
名無しさん@5周年 :2009/07/27(月) 11:08:35
人権擁護法案人権擁護法案人権擁護法案人権擁護法案人権擁護法案 人権擁護法案人権擁護法案人権擁護法案人権擁護法案人権擁護法案 民主議員多数参加 独裁政権 ヤバイんだって!! 言論抹殺 馬で遊んでる場合じゃねえぞ 人権擁護法案
黒勝ち、白勝ち、引き分け 3通り
801 :
名無しさん@5周年 :2009/08/14(金) 08:56:01
このスレは やまなし おちなし いみはある
802 :
名無しさん@5周年 :2009/09/08(火) 12:55:19
俺の勝ちかお前の負けの二通りだ!
「俺が台をひっくり返す」も入れろ
スレ上の方にある棋譜数の実測値の対数は手数に関して綺麗な直線になってる。 これに加えて着手可能数の少ない最終局面から逆算してく手法を使うと 棋譜数は10^50くらいになる。(10^55や10^60かもしれないが、覚えやすいということで50乗) ちなみに、計算モデルとして着手可能領域が円殻状に広がり円殻上の半分に石を置けると考えると実測値に近い値がでる。
>>803 「俺が台をひっくり返す」「お前が台をひっくり返す」
を入れて全探索してみました(※対称系は省きます)
以下、みつかった興味深い棋譜だけ抜粋します
1手終了棋譜
「俺が台をひっくり返す」
まず第一にやる気があるんでしょうか
それとも実は完全探索した挙句後手必勝と分かってて激怒したのでしょうか
バカと天才は紙一重ですね
興味深い棋譜です
64手終了棋譜
D3c3B3b2B1a1C4c1C2d2D1e1A2a3F5e2F1g1f2e3c5B4a5A4b5A6f4F3g3G2h2H1h3H4g4C6g5H5b6C7d6E6f6G6h6H7a7b7A8b8D7e7F7g7C8d8E8f8G8「お前が台をひっくり返す」
特に64手目、白37で勝ち必至の盤面で白、予想外の選択です
相手の弱さに嫌気が指したのでしょうか
そうだと推測するとその手は遅すぎます
5手目くらいで分かりそうなものですが
多分オセロなんかどうでもよくなる自体が発生したのでしょう
おそらく63手目を打たれた時点で
彼女が出来たのだろうと思います
おめでとうございます
>>804 分岐数の積の平均から求めた概算だと、
6.449E+54ぐらいらしいよ。
確か今までわかってるデータから求めた近似公式でもほとんど同じ値が出てたはず。
807 :
名無しさん@5周年 :2009/09/21(月) 06:49:13
809 :
名無しさん@5周年 :2009/10/09(金) 03:58:21
全ての分岐を羅列して数え上げてるんだけど 1日たってまだまだ8手目の20万通り程度
一日で20万局面って秒速2.3局面……
ちょっと書き換えて違うパソコンで走らせたら3時間で20万局面・・・
この手の全検索は、如何に無駄試行を減らせるかで検索速度は大分変わってくる オセロは綺麗な木構造だから、試行というより埋めていく処理に無駄があると速度が伸びないだろうな
ルールを考慮してソース書いたから無駄な試行はないとおもうけど 「明らかにここは角とるだろ」って局面でも見当違いなところ置いたりする試行があるのは否めないし 木構造といっても一手ごと羅列していかないと子ノードと親ノードの関連をつけるの面倒っていう・・・・
ん? 「全ての分岐を羅列して数え上げてる」んなら、 「『明らかにここは角とるだろ』って局面」も何もないんじゃないの?
>>815 何を言いたいのかわからないけど
その局面においていくつか置くことのできる場所がでると
そのうち何処においたかで分岐ができるかと
どっちの言ってることもわかるw
誰か解説して!
819 :
名無しさん@5周年 :2009/10/13(火) 18:57:23
とりあえずbitboardで検索だ!
深さ優先探索、配列ボード、Mobilityは律儀に一マスごとに置けるか見る。 これが一番簡単な実装だと思うが、それでもothello_counterの 数分の一程度の速度は出るはず。 オーダーが違うとか有り得ない。
いつ終わるんだろうこれ・・・・
822 :
名無しさん@5周年 :2009/10/25(日) 15:27:08
どっかに全探索データベース作って分散コンピューティングとやらで作業分担して完成を目指すってのはできないもんだろうか { 前の手へのリンク この手で打った石の情報 この手へリンクしている次の手へのリンク1 この手へリンクしている次の手へのリンク2 この手へリンクしている次の手へのリンク3 … この手へリンクしている次の手へのリンクn } こんな感じで1手毎の検索結果を貯めていけないだろうか
823 :
名無しさん@5周年 :2009/10/25(日) 15:29:25
データベースと検索プログラムを分ければ検索プログラムを逐次改良しながらデータベースを補完していけるんじゃないかな
にしたってすごいリソースが必要ですよね・・・
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年も経ったのか・・・
乙
829 :
784 :2009/11/27(金) 22:02:59
>>770-
>>784 の流れで
++++++++
+○????○+
+?●??●?+
+??!!??+
+??!!??+
+?●????+ ?={●,○,+}、!={●,○}
+○????○+ ●は10個、○は19個、+は35個
++++++++
現在これ探索中。
全探索まで 3〜17※ 時間かかるもよう。
※真ん中4つの空白禁止無しで探索盤面数を計算すると
探索盤面数
=(まだ置いていない黒の数+まだ置いていない白の数+まだ置いていない空の数)_C_(まだ置いていない黒の数)
×(まだ置いていない白の数+まだ置いていない空の数)_C_(まだ置いていない白の数)
=266181664320 となる。
これを全探索すると 17 時間かかることになるんだけど、
「真ん中4つは空白禁止」の枝狩りを入れると経験上全探索盤面数が 1/6 くらいに減って
。3時間くらいで終わる概算になる。
誰かこの「真ん中4つは空白禁止」のときの
厳密な全探索数の計算の仕方を考えてくれない?
終了時間に数倍の幅が残ってるとシミュレーション上ちょっと辛いので。
830 :
784 :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)。
書き込み test
832 :
784 :2009/11/27(金) 23:33:42
あ、結局真ん中の 16 パターンで分岐して探索して最後加算することで解決しました。
それで計算した結果
>>784 は 12時間半の探索であることが判明(speed=4.0Mboards/sec C2Q 2.4GHz)
833 :
784 :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
途中で試合放棄っていうのは?
当然考慮すべき
私も着手数の探索をやってみました。 >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通り? それとも複数あってその内これを選べばデッドロックって事あるだろうか?
最大着手数 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で解析しています
プログラムが遅すぎるというかゲーム木が大きすぎるというか 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ならどれくらいかかりそうか概算してやってくれ
844 :
840 :2009/12/26(土) 23:33:36
4×4の時間なのですが 最初のプログラムは色々と機能を実装してまして また、ぐるぐる回してるのですが途中で休憩しないと CPUが100%になるので0.05秒お休みさせてました。 そんなのを改良して4×4をやりましたら 10分27秒で終わりました。
>>844 1試合 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-その○の寄与している着手数
と定義する。
●は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)を満たさないものと、
総余腕数が負になるものは、その時点でアウトとして省いてある。
848 :
838 :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○の総余碗数 が必要になる。
849 :
838 :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 は否定される。 ちなみに、この話を実際のオセロ盤の広さで考えてみると、 最果てを兼ねるなんて言ってる場合ではなくて、 できるだけ「内部」を広く取って できるだけたくさんそこに石を詰めれるように 最果て○をいっぱい作らなくといけなくなって、 そのために着手数をもっと削らないといけないことがよく分かる。 今日は以上です。
長き解析お疲れ様です。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
854 :
名無しさん@5周年 :2009/12/27(日) 19:27:38
どれくらいの速度?
解析って全探索?
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;
858 :
857 :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
859 :
857 :2009/12/28(月) 23:59:32
stuck ってなんだよ。stack だよ
860 :
名無しさん@5周年 :2009/12/30(水) 03:32:58
>>650 四隅空いた状態で勝ったことあるよ
珍しいから写メ撮った
ああ、あのときね なんで盤面撮らずに俺撮るんだろうと思ったけど 四隅空いた盤面よりそんな俺の顔の方が珍しいってか、あはは お前馬鹿にしてんのか
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
あげるよ
まだ発表されてないが8x8オセロも後手必勝。 これは検証プロセスと論文準備の段階。 もうすぐパブリックレポート。 ちなみに6x6も後手必勝。 これは結構前に発表されている。
デタラメは要らないから。
867 :
名無しさん@5周年 :2010/05/20(木) 19:17:53
なんか話題ないの?
868 :
名無しさん@5周年 :2010/05/20(木) 22:44:58
試合結果は「勝」「負」「引き分け」の三通りしかないだろ。 試合経過はたくさんあるけど・・・
869 :
名無しさん@5周年 :2010/08/09(月) 17:21:08
保守