6月末〜7月初めにかけて、ICFPのプログラミングコンテストに参加しました。 去年割と良い成績だったので、今年も参戦しました。 ・・・が、今年は難しいのなんの。 メンバーは去年と同じくM氏と二人で。 受験やICPCとの合間で非常に時間的に厳しかったりしましたが、 こういうことに関しては労を厭いません。 そのしわ寄せは、後でなんとかするのだ。
今回はテーマが"再利用"ということだったらしく、 二週間間を空けて二回コンテストが行われた。 一回目が三日間で、二回目がその二週間後に一日間の時間が与えられた。 二回目は何らかの問題変更がなされて、最終的な結果には 二回目の提出物しか考慮されないというシビアな戦いだ。 二週間も間があるのなら、その間ずっと作っていた人が有利なんでは なかろうかとも思うところだが、そんなに甘いものではないということが 二回目の問題発表で判明する。
とりあえず、提出したものを。
正直、今回はあまり大したものが出来た気がしない。 (特に私が担当したところ…)今回のテーマは銀行から金を盗む泥棒ロボットと、その泥棒を捕まえる警察官ロボット(5個)の AIを考えるというものだった。 マップはグラフの形で与えられる。 泥棒は常に警察の位置が分かっていて、どの銀行にいくらお金があるかも分かっている。 移動は徒歩のみ。 警察は移動に徒歩か車が使える。 警察には泥棒の位置が分からないが、隣接1〜2マス(徒歩時2車時1)に泥棒がいればそのにおいを嗅ぐことが可能。 距離いくつのところに泥棒がいるかがわかる。 また、泥棒が8ターンに一回その場所にいた、という証拠を残すので これを元にも警察は泥棒の位置を推測することが出来る。 泥棒が銀行に盗みに入ったときは警察に位置がばれてしまう。 マップ上には車しか通れない道が存在する。 そのような道は(地理的に)非常に遠くをつないでいるので、 結果的に車を使うと速く移動できる。 銀行は(すべての銀行を一度襲撃すればゲーム終了になるのを防ぐために？) 盗難が発生すると、その何ターンか後にほかの銀行から、 全銀行の保持金額が均等になるように、金が補充される。 泥棒は逃げ切れば盗んだ額が得点になり、つかまれば0点になる。 警察は捕まえると守った額(+ボーナス)が得点になって、 捕まえられないとボーナスのみが得点となる。(んだったような気がする)
実装は去年と同じく「目利きのハッカーが選ぶ言語」のHaskellで。 今回は泥棒と警察を作らないといけなかったので、自然に私が泥棒、M氏が警察という分担になった。 そのほか、私はプロトコル部分の実装も行ったりした。
というわけで、私は泥棒の実装を行ったわけであるが、 正直どうやったらいいのかさっぱり。 いつものとおり、まずは簡単に考えてみる。 グラフの解析ルーチンをささっとこしらえて一番金のある銀行に最短距離で移動し続けるものを作った。 とりあえずこれは難なく完成した。 今回はあらかじめ提供されていたシミュレータを用いてシミュレーション。 これが重いのなんのって。PLT-Schemeで書いてあったようだが、もっとまともに作れないのか。 コンパチブルなものを作ってしまおうかとも思ったけど、めんどくさいからやめた。 ここでとりあえず盗みまくるものが出来たわけだが、ちゃんと動く警察のAIが無いから、 それ以上はどうやって作ればいいのかなかなか考えられない。 翌日ぐらいにM氏がそれなりに捕まえられるAIを作成。 これがまぁ、なんともあっさりと泥棒を捕まえてくれる。 というわけで、ちゃんと逃げられるものを作ることに。 まず、逃げるかどうかを判断しなければならないが、 これはどのぐらい近くに警察がいるかなどによりスコアをつけ、 そのスコアが閾値を超えていたら危険と判断して逃げることにした。 そして逃げるべき方向であるが、これも 警察からどの程度遠いかによってスコアをつけて、 最も安全と判断される場所に移動することに。 これで多少なりとも逃げられるようになるが、 着々と進化を続けるM氏の警察の前には連戦連敗を続ける。 狭い銀行(袋小路にあるような銀行)を襲うと、ほとんど一瞬で詰んでしまったりするので 狭い銀行は襲わないようにしたり、 逃げているときに狭い場所(逃げ場の少ないところ)に逃げてしまうことが 多いので、安全度にその場所が開けているか(今回は単手数で移動可能な場所が多いところ、とした) を加味するようにしたり、いろいろパラメータをいじったりして、 Firstバージョンの期間が終了した。 いろいろがんばったおかげで、提出した泥棒は提出した警察からは なんとか逃れられるようになっていた。
そして、二週間後。Twistバージョンが発表される。 あまりにも変わりすぎですがな！ とりあえず大まかに言うと警察が泥棒に味方できるようになったということである。 警察は裏切ることが出来て、一度裏切ったらもう元には戻れない。 裏切った警察は泥棒が逃げ切れば盗んだお金の一部をもらえる。 正義の警官は、ある警官が怪しければ告発することが出来る。 告発が正しければ、告発された警官は抹消される。 そして、脳を正義の警官に乗っ取られる。(この辺、警察やら泥棒やらはBotで、 Brainによって動かされているという設定。BotとBrainはTwistバージョンでは違うかもしれない) つまり、告発に成功したら二台分動かせるようになるということ。 そして、その動かしている方の分のスコアももらえる。 実質スコアが倍になるということ。 ただし、告発が失敗するとペナルティーとして、スコアが半分にされる上に 二度と告発が出来なくなる。 泥棒側だが、暗黒面に堕ちた警官と相談できるようになる。 つまり、今回は泥棒側もプラン提示、投票を行わなければならない。 警官プロトコルめんどくさー、とか思っていた私も結局同じようなものを作らなければならないことに。 また、裏切りたい警官が一人もいなければ、誰か一人を(金を払って)蹴飛ばすことが出来る(というか、義務が生じる)。 これによって、裏切りが無くとも多少逃げやすくなっている。 そしてここ、重要なことだが、期限が24時間しかない。 全くゲーム性の変わってしまったものに対して24時間でまともなAIを作れというのだ。 まぁでも、明らかに常人には無理でしょう。 それなりのものを作れば良いに違いない。 というわけで、泥棒側の戦略である。 まず、プロトコルが結構変わったので、それに対応。 Haskellだったので？改変はスムーズに完了した。 泥棒の戦略だが、上記のような使用を全活用するのはほとんど絶望的なので、 今回もやはりシンプルな戦略で行くことに。 (Firstバージョンでも泥棒と警察がそれなりに良い勝負だったし、)さらに泥棒に対して有利な条件になった 今回のバージョンではもっとつかまりにくいと考えて、 警察は基本的に仲間に入れないことにした。 警察を仲間にすると自分の取り分が少なくなる。 ただし、つかまってしまうと元も子もないので、 やばくなったら仲間に入れることにした、 やばい、というのも適当な基準だが、周りの状況をみて囲まれたっぽいような状況になれば、 やばいと判断。 仲間に出来る警官がいなければ最も近くにいる警官を蹴飛ばす(というか、そうしなければならないんだけど)。 仲間にした警官は、とりあえず泥棒からある程度の距離のところをうろうろしてもらうことにする。 そういうプランを泥棒は提示するけど、それが投票で否決されても、泥棒は自分勝手に行動する。 警察のプランは見ない(面倒なので…)。
というわけで、こんな感じなのだが、やはりというかなんというか、 こうやって書いてみてもしょぼさが漂っている…。 とくに駄目なのが逃げの部分。 警察から単に遠くに逃げるので、 角に追い詰められると一瞬で負ける。 つまり、警察の横を突っ切って広い場所に出る、ということが出来ない。 これを自然に入れるのなら、先読みを行わなければならないだろうけど、 どうにもこうにもうまくそれを行う方法が思いつかなかった。 やっぱり駄目だ…
M氏に書いてもらうしか。私は知りません。
ICFPエッセーに私が書いた分。 とりあえず、上の文章よりはまとまっていると思う。
・ロバーのアルゴリズム
近くにコップがいるかどうかで危険度を判別。
・危険度が基準以上なら、
→ 逃げる
なるべく、安全(コップから遠い)で開けた(ある手数で移動できるマスの数の多いところ)
ところに逃げる。
コップから遠いところに逃げるので、非常に角に追い詰められやすい。
これに対する対策は次で。
・危険度が低ければ
・近くの(歩数)
・安全な(近くにコップのいない)
・金のある
銀行を襲う
途中、コップににおいを嗅がれない様に、コップを避けてルートを探す。
逃げのアルゴリズムが一時的にコップに近づくがそのほうが結果的に良い場合を
認識しないので、角に追い込まれやすい。
さらに、逃げに入るのはコップに追われているとき、つまり銀行襲撃後、居場所がばれてから。
だから、襲った後、角に追い込まれそうな場所の銀行は襲わないことにした。
具体的には"開けていない"ところにある銀行は襲わない。
・終盤(150ターン〜)は逃げに徹する。が、逃げのアルゴリズムがしょぼいので
むしろつかまりやすくなる可能性もある。
なので、逃げに徹しないバージョンも作った。
裏切りコップの利用法
・基本的に仲間は作らない。
→そもそも、ルールが改変により若干ロバー有利になったので、
もともとのルールでロバーが逃げられるようなチューニングなのであれば、
コップを仲間にする必要がない。
(元のルールではコップ有利な気もするが)
・でも、やばくなったら頼る。
・裏切りコップがいなければ
一番近くにいるのをPushする。
・裏切りコップがいれば
自分の近くにいるのを根こそぎ仲間に。
…しかし、結局あんまりにげられないことが多い。
やばくなってからでは遅かったかもしれない。
良い順位が取れればいいね！