先日、CODE VS 4.0の紹介記事を書いたついでに、AIをサクっと実装してsubmitしてみました。

結果。44点 48位。超即席のAIとは言え、まさかこの天才プログラマーの私が20位にすら入れないとは…。ちょっとCODE VSを舐めてました。まあ、それぞれの敵AIとは個別に対戦できる機能が用意されているのでそれぞれのAIに対してチューンしていけばもう少し順位は上がるとは思いますが。

あ、なんか最近、このブログにも新規の読者が増えた関係で自分のことを「天才プログラマー」と書くごとに断りを入れないといけないのが面倒なのですが、真夜中にコンビニの前でうんこ座りをしてタバコを吹かしながら「ちげーよｗ 俺、マジ天才だし。勉強やればできるシー」とか言ってる頭の悪そうな茶髪の高校生を見かけることがあると思いますが、その程度の意味だと思っていただければと。

さて、高橋 直大(chokudai)さんの12月28日のツイートから。

CodeVS満点に関しては、正直予想通りとしか・・・。　参加者AIが本当に敵AIより強い状態でなくても、敵AIに最適化された過学習状態でも全勝出来てしまう上に、各AIに対して対戦可能になっている、というのは、まぁそりゃ全勝出来ないとだめ、みたいな設定に見える。

— 高橋 直大(chokudai) (@chokudai) December 28, 2014

上のツイートをされた時にはエクストラモードはまだなくて、上位の人の点数が横並びになっていたようです。

エクストラモードが用意されてからは、まだ満点は出てないです。AIと自由に対戦できる環境があればある程度対策は出来るけど、だからと言って必ず勝てるわけではないってことですね。あれ？なんか将棋電王戦の貸出ルールのときも誰かがそんなことを言ってたような…。

CODE VS 4.0に関しては私は問題の説明を読んだ時点では「こんなん速攻いくだけやん、ゲーム性、ちっともないやん」と思っていたのですが、世の中、そんなに甘くはないようです。

実際のところ、ワーカーの視界が狭く、スタートする場所がランダムなのでワーカーを無駄なく分配させて、視界(未踏の升)を最短でクリアにしていくだけでもかなり難しいです。むしろ、それだけでも一つのゲームとして成り立つほどに。

※ ゲーム内容を知らない人のために説明しますと、ワーカーというのは、複数いて、毎ターン、上下左右の4方向のいずれかに移動させることが出来ます。フィールドは100×100升で、左上らへんのランダムな位置に配置される自軍の城から最初ワーカーが出てきます。このワーカーに移動のための指令を出します。ワーカーからマンハッタン距離で4升分が視界で、視界上に資源が落ちていることがあるので、未踏の升(視界に一度も入っていない升)を効率的に無くしていく必要があります。

この手の戦略型ゲームは問題に対するアプローチの方法が正しいとしても、複数の(たくさんの)アルゴリズム上の問題に帰着して、それぞれのアルゴリズムを正しく効率的に実装するだけという「実装ゲーム」になることがしばしばあります。

※ 「実装ゲーム」という言葉には「頭を使わなくて済むが、時間がひたすらかかる」というネガティブな意味も含まれています。

ただし、それはこの手の問題を解き慣れている人の話で、普通は適切なアルゴリズムを知らなかったり、効率的に実装できなかったり、アプローチ自体が間違っていたり、既知の(or 既存の)アルゴリズムで解決できないために独自にアルゴリズムを開発しないといけなかったりと状況は様々です。

また、今回、上位のスコアが横並びとは言っても、ターン数には歴然たる差があると指摘する声も。

「上位のスコアが横並び」とあるけど、勝ち点が同じだけでそれ以外は並んでいない 1位から8位まで350ターンくらい差がありこの差は運の一言で片付けられるほど小さくは決して無い 「横並びになることを見越して」ということならまだしも、少なくとも今の時点でははっきりと差がついていると思う

— ustimaw (@ustimaw) January 9, 2015

まあ、実装ゲームであっても上位陣に差はあるし、実装ゲーム(実装するだけのゲーム)と言えるほど単純でもないということですかね。

私は今回CODE VS 4.0に参加して、この手のアルゴリズムにちょっと興味が出てきたので、自分の勉強も兼ねてプロコンの過去問を解説するサイトでも作ろうかなと少し思ってたり…。