【オセロ,将棋】ボードゲーム Part2【囲碁,War】
■ このスレッドは過去ログ倉庫に格納されています
比較的地味なボードゲーム専用のスレが欲しくて立ててみました。
前スレ
【オセロ,将棋】ボードゲーム【囲碁,War】
http://mevius.2ch.net/test/read.cgi/gamedev/1057763418/ よくわからんがハイパースレッディングって単純に性能2倍になるわけではないということではなくて? もちろんそうなんだけど、排他待ちを要するデータも、待ち合わせロスも
無いので、もうちょっと性能出るんじゃないかと思っていたのです。
あと、うまく説明できないけど、ノード数が多い探索は、ノード数比以上に
時間がかかっている気がしています。まだ感覚の話ですが。 LV3は強いんだけど詰み状態から詰みを逃してる棋譜が散見される。
直せるもんなら直したほうがいいんだろうけどかなり大変だろうな んー。シングル並列動作で6時間かかっても解けずに諦めた盤面とを見つけて、
パラレルで解いたら1時間40分だった。空きマス26だと通常1分程度なんだけど、
時々こういう時間がかかる盤面がある。今までテストが面倒なので、10分以内に
終わりそうな奴でテストしていたけど、もしかしたら探索ノードが多い奴ほど、
シングル並列動作での速度低下が大きいのかも知れない。
時間がかかる奴ほど、シングル・パラレル比が悪化するなら、今考えている大体
3倍程度ってのは成り立たなくなって、もっと悪い事になる。それなら感覚的に
合致する。普通に流れている時には、シングル並列で高速化できそうな手ごたえ
があるんだけど、時間がかかる盤面が来ると急速に逼塞していって、なかなか
回復しないという感じ。
パフォーマンスモニタにらみながら、unordered_mapのメモリアロケーションの方法
を想像してみた。初期確保件数指定(倍々で自動追加される)してみたけど、溢れて
もいないのにダラダラとメモリー使用量が増えていく。もしかしたらOSにメモリーを
貰いに行く動作が排他待ちになっているのかも知れない。どうやって検証しよう。
やっぱ自前置換表作るしかないのかなぁ。 あけおめです。
ヒープをダラダラと確保するのが気になったので、色々いじりました。
ordering用のvectorを、配列にしてスタックに。ついでにクラス化してメンテ性アップ。
少しだけ速度アップした気がする。
自前ハッシュテーブル型の置換表を作ってみた。
最初に大きく領域確保して、溢れた時以外領域確保しないようにした。
基本、余計な機能は実装していないので、処理は軽いはずなんだけど…
極ほんの少しだけ速度ダウンした感じ…
記譜作成はunordered_map版で実行しながら、改良をしてみたいと思います。
とはいえ、ソース的にはあんまり改良の余地がないんだよなぁ。
速度がそん色ないところまで行けたら、シングル版の並列での速度低下が
メモリー確保が原因か検証できるかなぁ。 チェーン型でハッシュを組んでましたが、テーブルがあふれると結局ダラダラと
メモリー獲得し始めるので、オープンアドレス型に変更して、まとめて領域を追加
するようにしました。
この辺、もう趣味の世界ですね。
何をしても、速度は上がりも下がりもしない(汗
やっぱり探索ノードを減らす工夫が重要ですね。 自己対戦のみで強くなるアルファゼロは理想ですが実装が難しそうなので
せっかく棋譜も集めてるので教師あり学習をやってみようかと思案中。 とりあえず、棋譜データからmin-max探索して黒有利の局面か白有利の局面かの2択を学習させようかな。とか思ってます。
そろそろ寝るか。。。 寝るタイミングを逸してしまったw
プログラミングってこれがあるから怖いよねw なんか100兆局くらい棋譜を集めると序盤DBだけでもかなり押せるんじゃないかなぁ。
そんな感じ。
いかん、寝なければww 質の悪い棋譜ばかり100兆局集めてもあんまり強くならない気がするのですがどうなんでしょう
質のいい棋譜がそれだけ集まればいいですがそれはほぼ不可能ですし… そうはいってもLV3の棋力はかなり高い。
囲碁将棋でいえばアマチュア3段くらいには相当するはず。 波があるからアマチュア3段は言い過ぎだったかなw
でもまあ強い時はかなり強い。 置換表一時調子が良かったのですが、修正加えたら崩壊。
なんとなく読み取りが変な感じなんだけど、どこがおかしいのか全くわからず。
>>578
棋譜たくさん集めて序盤DB作ったら、その序盤DBのMax手順以外の手について
は、分岐した以後の盤面だけで学習させると序盤の穴が埋まるというか、間違った
盤面でぼやっとした学習するの避けられるかも。
今、序盤についてはそのやり方で学習させてます。 とりあえず、昔作ったTINY-DNNのプログラムを引っ張り出してきて学習プログラムを仮組したが絶望的に遅いorz
グラボ使えればちっとは違うんだろか?うーむ。 オープンアドレスうまく動くようになりました。
ここに愚痴ると、直後に原因がわかる罠w
この数日の葛藤は何だったんだ。 >>582
Tiny-DNNはGPU対応していないんじゃないかなぁ。
結局、DCNNはGPUで処理しないと無理っつー気がする。 >>584
あ〜やっぱそうなんですかねぇ。
GPUも結構いいの買ったのでぜひ活用したいところではあります。 明日は仕事なのでハマらないうちに切り上げようww
社会人として自制しなければwww 学習回しても損失が全く減らない。。。
そういやそんなのあったな。orz なんかネットワーク初期化忘れてたみたいw
初期化したら損失減ったw
ちょっと希望が出てきた。 損失減ることは減るんだけどホントにちょっとづつしか減っていかない。
ネットワークの形状が悪いんだろうか?学習率だろうか?
うーん、深みにはまりそうorz 学習の速度はオプティマイザに依存します。
普通のSGDだと、あちこちぐるぐる回ったり、平野トラップで立ち往生したり、
局所最適解から抜け出せなくなったり。また、SGDは学習率(α)を大きくすると、
簡単に発散しちゃったりしますので、学習率を低めにして1000回とか学習する
事になります。それでも上記の問題で、なかなか収束しなかったり、うまく学習
できなかったりします。
そういうものなのです。昔は、初期値(乱数設定しているはず)を変えてみたりして
トライ&エラーしてましたが、今なら別のオプティマイザ(RMSpropやADAM)を試す
べきかと思います。それでも数百回は学習を繰り返さないといけないと思います。
久々に検索したら結構種類が増えてた。
https://qiita.com/ZoneTsuyoshi/items/8ef6fa1e154d176e25b8
自分は線形回帰モデルですが、SMORMS3を使って効率化を図っています。
それでも、数百回学習しないと損失は落ち着いてきません。 置換表ですが、結局のところ、ハッシュのビット数を増やしてチェーン接続があまり
生じないようにし、メモリーをある程度のサイズでまとめて確保する、チェーン型
ハッシュに落ち着いています。
普段速度計測に使っているFFO#40-49ではconcurrent_unordered_map版より若干
遅いのです。が、どうも残り28手(現在はそのあたりをチェック中)では、自作チェーン
ハッシュの方が早いというか、ノード数が増えた時に速度低下が少ないように感じて
おり、現在は自作置換表を使っています。
とはいえ、29手や30手まで行った暁にはチェーン接続が多発し始めて速度低下が
始まると思われるので、対策を考えて行きたいと思います。28手が終わるまでまだ
一カ月くらいかかるので、幸か不幸か時間はたっぷりあります(--;
今のところチェーンの代わりに2分木を置いて、ハッシュが衝突したときの速度低下を
O(n)からO(log(2)n)にしてみようかと考えています。 ふーむ。要素が少ない時はリストやツリーは遅く、配列が圧倒的に早いという認識でしたが。 あれ、序盤DBに棋譜を追加したら全然おかしな手を打つようになっちゃった。
棋譜がまずいのかな? くそ〜強いAI(自我があるとかではないよ)作りてぇなぁ 三連休とはいえそろそろ寝なければな。
生活のリズム崩すのはいくない。 質にばらつきのある棋譜から良いデータを抽出する方法はあるのだろうか? うーんせっかく3連休なのに捗らないな。
これだというアイディアが湧くまでこねくり回すしかないか。 結局アルファゼロという正解がある限りその呪縛から逃れるのはかなり難しいorz
うーん。 やっぱグラボも活用したいなぁ。
でも難しいんだよなぁ。
とくにウィンドウズだと。 昨日一日学習回して損失が初期値の2/3位になった。
この辺が限界かなぁ
それともぞうきんを絞るようにまだまだ損失減るんだろうか? NN系は学習してるんだかわからない時があるよね。
とことんまで回すと今度は過学習も怖くなってくるし。
こちらは、自作concurrent_mapクラスができました。
ハッシュキーは二分木で、ハッシュ値は64bit。
配列ハッシュキー版と同様に、削除もiteratorも無し。
すこーし速度があがったかなぁ程度。
衝突時の処理はチェーン式。流石に64bitだとキーの衝突が無い。
棋譜訂正は時間がかかるので、暇つぶしが必要な状態。
二分木を赤黒木に変えてみようかと思い始めています(汗。
本当はヒューリスティックスの改良の方が効果あるんだろうなぁ。 赤黒木を検討してますが、これ並列処理だと木全体をロックしないと
いかんのではないかと…。置換表のように追加の頻度が高いケース
では、排他待ちでパフォーマンス出ないかも。
まあ、やってみるしかないけれど。 赤黒木とかめっちゃむずかしいやつですやん。
さすがですな。 ん、なんか学習したネットワークがすべてのデータに対して同じ結果を返してるっぽい? 学習開始時のネットワークの重みの初期化をミスってるんだろうか
うーん。 tiny-dnn以外のGPU使えるライブラリで重みだけ学習してアプリケーションからはtiny-dnnを使うというのもあるのだろうか 全く同じ結果ではなく微妙に違う結果を返してるのは確認できたけど。
単に学習量がたりてないのかなぁ。 やっぱり全く同じ結果返してる??
混乱してきたorz 層が多すぎたのが悪かったみたい?
層減らしたら違う値になった。 お、LV1に勝った!
まあDNNの学習の効果の勝利というよりも序盤DBと詰みルーチンの補助による勝ちなんだけどね。
でもとりあえず、それっぽく動くところまで来ました。 序盤DBが良すぎてDNNの真価がわからないから序盤DB外してみるか… やっぱ序盤DBに頼るか…
こんなにプログラムが楽しいの久しぶりやな たぶんだけどまだまだ棋譜増やしたほうがいい。
ていうかあればあるほどいいい。まだまだ良くなる。
可能なら100万局を目指したい。 赤黒木大体できたけど…ただの二分木よりほんの少し遅い…。
元々ハッシュでランダマイズしているから、二分木の末端ノードまでの深さは
綺麗な正規分布になっていて、赤黒木にしても木の最頻高さで3割程度しか
小さくならないという事で、ツリーを修正するオーバーヘッドが効いているのか、
それとも木全体でしか排他できないのが原因なのか。
もうちょっと調べてから諦めます。 要素が100個未満ならぶっちゃけvectorでいいと思いますが。。。 前も同じこと言ったような気がするけど、学習させるなら局面の勝率より次の一手のほうがいいのだろうか? いまきたんですがここはどんなゲームを開発してるんですか
じぶんで開発したとして対戦相手=プログラムありますか >>619
とりあえず、落ち着いて。
過去ログから読んでください。 置換表に使ってるので要素数は現在残り28手で100万超える事もあります(汗
まあ、βカットの具合でだいぶ変わるので、学習進むと減るんですが。
最低でも残り30手まで行くつもりなので、1000万くらいは想定したいです。
次の一手ソート用の配列は、Array型にしています。32個確保すれば足ります。
こちらも比較したところ、明確に速度差がありました。この辺から、領域をチマチマ
確保されるオーバーヘッドが気になりだした次第です。
で、赤黒木ですが、実装が悪いのだと思いますが、現時点で2分木と比較して
およそ3倍時間がかかります。シングル動作でも同じくらいの差になるので、
排他待ちではなく、木のつなぎ替え処理の重さが原因かなと。置換表は追加が
の比率が大きいので、ポインタたどるロスは優位ではない感じ。
というわけで、赤黒木はちょっと放置。
というか、二分木もシングル動作は10倍くらい速い感じなので、今一度シングル
探索の並列化を試そうと思っています。 >>618
min-Max前提だと、探索値を求める際には勝率(点数)が必須で、
次の1手評価関数はオーダリングや前方枝刈向きではないですか?
探索深さ1なら次の1手で行けますが。
初代アルファ碁も、両方組み合わせていますが、次の1手評価関数で
手の優先順位をつける事で読み深さを実現した変則mctsで、最終的には
評価値で判断していますよね。 ふーむ、勝率のほうが応用が利くってことですかね?
もうしばらく勝率で学習させてみます。 ついネットワークを大きくしたくなっちゃうけど。
本当は小さいネットワークでエポック数を稼いだほうがいいのかもしれない。 そういえば、対称局面も学習データとして使ったほうがいいんでしたっけ? 囲連星は初期配置ないんでしょ?
だったら対象局面ありの方が良いと思う。
オセロは悩み中。
初手をF5固定にした時に、本当に対称局面が出てくるのかわからない。
対称局面が同じ重要性で生じないのであれば、評価値を希釈しちゃうだけ。
学習の時間も単純に倍々で増えるので、今はやっていない。
強いて言うなら、F5F6E6の次がF4とD6で斜め対称になるので、ここだけは
記譜作成時にはF4固定にして、D6の対称局面を作っている。 置換表自作の件、目的を見失っている(汗
一旦リセットして、最初からやり直して、当初の目的に戻ろうと思うorz 私は教師データの数が8倍になるのは大きいと思って対称局面も入れて学習させてます
とくにDeep Learningさせてると(ネットワークの規模にもよりますが)だいぶ過学習しなくなります
もっとも、Deep Learningするんだったら対称性を考慮したネットワークにしたほうがいいのかもしれないですが・・・ 着手できる場所の自由度が高いゲームは回転させるべきだと思う。
オセロは着手可能場所が限られるので、現れない局面が結構ありそう。
ちなみに、オセロは8倍じゃなくて4倍。初期配置が4対称だから。
囲連星は初手天元固定なのかな? >オセロは8倍じゃなくて4倍
たしかに棋譜で考えると4対称しか無いですね
今のところ、学習させるときには現局面しか渡してないので、
90度回転で一致する局面が存在するかもしれないから8倍で良いはず… うーん。今のやり方だとLV0やLV1とはいい勝負になるけどLV3には一生勝てないかも?
出来れば自己対戦による強化学習とか取り入れたいな〜
対称局面もやってみますね。 なんか長時間計算回してると画面が真っ暗になってマウスやキーボード押しても復帰しないことがあるんだが?
スリープは解除してるはずなんだけどなんなんだろう? LV0ってやっぱ棋力低いな。
そんなLV0といい勝負の俺のAIもあれだけど。
やればやるほどLV3の完成度の高さが際立つ。 自作置換表ですが、大体のところがまとまりました。
結局のところ、unordered_mapを作っていた形になります(汗
当初は領域の追加について、データ部分をまとめて追加する方向で改造し、
ハッシュ配列については22ビット固定で、高速化をしました。で、ハッシュ配列が
22ビット固定は芸がないと、二分木・赤黒木などを試しましたが、速度大幅低下。
要するに、unordered_mapにmapを組み合わせて、ハッシュのメリットを相殺して
しまっていたという事で。
最終的に、ハッシュ配列の追加方法をようやく思いつき、組んでみたところ、それが
そのままunordered_mapのrehashだと気が付きました(汗。その後、max_load_factor
などを追加して、unordered_mapと条件を揃えて速度比較となりました。
iteratorと削除が無い分だと思いますが、unordered_map、concurrent_unordered_map
に対して、それぞれシングル版、concurrent版とも若干高速になりました。
新たな課題は…stlも自作版も、どちらも並列に動かしたconcurrent版の方が遅いと
言う事です。もともとそういうものなのか…テスト方法が並列向けじゃないのか。 8対称はメモリがやばいので4対称にします。
4対称で16GB位食ってる。 思い切っていいPC買ったけどまだ足りないとかorzorzorz
ケチらず64GB積むべきだったか? 1エポック4539秒
これは厳しいorzorzorz
GPUが使えれば… ん、1エポック目だけど損失がかなり少ない。。
対称局面を入力とすることで特徴量がよりはっきりしたということだろうか? 対称局面学習以前はどちらかというとランダムに近かったが
対称局面学習以後はどちらかというと知性があるっぽく見える。
まだわからんが。 これでエポックが進めばとんでもなく強くなる?
まだわからんが。 マシンパワーが欲しい!
Googleに匹敵するマシンパワーが! まだLV3には遠く及ばないな。
でも希望が出てきた。 学習用、棋譜採取用、対戦統計用、開発用で4台マシンほしいw やっぱ思考時間短いのはいいな。
モンテカルロは強いけど思考時間長すぎたからな。 棋力が低すぎてすさまじい泥仕合になるの切ないorz メモリがもっとあれば異なるネットワークを並列に学習とかもできたかもなぁ
まさか32GBで足りないとは… DNNの評価値とMM法の評価値の和で最終評価値を算出するようにしてみました。
多分DNNのみより強くなってます。 黒番で軽く動かしてみました。
10局目
黒(airandom.dll)の勝利回数: 8
白(ai-lv1.dll)の勝利回数: 2
まずまずの結果かな。
ちなみに白番はうまく動いてなくて1の1とか打っちゃうので途中で中断しました。 うお、猛烈に追い上げられてるorz
悪くない手ごたえがあったと思いましたが…
25局目
黒(airandom.dll)の勝利回数: 15
白(ai-lv1.dll)の勝利回数: 10 ちょっとヒューリスティックを入れました。
詰めろがあるときは詰めろを優先的に打つ。
当たりの点数を恣意的に上げる。 うおお、キター
DNNでLV3に初勝利!
(;SZ[19]
;B[jj];W[kj];B[ji];W[jk];B[kk];W[kl];B[lk];W[ih]
;B[li];W[mj];B[lj];W[kh];B[ki];W[mi];B[lh];W[ll]
;B[lg];W[lf];B[kf];W[ik];B[le];W[mf];B[jh];W[mk]
;B[ke];W[ml];B[kj];W[kg];B[jg];W[mh];B[mg];W[mm]
;B[mn];W[kd];B[kh];W[ld];B[kg])
対LV1も流しなおしててこんな感じ
24局目
黒(airandom.dll)の勝利回数: 18
白(ai-lv1.dll)の勝利回数: 6 ついDNNの学習に計算リソースを使いたくなっちゃうけど
ぐっとこらえてすべての源泉である棋譜取りにリソースを回すのが正解かも? いやーこんなに充実してるの久しぶりだな。
長いトンネルを抜けたようだ。 うお、またLV3に勝った!
まだまだ負け越すだろうけど、偶然の勝利じゃないってことか。
(;SZ[19]
;B[jj];W[ik];B[ii];W[jk];B[kk];W[lk];B[ll];W[kj]
;B[kl];W[hh];B[mm];W[ji];B[ij];W[ih];B[nn];W[oo]
;B[jm];W[ml];B[hg];W[hk];B[om];W[lm];B[ln];W[nl]
;B[nm];W[im];B[pm];W[km];B[kn];W[pp];B[km];W[qp]
;B[lm]) 明日は仕事だから夜更かしは社会人として自制しなければwwwww
そろそろ切り上げるかwwww そういえば赤黒木って深さキャッシュして置くんですか?オーダーlogで深さを求める方法が思いつかない 長連判定入れなかったのが意外と響いてるな。
ちょくちょく長連に引っかかる ん、DNN学習の裏で棋譜取りしたら計算速度落ちてるな。
コア数は足りてるはずだがメモリ帯域が足を引っ張ったのだろうか? こちらの棋力が上がるのに呼応するようにLV3も素晴らしい手を返してくる。
奥が深いすな。 LV3との対戦統計とってみたいけどまだ時期尚早かな。
まずは大量の棋譜を手に入れる。
量が質に転換する地点が必ずあるはず。 将来的には自己対戦による強化学習は絶対取り入れたい。 今一手読みで打ってるから、3手読みとかモンテカルロか入れたらもちっと改善するかな?
でも計算量がどうなるかだなぁ。
遅いのはコリゴリ。 とりあえず2手読みにしてみたけど2手読みが限界かなぁ
3手は計算量的に相当厳しそう。 2手読み、なかなかいい感じ。
1手読みから明らかにうち筋が良くなっている。
もし3手読みにしたら… 3手読みを仮組してみました。
計算時間がやばいので前方枝刈で思いっきり枝刈してます。 あああ、惜しいなぁ!
今すごくいい勝ち方しそうだったのに!
(;GM[1]FF[4]AP[Zenith:7.0]SZ[19]HA[0]KM[6.5]CA[UTF-8]PB[]BR[]PW[]WR[]
ZT[60]DT[]RE[];B[jj];W[ik];B[kk];W[hj];B[ii];W[jk];B[ll];W[hh];B[mm];
W[nn];B[hi];W[gi];B[jl];W[hl];B[ki];W[km];B[lh];W[mi];B[kg];W[kl];B[ke];
W[kf];B[jf];W[lf];B[jd];W[ie];B[je];W[ig](;B[jg];W[jh];B[ih];W[ji];B[kh];
W[jh];B[ji];W[gg];B[jh])(;B[kh];W[jg];B[ih];W[gg];B[nm];W[gk];B[fh];W[gh];
B[gj];W[fj];B[gl];W[ek];B[fk];W[fl];B[mk];W[gm];B[mh];W[gl];B[jh];W[gj]))
もしこの勝ち方ができてたら瞬間最大棋力は名人に届く、ってくらいすごかった。 ■ このスレッドは過去ログ倉庫に格納されています