CODE VS Rebornで作ったAIの解説

 

目次

実行環境

ビームサーチ

盤面評価

カウンター

シミュレーターの高速化

探索の効率化

やってないこと

 

 

実行環境

機器:MacBook Pro 15 inch (2016)

言語:java

スレッド数:1

 

 

ビームサーチ

クライアント上

turn=0:深さ15、幅4200

turn!=0:深さ10~15、幅1200

1ターンで20秒を超えそうな場合(特にturn=0)は動的に幅を狭めてるので、平均すると実際の幅は上記の0.8倍くらいです。

ちなみに、サーバー上のaiは幅を25%にしてます(省メモリ化用の処理が追加されたため)

 

 

盤面評価

共通

r:一様乱数(0~0.001) 

連鎖数3未満の時

c:潜在的連鎖数(後述)

p:パターンマッチ数(後述)

score = c × 0.1 + p × 0.003 + r

連鎖数3以上の時

c:連鎖数×1.04^(max深さ-今探索してる深さ)

s:黒魔術スケール(いい感じにするために25日間かけて微調整を繰り返した値)

score = c × s + r

基本的には「大連鎖したい vs 早く連鎖打ちたい」のトレードオフの調節を担っています。

潜在的連鎖

その盤面にどれくらいの連鎖能力が秘められてるのかを表したものです。潜在的連鎖の定義は、全列に全数字の1x1ブロックを落としてみてそこから発生した連鎖数のうち、落とし方の全パターンの中での最高連鎖数です。

しかし、これはとても重い処理となり探索幅数が稼げません。でもこれをサボると盤面評価の質が下がります。このトレードオフの最適解を探す必要があります。

最終的には左右の端から2列目の2箇所のみに落とすようにしました。

パターンマッチ

発火が発生しうるパターンは限定的です(下図)。これがある数が多いほどよい(潜在的連鎖が上がりやすい)盤面だと考え、以下のパターンの数だけscoreを加算してます。ちなみにk=13まで調べています。

このパターンがあるだけでは連鎖にはなりません。連鎖はこれらのパターンがいい感じに隣り合ってる必要があります。しかし、これを導入するだけで高速に大連鎖が組めるようになりました。やっぱりこのゲームはよくわかりません。

f:id:kera6rhy:20190519192147p:plain


 

カウンター

カウンターのロマン

基本的に連鎖数はターンが経過するほど多くなります。しかし、相手に先に発火されてしまうとお邪魔ブロックだらけになってしまい自分の大連鎖が台無しになります。

しかし、うまくカウンターができれば後出しになるため、ターン数の恩恵を受けてより大連鎖を跳ね返すことができます。ロマンですね。

さらに、同連鎖数のカウンターでも恩恵があります。カウンター後、自分の盤面ではお邪魔は降りませんが、相手の盤面には振り続けます。そのターン中は相手は連鎖が組めない状態です。自分だけ連鎖が組めるターンを稼ぐことができるので、2発目を自分が優位の状態で発動できます。ロマンですね。

カウンターの実現方法

発火位置を高いとこに持っていけば実現できます。きつい崖の途中に発火点があるような状態です。

f:id:kera6rhy:20190519195021p:plain

 

わざと高い位置で潜在的連鎖を調べる

上記の潜在的連鎖で記載した1x1ブロックを落とす位置を、実際に落下が停止する位置ではなく下に4マス開けた位置で停止するように落としました。これだけで高い発火位置を生み出すことができます。

盤面の上部の確保 

 いくら発火位置を4マス確保しても、デンジャーラインギリギリまでブロックを積み上げてたら1ターンも時間を稼げません。そのため、上空4マスは空けるようにペナルティを与えました。

降ってくる回数の多い数を起爆ブロックにする

せっかくカウンターを組んでも、欲しいタイミングで起爆剤が来ないとカウンターできません。それで結構やられました。

そこで、15~23ターンの間で登場回数の多い上位3つの数で発火させるようにしました。

カウンターの現実

実際やってみると色々デメリットがありました。

・連鎖の組む速度が遅くなるため、結果的に後出しの恩恵が中和

・連鎖後のゴミが多くなるため、2発目が組みにくい(山形状のゴミの上にお邪魔4段がのっかるので、食らったお邪魔数以上の被害を受ける)

 

 

シミュレーターの高速化

アルゴリズム的な面

アルゴリズムと書きましたが、特に難しいアルゴリズムを実装したわけではありません。基本的な思想は「徹底的な無駄の削除」です。ただひたすら無駄な処理をしないようにしました。

本当に様々なことをしてきましたが、これを文で紹介すると大変なことになるのでソースコードでご勘弁ください。

条件分岐の削除

条件分岐は重い処理です。ループの最も深い場所のif文を1つ減らしただけで130%の速度になったこともあります。

割り算の削除

割り算は重い処理です。ループの最も深い場所の割り算を1つ減らしただけで130%(略

割り算は主に剰余で使っていましたが、ビット演算で代用することができたので割り算を減らすことができました。

前turn時のシミュレーション結果の再利用

15ターン先まで読むので、前ターンで読んだ2~15ターン先の先読み結果は今ターンで読んでも同じです。なので、うまく保存して再利用しました。結構効果あります。

キャッシュヒット率

メモリのキャッシュ特性を考慮すると非常に高速になります。

今回の例では盤面を縦ではなく横向きでデータを扱ってました。

f:id:kera6rhy:20190519175707p:plain

 

 

 

探索の効率化

重複盤面の削除

同じ盤面を評価する意味はありません。そして、シミュレーションは深さが進行すれば盤面数は指数関数的に増加します。すると例え同じ盤面が2つしかなくても無駄なシミュレーションが指数関数的に増えます。なので重複盤面は削除する必要があります。

が、実際のところ効果は薄かったです。微妙に強くなったかな?くらいでした。

連鎖した盤面は次の深さに持ち込まない

自分は3連鎖以上した盤面は次の深さに持ち込みません。限られた演算資源は一度発火した盤面よりまだ発火せずに連鎖を溜め込んでる盤面に当てるべきです。

全大会での知見ですが、これをするだけで途端に大連鎖するようになります。それくらい強力です。(だったと思います)

前turn時のシミュレーションで最高スコアの盤面の確約

 乱数要素が多いので、前ターンのシミュレーションで得た15ターン先の良い盤面を今ターンでも引き当てる確証はありません。そのため、良い盤面に行き着くまでのコマンド列を保存し、そのコマンド列に適合した盤面はscore+=10000とすることで必ずたどり着けるようにしました。

 

 

やってないこと

相手の盤面を見る

相手の盤面を見ることで、相手が発火しそうなタイミング・連鎖数を推測することができます。それに合わせて自分の発火タイミングを早めたりなど、戦いを有利に持っていくことができます。

しかし、カウンター前提で連鎖を組んでると急に発火させることができません(経験上)。そのため、相手の発火状況がわかったところでその情報をうまく使えなかったのでやめました。

SIMD

SIMDをやれば更に高速化できるが、知識と経験が皆無で断念しました。(javaは自動でSIMD化してくれるってどこかの記事に書いてあった気がしますが...)

並列化

並列化をやれば更に高速化できますが、モチベーションが上がりませんでした。並列化を想定したコーディングをしていないため全体的な大改修が必要だったこと、サーバー提出AIは1スレッドであることが主な要因です。

しかし決勝もサーバー提出と同環境であったため、結果的には並列化に工数を当てなくてよかったように思います。

 

大学院を卒業するので大学生活6年間を振り返る

ポエムです。6年間振り返ります。

 

入学前

中学くらいにプログラミングを触れたことがあったし、なんかゲーム作りたいな〜パソコン好きだしな〜と思ってたので、とりあえず情報系学部一本で進路を選んでました。専門学校も選択肢にありましたが、まあ無難に大学選びました。

 

大学1年(2013年)

とりあえず遊びたい〜楽しい大学生ライフを過ごしたい〜って思ってました。そのためには大学内での知り合いの数を増やすことが効果的だと思ったので、とりあえず学園祭実行委員会に入りました。やっぱり団体に所属すると超知り合い増えますね。なんだかんだ100~200人くらいは知り合いにカウントしていいんじゃないかくらいにはなりました。一方なんの団体にも所属してない人はやっぱり友達少ない傾向にありましたね。ほんと団体重要。

そんなこんなで大学生の定番っぽい遊びを色々堪能してた気がします。BBQとかドライブとか?僕は遊びに関しては受け身よりなタイプなので、遊びに誘ってくれた人には感謝してます。

この「遊んだ」というのが僕の中では結構重要です。この時期にたくさん遊んだからこそ後に勉強にめっちゃ集中できたんじゃないかな〜思うからです。もし遊んでなかったらず〜っと(今でも)「楽しい大学生ライフ」を追うのに必死になっていたかもしれません。どうやら僕は遊びたいと思う人種だったんですね。

あとは入学時は早くプログラミングの授業受けてぇ〜って思ってました。でも現実は悲しく、授業の進行速度が遅くて退屈でした。初学者向けで授業が構成されてるので当然です。なのでC言語の教科書を勝手に読み上げて、小さなクソゲーたくさん作ってました(dxlib+C言語)。

それからまわりにプログラミングを自発的にやってる人がいなかったのは悲しかったですね〜。情報学部なんだからいてもおかしくないだろって思うんですが、蓋を開けてみると「今の時代PCっしょ」って理由で入学した人が大多数でした。もちろんそういう人たちは授業でしかプログラミングをしません。所属してた友達グループのみんなもそんな感じで、授業の空き時間で溜まり場でみんな雑談してるとき、僕は軽く雑談に混ざりながらずっとクソゲー作ってた気がします。でもそんな僕にも遊びとかに誘ってくれたので、その点では感謝してます。

 

大学2年

プログラミングを自発的にやってる同期を発見したのがこの時期ですね。同学部他学科にいました。しかも結構人数多いグループみたいになってて超羨ましかったです。その人達との雑談は超楽しかったですね。初めてのプログラミング雑談を入学から2年経ってできましたから。

この頃授業でjavaがあったので、とりあえず教科書読んでたらネットワーク通信って章があったんですよね。そこの例では単に文字の送信しか載ってなかったですが、これがあればネトゲ作れんじゃん!!!ってテンション上がって作った記憶があります。C言語には教科書に書いてありませんでしたからね。やっぱり教科書に乗ってるかどうかが重要だなって思います。

あとこの頃は大学生活が鬼のように忙しかった時期ですね。特に秋がやばかったです。実験レポートっていう重い課題が毎週ある中、中間テストが3つくらいあり、しかもこの時期に学園祭があるので追い込みがあるんですが関わってる案件が4個くらいあってやばいし、しかも講義は普通にあるから、まじで死ぬ気でやってた気がします。ただ、結局これらはやりきることができたんですが、達成感は結構ありましたね。あと自分はこれくらいの量のタスクできるんだ〜って自己認識できたこともいい出来事だったかなって思います。

あとここで初めてプログラミングコンテストに参加します。CODE VSっていうゲームAI系コンテストです。途中参加でいい成績は出せませんでしたが、楽しかったので決勝戦会場に足を運びました。更にそこでは懇親会の場が用意されてたんですね。ともに戦った人たちと雑談できたんですが、これが超刺激的でしたね。初めて学外の学生やなんなら社会人と交流できたので、すごくテンション上がってた気がします。しかもみんなプログラミング超大好き。天国かな?って思いました。

 

大学3年

学園祭実行委員会をやめました。自分の勉強やりたい欲がピークに達しましてね。そもそも知り合い増やすっていう目標はすでに達成済みでしたし。まあ委員会の活動は楽しかったですよ、ただそれはまた別の話。

あと友達グループからいい感じ(主観)にフェードアウトしてぼっちになりました。自分の勉強やりたい欲がピークに達しましてね。やっぱ講義の空き時間とか普通に2時間空くので、結構もったいない部分だったんですよ。グループの人と一緒にいると、なんだかんだ雑談したりだらけてしまいますからね。あと講義もホントは前で受けたいんですがグループに所属してると固まって座るしやっぱ後ろの方なんですよね。なので、割と無言の自然な感じで前の方に座ったり、講義終わったら一人でさっさと勉強スペースに移動する感じで、いい感じ(主観)にグループからフェードアウトしました。でもその人達とはたまに目があったら軽い雑談とかしてくれるし、「まあ君ならそうするよね〜」みたいに僕のことを理解してる感じだったので、割といい人だったなってなんか今思う。

ただ、ぼっちで溜まり場にいるとめっちゃ知り合いに話しかけられます。そりゃ集団の中で知ってる人が僕だけって場合より、知っている僕だけがぽつんと座ってたほうが話しかけやすいですよねって思う。ここ盲点だった。そして、知り合いが知り合いを連れてきて絡んでくるので、その知らない人とも知り合いになるし、なんかぼっちになったら知り合いめっちゃ増えました。なにこれ。まあ嬉しいですけども。

まぁこんな感じで勉強時間を確保したんで、とりあえず読みたかった技術書超読みました。あとずっと作りたかったMMORPGjavaでずっと作ってました。あと授業も3年になるとやっと専門的な内容になってきて超楽しく講義受けてました。で今から自慢なんですがこの年度の成績が学科1位になったらしく40万円キャッシュバックされましたイェーイ。まぁそれだけ勉強したい欲が溜まってたってことですよ。

あとこの年もCODE VSが開催されましたので、僕は時間をフルで準備して文字通り全力で1位狙いに行きました。ところが僕全然上位に行けないんですよこれが。上の人強すぎ。異次元。神かって思いました。正直僕は学内ではプログラミングできる方なので、そのせいか本気出せば1位行けるっしょとか思ってました。いや世界は広いですね。なんだかんだ人生で初めて強者との壁、圧倒的な実力差を感じました。その決勝大会にも足を運んで強い人達に色々聞いたような気がします。

 

大学4年

大学院に行くことに決めてたので就活はしませんでした。入学したての頃は行くつもりはなかったんですがね。当時ネットで「大学院に行くと就職できない」ってよく見たので。でも大学院に行ったほうが大企業に就職できる〜みたな話を一次情報で手に入れたあたりから大学院に興味が出ました。

4年といえば研究室!ですが、僕は先生と相性が悪かったらしく、研究生活はダメダメでした。なんかめっちゃ休学とか考えてましたね。いや〜たくさんの人に相談しました。まぁ大学院に進学するとき研究室を変えられるってあとで知って休学はやめましたが。

あとこの年もCODE VSがありました。今回ももちろん時間をフルで準備して挑みましたが、前回の反省を踏まえてきっちり対策もとってきました。まあゲームAIの定番なアルゴリズムを勉強しただけですが。でも結果なんと3位!賞金5万円GET!やっぱり定番を知ってるかどうかは大きいらしいですね。3回目の挑戦でついに入賞することができました。

 

大学院1年

新しい研究室では普通に研究できてましたね。よい先生でした。ただ、僕は研究はあまり向かないってことを実際にやってみてわかりました。まあそういうこともあります。

また今年度からはCodingameっていう新しいゲームAIコンテストを見つけまして、これをずっとやることになります。なんかCODE VSと違い世界中の人が参加するので母数が3000人くらいいます。まあ僕もいつものように時間をフルで設けて挑戦したんですが、なんか4位になっちゃいました。世界4位。なんかウケますね。まぁ4位は1回しかとったことないですが、上位5%は常にキープしてるので、なんか自分ってその位置にいるんだ...って思いました。まぁ僕には無限の時間があるので多分その要因が大きいんですがね。

ちなみにここらへんで僕ビットコインで死にました。

それからついに就活が始まります。1月中旬くらいからはじめました。僕の予想ではゲームAIコンテストでいい実績があるので割と余裕じゃね?って思ってましたがそんな事ありませんでした。普通に落ちました。ゲームAIコンテストの能力が業務で生かされるかって言ったら微妙ですからね。普通にその他様々な要因が企業にマッチングしてるかどうかを見られていました。ただ、そんな中でも無事内定を取ることができました。就活解禁3時間前に。ギリギリセーフ。

 

大学院2年

一番近い記憶のはずなのになぜか一番記憶がありません。というか語るものが全くありません。ずっと研究してたからだと思います。そのおかげか、やっぱり自分の研究にだんだんと愛着がわきましたね。修論発表では結構自信を持って発表できたと思います。

 

おわりに

こうして文字起こししてみると、意外と密度のある大学生活を送ってきた気がします。ちなみに恋愛もほどほどにしましたがなんか迷惑掛かりそうなんで書くのはやめときます。

てかなんでこの記事書いたんだろう。でもポエムってたまに書きたくなりますよね。てかポエムって何?詩って出てきたんだが。

社会人になってもがんばります。

codingame -Mean Max- 参加記

この記事はKogakuin Advent Calendar 2017 6日目の記事です。

Kogakuin Univ Advent Calendar 2017 - Adventar

今回は世界111/2512位、日本5/67位でした。前回から随分と順位が下がってしまい、悔しいですね。

  

今回のゲーム

f:id:kera6rhy:20171129144819p:plain

貴重な水を相手より多く集めろ!ってゲームです。(映画MadMaxのパロディらしい)

3種類の車を操って、灰色のタンク車を倒すことで水が出現します。

↓のゲームのプレイ映像を実際に見てもらったほうが雰囲気はわかります。

Coding Games and Programming Challenges to Code Better

 

今回のゲームの特徴(ゲームAI作成の視点から)

・車はx,yそれぞれ-6000~6000の範囲の座標を持つ(状態数が多い!)

・車を3台同時に操る必要がある

・車たちは簡単な物理演算にしたがって動く

・1対1ではなく、3人のプレイヤーで戦う

・各車はそれぞれ妨害スキルを使用することが出来る

 

各車が出来ることは2つ

1:指定した(x,y)の方向に向かって、指定した量のアクセルを踏む

2:指定して(x,y)の地点にスキルを放つ

 

となっています。

 

今回の方針

シミュレーションベースではなくルールベースでやってみました。理由は1ターンあたり制限時間50msで車の行動選択肢が多く、シミュレーションはできないだろうと思ったため。(上位陣はシミュレーションがほとんどらしく、この判断ミスが最大の敗因ですね)

 

実装

Reap→Dest→Doofの順に行動を決めています。

1つの車あたりの処理

1:行き先を決める(Reap→Wreck、Dest→Tank or Wreck、Doof→敵Reap)

2:1ターンで進むであろう(適当予想)移動ベクトルを求める

3:移動ベクトルを加算した時に、他の車と衝突しなくなるまで移動ベクトルを回転させる

4:現在の車の速度を考慮して、求めた移動ベクトル通りに進むように、加速ベクトルを求める

 

今回は4番について詳しく解説します。

 

行き先ベクトルをそのまま加算しても、車はその方向には進みません。現在の車の速度ベクトル+移動ベクトルとなってしまうためです。

f:id:kera6rhy:20171129173751p:plain

正しく移動させるには、以下のような加速ベクトルを求める必要があります。

f:id:kera6rhy:20171129173809p:plain

この加速ベクトルを求めるには、余弦定理を使います。今回は式変形したこちらを使います。

f:id:kera6rhy:20171129164333p:plain

式の各変数を以下の図のように当てはめます。

f:id:kera6rhy:20171129161011p:plain

 

ここで、|b|を最大の600と決めます(移動は常に最大加速で進みたいので)。するとcの長さが決まり、-a+c=bによってbの速度ベクトルが求まります。

この速度ベクトルを出力すると、行き先ベクトル方向にきれいに進むようになりました。

 

細かく言えば他にも、cの長さが行き先ベクトルより長かった場合の処理(通り越してしまう)や、そもそもbが存在しない場合の例外処理も実装しましたが、(適当な処理でごまかしただけなので)解説は割愛します。

 

 感想

 ルールベースを実際にやってみたところ、かなり実装コストが高かったためかなり時間を取られました。1つ1つのルールの実装コストは低めですが、大量のルールを実装しなければならない、といった感じです。

対して、シミュレーションベースは初回にシミュ完成させるまでは実装コスト高ですが、それ以降の実装のノビが良い気がしました。

正直、ルールベースが大変なんてことは常識なのですが、「ちょっと挑戦してみたい」という気持ちが消化できて良かったです。二度とルールベースはやりません。

 ルールベースが適切な問題のあるらしいので、これからは問題に対して使用する手法をよく吟味しようと思います。

 

 

パーセプトロンを多層にするとなぜXOR回路を表現できるのか

自分なりの考察をまとめました。

 

なぜ考察するに至ったか

単層パーセプトロンは線形であるのに、多層になっただけでなぜXORの非線形領域分類ができるのか疑問であったが、手元の資料では解説されてなかったため。(論理回路的にはAND、OR、NANDの組み合わせで出来るから、それを真似れば出来ます〜程度であった)

 

 解説

単層パーセプトロンは線形領域でしか分類できません。これは式を見ても明らかです。

f:id:kera6rhy:20170612231239p:plainf:id:kera6rhy:20170612231651p:plain

そのため、単層パーセプトロンではXOR回路は表せません。

f:id:kera6rhy:20170612232105p:plain

 

一方、AND回路、OR回路、NAND回路は単層パーセプトロンで表せます。

f:id:kera6rhy:20170612233352p:plain

f:id:kera6rhy:20170612233334p:plain

f:id:kera6rhy:20170612233345p:plain 

 

 

そして、論理回路的にはXOR回路は以下のように表せます。 

f:id:kera6rhy:20170612232536p:plain

 

これを上で書いた各回路のパーセプトロンでそのまま置き換えるとこのようになります。

f:id:kera6rhy:20170612232740p:plain

 

 このうちの2層目であるAND回路部分が、今回私が疑問に思った点です。

「NAND回路出力結果とOR回路出力結果を、AND回路に入力する」とは、一体なんなんだ....

図を用いてしばらく考察したらイメージできました。

 

f:id:kera6rhy:20170612234936p:plain

このようなイメージのことを言っているのだと分かりました。

 

OR回路、NAND回路の入力はともに重みw=1なので、右のグラフ中では赤:1,青:1、灰:2となります。この値を高さと見れば、グラフの軸が3次元方向にもう1つ追加された感じでしょうか。

この内、高さが1.5以上であるのは灰部分のみであるので、その領域にある黒点がヒットし、XOR回路が表現されるという仕組みです。別の言い方をすれば、非線形領域を分類できる仕組みです。

 

考察

層を増やすということは、グラフの次元を1つ増やすことなのでは?と思った。

グラフの次元を1つ増やし3次元方向の高さを自在にコントロールすれば、非線形どころか飛び飛びの領域も分別できるなーと思った。

 

 

 

ちなみに、NAND回路のみでXOR回路を表現した場合は以下のようになり、先程のものと異なった形となります。ぜひ自分で確認してみてください。

f:id:kera6rhy:20170701144646p:plain

 

 

CodinGame - Code4Life - 参加記

keraです。

 

いつもCodinGameはタイトルが何かしらの映画タイトルになっているはずなのですが、今回の元ネタはよくわかりませんね。

 

今回のゲームは、市民のために薬を開発してスコアを稼ぐゲームです。

今回の順位は世界8/2366位、日本3/48位でした。

 

 

今回のゲーム「Code4Life」の概要

 とりあえず、こんなゲームです。

↓ゲーム画面

www.codingame.com

 

研究室のロボットを操縦して、様々な病気に対する薬を生産することが目的です。色々ルールがあります。

 

・市民に蔓延している病気の(病原体?)サンプルが配達される

・サンプルを解析すると必要な材料が特定できる

・材料には5種類の分子が存在する

・必要材料が揃えば、そのサンプルに対する薬ができ、スコアをもらえる

・サンプルにはランクがあり、高いものほどスコアと必要材料が多い

・薬を作成するとロボットのスキルが上がり、以後、作成の必要材料数が減る

・最終ターン時に、相手よりスコアが高ければ勝ち

 

これに加え、いくつか制限があります。

制限

・一度に持てるサンプルが3つまで

・一度に持てる分子は10個まで

・研究室で同時に存在する分子は、常に各5つ(ある条件下で6つになるが無視)

 

つまり一言でいうと、限られた資源をいかに上手く利用するか、いかに相手の邪魔ができるかが勝負のキモとなります。

 

 

 

実装したアルゴリズム

※この部分はプレイした人向けなので、説明してない部分が大量に出てきます。

基本設計方針

ステートマシン、だと思います。(定義をあまりしらない)

つまり、SAMPLES、DIAGNOSIS、MOLECULES、LABORATORY別にそれぞれ独立した関数を持っていて、ロボットがいる場所を担当する関数しか実行しません。

共有している変数があり(ほぼ全て)、それを利用して各処理が連絡を取り合ってます。

 

基本戦術

高ランクのサンプルはほぼ無視して、扱いやすいランク1サンプルを集めながら相手の妨害を優先します(同時に自分の専門スキル上げも狙います)。すると相手は諦めてクラウドにサンプルを上げるので、それを奪います。

奪うのには以下のメリットがあります。

・相手が自分の代わりに解析してくれるので、時間節約につながる

・相手が諦めるのは自分がそのサンプルの材料を持っているからであり、つまり相手が上げたものは自分にとって美味いサンプルである

まあこの2点が論理的に正しいかはわかりませんが、大体その通りに動きます。

 

どれくらい相手の邪魔をするかというと、相手がサンプルを解析しに行った段階で自分の行動をキャンセルし、分子供給場に向かって妨害待機するくらいです。

 

薬の作成

今回はいかに節約するかが大事なので、薬を提出する順番による専門スキルアップの差も考慮した最適・最小数な方法を追い求めるようにしました。

実装としては、薬の全提出パターンをシミュレートして、最も少ない分子数だったパターンを採用するような形です。

 

相手の妨害

相手が必要としている分子について、相手より先に集められそうならば集めます。自分の薬作成をそっちのけで妨害に走ります。

妨害は自分の手持ち分子が10個になるまでやり尽くします。

 

サンプルのアップロード

いらないサンプルをむやみにアップロードするということは、結局、すぐ相手に持って行かれ(上記の理由より)自分が不利になります。

ここでその時1位だった人の戦術を真似し、既にクラウドにいい物がある時に限り、手持ちのサンプルと素早く交換するようにアップロードするようにしたところ、確かに強くなりました。

 

 

感想

まあまあ満足です。

今回は一日平均3時間しかかけないでこの記録を出せました(今までは平均約9時間)。Ghost in the Cellの記事で書いた今後の目標の「最低限文化的な生活を送りながら」という部分が達成できたと思います。

 

また、今回は前回のCODERS OF THE CARIBBEANの記事でも書いた、コンテストにおける知見・改善案を実践してみました。以下の2つです。

・バグ撤去よりも新機能の実装を優先する

・上位陣の戦略をよく観察する

2つ目はいいと思いますが、1つ目に関してはこれが良い決断かは断言できません。しかし、実際にこうして好成績を残せたのは事実です。考察の余地はあるのではないでしょうか。

ちなみに、実は最終提出AIには(割りと致命的な)バグが有りました。結構頻繁に無限反復横跳びやり始めます(もちろん負けます)。これがなければもう少し順位上がったと思いますが、時間がありませんでしたね。

やっぱりバグ撤去と新機能の実装はトレードオフなんですかね。バランスが大事なんですかね。

 

一度でいいから優勝したい。

 

Codingame - CODERS OF THE CARIBBEAN 参加記

 

 

CODERS OF THE CARIBBEAN、タイトルからして海を連想させますね。

今回は船から大砲を撃って敵を倒すゲームです。

今回の順位は世界66/3623位日本5/69位でした。

↓ゲーム画面

www.codingame.com

 

今回のゲーム

・2人プレイ、ターン進行系、六角形タイル状マップのゲーム

・1人で1〜3隻の船を操作する

・船は地雷の設置や大砲の発射、船自体を衝突させるなどができる

・船は常に燃料を消費し、尽きたら沈む

・海に散りばめられている樽を回収すると燃料が補充できる

・相手の船を全て沈めれば勝ち

というものです。

 

実装したアルゴリズム

基本方針

船1隻に対して個別に2ターン先までを全探索(残り1隻のときは3手先まで)。

1ターンで船1隻が行える行動は、待機、加速、減速、左旋回、右旋回、大砲の発射の計6パターンと見て実装。

最初は3隻の移動パターン全ての全探索(1ターン:6×6×6=216通り、2ターン:216×216=46656)を実装したが、処理制限時間である50msを越えてしまうため、このような(6×6×3(隻))^2=11664通りで省略する形となった。(1ターン先しか読まないと詰み攻撃を回避できないため、2ターン先読みは外せない)

 

移動系

基本は近い樽に向かって移動。燃料を相手より多く保持するかが重要なため、意図的に樽を入手するタイミングは遅らせたりしている。

次ターンで敵攻撃の被弾(地雷や大砲)が確定してしまうタイルには触れない。

樽を全て回収した後は、敵の船に近づかせる。

何かあった時すぐ移動できるように、船の前方は空きタイルを保つ。

マップの端にいるにも関わらず、船がマップ外の方向に向いていたらペナルティ。(逃げ道が確保できない)

 

攻撃系

大砲の発射は、敵がそのまま真っすぐ進んだ場合の場所を狙う。

地雷も設置出来るが、戦略的な重要性が良く分からず実装はやめた。

自分より相手の近くにある樽に対しても大砲で狙い、敵の樽回収を妨害する。

 

生贄

実は燃料を残したまま被弾して一気に燃料0になると、その場に樽を残していく。その樽をうまく回収すれば自分の燃料がまた増え、相手より長く生き続けられる。これを狙うためにわざと自分自身を攻撃してその場に樽を出現させる戦術がある。(生贄)

樽を全て回収した時点で相手の方が燃料が多かった場合、自分の船1隻を生贄に捧げる。

 

感想

コンテスト期間10日間中95時間もかけてこの結果なので、正直なところ惨敗という感じです。

シミュレーターのバグを除去することに手こずり、勝利要素の考察に時間を使っていませんでした。(結局コンテストが終わってもバグは無くならなかった)

ランキング上位の動きを見てみると、いかに詰み攻撃をするかという攻めの戦略をしてましたが、私が必死で実装してたのはどのように敵より長く生き残るかと言った守りの戦略でした。上位陣の試合は常に見れるはずなのに目の前のバグに四苦八苦して、考察を疎かにしたことが敗因です。

 

改善点を挙げるならば、目の前にあるバグを完全に除去することよりも新しい機能・戦術の実装を優先すべきである、といったところでしょうか。

次回も頑張ります。

 

 

 

Codingame - Ghost in the Cell の参加記

keraです。

世界4位という肩書をもらえて幸福度が絶賛上昇中です。

↓順位表へのリンク

www.codingame.com

 

内容

・codingameとは

・今回のゲームの概要

・コンテストを振り返る

・本コンテストで必要だと感じたスキル

・感想

 

 

Codingameとは

・世界中の人が参加できるゲームAI系のプログラミングコンテスト

・年に5~6回のペースでコンテストが開催

・1週間ほどの制限時間の中で戦う

Webページ上で参加できるので、参加するためにまず○○を導入する(よくこれに結構時間がかかる)というものが無い点では、初心者に優しい。(ただしページは英語)

 

 

今回のゲームの概要

今回のGhost in the Cellというゲームは、簡単に言えば軍隊に指示を出して敵を倒すゲームって感じです。(似ているゲームが思いつかない...よくストラテジーゲームと言われるものに近いかも)

ゲーム勝利条件は相手の軍隊の殲滅か、最後に軍隊数が多かったほうが勝利となっています。

↓のリンクに実際のゲーム画面が載ってます。

https://plus.google.com/+Codingame/posts/AnXzBKaSaUH


ゲーム自体は質素に見えるかもですが、自分の作ったAIが世界の誰かが作ったAIと勝負すること自体に燃えるので意外と楽しい。

 

 

コンテストを振り返る

今回の期間は2017/2/26(日) 2:00(深夜)~2017/3/6(月)4:00(深夜)

(フランス企業が主催なのでどうしても時差が)

ちなみに学生で春休みだったので毎日6〜14時間ほどやってました。

 

2月26日

朝起きたら日本のスタートダッシュ勢の一人が暫定世界一位を獲得!この人を目標に頑張る

 

2月27日〜3月1日

ずっとバグに悩まされる。やればやるほど弱くなっていって自信を無くしてた。

コードが汚いのが原因だと考え、一度コード全体を整理整頓した。コードの全体像を把握することができ、そして必勝法を思いついた(あとで考えてみればそうでもなかった)。

 

3月2日

ひらめいた戦略(攻撃型ではなく防御型が最強なはずだ!)を実装したら順位が急上昇(確か3000人中500位→40位) 

細かい付け足しの後、暫定世界一位に (一瞬)

 

3月3日〜6日

終盤に入り、強い人が続々と追い上げてきた頃。

・細かいバグ取り

・対戦してわかった戦略上の穴を埋める

・強い人の戦略を盗み取る

をひたすら繰り返す。(ちなみにコンテスト中は自分のAIがずっと他の人と対戦してます)

そして最終的には世界4/3508位、日本1/81位に決定!(ちなみに学生のみなら世界1/1150位)やったぜ!

 

 

 本コンテストで必要だと感じたスキル

考察力

・このゲームはどのような戦略なら勝てるか

・ルール上の穴は無いのか

・相手の戦略は何が来そうか

のようなことを考える力

 

観察力

・なぜ今この相手に負けてしまったのか(相手との差は何か)

・相手のAIから盗めるものは何か見つけられるか

・今の自分のAIにバグのような挙動は見られるか

のようなものを対戦リプレイから見つける力(コンテスト中は対戦のリプレイを見ることができる)

 

実装力

・いかに制限時間内に頭の中の戦略をソースコードに変換できるか

・いかに早くバグに対処できるか

のような、いわゆるプログラミング力

 

逆を言えばこれらの力が身についたと感じました。

 

 

感想

今回僕が上位に行けた要因は、多少の考察力・観察力・実装力に対してのドーピング役となる「有り余る時間」 があったからですね。いわゆる時間パンチです。(あとレッドブル毎日飲んでました)

つまり他の全てのことを犠牲にしてるので、あまり賢くないです。

今後の目標は、このようなコンテストがあっても自分の勉強や文化的生活レベルを犠牲にする必要がない程度まで、 考察力・観察力・実装力をあげることですね。

 

追記 4/4

Github上に載せていた最終版AIのコードを削除いたしました。

Codingameはコンテスト終了後も同じゲームを継続してプレイできることが特徴です。

実は私のコードを丸コピしてプレイしている人が一定数いるらしく、コンテスト後の継続プレイに対する楽しみ(トップを目指す楽しみ)を奪ってしまうことに繋がるため、今回のような削除をしました。(私の配慮が足りていませんでした。)

 

裏を返せば(?)、いつでもGhost in the Cellをプレイできます!みなさんやりましょう!