🔙 Back to Top

Sun Nov 8 05:40:34 JST 2015

CODE RUNNER 2015 予選B

こないだありました. 86位で本戦に出場します.

CODE RUNNER 2015 予選B Write Up

もうソースコードが手元に無いのだけれど、覚えてる内に覚えてることを書く.

問題

問題ページは 予選 B 問題 であるが、ログインしないと読めないので、概略を書く.

状態について、

  1. ユーザーは、部屋に入っているか入っていないかの状態を持つ.
  2. また、パワー (整数値) と、スコア (整数値) という状態を持つ.
    1. 初期値として、部屋に入っていない、パワー 0、スコア 0.

操作について、

  1. ユーザーが出来る操作は2つある
    1. 部屋に入っていないのなら入る、さもなくば、部屋の中において攻撃を行う
    2. 部屋の情報を見る
      1. 部屋に入っているとき、部屋の情報を JSON で得る (テキストで得ることもできる)
      2. さもなくば、部屋に入ってないよ、的な短いテキストが返ってくる
  2. 本当は他にも、他のユーザーについての何か情報を得る操作があるけど、使わなかった.

部屋について、

  1. 部屋に入ろうとすると、3人がマッチングなされて、一つの部屋に割り当てられる
  2. 部屋には 10匹 のモンスターが一列に用意されている
    1. モンスターには HP (整数値) が割り振られている
      1. どんなHPを持つかについては事前情報はない
      2. 部屋の情報を見ることで知る
  3. 後述する攻撃によって、モンスター10匹が全員いなくなるか、入室してから1分すると、自動的に退室される
    1. 自ら退室はできない
  4. 退室時に、3人のユーザーに順位が与えられる
    1. 順位は、部屋中で、それぞれのユーザーが、削ったHPの合計で付けられる
    2. その順位に応じて、ユーザーそれぞれにスコアが与えられる (加算される)
      1. 普通に1,2,3位と順位が付けば、1000,600,300点である
      2. 同順位が着くと、1,1,3位、じゃなくて2,2,3位、のように悪いように付けられて、600,600,300点が与えられる

パワー、攻撃について、

  1. パワーは始め 0 であるが、(現実の) 時間 (ミリ秒) と共に自動的に増加する
    1. まだ一度も攻撃をしたことないユーザーは、ゲーム開始時刻から、今の時刻の差 (ミリ秒) の2乗のパワーを持つ
    2. あるいは、前回の攻撃をした時刻から、今の時刻の差の2乗 のパワーを持つ
  2. 攻撃という操作は、一列の先頭にいるモンスター一匹に対してのみ行う
    1. 攻撃をすると、自分の持っているパワーだけ、攻撃されたモンスターのHPが削られる
      1. 削られるHPとは、パワーとHPの最小値である
      2. パワーがHPを越えていれば、削るHPはHP分だけである
    2. HP 0 になったモンスターは即座に列から外れる
    3. 攻撃が終わると自分のパワーは 0 になる

部屋の情報について、

  1. 入室しているとき、部屋の情報を取ることができる
  2. 部屋の情報とは、残っているモンスターのHP全て、自分のパワー、部屋にいる各ユーザーの、部屋中で削った総 HP
    1. 他にもあったかもしれない

スコア、ゲームの勝敗について

  1. スコアは退室時に加算される
  2. 現実時間の1分ごとに5%減少する
  3. ゲーム中のスコアの最大値で、ゲームの順位がつく

考えたこと

パワーは時間の二乗だから、例えば、1ms待って攻撃を2回するより、 2ms待って攻撃を1回する方がよい. しかし、他のユーザーもいる. 他のユーザーが先に攻撃してモンスターがいなくなっては、攻撃はできない. ギリギリまで待って、一回、大きな攻撃をするほうが良い.

初めは、手で、数秒待って攻撃、を繰り返して、観察した. モンスターのHPは、多くは10進法で6桁、たまに7桁のようである. 他のユーザーのパワーが無い時に、 7桁のHPを持つモンスターを、一撃するとかなり有利だ.

ここまでで、次のようなメインと成るスクリプトを書いた. このスクリプト自体は大した意味がないので、最後までこのままだった.

#!/bin/bash
# main.sh
curl $APIURL # 入室

while :; do
  curl $GETINFO > info.json
  if [ テスト ]
    curl $APIURL # 攻撃
  fi
  sleep 0.5
done

入室も攻撃も同じAPIなのが困る.

  1. 初めに入室をする
  2. 次をループ
    1. 部屋の情報を得る
    2. 情報から何か調べて攻撃するタイミングであるかを計算する (テスト)
    3. 攻撃するタイミングなら攻撃する

部屋の情報は json で来るので、info.json として保存して、テスト中でこれを読む. 退室された時は、部屋の情報について json ではなく、 なんか適当な文字列が帰ってき、テストの中で失敗するので、 失敗したらプログラムを停止する、みたいな例外処理も、実際には書いた.

従って、 次のように動かす.

while :; do bash ./main.sh; sleep 0.1; done

while ループのなかで、一つの部屋についての処理が完結される、という想定.

今までのCODE RUNNER での自分のやり方であるが (これで成功してきたわけではないのだが)、 まず、他のユーザーの情報を使わず、できるだけ少ない情報だけを処理して、割と勝てるやり方を模索して、 成功したら、徐々に他のユーザーの情報も使うようにしていき… とやる.

テスト

まずはじめは、 HPの大きなモンスターが先頭にいて、十分にパワーを持っていたら攻撃をする、 みたいなテストを書いた.

使うデータは、自分のパワー \(p\) と先頭モンスターの残りHP \(hp\) だけ.

  1. \(hp > 2e7\) and \(p > hp/2\) ならば攻撃
  2. \(hp > 1e7\) and \(p > hp/1.5\) ならば攻撃
  3. \(hp > 5e6\) and \(p > hp\) ならば攻撃

初期はこんなんだった. 気持ちとしては、すごい強い敵のHP半分以上削れば、他のユーザーは自分より少ないHPしか削れなくて、有利だろう.

この時点で200位くらいをじっとしている

他の方が話すに、次のような戦略を取る人が大半だったらしい:

で、他のユーザーの削った総HP数 (言いにくいな) をようやく使う.
自分のそれを \(h_0\) 、他ユーザーのそれを \(h_1, h_2\) (\(h_1 > h_2\)) とする.

想像で次のような条件を追加した.

  1. 「勝ちすぎている」場合、攻撃をしない.
    1. 勝ちすぎているとは、\(h_0 > 2 h_1\) とした
  2. 「負けすぎている」場合、攻撃する
    1. 負けすぎているとは、\(2 h_0 < h_2\) とした

動かしてみて、最後の追い込みが足りずに負けることがわかった. つまり、最後のモンスターは弱くても、自分のパワーがちょっと小さくても、攻撃すれば部屋1位とれた、というケースが見られた. それに、パワーは、ある程度大きくなったら、使わないと損なのである. もちろん、次の部屋ででかいモンスターと当たれば、先制攻撃ができるが、 目の前の一位は取った方が良い.

上の「負けすぎている」を修正する形で、次の「逆転できる」を追加した.

  1. 「逆転できる」場合、攻撃する
    1. 逆転できるとは、\(h_0 + min(hp, p) > h_1\) である

結果的には、これは良かった. ポイントとしては \(h_2\) は見ないことである. これは2位を目指さずに常に1位を目指していることである. まあ、それはどうでもよくて. 部屋中序盤はともかく、中盤以降、 \(h_1\) の人は \(h_2\) の人に較べて優秀なのだ. その人の \(h\) を参考にして、合わせることは意義がある.

序盤でこれを使ってもしょうがないので、 \(p > 1e7\) の条件の下で、この「逆転できる」を、「負けすぎている」の代わりに用いた.

動かしてみると、まあまあ割と勝てている. 他ユーザーの情報を使ってようやく、ランキングも上がってきた.

50位くらい

よくよく考えると、退室時の \(h_0 + h_1 + h_2\) というのは、入室時に決まっていて、 モンスターのHPの合計値である (タイムアップによる退室のことは考えないことにした). ということは、いくつHP削れば絶対に勝てるか、というのは見積もれるのである.

現時点の \(h_0, h_1, h_2 (h_1 > h_2)\) と、 モンスターのHP の列 \(hp_0 .. hp_n\) を使って \[h_0 > h_1 + \sum_i hp_i\] ならば、相手がどうやっても自分は勝つことが分かる (既に勝っている). 先ほどの 「勝ちすぎている」は、それはそれで良く効いていたので、 それは残して、「既に勝っている」を頭に追加した.

逆に、残りのモンスター全員を自分一人で倒しても、勝てない場合も、もしかしたらある. 「既に負けている」も、同様に追加した.

最高で29位までいった

あとは、各パラメータを動かしながら調整した. ただ、そのころには他の人たちのAIも強くなり、 特にランキングも上げられなかった. 最後の方なんて、1/3の確率で部屋1位を取る運ゲーみたいな形になっていた.

他の方たちも口にしていたが、 先頭のモンスターの残りHPが少なすぎて誰も攻撃したがらず、譲りあう、 囚人のジレンマ状態を、打破できなかったこと.

また、早く退室できれば、時間あたりの稼げるスコアが高くなる、という戦略に、 終わってから気付いたが、 しかしどうすれば早く終わらせられるかは難しい.

副作用的な嬉しさとして、 始めに書いた bash スクリプトは、テストのためのスクリプトファイルを、 テストの度に起動するだけなので、 動かしながらスクリプトファイルを変更すれば、再読み込みしてくれること.