[過去ﾛｸﾞ]
【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
【オセロ,将棋】ボードゲーム【囲碁,War】 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
341: 名前は開発中のものです。 [sage] 2015/10/26(月) 09:44:35.41 ID:uWG/Yjb0 中盤探索に入るにあたって、評価関数の計算の試作をいろいろしているんだけど、 いまいちぱっとしない。１００回学習で１晩かかるし、３００回試行くらいしないと傾向が 見えてこないので、時間がかかる。 で、仕方ないので、裏で序盤定石を作り始めてしまった。 こちらも棋譜ベースで作ろうと考えている。 そこまで来た時に、データベースのどういうデータが使いたいのかが、逆にはっきりして 来て、今使ってる３６０万件棋譜の中のデータを選別しようかという方向に傾きつつあります。 が、やっつけで作って中身が思い出せないフォーマット変換のプログラムから直さなきゃならん。 開き直って、もう１度、データ変換から作り直そうかなと・・・ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/341
342: 310 [sage] 2015/10/30(金) 17:31:41.23 ID:uxyAnbEX 棋譜ベースで序盤２０手の定石DB作った。 定石DBは置換表をベースに作ったので、検索は速いけど、容量が大きい・・・。 簡単にαβで２０手探索してみた。 ネットで調べた定石集に載っていない手筋が出てきてしまった。むむむ。 ５手目までエビ系で、しかも石差＋２で黒勝ち。棋譜が偏っているのかな。 棋譜は例の５０万棋譜計画の奴で１０手目、２０手目以降を訂正したというデータ。 明らかに壊れたデータが入っていたりと、何かと使いにくい箇所があるデータだけど、 定石DB作るにはこの量でも足りないのかも。 定石探索用の簡易版minMaxを作りながらつらつら考えていたら、終盤探索の moveorderをもっと良くする方法を思いついた。評価関数の精度次第だけど。 新評価関数は、途中でうっかり仕込んだバグで遅延。ようやく原因が見つかって、３００回 試行まで来た。もうちょい収束させたいけど、テストに使える程度にはなってると思う。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/342
343: 310 [sage] 2015/11/08(日) 00:32:40.41 ID:LMw8+3qF moveorderを早くする方法というのは、事前に軽く探索した手順を保存し、その手順から 優先して探索するというもの。理論的にはscout missがゼロになる。 探索した手順を取り出す仕組みが必要になるので、その辺を改造しようと思ったところで、 悪い癖が出てしまいました。Cベースのソースを一旦棚上げして、C++ベースのクラスを 利用した形で一から作り直してしまいました。 moveorderの配列をvectorに変えたり、unordered_mapを見つけたので置換表に使って みたり。置換表は、システム任せにして動的にメモリ確保に行かすと、探索ノードの減少 以上に速度低下して使えない。最初からある程度メモリ確保させようとしているんだけど、 いまいち設定がわからない。動的にメモリ確保するので、速度のバラツキも大きい。 そもそもC++は初めてなので、目的がオセロからC++というかunordered_mapの習得に なりかかっていたので、一旦棚上げして、配列ベースの自作ハッシュの置換表に戻る 方向にしました。 とはいえ置換表を外してもnode/secが5kくらいしか出ていないので、実装が悪いところもありそう。 というわけで完全に寄り道しちゃってます。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/343
344: 310 [sage] 2015/11/12(木) 16:56:19.10 ID:4hPfHY6k ようやく、C++ベースの終盤探索（negaScout）が、Cベースより若干速くなりました。 ・unordered_mapの速度のバラツキはデバッガー上限定。 実行ファイルでも多少ばらつくけど、メモリ効率＆メンテナンス性からunordered_mapを採用。 ・探索した確定手順を返す方法の検討で苦戦。 negaScout＋置換表では原理的に無理と認識するのに時間を要しただけでしたorz 置換表無しnegaScoutかnegaMax＋置換表では、後者の方が高速。 ・確定手順を元にmoveorderする改造の効果は限定的。 moveorderで先頭にする処理が重い模様。適用範囲を狭めて行くと１〜３手で同等の速度。 ・ハッシュキー生成簡素化で若干速度アップ。 ・その他、細かいスピードアップ。 確定手順の導入で５０％以上速度アップを目論んでいたのですが、無駄な努力でありました。 一応、与える確定手順の数はマクロ定義で可変できるようにしてあります。 評価関数も修正を加えたいので、データ変換部からまた作り直しです。 目標も無しに同じ事２回やるのは面倒だなぁ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/344
345: 310 [sage] 2015/11/19(木) 14:23:44.03 ID:W/V+CKXD 定石部分もクラス化が終わりました。クラスなんての扱うの初めてなので、もうちょっと 綺麗にできたかなと思う面もありますが、C++習得が目的ではないので。 終盤確定読みは０．０５秒刻みで速度アップ。FFO#40で２．３秒になりました。 今まで、速いプログラムでは３０手目くらいから勝敗判定を始めると言う記述を読んで、 なんて速いんだと思いつつ、何に使うんだろうと思っていましたが、ようやく腑に落ちました。 オセロというゲームは勝敗だけが問題で、勝つんなら２石差で十分。「少なくとも負けない 手」というなら、(-1,0)のNull windowで探索してβカットされた手を選べば良い。評価値は 不定（これより良いという値）でも負けない手であるという点では「確定」手順です。moveorder が正確なら、極端に石差を減らす手も選ばない。これなら現状でも２５手ちょいくらいは行けそう。 ただ、これは勝勢の時の話で、敗勢の時の評価値は「これより悪い」という数字だし、 逆転は相手のミスに期待するしかなく、相手も同等のロジックのAI相手だと必敗となる。 結局定石段階で勝負がつく事になります。 今、定石DBは３０手を前提に組んでいますが、３１手目から勝敗判定ができるんなら、定石 を外れない限り中盤探索が不要になり、定石から外れた時にのみ中盤探索が必要になる。 つまり中盤探索は対PC戦では重要度が低く、定石が切れたら、即、終盤探索が始まる。 そもそも評価関数が良ければ、中盤もあまり深く探索する必要がないわけで。 深く読む意味って、なるべく評価が正確なステージを使いたいからなんだなぁと。 というわけで、次はそろそろ中盤探索です。Multi Prob Cutの英語論文を読まねばならぬ・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/345
346: 310 [sage] 2015/11/21(土) 00:05:47.02 ID:WWzrsUCT 定石DBを使って３０手目まで着手した盤面の予想石差が２で勝ち判定だったので、 試しに３１手目から勝敗判定をしてみました。 (-1,0)のNull windowで７分３０秒ほどで解けました。 （参考）勝ちと引き分けを区別するために(-1,1)で計算すると９分３０秒ほど。 探索ノード数がintではオーバーフローしてしまった・・・。 これから、３３〜４手目（残り２６〜７手）くらいで、１０秒程度で解けると予想されます。 勝勢ならこれで良いのですが、敗勢の時は、初段がβカットされないので１０倍程度 時間がかかる。そうすると、残り２５〜６手目くらいが勝敗読みの限度かなと。 もっと高速化が必要なのか。それとも、何か発想の転換ができるのか。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/346
347: 310 [sage] 2015/11/23(月) 21:01:42.47 ID:24rahmZ0 ProbCutとMultiProbCutのBUROさんの論文あらかた読み終えました。 最初、MPCの方から読んでちんぷんかんぷんだったので、ProbCutを読んで、 戻って来て、ようやく実装のイメージが湧くところまで来ました。 というか、この発想に至る道具立てや考え方は、既に揃ってた感じ。例えば>>323とか。 これ>>345-346の勝敗判定の高速化に使える気がする。相手側の手番では 前向きカットしないようにすれば、相手の反駁手を見逃さないからいけるんかなと。 あまり深い読みで使用するとパラメータ作りでしばらくPCを占有しそうだけど。 カットペアは結構アドホックに決めているのかな。各組合せを総当たりで調べても、 σにそんな差があるとは思えないし、特異的に良い組み合わせがあるとも思えないし、 むしろ読む深さの差が増えるにつれてダラダラとσが大きくなって行くだけじゃないか と思う。毎深さごとにMPCしてもオーバーヘッド負けになるだろうし、再帰的に使う事を 考えたら、２＾ｎ＋αで４，８，１２，１６，２０，２４ってな感じで良いのかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/347
348: 310 [sage] 2015/11/25(水) 22:32:57.73 ID:APRE5Y1F 条件を決めて簡単にMPCパラメータの計算プログラムを作って検証してみました。 ３０手目の時点（深さ３０）の時の浅い探索０〜１０手でMPCパラメータを計算してみました。 例の３００万件棋譜の３０手目以後完全読み（らしい）１９０万件ほどのデータからランダム に２００件ほど抽出して使用。 結論）δが１０石、R-2が０．７未満という状態で、とても使えたものではないという事に。 ただ、３５、４０、４５手目時点からのカットを試す価値はあるかも知れない。 一方、３０手目の時点で、深さ１０の探索に対して、浅い探索６までで計算すると、 浅い探索４手でδが２石、R-2が０．９３１、浅い探索６手でσが１．５石、R-2が０．９６２ 程度と、まずまずの結果に。これが、論文通りの使い方。 当たり前だけど、こちらは十分使えそう。ただ、結局深い探索に対して浅い探索の深さを 決めるのに、全パターン試すしか無いという。まあ、BUROさんのマネしちゃえば良いけど。 あと、中盤読みのプログラム、やっつけで、終盤探索の手順作成用の浅い読みプログラム 転用したんだけど、これnegaMaxなのよね。negaScout＋MTD(f)にするなり、もう少し、 素の高速化をしないとパラメータ計算が大変。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/348
349: 名前は開発中のものです。 [sage] 2015/11/29(日) 22:05:16.61 ID:gx8DmdDE googleとかfbが囲碁のAI作ってるが、どんなもんなの http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/349
350: 310 [sage] 2015/12/02(水) 23:21:25.70 ID:Xp/MZwxE とりあえずMPCの仕組と終盤探索用のパラメータだけ作り、終盤探索と勝敗判定に 適用してみました。 勝敗判定は３１手目から。浅い探索は残り手数の1/3。T=1.5で時間短縮が微妙な感じ。 終盤探索はFFO#40でテストしたところ、T=1.5だと途中で正解着手がカットされている 模様で、T=2.0で正解。T=2.0だと時間変わらずみたいな微妙な結果に。 もう一度、MPCの論文を良く読んでみましたが、どちらかというと評価関数の精度の差 の方が大きい様子で、もともと標準偏差が倍近いので、そこを何とかしなきゃならんと。 論文を良く読むと・・・評価関数に確定石はおろか、mobilityも使っていない。使っている のは、パリティー（手番）だけで、ここは自分の方が精度が良い方法のはず。という事で、 急きょ評価関数の説明変数をパターンだけにして再計算に着手しました。 とはいえ、書いてある学習係数があまりに違いすぎるので、自分がバグってる可能性も。 また、ネットでBUROさんのパワポ資料（２００２年）みたいなのを見つけて読んでみると、 「selective endgame search」と称して、MPCの終盤探索への応用がサラっと書かれて いて、「いまどきの強いオセロプログラムはみんなやってる」との事。iterative deepingを 前提にしているのでmoveorder作成で使ってるのかなぁ。正解着手だけ与えても速度アップ は限界があり、正解以外着手のnull window searchの時間がバカにならないので。 あと、中盤探索は（１７，５）というカットペアの記載あり。zebraのFFOのログでは中盤探索が 2.5ｋNPSなのに対して、僕のは250MPSと、速度が1/10なので・・・深さ１７はしんどいかなと。 ちょっと期待しているのは、前述のとおり確定石計算を評価関数で使用しなくなったので その分は速度アップしていないかなぁと。 評価関数の再計算を始めてしまったので、しばらくは中盤探索が動かせません。 というか、本当にLRの計算があっているのか、バグは無いのか、不安になる… http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/350
351: 名前は開発中のものです。 [sage] 2015/12/02(水) 23:37:59.26 ID:Xp/MZwxE >>349 囲碁オセロ板の該当スレで聞いた方が良いかなと。 コンピューター囲碁ソフトについて語るスレ30 [転載禁止]©2ch.net http://kanae.2ch.net/test/read.cgi/gamestones/1447640768/ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/351
352: 310 [sage] 2015/12/04(金) 23:35:12.62 ID:DNSRUk3b 結局、確定石が評価関数の誤差の大きさと、収束性の悪さの原因だったみたいです。 前半から中盤はmobilityのウェイトが大きそうなので、とりあえず復活させてみました。 あと、スムージングは、あるステージで出現しなかったパターンが隣接ステージにある 可能性も考慮し、ウェイトがゼロのパターンを減らす目的もあるようです。 実際、２００試行ちょっとでかなり誤差が減ったのですが、FFO#40で試すと途中の評価値 のバラツキというか、極端に０に近い局面が現れて、２σ以上の差異が簡単に出てしまい ます。そこで、ちょっとだけスムージングを入れて、かつデバッグ段階ではウェイトゼロの 出現をアラームできるように改造しようかと思っています。 評価関数の重要性を痛感しています。しばらくは、ここで悩む事になるのかなぁ。 最低でも３００試行するとなると３日かかる。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/352
353: 310 [sage] 2015/12/05(土) 23:27:03.86 ID:VLRyPTJJ モビリティーも収束悪化の原因でした。 確定石の数にしても、モビリティにしても、ある程度大きな数字が出るものがダメっぽいです。 評価パターンとウェイトを確認できるようにして、FFO#40〜41の完全読みに登場する盤面を チェックしましたが、ウェイトゼロのパターンは出現していないようです。 評価値が大きくぶれるところがありますので、スムージングを入れてみて計算開始です。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/353
354: 310 [sage] 2015/12/07(月) 10:00:41.29 ID:JSVZKjkd スムージングも外してみたら、Buroさんの論文なみ（か、それ以下）のσが出そうな 感じになってきました。収束が良いのでβも大きくできたし、その後の計算でも工夫を 入れたので、Buroさん論文みたいに３００回試行で十分なレベルになりそうです。 ウェイトゼロのパターンはありました。FFO#40の５０手目のCORN２ｘ５に１つ現れます。 現在selective endgame searchがどんなものなのか、想像を膨らませています。 iterative widening endcutのイメージがなんとなくつかめてきました。 ソースを探して見ちゃえば早いんだろうけど、面倒だし、想像だけで頑張る。 MPCが動いたら、solver改造して、本当に速くなるのか確認する。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/354
355: 310 [sage] 2015/12/10(木) 23:16:49.62 ID:lQAJMVKx 結局、評価関数は１０００回試行までやってます。 β・1/Nでやってるけど、それだと収束が遅いので、１００回試行ごとにβを倍々に。 １０００試行目で発散するステージが出たので、βを下げて最後の１００試行を実行中。 その間、反復深化などで使えるように、置換表を改造。前回評価範囲をmoveorderで 再利用します。いちいち消しているとメモリ解放で時間がかかるし、全データを入れたまま 用途をキーで区別すると、使用時に選択する事になりオーバーヘッドが気になるので、 一番新しい評価値をひたすら上書きし、置換表として使用する時のみ、今回探索か 区別するようにしました。moveorderで若干割り切った作りです。 同時に中盤探索（MPCなし、反復深化）をちゃんと作ってみました。MPC計算で、結構深い 深さまで探索する予定なので、反復深化が上手く機能するようなMPC計算ロジックを考え ようと思っています。 それができたらiterative wideningのテストをしてみようと思います。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/355
356: 310 [sage] 2015/12/11(金) 22:32:36.55 ID:c1YdnEjo あちゃ。ウィンドウ幅１でiterative wideningやると、正解着手もβカットされた手も 置換表の値が全部同じになって、次の探索でmoveorderが意味なしになって、 速度が大幅低下する事が発覚。 仕組み考えないと・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/356
357: 310 [sage] 2015/12/13(日) 23:14:55.34 ID:RUGsIY6w 一応回避したけど、MPCの速度向上は限定的。 中盤探索というか評価関数が驚くほど遅いのだろうという結論に。 放置していた中盤探索の素の高速化に入ります。 １か所ネタはあるんだけど。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/357
358: 名前は開発中のものです。 [sage] 2015/12/18(金) 00:28:56.19 ID:ht2BaviT 中盤探索で２か所改良して、速度は２倍にアップ。まだzebraの６掛け程度の速度です。 終盤探索のiterative wideningを想像しながらテストするも、いまいち速度向上が望めない。 MPCのカット基準を緩めながら（widening）、置換表にmoveorderを貯めていく事でβカット をどんどん起こさせて、最後の完全読み時点ではほぼ完ぺきな順序に並び変える事で 高速化を実現する方法だと想像しているんだけど、違うのかなぁ。 そんなこんなでやけくそ気味に、浅い探索（１１手読み）＋negaScout(-∞,+∞)を試したら FFO#40で1.93秒という最速タイムが出てしまった。MPCもMTD(ｆ）も意味なしorz #41,#42もこの方法でかなり高速化したけど、それでもまだzebraの方が速い。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/358
359: 310 [sage] 2015/12/20(日) 17:21:06.88 ID:UpZkem/K 中盤探索で改良をしたらかえって遅くなるを繰り返してます。 で、やけくそ気味にmoveorderの「置換表がない時」の計算値を、簡素化してみたら 中盤探索の速度そのままに、終盤探索部分の探索ノードが減少して高速化。 終盤探索部分も同様に簡素化したら、FFO#40で1.75秒以下になりました。 それでも相変わらず#41/42はzebraがずーっと早い。 で、MPC使うと遅くなる理由を考えていたら、いま使っているMPCのセットは終盤探索用に、 残り手数と浅い読みのセットを独自パターンにして計算した奴だと言う事を思い出した。 深い探索のスコア＝終局のスコアとなり、深い探索が不要になるので。 中盤の高速化するネタももう出てきそうにないし、先に進むか・・・ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/359
360: 名前は開発中のものです。 [sage] 2015/12/23(水) 11:41:36.91 ID:Acs4Om0o iterative wideningって詰め碁用のアルゴリズムっぽいけど違うの？ 310の言ってるのってただのAspiration Searchか何かに見えるけど てか置換表にmoveorderを溜めるとはどういう意味だ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/360
361: 310 [sage] 2015/12/23(水) 16:26:13.00 ID:MLtsaD3t どもです。 Ｂｕｒｏさんのパワポっぽい資料に名前しか書いてないので中身がわかりません。 わかっているのはＭＰＣと併用するらしいことくらいです。 iterative wideningで検索すると確かに碁の関連の英語論文がヒットしますね。 関係なさそうだと思って放置していましたが、ちょっと見てみようかなぁ。 置換表云々は、僕の想像です。 αβを前提にしたアルゴリズムで高速化するネタの一つに、moveorderを工夫して βカットが起きやすくするってのがあると思います。 反復試行する際、置換表には前回の評価の範囲が入っています。 それを今回探索のmoveorderの並べ替えに利用しようというものです。 反復深化なんかと同じ考え方です。 逆に言うと、反復を前提としたアルゴリズムで高速化するネタが、それくらいしか 思い浮かばないのです。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/361
362: 名前は開発中のものです。 [sage] 2015/12/23(水) 20:37:25.92 ID:Acs4Om0o ああ、オーダリングに以前の探索の結果を置換表から引いて使うってことか 置換表に順列か何かを放り込んでいくのかな？とか思ってしまった bitboard + NegaScout + 置換表 + MPC + 評価関数とマージンの学習 をやってるっぽいのはわかったけど、とりあえず定番どころは全部入れてるのかな NegaScoutで最初のノードを探索するときに、 探索窓を(-inf, inf)で探索せずに、前回の評価値eを使って (e - d, e + d)で探索して、失敗したときに限り窓を広げて再探索するのがAspiration Searchだけど もうやってるかな あとCPUのSIMD命令使ったり、並列化したりとかはめちゃ効果でかいよ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/362
363: 310 [sage] 2015/12/23(水) 22:38:37.71 ID:MLtsaD3t >>362 ご助言ありがとうございます。 MPCはまだ途中ですが、そんな感じです。 終盤ｎ手高速化の類もしています。中盤探索だと葉に近いところで置換表外すと、 著しく速度が低下するので、最後まで置換表を使っています。 で、中盤の速度がいまいちで１２手読みくらいが実用範囲って感じです。 MPCでｄ計算に１００棋譜くらい試して一晩で計算できる範囲は１３〜１４手くらいが 限界な感じです。そろそろMPC計算しちゃおうかと思いつつ、まだ悶々と中盤探索で どこか高速化できないかトライ中です。 SIMD命令はコンパイルオプションでそれらしい場所があったので、設定してみましたが、 速度変わらずで放置しています。どうやって使うものなのでしょうか？ そもそも、組込関数のpopcountとかbitscanで64ビット版が使えずに放置してる状況です。 並列化はMPCが終わって、一通りオセロの形にしてから、次ステップで勉強しようかと 思っています。 アスピレーションサーチは、１σは±７〜８手なので試しに±８の幅にしてテストしてみた ところ、確かに若干高速化できている様子です。mtd(f)は下から寄っていく時はβカットが 効くのですが上から寄っていく時は遅いので、一発目で探索できる確率を上げつつ、 ある程度幅を絞るには、このくらいがちょうど良い感じですね。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/363
364: 310 [sage] 2015/12/24(木) 20:33:24.09 ID:zDiJT168 ちと調べてみました。SIMD命令はx64でコンパイルしている時は、設定しなくても自動的に 使うようになっているみたいな説明を見つけました。 並列化とかベクター化とかもコンパイラが自動でやってくれるみたいですが、レポート出し たら確かに一つも対象になっていませんでした。評価値算出とmobilityの２関数は、なんか 効きそうな気がしますので、少し悶々とトライしてみます。 また、_mm_popcnt_u64と_BitscanFoward64は、今やってみたら、何故か使えました。 色々とコンパイラのオプションをいじったのが原因かなぁ。謎。 多少速度アップした模様です。 アスピレーションウィンドウはｄの計算しなきゃと思っていましたが、よくよく考えたら、 評価関数の計算時の誤差ログが残っていますので、そいつでパラメータ作成してみます。 と、久々にFFO#43まで時間計測したところ、#43で答えが違ってる。 数か月前に最終２手高速化をいじった時にバグを仕込んだ模様です。 調べようとdebugモードにしたら64ビット組込関数が使えない。 やっぱりコンパイルオプションのどこかみたいですが、わからない。 だんだん問題が発散してきて、頭の切り替えが追い付かなくなってますorz http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/364
365: 名前は開発中のものです。 [sage] 2015/12/24(木) 20:53:24.01 ID:DG4HDn4P pop_cntはめちゃめちゃ速度上がった経験あるが（三割アップ） オセロだとそうでもないのかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/365
366: 310 [sage] 2015/12/24(木) 22:56:29.36 ID:zDiJT168 _mm_popcnt_u32()はすでに使っていました。u64が使えなかっただけです。 u32→u64で３〜５％くらいの高速化になっています。 困った事に、debugビルドの側では、まだ64bit版が使えていません。 debugを使いたい時は32bitに直さないといけない。 コンパイルオプションをいろいろ見比べていますが、どこなのかいまだにわかりません。 #43は最終２手なのか１手なのか、どちらにバグがあるのか切り分けようとして ソースいじっているうちに直ってしまいました（汗）。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/366
367: 名前は開発中のものです。 [sage] 2015/12/25(金) 15:25:23.28 ID:skIhqDAd >>364 コンパイラの自動ループ展開（あんま賢くない）に限らず、 手動でAVXだのSSE命令だの使えるところは使ったらという話 あとMPCは本質的に前向き枝刈りなので、過激に刈りすぎると答えがずれる可能性はあると思うけど （バグの原因は当たりがついているようなので関係ない気がするが http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/367
368: 310 [sage] 2015/12/26(土) 11:23:54.66 ID:2a5cp76f どもです。バグったところはMPC使って無い箇所でした。 コンパイラの自動ループ展開は上記２か所で試してますが、なかなかうまく行きません。 なんとか依存関係を解消してループ展開強制すると劇的に速度低下する状態です。 その代り、いろいろググっていたら、BMI命令を見つけて、BLSIとPEXTを使ってみました。 速度バランスが変わったのでパラメータで置換表適用範囲を狭めるなどもしましたが、 FFO#40で1.55秒前後まで高速化できました。中盤探索も高速化はしているはずですが、 数％程度の改善というところでしょうか。まだ５０％は高速化したい状態です。 色々アドバイスいただいたお蔭で、ようやくSIMDまわりの使い方がわかってきました。 ここまで来ると、BITBOARD操作の関数の見直しをしたくなりますね。 中盤探索の一番重い部分なので。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/368
369: 310 [sage] 2015/12/28(月) 10:45:49.88 ID:i0yT273K デバッグモードでu64系の関数が使えない件、解消しました。 MTD(ｆ）に代えてアスピレーションウィンドウを採用しました。 中盤探索は、隣の評価値をたどっていくと、かえって遅くなるのでnegaScoutだけで 探索していましたが、これでMPC計算が多少高速化できそうです。 MPC計算はまだしていません。反復深化でどのくらいの深さの探索で、どのくらいの 件数なら実用的に計算できるか試行しています。１４手読みまでは行けそうですが、 １５手だと厳しいかなぁという状態。２０手付近では盤面によっては、探索ノードが爆発的 に増えて、時間のバラツキも大きいです。 また、FFO#40-44の完全読みを計測しました。zebra比で#40は圧勝、#41-42は引き分け ですが、#43-44は完敗。理由は#43-44は正解となる初手が２つあるためで、#43は１０秒 以上かかってます。むむむ。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/369
370: 名前は開発中のものです。 [sage] 2015/12/28(月) 21:28:38.25 ID:kMgyHY3u オセロ完全解析は何年後くらいになりそうですか？ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/370
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 632 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.014s