CODE VS for STUDENT 参加記
初戦で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で入賞したいからまた開催してください~~~~~
ここからは予選~決勝のログ(を整理したもの)です。
CODE VS for STUDENT で作ったAI、「MazAI」の紹介
CODE VS for STUDENTの決勝用AI提出が完了しました!
残念ながら、予選通過したバージョンからいい感じの改良ができず、実質的にはわずかなバグ修正だけで終わってしまいました。
予選通過したときの記事にも貼ったAIの動画がこれです↓
youtu.be
提出したAIの内容を紹介したいと思います。
名前は「MazAI」です。
決勝AIは名前が「MazAI-Z」になっています。マザイゼットです。
提出したAIの概要
敵の盤面は見ずに、一人ゲームとして処理した。
評価関数
すべての列に1~9のブロックを落とし、最大スコアの連鎖を記録。
スコア = 連鎖数 * 1000 + log_10(連鎖スコア) * 1000
また、一定数以上の連鎖をしたノードには送ったオジャマ数*1000点を加算する。
このスコアに以下の値に係数をかけたものを足す。
- 予告オジャマ数
- フィールドのオジャマ数合計
- フィールドの色ブロック数合計
- 和が10になる特定の配置の数(5種類)
- 各列の高さ(10列)
- 各列の高さの差の絶対値(9列)
- 最大連鎖
- 最大連鎖の消費ブロック数 / 連鎖数
- 最大連鎖の発火点の高さ
合計30次元
係数は機械学習を使って決めた。
詳しくは後述する。
探索
送れるオジャマの数が200を越えたら即発火する。
ビームスタックサーチ(chokudaiサーチ)を用いた。
ハッシュ(zobrist hash)による重複消去を実装した。
最初の発火までは深さ13・時間2500ms。
発火後は、深さ10・時間1500ms。
発火したノード(お邪魔を一定以上送ったノード)はそれ以上展開せず、ビームとは別に保存する。
発火ノードが存在しない時はビームサーチの結果を普通に使う。
発火ノードが存在するとき、そのいずれかに向かう。
発火ノードのうち、スコアと発火ターンで見て下位互換になっているものは候補から消しておく。
また、送るオジャマの数が200を超える発火ノードは最も早いものだけ残す。
向かうノードはノードのスコア/1.11^ターン数が最も高いものを採用した。
評価関数の係数の自動調整
「将棋 機械学習」でググったら出てきた
近年のコンピュータ将棋の急速な伸びの理由は? | やねうら王 公式サイト
に影響を受けてやってみました。
(けどよく分からなかったので助けてほしいです。)
を盤面とする。
の特徴値ベクトルを小文字でと表すことにする。
特徴値を計算する関数をとすればとも書ける。
ベースの評価関数の評価値を,パラメータベクトルをとする。
機械学習付き評価関数の評価値を次のようにする。
(はとの内積)
このとき、浅い探索の評価値を深い探索をしたときの評価値に近づけるということを考える。
からベースの評価関数の値を用いて手読んだ結果の最良の盤面をと表す。
をを満たす定数として、を調整して次の式を最小化したい。
つまり次式の最小化になる。
ここまで1つの盤面について考えたが、実際は複数の教師データについていい感じになるようにする。
盤面に対して教師データをとする。
個の教師データをと表すと、
に対する目的関数は
で表されて、これを最小化する。
これは微分可能な連続最適化の問題になり、勾配降下法を使うことができるが、勾配の計算が重いので代わりに確率的勾配降下法(SGD)を用いる。
SGDの学習率の更新にはAdaGradを使った。
あとは、特徴量に正規化をかけたりL2正則化を入れた。
は、最終的にはとした。
教師データは実際の対戦における自陣の盤面を使用した。
機械学習失敗話
- 正直、よく分からずに使っている部分があってパラメータおみくじみたいになった。
- 正規化を入れないとヤバかった気がする。(追記:正規化がバグってた)
- 改良したAIの対戦から教師データを取ったらなぜか弱くなったことがあった。
- 教師データの数を増やしたら弱くなったことがあった。
- 特徴量は2000次元くらいのものも試したが最終的に30次元の方が強かった。
- 30次元の特徴量は色々な特徴量をぶちこんだ所から係数が大きいものを人力チョイスした。
- ここを書いていて不安になって機械学習なしバージョンと戦わせ始めたら連敗した
- 追記:2-3くらいの割合で負けた
追記:
takaptさんにtwitterでリプを頂いてやり取りしていたら、正規化する時に分散の計算をバグらせていたことが分かりました。
takaptさんありがとうございました。
を計算するところを1箇所で割り忘れていて[\sigma^2 = N E(X^2) - E(X)^2]を計算していました。
このバグった正規化の結果から何を学習していたのかは謎です。
次元数を減らして強くなったというのは、特徴量の計算時間が減って探索ノード数が増えたという可能性があります。
悲しい・・・
CODE FESTIVAL 2016 参加記
予選
Aで通った.さすがに予選は余裕.
3日前~1日前
研究会での発表で神戸に行って,ついでに姫路城を観光してきた.
その後だったので忙しいと思った.
1日目
新橋からベルサール汐留まで歩いて10分位.
今年もコミュ障不動の構えをやっていたのでコンテストまで暇だった.
海外勢も来ていて英語のアナウンスがあったりして,グローバル感があった.
コンテスト
ABはやった.
Cはちょっと難しい.出力を間違えてWA.ペナルティはないのでどうでもいい.
Dはなぜか半分くらい通らなくて激ヤバ.飛ばしてEへ行く.
Eは部分点が調和級数でNlogNになるタイプのDPだったので取った.
満点は難しそうだったのでFへ.
Fは数え上げだったがかなりスムーズに解けた.コンテスト中一番のファインプレー?だったと思う.
Gは苦手そうだし部分点がないからパス.
Hは部分点だけ取るつもりが誤読で時間がかかった.RMQをStarrySky木にして部分点.
Dを通してないのがさすがにおかしくて,いや合ってるだろうと思ったところを丁寧に書き直したらACしては~~~~~~~~~となった.
おしまい.
35位,日本枠17位.
これはかなり良くて,全体順位で言っても1年目(44),2年目(53)より良い成績だった.
Dでハマらなければ1時間弱増えたかもしれないが他に解ける問題があったかは微妙だ.
I,Jは読んですらいない.
コンテンツ
tourist公演.たまに簡単な文や単語が聞き取れるくらいだったので通訳があって助かった.
飛行機で飛び回ってるという話でめっちゃ忙しそうだと思った.
今年はバッジ集めとかスタンプラリーがないのでのんびりした.
今年の夕飯は良かった.早めに行ったので寿司が食べられた.
Ponanzaの山本さんの公演を聞いた.
これは是非CODE VSに活かしたい.
続いて秋葉さんの公演,ペアプロを見た.
あのつくば大会の問題は面白かった.その時の記事に比が奇数:偶数なら勝ちと書いた気がするけど,2で割り続けて奇数:偶数なら勝ちだったようなので間違っていたかもしれない.
エキシビションはチーム戦なのに0完が2組出て見ててつらそうだった.
今年はホテルまで自力で歩くようでちょっとビックリした.Google Mapに助けられた.
銀座国際ホテルだった.
ホテルは鍵の開け方が分からなくて,他の参加者と開かねえなってやったあとまた別の人に助けられた.
ユニットバスがちょっと広い所が良かった他は普通?
コンビニで牛丼とSpriteを買ってダラダラtwitter見て優勝した.
2日目
十分な睡眠時間が確保できた.
ホテルから会場までは10分くらい.送迎のバスがない分むしろ去年より余裕があったかもしれない.
トーナメント
ラウンド1.Aは苦手そうでパス.
B問題の普通のDPを多倍長👊したら600点が帰ってきて通過出来た.
O(N^3)だと思ったので600点まで取れるとは思っていなかった.
Aは残りの時間で書いたけど最小の部分点さえ取れなかった.
ラウンド2.Aはすれ違う場合がどうなるのか不明で,自明な200点を取った.
Bも読んだけど難しそうで,もしかしたら400点対決になると思って400点を取りに行った.
B200点を提出している間により大きいケースを解く方法を考えていたが嘘しか思いつかなかった.
Bの部分点が落ちていてビックリした.逆転ができそうになく終了.
Aは終わった後よく考えると,ランダムに移動する方は止まる動きをしないので最初に調整して右に動くだけだった.それなら簡単だった.
ラウンド3.オープンコンテストになったので勝ちに行く方より満点を目指した.
AはNKlogNのDPが思いついて書いた.どうも間に合わなくてlogを削る必要があったが分からなかった.
Bは時間も無かったし部分点を取って終了.
Aはスライド最小値を使えばlogを削れると知ったのでスライド最小値をライブラリ化した.まだ原理は分かってない.
リレー
B(Um_nik)チームでやった.
最初は日本人ペアで5問潰すという作戦でやった.
僕のペアはEを担当した.gcdを取ってゴニョる問題だと分かったが,2人ともgcdを空で書けないのでhogloidさんに教えてもらった.
Iを読むが全然わからない.奇素数は解けるなあとか考察してたけどそもそも奇数で解けるらしくこの問題僕は向いて無いなと思った.
Kは問題の意味が分からなかった.
Jが手を付けられそうな雰囲気があった.黒に変えられる白は全体の1/3くらいということと,hogloidさんのヒントから,一つ黒を置く毎に黒の連結成分を3つ減らせばよさそうということが分かった.
すると3列ごとにタテに真っ黒にして,ヨコに適当に真っ黒にするとよさそうなことが分かり,自分が実装する流れになった.
実装を詰めずに書き始めたらかなりバグらせた.(黒い所を塗る,同じところを2回塗るetc...)
助けてアピールをしながらsubmitデバッグをしてた.
一番右の列を埋めたほうがいいよというアドバイスを貰って,実装してN=1000を試したら足りたので投げてAC.
全体の感想
良問がガンガン消費されてヤバイと思った(特にトーナメント)
ACM-ICPC 2016 アジアバンコク大会 参加記 (タイ旅行記)
つくば大会で悔しい思いをしたのもあり、なんやかんやタイに行くことになって、行きました。
チームpoは僕piroz,yosupo,dnkとコーチのhadroriで行きました。
バンコク大会に参加するにあたって特にコーチのhadroriさんや東工大の関係者には色々助けていただきました。
本当にありがとうございました。
結果は3位で、20000バーツの賞金をもらいました。
https://www.acm-icpc.eng.chula.ac.th/2016/asia/bangkok/scoreboard
残念ながら、ファイナル進出はダメそうです。
大会の写真などはfacebookにたくさんあります。
セキュリティチェックが必要です
セキュリティチェックが必要です
以下もう雑に参加記
コンテスト色々
ICPCはチュラロンコン大学で行われた。日本で例えるなら東大である。
海外からの参加者は参加費が6000バーツの参加費が必要になっていたが、その分(?)待遇はとても良かった。
日本のチームにはチュラロンコン大学で日本語を専攻している学生たちがガイドとしてついていて心強かった。
他の海外オンサイトの経験がないからなんとも言えないけど割と快適だと思う。
コンテスト本番
全体ではこんな感じになっていた。
解法 | 実装 | |
yosupo | 6 | 1 |
dnk | 3 | 6 |
piroz | 0 | 2 |
(修正しました)
チームメイトがめちゃくちゃ強くて僕は😇。
yosupoの解法生成の速さとdnkの実装力がとにかくすごい。
最初に12問を3分割して一人が4問読むようにした。
タイの特徴として最後の問題ともう1問が簡単になっているというのがあって、実装の速いdnkが最後の4問を読んでいたと思う。
僕はA-Dを読んだ。Aが難しそうでBがDPっぽくてまあマシ、Cが「は?」でDが幾何の構成っぽくて嫌だなあという感じだった。
Bを考察して解けそうな気分になったけど計算量がダメで、yosupoが考えた方が速そうなので投げた。
G(多分)の解法をもらって、フィボナッチ数の項目の和を求める問題だったんだけど、このタイプの式の計算方法を覚えていなかったのと、2次元配列で愚直な実装をするとJavaだと計算時間が結構ヤバいという事情があって、dnkに解いてもらった。ちょっと申し訳ない。
Bの解法をもらって、実装したら結構バグらせた(4WA)。つらい。
まず複数テストケースをある値についてまとめるという処理をミスって計算時間がおかしくなったり、DPから解を復元する部分をちゃんと理解していなくてヤバかった。
yosupoにめっちゃ助けてもらった。
まだ読まれていない問題を読んで(Hだっけ)「は?」となった。タイは問題文が読みにくいのが多い(今年はマシらしいが)。
その間にDの解法をyosupoから貰って、実装した。つくばのthin polygon(うろ覚え)と本質は同じで、2点が与えられるのであと1点を足して面積が0.5の三角形を作る問題。となるような点を探す。
最初Stern-Brocot木を実装して実は計算時間がやばくて1WA。extgcdにしたらなんとか解けた。extgcdのライブラリを持ってくるのを忘れたのでyosupoのを見た。
この後は問題を読んで分からん~~とずっとなるフェーズだった。
Cが解が大きくなる問題と聞いてJava得か?となったがint128で足りるじゃんと言ってしまいyosupoが実装した。
最後はyosupoのKが通るように祈ってた。
4問解法聞いて2問しか実装してないの、要精進と反省。
バンコク
飛行機に6時間くらい乗ると移動できる。
北半球で冬のはずなのに夏のように暑い。湿度は日本の夏より高い。
プミポン国王が亡くなって服喪期間中に訪れることになった。
タイの人々は全身の半分以上は黒を着ていたと思う。派手な色の服を着ている人は外国人っぽかった。
コンテストも風船が全部白、FAは黒で、ひもの色だけが異なるという仕様だった(わからない)
メシ。
これは焼きそばに近い?油と塩の均一な味がした。50バーツ。1バーツ3円なので150円くらい。
飯屋の机には大体ナンプラーと砂糖と唐辛子が置いてある。これはナンプラーをかけるとおいしかった。
ホテルの朝食とか表彰式のホテルのご飯とかは特にハズレなくおいしいと思った。
辛いものが多めなので苦手な人は注意する必要がありそう。
Bangkok Centre Hotelに泊まった。
高くも激安でもないくらいのホテルで、水回りが結構ボロくてギリギリ感がある。
ホテルからの眺めはこんな感じ。
ホテルの隣のマッサージ店は400バーツで1時間マッサージが受けられて普通に良かった。
アユタヤ
エクスカーションで行った。全然調べてなくて、ガイドの説明もよく聞き取れなかったのであまりよく分かってなかった😇
昔の都でミャンマーの軍に破壊された(ザックリ)
廃墟感がいかにも遺跡という感じでいいと思う。
鶏。
騙された話
アユタヤから帰って来た日の夜、賞金ももらったことだし有名店にでも行くか~という流れになった。
で、バンコクセンターホテル前のトゥクトゥクに乗った。(これが悪名高いことは帰国後に知った)
到着後すぐには僕は気づかなかったが、言った場所と違う店名がわからない謎のレストランに来た。(ヤバい)
Market Price(激ヤバ)の蟹カレーを4人で1つ頼んだ。店員の説明だと1200バーツだったがこれが2000バーツに化けた。
(食べかけでゴメン)
ちなみに表彰式のホテルの飯の次くらいにおいしかった。
騙された外国人たちが次々とタクシーやトゥクトゥクで運び込まれてくるのがいい話感が高かった。
タクシーの行き先には気をつけよう!
CODE VS for STUDENT 予選7位!
総合7位,学生5位で予選通過しました!
予選を通過できて本当によかった・・・
CODE VS 5.0の時から勉強した成果が発揮できたと思います。
CODE VS for STUDENT(公式サイト)は落ちものパズルのAIを作るコンテストです。
実際の試合はこんな感じです。
youtu.be
タテ・ヨコ・ナナメに連続するブロックの数字の和が10になると消えるというルールです。
お邪魔の個数はに比例するので、長い連鎖を素早く組むのが最初のポイントです。
決勝は、12月10日(土)にチームラボ本社で行われます。
今年も配信予定でchokudaiさんやきゃんちさんが来るそうですよ!
12月5日に決勝AI提出なのでそれまでまた頑張ります👊
ACM-ICPC 2016 アジアつくば大会 参加記
6完12位でした. 順位表
国内予選のときのブログはこれ↓
ACM-ICPC 2016 国内予選 参加記 - ぴろずメモ
1日目
秋葉原からつくばエクスプレスでつくばへ移動.
poは移動のスケジュールのマージンが少ない傾向がある.
つくばは町並みが整ってるけど人の密度は高くなくて不思議な感じがした.
プラクティス.
英字キーボードが練習のために買ったのと違う方で残念だった.
B問題で2次方程式の解の公式を思い出すのに時間がかかった.
筑波大学に移動して歓迎会.
スピーチジャンケンに負けてポ😇.嘘を言った.
ホテルが綺麗で良かった.(マークワンつくば)
いいじゃん pic.twitter.com/sKk0s21HCs
— ぴろず (@p_shiki37) October 15, 2016
ARCに参加して300-300-900-1300の900で無理を感じ寝ようとした.
前日までの生活が破滅していたので2時まで寝られずつらかった.
2日目
朝が早くてつらい.
推奨電車時刻をぶっちしてタクシーで移動した.歩かなくていいのでこれは良かった.
コンテスト
まずB問題を読む.
書けそうなのでPCが空いているか聞いたらすでにA問題がdnkさんによって解かれていた.(FA)
Bを普通にAC.
yosupoがCの解法をくれたので実装してAC.
この後幾つか問題を読んで,解ける問題ないなあという感じだった.
ABCDGの5完までは圧倒的速度で,5完時は1位だった.
ここですでに僕は置物になっていた.
大炎上したのがF.
Fの解法をyosupoから聞いたが,自信がなかったので実装をパス.あと,最初に推移閉包を取るのは嘘ということに気づけなかった.
ここで実装を引き受けていたら違う展開になっただろうなあと思う.結果論だけれども.
僕以外が実装しているときは構成ゲーのIを考えたりしていたが全く成果がなし.
Fは最終的に全員で解法を検討してデバッグもしたけど結局ミスに気づけなかった.
反省
前半は本当によかった.
実装に対する自信や幾何やその他難しい問題を解けるパワーがあれば後半置物にならずに済んだかなあと反省.
精進しよう.
チーム戦としては,さすがに国内予選の時よりは大分よくなった.
懇親会
スポンサーの企業ブースが沢山並んでいてお祭り感がある.
問題とそれを解いた人限定の景品を出すスポンサーがたくさんあり大変.
面白い問題が色々配られていて全完はまず不可能という感じだった.
頂いたもの:
すごい関数電卓.
Fixstarsに頂きましたが実はなぜもらえたのかよく分かっていない.
dwangoブースはWA回数に応じて輪投げができるWA投げをやっていて,poにとって有利だったのでやってきた.
うまくいって全部の景品をもらってきた.
- Indeed Tokyo リングノート
Indeedのスタッフに2人ゲーム(先手か後手を選べる)で勝つともらえる.
16x16の格子が与えられ,先手は直線で2分割し,後手は片方を選んで消滅させる.これを先手後手を入れ替えて続けていき,分割ができなくなったほうが負け.
全然分からなくて法則性が見えるまでDPしたりして,結局勝つまで4回かかった.
後手を選び,分割後のそれぞれの長方形のタテヨコ比が奇数:奇数のになるように分割し続ければ勝てる.
感想いろいろ
コンテストの環境は快適だった.
PENDINGがどれくらい待つか分からなくてドキドキするくらい.
DOMJudgeのJavaはpackage宣言がついていてもOKらしい.
スタックもデフォルトで64MB設定になっていたのでやさしい.
贅沢を言うとJava8が良かった.
去年のルールとは異なり英字キーボードしか提供されないのがわかっていたので,急いでLenovoの英字キーボードを買って使うようにした.
for文を高速で打ち込んだりは問題ないレベルにはなったが,使用頻度の低い記号が若干怪しいままだった.
逆に今は日本語キーボードに戻すのも大変なので,これからは英字配列を使う.
ライブラリは色々持っていったが結局高速入出力のみ使った.
これはしょうがないけどイベント中食事が圧倒的に偏る.ホテルの朝食にありがたみを感じた.
今後のICPC
もしかしたら今年まだ開催される海外の予選に参加するかもしれない.
来年は機会があればまた出たい.
ボンバーマン風ゲームのAIを書いてJava世界一になった (CodinGame Hypersonic参加記)
世界12位,日本3位,言語別では1位🎉🎉🎉
(タイトルに大げさな称号を入れたかっただけです)
Hypersonicはターン制ボンバーマンのようなゲームで、生き残ったターン数が長く、箱を壊した数の多い人が勝ちです。
リプレイで雰囲気が分かると思います。↓
https://www.codingame.com/replay/141181004
待機時間が生えたのでCodingame触ります
— カードの更新 (@p_shiki37) 2016年9月27日
codingame以外のことをしなくてもいい空間に2日間入りてえ
— カードの更新 (@p_shiki37) 2016年10月1日
初めは気軽に参加したのだけどやっぱりのめりこんでしまい、論文の進捗が危険になりました。
Code VS 5.0の反省を活かしてAIを作れたのが良かったです。
50位以内でTシャツももらえるので楽しみ。
ソースコードをgistに上げました。
追記:280行目は重複消去を意図していますが、ハッシュ値をセットに入れるコードが抜けていて機能していません。
Player.java · GitHub
以下、振り返りながら何をやったかダラダラ書いていきます。
続きを読む