【オセロ,将棋】ボードゲーム Part3【囲碁,War】 (636ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
310(126): 310 2020/05/29(金)20:25 ID:wYh6jGrP(3/3) AAS
orderingの中でパス処理をしていたのでmobility関数を呼びまくっているのが遅い原因
ではないかと思い、パスの処理の仕方を変えて、パスも１手とするように変更したところ、
１５〜２０％の速度低下まで戻りました。他にも、つられてバグが発覚したので修正。
かなりのレアケースでしか発生しないバグですが、今まで自信満々で完全読み切りは
間違っていないと思っていましたが、なんか自信なくなった。
中盤探索も同様に修正したら、浅い探索の読み筋が変わったみたいで、少しは精度が
良くなるのかなぁと期待しています。
168: 310 2020/03/11(水)19:25 ID:N0CjcdIm(1) AAS
Eigen UnsupportedのTensorクラスを見つけて、またぞろDCNNに興味が沸いて来ま
した。で、思い出しがてらウェブを眺めていました。前回断念したのは畳み込み層の
計算を行列で行うためのim2colのロジックを高速に行う方法が見つからなかったから
だと思い出しました（汗
しかし、気が付いてしまいました。所詮８×８のマスの定型変換で、汎用性いらないので
６４ビットのローテーションとマスク値とのandというビット演算で、前処理ができてしまい
ます。そのあとで行列に変換すれば良いだけの事でした。つまりim2col関数はいらん。
もう少しDCNNの最新動向をフォローしてから、同じ棋譜を学習させて試してみたいと
思います。
174: 310 2020/03/12(木)00:31 ID:CNvjXxHZ(1/2) AAS
GitHubとかよーわからんのだけど、コメント適当だったり、変数や関数名の英語が
変だったりするソース公開する度胸ないのを言い訳に、調べようとしていない（汗
176: 310 2020/03/12(木)00:39 ID:CNvjXxHZ(2/2) AAS
情報ありがとうございます。
ちと調べてみます。
前みたいにソースもデータも丸ごと飛んだら困るので。
183: 310 2020/03/16(月)00:36 ID:FpZgJFeI(1) AAS
しばらくは棋譜の遡りを優先しようと思っていたのですが、やっぱり暇ができると
どうしても何かやりたくなってしまい、結局序盤中盤の貪欲法絡みのブラッシュアップ
をしてしまい、またまた遡り対象の棋譜を増殖させています（汗。
DLやろうか、将棋AIの勉強しようかと思い立ち、将棋AIの本などを買い込んでつらつら
眺めていたら、実現確率探索なるものを見つけてしまいました。遷移確率は評価値の
Softmaxで作れる気がしています。現在、前方の打ち切りはProbCutでやっていますが、
途中の１つの盤面の評価値が酷い状態だと、その時点で問答無用でカット対象となって
しまう懸念があります。その点、実現確率探索の方が多少ロバストなのかなぁと。逆に、
手が広い局面では探索深さが浅くなってしまう悪影響も想定できます。
とはいえ、中盤探索のロジック自体は多少の改良で済むのですが、置換表使って中盤
探索の結果を終盤探索のオーダリングに使うところは結構修正が必要な気がします。
最悪反復深化をまるっとあきらめなきゃならないかも知れません。あと、なぜか評価値
に＋１〜２程度の手番加算がついたみたいになっている事から、探索深さを揃えられ
ないと、そっちからも悪影響が出る可能性があります。
かなり大幅な変更と、テストが必要なので、ちょっと躊躇しています。
プロジェクト全体コピーして別プロジェクト建てるレベルです。むむむ。
187: 310 2020/03/18(水)00:47 ID:Wk4mfxEa(1/3) AAS
結局、実現確率探索に取り掛かってしまいました（汗
新規ソリューション作ってコピペ始めたところで、いずれ評価関数を整数化したかった
事を思い出して、あちこち修正開始となりました。
一応、普通のDepthバージョンと同じ深さになるように調整して、速度比較してみるつもり。
189: 310 2020/03/18(水)23:45 ID:Wk4mfxEa(2/3) AAS
実現確率探索の中盤探索、プロトタイプのαβ版を作って癖を見ています。
実現確率は、評価値のSoftmaxで各要素を足して１．０になるように正規化するより、
最大値が１．０になるようにした方が使いやすいです。というのも、最大値をひたすら
追った枝の終了条件が綺麗に決まって最大深さを指定できるようになるからです。
１．０そのままだと終わらないので、例えば０．５にしておくと、深さｎにしたい時は１÷２＾ｎ
が閾値になります。０．１の時は１÷１０＾ｎです。まあ、なんでもよいという事です。
後は各要素の差のつき具合を決める定数を調整すると、評価値が悪い手について、
どこまで探索の深さを確保するのかが決まります。ここが職人的作業なのがネック。
絞ると爆速。∞だと、ただの全幅探索になります。
速度は結構出てるのですが、調整ミスると全くダメみたいな様子が見え隠れしていて、
本当に常に使えるのか、まだ心配です。おそらくProbCutでも同じような問題がおきて
いるんじゃないかと思いますが。
次は置換表ですが、合流が発生した時の実現確率がルートによって違うので、その
時の置換表の評価値を使って良いのか悩みどころです。また、上述のように最大探索
深さを調整できるので、反復進化的に閾値を下げて行く事が可能性です。そうすると、
反復深化的に使いたくなるのが人情ですが、オーダリングにどのように反映するのが
良いのか。これも悩みどころだったりします。
要するにあと１週間くらいは遊べそうです（笑）
190: 310 2020/03/18(水)23:56 ID:Wk4mfxEa(3/3) AAS
あと、裏で棋譜作成進行中ですが、評価関数の学習時に、既存データに対する
エラーが増加を始めて、過学習の傾向を示しているのですが、例えばFFOの盤面
のように教師データ中に現れない盤面に対するエラーは減少しています。
状況的には、極端な石差がついている盤面の評価値が、石差ほどの評価値になって
おらず、じわじわと汎化が進んでいる一方、±０近傍の盤面は既に多いため、過学習
気味になっているのかなぁと推測しています。
とはいえ、非常に気持ち悪いです。
というわけで、ちょっと工夫をして石差が大きい棋譜を優先的に遡りチェック対象にしたり、
新規の自己対局するときに石差が大きくなる（悪い）進行も作るようにする事で、ほんの
少しですが、石差が大きい棋譜が増えるようにしてみました。まあ気休めです。
191: 310 2020/03/19(木)23:17 ID:opMYHtHc(1) AAS
実現確率探索の中盤探索ができました。置換表と並列処理のところまでです。
反復深化→読み切り処理までです。置換表というか、オーダリング処理を結構修正。
反復深化まではそこそこ機能していますが、置換表経由で読み切り処理の高速化が
性能が出ません。置換表経由で、中盤探索の結果を用いて終盤探索のオーダリング
をするところで、置換表データの不足があったり、オーダリングの間違いが生じて、
無駄な探索をしているように思います。
とすると、これは読み切り処理を前提とすると結構致命的な問題な気がします。
もちろん、まだバグや仕様ミスの可能性もありますが。というわけで、Solver関係には
使えない可能性が出てきました。
また、評価関数で実現確率を導いているので、浅い段階での間違いに対して、探索
対象をロックしてしまいやすく、深く探索していっても間違いがなかなか改まらない
傾向が見受けられます。
まあ、仮にダメでも、新バージョンにする過程で、これまでペンディングしていた細かい
修正ができますし、既存タイプの中盤探索も作ってあるので、このまま進めてみます。
193: 310 2020/03/21(土)02:31 ID:XYOBIhf/(1) AAS
実現確率探索で、探索幅広げる方向の反復を試してみましたが効果はあまりなし。
単体で使用するとかなり早いのですが、置換表使った探索との相性がいまいち。
とりあえずSolverまで作って速度計測していますが、既存の反復深化より遅く、反復
深化無しよりは若干早いという感じで、単体の速度を利用して幅を思いっきり広げて
みましたが、こちらは逆に遅くなるという体たらく。
置換表周りでどこか間違いがあるのかなぁという気もしていますが、今のところ不明。
Solver周りでの活用は一旦置いといて、自己対局で使ってみる事にします。
198: 310 2020/03/28(土)00:29 ID:vtZj/mQ8(1/2) AAS
実現確率探索というか、ソース全体見直し版が、だいたいできました。
まだデバッグ全部済んだわけではありませんが、後はログメッセージなんかの
細かいところくらいの修正かなと。
実現確率探索自体は、棋譜作成にフックを入れる感じでの使用にとどめていますが、
しばらく動かして、結果がよさそうなら切り替えようかなと思います。というか、対戦版
作るときには、中盤探索は実現確率探索で行くと思います。
で、実現確率探索と呼んでいますが、実際のところは違います。本来の実現確率は
「プロ棋譜など別途棋譜集から、よく出てくる手を回帰分析で確率化したもの」で、
よく出る手については深く探索しましょうという内容です。自分の奴は、確率を１手読み
の評価値から生成しています。１手読みにした理由は、差分計算で速く計算できる
からです。というわけで、本来は別の名前にした方が良いのですが、ネーミングセンス
が無いので放置です（笑）
他にも、本来と違う形で実装してるけど、放置してある名前が結構ありますorz
200: 310 2020/03/28(土)22:16 ID:vtZj/mQ8(2/2) AAS
見直し版のチェックを本番やりながら進めてます。
今のところ、学習の速度が３０％程度ダウンしたものの、終盤探索の速度が
３０〜５０％高速化している感じ。どちらも原因不明。
201(1): 310 2020/03/31(火)00:30 ID:1mhY2vrp(1) AAS
見直し版で、遡りチェックで無駄な処理を見つけて直しました。
更に速度アップして、トータル５０％強の速度アップとなりました。
まだ探索自体の速度は上がってませんが、まだ無駄があったとは。
202: 310 2020/04/01(水)23:58 ID:SRR0rDGm(1) AAS
急に探索自体の速度アップを思い立ちまして、いくつか実行。
ヒープ領域に作っていたオーダリング処理をスタック領域に来るように修正。
置換表のHash関数の修正で、置換表のキーエントリーの偏りを減らす。
これらにより更に高速化して、トータルで前バージョンの倍速近くなった感じです。
残り２６手探索処理が１時間に９０件弱→１６０件くらい。
あと、もうちょっとやってみたい事があります。
207: 310 2020/04/06(月)22:33 ID:eOx9NvDZ(1) AAS
更に少し高速化しました。
オーダリングのvectorをスタック領域の配列に変更する部分ですが、並列探索部分
にも適用しました。配列も&でアドレス渡せばSTLのalgorism周りが使えるの知りました(^^;
スレッド間でのlockも他の処理と一緒にできるので、オーバーヘッドはありません。
あと、地味にセーブの時間がかかっていたので、回数減らしました。
残り２６手１０００件で１０時間半が、５時間４０〜５０分くらいまで来ました。平均２０秒強。
残り２５手の読み切りができていてBookで時短しているので、まったくの新規棋譜の
読み切りはもっと遅くなります。
sort部分も何とかならないかと思いましたが、もともと３２件以下（オセロはたまたま
ですが次の手の上限は３２）は挿入ソートになっているようです。コピペで挿入ソート
を組んで、速度比較してみましたが、有意差は出ませんでした。
件数少ない時に早くかつ安定ソートな方法が他にないか調べてみようかと思います。
248: 310 2020/04/22(水)20:43 ID:ZptezZKq(1/2) AAS
相変わらず棋譜作成中。
プログラムはそれなりに改良しているつもりだけど、成果は全くなし。
まあ、思いついて試すのが楽しいんだけどね。
つか、逆順探索での棋譜訂正。やってるそばからあまりに間違っている筋を
見つけて、修正かける過程で、新しい棋譜どんどん増えて、バックログがどんどん
増えていく地獄になっています。まだまだ重要な分岐でも間違いというか未探索
が多すぎる。
手作業で修正箇所見つけるの面倒なので、延々やらないといけないけど、
ε-Greedy的な何か導入しようかなぁと思い始めています。
250: 310 2020/04/22(水)22:21 ID:ZptezZKq(2/2) AAS
あるところまでは、間違いは間違いと学習するための時間かも知れませんね。
255: 310 2020/04/24(金)19:50 ID:wU9GyZ2x(1/2) AAS
DCNNなら層数よりもフィルタ数の方が大事かも。
257: 310 2020/04/24(金)22:19 ID:wU9GyZ2x(2/2) AAS
>>256
２５６フィルタあるんなら流石に大丈夫そうだね。
284: 310 2020/05/09(土)00:56 ID:tOwbW1Pp(1) AAS
棋譜作成触りすぎるとなかなかはかどらなくなるので、しばし回しっぱなし。
そろそろBookが巨大化しすぎているので、メモリーからSDDに移せないか検討中。
concurrent_unordered_mapを自作した経緯があるので、同じような感じでランダム
アクセスなDB化をしてます。確定分は探索で使うのでメモリーにおいて、速度を
必要としないアクセスをDBにしようかなと。
巨大Bookの作成処理の類を並列処理にしているので、何とか並列にできないかと
色々やっていますが、色々と罠がある。複数プロセスからの並列更新はあきらめた
けど、単一プロセスからの並列更新でロック範囲がまだいまいち。
専門書買ってコード見て勉強した方が早いんだろうけど、まあ、しばらく楽しみます。
287: 310 2020/05/12(火)23:05 ID:AcB4a3UT(1) AAS
うぬぬ。DB化は並列諦めてみたけど、やはり更新が遅すぎる。
もうちょっと工夫してみるけど。
296: 310 2020/05/18(月)21:57 ID:lyHQ6R5E(1/3) AAS
Hash関数変更
DBのハッシュキーの効率が悪かったので、ちょっと考えてみた。
今まではshuffle_epi8でバイト単位シャッフルしていたのを、BMIのpextでビット単位の
シャッフルと、rotateしたものを、xorでまとめていく方法。以前よりは、ちょっと良くなった
気がする。
何をもってよくなったかの指標が欲しくなり、ネットを探索したけど、数値指標みたいなの
は見つからない。確率論の誕生日問題の反対みたいな状況なのでしばらく考えてみる。
要するに、１万人くらいの生徒がいる学校で、誰一人誕生日ではない日が何％くらい存在
するのかという類の問題です。
また、そう考えてみると、現状では直観よりかなり未使用キーが多い気がしています。
xorを繰り返してビットのオンオフをすると、いずれ立っているビット数が３２個を平均と
した正規分布（二項分布）になって、一様分布にならないのではないかという疑念が。
正規分布だと、中央に近いところは重複しやすく、立っているビット数が０とか６４とか
の出現確率が下がる事になります。xor繰り返すと正規分布に本当に近づいていくのか、
ちょっと検証してみたい。
297: 310 2020/05/18(月)22:17 ID:lyHQ6R5E(2/3) AAS
DBの件
たぶんあるだろうとネットで検索してみたら、Kyoto Cabinetなるキーバリュー型の
簡易DBライブラリがある事が判明。ほかにもLevelDBとか、何種類かあるみたい。
RDB使うまでもないけど、データ量が多いとメモリーだとリソース勿体ないみたいな。
やはりみんな考える事は一緒だなと。せっかくなので導入の方向で検討。
DBの速度問題
また、おそらく１棋譜単位でのBook更新は速度的に問題ないのですが、DAG（合流）
時に、棋譜外の合流元の方の更新がされないという問題があり、学習前に一括で
再構築しています。この一括更新が件数の関係ですごく時間がかかる事が問題です。
一応、１棋譜単位で更新した時に、DAG分もちゃんと処理するロジックを検討中です。
バグさえなければ速度問題はかなり解消できるはず。とはいえ、何回もループを回す
処理となるため、速度に自信なし。
298: 310 2020/05/18(月)23:50 ID:lyHQ6R5E(3/3) AAS
DBの件…
確定探索の時にはメモリーに確定分だけおいとくと考えていましたが、
今件数確認したらおよそ２／３は確定分として確保しなきゃならない
事に気づきました（汗
棋譜作成時はメモリーでやるしかないかも。
１棋譜更新でのDAG問題回避はやりたいかな。
Book再構築にだいたい２０分くらいかかる。
DAG回避で１棋譜分更新するのが１秒として１０００棋譜追加でおよそ１６分。
これ以下の時間で済むならやる価値ありそう。
299: 310 2020/05/20(水)01:15 ID:Xgj8E+2H(1/2) AAS
久々に完全読み切りでバグ発生。
ProbCutを広げながらmtd(f)している時に、どうもパス絡みで発生しているっぽい。
ProbCutによるIterative Wideningを止めたらちゃんと読み切る。
まあ、置換表絡みなんだとは思うけど、事例が少なすぎて（数か月に１回程度）、
前の記録消しちゃったので、とりあえず記録を残し、絆創膏当てて続行。
気が向いたらデバッグしてみる。可能性があるところはなんとなくわかっている
つもりだけど。
Book更新時のDAG回避は、かなり悩ましい。というか頭がこんがらがる。
未使用Hashの期待値計算も頭が未だにこんがらがってます。。
302: 310 2020/05/20(水)17:28 ID:Xgj8E+2H(2/2) AAS
Hash関数の効率判断基準できました。
同じキーにデータが８つくらい入っているようなものもあり、それが適正かどうか
判断できなくてゴチャゴチャしていましたが、昨夜しれっと書いたように未使用キー
の数の期待値に着目したら簡単でした。
キーサイズと、データ件数からExcelなどで簡単に計算できます。
３件程度調べてみましたが、理想的な一様ランダム値で生じる未使用キー数の
期待値との差は０．１％未満で、このHash関数も一様ランダム化するものと言って
良いレベルでした。
逆に言えば、自分の典型的な使用方法だと２０〜３０％のキーが未使用になる
という事のようです。これはこれで…。
304: 310 2020/05/21(木)00:46 ID:ahADKaci(1) AAS
Hash値、１件２件…と期待値出そうと思ったら、なんとなく昔の記憶が戻ってきて、
０件の時は不要だけど、こちらではPとかCとかが必要になるような気がしてきた。
確率の勉強するかな。
ZDDちらっと見てみたけど、ちょっと目的と違うような感じがしている。
本買ってみるけど。
脱線はこれくらいにして、DAG考慮したBook更新に戻ろう。
308: 310 2020/05/29(金)00:49 ID:wYh6jGrP(1/3) AAS
DAG時のBook更新の件、めっちゃ悩み中。
普通にやったら１件更新に１４秒とかかかって使い物にならない。
逆引きDBを作ろうかと思うのだけど、結構なサイズになるので、それこそメモリーに
置きたくない。形としてはunordered_multimapになるんだけど、Kyoto Cabinetが重複
キーを許すのか英文読まなきゃならないので止まってる。
そうこうするうちに完全読み切りのバグがまた発生して、事例が３件になったので、
調査開始。２か所間違いを発見。一つ目はケアレスミス。
２つ目は最善手の直後にパスが来るケース。置換表登録はパス後、オーダリングなどで
読む時はパス前の盤面になっていた。これで値が狂う理由がいまいち理解できないの
だけど、修正したら正しい答えが出るようになった。パスの処理は本当に鬼門。
たぶんバグは取れたけど、５０％くらい速度低下。どこかにまだバグがありそう。
309: 310 2020/05/29(金)00:56 ID:wYh6jGrP(2/3) AAS
速度低下は５０％どころではなかった…１５０〜２００％だorz
312: 310 2020/05/31(日)10:02 ID:/CnVYfEH(1) AAS
またエラーが…
なんとなく記憶をたどっていくと、初段で並列処理してMap-Reduceすると、βカットの関係で
評価値は合っていても、ｏｒｄｅｒｉｎｇ次第で間違った手を返す事を思い出しました。
で、たまたま回避策となっていた処理を>>201で外してしまったのではないかと。
並列探索だと本質的に回避できない気がするので、初段を順次処理に変更。残り空きマス
２６での平均処理時間。一時は２０〜２５秒くらいまで来ていたのが、３０秒程度に悪化orz
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.026s