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
以下、振り返りながら何をやったかダラダラ書いていきます。
続きを読むACM-ICPC 2016 国内予選 参加記
チーム結成
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完でアジア地区予選に進めそうなので頑張ります。
予選後
懇親会に参加してチーム内反省会をするなどした。
帰って一人二次会(お酒を飲むだけ)をしながらこれを書いている。
CODE VS 5.0 決勝に出場しました
結果は、Bリーグで1勝2敗のリーグ3位で敗退となりました。
応援して下さった方々ありがとうございました!
悔しさはありますが、実力相応の結果だと思います。(むしろ決勝に来れたのが奇跡的です)
一方、自分が工夫した部分が決勝でうまく働いているシーンがあってそれは嬉しかったです。
CODE VSが来年も開催されればチャレンジしたいです。
各対戦振り返り
vs D0
oxxooxoxx 4-5 負け
予選終了から本戦までの間、本戦AIからリスキー行動*1を外したAIを戦わせていたのですが、1-6という厳しい結果でした。
敵分身も使ってくる相手だったので、本戦版でも相性はそれほど良くならないはずです。
ソウル回収効率で言うとほとんど互角に見えます。
私のAIが回転斬に消極的な一方、D0さんは回転斬に積極的に忍力を使うので、D0さんがうまく回転斬を使うかが勝敗を分けていたように見えます。
また、要所要所で敵分身を使ってくるのも効いていました。
ラウンド8では、こちらが回転斬準備で犬に囲まれた時に敵分身を使ってきたので、こちらの分身油断モードが発動しなくなりました。
また、トドメも敵分身でした。
ラウンド9でも、回避困難な状況で敵分身を使われて負けたので、この辺りはキッチリやってくるなあと思いました。
ラウンド1はD0さんが回転斬で忍力を使いきり、なにもしなくても2手詰みとなったので、超高速反復横跳び→移動なし回転斬りが発動しました。
誰にも気づかれてなさそうです。
vs togatoga
xooxxooo 5-3 勝ち
予選終了から本戦までの間で15-26でした。
togatogaさんは回転斬のプロですが、超高速は使わないので、超高速低コスト回転斬高コストを引けば勝率は上がります。
本戦では回転斬り高コストが多かったので、そこは運に恵まれました。
ラウンド1では、早くから分身油断が発動していて、最後は犬に囲まれた時に回転斬が低コストにも関わらず使わずに負けてしまいました。
ラウンド7でコスト7高速移動を使っていることに対するコメントですが、より正確に言うと、まず妨害警戒で防御系忍術を使わざるを得ない状況だったはずです。
そして、その中で超高速だけ獲得できそうなソウルが多かったため、超高速を使ったのだと推測します。
ラウンド8は、見応えのある試合になったと思います。(自画自賛)
AIに搭載した機能のほとんどが使われている、自分のAIを象徴する試合です。奇跡か。
まず、敵分身を使われないまま犬30を超えたので、分身油断モードが発動し、左下で犬をすり抜けながらソウルを回収しています。
中盤からは回転斬りで追い上げました。2ターン目に回転斬りを発動した時、出来るだけ多くの犬を巻き込めるような動きをするようにしています。
犬で互角になった後、近くに取れるソウルが無くなり困っているシーンでは、評価値が3ターン連続で悪化した時に発動する分身連打モードで左上に強引にすり抜け、勝利を確実にしました。
最後は2手詰めの落石+ドヤ顔回転斬で締めてます。
私のAIは回転斬の条件が厳しく、コスト6でも4体巻き込めないと積極的に使いません。
他にも、使用後の残り忍力や、このソウル差で犬の差をひっくり返せるかなどを考慮します。
vs colun
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は本当に楽しめました。恐らく最後?の春休みのいい思い出になりました。
AIをこっそり公開しています
実行可能jarとソースとreadmeが入ってるzipです。
jarをCODE VSクライアントと同じフォルダに置いてreadmeにあるコマンドをコピペすれば多分すぐに動かせます。
本戦のAIより少し強くなっているので是非戦わせてみてください。
ソースはめちゃくちゃ汚いので見る価値は多分無いです。
https://dl.dropboxusercontent.com/u/264857305/pirozAI_v6.zip
(そのうち消えると思います)
*1:敵の忍術使用によって負ける可能性のある行動
CODE VS 5.0 でやったこと
決勝用AIの提出が完了しました。
提出完了後TLで感じたのですが、マラソンなどで経験を積んでいる人はやはり違うなあと感じました。
僕が試行錯誤で進んでいる所を当然のこととして一瞬で先に行っているのだろうなあと思います。
なのでここに書いてあることは相当筋が悪いです。
最終的にできたもの
- 幅100ビームサーチで3手探索。1手目のみ敵味方の忍術を考慮。
- 忍者2人を別々に考えたりはしない
- 序盤は再優先に取得するソウルを変えながら深い探索をし、最も良いものを採用。
- 落石や分身の危険・チャンスを察知し、相手の反応を伺う。
- 最初の落石・分身チャンスはとりあえず攻撃してみる。
- 「落石油断モード」「分身油断モード」
- 相手が分身を使ってソウルを強引に取っていると判断した場合、ソウルに敵分身する。
- 評価値の悪化を検出し、様々な評価関数を試す。
- それでも悪化が続いたら、「分身連打モード」
- 回転斬のために移動する「回転斬準備」
- 相手のソウルが尽きた時、詰み手順探索
- 二手詰みが見つかる程度
- 勝ちを確信したときにダンス💃
評価関数
n手先の盤面は、n個の移動経路の評価値の和と、最後の盤面の評価値を足して算出する。
- 盤面の評価
- 忍力(x100)
- 最も近いソウルまでの距離(x-1) (岩のあるマスは重みをつけて算出)
- 忍者同士が近すぎる時のペナルティ(距離3以下で-2)
- 経路の評価
- 獲得するソウル(x300)
- 回転斬で撃破する犬(x100)
- スキルを使われると即死する場合のペナルティ(状況により-10^5~-0.1)
以下、gitの履歴を見ながらひたすら振り返ります。
自分のモチベーション維持にAI名にバージョンを入れるのをやっていました。
v1~
とりあえず動かそうという段階。
- 犬が隣接していないマスに移動
- 岩は動かせないものとする
- ソウルまでの距離を計算し、最も近いソウルに移動
v2~
オンライン対戦での反省を活かしながら実装を進めた。
- 真面目なシミュレータを作る
- 1手探索。評価関数はソウルまでの距離と、端ペナルティなど。
- 詰んだら回転斬
- 詰んだら超高速
- 移動を落石によって妨害されて犬に捕まりそうな時、自雷撃
- 相手がスキル無しだと落石で詰む場合、敵落石
- 相手に2回回避されるまでやる。相手が防御系忍術を使えない場合は必ずやる。
- 詰んだら自分身
- 詰んだら自雷撃
v3.0~
作り直し。確かシルバーに居て、追い上げるぞという感じだった気がする。
気にするべき妨害は落石と分身。雷撃は即死にはならない。
分身は、自分身を使っていないときは即死にはならないので、考えないことにする。
評価関数は
- 忍力
- 最も近いソウルまでの距離(岩は通過できないとする)
- 壁付近のペナルティ
- 忍者同士が近すぎることのペナルティ
- 忍者周辺4マスに障害物や犬が多すぎることのペナルティ
- スキルを使われると即死する場合のペナルティ
を入れた。
1手探索で、高速移動、自雷撃、自分身、回転斬を試す。
自雷撃は忍者からの距離3まで。落石対策に関わる範囲がこれくらいなので。
自分身は四隅・犬の出現ポイント・忍者の居るマスを試す。
相手のスキルは、忍者の移動経路上の落石を常に考慮する。
自分身を使う場合は、忍者からの距離2までの敵分身と、分身上の落石を考慮する。
相手が妨害スキルを使ってこない場合にそのスキルへの警戒を緩める、「落石油断モード」や「分身油断モード」を実装した。
「分身油断モード」は実装が悪く、ほとんど機能しなかった。「落石油断モード」は妨害をしないAIにまあまあ刺さっていた。
v3.8~
ビームサーチを実装した。実行速度の関係で、2手目以降はスキル使用なし敵の妨害考慮なしにした。
最初は幅5深さ5とかを設定している(※まるで意味が無い)
評価関数は、盤面の評価と経路の評価を分ける必要性を感じたので、分けた。
盤面の評価は、
- 忍力
- 最も近いソウルまでの距離(岩は通過できないとする)
- 忍者同士が近すぎることのペナルティ
経路の評価は、
- 獲得するソウル
- 回転斬で撃破する犬
- スキルを使われると即死する場合のペナルティ
が該当する。
そして、複数手先の盤面の評価値は、経路の評価値の和+最後の盤面の評価値となる。
v4~/高速化
ビームサーチを実装したことで実行時間の問題が出てきたのでv3のAI部分を一旦消して、シミュレーション部分の高速化に取り組んだ。
ここで最後の方に実装したのも含めて高速化の話をしてしまいます。
AIはJavaで書いていたのでJavaの話です。
高速化をする上で役に立ったモノ・テクを列挙してみます。
オブジェクトプーリング
二次元配列のnewの時間がヤバイのでプールを作った。
ターン毎にほとんどの情報を捨てるので、ターン終了時にインデックスをリセットし、最初から順に取り出すということをしていた。
キャッシュ
犬の行動をシミュレーションするのに、忍者からの距離をBFSで求める部分がボトルネックになっていたので、岩と忍者の位置を入力、距離の配列を出力としてHashMapに突っ込み、必要に応じて取り出すようにした。
忍者が岩を動かさなければキャッシュにヒットしまくりなのでかなりの短縮になった。
バケツソート
犬を忍者からの距離順・id順にソートする部分に標準ライブラリを使っていたが遅いため専用のソート関数を自作した。
距離は0から100程度までしかない(本当?)ためバケツソートを使う。id順にソートする部分は挿入ソートを用いた。
配列を初期化する時間をケチるために、タイムスタンプを使って、バケツから出し入れするときに有効なデータか判定した。
並列化
移動を全パターン試すという処理がよく出てくるので、パターンをいくつかのブロックに分けて突っ込む。java.util.concurrentパッケージ大活躍。
色々高速化して結局一番遅いのはやっぱり犬の移動シミュレーションでした。
おおよそO(犬の数)になったと思うのですがう~ん
v5~
v4で高速化が済んだのでv5とした(バージョンの上げ方が適当過ぎる)
高速化が済んだ分探索できる量が増えたので、色々実験をしてどこに計算時間を割けばいいか色々検証する。
ビームサーチのパラメータ調整をした。
パラメータ調整に関する知見が全く無かったので、眺めてみたり自己対戦を重ねた。
色々試した結果、幅15深さ1か幅100深さ2くらいが適当だなあと思った。
深さや幅をこれ以上増やしてもあまり効果が得られなかった。
同一局面除去しないとビームサーチが貪欲と化すので気をつけましょう😇
— ぴろず (@p_shiki37) 2016年3月22日
評価関数が最も近いソウルまでの距離を利用しているからビーム内が似たり寄ったりになると思ったのですが、そもそもの原因はこっちだったかもしれない・・・
つまりビームサーチというよりは枝刈り全探索に近い?
探索が改良された分、評価関数のペナルティ項の多くを消した。
評価関数、特に何も考えずに忍力1につき100点、ソウル取ることは100点(つまりソウル獲得で合計+300点)
としていたが、忍術を使ってでもソウルを取る方が良い場面の方が多いので、ソウルを取ることの点数を300点にし、ソウル獲得は合計500点になった。
したがって、コスト5未満の忍術を使ってソウルを取れるなら積極的に忍術を使う。
結構動きが良くなるが、コスト高めの高速移動を使いすぎる傾向が出た。
普通のビームサーチの後、ビームに残ったものから追加の細いビームサーチをして、最も良い物を採用という処理を追加してみた。
これは出現するソウルなどを考慮していない分、微妙な動きをしてしまうのであとで消した。
ビームサーチが貪欲に近くなってしまうことの対策として、通常の評価関数で取れるソウルが無くなった時、複数の評価関数を試すという処理を取り入れた。
色々な評価関数を試してみたが、最も効果があったのは、特定の点との岩を無視した距離を使う評価関数だった。
点としては、マップ上の4隅と中央を使った。つまり、困ったときに追加で5つの評価関数を試す。
これにより、近くのソウルが取れない時に大胆な移動をして遠くのソウルを集めることが可能になった。
複数の評価関数を試しても3ターン連続で評価値が悪化する時、「分身連打モード」に移行する。
「分身連打モード」では、敵のスキルを無視し、いずれかの角に自分身を連打しながら最も近いソウルに向かうという動きに限定し、11手の深い探索を行う。
これにより、強引なソウル取得による粘りが可能になった。
なお敵分身には弱いが、敵分身を適切に使ってくるAIは予選のときにはほとんど居なかったので、結果として強くなった。
通常の探索でソウルが取れるまで近づければ、通常のモードに戻る。
v6
v5のAIのメイン部分がスパゲッティ化して頭が痛くなったので、一度リセットしてv6にした。
決勝の前日、最後のリセット。
v3の時にあった「落石油断モード」「分身油断モード」を復活。
これで「落石油断モード」「分身油断モード」「分身連打モード」「秒読みモード」の4つがあることになりif文地獄と化した。
上位陣で回転斬をうまく活用する流れがあったので、回転斬を積極的に使う動きを追加した。
具体的には特定の条件を満たすと、2ターン目に多くの犬を回転斬で倒せるような移動を探索する。
相手が忍術を使わないと落石や分身で詰むようなタイミングで、相手がどの忍術を使うか、あるいは使わないかを記録して、
攻撃をするかどうかの判断材料にする仕組みを復活。
pirozAI[6.5.1]、決勝進出!
決勝までの間もオンライン対戦をしたいが、油断モードや分身連打モードの対策をされるとマズイので、
実行時引数でこれらのモードを抑制できるようにした。
本戦に向けて並列化などのパフォーマンス改善をした後、基本的な動きの改善を試みた。
忍者同士が固まってしまう問題に対して、
- フィールドを4分割し、同じエリアに入っていると減点
- 忍者同士の距離が3以下だと減点
を試した所、後者が良かった。
また、序盤のソウル取得効率が勝敗に大きく影響することに気づいたため、
序盤は、再優先で取得するソウルを指定した評価関数というものを実装し、それぞれで細くて長めのビームサーチを実行。
最も評価がよかった評価関数を採用し、通常のビームサーチを行うという動きを実装した。
序盤のソウル取得効率が向上した。
ここまで忍者からソウルまでの距離計算では、岩は通れないものとしていて実際との剥離が大きかったため、
動かせる岩を重さ3,動かせない岩を重さ10として距離を計算するようにした。
動きはおおむね良くなったが、ソウルが岩で囲まれているような場合や、ソウルが岩でできた通路にある場合にはハマることが増えた。
これの対策にもなるが、2番目に近いソウルと3番目に近いソウルへ向かう評価関数を追加し、
複数の評価関数を試すフェーズに入れた。
複数の評価関数を試すフェーズに早めに突入するために、ビームの中身を見て、1手目から3手目で評価関数が下がるならば早めにこのモードに入るようにした。
複数手詰み探索を実装した。実際に動かしてみると、価値のある詰みを見つけられることはほとんど無かった。
唯一、敵が自分身を使えない時に2手詰みを発見できるので、この場合のみ探索するようにした。
これだけだと勿体無いので、勝ちを確信した時に意味のない動きをする「ダンスモード*1」を実装した。
ちなみにデバッグには役立った。
もうすぐ決勝
決勝出るぞニコファーレ行くぞ
ニコ生で放送されるぞ
live.nicovideo.jp
正直決勝進出者は皆強すぎなので勝てる気がしません。
あとは乱数の神に祈って、いい戦いを見せてくれることを期待します。
*1:またの名を煽りモード