天下一 Game Battle Contest 2020参加記

tenka1.klab.jp

5,000円ゲット 🎉

住所を連絡したときの返信で「ブログ記事とか書いてね！」と言われていて、すっかり忘れていたので、今さら書く。

概要

KLab株式会社主催のゲームAIコンテスト。

去年までは天下一プログラマーコンテストということで、競技プログラミングのコンテストだったけれど、今年はゲームAIになったらしい。 ゲームAIコンテストというとCODE VSがあった。 CODE VSはAI作成期間が数週間あってガッツリ時間が取られるけれど、天下一のほうは4時間の短期決戦。

AtCoderができる前のプログラミングコンテストとかGoogleくらいしかやっていない2009年にKLabは1回コンテストを開いていた。 懐かしい。 過去のコンテスト一覧に載っていないな。 黒歴史なのか？

suztomo.hatenadiary.org

ゲームのルール

冒頭のリンク先から、参加者でなくても見られるはず。

コンテスト時間は4時間しかないので、シンプル。 でもちゃんとバランスが取れていてゲームになる。 これはホントすごい。 別に5,000円をもらったから褒めているわけではない。

1分ごとに20x20マスの正方形が与えられて、参加者は正方形の領域を指定してマスを取っていく。 各マスには点数が決まっていて、マスの点数/取った人数　の点数が1分ごとの最後に入る。 基本はこれだけ。ただし、

  • 1辺がmの正方形の領域を確保するのに (m+1)*(m+1)*125ミリ秒掛かる
    • m*mではない
    • m=1なら0.5秒/マス、m=2なら0.281秒/マス、m=3なら0.222秒/マス
    • mが大きいところではたいした差は無いものの、小さいところだと差が大きくて、なるべく大きく取りたくなる
  • 「マスの点数/取った人数」は、4近傍連結成分内の最小値が、連結成分全体に適用される
    • 点数の低いマスが1個でも含まれていると大損なので、なるべく小さく取りたくなる
    • 点数が高いマスには人が集まるからどうせ最後は一定になるんじゃないの？
      • →高いマスは点数が下がるかもしれないが、低いマスは低いままなのでちゃんと避けないといけない
  • 1時間ごとに点数が10倍になっていく
    • 最後の1時間は最初の1時間の1,000倍
    • 最初のほうはスコアを気にせず試行錯誤できる
    • でも、わりと接戦になるので、2時間目から3時間目あたりは手を抜けない
    • でも、この辺で一旦プログラムを止めてでも、改良できれば最後の点数の伸びが違ってくるよなぁ、で悩ましい

WebAPIを叩いてゲームに参加する。 領域を確保するAPIを叩いて、指定された時間が経過する前にもう1回APIを叩くと、時間が経過するまでAPI内部で待って処理を実行してくれる。 プログラム中でウェイトを入れる処理を書かなくて良くなるので、これはありがたい。 WebAPIを叩いて戦うとなると、「まず運営のサーバーへのレイテンシが小さいサーバーを借ります」となりそうなところ、そういうのもあまり要らない。 すごい。

1個の盤面を全参加者で共有して戦うのは良いのだけど、サブアカウントを量産して自分が取っていないマスだけを取るというチートができちゃうんじゃないかというのがちょっと気になった。 まあ、そういう奴がいたらBANすれば良いだけか。

そういえば、3Dでおしゃれな感じの人力で操作できるビジュアライザもあったのだけど、ほとんど使っていないな。 最初に感覚を掴むのにちょっと触って、それ以降は放置。 状況の確認もWebAPIを叩いていた。 なぜかというと、状況確認のAPIにもレートリミットがあって、ビジュアライザが毎秒（だったっけ？）1回消費してしまうから。 何とかしてほしいところではあるものの、AIとレートを共有していないとビジュアライザのほうのAPIをAIから叩くというズルができてしまうから難しい。

私のAI

import os
import random
import time
from typing import List, Tuple
from urllib.request import urlopen

GAME_SERVER = os.getenv('GAME_SERVER', 'https://contest.gbc-2020.tenka1.klab.jp')
TOKEN = os.getenv('TOKEN', 'xxxx')

def call_api(x) -> str:
    with urlopen(f'{GAME_SERVER}{x}') as res:
        return res.read().decode()


def calc_score(stage: List[List[int]], num_claim: List[List[int]], my_claim: List[List[int]]) -> float:
    visited = [[False for _ in range(20)] for _ in range(20)]

    def f(r, c) -> Tuple[float, int]:
        if r < 0 or r >= 20 or c < 0 or c >= 20 or my_claim[r][c] == 0 or visited[r][c]:
            return 1e+300, 0
        visited[r][c] = True
        r1 = stage[r][c] / num_claim[r][c]
        r2 = 1
        for r3, r4 in (f(r+1, c), f(r-1, c), f(r, c+1), f(r, c-1)):
            r1 = min(r1, r3)
            r2 += r4
        return r1, r2

    score = 0.0
    for i in range(20):
        for j in range(20):
            x, y = f(i, j)
            score += x * y
    return score

def main():
    while True:
        game_resp = call_api('/api/game')
        game_id, remaining_ms = list(map(int, game_resp.split()))

        if game_id < 0:
            break

        stage_resp = call_api(f'/api/stage/{game_id}').split('\n')
        assert stage_resp[0] == '20'
        stage = [list(map(int, x.split(' '))) for x in stage_resp[1:21]]

        while True:
            areas_resp = call_api(f'/api/areas/{TOKEN}/{game_id}').split('\n')
            if areas_resp[0] == 'too_many_request':
                time.sleep(0.5)
                continue
            assert areas_resp[0] == 'ok'
            num_claim = [list(map(int, x.split(' '))) for x in areas_resp[1:21]]
            my_claim = [list(map(int, x.split(' '))) for x in areas_resp[21:41]]

            score = calc_score(stage, num_claim, my_claim)
            num = 0
            for i in range(20):
                for j in range(20):
                     num += my_claim[i][j]
            print(f'game_id: {game_id}  score: {score}  num: {num}')

            best = -1.0
            r, c, size = -1, -1, -1
            base = calc_score(stage, num_claim, my_claim)
            for k in range(1, 4):
                for i in range(21-k):
                    for j in range(21-k):
                        for ii in range(k):
                            for jj in range(k):
                                if my_claim[i+ii][j+jj]==0:
                                    num_claim[i+ii][j+jj] += 1
                                my_claim[i+ii][j+jj] += 1
                        s = (calc_score(stage, num_claim, my_claim)-base)/k
                        if num<64:
                            s += random.gauss(100, 10)
                        for ii in range(k):
                            for jj in range(k):
                                my_claim[i+ii][j+jj] -= 1
                                if my_claim[i+ii][j+jj]==0:
                                    num_claim[i+ii][j+jj] -= 1
                        if s>best:
                            best = s
                            r = i
                            c = j
                            size = k
            if r==-1:
                break
            print(f"{r}-{c}-{size}")
            claim_resp = call_api(f'/api/claim/{TOKEN}/{game_id}/{r}-{c}-{size}').split('\n')[0]
            if claim_resp == 'game_finished':
                break
            assert claim_resp == 'ok'

        while int(call_api('/api/game').split()[0]) == game_id:
            time.sleep(0.5)

if __name__ == "__main__":
    while True:
        try:
            main()
        except:
            pass
        time.sleep(1)

頑張っているように見えるかもしれないが、書いたのはbest = -1.0からprint(f"{r}-{c}-{size}")の間だけ。 他はサンプルコードそのまま。 サンプルコードでは、ここが未取得の1x1マスをランダムに取得するようになっていた。

1辺の長さ1-3の正方形を全ての場所に置いて、一番スコアが高いところ（スコアを計算する関数はサンプルにある）に置くだけ。 1x1だけ取っていくのが良さそうだけど、点数が高いところは結局下がって、2x2とか3x3で取ったほうが良さそう盤面になることが多かった。

大きい正方形のほうが点数が高くなりがちなものの時間が掛かるという代償がある。 なので、1辺の長さで割っている。 これ何が正しいのか分からなかった。 1辺の長さで割ることが正しいなら1-3ではなく4とか5とかも試せるはずだけど、range(1, 4)をrange(1, 5)にしたらスコアが下がった。

みんな同じ事を考えて、最初に同じ所を取って点数がガクっと下がったら嫌なので、一応乱数で少しばらしてみた。 効果は分からん。

たいしたことは何もやってないな。 いつもQiitaを使っているのでQiitaに書こうと思ったが、記事のプログラミング要素が少なすぎて怒られそうなので、はてなに書いた😇