[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
369: 310 2015/12/28(月)10:45 ID:i0yT273K(1) AAS
デバッグモードでu64系の関数が使えない件、解消しました。
MTD(ｆ）に代えてアスピレーションウィンドウを採用しました。
中盤探索は、隣の評価値をたどっていくと、かえって遅くなるのでnegaScoutだけで
探索していましたが、これでMPC計算が多少高速化できそうです。
MPC計算はまだしていません。反復深化でどのくらいの深さの探索で、どのくらいの
件数なら実用的に計算できるか試行しています。１４手読みまでは行けそうですが、
１５手だと厳しいかなぁという状態。２０手付近では盤面によっては、探索ノードが爆発的
に増えて、時間のバラツキも大きいです。
また、FFO#40-44の完全読みを計測しました。zebra比で#40は圧勝、#41-42は引き分け
ですが、#43-44は完敗。理由は#43-44は正解となる初手が２つあるためで、#43は１０秒
以上かかってます。むむむ。
370: 2015/12/28(月)21:28 ID:kMgyHY3u(1) AAS
オセロ完全解析は何年後くらいになりそうですか？
371: 310 2015/12/29(火)02:31 ID:F/Ba7yoX(1/3) AAS
ちょっと一括変換操作を誤って大変な事になっていました。一通り直していたところ、
FFO#40で1.45秒程度が出るようになってしまいました。多分、修復がてら置換表登録・
検索関数の変数の並びを、整列したのが効いたのだと思っていますが、びっくりポンです。
前回課題の正解着手が複数あるケースですが、MTD(ｆ）のような評価値決め打ち系の
探索では、ぴったりの答えが見つかった時点で、ほかの手を探索する必要が無い事に
気づき、直してみたところ、FFO#44は速度アップしました。が、#43はまだ駄目です。
とはいえ、#43は浅い探索の評価値が外れすぎて時間がかかっているような感じなので、
浅い探索の深さを残り手数で調整すると直りそうな気がしています。
あと、FFOテストの全データをテストできるように登録しましたが、#59を見て、はたと、
途中全滅時のスコア計算が違う事に気づきました。自分のは一番単純なアメリカルール
です。ここを直すと、確実に時間が遅くなるような気がしますが、明日直してみます。
てな事をやって、一晩に０．１秒（比率にして７％前後）も短縮していると、まだなんか
やる事があるんじゃないかと・・・。
372(1): 2015/12/29(火)03:05 ID:rs+91GZQ(1) AAS
結局MTD(f)をやってるのかやってないのか意味わからんな
373: 310 2015/12/29(火)10:25 ID:F/Ba7yoX(2/3) AAS
って、βカットしない事を確認しなきゃきゃいけないから、ぴったりの答えがあっても
全手を探索しないとダメじゃん。すんません。
374: 310 2015/12/29(火)10:52 ID:F/Ba7yoX(3/3) AAS
>>372
やったりやらなかったりで、いろいろ比較して試してます。
MTD(ｆ）では、ワーストケースではウィンドウ中心が評価値の最少単位で動く関係で、
１石以下の少数計算をする中盤探索では、よけいに時間がかかる事が多いです。
そのため、アスピレーションウィンドウ導入前はただのnegaScoutにしてました。
終盤探索は、最少単位が１石になりますので、許容範囲です。
MTD(ｆ）もアスピレーションウィンドウも、所詮本チャンのnegaScoutを呼び出すための
ドライバーにすぎないので、どちらも用意して、何かの折に速度比較しています。
今回は、ボツりましたが、ぴったりの値が見つかったら後の探索を省略する際には、
MTD(ｆ）の方がマッチングが良かったので、そうしました。
ボツになりましたので、またアスピレーションウィンドウに戻りましたが。
#40ではzebraよりはるかに高速化できましたが、#43など遅いケースでは、数倍の時間が
かかります。こういうタイプの時間差は、単純な高速化じゃなくて、何らかのアルゴリズム
の違いがあるのかなと想像しています。
375: 310 2015/12/30(水)00:01 ID:lfikhn/D(1) AAS
結局、本日は探索速度アップばかりやってました。
中盤探索というか評価関数の計算でBMI2命令を徹底的に使ってみました。
また、ボードの回転操作系も見直しました。
１０％程度は高速化できたと思います。でも、期待したほどではなかった。
あと、速度アップするなら、ボードの対角線転置かなぁ。あと効果は微妙だけど、１８０度
回転がビットオーダーの逆転なので、これも何か組み込み関数があったらうれしいなと。
終盤探索では、FFO#59問題に対処。
スコア計算の修正と、全滅など６４石の差がついた時に、βカットと同様に後続の探索を
パスして時短。minMaxで言うところのα値の更新があり得なくなるからです。
浅い探索が１１手だと３秒程度で解けるのに、１５手だと６０秒かかったりと、いまいち動き
に納得がいかないので、まだ何か問題があるかも知れません。
中盤探索をあと５０％は高速化したいなぁ。というか、zebra見てるとできるはず。
376: 310 2015/12/31(木)21:04 ID:i5TR43+g(1/2) AAS
2015年の年の瀬は、MPC計算のメモリーリークの原因探しで更けていく・・・
置換表クラスあたりっぽいんだけど、デバッグの仕方が良くわからないという・・・
377: 310 2015/12/31(木)23:46 ID:i5TR43+g(2/2) AAS
ギリギリ１２時前に直った。
メモリリークではなく、不正なアクセスでした。
多分直ったと思う・・・
来年の抱負は、MPCの計算をする事と、GUIを作る事です。
元々VBのGUIからDLLで呼び出すつもりでしたが、なんとなくC++でやってみようか
という気になってきています。
378: 310 2016/01/03(日)11:08 ID:3YPfF+nL(1) AAS
バグは解消してました。なんとも不可思議な事になっていました。
スタック領域を破壊していて、破壊された箇所がたまたまdepth（残り探索深さ）だったため、
探索深さがマチマチになってました。計算時間やメモリ使用量が異常になる以外は、そこそこ
それっぽい探索結果が出ていたため、メモリリークだと思ってしまったという。
中盤探索の置換表適用範囲も、ちゃんと効くようになって深さ１１〜１２まで置換表を使用
するのが効果的と出て、探索値のバラツキもそこそこ揃って、探索時間も予想できる範囲に。
メモリ使用量も安定しました。
ある棋譜に対し、２０手目から終局まで順に、深さ１〜１７の探索を、反復深化を活用しながら
探索値を求めるプログラムを用意して、１４棋譜を対象に実行したところ凡そ７時間で完了。
速度的にはこんなものかなぁという感じ。もっとも、深さ１７だと結構、探索時間・ノード数の
バラツキが大きいので、１０件前後だと終了時刻もバラツクはず。
とりあえず、棋譜からランダムに１０件程度を抽出し、この探索結果を貯めていくところまで
作りました。トータル１００件程度集めれば、MPCパラメータ計算には十分だと思う。
探索結果を貯めてあるので、毎晩１０件くらいづつ追加し、直説法で都度パラメータ再計算
して精度を上げていく事ができる。
379: 310 2016/01/04(月)22:22 ID:1p46+Vgy(1) AAS
MPCのための探索データ蓄積の間に、並列処理について調べてみました。
VC++だとopenMPとPPLってのが使えるみたいです。
?concurrent_unordered_mapが便利そうなので、PPLにしよううかなと。
で、脳内コーディングであれこれ考えていたら、AIの中でBoardクラスを参照渡しして、
差分型で盤面を進めたり戻したりしているのが、とても並列処理と相性が悪い事に
思い至りまして・・・。コピー型に戻して、何をクラス化するのかとか見直してみようかと
言う事に。
多分数日がかりになるかなと。
380(1): 2016/01/04(月)22:36 ID:iMclxIQO(1) AAS
Boardはスレッドごとに持てばいいんでない
スレッドを生成するときだけコピーすれば
381: 2016/01/05(火)01:07 ID:UyX0E5Wd(1) AAS
自分の場合は将棋作ってて、並列にしたけどstockfishのソースとか参考になるよ
スレッド待機させてノードの終わりの方で判定して、OKなら分割させて
そこで上でも言われてるけど、盤の情報をコピーして走らせるの
自分は盤面作成とか更新巻き戻しなどを最初スレッドとか考えてなく直にアクセスしてて
全てポイントにからに変更するのが、かなりだるかった
382: 2016/01/05(火)20:35 ID:zrGyzNpa(1) AAS
へーこのスレって意外と人いるんだなぁ
将棋作ってる人がいるとは驚き
383: 310 2016/01/09(土)02:12 ID:GhyCVx1P(1) AAS
どもです。
とりあえず、コピー方式に変えてましたが、変にバグを仕込んだりして、時間がかかって
ました。ようやくデバッグもあらかた終わったのですが、まだ原因不明・解釈不能な速度
差があって、終盤探索のみ速度が１０％以上低下した状態です。
というか、コピー版を書きながら気づいた箇所を、ボードクラス版にも反映すると、ボード
クラス版が高速化して、差が広がるという。
で、クラス版がFFO#40で１．４０〜１．４２秒になりました。
>>380さん
おっしゃる通りですorz
プログラム直しながら、ネットでVC++の解説をつまみ読みしながらのコーディングに
限界を感じたので、オライリーさんの出番という事で、アマゾンに本を数冊注文しました。
到着待ちの間にやるなら、適当に作っていったクラスの整理統合かなぁ。
あと、openMPのお勉強。
384: 2016/01/09(土)02:32 ID:Uphigh+6(1) AAS
最近のvc++使ってるのなら普通にstd::threadでやるのもいいかも
385: 310 2016/01/10(日)01:14 ID:F6Uvkb4b(1) AAS
うわ。色々やり方あるのね。
VC++だとPPL、openMP、std::threadか。
PPLについては、逐次処理のまま置換表で使っているunordered_mapをconcurrent版に
変えてみたところ、置換表付探索の速度がおおよそ半分になってしまったので、結構
微妙な印象を持っています。
とりあえずopenMPでどこまでできるか試してみて、気に入らなかったらstd::threadで
細かく制御できないか考えてみます。
先ほど、コピー版で置換表登録に影響するバグ発見。直したところ、FFO#40が1.26秒
とかになってしまいました（汗）。不可思議な速度差の原因はこれで間違いないと思います。
edaxまであと１０倍の速度アップかぁ。並列化で３倍くらいまで詰められないかと期待。
一応、Boardクラスのポインタ渡し版（差分方式）も試してみましたが、今のところ、若干
速度低下しています。もともとの差分方式は、Boardクラスを継承したAIクラスのメンバ
関数として実装してます。
これらの一見無駄な作業も、バグ探し＆逐次探索の速度アップに有効だったという事でorz
386: 310 2016/01/11(月)20:31 ID:IrhGHm3u(1) AAS
とりあえずopenMPで並列化トライしてみましたが、コンパイル中に内部エラーになる。
ネットで見ると最適化オプションがらみらしいけど、なんかよくわからなかったのでパス。
PPLを使って、とりあえず並列化のテスト。オセロでは標準的と思われるｎ段YWBCに
してみました。forループみたいな特定の形ではPPLは結構簡単という印象。
バグは一通りとれた状態だと思いますが、FFO#40で１．２５秒が０．８５秒程度になり
３０％強の高速化。あと少しだけソース修正するつもり。
使ってるパソコンは２コアでした。昨夜まで４コアのつもりでいましたが（汗）、２コアなら
こんなものなのかな。
387: 2016/01/11(月)21:53 ID:oLh2eOse(1) AAS
2コアYBWCにしてはまあまあ並列化されてるような感じ
もちろんもっと効率化はできるけど
388: 310 2016/01/13(水)13:02 ID:Yd1pcfW8(1) AAS
どもです。
コア数２だと、理屈の上では２倍近くまでは速度アップできるのかなぁと思います。
一般的にはどのくらいの倍率をターゲットにしているのでしょうか。
YBWCの適用のパターンをいくつか試しましたが、タスクマネージャーで見たCPU使用率
は、ほぼ１００％になってるので、単純にはスピードアップは難しい感じがしてます。
PPL自身のオーバーヘッドなのか。
PPLは楽ちんだけど、チューニング箇所がなさすぎな感じ。
あと、YBWCやってる以上、YBの着手をmove orderingする意味が無い感じなので、
sortが一つ省けるかなぁというところ。ルートに近いので、あまり効果は無いと思うけど。
ここまで来ると、８コアのパソコン持ってきたら・・・
SIMD拡張命令だBMI命令だを使っておきながら、コア数２で頑張るのもどうかみたいな。
389: 310 2016/01/16(土)09:10 ID:mjTPCiWE(1/2) AAS
PPLはMicrosoftのDeveloper Networkくらいしか情報が無いので、ひたすらリンクを
たどって情報収集してますが、ほとんど機械翻訳で、結局カーソルあてて英文読ま
ないと意味が分からないという・・・
で、排他制御とかいい加減にしていたノード数カウントなどをきちんとして、ソースの見易さ
と効率を上げようと色々と細かく修正。combinableとかcritical_sectionとかInterlockedとか。
と・・・思ったら・・・中盤探索で確率１０％程度で違う答えが返ってくる・・・
並列探査のバグはわかりにくくて時間を食ったのですが、どうもcombinableの動作が変。
期待した動作をしていない。でも、情報が無さすぎで、どこを直せば良いのかわからず、
結局同等の機能を動的配列にしてしまった。
390: 310 2016/01/16(土)11:37 ID:mjTPCiWE(2/2) AAS
中盤探索を１万回程度回して、違った答えが返ってこない事を確認できました。
ノード数カウントはInterlockedIncrementを使っているんだけど、やはり排他待ちロスが
大きいようで、ノードカウントありだと０．８秒前後、無しだと０．７秒前後になる。
使えなかったcombinableみたいな形にして、一つの再帰関数内はローカル変数で加算
して、最後にまとめて１か所で排他加算するようにしてみようかな。
並列タスクの起動順で、探索ノード数が違ってくる関係で、実行時間のバラつきが±０．５
秒くらいになっている。
391: 310 2016/01/18(月)09:54 ID:ED4vwFCp(1) AAS
結局、ノード数・リーフ数カウントは、戻り値を構造体にして返す方向にて検討。
普段の探索には不要だけど、solverだと表示したいので。
これで完全にローカル変数になり、排他ロスを気にする必要がなくなる。
デバッグ用の置換表回りの統計は、所詮デバッグ用なので、一旦全削除。
必要になったら、こちらは#ifdefで囲って、排他加算する。
で、構造体の形であれこれ悩んでいたら、戻り値をクラスにできる事に気が付いて・・・
あらためてC++すげーと感心中。
けど、かなり全面的な修正になるので、時間食ってます。
まずは中盤探索を修正して、ノード数がおかしくない事を確認。
終盤探索の修正はこれから。探索を使う系の統計処理も変更しなきゃならないけど、
MPC以外は、次いつ使うかわからないｗ
392: 310 2016/01/19(火)00:13 ID:Dh1WPUXC(1) AAS
終盤探索の修正完了。
０．８秒±０．０５秒と、結局、Interlockedでグローバル変数のノード数を加算するのと、
大して時間が変わらないか、もしかしたら微妙に遅くなったかも。元に戻すのが面倒
なので、他で改良点を探すしかないかなと。
393: 310 2016/01/21(木)10:04 ID:c00KCFqr(1) AAS
YBWCでは、最適着手手順（PV）のラインで置換表でmoveorderする意味が無いという事
を突き詰めていくと、いちいち前回探索の置換表を引くループを回して、都度最善の着手
を求めるのではなく、前回探索で得たPVを渡せば、時間が短縮できそうな気がしてきま
した。ツリーの浅い部分なので、全体にどれくらい効くのかはわかりませんが。
また、浅い探索などで最適着手手順を取得する時、negaScout＋置換表だと正しいscoutmiss
が発生した時に、nullサーチ時の置換表が適用されて、それ以後のPVが得られないという
事で、悩むところではあります。
まずは戻り値の構造体でPVを返すように改造して、効果を見たうえで、YBWCを適用する
深さでnegaScoutをやめてnegaMaxにするか、それともnullサーチは置換表適用外とするか
どれが良いか試してみようかなと思っています。
できるだけ高い位置で並列化した方が良いという指摘と、置換表もなるべく高い位置で
効かせた方が良いという指摘の、どちらを優先するのかですね。置換表はばっさり探索
をカットできるけど、並列化はカットせずに時短するので、置換表優先かなという気もして
いますが、高い位置でどれくらい置換表が効いているのかもわからないですし・・・。
394: 310 2016/01/23(土)01:31 ID:0OQfWIYl(1) AAS
パソコン再起動すると、何かのタスクがCPUを３０％くらい占有してしまいます。
昨日まで快調に動いていたのが突然遅くなって、悩んでいましたが、これが原因のようです。
というわけで、本日は色々改変したソースの速度が計測できずに悶々としてました。
色々すったもんだ挙句、PVラインを渡す形にしましたが、効果があったかどうかは微妙。
色々付け足した事で生じた速度低下はペイしたかなぁという感じで、#40で0.78秒前後。
本格的にネタが尽きて来たので、ここから先は、MPCをきちんと実装してiterative widening
にかけるしかないかなぁという感じです。あと、定数で渡している置換表適用高さなどの
パラメータを、空マスや使用条件で作ると、実用的になるかな。
395: 310 2016/01/27(水)01:18 ID:IVwAw5rN(1) AAS
オライリーの並列化本が来たので拾い読みしながら並列プログラミングの勉強。
PPLの各アルゴリズムが何を目的とするものなのかが、少しずつ分かってきました。
抽象化度が高いので、最初のとっかかりとしては良いかも。何故かcombinableが
上手く動かないとか、parallel_reduceの中身がよく分からないとかありますが。
で、並列化できるところを探して速度が上がるか試したり、同じ処理をより綺麗に書き
換えしたりして、微妙に速度アップし、0.70〜0.75秒くらい、ノード数が15M、NPSが21M
nps程度になりました。たまに0.68秒台が出ます。
Edax4.3のFFOベンチの結果を確認したところ、ノード数で１．５倍、NPSで４倍、計６倍の
差があります。NPSをコア・クロック換算しても１．５〜２倍の差があり、ノード数は別として、
まだ速度アップの余地があるのではないかという事で、単品速度アップに走ってます。
ノード数はMPC導入後のiterative wideningである程度追い付けるかなと淡い期待。
いくつか速度アップネタがありますが、サッカー日本代表見ながらでははかどらず。
続きは明日。
396: 310 2016/01/29(金)11:31 ID:trvaxUQ+(1) AAS
先日の速度アップネタはすべて不発でしたが、その際にノード数のカウント漏れを見つけ
て、修正したところ、ノード数は１７〜８Mという感じでした。その際に、最終２手高速化の
箇所でもカウント漏れがあり、まずは正確なノード数を簡便に把握しようと外してみたところ、
意に反して速度低下しないところか、どうも微妙に高速化したように見えまして（汗。
最終３手高速化を試してみたり、最終１手高速化も外してみたり、moveorder適用とか、
そもそもmobilityを求めずに空マスを順に着手してみるとか、その辺の適用深さを変えて
みたりいろいろとやって現時点の最適パラメータにしてみたところ、0.63〜0.68秒、最速で
0.60秒が出るようになりました。
αβカットの効きが悪くなっているため、ノード数は２４〜２５Mとなりました。
その分NPSは３７〜３８Mと速くなっていますが、こんな方向で高速化してて良いのか？
というわけで、ノード数が違う段階でNPSを比較しても意味が無いという事に気が付きました。
397: 310 2016/01/30(土)20:51 ID:yCKBToEa(1) AAS
囲碁がすごい事になってますね。オセロで一通り勉強したら小さい盤の囲碁をやって
みようと思っていたので、モチベーション低下中。とはいえ、ああいうのをオセロに応用
しようとしたら、あそこまでマシンパワーいらないんじゃないかとか・・・。
ここのところ、もっぱらSTLやPPLの機能を綺麗に使う方向での改良ばかりしてました。
pararell_reduceの使い方もわかりました。negaScoutの繰り返しループが綺麗に並列化
できたんじゃないかと。ただ、MAPする件数がしれているので、parallel_reduceではなく
逐次版のaccumlateの方が速いという結果に。あと、時間計測が結構飛び飛びの値に
なるので時間計測関数を精度１msのものに変更。
色々やった結果、若干高速化したうえで、時間のバラつきが消えてくれました。
１００回試行で計測すると610ms±15ms（１σ）となり、逐次処理のほぼ２倍の速度に。
ノード数は同程度で、NPSは40M超えて来ました。このNPSのままノードを半減できれば
良いのに。
398: 310 2016/02/07(日)21:48 ID:xNqeS9Ve(1) AAS
ここら辺で、EDAXとかとの速度差の原因を考えたところ、次の２点が考えられました。
１．評価関数の精度が悪い可能性
２．個々の関数で速度アップの余地がある可能性
という事で、１は熟考が必要なので後回しで、速度アップの対象として、flipとmobilityの
高速化を検討。とはいえ、良い知恵があるわけでもないので、ネット徘徊。
現在、ポインタ関数で分岐して処理しているflip関数を１発で処理するopenCLのソースを
発見。Master Othelloの作者のものでEDAX4.3のflip関数を参考にしているらしい。
中身を解読するとベクターを使っている。とりあえず処理を真似て逐次処理で組んでみたら
結構速度アップしました。
解読の過程で、ようやくベクタ化の意味がわかったので、mm256系の命令を使って、
ベクタ化してみましたが、若干速度低下。原因は恐らくlzcntで一回ベクタを抜けてしまう
所だと思うので、ハッカーのたしなみを読んでベクタ演算で組み直してみる予定。
合わせてmobility関数もベクタ化。若干速度アップしたかなという程度。
組み込み関数は使い方が面倒臭いので、演算子のオーバーロードしまくってみました。
flip関数は非ベクタの分岐無しバージョン、mobilityはベクタという状態で、500msを切る
数字が出るところまで来ました。flipのベクタ化ができて、パラメータ調整するともうちょい
良い数字が出るかなと期待。
上下前次1-新書関写板覧索設栞歴
あと 604 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.021s