[過去ﾛｸﾞ] 【オセロ,将棋】ボードゲーム Part2【囲碁,War】 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
517: 310 [sage] 2018/11/25(日) 09:01:51.50 ID:Mml0PIJf(1) AAS
Iterative Widening何とかできた。平均的に高速化できていると思う。
FFOについては相変わらず>>495495(2): 名前は開発中のものです。 [sage] 2018/11/17(土) 18:39:02.10 ID:8gp5y6uH(4/5) AAS
空きマスリストを作る方式でやってみたのですがビット演算のほうが5%速かったみたいです
こうなるとオーダリングのコストを下げるしか無くなってきました
さんと比較して速度は半分くらいかな。
一方で記譜作成的には倍速になったイメージ。細かく４σまでWideningして
いる事で、仮探索の誤答が減った事が効いています。
仮探索で増える時間
＞ 仮探索が正解した時に減る時間 ＋ 誤答した時に増える時間
Iterative Wideningで、仮探索時間の削減と正答率の向上の両方が実現できた
感じです。この辺、課題盤面との相性がある話なので、統計的に計ろうとすると
かなり面倒です。というか、統計的に計るためには、前提となる評価関数をロック
しなきゃなりませんが、現在記譜作成しながら評価関数学習させてますので、
前提が常に動いてしまいます。
現在オーバーヘッドが嫌で、ノード数をとっていません。並列化するとロック
の待ち時間で数％〜１０％くらい速度が落ちちゃうからです。ノード数をとれば
純粋な速度比較がしやすいのですが、悩みどころです。
522: 310 [sage] 2018/11/27(火) 09:45:52.43 ID:IL6H1udh(1) AAS
自分の場合、プログラムいじるネタが欲しくて、ヘウレーカ！って感じを味わいたくて、
続けているだけだからなぁ（汗
目標でかすぎるとか、期限切りすぎると、焦って嫌になるだけだよ。
オセロなんて、既にやってる人ほとんどいないから、ちょうど良いのだｗ
今の目標は、６０歳になるまで続ける事ｗ
535(761): 310 [sage] 2018/12/02(日) 10:27:19.04 ID:YQiXDU8o(1) AAS
使用コア数制限するパラメータないの？
自分のは並列化処理に使用コア数カウンタ入れて、同時並列数を制限している。
もっとも常に４コアで４多重マックスで動かしているけどorz。１６コアなら１つくらい
他のプロセスに空けても、あんま速度低下なさそうでうらやましい。
今現在は記譜作成がメインなので、気が向かない時もほっとけば棋譜を訂正しながら
勝手に学習して、少しづつ速度アップしてくれている。気が向かない時に焦らずに済む
のでお勧め(^^;
一時速度アップに燃えていたけど、１勝９敗以上の比率で速度アップに失敗して（まあ
そんなもんなんだけど）、今は停滞期間中ｗ
540: 310 [sage] 2018/12/09(日) 13:20:20.42 ID:j5g2lrg3(1) AAS
まったりと記譜取りしてても仕方ないので、速度アップできないか色々あがいてました。
久々にプロファイラで確認したところflip関数が３０％、mobility関数が８％ほどでした。
Edaxのソース見つけたので禁断の答え合わせ。flip関数は一つ昔のタイプなので、
恐らく自分の方が早い。mobilitiy関数は少し早そうなので、考え方を導入。でも誤差
範囲の効果しかなかった。
速度計測ルーチンを作って、並列単体速度比が１．２程度しか無い事が判明。
並列処理で排他待ちしそうなところに無駄がないかチェックしたところ、ほぼ全部無駄
だった事が判明（汗。無駄箇所を全て削除したけど、誤差範囲（汗
後方枝刈（ヒューリスティックスなオーダリング）が気になるので、ノード採取してみた。
やはり２割程度速度ダウンするので、プリプロセッサで普段は切り離す事に。
その他もろもろ誤差範囲の改良を積み上げた結果、なんとなく１〜２割は速度アップ
した気がしますが、並列処理の効率が悪いのと、後方枝刈の工夫が足りていないの
２か所が、これからの課題かなと思います。
あれ？なんか、ループしてmin-Max探索の高速化に目的が戻ってきている（笑）
549: 310 [sage] 2018/12/18(火) 00:10:23.05 ID:4TPQUuZQ(1/2) AAS
FFOテスト（#40−#49）、色々誤差範囲の改良を加えてじわじわスピードアップ
していたけど、ある日突然２０％くらい悪化。元に戻せるところは戻したけど、
結局ダメで、裏で評価関数の学習し続けた結果、途中経過でたまたま探索が
悪化するところにはまってしまったと言う事かなぁと。
実際、悪化しているの#49だけで他は改善していたし、学習都度表示している
FFO問題の８手読みの次の一手の合否が、14/20から11/20に悪化している。
こういうのあると、速度アップで何を信じて良いのかわからなくなるよね…
550: 310 [sage] 2018/12/18(火) 00:14:29.31 ID:4TPQUuZQ(2/2) AAS
という問題もありながら、ノード数表示して、>>492492(1): 名前は開発中のものです。 [sage] 2018/11/17(土) 11:45:17.49 ID:8gp5y6uH(3/5) AAS
間違えて前のバージョンを載せてしまいましたｗ
今回はこちらです。比較になってちょうどよかったかも
FFO#40 ( Exact:(a2:+38) 1.29sec node: 10.63[Mn] nps: 8244[Knps] )
FFO#41 ( Exact:(h4: +0) 2.97sec node: 25.54[Mn] nps: 8599[Knps] )
FFO#42 ( Exact:(g2: +6) 2.24sec node: 20.58[Mn] nps: 9189[Knps] )
FFO#43 ( Exact:(C7:-12) 2.54sec node: 19.23[Mn] nps: 7572[Knps] )
FFO#44 ( Exact:(B8:-14) 4.32sec node: 32.07[Mn] nps: 7418[Knps] )
FFO#45 ( Exact:(b2: +6) 27.68sec node: 294.61[Mn] nps:10644[Knps] )
FFO#46 ( Exact:(b3: -8) 7.56sec node: 68.56[Mn] nps: 9070[Knps] )
FFO#47 ( Exact:(G2: +4) 3.25sec node: 36.70[Mn] nps:11293[Knps] )
FFO#48 ( Exact:(F6:+28) 21.11sec node: 195.99[Mn] nps: 9286[Knps] )
FFO#49 ( Exact:(e1:+16) 34.84sec node: 346.90[Mn] nps: 9958[Knps] )
FFO#50 ( Exact:(d8:+10) 108.94sec node: 960.91[Mn] nps: 8820[Knps] )
FFO#51 ( Exact:(E2:+6) 36.21sec node: 378.54[Mn] nps:10453[Knps] )
FFO#52 ( Exact:(a3:+0) 63.95sec node: 730.82[Mn] nps:11429[Knps] )
FFO#53 ( Exact:(d8:-2) 545.77sec node: 6.17[Gn] nps:11304[Knps] )
FFO#54 ( Exact:(c7:-2) 626.09sec node: 7.42[Gn] nps:11848[Knps] )
FFO#55 ( Exact:(G6:+0) 2492.74sec node: 31.10[Gn] nps:12475[Knps] )
FFO#56 ( Exact:(H5:+2) 212.26sec node: 2.52[Gn] nps:11894[Knps] )
FFO#57 ( Exact:(a6:-10) 520.85sec node: 6.35[Gn] nps:12183[Knps] )
FFO#58 ( Exact:(g1:+4) 588.80sec node: 8.54[Gn] nps:14512[Knps] )
FFO#59 ( Exact:(g8:+64) 1.88sec node: 8.86[Mn] nps: 4722[Knps] )
さんの結果と比較すると、
ノード数に圧倒的な差が。NPSは速いけど、それ以上にノード数が多い。
枝刈の差というにはあまりに大きな差で、一桁近い差です。
これ、Iterativeな手法で生じる置換表探索の差じゃないかと思う。
自分のは置換表の動作が遅いので、あまり深い探索まで置換表を適用できず、
読切において後ろの方は置換表が無い（そもそも使用していない）事で、何度も
再探索しているからかなと。
concurrent_unordered_mapを使っているけど、自前でハッシュDB作った方が
良いかもと思い始めた。そこで速度アップすると、置換表適用深度を深くできる。
こういう時、自前で作る人はチェーンハッシュ使っているのかな？
553: 310 [sage] 2018/12/19(水) 22:48:18.33 ID:T2sH1fj1(1) AAS
ハッシュの構想し始めましたが、確かに自分が作って早くなる保証はないですね。
インターフェースを既存のstlに合わせようとか思って調べ始めたら面倒になりました。
で、色々見ていたら、そのまんま効率化できそうな使い方を見つけた。
有れば読み込んで更新、無ければ追加の方法です。
あとバケットサイズとか個数とか、その辺を調べていった方が早くなるかも。
並列処理だとtry_emplaceが使えないのね。これが使えたらきっと早くなるのに。
555: 310 [sage] 2018/12/21(金) 00:04:37.10 ID:kvniGc89(1) AAS
いや。まぁ。バケットか中のレコードか、どちらかの単位で排他かけるだけです。
Hash関数がきちんとばらけさせてくれたら、基本的にあんまり排他で捕まる事は
無いので、それほど気にしなくてもパフォーマンスに影響ないかなぁと。実際に
concurrent_unordered_mapの配列用意して、適当にハッシュでばらけさせて格納
してみたら（つまり、同じmapじゃなければ排他はおきない）、排他で遅くなっている
訳ではない事が確認できています。
と言いながら、iteratorとか考えだすと、何を並列セーフにして、何をアンセーフに
するかみたいな事で悩んじゃいます。
先日の続きでmax_load_factorとかbacketサイズとかいじってみましたが、
パフォーマンスにほとんど影響がないです。というか、どうせ後で逐次的に拡張する
くらいならと、backetサイズを増やしても性能は上がらないし、max_load_factorを
増やしても、性能が落ちるだけだったり…。
棋譜作成だけなら並列化レベルをもう１段上げて、４記譜同時作成とかすれば、
個々の読み切りはシングルスレッドに下げられて、ただのunordered_mapが使えるし
その方が棋譜作成的には速度アップしそうな気がしてきた（汗
FFO的には別処理になるけど。
559: 310 [sage] 2018/12/26(水) 00:20:29.39 ID:Rkthqh0l(1/2) AAS
４記譜並列作成実装してみました。ただいま本番状態でテスト中。
並列処理の基本は、なるべく上位の層で並列化すべしでした。
現状、並列探索の速度は、シングル探索の２倍程度です。
１つ１つの探索には時間が2倍かかるけど、４つ並列なので、トータルでは
半分の時間で処理できるので、実質２倍みたいな。
探索中のオーバーヘッドはほぼ無いはずで、待ち合わせロスくらいなので、
大量に一気に処理する分には、ほぼ無視できるかなと。
これやると、スレッドの数がモロに効いてくるんで…４８並列くらいできたら…
562: 310 [sage] 2018/12/26(水) 03:07:45.74 ID:Rkthqh0l(2/2) AAS
あれれ。思ったほど速度が出ない…というか、単体の速度が半分どころか、
1/4くらいになっているイメージ…。深さが深いものほど遅いという事は、
置換表周りかなぁ。
棋譜作成する対象によって速度が結構変わるので、評価しづらい。
メモリー配置等の問題も考えないといかんような気がしてきた。
いかん。夜も更けていく…。
>>561なんか、フラッシュメモリー自体は書き込みが遅くて、SSDだとその辺を並列
化とかキャッシュとかで回避しているらしいです。USBメモリーは、その辺真面目
にやっているもの（高価）と、そうじゃないもの（安価）で差があるけど、それでも
SSDには敵わないとか。
564: 310 [sage] 2018/12/27(木) 00:00:43.02 ID:APLuuq5f(1/3) AAS
悩ましい。
シングルmin-Maxの並列動作と、パラレルmin-Maxのシングル動作。
どうも速度的には大差ない感じ。
２倍くらい速度出ると思ったのに…。
スレッド数が増えたら差が出てくるのかなぁ。
567: 310 [sage] 2018/12/27(木) 22:00:15.50 ID:APLuuq5f(2/3) AAS
色々あがいた挙句、そこそこ時間がかかる２６手空きを、それぞれで解いてみた。
並列探索で６分。シングル単独動作で１２分。シングル４並列動作で１８分。
やはり、シングルも４並列する事でなにがしかのオーバーヘッドがあるようです。
単純計算だと並列探索６分を４個で２４分に対して、シングル１８分で４つ解ける
事から３３％の速度アップが見込める事になるけど、体感そこまでの効果が感じ
られないというか、時間がかかる問題では更に差が大きくなっていて、そいつらに
足を引っ張られている印象。
そのうえで、裏でゴソゴソやりながら計算させる時に色々弊害があるので、
CPUの増強を決断するまで放置しようかと思います。
色々あがいた結果か、並列探索ですこーし速度アップした感じ。
１０％行くかいかないか。
569: 310 [sage] 2018/12/27(木) 23:06:53.59 ID:APLuuq5f(3/3) AAS
もちろんそうなんだけど、排他待ちを要するデータも、待ち合わせロスも
無いので、もうちょっと性能出るんじゃないかと思っていたのです。
あと、うまく説明できないけど、ノード数が多い探索は、ノード数比以上に
時間がかかっている気がしています。まだ感覚の話ですが。
571: 310 [sage] 2018/12/29(土) 09:40:46.33 ID:hnomLa8j(1) AAS
んー。シングル並列動作で６時間かかっても解けずに諦めた盤面とを見つけて、
パラレルで解いたら１時間４０分だった。空きマス２６だと通常１分程度なんだけど、
時々こういう時間がかかる盤面がある。今までテストが面倒なので、１０分以内に
終わりそうな奴でテストしていたけど、もしかしたら探索ノードが多い奴ほど、
シングル並列動作での速度低下が大きいのかも知れない。
時間がかかる奴ほど、シングル・パラレル比が悪化するなら、今考えている大体
３倍程度ってのは成り立たなくなって、もっと悪い事になる。それなら感覚的に
合致する。普通に流れている時には、シングル並列で高速化できそうな手ごたえ
があるんだけど、時間がかかる盤面が来ると急速に逼塞していって、なかなか
回復しないという感じ。
パフォーマンスモニタにらみながら、unordered_mapのメモリアロケーションの方法
を想像してみた。初期確保件数指定（倍々で自動追加される）してみたけど、溢れて
もいないのにダラダラとメモリー使用量が増えていく。もしかしたらOSにメモリーを
貰いに行く動作が排他待ちになっているのかも知れない。どうやって検証しよう。
やっぱ自前置換表作るしかないのかなぁ。
572: 310 [sage] 2019/01/01(火) 10:13:37.88 ID:y24geaJt(1) AAS
あけおめです。
ヒープをダラダラと確保するのが気になったので、色々いじりました。
ordering用のvectorを、配列にしてスタックに。ついでにクラス化してメンテ性アップ。
少しだけ速度アップした気がする。
自前ハッシュテーブル型の置換表を作ってみた。
最初に大きく領域確保して、溢れた時以外領域確保しないようにした。
基本、余計な機能は実装していないので、処理は軽いはずなんだけど…
極ほんの少しだけ速度ダウンした感じ…
記譜作成はunordered_map版で実行しながら、改良をしてみたいと思います。
とはいえ、ソース的にはあんまり改良の余地がないんだよなぁ。
速度がそん色ないところまで行けたら、シングル版の並列での速度低下が
メモリー確保が原因か検証できるかなぁ。
573: 310 [sage] 2019/01/05(土) 09:07:42.68 ID:KwyVlHZX(1) AAS
チェーン型でハッシュを組んでましたが、テーブルがあふれると結局ダラダラと
メモリー獲得し始めるので、オープンアドレス型に変更して、まとめて領域を追加
するようにしました。
この辺、もう趣味の世界ですね。
何をしても、速度は上がりも下がりもしない（汗
やっぱり探索ノードを減らす工夫が重要ですね。
581: 310 [sage] 2019/01/06(日) 14:23:08.43 ID:a93oWf/5(1/3) AAS
置換表一時調子が良かったのですが、修正加えたら崩壊。
なんとなく読み取りが変な感じなんだけど、どこがおかしいのか全くわからず。
>>578578(3): 名前は開発中のものです。 [sage] 2019/01/06(日) 03:01:38.94 ID:aGENq217(1) AAS
質の悪い棋譜ばかり100兆局集めてもあんまり強くならない気がするのですがどうなんでしょう
質のいい棋譜がそれだけ集まればいいですがそれはほぼ不可能ですし…
棋譜たくさん集めて序盤DB作ったら、その序盤DBのMax手順以外の手について
は、分岐した以後の盤面だけで学習させると序盤の穴が埋まるというか、間違った
盤面でぼやっとした学習するの避けられるかも。
今、序盤についてはそのやり方で学習させてます。
583: 310 [sage] 2019/01/06(日) 20:34:20.52 ID:a93oWf/5(2/3) AAS
オープンアドレスうまく動くようになりました。
ここに愚痴ると、直後に原因がわかる罠ｗ
この数日の葛藤は何だったんだ。
584(1): 310 [sage] 2019/01/06(日) 20:36:40.74 ID:a93oWf/5(3/3) AAS
>>582582(1): 535 [sage] 2019/01/06(日) 20:12:44.73 ID:6f3tqt5A(6/8) AAS
とりあえず、昔作ったTINY-DNNのプログラムを引っ張り出してきて学習プログラムを仮組したが絶望的に遅いorz
グラボ使えればちっとは違うんだろか？うーむ。
Tiny-DNNはGPU対応していないんじゃないかなぁ。
結局、DCNNはGPUで処理しないと無理っつー気がする。
590: 310 [sage] 2019/01/09(水) 20:33:25.82 ID:9GUGdavc(1/2) AAS
学習の速度はオプティマイザに依存します。
普通のSGDだと、あちこちぐるぐる回ったり、平野トラップで立ち往生したり、
局所最適解から抜け出せなくなったり。また、SGDは学習率（α）を大きくすると、
簡単に発散しちゃったりしますので、学習率を低めにして１０００回とか学習する
事になります。それでも上記の問題で、なかなか収束しなかったり、うまく学習
できなかったりします。
そういうものなのです。昔は、初期値（乱数設定しているはず）を変えてみたりして
トライ＆エラーしてましたが、今なら別のオプティマイザ（RMSpropやADAM）を試す
べきかと思います。それでも数百回は学習を繰り返さないといけないと思います。
久々に検索したら結構種類が増えてた。
外部ﾘﾝｸ:qiita.com
自分は線形回帰モデルですが、SMORMS3を使って効率化を図っています。
それでも、数百回学習しないと損失は落ち着いてきません。
591: 310 [sage] 2019/01/09(水) 22:31:13.85 ID:9GUGdavc(2/2) AAS
置換表ですが、結局のところ、ハッシュのビット数を増やしてチェーン接続があまり
生じないようにし、メモリーをある程度のサイズでまとめて確保する、チェーン型
ハッシュに落ち着いています。
普段速度計測に使っているFFO#40-49ではconcurrent_unordered_map版より若干
遅いのです。が、どうも残り２８手（現在はそのあたりをチェック中）では、自作チェーン
ハッシュの方が早いというか、ノード数が増えた時に速度低下が少ないように感じて
おり、現在は自作置換表を使っています。
とはいえ、２９手や３０手まで行った暁にはチェーン接続が多発し始めて速度低下が
始まると思われるので、対策を考えて行きたいと思います。２８手が終わるまでまだ
一カ月くらいかかるので、幸か不幸か時間はたっぷりあります(--;
今のところチェーンの代わりに２分木を置いて、ハッシュが衝突したときの速度低下を
O(n)からO(log(2)ｎ)にしてみようかと考えています。
601: 310 [sage] 2019/01/18(金) 00:47:06.53 ID:YI61Q9H1(1) AAS
NN系は学習してるんだかわからない時があるよね。
とことんまで回すと今度は過学習も怖くなってくるし。
こちらは、自作concurrent_mapクラスができました。
ハッシュキーは二分木で、ハッシュ値は64bit。
配列ハッシュキー版と同様に、削除もiteratorも無し。
すこーし速度があがったかなぁ程度。
衝突時の処理はチェーン式。流石に64bitだとキーの衝突が無い。
棋譜訂正は時間がかかるので、暇つぶしが必要な状態。
二分木を赤黒木に変えてみようかと思い始めています（汗。
本当はヒューリスティックスの改良の方が効果あるんだろうなぁ。
603: 310 [sage] 2019/01/19(土) 09:03:58.77 ID:/dbSBJQm(1) AAS
赤黒木を検討してますが、これ並列処理だと木全体をロックしないと
いかんのではないかと…。置換表のように追加の頻度が高いケース
では、排他待ちでパフォーマンス出ないかも。
まあ、やってみるしかないけれど。
616: 310 [sage] 2019/01/22(火) 00:34:53.58 ID:9pySCUmT(1) AAS
赤黒木大体できたけど…ただの二分木よりほんの少し遅い…。
元々ハッシュでランダマイズしているから、二分木の末端ノードまでの深さは
綺麗な正規分布になっていて、赤黒木にしても木の最頻高さで３割程度しか
小さくならないという事で、ツリーを修正するオーバーヘッドが効いているのか、
それとも木全体でしか排他できないのが原因なのか。
もうちょっと調べてから諦めます。
621: 310 [sage] 2019/01/23(水) 01:56:46.43 ID:QHWWUXAJ(1/2) AAS
置換表に使ってるので要素数は現在残り２８手で１００万超える事もあります（汗
まあ、βカットの具合でだいぶ変わるので、学習進むと減るんですが。
最低でも残り３０手まで行くつもりなので、１０００万くらいは想定したいです。
次の一手ソート用の配列は、Array型にしています。３２個確保すれば足ります。
こちらも比較したところ、明確に速度差がありました。この辺から、領域をチマチマ
確保されるオーバーヘッドが気になりだした次第です。
で、赤黒木ですが、実装が悪いのだと思いますが、現時点で２分木と比較して
およそ３倍時間がかかります。シングル動作でも同じくらいの差になるので、
排他待ちではなく、木のつなぎ替え処理の重さが原因かなと。置換表は追加が
の比率が大きいので、ポインタたどるロスは優位ではない感じ。
というわけで、赤黒木はちょっと放置。
というか、二分木もシングル動作は１０倍くらい速い感じなので、今一度シングル
探索の並列化を試そうと思っています。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.065s