CODE VS 5.0がめちゃめちゃ面白いのだが

投稿日時: 投稿者:

さて、いよいよ始まったCODE VS 5.0。
今回の見どころなどを簡単にご紹介したいと思います。

CODE VS公式サイト
https://codevs.jp/

前回のCODE VS 4.0では、レビューするために軽い気持ちで参加した私ですが、あまり時間がとれず、バトル開始後にいかに綺麗に自分の視界を塗りつぶすかということだけで終わってしまいました。そのことは、以下の記事に詳しいです。

CODE VS 4.0 途中経過 その3
http://yaneuraou.yaneu.com/2015/01/31/code-vs-4-0-%E9%80%94%E4%B8%AD%E7%B5%8C%E9%81%8E-%E3%81%9D%E3%81%AE3/

そのときに打ち立てた理論が「直進最速理論イニシャルY」です。(本戦進出者の間でもこの言葉が使われていました。)

実はそれを行なうプログラム部分だけで私は3000行以上書いていて、視界を綺麗に塗りつぶすのも簡単ではないな～というか、この大会で上位に入賞するにはプログラミング力ももちろん大切ですが、実装するのに相応の時間も必要なので時間もそれなりに確保できていることが前提なのかなという気はしていました。

その点、今回のCODE VS 5.0は、ちょうど学生さんは春休み中だと思うので時間はたっぷりある状況でしょうから、レベルの高い戦いが待ってそうです。

今回は私も本気で参加してみようかと思い、以下のようなツイートをしたところ、CODE VSの公式twitterアカウントがこのツイートを予選開始直前にRTして、いきなり参加者全員に私が挑戦状を叩きつけたみたいな感じでのスタートと相成りました。


私のほうは、3月1日がちょうど出張で時間が取れなかったのですが、ゲーム自体は、「かくれんぼ」ゲームだとtwitterでは書いている人が多かったです。

このゲームはペンゴのようなゲームで、プレイヤー(忍者)は、岩を押せます。敵が最短路を辿ってくるので、岩をうまく動かしてなるべく長いターン、耐え忍んでください、というゲームだと私は捉えました。

私はまだ指をかじって観戦しているしかないなか、chokudaiさんが(遊びで)参加する宣言。


1000行程度のざっくりとした実装のようですが…。

速攻一位に！！！


「このプログラム、7000行ぐらい書かないとまともな強さにならないな～」と思っていた私は、もうこの時点で敗北感たっぷり。

この手の大会で上位入賞のために開発の時間を確保するのはもちろん大切なことですが、それより、限られた時間で効率的な(よい動きをする)AIを実装するのも大切なことなんだなぁと思い知らされました。

まあともかく、私は私のやり方でゲームを楽しみたいと思います。

あまり詳しく書くとヒントになっちゃうので詳しく書けないですが、ざっと思ったことを簡単に書き残しておきます。

忍者は二人います。忍者は1ターンに2歩進めます。その場にとどまるという選択もあります。4方向+N(とどまる)で5つの選択があります。2歩なので5×5 = 25通りあります。上に移動して下に移動するような組み合わせは、その場にとどまっているのと同じではないかと言われそうですが、これによりブロックを押せるケースがあるので、同じとは限りません。このへんなかなか難しいです。(ただし上+Nと、N+上は同じ。)

忍者が二人いるので1ターンで25×25 = 625通りの組み合わせがあります。
2ターンで625×625 = 390,625。3ターンで244,140,625通りあります。

将棋ソフトではプログラムをキチキチにチューニングしても1スレッドあたり1Mnps(1M nodes / second)ぐらいしか読めないので、それを目安にすると、このゲームでも、全幅探索でも2ターンは読めますが、3ターン以上読むのはなかなか大変でしょう。

また、先を読むのを難しくする要素として、このゲームでは「スキル」が使えて、1ターンごとにこのスキルで相手のことを妨害したり自分のほうの岩を取り除いたりできます。

私としてはペンゴのようなゲーム性だと捉えると、将棋ソフトっぽい探索で頑張って、岩をうまく移動させてうまく耐え忍ぶところにゲームの価値を見出したいところですが、「スキル」があると相手に岩を落とされるようなアクシデントが発生して、なかなか読み通りにいかなくなってきます。

こうなってくると先を深く読んでもあまり勝敗には直結しなくなってきます。相手が妨害してくるからです。また、スキルポイントを回復させる忍者ソウルというアイテムの出現場所がランダムなのでそのへんも考慮するとあまり先まで読めないゲームとなっていると思います。

これはつまり、「将棋ソフトのような探索系が得意なプログラマが有利にならないように、このゲーム向きにアルゴリズムを工夫しないと勝てなくなっている」ということで、競技プログラミング上、大切な要素だと思います。

CODE VSも今回で5回目のようで、さすがに問題もシステムもこなれていますし、またルールも明瞭です。(できれば敵のシミュレーション部分のソースコードがサンプルとして欲しかった気はしますが) BOTと対戦して予選の成績を決める前回とは異なり、今回はオンライン対戦でレーティング変動によって順位を決める仕組みとなっており、システム面でも不満はないです。

今回は、大変素晴らしい、本当にやるに値するプログラミングコンテストとなっていると思います。

個人的には、忍者のスキルはもっと減らして、読み合いで勝負がつくようになっているほうが好みなのですが(探索系のノウハウが使えるからというのもありますが、観戦したときに、そちらのほうが芸術的な岩の配置などを考えるAIが出てきて楽しそう)、今回のこれはこれでチャレンジングな課題だと思います。

将棋ソフトっぽい探索系のノウハウがほとんど生きそうにないので私の力の発揮できる場所がないような気もしますが、これはこれで頑張りたいと思います。

それでは皆さん、予選終了まで存分に楽しみましょう！

関連記事)
CODEVS 5.0本戦用ソースコードの提出が終わりました
CODEVS 5.0 準優勝しました！ ←　結局準優勝した✌

「CODE VS 5.0がめちゃめちゃ面白いのだが」への4件のフィードバック

  1. 直大氏はほんとに黒船だったんですね。
    面白そうですけど、自分の技量では無理そうです。
    AIを構築ってどうやるの？ってレベルなので、観測することにします。
    しかし、収穫加速の法則ってすごいですよね。
    もう、オンラインジャッジが当たり前になってしまいました。
    何とかチャンネルで遊んでた時はスレにべた貼してる人が多かった中自分はイデオンに張るようにしてたんですけど。
    いやー、老害になる日も近いな。Orz

    返信 ↓

    • > AIを構築ってどうやるの？ってレベルなので、観測することにします。

      例えば、犬は最短路を通ってくるので犬までの距離をdとして
      評価値 = – d * 100;
      犬はいっぱいいるので、全部の犬に対してこれを足し合わせたものとする。

      そして、評価値が一番高くなる移動先を見つけるんだ。

      ほら、簡単でしょう？

      返信 ↓

      • AIがゲシュタルト崩壊を。ごごご・・・。
        評価値ってそんなもんでいいのですか？
        秘伝の係数とかがあって、重みづけとか、なんか門外不出の技術が100位ありそうな気分なんですけど。
        ふむふむ。
        なんか新しい知見が得られた気がします。
        大感謝です！

        返信 ↓

  2. ちょっと思ったのですが、屋根さんって物事に力を注いで解決するタイプなんですね。
    自分は逆で、物事に力を入れないでバランスで解決するタイプです。
    なので、コード自体はあんまり書きません。
    屋根さんはゴリゴリ書くタイプなのでしょうけどね。
    なんか面白いですね。
    あぁ、でも、脳内コーディングは割とやってて最適化省力化の計算は結構やってるかもです。
    いわゆるconstexprですね。

    返信 ↓

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です