総合7位,学生5位で予選通過しました！
予選を通過できて本当によかった・・・
CODE VS 5.0の時から勉強した成果が発揮できたと思います。
CODE VS for STUDENT(公式サイト)は落ちものパズルのAIを作るコンテストです。
実際の試合はこんな感じです。
youtu.be
タテ・ヨコ・ナナメに連続するブロックの数字の和が10になると消えるというルールです。
お邪魔の個数はに比例するので、長い連鎖を素早く組むのが最初のポイントです。
決勝は、12月10日(土)にチームラボ本社で行われます。
今年も配信予定でchokudaiさんやきゃんちさんが来るそうですよ！
12月5日に決勝AI提出なのでそれまでまた頑張ります👊
6完12位でした． 順位表
国内予選のときのブログはこれ↓
ACM-ICPC 2016 国内予選 参加記 - ぴろずメモ
秋葉原からつくばエクスプレスでつくばへ移動．
poは移動のスケジュールのマージンが少ない傾向がある．
つくばは町並みが整ってるけど人の密度は高くなくて不思議な感じがした．
プラクティス．
英字キーボードが練習のために買ったのと違う方で残念だった．
B問題で2次方程式の解の公式を思い出すのに時間がかかった．
筑波大学に移動して歓迎会．
スピーチジャンケンに負けてポ😇．嘘を言った．
ホテルが綺麗で良かった．(マークワンつくば)
いいじゃん pic.twitter.com/sKk0s21HCs
— ぴろず (@p_shiki37) October 15, 2016
ARCに参加して300-300-900-1300の900で無理を感じ寝ようとした．
前日までの生活が破滅していたので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のスタッフに2人ゲーム(先手か後手を選べる)で勝つともらえる．
16x16の格子が与えられ，先手は直線で2分割し，後手は片方を選んで消滅させる．これを先手後手を入れ替えて続けていき，分割ができなくなったほうが負け．
全然分からなくて法則性が見えるまでDPしたりして，結局勝つまで4回かかった．
後手を選び，分割後のそれぞれの長方形のタテヨコ比が奇数：奇数のになるように分割し続ければ勝てる．
コンテストの環境は快適だった．
PENDINGがどれくらい待つか分からなくてドキドキするくらい．
DOMJudgeのJavaはpackage宣言がついていてもOKらしい．
スタックもデフォルトで64MB設定になっていたのでやさしい．
贅沢を言うとJava8が良かった．
去年のルールとは異なり英字キーボードしか提供されないのがわかっていたので，急いでLenovoの英字キーボードを買って使うようにした．
for文を高速で打ち込んだりは問題ないレベルにはなったが，使用頻度の低い記号が若干怪しいままだった．
逆に今は日本語キーボードに戻すのも大変なので，これからは英字配列を使う．
ライブラリは色々持っていったが結局高速入出力のみ使った．
これはしょうがないけどイベント中食事が圧倒的に偏る．ホテルの朝食にありがたみを感じた．
もしかしたら今年まだ開催される海外の予選に参加するかもしれない．
来年は機会があればまた出たい．
世界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
以下、振り返りながら何をやったかダラダラ書いていきます。
続きを読むhadroriさんからDMが飛んできてよすぽ&dnkチームに空きがあるからどう？と誘われたので参加した。
僕が最年長だけど競プロ的には最弱なのでつらい。
あと、自分だけJavaを使うので若干デバッグで不利かもしれない。
チーム名がなかなか決まらず「po」になった。
http://icpc.logic.cs.tsukuba.ac.jp/team/279830
模擬Bとそれとは別に練習1回やって国内予選へ。
まずBを読んでBを解いた。
ICPC特有の事情によってJavaはテンプレが必要だが、ちゃんと準備してなくて焦った。
難しく無い問題の割に時間をかけてしまった。
次にCの解法が降ってきたのでそれを実装した。
降ってきた解法がやや間違っていたが勘違いだったのですぐに修正できた。
D,Eをチームメイトが実装している間にFを考えた。
前半パートの時点で既に実装が重そうでつらい。
No.348 カゴメカゴメ - yukicoder
を思い出した。
後半パートは(根付き)木の同型判定になることが分かった。
木の同型判定は、部分木の同型判定を行ってマッチングを使うと可能なのは知っていたが、つらそうだと思った。
Fは実装が重そうなので後回しされることになった。
Gの解法を聞きながら「合ってるんじゃない？」とか言ったら不完全で結果爆発炎上した。
結果的にABCDEの5完でアジア地区予選に進めそうなので頑張ります。
懇親会に参加してチーム内反省会をするなどした。
帰って一人二次会(お酒を飲むだけ)をしながらこれを書いている。
結果は、Bリーグで1勝2敗のリーグ3位で敗退となりました。
応援して下さった方々ありがとうございました！
悔しさはありますが、実力相応の結果だと思います。(むしろ決勝に来れたのが奇跡的です)
一方、自分が工夫した部分が決勝でうまく働いているシーンがあってそれは嬉しかったです。
CODE VSが来年も開催されればチャレンジしたいです。
oxxooxoxx 4-5 負け
予選終了から本戦までの間、本戦AIからリスキー行動*1を外したAIを戦わせていたのですが、1-6という厳しい結果でした。
敵分身も使ってくる相手だったので、本戦版でも相性はそれほど良くならないはずです。
ソウル回収効率で言うとほとんど互角に見えます。
私のAIが回転斬に消極的な一方、D0さんは回転斬に積極的に忍力を使うので、D0さんがうまく回転斬を使うかが勝敗を分けていたように見えます。
また、要所要所で敵分身を使ってくるのも効いていました。
ラウンド8では、こちらが回転斬準備で犬に囲まれた時に敵分身を使ってきたので、こちらの分身油断モードが発動しなくなりました。
また、トドメも敵分身でした。
ラウンド9でも、回避困難な状況で敵分身を使われて負けたので、この辺りはキッチリやってくるなあと思いました。
ラウンド1はD0さんが回転斬で忍力を使いきり、なにもしなくても2手詰みとなったので、超高速反復横跳び→移動なし回転斬りが発動しました。
誰にも気づかれてなさそうです。
xooxxooo 5-3 勝ち
予選終了から本戦までの間で15-26でした。
togatogaさんは回転斬のプロですが、超高速は使わないので、超高速低コスト回転斬高コストを引けば勝率は上がります。
本戦では回転斬り高コストが多かったので、そこは運に恵まれました。
ラウンド1では、早くから分身油断が発動していて、最後は犬に囲まれた時に回転斬が低コストにも関わらず使わずに負けてしまいました。
ラウンド7でコスト7高速移動を使っていることに対するコメントですが、より正確に言うと、まず妨害警戒で防御系忍術を使わざるを得ない状況だったはずです。
そして、その中で超高速だけ獲得できそうなソウルが多かったため、超高速を使ったのだと推測します。
ラウンド8は、見応えのある試合になったと思います。(自画自賛)
AIに搭載した機能のほとんどが使われている、自分のAIを象徴する試合です。奇跡か。
まず、敵分身を使われないまま犬30を超えたので、分身油断モードが発動し、左下で犬をすり抜けながらソウルを回収しています。
中盤からは回転斬りで追い上げました。2ターン目に回転斬りを発動した時、出来るだけ多くの犬を巻き込めるような動きをするようにしています。
犬で互角になった後、近くに取れるソウルが無くなり困っているシーンでは、評価値が3ターン連続で悪化した時に発動する分身連打モードで左上に強引にすり抜け、勝利を確実にしました。
最後は2手詰めの落石+ドヤ顔回転斬で締めてます。
私のAIは回転斬の条件が厳しく、コスト6でも4体巻き込めないと積極的に使いません。
他にも、使用後の残り忍力や、このソウル差で犬の差をひっくり返せるかなどを考慮します。
xoxxooxox 4-5 負け
予選終了から本戦までの間で4-14でした。
一切妨害をしてこない相手なので、リスキー行動を解除した時には相性のよい相手になるはずです。
それでも勝てなかったので、colunさんのAIがとても強いと言えます。(バグってるのに・・・)
本戦の試合でも強引な分身を使って勝っている試合がいくつかあるように見えます。
恐らく、超加速のコストの低さよりも、自分身のコストの低さの方が勝率に寄与しています。
自分身コスト2をもっと引ければ分からなかったかもしれないです。
リーグを2勝まみれにしたかったなあ・・・
ラウンド8で詰ませたかのようなコメントをしていましたが、完全に嘘でした。(画面が見えていない)
詰ませが発動したのではなく、相手がスキル無しだと詰むときに、初回とりあえず妨害してみるやつです。
刺さったのはたぶんcolunさん側のバグです。
私はステージで自分の試合結果見るのめちゃくちゃ緊張してました。
冷静なコメント入れられる人々すごい。
結論として勝ちたかったしか出てこない・・・
懇親会では予選の思い出を語れて面白かったです。逃げ切り狙いトークとか。
CODE VS 4.0の時は折れたけどCODE VS 5.0はやれたのは、最初にやるべきことが分かりやすいからということと、オンライン対戦でモチベーションが上がったことだと思います。
最初は犬避けてソウル集めるだけで勝てる→オンライン対戦で強い人の戦法を(可能な限り)パクるで結構行けます。
積極的に攻撃するAIはそうでないAIに比べて難しいので決勝に攻撃AIが少ないのは仕方ない気がします。
さらに、安全志向AI＞攻撃AI＞リスキー行動AI＞安全志向AIみたいな相性があり、
リスキー行動AIは予選だとシルバー～ブロンズの超攻撃AIにレーティング持ってかれるので、決勝に進出するのが難しい状況でした。
それにより安全志向AI優勢の流れが更に強くなった気がします。
繰り返しになりますが、後半リスキー行動取りまくりAIで決勝環境勝てなかったのホント悔しいです・・・
とはいえ、攻撃強くしすぎると殺伐詰み探索勝負になってしまうのでもしかしたらワザと避けているのかもしれません。
CODE VS 3.0とかそんな感じだったのだろうか・・・？
もっと特徴的な戦法も考えたことはあります。
例えば岩の配置を整備し、うまく犬の最短経路を切り替えることで犬を往復させるとか、
忍者に時計回りにグルグル移動することを強制させると実は強いんじゃないかとか。
CODE VS 5.0は本当に楽しめました。恐らく最後？の春休みのいい思い出になりました。
実行可能jarとソースとreadmeが入ってるzipです。
jarをCODE VSクライアントと同じフォルダに置いてreadmeにあるコマンドをコピペすれば多分すぐに動かせます。
本戦のAIより少し強くなっているので是非戦わせてみてください。
ソースはめちゃくちゃ汚いので見る価値は多分無いです。
https://dl.dropboxusercontent.com/u/264857305/pirozAI_v6.zip
(そのうち消えると思います)
*1:敵の忍術使用によって負ける可能性のある行動
決勝用AIの提出が完了しました。
提出完了後TLで感じたのですが、マラソンなどで経験を積んでいる人はやはり違うなあと感じました。
僕が試行錯誤で進んでいる所を当然のこととして一瞬で先に行っているのだろうなあと思います。
なのでここに書いてあることは相当筋が悪いです。
n手先の盤面は、n個の移動経路の評価値の和と、最後の盤面の評価値を足して算出する。
以下、gitの履歴を見ながらひたすら振り返ります。
自分のモチベーション維持にAI名にバージョンを入れるのをやっていました。
とりあえず動かそうという段階。
オンライン対戦での反省を活かしながら実装を進めた。
作り直し。確かシルバーに居て、追い上げるぞという感じだった気がする。
気にするべき妨害は落石と分身。雷撃は即死にはならない。
分身は、自分身を使っていないときは即死にはならないので、考えないことにする。
評価関数は
を入れた。
1手探索で、高速移動、自雷撃、自分身、回転斬を試す。
自雷撃は忍者からの距離3まで。落石対策に関わる範囲がこれくらいなので。
自分身は四隅・犬の出現ポイント・忍者の居るマスを試す。
相手のスキルは、忍者の移動経路上の落石を常に考慮する。
自分身を使う場合は、忍者からの距離2までの敵分身と、分身上の落石を考慮する。
相手が妨害スキルを使ってこない場合にそのスキルへの警戒を緩める、「落石油断モード」や「分身油断モード」を実装した。
「分身油断モード」は実装が悪く、ほとんど機能しなかった。「落石油断モード」は妨害をしないAIにまあまあ刺さっていた。
ビームサーチを実装した。実行速度の関係で、2手目以降はスキル使用なし敵の妨害考慮なしにした。
最初は幅5深さ5とかを設定している(※まるで意味が無い)
評価関数は、盤面の評価と経路の評価を分ける必要性を感じたので、分けた。
盤面の評価は、
経路の評価は、
が該当する。
そして、複数手先の盤面の評価値は、経路の評価値の和+最後の盤面の評価値となる。
ビームサーチを実装したことで実行時間の問題が出てきたのでv3のAI部分を一旦消して、シミュレーション部分の高速化に取り組んだ。
ここで最後の方に実装したのも含めて高速化の話をしてしまいます。
AIはJavaで書いていたのでJavaの話です。
高速化をする上で役に立ったモノ・テクを列挙してみます。
二次元配列のnewの時間がヤバイのでプールを作った。
ターン毎にほとんどの情報を捨てるので、ターン終了時にインデックスをリセットし、最初から順に取り出すということをしていた。
犬の行動をシミュレーションするのに、忍者からの距離をBFSで求める部分がボトルネックになっていたので、岩と忍者の位置を入力、距離の配列を出力としてHashMapに突っ込み、必要に応じて取り出すようにした。
忍者が岩を動かさなければキャッシュにヒットしまくりなのでかなりの短縮になった。
犬を忍者からの距離順・id順にソートする部分に標準ライブラリを使っていたが遅いため専用のソート関数を自作した。
距離は0から100程度までしかない(本当?)ためバケツソートを使う。id順にソートする部分は挿入ソートを用いた。
配列を初期化する時間をケチるために、タイムスタンプを使って、バケツから出し入れするときに有効なデータか判定した。
移動を全パターン試すという処理がよく出てくるので、パターンをいくつかのブロックに分けて突っ込む。java.util.concurrentパッケージ大活躍。
色々高速化して結局一番遅いのはやっぱり犬の移動シミュレーションでした。
おおよそO(犬の数)になったと思うのですがう～ん
v4で高速化が済んだのでv5とした(バージョンの上げ方が適当過ぎる)
高速化が済んだ分探索できる量が増えたので、色々実験をしてどこに計算時間を割けばいいか色々検証する。
ビームサーチのパラメータ調整をした。
パラメータ調整に関する知見が全く無かったので、眺めてみたり自己対戦を重ねた。
色々試した結果、幅15深さ1か幅100深さ2くらいが適当だなあと思った。
深さや幅をこれ以上増やしてもあまり効果が得られなかった。
同一局面除去しないとビームサーチが貪欲と化すので気をつけましょう😇
— ぴろず (@p_shiki37) 2016年3月22日
探索が改良された分、評価関数のペナルティ項の多くを消した。
評価関数、特に何も考えずに忍力1につき100点、ソウル取ることは100点(つまりソウル獲得で合計+300点)
としていたが、忍術を使ってでもソウルを取る方が良い場面の方が多いので、ソウルを取ることの点数を300点にし、ソウル獲得は合計500点になった。
したがって、コスト5未満の忍術を使ってソウルを取れるなら積極的に忍術を使う。
結構動きが良くなるが、コスト高めの高速移動を使いすぎる傾向が出た。
普通のビームサーチの後、ビームに残ったものから追加の細いビームサーチをして、最も良い物を採用という処理を追加してみた。
これは出現するソウルなどを考慮していない分、微妙な動きをしてしまうのであとで消した。
ビームサーチが貪欲に近くなってしまうことの対策として、通常の評価関数で取れるソウルが無くなった時、複数の評価関数を試すという処理を取り入れた。
色々な評価関数を試してみたが、最も効果があったのは、特定の点との岩を無視した距離を使う評価関数だった。
点としては、マップ上の4隅と中央を使った。つまり、困ったときに追加で5つの評価関数を試す。
これにより、近くのソウルが取れない時に大胆な移動をして遠くのソウルを集めることが可能になった。
複数の評価関数を試しても3ターン連続で評価値が悪化する時、「分身連打モード」に移行する。
「分身連打モード」では、敵のスキルを無視し、いずれかの角に自分身を連打しながら最も近いソウルに向かうという動きに限定し、11手の深い探索を行う。
これにより、強引なソウル取得による粘りが可能になった。
なお敵分身には弱いが、敵分身を適切に使ってくるAIは予選のときにはほとんど居なかったので、結果として強くなった。
通常の探索でソウルが取れるまで近づければ、通常のモードに戻る。
v5のAIのメイン部分がスパゲッティ化して頭が痛くなったので、一度リセットしてv6にした。
決勝の前日、最後のリセット。
v3の時にあった「落石油断モード」「分身油断モード」を復活。
これで「落石油断モード」「分身油断モード」「分身連打モード」「秒読みモード」の4つがあることになりif文地獄と化した。
上位陣で回転斬をうまく活用する流れがあったので、回転斬を積極的に使う動きを追加した。
具体的には特定の条件を満たすと、2ターン目に多くの犬を回転斬で倒せるような移動を探索する。
相手が忍術を使わないと落石や分身で詰むようなタイミングで、相手がどの忍術を使うか、あるいは使わないかを記録して、
攻撃をするかどうかの判断材料にする仕組みを復活。
決勝までの間もオンライン対戦をしたいが、油断モードや分身連打モードの対策をされるとマズイので、
実行時引数でこれらのモードを抑制できるようにした。
本戦に向けて並列化などのパフォーマンス改善をした後、基本的な動きの改善を試みた。
忍者同士が固まってしまう問題に対して、
を試した所、後者が良かった。
また、序盤のソウル取得効率が勝敗に大きく影響することに気づいたため、
序盤は、再優先で取得するソウルを指定した評価関数というものを実装し、それぞれで細くて長めのビームサーチを実行。
最も評価がよかった評価関数を採用し、通常のビームサーチを行うという動きを実装した。
序盤のソウル取得効率が向上した。
ここまで忍者からソウルまでの距離計算では、岩は通れないものとしていて実際との剥離が大きかったため、
動かせる岩を重さ3,動かせない岩を重さ10として距離を計算するようにした。
動きはおおむね良くなったが、ソウルが岩で囲まれているような場合や、ソウルが岩でできた通路にある場合にはハマることが増えた。
これの対策にもなるが、2番目に近いソウルと3番目に近いソウルへ向かう評価関数を追加し、
複数の評価関数を試すフェーズに入れた。
複数の評価関数を試すフェーズに早めに突入するために、ビームの中身を見て、1手目から3手目で評価関数が下がるならば早めにこのモードに入るようにした。
複数手詰み探索を実装した。実際に動かしてみると、価値のある詰みを見つけられることはほとんど無かった。
唯一、敵が自分身を使えない時に2手詰みを発見できるので、この場合のみ探索するようにした。
これだけだと勿体無いので、勝ちを確信した時に意味のない動きをする「ダンスモード*1」を実装した。
ちなみにデバッグには役立った。
決勝出るぞニコファーレ行くぞ
ニコ生で放送されるぞ
live.nicovideo.jp
正直決勝進出者は皆強すぎなので勝てる気がしません。
あとは乱数の神に祈って、いい戦いを見せてくれることを期待します。
*1:またの名を煽りモード
CODE VS 5.0の予選を6位で通過しました！
https://codevs.jp/user/ranking/50/
レートが最高点に達したなと思ったら止める戦法で逃げ切りました！
ずるい！
例年通りなら決勝はニコファーレで行われ、ニコ生で中継があるはずです。
体調を崩したりしなければ行くつもりです。
犬を避けながら最も近いソウルに向かいます( ◠‿◠)
NoneAIなどに勝ちます( ◠‿◠)
詰んだら回転斬を使うようにします( ◠‿◠)
NormalAIに勝ち越します( ◠‿◠)
オンライン対戦に行きます( ◠‿◠)
岩が降ってきます(´･‿･｀)
楽しい！！
✌('ω'✌ )三✌('ω')✌三(✌'ω')✌
追記:
CODE VS 5.0に参加していない人向けに訳すと、
最初にやるべきことが分かりやすいルールで、プリセットAIと対戦して強化したり、
オンラインで「そういう戦術もあるのか～」ってなるのがとても楽しいです。
CODE VSを知ったのは3.0の決勝の放送の時で、4.0の時は何もしないAIを書いて飽きました。
5.0は5日から始めましたが、とっつきやすさやオンライン対戦の面白さから熱中してしまいました。
上位勢の動きを見ると、「そんな動きどうやったらプログラムできるんだ・・・」と思います。
私のAIはバランスよく強いというよりは一部の相手に相性が良いようなタイプだと思うので、
予選を通過したのは本当に奇跡的だったと思います。
提出が不利そうだったので踏みとどまったのは正解でした。
ゲーム外の勝負もしていく心構えだったので、躊躇なく逃げ切りに入りました。
最終日のほとんどは順位表に張り付いて通過ボーダーの推移を見守っていました。
決勝のAIを提出するタイミングになったら、予選期間中どんなことをやっていたのかを振り返ってブログに書きたいです。
CODE RUNNERで2位だったので(?)
キャリフル経由でオフィス見学のお誘いがあったので行ってきました！
CODE VS予選真っ只中、CODE VSやCODE RUNNERの開発者の方とお話することになりました。CODE VSのコツは聞けませんでした。
その代わり去年のCODE RUNNERの話は色々できて、今年はもっと面白くなるだろうと思いました。
あと参加記を書くとやっぱりチェックされるようです。適当なこと書けないですね(´･‿･｀)
