[過去ﾛｸﾞ]
【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
【オセロ,将棋】ボードゲーム【囲碁,War】 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
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.5c
h.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
371: 310 [sage] 2015/12/29(火) 02:31:09.04 ID:F/Ba7yoX ちょっと一括変換操作を誤って大変な事になっていました。一通り直していたところ、 FFO#40で1.45秒程度が出るようになってしまいました。多分、修復がてら置換表登録・ 検索関数の変数の並びを、整列したのが効いたのだと思っていますが、びっくりポンです。 前回課題の正解着手が複数あるケースですが、MTD(ｆ）のような評価値決め打ち系の 探索では、ぴったりの答えが見つかった時点で、ほかの手を探索する必要が無い事に 気づき、直してみたところ、FFO#44は速度アップしました。が、#4
3はまだ駄目です。 とはいえ、#43は浅い探索の評価値が外れすぎて時間がかかっているような感じなので、 浅い探索の深さを残り手数で調整すると直りそうな気がしています。 あと、FFOテストの全データをテストできるように登録しましたが、#59を見て、はたと、 途中全滅時のスコア計算が違う事に気づきました。自分のは一番単純なアメリカルール です。ここを直すと、確実に時間が遅くなるような気がしますが、明日直してみます。 てな事をやって、一晩に０．１秒（比率にして７％前後）も短縮していると、まだなんか やる事があるんじゃないかと・
・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/371
372: 名前は開発中のものです。 [sage] 2015/12/29(火) 03:05:56.17 ID:rs+91GZQ 結局MTD(f)をやってるのかやってないのか意味わからんな http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/372
373: 310 [sage] 2015/12/29(火) 10:25:40.74 ID:F/Ba7yoX って、βカットしない事を確認しなきゃきゃいけないから、ぴったりの答えがあっても 全手を探索しないとダメじゃん。すんません。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/373
374: 310 [sage] 2015/12/29(火) 10:52:28.77 ID:F/Ba7yoX >>372 やったりやらなかったりで、いろいろ比較して試してます。 MTD(ｆ）では、ワーストケースではウィンドウ中心が評価値の最少単位で動く関係で、 １石以下の少数計算をする中盤探索では、よけいに時間がかかる事が多いです。 そのため、アスピレーションウィンドウ導入前はただのnegaScoutにしてました。 終盤探索は、最少単位が１石になりますので、許容範囲です。 MTD(ｆ）もアスピレーションウィンドウも、所詮本チャンのnegaScoutを呼び出すための ドライバーにすぎないので
、どちらも用意して、何かの折に速度比較しています。 今回は、ボツりましたが、ぴったりの値が見つかったら後の探索を省略する際には、 MTD(ｆ）の方がマッチングが良かったので、そうしました。 ボツになりましたので、またアスピレーションウィンドウに戻りましたが。 #40ではzebraよりはるかに高速化できましたが、#43など遅いケースでは、数倍の時間が かかります。こういうタイプの時間差は、単純な高速化じゃなくて、何らかのアルゴリズム の違いがあるのかなと想像しています。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/37
4
375: 310 [sage] 2015/12/30(水) 00:01:33.75 ID:lfikhn/D 結局、本日は探索速度アップばかりやってました。 中盤探索というか評価関数の計算でBMI2命令を徹底的に使ってみました。 また、ボードの回転操作系も見直しました。 １０％程度は高速化できたと思います。でも、期待したほどではなかった。 あと、速度アップするなら、ボードの対角線転置かなぁ。あと効果は微妙だけど、１８０度 回転がビットオーダーの逆転なので、これも何か組み込み関数があったらうれしいなと。 終盤探索では、FFO#59問題に対処。 スコア計算の修正と、全滅など６４
石の差がついた時に、βカットと同様に後続の探索を パスして時短。minMaxで言うところのα値の更新があり得なくなるからです。 浅い探索が１１手だと３秒程度で解けるのに、１５手だと６０秒かかったりと、いまいち動き に納得がいかないので、まだ何か問題があるかも知れません。 中盤探索をあと５０％は高速化したいなぁ。というか、zebra見てるとできるはず。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/375
376: 310 [sage] 2015/12/31(木) 21:04:10.05 ID:i5TR43+g 2015年の年の瀬は、MPC計算のメモリーリークの原因探しで更けていく・・・ 置換表クラスあたりっぽいんだけど、デバッグの仕方が良くわからないという・・・ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/376
377: 310 [sage] 2015/12/31(木) 23:46:42.84 ID:i5TR43+g ギリギリ１２時前に直った。 メモリリークではなく、不正なアクセスでした。 多分直ったと思う・・・ 来年の抱負は、MPCの計算をする事と、GUIを作る事です。 元々VBのGUIからDLLで呼び出すつもりでしたが、なんとなくC++でやってみようか という気になってきています。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/377
378: 310 [sage] 2016/01/03(日) 11:08:48.54 ID:3YPfF+nL バグは解消してました。なんとも不可思議な事になっていました。 スタック領域を破壊していて、破壊された箇所がたまたまdepth（残り探索深さ）だったため、 探索深さがマチマチになってました。計算時間やメモリ使用量が異常になる以外は、そこそこ それっぽい探索結果が出ていたため、メモリリークだと思ってしまったという。 中盤探索の置換表適用範囲も、ちゃんと効くようになって深さ１１〜１２まで置換表を使用 するのが効果的と出て、探索値のバラツキもそこそこ揃って、探索
時間も予想できる範囲に。 メモリ使用量も安定しました。 ある棋譜に対し、２０手目から終局まで順に、深さ１〜１７の探索を、反復深化を活用しながら 探索値を求めるプログラムを用意して、１４棋譜を対象に実行したところ凡そ７時間で完了。 速度的にはこんなものかなぁという感じ。もっとも、深さ１７だと結構、探索時間・ノード数の バラツキが大きいので、１０件前後だと終了時刻もバラツクはず。 とりあえず、棋譜からランダムに１０件程度を抽出し、この探索結果を貯めていくところまで 作りました。トータル１００件程度集めれば、MPC
パラメータ計算には十分だと思う。 探索結果を貯めてあるので、毎晩１０件くらいづつ追加し、直説法で都度パラメータ再計算 して精度を上げていく事ができる。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/378
379: 310 [sage] 2016/01/04(月) 22:22:10.63 ID:1p46+Vgy MPCのための探索データ蓄積の間に、並列処理について調べてみました。 VC++だとopenMPとPPLってのが使えるみたいです。 ?concurrent_unordered_mapが便利そうなので、PPLにしよううかなと。 で、脳内コーディングであれこれ考えていたら、AIの中でBoardクラスを参照渡しして、 差分型で盤面を進めたり戻したりしているのが、とても並列処理と相性が悪い事に 思い至りまして・・・。コピー型に戻して、何をクラス化するのかとか見直してみようかと 言う事に。 多分数日がかりになるかなと
。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/379
380: 名前は開発中のものです。 [sage] 2016/01/04(月) 22:36:46.74 ID:iMclxIQO Boardはスレッドごとに持てばいいんでない スレッドを生成するときだけコピーすれば http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/380
381: 名前は開発中のものです。 [sage] 2016/01/05(火) 01:07:47.45 ID:UyX0E5Wd 自分の場合は将棋作ってて、並列にしたけどstockfishのソースとか参考になるよ スレッド待機させてノードの終わりの方で判定して、OKなら分割させて そこで上でも言われてるけど、盤の情報をコピーして走らせるの 自分は盤面作成とか更新巻き戻しなどを最初スレッドとか考えてなく直にアクセスしてて 全てポイントにからに変更するのが、かなりだるかった http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/381
382: 名前は開発中のものです。 [sage] 2016/01/05(火) 20:35:26.92 ID:zrGyzNpa へーこのスレって意外と人いるんだなぁ 将棋作ってる人がいるとは驚き http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/382
383: 310 [sage] 2016/01/09(土) 02:12:28.10 ID:GhyCVx1P どもです。 とりあえず、コピー方式に変えてましたが、変にバグを仕込んだりして、時間がかかって ました。ようやくデバッグもあらかた終わったのですが、まだ原因不明・解釈不能な速度 差があって、終盤探索のみ速度が１０％以上低下した状態です。 というか、コピー版を書きながら気づいた箇所を、ボードクラス版にも反映すると、ボード クラス版が高速化して、差が広がるという。 で、クラス版がFFO#40で１．４０〜１．４２秒になりました。 >>380さん おっしゃる通りですo
rz プログラム直しながら、ネットでVC++の解説をつまみ読みしながらのコーディングに 限界を感じたので、オライリーさんの出番という事で、アマゾンに本を数冊注文しました。 到着待ちの間にやるなら、適当に作っていったクラスの整理統合かなぁ。 あと、openMPのお勉強。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/383
384: 名前は開発中のものです。 [sage] 2016/01/09(土) 02:32:30.66 ID:Uphigh+6 最近のvc++使ってるのなら普通にstd::threadでやるのもいいかも http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/384
385: 310 [sage] 2016/01/10(日) 01:14:26.88 ID:F6Uvkb4b うわ。色々やり方あるのね。 VC++だとPPL、openMP、std::threadか。 PPLについては、逐次処理のまま置換表で使っているunordered_mapをconcurrent版に 変えてみたところ、置換表付探索の速度がおおよそ半分になってしまったので、結構 微妙な印象を持っています。 とりあえずopenMPでどこまでできるか試してみて、気に入らなかったらstd::threadで 細かく制御できないか考えてみます。 先ほど、コピー版で置換表登録に影響するバグ発見。直したところ、FFO#40が1.26秒 とかになってしまい
ました（汗）。不可思議な速度差の原因はこれで間違いないと思います。 edaxまであと１０倍の速度アップかぁ。並列化で３倍くらいまで詰められないかと期待。 一応、Boardクラスのポインタ渡し版（差分方式）も試してみましたが、今のところ、若干 速度低下しています。もともとの差分方式は、Boardクラスを継承したAIクラスのメンバ 関数として実装してます。 これらの一見無駄な作業も、バグ探し＆逐次探索の速度アップに有効だったという事でorz http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/385
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 617 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.024s