CODE VS Reborn予選

• https://codevs.jp/
• https://github.com/kusano/codevs2019
  • ai_alice.cppが本体
    • AI名はソードアート・オンライン アリシゼーションのA.L.I.C.E.（Artificial Labile Intelligent Cybernated Existence、人工高適応型知的自立存在）から
      • 特に意味は無い
      • スキルに特化するとかならそれを名前にすれば良いのだけど、メインの汎用的なAIは名付けが難しい

CODE VS Reborn - ニコニコ動画

予選16位で決勝進出ならず。

本戦は今週土曜日でまだ観戦の空きがある。

日本中のプログラマが技術を競う「CODE VS Reborn」決勝開催！ : ATND

分かっている人向けまとめ

• ビームサーチ
  • ビーム幅は45,056（ローカル初手）、32,768（ローカル2手目以降）、 4,096（運営サーバー）
    • 時間切れになることがないように、これに 残り時間/3分 を掛ける
  • 深さは最大14（初手）、12（2手目以降）
    • 最初の連鎖の打ち合いが試合の勝敗に直結しそうなので初手は増やした
      • 最初に勝てるから勝てるのか、勝てるから最初も勝てるのかは分からん
• 連鎖とスキルの使い分け
  • 連鎖を目指すのとスキルを目指すのでそれぞれ読んで、お邪魔ブロック数が多い方を選択
    • スキルはおまけだと思っているので、ビーム幅256。連鎖判定が無い分そもそも軽い
    • スキルを使用しようとしているのに、相手が対スキルモード（3連鎖をこまめに打つ）に入って潰されることがあったので、もっと何か考えるべきだった
• 評価関数
  • 連鎖を目指すとき（上から順番に優先。細かな重み付けはしていない）
    • 連鎖候補数が多い
      • 1-9の1個のブロックを全ての列に落とす9x10=90通りを試して連鎖数を計算
      • お邪魔ブロックを1列落としてからブロックを落とす
        • 連鎖の発火点が谷底になることを防ぐ
        • 候補数の計算では1ブロックだけど、実際には3-4ブロックの塊なので、たいていは同じように消せる
          • 下に敷いたブロックで連鎖が暴発する可能性もあるので必ず消せるわけではない
    • ブロック数が多い
      • ブロックが積み上がってしまうデメリットよりも、後の連鎖で活用できるメリットの方が大きい
    • ブロックの塊数が少ない
      • 最下行を見て、ブロックが空マスで分割されていれば減点
      • 塊になっていないと連鎖になりにくい
    • 最も上にあるブロックの高さが低い
      • ただし、フィールドの下半分よりも低ければ考慮しない
        • 高さが低ければリスクも低いので無視
    • フィールドのハッシュ値の下6ビット（乱数）
  • スキルを目指すとき（上から順番に優先）
    • スキルゲージが多い
      • ブロックを積んでからスキルゲージを溜めても良いので、↓との優先度は考えるべきだったかも
    • スキルを発動したときに消えるブロックが多い
    • ブロック数が多い
    • フィールドのハッシュ値の下6ビット
• 発火のタイミング
  • 深さ$d$で連鎖・スキルを発動させたときの発生お邪魔ブロック数を$n$として、$n 1.1^{-d}$が最も大きくなる手数で発火
  • 連鎖が小さいまま打っても困るし、遙か先の連鎖を夢見ていてもしょうがないし
  • 1手あたり平均的に連鎖がどのくらい増えるかとかから適当に決めた
• 再計算のタイミング
  • 以下のいずれかの条件を満たすときはビーム探索をやり直し
    • 計算済みの手数が0（初手、連鎖・スキル発動直後）
    • 計算済みの手順を試して想定通りのお邪魔ブロックが発生しなかった
      • 要は、計算したときと、降らされるお邪魔ブロックやスキルゲージの状況が変わったということ
      • 前の盤面のお邪魔ブロック数を覚えておいたりするよりも、このように単に試す方が簡単
• 相手との駆け引き
  • 毎ターン相手の手を2手分全探索して、お邪魔ブロック数が最大（こちらが連鎖を狙っているとき）、スキルゲージの削りが最大（スキルを狙っている場合）の手を求め、上記の再計算の判定や再計算中は相手がその行動をすると仮定して計算
    • 1手目をより優先
    • 相手が連鎖を撃ってくると思って連鎖が短いまま発動させたけれど、結局相手は連鎖を撃ってこない、ということもあったのでビビりすぎかもなぁ……
  • 積極的に相手の連鎖を潰すようなことはしていない
    • そういうのもありだとは思うのだけど、そこまで手が回らなかった
• 実行環境
  • Intel Core i7-9700K 3.6GHz 8コア8スレッド
  • メモリ32GB
  • 最終日にAWSの72vCPUマシン（ハイパースレッディング有効なので実質36コア？）を借りてみたけれどほとんど性能が変わらず
    • コア数が4.5倍なら性能も4.5倍だろうと安直に考えていたが、甘かった
    • メモリ帯域がボトルネックだったのかな
    • もっと前の段階で借りて調整すれば良かった

分かっていない（失礼）人向け

周りの過去にCODE VSに参加していた人達はRebornで盛り上がっていたから、てっきり参加者が1,000人くらいはいるかと思っていたのに、112人で寂しかった。次があったときに、どこから手を付ければ良いのかとか、ツラツラと書いていく。ゲーム形式が変わったら役に立たないけど。

土曜日の決勝戦を観戦するときにも、この辺の話を知っていたほうが楽しめるはず。

CODE VS

2011年から開催されているゲームのAIを作るコンテスト。過去に6回（無印、2.0、2.1、3.0、4.0、5.0）、毎年開催されていた。「そういえば6.0の話が無いし、もう終わりなのかなぁ」と思っていたところで、数年ぶりにRebornとして復活。

他のプログラミングコンテストと比べて、イベントとしての盛り上げ方が強い。他は参加者以外はせいぜい風船が上がるのを見る（ACM-ICPC）くらいだけど、CODE VSはゲームの画面もしっかりと作り込んでいてイベントとして楽しい（と思う）。なので、テレビ局も取材に来るし、あちこちのウェブメディアに記事も上がる（主催者が裏でちゃんと話を通しているのだろうという気はする）。

学生プログラマー、日本一の栄冠は | その他 | NHK生活情報ブログ:NHK

CODE VS Reborn

Rebornだからか、今回のゲームは2.0/2.1の焼き直し。その分ゲームバランスの調整がすごい。感動した。2.1のときにやねうらお氏が文句を付けていたけれど、その辺も改善されている。

CODE VS 2.1予選問題は悪問ではないか - やねうらおブログ(移転しました)

前回はたしか縦横斜めに見て（ブロックの数は問わず）数字の合計が10になったら消えた。今回は2個のブロックの合計が10になったら消える。前回のルールだと人間が見ても何が何だか分からないが、今回は慣れてくると人間でも連鎖が見える。ちなみにこの記事の冒頭のスクリーンショットの1Pの連鎖は17連鎖になる。

ぷよぷよと異なり、お邪魔ブロックは1行分（10個）にならないと降ってこない。これによって、駆け引きはあるものの、ランダム性が減って、相手のフィルールドを凝視しなくてもある程度は戦える。

また、スキルという要素が増えている。ブロックを消すと（1連鎖でも10連鎖でも）スキルゲージが8増える。3連鎖以上で連鎖数をCとして、相手のスキルゲージを12+2C減らせる。スキルゲージは最大が100で、80以上ならばスキルが発動できる。スキルによって5と周囲8マスのブロックが消え、消したブロック数に応じて、相手にお邪魔ブロックが発生。なぜ5なのかというと、5は5自身との合計が10になるので、他の数字よりも連鎖で残りやすいからだと思う。うまい。

それはそれとして、今回の #codevs はゲームのルールとバランスの調整が絶妙で、この手のAI作成をしたことが無い人もある程度は戦える。面白い。あと、CODE VS 2.0/2.1と似たゲームなので、過去のブログ記事なりコードなりが参考になる。ゴールデンウィークに皆挑戦するべき。（このくらいは良いだろ）

— kusanoさん@がんばらない (@kusano_k) 2019年4月27日

これがどういう意味かというと、スキルが強い。

連鎖を組むようなプログラムを書くのは大変でも、スキルを狙っていくプログラムならば、ゲーム木探索とかビームサーチとかを知らなくても書ける。1連鎖でも大連鎖でもスキルゲージの増加は一定なので、連鎖を組まなくても単に消していけば良い。スキルゲージが溜まったらなるべくブロック溜めてスキルを撃つ。これだけで、ちょっと連鎖を組んでいるプログラムとは良い勝負になるし、強い人にも一発入れられる。

では上位陣がスキルを撃ち合うだけの詰まらない試合になるかというとそんなこともなくて、連鎖をとてもうまく組んだり、スキル狙いを察して3連鎖（2連鎖以下ではスキルゲージが削れないというのがまたうまくて、3連鎖は連鎖を狙わないと作れない）を連発したりすると、ぎりぎりスキルを撃たせないことができるようになっている。ということで、上位陣の試合を見ていてもほとんどスキルは使っていない。

ここから、もう1回何かどんでん返しがあって、決勝でボマー（Twitterでスキルを使うAIがこう呼ばれていた）が荒らし回ると面白いのだが、どうなるか。

RandomFallに勝てるAI

あらかじめ用意されたRandomFallというAIに勝てないプログラムはそもそもランキングに参加できなかった。RandomFallはランダムな位置にランダムな回転でブロックを落としていくAI。これに勝つのは簡単で、スキルが使えるときにスキルを使えば良い。

random_skill.py

# coding: utf-8
from sys import stdout
from random import randint

# ENDがn回出てくるまで読み飛ばす
def read_end(n):
  for _ in range(n):
    while raw_input()!="END":
      pass

print "RandomSkill"
stdout.flush()

read_end(500)
while True:
  for _ in range(3):
    input()
  skill_gauge = input()
  read_end(2)
  if skill_gauge<80:
    print randint(0, 8), randint(0, 3)
  else:
    print "S"
  stdout.flush()

CODE VS Reborn RandomFallに勝てるAI - ニコニコ動画

と思ったけど、スキルを使わなくても、確率的に2回に1回は勝てるのだから、何回か試せばランキングに参加できたのかな？

シミュレーター

これ以上のことをしようと思うと、ゲームのブロックの落下やブロックの消去、お邪魔ブロック数の計算などをそのまま自前のプログラムに組み込む必要がある。これを皆「シミュレーター」と呼んでいた。面倒だが必須。

ここが全体の速度に一番効いてくるので、遅いのはダメ。ある手を試して、戻して、別の手を試す、ということを繰り返すので、書き換えた場所だけを戻すundoができるようになっていると良い。

盤面が2次元なので2次元配列で管理するのが自然だけれど、1次元で持っていた方が高速だし、何かと楽。例えばスキルで消えるブロックを探索する処理が、2次元では

for (int x=0; x<10; x++)
for (int y=0; y<16; y++)
  if (field[x][y]==5)
    for (int dx=-1; dx<=1; dx++)
    for (int dy=-1; dy<=1; dy++)
      if (dx!=0 || dy!=0)
        if (field[x+dx][y+dy]!=10)
          erased.push_back(Position(x+dx, y+dy));

こんな感じになるところ、1次元だと

int D[] = {-11, -10, -9, -1, 1, 9, 10, 11};
for (int p=0; p<10*16; p++)
  if (field[p]==5)
    for (int d: D)
      if (field[p+d]!=10)
        erased.push_back(p+d);

こんな感じ。

強い人達は、ビットに情報を詰め込んで複数のマスを1個の変数で扱っていた（BitBoard）。そもそも演算回数が減るし、メモリ使用量が減ることでCPUキャッシュに乗りやすくなる効果もあるはず。

連鎖を組む

シミュレーターを使って、各ターンで落とし方を全て試して最も連鎖数が多くなるものを選ぶだけでは、せいぜい2-3連鎖にしかならない。いつか狙ったブロックが来たときに連鎖ができる、連鎖の候補を伸ばしていく必要がある。

この候補の連鎖数は、1-9のブロックを各列に落としてみて連鎖をさせれば分かる。これが大きくなるようにパックを落とせば良い。これで、10-20連鎖くらいは組める。同じ事をすれば、ぷよぷよの連鎖も組める。

chain.cpp

int max_chain_cand = -1;
Move result;

for (int x=0; x<9; x++)
for (int spin=0; spin<4; spin++) {
    int chain_num = field.move(pack, Move(x, spin));

    # 12連鎖以上可能なら連鎖
    if (chain_num>=12) {
        field.undo()
        return Move(x, spin);
    }

    # 連鎖候補数を調べる
    for (int n=0; n<9; n++)
    for (int x2=0; x2<0; x2++) {
        chain_cand = field.move(make1BlockPack(n), Move(x2, 0))
        field.undo()
        # 連鎖候補数が今までのものよりも多ければ選択
        if (chain_cand > max_chain_cand)
            result = Move(x, spin);
    }
}
return result;

ビームサーチ

ぷよぷよと異なりCODE VS Rebornでは、500ターン全てのパックが最初に与えられる。n+1目以降のパックを見る前にn手目を確定してしまうと連鎖の効率が悪くなる。n手目では連鎖候補数が少なくても、後から大連鎖ができるn手目があるかもしれない。かといって、全ての手の組み合わせを読んでいくと指数的に計算量が増える。1ターンあたりだいたい1連鎖増やせるので、十数手は読みたい。

そこでビームサーチという手法がある。各深さで評価が高い一定数（ビーム幅）のノードのみを覚えておく。

beam.cpp

struct Node {
  long long value;  // 評価値
  Field filed;  // 盤面
  vector<Move> moves;  // ここまでの手順
  // Node(long long value, ...
};

vector<Node> beam;
beam.push_back(Node(0, initialField, vector<Move>()));

for (int depth=0; depth<20; depth++) {
    vector<Node> beamPre;
    beamPre.swap(beam);

    for (Node &node: beamPre) {
        Field field = node.field;

        for (int x=0; x<9; x++)
        for (int spin=0; spin<4; spin++) {
            Move move(x, spin);
            field.move(move);

            long long value = evaluate(node.field);  // 連鎖候補数＋α
            vector<Move> moves = node.moves;
            moves.push_back(move);
            beam.push_back(Node(value, field, moves));

            field.undo();
        }
    }
    sort(beam.begin(), beam.end(), /* valueの降順にソート */);
    beam.resize(1000);
}

return beam[0].moves[0];

fieldを丸ごとコピーすると重いので、必要な情報だけNodeに保持するとか、movesから生成するとか工夫をしたほうが良い。

Zobrist Hash

例えば将棋だと、3七歩→2六歩　でも、2六歩→3七歩　でも同じ局面になる。CODE VS Rebornの場合はそういうことはないので、異なる手順で同じ盤面になることは少ないと思っていたけど、同じ数字のブロックを含むパックとか、似たパックが異なるターンで落ちてくるとかで、けっこう同じ盤面になることがあった。同じ盤面を再計算するのは全くの無駄なので排除したい。盤面全てを比較するのは無駄なのでハッシュ値が欲しい。

Zobrist Hashという手法がある。(x座標, y座標, ブロックの数字)ごとに異なる乱数を割り振り、現在の盤面に存在するもののxorを盤面のハッシュ値とする。例えば、(0, 1)に8があって、(1, 3) に11があって…ならば、盤面のハッシュ値は Hash[0, 1, 8] ^ Hash[1, 3, 11] ^ ...。この手法のメリットは差分計算ができるところ、盤面の変化した部分だけをxorしていけば良い。盤面が異なればスキルゲージなども異なりそうだけど、念のためスキルゲージなどの値も適当に加えた。

ハッシュ値が$n$ビットだと、だいたい$2^{n/2}$個くらい盤面があると、異なる盤面が同じハッシュ値になることがありえる（誕生日攻撃）。32ビットではなく64ビットにしておいたほうが無難。

並列化

ビームサーチで各ノードの処理は独立しているので、別スレッドに割り振れば並列化できる。

8スレッドくらいまでは素直に性能が上がったけれど、AWSで72論理コア（36物理コア？）のマシンを借りて36スレッドにしたら、1スレッドで処理している各スレッドで計算したノードを統合する処理がボトルネックになってしまった。そこを何とかしてもまだ8スレッドと性能が変わらなかった。何かもう一工夫必要らしい。

ランダム要素

最初のうちは、乱数を時刻で初期化するとか、残り時間に応じて処理を変えるとかは止めたほうが良い。同じ入力に対しては常に同じ結果が変えるようにしておく。後から試合を見直しておかしなところがあっても、再現できないとデバッグができない。自己対戦のためには、乱数のシードを引数か何かで与えて、変えられるようにしておけば事足りる。