オセロAI"Egaroucid"全般
【基本的な情報】
Egaroucidはにゃにゃんが作っているオセロAIである。2021年6月に一瞬だけ世界10位になった。
Webサイトで遊べるようにしている。
https://scrapbox.io/files/613daf561237f30022c66380.png
【関連URL】
【各分野の思考】
【変更履歴】
2021/09/12 16:39
とりあえず深層学習を切り上げて圧縮アルゴリズムの調整を行った。
近い数値の連続はとても少ないので圧縮率は悪くなる傾向にあるが、まあとは言え許容範囲なので精度を上げる努力をした。
最大絶対誤差は0.090らしい。
数値を表すのに87文字、似た数値の連続を表すのに4文字くらい使った。
2021/09/12 16:43
圧縮すると推論の正しさがわかりにくくなるので、とりあえずパラメータファイル読み込みによってパラメータを入手する方向で推論パートを書くことにする。
2021/09/12 17:40
ファイルに出力したパラメータを読み込んで推論するテストをしてみた。
一番上がPythonによる推論、下5つがC++による推論で、Dropoutのランダムの関係で多少ずれるがまあ大丈夫そう。もしかしたらDropout減らした方が良いかも(知らんけど)
https://scrapbox.io/files/613dbcfac557d4001d1317b5.png
2021/09/12 17:45
試しにこの評価関数で対戦するも普通に弱かった(思考時間ほぼなしの私vsレベル3で引き分けた)
とりあえずC++で書いた方の前処理が間違っていないか確認をすることにする。
2021/09/12 19:15
弱い原因を探すため、とりあえずAIのコードでNNに入力するデータを加工する前処理を見たら盤面入力で軽微なバグを発見したので修正。ぶっちゃけ変わらないような気はするが…
2021/09/12 19:46
入力に盤面の生データを入れているので、学習時に盤面の回転を実装しなくてはいけないことに気づいた。愚かなことをした…
てかそもそも昔の自分が書いた盤面回転間違っていたし。。。。。。
2021/09/12 19:54
手番の逆転でデータの水増しをしていたが、そもそもオセロにおいて「手番が逆転した状態」はほぼ起こらないと推測されるのでやめることにした。
2021/09/15 16:41
序盤は完全にbook化してNNは中終盤に特化させるとデータの偏りとか全く気にせず学習できるはず。やること増えてきたができる見通しが立ってきた!
2021/09/20 13:44
やはり深層学習"だけ"を使って盤面評価を行うのはデータ数の面から考えてかなりリスキーなので、深層学習、強化学習、そしてMCTSを組み合わせるAlphaZero方式を採用してみることにした。
2021/09/21 23:19
AlphaZero風アイデアを大方実装して自己対戦を始める手前まで来たが、ここで棋譜を使った学習で対戦するとめちゃくちゃ弱かった。序中盤が弱すぎるので、とりあえず棋譜からbookを作って最序盤はお茶を濁すことにする。
中盤力がなくて30手目くらいではすでにAIが勝つルートが全く残っていない状態で、終盤力が全くわからない。とりあえず明日自己対戦させてみるか…正直MCTSのどこかにバグを埋め込んでいそうだが…
自己対戦は多様性確保のために序盤ランダム打ちとする。また、序盤ランダム打ちの結果を使って最後にきちんとしたbookを作る。
あと地味に盤面回転(1手目を必ずd3にするやつ)をまだ実装していないので明日以降の自分、がんばれ。
2021/09/21 23:43
なぜかMCTS関係のどこかが遅いことが気になったので調査してみる。
これ、推論が遅かった。convの計算量が多めなのでconvを小さくしてみる。
とりあえず正確性の高い大きなモデルの設計がだいたい固まった。
明日は蒸留を試みる。
うまくいったら蒸留モデルで自己対戦してさらに強くする。
自己対戦は片方のプレーヤーに時々ランダム打ちをさせて多様性を確保する。
気が向いたら以下もやる
盤面の重みを機械学習で作らせる(対称な入力を生成してdense1つに集約してパラメータ調整をさせる)
空きマスのパラメータも入力に与える
2021/09/23 21:42
推論が書き終わった。
kerasのconvのpaddingは処理前に行われるのにハマってた。
誤差の問題であまり大きなモデルにするととんちんかんな結果を返すようになるのでモデルを小さくするのが急務。
これ、普通に誤解で私の実装のバグだった。
2021/09/24 16:23
できたモデルを使って対戦するもめっちゃ弱い。book作り直ししていて気づいたのだが、明らかに棋譜に偏りがあった。ということで自己対戦必須。自己対戦の作戦を練る。
自己対戦について
序盤N手、M盤面をあり得るパターン全部book化する。
1手目の対称性とこちらが打つ手を一意に定めてMを小さくする。
N=10いけば泣いて喜ぶ。
ということで、学習に使うデータはN手より後のもののみとする。
序盤N手双方完全ランダム打ち、その後はランダムに選んだ片方が確率pでランダム打ちをするようにして棋譜の多様性を確保する。
2021/09/24 16:37
何手をbook化するか考える。
table: bookを何手作るか
N M_先手 M_後手
6 80 30
8 480 180
10 2400 1508.4
12 13656.0 13711.7
まあ10手が限度でしょう。
20:34 訂正
これ計算ミスっていて、6手が限度。
2021/09/24 18:08
自己対戦のランダム打ちだが、6以上のランダムに選んだ整数kについてK手まで完全ランダム打ちして、その後真面目に打って真面目に打ったところを学習データにするようにする。
2021/09/24 20:45
自己対戦後のbestとの戦いは、bookを使い終わった6手以降の局面をランダムに選んでそこから勝負させるのを何回かやって勝ち越すかで決定する。
2021/09/25 2:19
MCTSのバグを潰した。
MCTSの子ノード展開は遅延的に行うとメモリ関係がgood
推論が遅いのでこれからexpとtanhの前計算で高速化する。
2021/09/25 2:43
推論高速化(離散化前計算)で全体が1.6倍速に
2021/09/25 3:44
人間の対戦の棋譜を入手できたので(加工プログラムとか頑張って編集した)それで再学習してみてる。
バリエーションについては序盤10手が4700局で2678パターンあったので優秀そう。
畳み込みのpaddingを最適化しやすく書き直したらAI全体が5.5倍速になって草
2021/09/27 13:46
機械学習がうまくいったのでc_puctとc_endのパラメータ調整をした。
最終10手を残したくらいで必勝読みさせて終局判断すれば精度が上がりそう。
これ、結局最終8手で終局判断するのが高速で精度も上がった
2021/09/27 17:55
自己対戦について、
最初6手(初手は固定なので実質5手)ランダム打ち
その後は最終的なノードの訪問回数を全部の訪問回数の和で割ったやつをrandomで確率的に選ぶ
↑softmaxだと差が激しくなってしまうのでなんとなく線形にしたけどいけるかなー
試したけどだめだったのでsoftmaxにした。
2021/09/29 2:37
book性能が悪いのに薄々気づいていたので一旦bookを廃止したらなんか初代に勝利して笑った
明日はbookを真面目に今のAIを使って作ってみて、何手までbook化できるか検証する。
入力増やしてもそんなに痛くないので、盤面入力に白/黒でない場所、および空きでないマスを追加してみようかな。
これ、性能全く上がらなかった
2021/09/29 12:13
bookはAIの性能が上がってからで良いやということで、自己対戦を書き直してやってみる。
2021/10/01 2:00
自己対戦において、毎回確率的な遷移をしては全く精度が上がらない気がした(というかなんか弱いので)ので、一定の確率(75%)で正確に打つようにし、そのときだけ盤面を保存し、教師データとして使うことにした。
2021/10/01 2:43
https://scrapbox.io/files/6155f72bb8f6900023c88fce.png
自己対戦したらゆるやかーにグラフが上がるようになって嬉しい。
2021/10/01 4:11
多様性確保のため、初手の後の3手をランダム打ちするようにした。これくらいなら多分有利不利があんまり変わらないので。いやまあ変わってもいいけど。
2021/10/01 8:33
自己対戦で鍛えたモデルが既存のものに全然勝ち越さないので、AlphaZero方式でモデルを評価せずにアップデートするようにした。
理論上は勝ち越しとか関係なく書き換えていればいつか強くなるので。
2021/10/02 11:12
新たな棋譜というかbookを入手したのでそれを使って学習。
これ、あんまり強くなかった
2021/10/02 13:12
結局9/28の人間の棋譜で学習したモデルに、さっき入手したbookを加工したものをbookにして使うことにした。
探索の最中に(自分の手番で)bookの盤面に出くわしたら終局と判断してbookのvalueを返す。
そもそも入力された盤面がbookにあったらそのpolicyを返す。
2021/10/03 23:56
27000くらいのパラメータの大きなモデルを作った。こどげなんて知らん。出すなら後で蒸留してやる。
Web公開用にwasm化した。
wasm化すると静的に公開できるのはもちろん、AIが"その対戦専用"になるので、前回の探索結果を用いることができる。
前回の探索で10回以上訪問したノードの成功率をハッシュテーブルに記憶して、新たな探索でノード展開時に検索してヒットしたらバイアスに加える。前回の値pvと今回のそのノードの訪問数nについて、バイアスとしてpv/n (n>0), 0 (n=0)を与える。n+1で割っても良かったのだが、0回訪問時は先入観なしの方が性能が良かったのでこうした。
2021/10/05 18:36
昨日若干UIを変更した。合法手をその番の色で表したり,あとは読みきったときに一瞬で打たないようにした。
2021/10/05 18:37
やはりセルフプレイが一番現実的な気がするので,10手あとまでの重みの移動平均をvalueに,policyはone hotじゃない形式でやった。
2021/10/06 0:13
ノードたちを毎回リセットしないようにした。こうすると精度がかなり上がる(累計ノード訪問回数が増えるので)
アーク評価値のsqrtを試しにそのノードの訪問回数/そのノードの合法手数とした。
2021/10/06 15:25
人間の棋譜から強いAIで評価値と方策(複数)を計算させて,それを学習してみようかと思った。
とりあえず大量に計算しなきゃなので6手読み。
2021/10/06 20:48
vacant_lst周りでバグがあって,いやこれまでなんで動いてたの…となった
rotateさせた後でvacant_lstを作っていた
これ,私の頭がバグってた。
2021/10/06 21:48
MCTSで木と重みを作ってそれをminimaxしたら良くない?
MCTSの根に近いノードの重みについてはその下の有望でない手を含めた重みなので。ってことは,訪問回数によってMCTSの段階である程度重みに重みをつけたら良いのではないか。
2021/10/07 17:05
コードがレガシーの塊になりつつあるので書き直した。結構コンパクトになった。
2021/10/09 5:34
bookを自前で用意した。序盤8手で自分の選ぶ手を固定したので198個くらいで済んだ。適当に埋め込んだ
たまに全消しで負けるので,1手読みで全消しされる手があったらそれを選ばないように明日以降する。
2021/10/10 0:13
book10手全網羅、4万局でNNを学習してこどげ20位、25.26まで戻ってきた。
連続パスで負けることがあるのでパスの時はvalueを人為的に下げるようにしてみる。
これ、意味無し
2021/10/10 20:08
bookは16手で評価値の絶対値が3.0未満のものにしたがもう少し入れられそう。
2021/10/11 16:28
自己対戦で5000局の棋譜を作って学習してみる。
一応新モデルが勝ち越した
けど弱いのでlearning rate=0.001から0.0001にしてみた
2021/10/12 15:08
こどげ向けに圧縮方法を変更。32%程度パラメータを追加できるようにした。
2021/10/13 17:59
convを50カーネルで行うようにするとpolicy lossが結構下がったのだがvalue lossが一向に0.75くらいから下がらない。多分まあ教師データの質の問題だろうということで、やはり自己対戦が必要か…だるい。
あと、アーク評価値(の改変版)の各種パラメータ調整をNNで行ってしまおうと思い始めた。
薄々気づいてはいたが、value networkは自石が少なくなるように学習していそうで残念なことになっている。初代Egaroucidで使っていたパラメータをもう一回使ってみるか。
2021/10/14 1:50
AlphaZeroでなくAlphaGo方式で、playoutをちゃんとやることにした。さすがにdual networkは遅かったのでrollout policyを小さいモデルで別に作ることにした。
これ、おそすぎて無理
2021/10/14 18:56
自己対戦にもう一度チャレンジ
片方はbookを使う、ランダム打ちは2手まで、の変更を加えた
2021/10/14 22:26
自己対戦の多様性を調べてみたら若干多様性にかけていたので10手目まで10%の確率でランダム打ちさせてみた
https://scrapbox.io/files/6168368a47fb060021a467bd.png
終局まで同じのが3%程度なので許す。
2021/10/15 2:44
アーク評価値の重み項に1手読みminimaxを使ってみる。
MCTSの出力する手の選択にノードの訪問回数と重みとpolicyを組み合わせてみる
2021/10/24 18:29
オセロAIにおいてMCTS系探索はやっぱり弱いよねーと思ったのでこれまで学んだことを使ってNegascoutしたEgaroucid3を作ることにした。
とりあえず基本的な関数と最小限のNegascoutと置換表、そしてbookを書いたので次は評価関数を作る。
評価関数は適当な棋譜から算出した勝率によって作る。
数マスのパターンを用意してそれぞれの増すの並びに固有のパラメータをつける。その総和(を(-1,1)でminmax取ったやつ)を評価値とする。
勝敗は-1、0、1で決定する。
パラメータ調整はとりあえず出現するパターンは焼きなまし、その値を教師データにしたNNを作り、NNの出力結果をパラメータとして埋め込もうと思う。NN埋め込んだら重いから…
あーでもパラメータ全埋め込みしたら中盤から終盤にかけて区切っての評価ができないな…十分小さなNNを埋め込むかも。
これ、NN埋め込んで前計算で全パターン計算しておけばO(1)じゃん。NNで圧縮。
だいたい20手まではbookを使うと想定して、
0-20手
20-30
30-40
40-50
50-60
くらいで5フェーズに区切ってそれぞれ学習したいな。
値はすべて黒、先手の値として、マイナスつけるのはAI側で行う。
2021/10/25 22:58
とりあえず10パターンでの評価関数が書けた
NegascoutにNegaalphaをくっつけてみた。
2021/10/26 3:04
モデルの段階で10種類74パターン全部を使って学習することで精度向上を狙う。
2021/10/26 19:35
なんかあんまり強くならないので現実逃避に終盤ソルバーを作る。
FFO終盤テストを使ってベンチマークを計測
なんか色々やっていたらかなりnpsあげる手法も思いついたしなんだかんだ良かった
ただし終盤ソルバーが多分Negaalphaのところでバグってる。
2021/10/26 23:52
とりあえず終盤ソルバーを書き終わった
モデルの学習し直しを始めた。
入力を実際に使う10種類76パターンの入力で学習。
最終的に自己対戦できちんと追学習かけたいなあ
2021/11/01 21:40
終盤
終盤の評価値の信頼性はかなり高いので、速さ優先探索に重みつけして評価値も加えた。これで速さを優先した勝ちルートを優先して探索してくれる。
この工夫でFFO必勝読みが2-6倍速になった。
中盤
評価値はマジで信用できない。悲しい。これはとりあえず117万棋譜でゴリ押して学習してみることにした。
パターンも増やした。
パラメータを後述のbookに割くため、強いAI相手なら最低でも20手はbookを使えるようになった。ということで20手以降を4フェーズに分割してパラメータ調整を行うことにした。これでパラメータ数を減らしつつパターン数も増やせるはずなのだ…
序盤
book最高!ということで、人間の棋譜と自己対戦からbookを生成した。
book使用のため初手を必ずf5に打つよう補正していたが、 book登録にそんなに時間がかからなくてメモリ余裕も十分あるので、盤面回転で1盤面あたり4つをbook登録することにした。
余談だが手筋が違って違う向きで出現するパターンに強くなるのでよりbookにヒットするようになる
対Master Reversi for HTML5 基本
35手目くらいまでbookヒットして、35-39手だけ2秒設定で読んで39手くらいで必勝読みして勝てたり勝てなかったり。
相手は多分8手読み&18手必勝読みなので、やっぱり評価関数が強いなーという印象(序盤35手くらいは相手のbookにも当たっていそうだけれど)
2021/11/02 0:52
そういえばProbCutについて書き忘れていた。
Multi Prob Cut(MPC)はN手読むときにN/4手読んだ結果を使って実現することにした。実際のminimax値Vは少ない手数読んだminimax値vを使ってV=avとして線形回帰した。信頼度は91%、1.4くらいが良さそう。
2021/11/02 5:09
MPCは水平線効果に弱すぎるのでとりあえず無効化
bookを見ると斜め取りに弱すぎるようなので斜め取りの棋譜を80万局生成してみている。精度とランダムさがいい感じなことを願って。
2021/11/02 14:41
book生成のための自己対戦はとりあえず
序盤6手は1手読みによる評価関数で重みをつけたランダム打ち
以降は10msで探索
で行うことにした。最初は序盤10手を重みつけランダム打ちしていたが多様性がありすぎてbookを作れなかった…
2021/11/02 19:57
book生成用自己対戦がうまくいかないのでとりあえず諦めた。
これ、地味にコードバグってたんでいつか再挑戦する
評価関数に着手可能数および潜在的着手可能数を追加してNNをもう一つかませることにした。lossが0.1くらい余計に落ちるのでまあいけそう(前やったらだめだったけどそれは多分データ不足なので見なかったことにする)
中盤の評価関数はそれでもまだ弱いので、中盤深読みできるように経験的に優秀と知られている開放度をmove関数でついでに計算したいがどうやって実装しよう…
2021/11/02 21:16
評価関数に着手可能数と潜在的着手可能数を加えたら結構精度が上がったのでMPCを復活させてみる。
これで世界11位になった!!
2021/11/03 2:32
move orderingに開放度の近似値を入れて3%性能向上。
MPCの回帰をやり直した
これで世界10位!!
2021/11/05 14:12
夜中に10時間かけてしっかりした自己対戦を2万局行ったのでその結果を使って追学習をかけた。
2021/11/07 2:39
GPUがフリーだったので試しに勝率ではなく最終石差を使って学習をかけてMPCの定数を計算して提出したらなんか世界4位になった。
てことで自己対戦を18時間くらいしてもらって明日夜からまた学習かけて評価関数をアップデートする。
2021/11/07 22:39
自己対戦が72846局集まったのでそれを使って1、2エポックずつ軽く学習させてみる。
自己対戦から学習まで一連の処理を自動で行うコード書いて1週間くらい放置したいなあ
2021/11/08 23:46
自己対戦から学習までを行うプログラムを書いた。
800局の対戦から1盤面20個のパターンの組み合わせを選んで学習(つまり学習データはだいたい16万)する
さらにその結果を使って小さい方のNN(4入力-4dense-1出力)を学習し、掃除して完了。
多分全体が1時間で1サイクル回る。
2021/11/09 16:15
自己対戦のminimax値にランダム要素を入れて多様性を確保した
途中の石損を考慮するために途中の評価値と終局結果の平均を教師データとした(重みをつけるかも)
終盤20手完全読みさせた
2021/11/09 19:23
MPCの式を
V=av+e
から
V=a(v+b)+c+e
にして定数を焼き鈍した。
これただ冗長にしただけじゃん…高校数学ができません
2021/11/11 13:32
Egaroucid3にレガシーが溜まってきたのでEgaroucid4を作る。
基本的にはEgaroucid3を書き直したもの。
2021/11/12 2:18
とりあえず新評価関数を書いた
評価値が完全にintなのでMTD-fを書いてみた。
Negaalphaでもfail softした
置換表への登録バグを直した
2021/11/12 4:12
モデルを見ると推論と答えで符号さえ違うのが結構あり嫌な気持ちになったので符号違い絶対許さないマンなloss関数を設計した。
夜中に学習かな。もう早朝だが。
2021/11/12 21:38
評価関数の特に20-40手がヘボいので、30手まで人間の棋譜、その後終局までEgaroucidに打たせるハーフ自己対戦を2万局行うことにした。
2021/11/13 0:22
暇なのでハッシュテーブルの限界高速化をした
ハッシュ衝突確率が十分に低いのでハッシュテーブル自体のサイズを小さくしてキャッシュヒット率を上げた。
キーが8つあったがそれぞれ高々6560までの大きさしかないので2つのキーを1つのintにまとめた。
register時にいちいちmallocするのが時間の無駄に感じたので最初に1要素だけmallocしておくことにした。
ぶっちゃけほとんど速くなってない!!!普通にボトルネックは別にありそう。
2021/11/13 2:10
評価関数で状態を反転させた値も考えた平均を取っているが、そのあたりが遅そうなので前計算させた
しかしここで誤差の蓄積が問題になってきた。出てくる数値を制限して学習したいがkerasにそんなものはないので学習アルゴリズムを自前実装する必要がありそう。本格的に機械学習に足を突っ込むことになるな…
2021/11/14 1:27
NNの圧縮は量子化の工夫でお茶を濁した
とりあえず終盤30手600msソフト打ちのデータ2万局くらいで学習
2021/11/14 3:46
必勝読みに2石以上の勝ち負けについてMPCを入れた
2021/11/14 13:48
パラメータを離散化できる値で表現した後にその値を自己対戦で山登りしてみる
なんかだめ
GAが強そう
2021/11/14 17:17
推論見直してたらバグ発見。直した。
2021/11/16 1:25
なんかやっぱり評価関数がだめなので、新モデルを作ってみる。夜中に学習してもらう。
2021/11/16 5:48
よく考えたら活性化関数で非線形にしてるから途中で勝手に平均取ったりしちゃだめなのはそれはそうじゃん。ってことで修正。各パターンについて8種類または4種類の値を全部Addかけた。
よく考えたらこれConcatenateの方が精度上がりそうだけどとりあえず放置。だるいので。
2021/11/17 4:24
新モデルが結構強くて6位から7位くらいになれた。
良さげなので25手棋譜、以降15手読み&18手完全読みで自己対戦を34560局かけた。これで明日学習かな。
2021/11/18 15:27
MPCの標準偏差をフェーズごとと新たに読み手数の深さで分けたらめっちゃ強くなった
世界3位
2021/11/20 20:26
MPCの浅い探索の手数にバグがあった…なんで強いの…
2021/11/23 16:37
bookは命です。