[過去ログ] 【オセロ,将棋】ボードゲーム【囲碁,War】 (1002レス)
1-
抽出解除 レス栞

このスレッドは過去ログ倉庫に格納されています。
次スレ検索 歴削→次スレ 栞削→次スレ 過去ログメニュー
353: 310 2015/12/05(土)23:27 ID:VLRyPTJJ(1) AAS
モビリティーも収束悪化の原因でした。
確定石の数にしても、モビリティにしても、ある程度大きな数字が出るものがダメっぽいです。

評価パターンとウェイトを確認できるようにして、FFO#40〜41の完全読みに登場する盤面を
チェックしましたが、ウェイトゼロのパターンは出現していないようです。

評価値が大きくぶれるところがありますので、スムージングを入れてみて計算開始です。
354: 310 2015/12/07(月)10:00 ID:JSVZKjkd(1) AAS
スムージングも外してみたら、Buroさんの論文なみ(か、それ以下)のσが出そうな
感じになってきました。収束が良いのでβも大きくできたし、その後の計算でも工夫を
入れたので、Buroさん論文みたいに300回試行で十分なレベルになりそうです。

ウェイトゼロのパターンはありました。FFO#40の50手目のCORN2x5に1つ現れます。

現在selective endgame searchがどんなものなのか、想像を膨らませています。
iterative widening endcutのイメージがなんとなくつかめてきました。
ソースを探して見ちゃえば早いんだろうけど、面倒だし、想像だけで頑張る。
MPCが動いたら、solver改造して、本当に速くなるのか確認する。
355: 310 2015/12/10(木)23:16 ID:lQAJMVKx(1) AAS
結局、評価関数は1000回試行までやってます。
β・1/Nでやってるけど、それだと収束が遅いので、100回試行ごとにβを倍々に。
1000試行目で発散するステージが出たので、βを下げて最後の100試行を実行中。

その間、反復深化などで使えるように、置換表を改造。前回評価範囲をmoveorderで
再利用します。いちいち消しているとメモリ解放で時間がかかるし、全データを入れたまま
用途をキーで区別すると、使用時に選択する事になりオーバーヘッドが気になるので、
一番新しい評価値をひたすら上書きし、置換表として使用する時のみ、今回探索か
区別するようにしました。moveorderで若干割り切った作りです。

同時に中盤探索(MPCなし、反復深化)をちゃんと作ってみました。MPC計算で、結構深い
深さまで探索する予定なので、反復深化が上手く機能するようなMPC計算ロジックを考え
ようと思っています。

それができたらiterative wideningのテストをしてみようと思います。
356: 310 2015/12/11(金)22:32 ID:c1YdnEjo(1) AAS
あちゃ。ウィンドウ幅1でiterative wideningやると、正解着手もβカットされた手も
置換表の値が全部同じになって、次の探索でmoveorderが意味なしになって、
速度が大幅低下する事が発覚。

仕組み考えないと・・・。
357: 310 2015/12/13(日)23:14 ID:RUGsIY6w(1) AAS
一応回避したけど、MPCの速度向上は限定的。
中盤探索というか評価関数が驚くほど遅いのだろうという結論に。

放置していた中盤探索の素の高速化に入ります。
1か所ネタはあるんだけど。
359: 310 2015/12/20(日)17:21 ID:UpZkem/K(1) AAS
中盤探索で改良をしたらかえって遅くなるを繰り返してます。

で、やけくそ気味にmoveorderの「置換表がない時」の計算値を、簡素化してみたら
中盤探索の速度そのままに、終盤探索部分の探索ノードが減少して高速化。
終盤探索部分も同様に簡素化したら、FFO#40で1.75秒以下になりました。

それでも相変わらず#41/42はzebraがずーっと早い。

で、MPC使うと遅くなる理由を考えていたら、いま使っているMPCのセットは終盤探索用に、
残り手数と浅い読みのセットを独自パターンにして計算した奴だと言う事を思い出した。
深い探索のスコア=終局のスコアとなり、深い探索が不要になるので。

中盤の高速化するネタももう出てきそうにないし、先に進むか・・・
361: 310 2015/12/23(水)16:26 ID:MLtsaD3t(1/2) AAS
どもです。
Buroさんのパワポっぽい資料に名前しか書いてないので中身がわかりません。
わかっているのはMPCと併用するらしいことくらいです。

iterative wideningで検索すると確かに碁の関連の英語論文がヒットしますね。
関係なさそうだと思って放置していましたが、ちょっと見てみようかなぁ。

置換表云々は、僕の想像です。
αβを前提にしたアルゴリズムで高速化するネタの一つに、moveorderを工夫して
βカットが起きやすくするってのがあると思います。

反復試行する際、置換表には前回の評価の範囲が入っています。
それを今回探索のmoveorderの並べ替えに利用しようというものです。
反復深化なんかと同じ考え方です。

逆に言うと、反復を前提としたアルゴリズムで高速化するネタが、それくらいしか
思い浮かばないのです。
363: 310 2015/12/23(水)22:38 ID:MLtsaD3t(2/2) AAS
>>362
ご助言ありがとうございます。

MPCはまだ途中ですが、そんな感じです。
終盤n手高速化の類もしています。中盤探索だと葉に近いところで置換表外すと、
著しく速度が低下するので、最後まで置換表を使っています。

で、中盤の速度がいまいちで12手読みくらいが実用範囲って感じです。
MPCでd計算に100棋譜くらい試して一晩で計算できる範囲は13〜14手くらいが
限界な感じです。そろそろMPC計算しちゃおうかと思いつつ、まだ悶々と中盤探索で
どこか高速化できないかトライ中です。

SIMD命令はコンパイルオプションでそれらしい場所があったので、設定してみましたが、
速度変わらずで放置しています。どうやって使うものなのでしょうか?
そもそも、組込関数のpopcountとかbitscanで64ビット版が使えずに放置してる状況です。

並列化はMPCが終わって、一通りオセロの形にしてから、次ステップで勉強しようかと
思っています。

アスピレーションサーチは、1σは±7〜8手なので試しに±8の幅にしてテストしてみた
ところ、確かに若干高速化できている様子です。mtd(f)は下から寄っていく時はβカットが
効くのですが上から寄っていく時は遅いので、一発目で探索できる確率を上げつつ、
ある程度幅を絞るには、このくらいがちょうど良い感じですね。
364
(1): 310 2015/12/24(木)20:33 ID:zDiJT168(1/2) AAS
ちと調べてみました。SIMD命令はx64でコンパイルしている時は、設定しなくても自動的に
使うようになっているみたいな説明を見つけました。

並列化とかベクター化とかもコンパイラが自動でやってくれるみたいですが、レポート出し
たら確かに一つも対象になっていませんでした。評価値算出とmobilityの2関数は、なんか
効きそうな気がしますので、少し悶々とトライしてみます。

また、_mm_popcnt_u64と_BitscanFoward64は、今やってみたら、何故か使えました。
色々とコンパイラのオプションをいじったのが原因かなぁ。謎。
多少速度アップした模様です。

アスピレーションウィンドウはdの計算しなきゃと思っていましたが、よくよく考えたら、
評価関数の計算時の誤差ログが残っていますので、そいつでパラメータ作成してみます。

と、久々にFFO#43まで時間計測したところ、#43で答えが違ってる。
数か月前に最終2手高速化をいじった時にバグを仕込んだ模様です。
調べようとdebugモードにしたら64ビット組込関数が使えない。
やっぱりコンパイルオプションのどこかみたいですが、わからない。

だんだん問題が発散してきて、頭の切り替えが追い付かなくなってますorz
366: 310 2015/12/24(木)22:56 ID:zDiJT168(2/2) AAS
_mm_popcnt_u32()はすでに使っていました。u64が使えなかっただけです。
u32→u64で3〜5%くらいの高速化になっています。

困った事に、debugビルドの側では、まだ64bit版が使えていません。
debugを使いたい時は32bitに直さないといけない。
コンパイルオプションをいろいろ見比べていますが、どこなのかいまだにわかりません。

#43は最終2手なのか1手なのか、どちらにバグがあるのか切り分けようとして
ソースいじっているうちに直ってしまいました(汗)。
368: 310 2015/12/26(土)11:23 ID:2a5cp76f(1) AAS
どもです。バグったところはMPC使って無い箇所でした。

コンパイラの自動ループ展開は上記2か所で試してますが、なかなかうまく行きません。
なんとか依存関係を解消してループ展開強制すると劇的に速度低下する状態です。

その代り、いろいろググっていたら、BMI命令を見つけて、BLSIとPEXTを使ってみました。
速度バランスが変わったのでパラメータで置換表適用範囲を狭めるなどもしましたが、
FFO#40で1.55秒前後まで高速化できました。中盤探索も高速化はしているはずですが、
数%程度の改善というところでしょうか。まだ50%は高速化したい状態です。

色々アドバイスいただいたお蔭で、ようやくSIMDまわりの使い方がわかってきました。

ここまで来ると、BITBOARD操作の関数の見直しをしたくなりますね。
中盤探索の一番重い部分なので。
369: 310 2015/12/28(月)10:45 ID:i0yT273K(1) AAS
デバッグモードでu64系の関数が使えない件、解消しました。

MTD(f)に代えてアスピレーションウィンドウを採用しました。
中盤探索は、隣の評価値をたどっていくと、かえって遅くなるのでnegaScoutだけで
探索していましたが、これでMPC計算が多少高速化できそうです。

MPC計算はまだしていません。反復深化でどのくらいの深さの探索で、どのくらいの
件数なら実用的に計算できるか試行しています。14手読みまでは行けそうですが、
15手だと厳しいかなぁという状態。20手付近では盤面によっては、探索ノードが爆発的
に増えて、時間のバラツキも大きいです。

また、FFO#40-44の完全読みを計測しました。zebra比で#40は圧勝、#41-42は引き分け
ですが、#43-44は完敗。理由は#43-44は正解となる初手が2つあるためで、#43は10秒
以上かかってます。むむむ。
371: 310 2015/12/29(火)02:31 ID:F/Ba7yoX(1/3) AAS
ちょっと一括変換操作を誤って大変な事になっていました。一通り直していたところ、
FFO#40で1.45秒程度が出るようになってしまいました。多分、修復がてら置換表登録・
検索関数の変数の並びを、整列したのが効いたのだと思っていますが、びっくりポンです。

前回課題の正解着手が複数あるケースですが、MTD(f)のような評価値決め打ち系の
探索では、ぴったりの答えが見つかった時点で、ほかの手を探索する必要が無い事に
気づき、直してみたところ、FFO#44は速度アップしました。が、#43はまだ駄目です。
とはいえ、#43は浅い探索の評価値が外れすぎて時間がかかっているような感じなので、
浅い探索の深さを残り手数で調整すると直りそうな気がしています。

あと、FFOテストの全データをテストできるように登録しましたが、#59を見て、はたと、
途中全滅時のスコア計算が違う事に気づきました。自分のは一番単純なアメリカルール
です。ここを直すと、確実に時間が遅くなるような気がしますが、明日直してみます。

てな事をやって、一晩に0.1秒(比率にして7%前後)も短縮していると、まだなんか
やる事があるんじゃないかと・・・。
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(f)では、ワーストケースではウィンドウ中心が評価値の最少単位で動く関係で、
1石以下の少数計算をする中盤探索では、よけいに時間がかかる事が多いです。
そのため、アスピレーションウィンドウ導入前はただのnegaScoutにしてました。
終盤探索は、最少単位が1石になりますので、許容範囲です。

MTD(f)もアスピレーションウィンドウも、所詮本チャンのnegaScoutを呼び出すための
ドライバーにすぎないので、どちらも用意して、何かの折に速度比較しています。
今回は、ボツりましたが、ぴったりの値が見つかったら後の探索を省略する際には、
MTD(f)の方がマッチングが良かったので、そうしました。

ボツになりましたので、またアスピレーションウィンドウに戻りましたが。

#40ではzebraよりはるかに高速化できましたが、#43など遅いケースでは、数倍の時間が
かかります。こういうタイプの時間差は、単純な高速化じゃなくて、何らかのアルゴリズム
の違いがあるのかなと想像しています。
375: 310 2015/12/30(水)00:01 ID:lfikhn/D(1) AAS
結局、本日は探索速度アップばかりやってました。

中盤探索というか評価関数の計算でBMI2命令を徹底的に使ってみました。
また、ボードの回転操作系も見直しました。
10%程度は高速化できたと思います。でも、期待したほどではなかった。
あと、速度アップするなら、ボードの対角線転置かなぁ。あと効果は微妙だけど、180度
回転がビットオーダーの逆転なので、これも何か組み込み関数があったらうれしいなと。

終盤探索では、FFO#59問題に対処。
スコア計算の修正と、全滅など64石の差がついた時に、βカットと同様に後続の探索を
パスして時短。minMaxで言うところのα値の更新があり得なくなるからです。

浅い探索が11手だと3秒程度で解けるのに、15手だと60秒かかったりと、いまいち動き
に納得がいかないので、まだ何か問題があるかも知れません。

中盤探索をあと50%は高速化したいなぁ。というか、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
ギリギリ12時前に直った。
メモリリークではなく、不正なアクセスでした。
多分直ったと思う・・・

来年の抱負は、MPCの計算をする事と、GUIを作る事です。
元々VBのGUIからDLLで呼び出すつもりでしたが、なんとなくC++でやってみようか
という気になってきています。
378: 310 2016/01/03(日)11:08 ID:3YPfF+nL(1) AAS
バグは解消してました。なんとも不可思議な事になっていました。
スタック領域を破壊していて、破壊された箇所がたまたまdepth(残り探索深さ)だったため、
探索深さがマチマチになってました。計算時間やメモリ使用量が異常になる以外は、そこそこ
それっぽい探索結果が出ていたため、メモリリークだと思ってしまったという。

中盤探索の置換表適用範囲も、ちゃんと効くようになって深さ11〜12まで置換表を使用
するのが効果的と出て、探索値のバラツキもそこそこ揃って、探索時間も予想できる範囲に。
メモリ使用量も安定しました。

ある棋譜に対し、20手目から終局まで順に、深さ1〜17の探索を、反復深化を活用しながら
探索値を求めるプログラムを用意して、14棋譜を対象に実行したところ凡そ7時間で完了。
速度的にはこんなものかなぁという感じ。もっとも、深さ17だと結構、探索時間・ノード数の
バラツキが大きいので、10件前後だと終了時刻もバラツクはず。

とりあえず、棋譜からランダムに10件程度を抽出し、この探索結果を貯めていくところまで
作りました。トータル100件程度集めれば、MPCパラメータ計算には十分だと思う。
探索結果を貯めてあるので、毎晩10件くらいづつ追加し、直説法で都度パラメータ再計算
して精度を上げていく事ができる。
379: 310 2016/01/04(月)22:22 ID:1p46+Vgy(1) AAS
MPCのための探索データ蓄積の間に、並列処理について調べてみました。
VC++だとopenMPとPPLってのが使えるみたいです。
?concurrent_unordered_mapが便利そうなので、PPLにしよううかなと。

で、脳内コーディングであれこれ考えていたら、AIの中でBoardクラスを参照渡しして、
差分型で盤面を進めたり戻したりしているのが、とても並列処理と相性が悪い事に
思い至りまして・・・。コピー型に戻して、何をクラス化するのかとか見直してみようかと
言う事に。

多分数日がかりになるかなと。
383: 310 2016/01/09(土)02:12 ID:GhyCVx1P(1) AAS
どもです。

とりあえず、コピー方式に変えてましたが、変にバグを仕込んだりして、時間がかかって
ました。ようやくデバッグもあらかた終わったのですが、まだ原因不明・解釈不能な速度
差があって、終盤探索のみ速度が10%以上低下した状態です。
というか、コピー版を書きながら気づいた箇所を、ボードクラス版にも反映すると、ボード
クラス版が高速化して、差が広がるという。
で、クラス版がFFO#40で1.40〜1.42秒になりました。

>>380さん
おっしゃる通りですorz

プログラム直しながら、ネットでVC++の解説をつまみ読みしながらのコーディングに
限界を感じたので、オライリーさんの出番という事で、アマゾンに本を数冊注文しました。
到着待ちの間にやるなら、適当に作っていったクラスの整理統合かなぁ。
あと、openMPのお勉強。
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まであと10倍の速度アップかぁ。並列化で3倍くらいまで詰められないかと期待。

一応、Boardクラスのポインタ渡し版(差分方式)も試してみましたが、今のところ、若干
速度低下しています。もともとの差分方式は、Boardクラスを継承したAIクラスのメンバ
関数として実装してます。
これらの一見無駄な作業も、バグ探し&逐次探索の速度アップに有効だったという事でorz
386: 310 2016/01/11(月)20:31 ID:IrhGHm3u(1) AAS
とりあえずopenMPで並列化トライしてみましたが、コンパイル中に内部エラーになる。
ネットで見ると最適化オプションがらみらしいけど、なんかよくわからなかったのでパス。

PPLを使って、とりあえず並列化のテスト。オセロでは標準的と思われるn段YWBCに
してみました。forループみたいな特定の形ではPPLは結構簡単という印象。

バグは一通りとれた状態だと思いますが、FFO#40で1.25秒が0.85秒程度になり
30%強の高速化。あと少しだけソース修正するつもり。

使ってるパソコンは2コアでした。昨夜まで4コアのつもりでいましたが(汗)、2コアなら
こんなものなのかな。
388: 310 2016/01/13(水)13:02 ID:Yd1pcfW8(1) AAS
どもです。

コア数2だと、理屈の上では2倍近くまでは速度アップできるのかなぁと思います。
一般的にはどのくらいの倍率をターゲットにしているのでしょうか。

YBWCの適用のパターンをいくつか試しましたが、タスクマネージャーで見たCPU使用率
は、ほぼ100%になってるので、単純にはスピードアップは難しい感じがしてます。
PPL自身のオーバーヘッドなのか。
PPLは楽ちんだけど、チューニング箇所がなさすぎな感じ。

あと、YBWCやってる以上、YBの着手をmove orderingする意味が無い感じなので、
sortが一つ省けるかなぁというところ。ルートに近いので、あまり効果は無いと思うけど。

ここまで来ると、8コアのパソコン持ってきたら・・・
SIMD拡張命令だBMI命令だを使っておきながら、コア数2で頑張るのもどうかみたいな。
389: 310 2016/01/16(土)09:10 ID:mjTPCiWE(1/2) AAS
PPLはMicrosoftのDeveloper Networkくらいしか情報が無いので、ひたすらリンクを
たどって情報収集してますが、ほとんど機械翻訳で、結局カーソルあてて英文読ま
ないと意味が分からないという・・・

で、排他制御とかいい加減にしていたノード数カウントなどをきちんとして、ソースの見易さ
と効率を上げようと色々と細かく修正。combinableとかcritical_sectionとかInterlockedとか。

と・・・思ったら・・・中盤探索で確率10%程度で違う答えが返ってくる・・・
並列探査のバグはわかりにくくて時間を食ったのですが、どうもcombinableの動作が変。
期待した動作をしていない。でも、情報が無さすぎで、どこを直せば良いのかわからず、
結局同等の機能を動的配列にしてしまった。
390: 310 2016/01/16(土)11:37 ID:mjTPCiWE(2/2) AAS
中盤探索を1万回程度回して、違った答えが返ってこない事を確認できました。

ノード数カウントはInterlockedIncrementを使っているんだけど、やはり排他待ちロスが
大きいようで、ノードカウントありだと0.8秒前後、無しだと0.7秒前後になる。
使えなかったcombinableみたいな形にして、一つの再帰関数内はローカル変数で加算
して、最後にまとめて1か所で排他加算するようにしてみようかな。

並列タスクの起動順で、探索ノード数が違ってくる関係で、実行時間のバラつきが±0.5
秒くらいになっている。
391: 310 2016/01/18(月)09:54 ID:ED4vwFCp(1) AAS
結局、ノード数・リーフ数カウントは、戻り値を構造体にして返す方向にて検討。
普段の探索には不要だけど、solverだと表示したいので。
これで完全にローカル変数になり、排他ロスを気にする必要がなくなる。

デバッグ用の置換表回りの統計は、所詮デバッグ用なので、一旦全削除。
必要になったら、こちらは#ifdefで囲って、排他加算する。

で、構造体の形であれこれ悩んでいたら、戻り値をクラスにできる事に気が付いて・・・
あらためてC++すげーと感心中。

けど、かなり全面的な修正になるので、時間食ってます。
まずは中盤探索を修正して、ノード数がおかしくない事を確認。
終盤探索の修正はこれから。探索を使う系の統計処理も変更しなきゃならないけど、
MPC以外は、次いつ使うかわからないw
392: 310 2016/01/19(火)00:13 ID:Dh1WPUXC(1) AAS
終盤探索の修正完了。

0.8秒±0.05秒と、結局、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を30%くらい占有してしまいます。
昨日まで快調に動いていたのが突然遅くなって、悩んでいましたが、これが原因のようです。
というわけで、本日は色々改変したソースの速度が計測できずに悶々としてました。

色々すったもんだ挙句、PVラインを渡す形にしましたが、効果があったかどうかは微妙。
色々付け足した事で生じた速度低下はペイしたかなぁという感じで、#40で0.78秒前後。

本格的にネタが尽きて来たので、ここから先は、MPCをきちんと実装してiterative widening
にかけるしかないかなぁという感じです。あと、定数で渡している置換表適用高さなどの
パラメータを、空マスや使用条件で作ると、実用的になるかな。
1-
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ

ぬこの手 ぬこTOP 0.031s