[過去ﾛｸﾞ]
【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
【オセロ,将棋】ボードゲーム【囲碁,War】 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
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
386: 310 [sage] 2016/01/11(月) 20:31:40.39 ID:IrhGHm3u とりあえずopenMPで並列化トライしてみましたが、コンパイル中に内部エラーになる。 ネットで見ると最適化オプションがらみらしいけど、なんかよくわからなかったのでパス。 PPLを使って、とりあえず並列化のテスト。オセロでは標準的と思われるｎ段YWBCに してみました。forループみたいな特定の形ではPPLは結構簡単という印象。 バグは一通りとれた状態だと思いますが、FFO#40で１．２５秒が０．８５秒程度になり ３０％強の高速化。あと少しだけソース修正するつもり。 使ってるパソコ
ンは２コアでした。昨夜まで４コアのつもりでいましたが（汗）、２コアなら こんなものなのかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/386
387: 名前は開発中のものです。 [sage] 2016/01/11(月) 21:53:26.50 ID:oLh2eOse 2コアYBWCにしてはまあまあ並列化されてるような感じ もちろんもっと効率化はできるけど http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/387
388: 310 [sage] 2016/01/13(水) 13:02:44.01 ID:Yd1pcfW8 どもです。 コア数２だと、理屈の上では２倍近くまでは速度アップできるのかなぁと思います。 一般的にはどのくらいの倍率をターゲットにしているのでしょうか。 YBWCの適用のパターンをいくつか試しましたが、タスクマネージャーで見たCPU使用率 は、ほぼ１００％になってるので、単純にはスピードアップは難しい感じがしてます。 PPL自身のオーバーヘッドなのか。 PPLは楽ちんだけど、チューニング箇所がなさすぎな感じ。 あと、YBWCやってる以上、YBの着手をmove orderingする意味が無
い感じなので、 sortが一つ省けるかなぁというところ。ルートに近いので、あまり効果は無いと思うけど。 ここまで来ると、８コアのパソコン持ってきたら・・・ SIMD拡張命令だBMI命令だを使っておきながら、コア数２で頑張るのもどうかみたいな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/388
389: 310 [sage] 2016/01/16(土) 09:10:45.76 ID:mjTPCiWE PPLはMicrosoftのDeveloper Networkくらいしか情報が無いので、ひたすらリンクを たどって情報収集してますが、ほとんど機械翻訳で、結局カーソルあてて英文読ま ないと意味が分からないという・・・ で、排他制御とかいい加減にしていたノード数カウントなどをきちんとして、ソースの見易さ と効率を上げようと色々と細かく修正。combinableとかcritical_sectionとかInterlockedとか。 と・・・思ったら・・・中盤探索で確率１０％程度で違う答えが返ってくる・・・ 並列探査のバグはわか
りにくくて時間を食ったのですが、どうもcombinableの動作が変。 期待した動作をしていない。でも、情報が無さすぎで、どこを直せば良いのかわからず、 結局同等の機能を動的配列にしてしまった。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/389
390: 310 [sage] 2016/01/16(土) 11:37:48.70 ID:mjTPCiWE 中盤探索を１万回程度回して、違った答えが返ってこない事を確認できました。 ノード数カウントはInterlockedIncrementを使っているんだけど、やはり排他待ちロスが 大きいようで、ノードカウントありだと０．８秒前後、無しだと０．７秒前後になる。 使えなかったcombinableみたいな形にして、一つの再帰関数内はローカル変数で加算 して、最後にまとめて１か所で排他加算するようにしてみようかな。 並列タスクの起動順で、探索ノード数が違ってくる関係で、実行時間のバラつきが±０．
５ 秒くらいになっている。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/390
391: 310 [sage] 2016/01/18(月) 09:54:27.64 ID:ED4vwFCp 結局、ノード数・リーフ数カウントは、戻り値を構造体にして返す方向にて検討。 普段の探索には不要だけど、solverだと表示したいので。 これで完全にローカル変数になり、排他ロスを気にする必要がなくなる。 デバッグ用の置換表回りの統計は、所詮デバッグ用なので、一旦全削除。 必要になったら、こちらは#ifdefで囲って、排他加算する。 で、構造体の形であれこれ悩んでいたら、戻り値をクラスにできる事に気が付いて・・・ あらためてC++すげーと感心中。 けど、かなり全面的な修正
になるので、時間食ってます。 まずは中盤探索を修正して、ノード数がおかしくない事を確認。 終盤探索の修正はこれから。探索を使う系の統計処理も変更しなきゃならないけど、 MPC以外は、次いつ使うかわからないｗ http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/391
392: 310 [sage] 2016/01/19(火) 00:13:53.27 ID:Dh1WPUXC 終盤探索の修正完了。 ０．８秒±０．０５秒と、結局、Interlockedでグローバル変数のノード数を加算するのと、 大して時間が変わらないか、もしかしたら微妙に遅くなったかも。元に戻すのが面倒 なので、他で改良点を探すしかないかなと。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/392
393: 310 [sage] 2016/01/21(木) 10:04:20.88 ID:c00KCFqr YBWCでは、最適着手手順（PV）のラインで置換表でmoveorderする意味が無いという事 を突き詰めていくと、いちいち前回探索の置換表を引くループを回して、都度最善の着手 を求めるのではなく、前回探索で得たPVを渡せば、時間が短縮できそうな気がしてきま した。ツリーの浅い部分なので、全体にどれくらい効くのかはわかりませんが。 また、浅い探索などで最適着手手順を取得する時、negaScout＋置換表だと正しいscoutmiss が発生した時に、nullサーチ時の置換表が適用されて、それ以後のP
Vが得られないという 事で、悩むところではあります。 まずは戻り値の構造体でPVを返すように改造して、効果を見たうえで、YBWCを適用する 深さでnegaScoutをやめてnegaMaxにするか、それともnullサーチは置換表適用外とするか どれが良いか試してみようかなと思っています。 できるだけ高い位置で並列化した方が良いという指摘と、置換表もなるべく高い位置で 効かせた方が良いという指摘の、どちらを優先するのかですね。置換表はばっさり探索 をカットできるけど、並列化はカットせずに時短するので、置換表優先かなという気もして いますが、高
い位置でどれくらい置換表が効いているのかもわからないですし・・・。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/393
394: 310 [sage] 2016/01/23(土) 01:31:00.95 ID:0OQfWIYl パソコン再起動すると、何かのタスクがCPUを３０％くらい占有してしまいます。 昨日まで快調に動いていたのが突然遅くなって、悩んでいましたが、これが原因のようです。 というわけで、本日は色々改変したソースの速度が計測できずに悶々としてました。 色々すったもんだ挙句、PVラインを渡す形にしましたが、効果があったかどうかは微妙。 色々付け足した事で生じた速度低下はペイしたかなぁという感じで、#40で0.78秒前後。 本格的にネタが尽きて来たので、ここから先は、MPCをきちんと
実装してiterative widening にかけるしかないかなぁという感じです。あと、定数で渡している置換表適用高さなどの パラメータを、空マスや使用条件で作ると、実用的になるかな。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/394
395: 310 [sage] 2016/01/27(水) 01:18:29.98 ID:IVwAw5rN オライリーの並列化本が来たので拾い読みしながら並列プログラミングの勉強。 PPLの各アルゴリズムが何を目的とするものなのかが、少しずつ分かってきました。 抽象化度が高いので、最初のとっかかりとしては良いかも。何故かcombinableが 上手く動かないとか、parallel_reduceの中身がよく分からないとかありますが。 で、並列化できるところを探して速度が上がるか試したり、同じ処理をより綺麗に書き 換えしたりして、微妙に速度アップし、0.70〜0.75秒くらい、ノード数が15M、NPS
が21M nps程度になりました。たまに0.68秒台が出ます。 Edax4.3のFFOベンチの結果を確認したところ、ノード数で１．５倍、NPSで４倍、計６倍の 差があります。NPSをコア・クロック換算しても１．５〜２倍の差があり、ノード数は別として、 まだ速度アップの余地があるのではないかという事で、単品速度アップに走ってます。 ノード数はMPC導入後のiterative wideningである程度追い付けるかなと淡い期待。 いくつか速度アップネタがありますが、サッカー日本代表見ながらでははかどらず。 続きは明日。 http://mevius.5ch.net/test/read.cgi/
gamedev/1057763418/395
396: 310 [sage] 2016/01/29(金) 11:31:08.14 ID:trvaxUQ+ 先日の速度アップネタはすべて不発でしたが、その際にノード数のカウント漏れを見つけ て、修正したところ、ノード数は１７〜８Mという感じでした。その際に、最終２手高速化の 箇所でもカウント漏れがあり、まずは正確なノード数を簡便に把握しようと外してみたところ、 意に反して速度低下しないところか、どうも微妙に高速化したように見えまして（汗。 最終３手高速化を試してみたり、最終１手高速化も外してみたり、moveorder適用とか、 そもそもmobilityを求めずに空マスを順に
着手してみるとか、その辺の適用深さを変えて みたりいろいろとやって現時点の最適パラメータにしてみたところ、0.63〜0.68秒、最速で 0.60秒が出るようになりました。 αβカットの効きが悪くなっているため、ノード数は２４〜２５Mとなりました。 その分NPSは３７〜３８Mと速くなっていますが、こんな方向で高速化してて良いのか？ というわけで、ノード数が違う段階でNPSを比較しても意味が無いという事に気が付きました。 http://mevius.5ch.net/test/read.cgi/gamedev/1057763418/396
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 606 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.019s