初戦でkimiyukiさんに負けてベスト8です😇
AIの概要はこっちに書いてあります。
piroz.hatenablog.com
もう決勝からだいぶたっていてタイムシフトも消えてしまったのでかなり記憶が薄いです。
権利上の関係とかで動画にはならないのかな～～～
決勝当日
チームラボ本社は水道橋にある。
行くのは二度目だが出口を間違えて知らないところに出た。
その日東京ドームでライブがあるせいかわからなかったが人が多かった。
12:00に本社に突入したらまだリハーサルをしていてダメだった。(受付開始12:30と書いてあったので自分が悪い)
(どうでもいいけどエレベーター降りるとすぐオフィス内でビビる)
昼を食べてなかったので駅の方まで戻ってすき家で食べて、12:30に再突入した。
カメラやら配信機材やらが色々あってすごい。
Normal
人が足りてない・・・😇
上位の方はちゃんと探索して連鎖してた。見てて面白かった。
Hard
第一回戦第二試合が僕 vs kimiyukiさん。
予選では割と勝ち越してる相手だったのですがダメでしたね・・・
予選から決勝までの間に全然強化できなかったのが悔しいです。
コメントでも言ったけどトーナメントなので初戦負けるとバイバイで悲しい。
僕のAIは200以上そんなに出ないんだけど他の人たちは250～500くらいをポンポン出し、1000まで叩き出していたのでもうこれは勝てそうにないという感じだった。
当日色々
参加者全員にスポンサーから色々配られていたが、スクエニからはスライムが描かれたペットボトルカバーが貰えた。
懇親会は酒＆ピザだった。
決勝AIの反省
前回の記事の通り機械学習がバグっていてパラメータがおかしい可能性があった。
また、ハイパースレッディングが有効だったので、2スレッド実行すれば若干速くなるのではと2スレッドにしたら競合していた(最悪)。
他の参加者と話していて結局敗因は何かということを考えた。
今回のゲームの場合、評価関数を凝るよりはいかに探索を頑張るかという所のほうが重要なんだと思った。
連鎖のチェックをする場所を限定して盤面の評価を速くしたり、発火ターンを限定して読む幅を増やすのが効果的なのだと思う。
これらは試してみて今のAIと戦わせてみたい。
結局機械学習でAI強くできたの
冷静に100先をさせたところ、ベースの評価関数よりは明らかに強くなっていた。
| ベース | 決勝提出 | バグ修正 | |
| ベース | - | 72-100 | 61-100 |
| 決勝提出 | 100-72 | - | 88-100 |
| バグ修正 | 100-61 | 100-88 | - |
(これらAIはパラメータのみが異なる。ただし、ベースはパラメータすべて0と考える。)
最後に
CODE VSで入賞したいからまた開催してください～～～～～
ここからは予選～決勝のログ(を整理したもの)です。
10/18
「オンライン機械学習」を買った。
シミュレータを実装した。
ランダムAIを書き、ランダムAIと対戦させ、1ターン後の盤面が自分のシミュレーション結果と一致しているか確かめた。
10/19
連鎖のスコアを計算するようにした。
評価関数を書いた。1個のブロックを全ての場所に落としてみて連鎖の最大スコアを評価値とする。
chokudaiサーチを書いた。
一人ゲームとみなして評価関数を評価する準備をする。200ターンシミュレーションして得られるスコアを計測できるようにした。
ちゃんとログを見たら評価関数が重すぎてまともにchokudaiサーチが動いていなかった。
高速化を頑張る。
最初に連鎖が始まるかのチェックを入れるようにして7割枝刈りできた。スコア1597。
探索の深さを10から3に変えて1889。
10/20
ビットボードを書いた。
デバッグ出力を読みやすくした。
機械学習のためのデータを取るためのコードを書く。
さらに高速化する。
重複消去は効果がないと思っていたが、入れたらけっこう重複が消えた。スコア2138。
10/21
ケイマに点数をつけた。
ケイマありで2094点(22回平均),なしで2025点(28回平均)でありのほうが若干強そう。
CODE VS 2.1の動画やブログから情報を漁りまくる。
人のコードを参考にしてシミュレータを1から書き直す。
2倍くらい速くなった。
細かい高速化を入れた。
10/23
Javaからgnuplotを触れるようにした。
学習をさせたら、
・非オジャマブロックが多いほど連鎖スコアが大きい
・非オジャマブロックが少ないほど連鎖スコアが伸びやすい
ことが分かった（当たり前）
機械学習で得たパラメータを利用した評価関数を作ったら対戦では弱くなった。
でもお邪魔ブロックの置き方はうまく、また大きめの連鎖を作る能力では勝っていた。
スコアは1826点。
Adagradについて調べた。
現在スコア(X) vs 5ターン後スコア(Y)
損失関数の値が小さくなっていく様子
10/24
threepipesさんのリプレイを見て、21ターン450点を目標にした。
21～25ターン目に発火させた時のスコアのlogを特典とする新しい評価関数のテスト方法を作った。
ひたすら色々な評価関数をためしてみる。
何やっても強くならないと嘆く。
10/25
オジャマ計算がバグっていることに気づく。
評価関数で一番強かったのは連鎖数とlog(連鎖スコア)の線形和(4.94)
機械学習の方は4.83
10/26
連鎖を逆再生して、和が10になって消えたブロックの組が元々どの位置にあったか検証してみる。
連鎖前まで巻き戻した場合
1連鎖巻き戻した場合
4位のやつ(フネって呼んでる)は全巻き戻しバージョンだと7位。
リファクタリングをした。
10/27
AWS上で教師データの生成プログラムが動くことを確認した。
出現しやすいパターンに加点するやつを試してみたけど微妙。
(これは探すパターンの種類を増やしすぎると遅くなるというのも関係しそう)
頻出のケイマ・大ケイマ・フネによる2連鎖に加点するのを作ったら結構強かった。
10/28
夢でパラメータ調整をしていた。
colunさんのCODE VS説明スライドを見た。
下に進む連鎖がよいなら、下に進む2連鎖の形を評価するようにした。まあまあだった。
ネクストに発火点のブロックがあったら加点する評価関数を考えたが微妙だった。
発火点の高さに点をつける評価関数、足場になるようにブロックを捨てるように積んでしまい微妙。
10/29
どうしても強くならないので強い人の動きを見てみた。(この時omuさんがトップ)
特別なことをしているようには見えなかったので、自分のAIを見直してみた。
探索時間を500msから1200msにして探索深さを4から8に上げたらめちゃくちゃ強くなった。
そんなことだったのかとショックを受けた。
発火したノードは展開をやめて別のところで処理するアイデアが出てきた。
思ったより探索時間を長くしたり深さを上げる効果があった。
ビームに思ったより多様性がある？
ビームの中を可視化するために雑にdotを吐いてgraphvizに投げたら見れないのが出てきた。仕方ないので葉ノードを省略したら見れるようになった。
見てもよくわからなかった。
初手は全探索してそこから別々にビームサーチしてみたら弱くなった。(さすがに無駄が多すぎる)
10/30～11/02
(ここはログを残していなかった)
11/03
おじゃまが降ってきた時の、おじゃまが減る数の計算が間違っていたのを修正した。
前のターンの計算結果を保存するようにした。これで旧バージョンに100-80
この2つで結構順位が上がった。
発火点を伸ばしていくほうがきれいな連鎖が組めそう。
発火点周辺のパターンから特定のパターンを用いて連鎖を伸ばして、それに近くなるように詰むと特典になるような評価関数のことを考えてみた。
かなり考えたけど暴発などの制御が難しく、ある程度妥協しながら実装したら最終的に弱かった。
11/06
負け方を観察すると過半数はファーストの打ち負けだった。
オジャマを送る数が一定以上になったらオジャマx1000点を加算して無理やり発火させていたので、そこを良くする方法を考えた。
発火ノードを展開せずに別に保存しておいて、発火の候補から威力とターン数のバランスを見て良さそうなやつに向かうようにした。
凝視のことも考えたが、計算コストに対して割に合わなそうなのでやめた。
11/07
一時的ではあるが1位になったりした。
EC2に課金して教師データを生成し始めた。
ところでx2largeやx4largeで動かしたけどどちらもCPU使用率を100%にできなかった。
これの原因は未だに分かってないのだけど、メモリ律速になっているのが有り得そう。
11/08
連鎖の候補を列挙できるようになったので、1人ゲーのAIを改良して再測定した。
増えた教師データで学習させたりしたけどあまり変わらなかった。
1000次元のパラメータが多すぎるという可能性を考えて、学習結果の係数が大きい所だけに注目して、特徴量を人力でチョイス。
人力次元削減(大嘘)
77-48で強くなった。
11/14
タイから帰ってきたら学生7～9位くらいに居て焦る。
最後に苦し紛れのパラメータ(思考時間とかの自動調整出来ない方)調整をして終了。
数日して決勝進出が確定。
11/29
CODE FESTIVALくらいまでの間全然やる気が起きずなにもしてなかった。
オン対戦再開してほしかった。
教師データを増やすべく自分の少し古いAIと対戦させ始めた。
Diverse Beam Searchという手法について論文を呼んだ。
要するにビームに入っているノードに近いと減点するような評価関数を作ると多様性が上がるよみたいな話だと思った(雑)。
多様性を上げるために、今までに探索した盤面とのハミング距離を取ったり、発火点の位置を比較して類似盤面の評価を下げるような工夫をしたが強くならなかった。
11/30
最初の発火までは長めの思考時間を使うようにした。
自己対戦では当然強くなった。なので多様性以前の問題という可能性も出てきた。
本番環境において、スレッド数1と2での処理性能の差を測ろうとしたが、時間ではなく繰り返し数を指定しているのにAIの動きが変わってしまい、比較できなかった。
(振り返ってみるとこれは競合している証拠だった)
合議制ビームサーチってのは評価関数を複数もって、それぞれの上位を採用するやつ。takaptさんのququeをわけるのと発想は同じ。 #codevs
— not (@not_522) 2016年3月22日
合議制ビームサーチでググってもそれっぽい情報が出てこないし、英語で何というか分からないのでこのツイートから想像で書いてみた。
めっちゃバグった。
12/01
冷静に書き直したら合議制beam-stack search(?)が書けた。
普通のbeam stack searchとあまり強さが変わらないのでやめておいた。
評価関数や思考時間と強さの関係を探ろうと色々対戦させるが、直感と違う結果が出て混乱する。
実は思考時間1500msと2500msで強さがそんなに変わらない説が出て、敵の盤面を考慮するAIを考えてみた。
時間の制約上、沢山の分岐は考えられないので、自分が最速で発火した場合に刺さるかどうかを検証して使うようにしてみた。
が、刺さると分かるケースがかなり稀で、刺さると分かった場合は発火を急がなくても勝てることが多く、ダメだった。
(これ以降日付の記録がなくて不明)
合議制はやっぱりダメそうだった。
評価関数を色々ためしたが結局予選最終で使った奴が強かった。
結局予選とほぼ同じ動きのAIを出した。
提出後
機械学習にバグがあったことが分かった。
決勝後
複数スレッドの場合に評価関数内で使いまわしている配列で競合することが分かった。
