【オセロ,将棋】ボードゲーム Part2【囲碁,War】

**名前は開発中のものです。** · 2017/10/15(日) 17:34:58.03

比較的地味なボードゲーム専用のスレが欲しくて立ててみました。

前スレ
【オセロ,将棋】ボードゲーム【囲碁,War】
http://mevius.2ch.net/test/read.cgi/gamedev/1057763418/

**535** · 2018/12/02(日) 21:28:29.33

>>535
その手がありましたねｗｗ
作業中は１２プロセス位にしとくか

なにはなくとも棋譜取りだけはコツコツつづけます。
一日で多分３～４０００局くらい取れるはず。

ちなみに今これ見てるけど速攻挫折しそうorz
https://github.com/HerveFrezza-Buet/RLlib

**535** · 2018/12/03(月) 20:43:08.98

一日回して4652局
思ったより取れてる。

**535** · 2018/12/03(月) 23:14:26.77

平日まとまった時間が取れなくてもちょっとづつでも進んでいかないとねぇ。
まあ、棋譜取りしてるだけでもいくらか気がまぎれるけど。
１００万局目指すか。

**535** · 2018/12/08(土) 23:40:47.79

RLlibやっとサンプルがコンパイルできた
ここまで長かった
つかリンクオプションで-lgslつけなきゃいけないとかずっぽり嵌ったわ

**310** · 2018/12/09(日) 13:20:20.42

まったりと記譜取りしてても仕方ないので、速度アップできないか色々あがいてました。

久々にプロファイラで確認したところflip関数が３０％、mobility関数が８％ほどでした。
Edaxのソース見つけたので禁断の答え合わせ。flip関数は一つ昔のタイプなので、
恐らく自分の方が早い。mobilitiy関数は少し早そうなので、考え方を導入。でも誤差
範囲の効果しかなかった。

速度計測ルーチンを作って、並列単体速度比が１．２程度しか無い事が判明。
並列処理で排他待ちしそうなところに無駄がないかチェックしたところ、ほぼ全部無駄
だった事が判明（汗。無駄箇所を全て削除したけど、誤差範囲（汗

後方枝刈（ヒューリスティックスなオーダリング）が気になるので、ノード採取してみた。
やはり２割程度速度ダウンするので、プリプロセッサで普段は切り離す事に。

その他もろもろ誤差範囲の改良を積み上げた結果、なんとなく１～２割は速度アップ
した気がしますが、並列処理の効率が悪いのと、後方枝刈の工夫が足りていないの
２か所が、これからの課題かなと思います。

あれ？なんか、ループしてmin-Max探索の高速化に目的が戻ってきている（笑）

**535** · 2018/12/09(日) 15:16:13.02

んあ？RLlibって強化学習のライブラリではあるけどalpha zeroとは直接関係ないのか？
全部無駄だった？
www

**535** · 2018/12/09(日) 20:10:15.58

ふらふら浮気しまくりｗｗ
浮き草のような人生だ。

今これ見ようとしてます。
https://github.com/novoselov-ab/ai-zero

**535** · 2018/12/09(日) 21:08:44.25

g++ にfilesystemってヘッダがないorz
とりあえずいまVSインストールしてる

**535** · 2018/12/09(日) 21:40:01.98

動いたっぽい。
久しぶりに一歩進んだ気分。

**535** · 2018/12/10(月) 22:15:43.67

なんか非合法手を選んでしまうみたいなんだが？
うーんなんだろ？

**535** · 2018/12/12(水) 22:24:55.51

他人のコードに頼るのやめて自力実装に走るべきだろうか？
他人のコードってなによりいまいち情熱が湧いてこない。

でも他人のコードも読めるようにならないと先はないんだろうなぁ。
我流じゃすぐ限界迎えそう。

悩ましい。

**535** · 2018/12/14(金) 00:02:46.12

まただよ（再起動）
windows10でも変わらずか…

**535** · 2018/12/14(金) 22:52:23.39

コーディングは進まないけど棋譜だけは溜まっていきます。
今、LV3 vs LV3の棋譜が61950局分溜まってます。
ファンがうるさいから夜中は回してないから日中だけなのにこのペース。
8コアはさすがといったところか。
アルファ碁Leeが16万局分の棋譜を使ったらしいからとりあえずその辺目指すか。

**310** · 2018/12/18(火) 00:10:23.05

FFOテスト（#40－#49）、色々誤差範囲の改良を加えてじわじわスピードアップ
していたけど、ある日突然２０％くらい悪化。元に戻せるところは戻したけど、
結局ダメで、裏で評価関数の学習し続けた結果、途中経過でたまたま探索が
悪化するところにはまってしまったと言う事かなぁと。

実際、悪化しているの#49だけで他は改善していたし、学習都度表示している
FFO問題の８手読みの次の一手の合否が、14/20から11/20に悪化している。

こういうのあると、速度アップで何を信じて良いのかわからなくなるよね…

**310** · 2018/12/18(火) 00:14:29.31

という問題もありながら、ノード数表示して、>>492さんの結果と比較すると、
ノード数に圧倒的な差が。NPSは速いけど、それ以上にノード数が多い。
枝刈の差というにはあまりに大きな差で、一桁近い差です。

これ、Iterativeな手法で生じる置換表探索の差じゃないかと思う。
自分のは置換表の動作が遅いので、あまり深い探索まで置換表を適用できず、
読切において後ろの方は置換表が無い（そもそも使用していない）事で、何度も
再探索しているからかなと。

concurrent_unordered_mapを使っているけど、自前でハッシュDB作った方が
良いかもと思い始めた。そこで速度アップすると、置換表適用深度を深くできる。

こういう時、自前で作る人はチェーンハッシュ使っているのかな？

**535** · 2018/12/18(火) 23:29:10.84

昔自前でハッシュ作ったことありますが素朴な実装だとさほど性能出なかった記憶がありますね。
自分の場合STLでいいじゃんみたいな結果でした。
テーブルのサイズをでかくすると意外と巡回が遅くなるみたいな。

**535** · 2018/12/19(水) 21:16:40.83

スマホでconnect4のパーフェクトソルバーをちょくちょく遊んでるのですが
パターンをかなり覚えて７割くらい勝てるようになりました
囲碁とかも真の棋理が明らかになった方が
逆に人間がコンピュータに勝てるようになるかもしれませんね

**310** · 2018/12/19(水) 22:48:18.33

ハッシュの構想し始めましたが、確かに自分が作って早くなる保証はないですね。
インターフェースを既存のstlに合わせようとか思って調べ始めたら面倒になりました。

で、色々見ていたら、そのまんま効率化できそうな使い方を見つけた。
有れば読み込んで更新、無ければ追加の方法です。

あとバケットサイズとか個数とか、その辺を調べていった方が早くなるかも。

並列処理だとtry_emplaceが使えないのね。これが使えたらきっと早くなるのに。

**535** · 2018/12/20(木) 23:32:19.98

また再起動してる。。。
まあいいけど、もう諦めぎみ。

なんか仕事が急に忙しくなってますますコーディングから遠ざかってますが、
棋譜だけは地味に溜まってます。今82889局分溜まってます。

並列化ハッシュってどんななんですかね。そういえば知らない。

**310** · 2018/12/21(金) 00:04:37.10

いや。まぁ。バケットか中のレコードか、どちらかの単位で排他かけるだけです。
Hash関数がきちんとばらけさせてくれたら、基本的にあんまり排他で捕まる事は
無いので、それほど気にしなくてもパフォーマンスに影響ないかなぁと。実際に
concurrent_unordered_mapの配列用意して、適当にハッシュでばらけさせて格納
してみたら（つまり、同じmapじゃなければ排他はおきない）、排他で遅くなっている
訳ではない事が確認できています。

と言いながら、iteratorとか考えだすと、何を並列セーフにして、何をアンセーフに
するかみたいな事で悩んじゃいます。

先日の続きでmax_load_factorとかbacketサイズとかいじってみましたが、
パフォーマンスにほとんど影響がないです。というか、どうせ後で逐次的に拡張する
くらいならと、backetサイズを増やしても性能は上がらないし、max_load_factorを
増やしても、性能が落ちるだけだったり…。

棋譜作成だけなら並列化レベルをもう１段上げて、４記譜同時作成とかすれば、
個々の読み切りはシングルスレッドに下げられて、ただのunordered_mapが使えるし
その方が棋譜作成的には速度アップしそうな気がしてきた（汗

FFO的には別処理になるけど。

**535** · 2018/12/22(土) 00:08:33.74

採りためた棋譜をもとに序盤DBを更新してみましたが、
確かにうち筋は変わってる気がしますが強くなってるかはよくわからないというorz
まあ序盤DBは誤魔化しみたいなものだから期待しすぎもよくないか。

**535** · 2018/12/22(土) 00:42:25.73

序盤DB更新で強くなってるか統計とってみたいけどモンテカルロが遅すぎてそれもままならないというorz
やはりモンテカルロに代わる何かを実装しなければ…

**535** · 2018/12/26(水) 00:12:59.86

棋譜USBメモリにコピーしたらめっちゃ時間かかるorz
１３０MBくらいなのにUSBメモリってやっぱ遅いんだな。

**310** · 2018/12/26(水) 00:20:29.39

４記譜並列作成実装してみました。ただいま本番状態でテスト中。
並列処理の基本は、なるべく上位の層で並列化すべしでした。

現状、並列探索の速度は、シングル探索の２倍程度です。
１つ１つの探索には時間が2倍かかるけど、４つ並列なので、トータルでは
半分の時間で処理できるので、実質２倍みたいな。

探索中のオーバーヘッドはほぼ無いはずで、待ち合わせロスくらいなので、
大量に一気に処理する分には、ほぼ無視できるかなと。

これやると、スレッドの数がモロに効いてくるんで…４８並列くらいできたら…

**535** · 2018/12/26(水) 00:30:44.15

310さんはintel派なんでしたっけ？
AMDでもzen2はかなりコスパいいものが来ると思いますが…

**535** · 2018/12/26(水) 00:40:17.50

試しにSSDに棋譜コピーしてみたらかなり速いｗ
やっぱそうなのか。

**310** · 2018/12/26(水) 03:07:45.74

あれれ。思ったほど速度が出ない…というか、単体の速度が半分どころか、
1/4くらいになっているイメージ…。深さが深いものほど遅いという事は、
置換表周りかなぁ。

棋譜作成する対象によって速度が結構変わるので、評価しづらい。

メモリー配置等の問題も考えないといかんような気がしてきた。

いかん。夜も更けていく…。

>>561
なんか、フラッシュメモリー自体は書き込みが遅くて、SSDだとその辺を並列
化とかキャッシュとかで回避しているらしいです。USBメモリーは、その辺真面目
にやっているもの（高価）と、そうじゃないもの（安価）で差があるけど、それでも
SSDには敵わないとか。

**535** · 2018/12/26(水) 21:06:48.31

明日か明後日あたりで棋譜１０万局分溜まりそう
深層学習のプログラム、組みたいなぁ
でも難しいんだよなぁ

**310** · 2018/12/27(木) 00:00:43.02

悩ましい。

シングルmin-Maxの並列動作と、パラレルmin-Maxのシングル動作。
どうも速度的には大差ない感じ。
２倍くらい速度出ると思ったのに…。

スレッド数が増えたら差が出てくるのかなぁ。

**535** · 2018/12/27(木) 20:54:08.52

10万局いきました。

**535** · 2018/12/27(木) 21:18:27.23

多分俺が世界で一番囲連星LV3の計算を回した人だろうなｗ

**310** · 2018/12/27(木) 22:00:15.50

色々あがいた挙句、そこそこ時間がかかる２６手空きを、それぞれで解いてみた。

並列探索で６分。シングル単独動作で１２分。シングル４並列動作で１８分。
やはり、シングルも４並列する事でなにがしかのオーバーヘッドがあるようです。

単純計算だと並列探索６分を４個で２４分に対して、シングル１８分で４つ解ける
事から３３％の速度アップが見込める事になるけど、体感そこまでの効果が感じ
られないというか、時間がかかる問題では更に差が大きくなっていて、そいつらに
足を引っ張られている印象。

そのうえで、裏でゴソゴソやりながら計算させる時に色々弊害があるので、
CPUの増強を決断するまで放置しようかと思います。

色々あがいた結果か、並列探索ですこーし速度アップした感じ。
１０％行くかいかないか。

**535** · 2018/12/27(木) 22:05:17.88

よくわからんがハイパースレッディングって単純に性能２倍になるわけではないということではなくて？

**310** · 2018/12/27(木) 23:06:53.59

もちろんそうなんだけど、排他待ちを要するデータも、待ち合わせロスも
無いので、もうちょっと性能出るんじゃないかと思っていたのです。

あと、うまく説明できないけど、ノード数が多い探索は、ノード数比以上に
時間がかかっている気がしています。まだ感覚の話ですが。

**535** · 2018/12/28(金) 20:37:08.10

LV３は強いんだけど詰み状態から詰みを逃してる棋譜が散見される。
直せるもんなら直したほうがいいんだろうけどかなり大変だろうな

**310** · 2018/12/29(土) 09:40:46.33

んー。シングル並列動作で６時間かかっても解けずに諦めた盤面とを見つけて、
パラレルで解いたら１時間４０分だった。空きマス２６だと通常１分程度なんだけど、
時々こういう時間がかかる盤面がある。今までテストが面倒なので、１０分以内に
終わりそうな奴でテストしていたけど、もしかしたら探索ノードが多い奴ほど、
シングル並列動作での速度低下が大きいのかも知れない。

時間がかかる奴ほど、シングル・パラレル比が悪化するなら、今考えている大体
３倍程度ってのは成り立たなくなって、もっと悪い事になる。それなら感覚的に
合致する。普通に流れている時には、シングル並列で高速化できそうな手ごたえ
があるんだけど、時間がかかる盤面が来ると急速に逼塞していって、なかなか
回復しないという感じ。

パフォーマンスモニタにらみながら、unordered_mapのメモリアロケーションの方法
を想像してみた。初期確保件数指定（倍々で自動追加される）してみたけど、溢れて
もいないのにダラダラとメモリー使用量が増えていく。もしかしたらOSにメモリーを
貰いに行く動作が排他待ちになっているのかも知れない。どうやって検証しよう。
やっぱ自前置換表作るしかないのかなぁ。

**310** · 2019/01/01(火) 10:13:37.88

あけおめです。

ヒープをダラダラと確保するのが気になったので、色々いじりました。

ordering用のvectorを、配列にしてスタックに。ついでにクラス化してメンテ性アップ。
少しだけ速度アップした気がする。

自前ハッシュテーブル型の置換表を作ってみた。
最初に大きく領域確保して、溢れた時以外領域確保しないようにした。
基本、余計な機能は実装していないので、処理は軽いはずなんだけど…
極ほんの少しだけ速度ダウンした感じ…

記譜作成はunordered_map版で実行しながら、改良をしてみたいと思います。
とはいえ、ソース的にはあんまり改良の余地がないんだよなぁ。

速度がそん色ないところまで行けたら、シングル版の並列での速度低下が
メモリー確保が原因か検証できるかなぁ。

**310** · 2019/01/05(土) 09:07:42.68

チェーン型でハッシュを組んでましたが、テーブルがあふれると結局ダラダラと
メモリー獲得し始めるので、オープンアドレス型に変更して、まとめて領域を追加
するようにしました。

この辺、もう趣味の世界ですね。
何をしても、速度は上がりも下がりもしない（汗

やっぱり探索ノードを減らす工夫が重要ですね。

**535** · 2019/01/05(土) 21:26:02.72

自己対戦のみで強くなるアルファゼロは理想ですが実装が難しそうなので
せっかく棋譜も集めてるので教師あり学習をやってみようかと思案中。

**535** · 2019/01/06(日) 00:55:45.70

とりあえず、棋譜データからmin-max探索して黒有利の局面か白有利の局面かの２択を学習させようかな。とか思ってます。
そろそろ寝るか。。。

**535** · 2019/01/06(日) 02:33:16.90

寝るタイミングを逸してしまったｗ
プログラミングってこれがあるから怖いよねｗ

**535** · 2019/01/06(日) 02:46:46.55

なんか１００兆局くらい棋譜を集めると序盤DBだけでもかなり押せるんじゃないかなぁ。
そんな感じ。

いかん、寝なければｗｗ

**名前は開発中のものです。** · 2019/01/06(日) 03:01:38.94

質の悪い棋譜ばかり100兆局集めてもあんまり強くならない気がするのですがどうなんでしょう
質のいい棋譜がそれだけ集まればいいですがそれはほぼ不可能ですし…

**535** · 2019/01/06(日) 03:14:04.86

そうはいってもLV3の棋力はかなり高い。
囲碁将棋でいえばアマチュア３段くらいには相当するはず。

**535** · 2019/01/06(日) 03:18:59.57

波があるからアマチュア３段は言い過ぎだったかなｗ
でもまあ強い時はかなり強い。

**310** · 2019/01/06(日) 14:23:08.43

置換表一時調子が良かったのですが、修正加えたら崩壊。
なんとなく読み取りが変な感じなんだけど、どこがおかしいのか全くわからず。

>>578
棋譜たくさん集めて序盤DB作ったら、その序盤DBのMax手順以外の手について
は、分岐した以後の盤面だけで学習させると序盤の穴が埋まるというか、間違った
盤面でぼやっとした学習するの避けられるかも。

今、序盤についてはそのやり方で学習させてます。

**535** · 2019/01/06(日) 20:12:44.73

とりあえず、昔作ったTINY-DNNのプログラムを引っ張り出してきて学習プログラムを仮組したが絶望的に遅いorz
グラボ使えればちっとは違うんだろか？うーむ。

**310** · 2019/01/06(日) 20:34:20.52

オープンアドレスうまく動くようになりました。
ここに愚痴ると、直後に原因がわかる罠ｗ

この数日の葛藤は何だったんだ。

**310** · 2019/01/06(日) 20:36:40.74

>>582
Tiny-DNNはGPU対応していないんじゃないかなぁ。
結局、DCNNはGPUで処理しないと無理っつー気がする。

**535** · 2019/01/06(日) 20:44:29.63

>>584
あ～やっぱそうなんですかねぇ。
GPUも結構いいの買ったのでぜひ活用したいところではあります。

**535** · 2019/01/06(日) 22:23:00.36

明日は仕事なのでハマらないうちに切り上げようｗｗ
社会人として自制しなければｗｗｗ

**535** · 2019/01/07(月) 20:55:27.41

学習回しても損失が全く減らない。。。
そういやそんなのあったな。orz

**535** · 2019/01/07(月) 23:12:38.14

なんかネットワーク初期化忘れてたみたいw
初期化したら損失減ったｗ

ちょっと希望が出てきた。

**535** · 2019/01/08(火) 23:12:12.87

損失減ることは減るんだけどホントにちょっとづつしか減っていかない。
ネットワークの形状が悪いんだろうか？学習率だろうか？
うーん、深みにはまりそうorz

**310** · 2019/01/09(水) 20:33:25.82

学習の速度はオプティマイザに依存します。

普通のSGDだと、あちこちぐるぐる回ったり、平野トラップで立ち往生したり、
局所最適解から抜け出せなくなったり。また、SGDは学習率（α）を大きくすると、
簡単に発散しちゃったりしますので、学習率を低めにして１０００回とか学習する
事になります。それでも上記の問題で、なかなか収束しなかったり、うまく学習
できなかったりします。

そういうものなのです。昔は、初期値（乱数設定しているはず）を変えてみたりして
トライ＆エラーしてましたが、今なら別のオプティマイザ（RMSpropやADAM）を試す
べきかと思います。それでも数百回は学習を繰り返さないといけないと思います。

久々に検索したら結構種類が増えてた。
https://qiita.com/ZoneTsuyoshi/items/8ef6fa1e154d176e25b8
自分は線形回帰モデルですが、SMORMS3を使って効率化を図っています。
それでも、数百回学習しないと損失は落ち着いてきません。

**310** · 2019/01/09(水) 22:31:13.85

置換表ですが、結局のところ、ハッシュのビット数を増やしてチェーン接続があまり
生じないようにし、メモリーをある程度のサイズでまとめて確保する、チェーン型
ハッシュに落ち着いています。

普段速度計測に使っているFFO#40-49ではconcurrent_unordered_map版より若干
遅いのです。が、どうも残り２８手（現在はそのあたりをチェック中）では、自作チェーン
ハッシュの方が早いというか、ノード数が増えた時に速度低下が少ないように感じて
おり、現在は自作置換表を使っています。

とはいえ、２９手や３０手まで行った暁にはチェーン接続が多発し始めて速度低下が
始まると思われるので、対策を考えて行きたいと思います。２８手が終わるまでまだ
一カ月くらいかかるので、幸か不幸か時間はたっぷりあります(--;

今のところチェーンの代わりに２分木を置いて、ハッシュが衝突したときの速度低下を
O(n)からO(log(2)ｎ)にしてみようかと考えています。

**535** · 2019/01/09(水) 23:20:11.40

ふーむ。要素が少ない時はリストやツリーは遅く、配列が圧倒的に早いという認識でしたが。

**535** · 2019/01/12(土) 00:34:20.08

あれ、序盤DBに棋譜を追加したら全然おかしな手を打つようになっちゃった。
棋譜がまずいのかな？

**535** · 2019/01/12(土) 01:02:50.64

くそ～強いAI（自我があるとかではないよ）作りてぇなぁ

**535** · 2019/01/12(土) 01:39:38.14

三連休とはいえそろそろ寝なければな。
生活のリズム崩すのはいくない。

**535** · 2019/01/12(土) 21:33:08.59

質にばらつきのある棋譜から良いデータを抽出する方法はあるのだろうか？

**535** · 2019/01/12(土) 22:30:56.75

うーんせっかく３連休なのに捗らないな。
これだというアイディアが湧くまでこねくり回すしかないか。

**535** · 2019/01/13(日) 22:01:49.93

結局アルファゼロという正解がある限りその呪縛から逃れるのはかなり難しいorz
うーん。

**535** · 2019/01/14(月) 21:36:22.16

やっぱグラボも活用したいなぁ。
でも難しいんだよなぁ。
とくにウィンドウズだと。

**535** · 2019/01/16(水) 00:51:29.20

昨日一日学習回して損失が初期値の2/3位になった。
この辺が限界かなぁ
それともぞうきんを絞るようにまだまだ損失減るんだろうか？

**310** · 2019/01/18(金) 00:47:06.53

NN系は学習してるんだかわからない時があるよね。
とことんまで回すと今度は過学習も怖くなってくるし。

こちらは、自作concurrent_mapクラスができました。
ハッシュキーは二分木で、ハッシュ値は64bit。
配列ハッシュキー版と同様に、削除もiteratorも無し。
すこーし速度があがったかなぁ程度。
衝突時の処理はチェーン式。流石に64bitだとキーの衝突が無い。

棋譜訂正は時間がかかるので、暇つぶしが必要な状態。
二分木を赤黒木に変えてみようかと思い始めています（汗。

本当はヒューリスティックスの改良の方が効果あるんだろうなぁ。

**535** · 2019/01/18(金) 22:51:46.73

今週は残業がひどかったorz
でも土日は休める。

**310** · 2019/01/19(土) 09:03:58.77

赤黒木を検討してますが、これ並列処理だと木全体をロックしないと
いかんのではないかと…。置換表のように追加の頻度が高いケース
では、排他待ちでパフォーマンス出ないかも。

まあ、やってみるしかないけれど。

**535** · 2019/01/19(土) 11:25:42.95

赤黒木とかめっちゃむずかしいやつですやん。
さすがですな。

**535** · 2019/01/19(土) 19:50:28.36

ん、なんか学習したネットワークがすべてのデータに対して同じ結果を返してるっぽい？

**535** · 2019/01/19(土) 19:58:01.80

学習開始時のネットワークの重みの初期化をミスってるんだろうか
うーん。

**535** · 2019/01/19(土) 20:54:13.90

tiny-dnn以外のGPU使えるライブラリで重みだけ学習してアプリケーションからはtiny-dnnを使うというのもあるのだろうか

**535** · 2019/01/20(日) 02:28:47.86

全く同じ結果ではなく微妙に違う結果を返してるのは確認できたけど。
単に学習量がたりてないのかなぁ。

**535** · 2019/01/20(日) 15:00:24.16

やっぱり全く同じ結果返してる？？
混乱してきたorz

**535** · 2019/01/20(日) 15:40:18.18

層が多すぎたのが悪かったみたい？
層減らしたら違う値になった。

**535** · 2019/01/20(日) 17:41:45.52

お、LV１に勝った！
まあDNNの学習の効果の勝利というよりも序盤DBと詰みルーチンの補助による勝ちなんだけどね。
でもとりあえず、それっぽく動くところまで来ました。

**535** · 2019/01/20(日) 17:54:10.26

序盤DBが良すぎてDNNの真価がわからないから序盤DB外してみるか…

**535** · 2019/01/20(日) 17:59:21.27

酷すぎｗｗｗｗ
でもランダムよりはマシに見える。

**535** · 2019/01/20(日) 18:24:44.15

やっぱ序盤DBに頼るか…
こんなにプログラムが楽しいの久しぶりやな

**535** · 2019/01/20(日) 20:01:09.83

たぶんだけどまだまだ棋譜増やしたほうがいい。
ていうかあればあるほどいいい。まだまだ良くなる。
可能なら１００万局を目指したい。

**310** · 2019/01/22(火) 00:34:53.58

赤黒木大体できたけど…ただの二分木よりほんの少し遅い…。

元々ハッシュでランダマイズしているから、二分木の末端ノードまでの深さは
綺麗な正規分布になっていて、赤黒木にしても木の最頻高さで３割程度しか
小さくならないという事で、ツリーを修正するオーバーヘッドが効いているのか、
それとも木全体でしか排他できないのが原因なのか。

もうちょっと調べてから諦めます。

**535** · 2019/01/22(火) 22:52:21.02

要素が１００個未満ならぶっちゃけvectorでいいと思いますが。。。

**535** · 2019/01/22(火) 23:02:42.33

前も同じこと言ったような気がするけど、学習させるなら局面の勝率より次の一手のほうがいいのだろうか？

**名前は開発中のものです。** · 2019/01/22(火) 23:17:25.29

いまきたんですがここはどんなゲームを開発してるんですか
じぶんで開発したとして対戦相手=プログラムありますか

**535** · 2019/01/22(火) 23:34:54.50

>>619
とりあえず、落ち着いて。
過去ログから読んでください。

**310** · 2019/01/23(水) 01:56:46.43

置換表に使ってるので要素数は現在残り２８手で１００万超える事もあります（汗
まあ、βカットの具合でだいぶ変わるので、学習進むと減るんですが。
最低でも残り３０手まで行くつもりなので、１０００万くらいは想定したいです。

次の一手ソート用の配列は、Array型にしています。３２個確保すれば足ります。
こちらも比較したところ、明確に速度差がありました。この辺から、領域をチマチマ
確保されるオーバーヘッドが気になりだした次第です。

で、赤黒木ですが、実装が悪いのだと思いますが、現時点で２分木と比較して
およそ３倍時間がかかります。シングル動作でも同じくらいの差になるので、
排他待ちではなく、木のつなぎ替え処理の重さが原因かなと。置換表は追加が
の比率が大きいので、ポインタたどるロスは優位ではない感じ。

というわけで、赤黒木はちょっと放置。

というか、二分木もシングル動作は１０倍くらい速い感じなので、今一度シングル
探索の並列化を試そうと思っています。

**310** · 2019/01/23(水) 02:07:28.76

>>618
min-Max前提だと、探索値を求める際には勝率（点数）が必須で、
次の１手評価関数はオーダリングや前方枝刈向きではないですか？
探索深さ１なら次の１手で行けますが。

初代アルファ碁も、両方組み合わせていますが、次の１手評価関数で
手の優先順位をつける事で読み深さを実現した変則mctsで、最終的には
評価値で判断していますよね。

**535** · 2019/01/23(水) 20:43:46.28

ふーむ、勝率のほうが応用が利くってことですかね？
もうしばらく勝率で学習させてみます。

**535** · 2019/01/23(水) 21:07:20.14

ついネットワークを大きくしたくなっちゃうけど。
本当は小さいネットワークでエポック数を稼いだほうがいいのかもしれない。

**535** · 2019/01/23(水) 21:28:27.72

そういえば、対称局面も学習データとして使ったほうがいいんでしたっけ？

**310** · 2019/01/24(木) 01:32:42.88

囲連星は初期配置ないんでしょ？
だったら対象局面ありの方が良いと思う。

オセロは悩み中。
初手をF5固定にした時に、本当に対称局面が出てくるのかわからない。
対称局面が同じ重要性で生じないのであれば、評価値を希釈しちゃうだけ。
学習の時間も単純に倍々で増えるので、今はやっていない。

強いて言うなら、F5F6E6の次がF4とD6で斜め対称になるので、ここだけは
記譜作成時にはF4固定にして、D6の対称局面を作っている。

**310** · 2019/01/24(木) 01:49:46.37

置換表自作の件、目的を見失っている（汗
一旦リセットして、最初からやり直して、当初の目的に戻ろうと思うorz

**578** · 2019/01/24(木) 01:53:14.72

私は教師データの数が8倍になるのは大きいと思って対称局面も入れて学習させてます
とくにDeep Learningさせてると（ネットワークの規模にもよりますが）だいぶ過学習しなくなります
もっとも、Deep Learningするんだったら対称性を考慮したネットワークにしたほうがいいのかもしれないですが・・・

**310** · 2019/01/24(木) 02:08:25.51

着手できる場所の自由度が高いゲームは回転させるべきだと思う。
オセロは着手可能場所が限られるので、現れない局面が結構ありそう。

ちなみに、オセロは８倍じゃなくて４倍。初期配置が４対称だから。
囲連星は初手天元固定なのかな？

**578** · 2019/01/24(木) 07:09:21.18

>オセロは８倍じゃなくて４倍
たしかに棋譜で考えると4対称しか無いですね
今のところ、学習させるときには現局面しか渡してないので、
90度回転で一致する局面が存在するかもしれないから8倍で良いはず…

**535** · 2019/01/24(木) 22:03:23.55

うーん。今のやり方だとLV0やLV1とはいい勝負になるけどLV3には一生勝てないかも？
出来れば自己対戦による強化学習とか取り入れたいな～

対称局面もやってみますね。

**535** · 2019/01/24(木) 22:45:59.18

なんか長時間計算回してると画面が真っ暗になってマウスやキーボード押しても復帰しないことがあるんだが？
スリープは解除してるはずなんだけどなんなんだろう？

**535** · 2019/01/25(金) 23:18:39.41

LV0ってやっぱ棋力低いな。
そんなLV0といい勝負の俺のAIもあれだけど。
やればやるほどLV3の完成度の高さが際立つ。

**310** · 2019/01/26(土) 17:00:37.38

自作置換表ですが、大体のところがまとまりました。
結局のところ、unordered_mapを作っていた形になります（汗

当初は領域の追加について、データ部分をまとめて追加する方向で改造し、
ハッシュ配列については２２ビット固定で、高速化をしました。で、ハッシュ配列が
２２ビット固定は芸がないと、二分木・赤黒木などを試しましたが、速度大幅低下。
要するに、unordered_mapにmapを組み合わせて、ハッシュのメリットを相殺して
しまっていたという事で。

最終的に、ハッシュ配列の追加方法をようやく思いつき、組んでみたところ、それが
そのままunordered_mapのrehashだと気が付きました（汗。その後、max_load_factor
などを追加して、unordered_mapと条件を揃えて速度比較となりました。

iteratorと削除が無い分だと思いますが、unordered_map、concurrent_unordered_map
に対して、それぞれシングル版、concurrent版とも若干高速になりました。

新たな課題は…stlも自作版も、どちらも並列に動かしたconcurrent版の方が遅いと
言う事です。もともとそういうものなのか…テスト方法が並列向けじゃないのか。

**535** · 2019/01/26(土) 17:38:15.71

8対称はメモリがやばいので4対称にします。
4対称で16GB位食ってる。