(ルール変更前の)CODE VS 4.0

CODE VS 4.0について、ルール変更がアナウンスされる前後に調べていたこと、やろうとしていたことについて少し書いておきます。

内容は以下の2つです。

• 最終的なスコア(ターン数)はどうなるか
• 相手ユニット数からのAIの判別

最終的なスコア(ターン数)はどうなるか

Extraモードが追加される前は、数十人が全ステージをクリアし、各ステージの相手を倒すまでのターン数の合計の少なさが順位を決める大きな要因となっていました。

CODE VS 4.0では、複数回の提出の中から一番よかったものがその参加者のスコアになります。そのため、プログラムが出すスコアの平均だけではなく、分散も影響します。同じプログラムで試行を続けた場合での最終的なスコア(つまり、複数回挑戦した中で一番いいスコア)がどうなるか予想できればと思って少し調べたことを書いておきます。

合計ターン数が、正規分布に従うと仮定しました。ステージは各AIについて3回ですから、ターン数の合計が正規分布に従うという仮定は適切でないかもしれませんが、いい方法を知らなかったのでこれでやってました。

What Is the Expected Value of the Maximum of N Iid Normal Variables? - Quora

上のリンクの中に、正規分布からn個とってきたときの最大値の期待値の近似式が載っていました。標準正規分布でn個の変数を取ってきたときのr番目の値の期待値はだそうです(は標準正規分布の逆関数)。この式を使って、たとえば今のプログラムが全ステージクリアしたときにかかるターン数の平均が5000、標準偏差が150、あと100回全ステージクリアできると仮定したら、

のようにして最終的にどれくらいのスコアになりそうか予想しながらやってました。

の値は下のような感じです(nは1~100)。

ここから言える事は余りありませんが、スコアが正規分布に従って、4,5回以上の試行回数が望めるなら、スコアの平均を改善するよりも同じ分だけ標準偏差を増やしたほうが(もしそれが可能ならば)いいかもしれないです。

相手ユニット数からのAI判別

相手のAIを判別して各AI応じて戦略を変えようとしました。今回のルールではほとんど相手の状態について公開されておらず、ステージが始まってから最低でも100ターンほど経過しないと相手のユニットが視野に入ることはありません。しかし、ターン数をできるだけ減らそうと思うと、できるだけ早い段階(理想的には80ターン前後)で相手のAIが何なのかを判別したいです。相手のユニットが視野に入るまでに使える(事に気づいた)相手に関する情報は、相手が生産したユニットの数だけです。

相手が生産したユニットの数、というのは入力としては与えられませんが、「敵味方関係なくユニークなIDが生産順に連番で採番される」という仕様から、もし1ターン前にユニットの生産を行っていれば、自分のユニットのIDの最大値から今まで自分が生産したユニットの数を引いた数(に1を足した数)を計算すると、2ターン前の相手のユニットの数を知ることができます(確かめていませんが、2P側なら1ターン前の相手ユニットの数を知ることができます)。

上の図はgrunの生産したユニットの数のデータを取って、それをプロットしたものです。X軸がターン数、Y軸がユニットの数です。データ数はそんなに多くないのであまり正確では無いかもしれません。90ターン付近ではユニットの数が37に固まっていました。

この上の図はschwarzのユニット数の変化です。この2つを重ねると下の図のようになります。

赤がschwarz、緑がgrunです。こんな感じで各AIについて生産するユニットの数には違いがあるので、それを利用して判別できないかと考え始めたころにルール変更のアナウンスがありました。ルール変更後ではステージ数が増えたことにより、1回の挑戦の中で全ステージで1度も誤判別を起こさずにクリアすることが難しくなりました。また、相手のユニットの数は毎回必ず決まった値になるとも限らず、あまり高い精度が出せる気がしなかったので、この方法で判別することについて考えるのをやめました。うまくやればユニット数だけで相手AIを高い精度で判別できるんでしょうか。

その他

手動でやる可能性についてTwitterで話を聞くまで完全に頭になかったことが悔しい