[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
363: 310 2015/12/23(水)22:38 ID:MLtsaD3t(2/2) AAS
>>362
ご助言ありがとうございます。
MPCはまだ途中ですが、そんな感じです。
終盤ｎ手高速化の類もしています。中盤探索だと葉に近いところで置換表外すと、
著しく速度が低下するので、最後まで置換表を使っています。
で、中盤の速度がいまいちで１２手読みくらいが実用範囲って感じです。
MPCでｄ計算に１００棋譜くらい試して一晩で計算できる範囲は１３〜１４手くらいが
限界な感じです。そろそろMPC計算しちゃおうかと思いつつ、まだ悶々と中盤探索で
どこか高速化できないかトライ中です。
SIMD命令はコンパイルオプションでそれらしい場所があったので、設定してみましたが、
速度変わらずで放置しています。どうやって使うものなのでしょうか？
そもそも、組込関数のpopcountとかbitscanで64ビット版が使えずに放置してる状況です。
並列化はMPCが終わって、一通りオセロの形にしてから、次ステップで勉強しようかと
思っています。
アスピレーションサーチは、１σは±７〜８手なので試しに±８の幅にしてテストしてみた
ところ、確かに若干高速化できている様子です。mtd(f)は下から寄っていく時はβカットが
効くのですが上から寄っていく時は遅いので、一発目で探索できる確率を上げつつ、
ある程度幅を絞るには、このくらいがちょうど良い感じですね。
364(1): 310 2015/12/24(木)20:33 ID:zDiJT168(1/2) AAS
ちと調べてみました。SIMD命令はx64でコンパイルしている時は、設定しなくても自動的に
使うようになっているみたいな説明を見つけました。
並列化とかベクター化とかもコンパイラが自動でやってくれるみたいですが、レポート出し
たら確かに一つも対象になっていませんでした。評価値算出とmobilityの２関数は、なんか
効きそうな気がしますので、少し悶々とトライしてみます。
また、_mm_popcnt_u64と_BitscanFoward64は、今やってみたら、何故か使えました。
色々とコンパイラのオプションをいじったのが原因かなぁ。謎。
多少速度アップした模様です。
アスピレーションウィンドウはｄの計算しなきゃと思っていましたが、よくよく考えたら、
評価関数の計算時の誤差ログが残っていますので、そいつでパラメータ作成してみます。
と、久々にFFO#43まで時間計測したところ、#43で答えが違ってる。
数か月前に最終２手高速化をいじった時にバグを仕込んだ模様です。
調べようとdebugモードにしたら64ビット組込関数が使えない。
やっぱりコンパイルオプションのどこかみたいですが、わからない。
だんだん問題が発散してきて、頭の切り替えが追い付かなくなってますorz
365: 2015/12/24(木)20:53 ID:DG4HDn4P(1) AAS
pop_cntはめちゃめちゃ速度上がった経験あるが（三割アップ）
オセロだとそうでもないのかな。
366: 310 2015/12/24(木)22:56 ID:zDiJT168(2/2) AAS
_mm_popcnt_u32()はすでに使っていました。u64が使えなかっただけです。
u32→u64で３〜５％くらいの高速化になっています。
困った事に、debugビルドの側では、まだ64bit版が使えていません。
debugを使いたい時は32bitに直さないといけない。
コンパイルオプションをいろいろ見比べていますが、どこなのかいまだにわかりません。
#43は最終２手なのか１手なのか、どちらにバグがあるのか切り分けようとして
ソースいじっているうちに直ってしまいました（汗）。
367: 2015/12/25(金)15:25 ID:skIhqDAd(1) AAS
>>364
コンパイラの自動ループ展開（あんま賢くない）に限らず、
手動でAVXだのSSE命令だの使えるところは使ったらという話
あとMPCは本質的に前向き枝刈りなので、過激に刈りすぎると答えがずれる可能性はあると思うけど
（バグの原因は当たりがついているようなので関係ない気がするが
368: 310 2015/12/26(土)11:23 ID:2a5cp76f(1) AAS
どもです。バグったところはMPC使って無い箇所でした。
コンパイラの自動ループ展開は上記２か所で試してますが、なかなかうまく行きません。
なんとか依存関係を解消してループ展開強制すると劇的に速度低下する状態です。
その代り、いろいろググっていたら、BMI命令を見つけて、BLSIとPEXTを使ってみました。
速度バランスが変わったのでパラメータで置換表適用範囲を狭めるなどもしましたが、
FFO#40で1.55秒前後まで高速化できました。中盤探索も高速化はしているはずですが、
数％程度の改善というところでしょうか。まだ５０％は高速化したい状態です。
色々アドバイスいただいたお蔭で、ようやくSIMDまわりの使い方がわかってきました。
ここまで来ると、BITBOARD操作の関数の見直しをしたくなりますね。
中盤探索の一番重い部分なので。
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でグローバル変数のノード数を加算するのと、
大して時間が変わらないか、もしかしたら微妙に遅くなったかも。元に戻すのが面倒
なので、他で改良点を探すしかないかなと。
上下前次1-新書関写板覧索設栞歴
あと 610 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.014s