※このページのゲーム画像は公式Visualizerよりお借りしています。
目次
はじめに
先ほどPostmortemとして投稿したSpring Challenge 2021についてですが、そのゲーム性や、私のAI・戦術の詳細についてもう少し検討したいと思います。この検討内容は断定口調で書くことも多いですが個人の感想ですので、「これは間違っているのではないか」というようなところもあると思います。私の成長になりますのでそういった箇所があれば、連絡お待ちしてます。
以下文体が敬体ではなくなりますが、今回は私の脳内の自問自答の再現ということでご理解のほどお願いいたします。
Spring Challenge 2021のPostmortemはこちら
Spring Challenge 2021のゲーム性
ここでは、Spring Challenge 2021のゲーム性について考える。ここで言いたいゲーム性というのは、ゲームのルールではなく、その性質のことである。一応、このゲーム性の検討によって、ゲームから少し抽象化した性質を抽出して似た性質をもつ別のゲームで利用できるようになりたいと考えている。
基本は資源（sun）をいかに相手より多く集めるかを競うゲーム
今回のゲームでは、あらゆる行動をするたびにsunを消費する。このため
自分が得られるsunの量 ≒ 自分の行動能力
となる。また、最終的にsun3ポイントがscore1ポイントに換算されるので、sunの収入は最終スコアに直結し、各AIがいかに相手より多くsunを得られるかがカギとなる。
これは参加者皆が同意するところであるろうけれども、このゲームはsunはそのまま保持しているよりは木にしておいたほうが将来的なsunが多くなる。したがって、ゲーム終盤か、次のターンにどうしてもコストのかかる行動がしたいということでもない限りはsunはあまり保持しておく利点がない。木はいわば配当がとてつもなく大きい株である。一方で、木が多くなるほどGROWの効率が悪くなるので、いずれは刈り取り、場合によってまた新しく種をまくことになる。
CodinGameで私が取り組んだBot Programmingゲームはそれほど多くないのだが、この資源システムは私の取り組んだ中ではCodinGameのCode Royaleというゲームに少し近そうである。このゲームについて軽く触れると、資源地を建設し、その資源から兵を練兵場で生産し、相手の体力を減らすというゲームである。
相手との影響が少なそうだがそこに順位の差が現れるゲーム
Wood2,Wood1,Bronzeと、ゲームのルールを一通り体験してみると、まるでOptimizationのような感じを受けた。Woodではそもそも相手が関係するルールがあまり適用されていなかったのでもちろんだが、Bronzeでもコンテスト開始当初は影の効果は自分自身の収入のOptimizationとして考慮されることがほとんどだった。コンテスト中よく見られた、とびとびのところにSEEDするというような戦術などがこれに含まれる。
自分のOptimizationとして主に使われていたというのは、このゲームはCellがあるものの、既存の駒（木）を隣接するマスに移動させるといった行動は存在せず（逆にあったらホラーなのだが）、一度植えた木はCOMPLETEするまで消せないので相手の木のあるCellに日光を当てさせないという戦術は、ルールを理解した初期では成功させづらいからである。
しかしこのゲームは比較的Sunを尺度に何が良い行動かをヒューリスティックで当てやすいために、いざコンテスト期間中盤となると、敵を無視したOptimizationを用いたAIは大量に膨れ上がり、敵を無視したOptimizationだけでは、大群に飲まれてしまう。結果、ゲームスコアとしてはさほど大きな差には見えずとも、扱いづらい相手との影響をうまく考慮できたAIが群れから前に飛び出せるようなゲームであった。
前半で劣勢だったのを後半で巻き返すというのが難しいゲーム
このゲームは「資金を株の購入に使って得られた配当金でまた株を購入することを繰り返すゲーム」という形なだけに、序盤に一度劣勢に立つとあまり逆転は見込めない。サイトのほうで負けた試合の様子を観察していると、中盤から後半にかけて相手のほうがたくさん木を収穫しているという状況がよくあるが、そういったときはそもそも前半から劣勢に立たされた結果相手に比べて育っていた木が少ないということが多い。相手がスコアをたくさん獲得したターン前後に目が行きがちであるが、相手がそのターンでたくさんスコアを獲得できた背景にはもっと前の部分での立ち回りの良さがある。なお、特に一番わかりやすい例として、初日に隣にSEEDしてしまう場合、このAIをlegendで提出すると、もれなくこうなる。もちろん圧倒的な実力差があればそんなこともないが、いずれにせよ序盤の悪手は致命的であるということは間違いない。
木をいつ収穫するかの一種のチキンレース
木はいつ収穫するのが一番だろうか？という問いには答えがない。もちろんある程度妥当らしいタイミングは絞ることができる。相手が全く収穫しない場合は、自分の木が多すぎてGROW効率、日光で得られるポイントの効率が悪くなった時に収穫すればよい。一方、相手が途中で収穫する場合、その前に収穫するか収穫が出遅れてしまうかではポイントが異なる。かといって、相手より先に収穫したからと言って有利になるとも限らない。早すぎる段階で収穫すると後に得られるSunが少なくなるため、この辺りはちょうど良いタイミングが選択されるような評価をしなければいけない。この、「ちょうど良いタイミング」がAIにより異なるだろう。以下の文章を読んでみてほしい。
「相手がちょうど良いタイミングでCOMPLETEすると仮定して、それを考慮したうえで自分がちょうど良いタイミングでCOMPLETEする」
何を言ってるかわからないかもしれないが、おそらくこのようにしてCOMPLETEしているAIが多いのではなかろうか。いわゆるDUCT？（ちょっと知識不足だが）というものではこうはならない気もするが、相手を考慮したビームサーチではたいていこうなる。では、
「相手がちょうど良いタイミングでCOMPLETEすると仮定して、それを考慮したうえで自分がちょうど良いタイミングでCOMPLETEする。この自分の行動を仮定して相手のちょうど良いタイミングを考え直してもらう」
とすると相手のちょうど良いタイミングがしばしば変わるのである。
これはこのゲームでの相手の様子をうかがう要素で、私が思うにこの要素がほとんどのBot Programingの題材が持っている特性である。であるので、私は毎度この相手の様子をうかがう要素を見つけ、意識しながらコードを書くことにしている。
なお、育てた自分の木をいつ消すかというこのチキンレースはややCodinGameのSmash the Codeみがある。このゲームを簡単に説明すると、連鎖が1ターンですべて処理されてしまうぷ〇ぷよである。
自身のAIの詳細
ここでは自身のAIについて、その詳細な情報及び、それらに至るまでに考えたことをつづっておく。
アルゴリズム
アルゴリズムは、行動1回=深さ1の、日数を揃えないビームサーチとなった。以下それまでを時系列順に述べる。
最初のアルゴリズムの選定
今回にかかわらず、私はCodinGameのBotProgrammingでは、基本以下の形を採用している。
一手全探索→数手全探索→ビームサーチ
上の変遷には、ひとつ前のコードの大部分をそのまま使えるという利点がある。一手全探索の部分でゲーム情報の格納、大まかな盤面評価などの一連の流れを実装し、数手全探索で再帰的関数あるいはループを用意し、ビームサーチで取り出し数に上限を設ける。段階的にビームサーチに持っていくことで途中途中である程度うまくいっているかが自動的に確認される仕組みのつもりである。
今回もこの流れに従い、ビームサーチを実装した。この上の流れによって作られたビームサーチは自然と深さ1は行動一回に対応する。
ビームサーチはよい選択だろうか？
実際にビームサーチを完成させたが、思ったよりうまくいかなかった。Githubで自身のコードの変遷を確認するとビームサーチが完成した時はシルバー解禁前で、確かこの時の順位は1000位前後であるから、ビームサーチの割にあまりうまくいっていないというのはお判りいただけるだろう。後に実際はビームサーチが壊れていたことが発覚した、というのは置いておき、これには私が考える「ビームサーチの弱点」が如実に表れていると考えた。先に断っておくと「ビームサーチの弱点」というのは、ビームサーチの欠陥ということではなく、しっかり考慮して利用すべき点ということである。
ビームサーチはたいていの場合もっともらしい結果を返してくれるのでついつい何も考えず実装しようとしてしまうが、何も考えずにくみ上げたビームサーチには「良いものを選ぶ」という一方で「現実逃避、先延ばしをしたがる」という弱点がある。仮にビームサーチ中において相手は一切動かないと仮定し、評価値は行動後時点の盤面の評価値のみとして、今回のゲームでいくつか例を考えてみる。
例1.サーチの深さ内では評価が高いが、最終的には勝てないAI
自分：赤
現在のDay：7 （8日目）
ビームサーチの深さ：2 （2回の行動を決める）
盤面評価：その盤面から両者最後までWAITし続けた際の自身の獲得ポイント
上のような場面、盤面評価というのは、このゲームでありがちである。特にこの盤面評価はゲームのルールに従って定めているだけに妥当に思われる。しかし、このような場合にSEEDするという選択肢が浮かぶだろうか。SEEDという行動は将来的にスコアを伸ばすためには必須のシステムであるが、この盤面評価では「SEEDをふくめてあと二回しか行動できませんよ。それ以降はWAITしてもらいます。」といわれているのである。であれば、残り日数も多いのでここはsize1の木を二つGROWし、得られる収入を最大化するであろう。あるいはもしかするとCOMPLETEしてしまったほうが良いという結論が出るかもしれない。いずれにせよ、将来的なスコアのために必須なSEEDという選択肢はビームサーチの上位には上がらず、木がいっこうに増えないのである。
これを解消するにはいくつか方法があるが、その一つとして、「見込み」の評価値を追加するという方法がある。上の盤面評価も最終日までWAITした際のポイントとしているのでもらえる「見込み」のポイントを付けているのだが、それとは別に、「盤面に種があると加点」とか「木（種）の数とそのサイズに応して加点」とかが有効である。ただし、これらの加点方法はルールから生まれるものではないので、各自で適した大きさを設定しなければならないのが難しいところである。
なお、私のAIでは1ターン目にSEEDする行動を別枠でもって置き、SEEDする中での最大評価のものも出すことにしている。あわせて、木の数でわずかに加点したり、SEED先の座標によって行動自体に得点を付けたりもしている。（評価重ねすぎなので非推奨）
例2.最後の深さでの評価は高いけれども、その前までの行動から目を背けるAI
自分：青
現在のDay：7 （8日目）
ビームサーチの深さ：3 （3回の行動を決める）
盤面評価：次の日に自分が貰えるSun-相手がもらえるSun
盤面は例1と同じで、今度は自分は青としている。深さも先ほどより1増えて、全探索よりビームサーチが有効になってくる頃かもしれない。盤面評価も変わって、これは相手の妨害も狙った評価方法だ。（こんな極端な評価はしないと思うが。）
深さ3とあって人間の頭で全部考慮するのは難しいが、私が思うにこのAIがとるのは
GROW 3→WAIT→WAIT
か、この順を入れ替えたものであるだろう。（ほかに同点のものも見つけたが今回紹介したい残念な行動例はこちらのほうが適切なのでこちらを強引に採用する）これが高評価となるのはCell3がSize3にし、二日進めることで、その次の日Cell1,Cell4にある相手の木の収入をなくせるからである。
ただしこれがあまり良い行動ではないことも明らかだろう。このAIは3日後自分の木の立ち位置が優位になることを知り、ビームサーチで最後の深さが2日後になるものを全体的に高評価にしているだけである。だから、今回GROWしたら、次のターンでの探索ではWAITではなく別の木を成長させたり、3ターンの間に「立ち位置が優位になる前の日」を過ぎなければならなくなる頃までゲームが進むと、途端に固執しなくなり行動を変えたりするのである。
これを解消するにはいくつかあるが、私がお勧めしたいのは（自分はコンテスト中にできなかったが）日数をそろえるビームサーチである。例えば3日後まで探索するといったことである。この場合最終局面がすべて同じ日になるので、日について同一条件下で判定できる。これを一般に応用するといろいろな条件でそろえて評価できるが、なんでもそろえればよいというわけでもなく、例えば3回SEEDするまで探索といった揃え方は特に意味を持たない（私は今のところ見いだせない、というだけである）。ビームサーチの書き方が少し変わるので一度行動単位で作ってしまうと書きかえたくなかったりするが、その場合はその点でのディスアドバンテージは覚悟しなければならない。（多分結構痛い。それだけに日数をそろえるビームサーチは賢い）
一応、前の行動まででの評価値を適度に加算していくことで、「最終の深さでだけよいもの」をはじくという手もある。
（例ここまで）
以上二つの例からわかるように、今回のゲームはSEED、GROW、COMPLETE、WAITの効果が同列に並べがたい行動である（特に、SEED、WAITは他二つと大きく異なる）ために、雑に実装したビームサーチでは思ったほどの効果が出せないのである。
最終提出以外のAIのアルゴリズム
最終提出は結局最初に組み上げたビームサーチを基盤にしたものであったが、コンテスト中盤では、あまり1行動を深さ1とするビームサーチで効果が出なかったためにほかの方針のAIも作成し検討した。
・一日を深さ1とするビームサーチ
日は揃えられるので整合性が取れるが、この場合一日に取りうる行動の組み合わせが膨大なだけに扱いきれなかった。
・モンテカルロ木探索
理論の言わんとすることはわかるのだが、実装がよくわからなくてただのモンテカルロ法になってしまった。このゲームではかなり有力な方法だと思う。
これは構想だけで終わったが、私は各ターンでの可能な行動が固定ではないようなゲームでは基本使わないので、今回もあまり使う気になれなかった。
ゲーム情報をどのようにして保持するか
今回、Postmortemでも書いたようにBitBoardを使用した。64bit整数型の変数を11個用意し、木を、プレイヤーごと、サイズごとに2*4個の整数に振り分け、Dormantであるかをプレイヤーごと2個の整数に振り分ける。そして残りの一個はrichnessが0のところを示したものになる。各整数は37bitを使用する。
しかし上の用意の仕方は少々余分で、もし盤面の情報を正確に保持したいだけであれば、以下の8個で充分である。
size0,size1,size2,size3,me,foe,dormant,richness
size0~size3:各セルに該当するサイズの木があれば1を立てる
me,foe:各セルに自分（敵）の木があれば1を立てる
dormant:各セルに行動済みの木があれば1を立てる
richness:各セルのrichnessが0であれば1を立てる
これでも十分に高速である。（例えば自分の木は(size0|size1|size2|size3)&meで求められる）
では、最初に示した11個の整数で保持する方法では何が便利かというと、相手と自分が同じ場所にSEEDした場合に両方の種を植えられるのである。別にこの機能がいらないという人はいらないと思うが、相手側の行動を探索により先に決定して自分の行動を決定する場合、相手の行動と自分の行動がかち合う場合の挙動は考えておくべきである。仮に、ルールに従い両者が同じCellに種をまいた場合どちらも種をまけないとすると、相手側の行動はすでに完全に一つに定めてしまっているので仮定していた今後の相手の動きをシミュレーションできなくなる可能性がある。
例えば、後の相手の行動で、その種をGROWする行動があったらどうするか。それらをすべて無効にする手もあるが、その場合は種の位置を相手に合わせる場合の評価値が高くなってしまうかもしれない。もちろん、それで相手のSEEDが防げるならそれほど悪くないかもしれないが、あくまで相手の行動はこちらの推測でしかないので、予想が外れた場合の悲惨さはこの上ないだろう。
この点、11個の整数を用意する方法では、ゲームのルールを拡張したものになっている。ここでは、各Cellに対して、プレイヤーごとに1つまで木を保存できるので、同じターンでかぶってしまった際には応急処置的に両方の種を植えることで対応できる。シミュレーションの厳密性は弱くなるが、そもそも相手の動きの推測はそれほど的中率も高くないので、さほど問題はないように感じられる。
自分よりも相手に時間をかける
自分のAIの100msの使い方であるが、
最初の45ms・・・相手の行動をビームサーチで決定
その後40ms・・・相手の行動をシミュレーションしつつ自分の行動をビームサーチで決定
である。
これを見ると、相手の行動決定はもう少し短く20~30msでよい気がする。これについては、私のビームサーチが日数をそろえていないことに原因がある。自分の行動についてビームサーチで探索するときに相手も最初の45msで仮定した行動を同時にとってもらうのだが、この時、予測した相手の10ターン程度の行動がたまたまWAITをあまりしない行動だった場合どうなるだろうか。この場合、自分が多めにWAITをとると、あるタイミングで相手が急に動かなくなるのである。結果、まず先にWAITして、相手が全く動かなくなってからボコボコにするというものがビームサーチから得られてしまうことがある。そのため、相手の行動は自分よりも先の深さまで仮定しておくほうが安全である。
種を植える場合は4日後に注目
ある程度AIが完成したもの同士では妨害の強さが勝者を決めるといっても過言ではない。このゲームでの妨害とは、すなわち場所の取り合いか日光の取り合いなのだが、今回は日光の取り合いに注目する。
しかし、木のCOMPLETEを考えない場合、相手の木と影で争うようなところに植えるかどうかはほとんど相手との差を生まない。なぜならば、相手の陰になった3日後には相手が自分の木の陰になるからである。
では、どのようにして相手の妨害にまわるか。一番わかりやすいのは、相手を自分の木の陰にして、その後撤収することである。ただし、このゲームのAIを考えた人はわかると思うが、そんなに臨機応変に動けるものではないし、すぐに撤収するのは今後手に入るSunから見てももったいない気がする。
ならばできるだけ猶予を長くしてみてはどうだろうか。まず明日日が当たる側にあるCellに植えてみる。（下側の画像において、青を自分とした場合）
すると、次の日は種の状態で迎えることになる。いまいち妨害ができていない。また、順調に毎日育てると、その3日後最大サイズで朝を迎えるが、近くの赤の木が成長していたら相手の陰になってしまう。むしろ妨害されてしまうようだ。
同様に2日後、3日後に日の当たる側になるものについても、自分が日の当たる側にいるときに自分の木が最大になっていないためにあまり効果を発揮できず、さらにその三日後には相手の木に隠されてしまう。
種を植えた4日後に相手の木を隠せるかに注目したい。これは画像を見てもらったほうが早い。
上の画像で赤が自分だとして、赤い丸で囲った部分においてほしいのである。その左上でもまあ問題ないのだが、5日、6日後も考えると赤い丸のほうが好ましいように思われる。毎ターン成長させると、4日後は最大サイズで朝を迎えることになる。5、6日後までおいておくと3日連続で妨害することができる。その後はCOMPLETEして得点化することもできるし、その前にsize3を利用して次の場所へSEEDしておくこともできる。
こうやって生まれる差はたかが3~9sunではあるが、ゲーム性で紹介した通り、序盤から中盤、その中でも特にDay7前後で行われる妨害は勝敗を分けうる（Day3とかでやろうとするとsize3にするためのsunが確保できなかったりする）。
おわりに
かなり長くなってしまいましたが、以上で終わりになります。上でいろいろなことを書いていますが、このコンテストでは何より楽しみながらコーディングできたのがよかったです。CodinGameでの次のコンテストは秋のようですが、次の大会も今から楽しみです。
