2018の20日目として書かれた記事です。ついて?」の予定です。初めましての方は初めまして、Misterです。東京大学のTSGというプログラミングサークルに所属しています。ライブ競技プログラミング反省」という記事を書きました。今回はその続きとして、私がプレイヤーとして参加したもう1つの企画「ライブAIプログラミング」について書きます。簡単に説明すると、「ライブAIプログラミング」は「75分間でできるだけ強いゲームAIを作る」という企画です。「ゲームAI」と言ってもそこまで大それたものではなく、ゲームをプレイするプログラム全般を指します。コンテストの内容と感想、盤面生成に関する妄想など」という記事を投稿しています。裏の話が見られて面白いので、ぜひこちらも読んでみてください。ゲーム概要まずこのゲームは攻守に分かれてのターン制で行われる。まばらに壁が配置され、外周が壁で囲まれた2次元グリッドがある。各ターン、攻撃側はBeam、守備側はTargetのうち1台を、4方向のうちいずれかに動かすことができる。このとき各ロボットは壁か他のロボットに接触するまで、止まることなく直進し続ける。Beamは移動の際、移動する方向にビームを打つことができる。ビームは壁によって遮蔽されるが、ビーム上にいたTargetは消滅する。ビームは盤面上に残り続け、Targetにとっては壁となる(接触しても消滅はしない)。各ケースについて攻守を交代し、共通の盤面にてゲームを行う。攻撃時にTargetをより早く全滅させたプレイヤーに所定のスコアが入る。ゲームは最大300ターンまで行われる。制約、スコア、ケース数は以下の通り。大体上の通りですが、文で言われてもイメージが湧かないと思います。先に上げたmoratorium氏の記事にゲーム動画が載っているので、そちらも参照していただけると良いかと。本番の流れ環境整備それでは早速乱択を、とやりたくなりますがここで思い留まります。過去に何度か長めの実装をした経験1から、適当に実装したら後でコードが壊滅することは目に見えていました。いって、十分丁寧に実装するには75分は短いかも分かりません。悩んだ結果、自分の実装スピードを信じてクラスから実装することにしました。結果としては実装が幾分楽になったので、この判断は正しかったように思います。初期段階では、クラスの構造は以下のような感じでした。targets;};一番懸念していたBoard::load()の実装もそれほど複雑ではなく、各メンバ関数の具体的な実装は20分くらいで終わりました。ちなみにこれは競プロの癖ですが、わざわざメンバ変数をprivateにはしません。普段のプログラミングでやったらアウトですが、どのみち使い捨てるコードなので。壁のない方へそして乱択の実装に移るわけですが、この際少し動きを工夫しました。隣接マスが壁であるような方向に移動すると、そのターンロボットは移動できません。これは基本的に不利です。いうのも攻撃側なら全然Targetを探せないし、守備側ならBeamにとって格好の的になってしまうからです。いうことで、少しだけコードをイジって「1マス先が壁でない方向へ移動する」ようにして、乱択を提出しました。この時点で大体30分です。二重for文で同じ変数名を使っている。遷移をミスって、forで無限ループが起きる2。壁を表す文字を勘違いする3。いった酷いミスを連発しており、これらの対処に20分ほど費やしてしまいました。次に目指したのは「攻撃時にBeamと同じ列か行にいるTargetを確実に潰す」という動きの実装です。そのために、「指定された方向の先にTargetがいるか判定する」Robotのメンバ関数を実装しました。具体的には「壁にぶつかるまで移動して、途中でどれかのTargetの座標と一致したらtrueを返す」という簡単なものです。これを提出したのが60分頃。ビジュアライザを見るとたまに上手く動いていないときがあり、その原因を探っていたらコンテスト終了になりました。ちなみに以下が最後までバグらせていた箇所です。コンテスト後、ここを修正したらちゃんとTargetを潰してくれました。Beamを避けるコンテスト中は時間がなかったので、Targetの動きは最後まで乱択でした。それでは物足りなかったので、コンテスト後に延長戦として「Beamと同じ行、列になるような箇所に移動しない」という動きも実装しました。実装できて理想通りの動きをしてくれたのですが、なぜかこれがrandomに負けるという始末4。ゲームAIって難しいですね。ちなみに最終的にクラスの構造は以下のように変わりました。targets;};やりたかったこと今回はコードのテスト用に、運営側で「random」「cat」という2つの対戦用AIを用意していただきました。強いcatはおろか、上に述べた通りrandomにも安定して勝てるAIは作れませんでした。数手掛けてTargetを潰すようなムーブを探索する。Targetを極力スペースが広い、かつBeamから遠い箇所に逃がす。考えられますが、上手い実装が思い浮かびません。機械学習やゲーム理論を学べばもっと強いのが作れるかも知れませんが、当然ながら知識及ばず。なんとかしてcatに勝ちたいですね。感想1つ言わせてもらうとすれば、75分は非常に短いです。こと1週間ほど用意して、当日に複数人のAIを戦わせるのもありかもしれません(それはライブプログラミングではありませんが)。少なくとももっとハイレベルな戦いが見れると思います。それとやはりゲームAI実装は難しいです。競プロ以上に複雑な実装もこなせるようになりたいですね。本記事は以上になります。ここまで読んでいただきありがとうございました。6文字でJSを書く話」です。JSはJavaScriptとして、5、6文字とは......?楽しみですね。4)のように、ループ回数を制御するiをインクリメントし忘れました。競プロで壁と言えば#なのですが、今回は*でした。実はBeamを避ける機能を実装する前後で、randomに対する勝率が落ちました。Targetの動きが狭まったことが原因でしょう。※各問題名は表記ミスではありません。長さの数列が与えられる。「Attention」の解説。Cuboid」の解説。公式はてなブログをはじめよう!misteerさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。