世界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
以下、振り返りながら何をやったかダラダラ書いていきます。
Wood3～Wood1
Woodリーグはルールが徐々に追加されていく。
AIは最も箱を壊せそうな場所に移動して爆弾を置くのを繰り返すだけでOK。
Wood1では敵の爆風を避ける必要があるので、爆風が来る場所を目標に設定しないようにし、さらに1手先で爆風に突っ込まないようにした。
Bronze
Bronzeからはルール変更がない。
ここでAIを一度書き直した。
100msの思考時間ではまともに探索が出来ないと思っていた。
敵とアイテムを無視し、自分が爆弾を置くのは1手目のみと仮定する。
すると、生き残る方法をDPで高速に求めることができる。
これでフィールド上の爆弾が爆発する8ターン先まで探索した。
DPを生き残るかどうかのbooleanからdoubleにすることで評価値のようにすることができて、木箱への距離を入れることで木箱に向かう動きにした。
最後に、爆弾を置くかどうかの2択を、生き残るターン数や壊せそうな箱の数で決定した。
Silver
DPの評価にアイテムを追加した。
DPの状態にアイテムを取ったかどうかを含められないため、現在地から離れ続けながらアイテムを取れる時のみ加点するようにした。
アイテムの評価は木箱より高くなるようにするとうまくいった。爆風シミュレーションでアイテムを無視していることと相性が良かったのだと思う。
敵の爆弾で閉じ込められるケースが多くなったので、敵が爆弾を持っているときは1ターン目で必ず置くと思ってシミュレーションするようにした。
Gold昇格直前だけ日本1位だった。
このタイミングのAIの動きはこんな感じ。
youtu.be
Gold
AIの思考時間を計測してみたら0.5msの爆速でびっくりした。
時間計測は最初に入れよう(反省)。
爆弾の置き方の効率の悪さが気になってきたので、作り直しを決意した。
ルールを読み直したら思っていた処理順と実際の処理順がかなり違っていた。
作りなおしの考察と実装に2日かかり、その間にギリギリLegendaryに昇格した。
Legendary
ビームサーチ+重複消去を実装した。
盤面のハッシュ値にはZobrist Hashingを用いた。
爆弾シミュレーションの高速化のため、盤面のハッシュ値をキー、次の盤面(と付加情報)を値としたマップを持って、既にシミュレーションした盤面を再計算しないようにした。
アイテムを取ったり爆弾設置をしなければ爆発シミュレーションの結果は変わらないので、再計算を避ける効果は大きいはず。
ビームサーチのノードのハッシュ値は(盤面のハッシュ値) xor (自分の位置によるハッシュ値)。ハッシュが衝突したら同一盤面とみなして後のノードは破棄する。
アイテムを取ったりすると盤面のハッシュ値が変わるのでスコアが更新されているのにノードを破棄してしまうということは起こっていない・・・と思う。
ビームサーチでは、最初の5ターンは爆弾を置く動きをシミュレーションし、追加で9ターン爆弾設置禁止でシミュレーションした。
5ターンは爆弾の連鎖を作って逃げ切るのに丁度良いと後で思った。
追加の9ターンは爆風から逃げ切れるかの判定に必要な分を確保した。
評価関数は
- 既に壊した箱の数
- これから爆風に巻き込まれるであろう箱の数
- 最大爆弾数
- 爆弾範囲
- 最も近い箱へのマンハッタン距離
を使った。
これで前AIよりかなりまともな動きをするようになった。
特に2ターン目以降にボムを置くことが考慮できるようになったため、
「箱に囲まれている行き止まりに移動して爆弾を置いて帰ってくる」
「連鎖を考慮して計画的に爆弾を配置する」
という動きができるようになった。
改良
ビームサーチをchokudaiサーチに変えたら、実行時間が安定し時間を有効に使えるようになったことで強くなった。
chokudai幅1で繰り返し回数が1000程度、盤面が複雑だと100程度だった。
アイテムが好きすぎて箱破壊数で負ける傾向が強かったので、箱の評価値を上げたら強くなった。
敵を追いかける動きをした後爆破されることが多かったので、最初の動きで、敵が居た位置に移動することにペナルティを設けた。
前を進んでいる敵は自身がギリギリ逃げられるように爆弾を置いていくので、ついていくと詰みやすいし、木箱も壊せない。
このペナルティを実装するために、遷移にスコアを加算できるようにした。(コード中のpermanentScore)
木箱を壊したりアイテムを取るのを先延ばしにしてしまう傾向があったので、木箱の破壊数やアイテムの所持数に応じてpermanentScoreを加算することで素早い行動を促した。
競争が激しいところよりも木箱を独り占めできるほうが都合がいいため、3人以上の対戦では、自分が最も近いであろう木箱の数で加点をした。
これは効果がよくわからなかった。2人対戦でこの点数を入れるとむしろ弱くなった。
最後の方はパラメータ調整職人をして、先延ばし防止の工夫がしっかり機能するようにするなど調整をして終わり。祈る。
やってみたかったこと
有効な動きはそんなにないので、目的を数種類設定して数ターン一気に飛ばすビームサーチとかやったら面白そうなんじゃないかと思った。
なんとかして爆弾ありで10ターン程度読めば序盤の2個目の爆弾も考慮できて良かったかもしれない。
というか、探索ターン数のパラメータは全然触らなかったので変えたら何か起こるかもしれない。
箱がなくなったときの攻撃。
箱がなくなった時、相手の隣のマスに移動できたら、ボム4個で自爆巻き添えができる。(特に意味がない)
敵を詰ませられるかでボム設置に加点する。
2ターン以上の詰み回避。
コンテスト後にTLでモンテカルロ木探索の話題が上がっていた。
敵の行動を含めた死亡回避には強いのかな・・・？
