MON.T+α ProgrammingRoom

MON.T+α Programming Room

MON.T+αの活動を綴っています。

【Postmortem】Spring Challenge 2021

f:id:montplusa:20210520022402p:plain

※画像は公式Visualizerよりお借りしました

 

はじめに

 投稿はおよそ二か月ぶりになります。本日は5/6 - 5/17の期間にCodinGame様主催で開催されたコンテスト「Spring Challenge 2021」についての記事になります。全文に目を通してられない方は上の目次だけでもぜひ見ていってください。

 私がCodinGameを知って以降初めて開催されたコンテストだったのですが、うれしいことにLegendに到達でき、結果136位/6867人でした。

 まだプログラミングを初めて間もないのでまだまだ業界用語についてはところどころ間違っていたりすると思いますが、発見された方は優しくご指摘いただけると嬉しいです。

 前回書いたPostmortemはこちら

ゲーム概要

 ゲームルールにつきましては、英語の原文を日本語で読みやすく訳してくださっている方がいらっしゃるので引用します。

雑にいえば木を育てて得点を得るゲームです

最終提出AIの詳細(戦術、アルゴリズム

言語:Go言語

 今回コンテストに提出したAIはGo言語を使用したものになります。元々私が書ける言語はPythonしかなかったのですが、今回後述するようなアルゴリズムを実装する際に実行速度の差が問題になるだろうと予想したため、かなり高速な言語を選びました。速度ならC++やRustもあるではないかといわれるとまさにその通りだと思いますが、単純に自分が苦手としていて知識も足りないので選べませんでした。

アルゴリズム:ビームサーチ

 注:先に言っておきますが、以下のアルゴリズムと評価方法の組み合わせは個人的には推奨しません。その理由を含め詳細な情報・検討内容は別記事にまとめる予定ですので、興味を持ってくださった方は気長にお待ちください。

 アルゴリズムはdepth1をSEED,GROW,COMPLETE,WAITのいずれかの行動一回分に相当させたビームサーチを行いました。ビームサーチは一手目がSEEDであるものとそうでないもので完全に別々の枠を用意し、それぞれの最大から評価値の高いほうを最後に選択するようにしました。以下、AIの概要です。

・深さ:10

・幅(一手目がSEEDであるもののみ) :50

・幅(一手目がSEEDでないもの):120

・盤面評価回数:10000前後

 上の方法で最初の45msで相手がとる行動をビームサーチで探索し、その探索で得た行動をとると仮定した状態で、40msで自分がとる行動をビームサーチで探索しています。

 

ビームサーチを機能させるために選択肢を絞る

 ビームサーチはできるだけ短い時間で高い効果を得たいので、以下の行動は排除しました。

必ず排除するもの

・種がすでにあるときのSEED

・自分の木に隣接したCellへSEED

・12日目以前のCOMPLETE

ビームサーチの一手目の検討時以外では排除するもの

・SEED後のCOMPLETE

・GROW後のCOMPLETE

・GROW後、それより大きい木に対するGROW

 

ゲーム情報・盤面の保持:BitBoard

 今回、初めてBitBoardによって盤面情報を保持してみました。主な理由はビームサーチ時に各手を試すごとに発生するスライスや配列のアロケート?が100msにできる盤面評価回数を少なくしていたからです。今回これに合わせてビット演算も学ぶことができました。盤面は10個のintを用いて

自分、相手のsize3,2,1,0の木の位置で4*2個

自分、相手それぞれでDormantであるかについてで2個

になります。(37bitを使って、対象の木が存在する場合、Dormantの場合に1を立てます)
 richnessについては、richnessは0のものを除くとindexから自動的に定まるので、richnessが0の場所に1を立てたintだけを用意しました。また、隣接情報は、あらかじめ各cellにおいてそのcellとその周囲六マスに1を立てたbitを用意しておき、それを参照して隣接しているかを高速に判定しています。

評価方法:盤面の評価値+各行動の評価値

 盤面の評価値はsunの値ベースで、

value=score*3+sun+(この盤面でDAY23までに得られるsun)

を基本としています。sizeが3の木に関しては順にcompleteした場合に得られるスコア*3を適度に小さくして盤面評価値に加算しています。

ただし、これだけで評価してしまうと相手の要素が少ないので、たいてい最後にまとめてCOMPLETEする

...→COMPLETE→COMPLETE

という実践的でない行動の列が完成してしまう上に、次の日の日光の向きなどを一切考慮しなくなるので、盤面評価のほかに、行動をする際にその行動の妥当性を考えて加点・減点するようにしました。加点・減点のポイントは

SEEDの場合

・SEEDした4日後、5日後、6日後は他の木を陰で隠せるcellか、それとも隠されるcellか

(隠しつつ隠されるようなcellもあります)

GROWの場合

・GROWすることによって一日後、二日後に相手が獲得するsunを減らせるか

COMPLETEの場合

・COMPLETEしたことによって一日後、二日後に相手が獲得するsunが増加してしまわないか

WAITの場合

・過度にSUNを余らせてWAITしていないか

になります。この行動評価の加点・減点ですが、良い行動、悪い行動の着眼点として直感的に正しいことはわかりますが、あまり各行動のバランスの取れるような採点方法ではないではないため、AIの強さはなかなか安定しません。まれに型にはまりそれなりに強くなります。

(なお、Visualizerでは、毎ターンその盤面を評価して評価値に合わせて五種類の表情を出力するようにしてあります。上で述べた盤面評価があまり妥当な評価になっていないことは彼の感情がジェットコースターであることからよくわかります)

最終提出までの失敗から得た教訓

1.Go言語のデフォルトはスライスは参照渡し、配列は値渡し

 Bronzeに到達してすぐはゲームのルールがあまりつかめず、硬直していました。

 とりあえず少し考えてみましたが、やはり何もわからなかったので、とりあえずCell,Treeといった各種classを作成し、入力データをそれらに格納しました。また、与えられるPossibleActionsに頼らず、盤面情報から可能な手を列挙する関数を用意しました。

 ところが、いざこれを使い一手全探索から試してみようとすると、まったく思うような結果になりませんでした。よく確認するとTreeをまとめたtreesというのがスライスで、各行動を試すたびにtreesが変わっているのが原因でした。

 なお、この後ビームサーチを実装したときも、今回ビームサーチは行動のスライスと評価値をセットにしたものを追加して、次の深さで評価値の高いものから順に取り出すという方法を採用していますが、この行動のスライスのアドレスを使いまわしていたことで、次の深さで取り出してみると同じ行動が何個も入っている事件が発生してしまいました。

2.ビームサーチ実装後は、一度正常に機能しているか試す

 ビームサーチを実装すると、それに評価関数をうまくつけてどれくらい通用するか試してみたくなりました。もちろん一度submitしてみるくらいなら問題ないのですが、私はビームサーチが正常に機能しているか試さずにその後評価関数の調整に移ってしまいました。結果、1で述べた同じ行動が何個も入っている事件も中盤まで気付きませんでしたし、なんとそもそもビームサーチ用関数は時間制限で打ち切った場合にちょうど検討していた手を最善として返していたということにも終了数日前まで気づきませんでした。おそらくまだバグが残っているのではないかとも思われますが、もうコンテストに充てられる時間もなかったので実装直後に誤った条件下で肉付けてしまった評価関数が邪魔をして上で紹介したような評価方法になってしまいました。

 私にはよくあることなのですが、土台がある程度形になるとついついその先へと焦ってしまいます。その気持ちを抑え、いま一度土台がしっかりとしているか確認して次へ進むようにしたいです。

3.ローカルでテストする環境を用意する

 今回のコンテストではローカルにコードを保存しつつテストはすべてIDEのみで終わらせていました(私は環境構築が苦手なこともあり今回はそれにかけられるほど時間がありませんでした)。これが原因で、Legend到達前後では自分のAIが強くなっているのかが分からず、サイトの「PLAY MY CODE」を押して一勝しては「強くなったんじゃないか」と期待し、一敗しては「ああ弱くなってるかも」と一喜一憂していました。

 ただし、これについては良かった点として、ゲームの結果が自動的にVisualizerで再生されるので、統計データに惑わされずゲーム内の動きでうまくいっていない動きを確認しやすかったという点もあります。今後はうまく組み合わせる(かVisualizerを含めてローカルで環境構築する)ようにできたらいいなと思いました。

おわりに

 ここまで読んでくださった方、ありがとうございます。この記事はSpringChallenge2021で自分以外の参加者がどんなAIだったのか確認して回っているような方にちらっと紹介する形で投稿いたしました。本記事とは別に、より詳細な情報と検討をまとめた記事を作成する予定ですので、もし興味を持ってくださった方がいらっしゃれば、そちらも見ていただけると幸いです。(投稿までしばらくお待ちください)

更新:投稿しました!

t.co

 今回は日程の都合があまり良くなかったので軽く書いてみるくらいのつもりでしたが、気づけばそれなりの時間をかけてしまいました。次回はより高順位(少し高めに目標をつけるなら賞品ラインくらい)を目指していきたいです。インターネット上ではありましたが、周りでたくさんの人が一緒に取り組んでいるような感じがして楽しかったです。