見出し画像

Screepsふりかえり

みつよし

3,4年前からScreepsというリアルタイムストラテジーゲームをプレイしています。
これはユニットの一挙手一投足をプログラムしないとプレイできないというとても硬派なゲームで、さらに使える計算資源が限られるため遊んでいくうちに計算機科学の知識がつくようになります。
昨年は公式マッチに参加したのを皮切りに新アーキテクチャの実装を進めて、コードとゲームの両面で大きな進捗がありました。

ゲームの進捗

Season3

Screepsでは常時デプロイされているMMO世界とは別に、改変されたルールで順位をつけるSeasonマッチが開催されます。
Season3はMMO世界のエンドコンテンツであるPowerを収集することによる順位づけで7-8月に行われました。
シーズンの様子と結果はSeason3の公式タイムラインから読むことができます。

このシーズンでわたしはOSとプロセスによるアーキテクチャに完全移行し、強豪プレイヤーの防備を崩すためのquadと、得点獲得のためのpower processingを実装しました。
具体的な実装はコードの進捗の項で説明します。

初シーズンで勝手がわからず、隣人を潜在的脅威とみなして開始直後に攻撃しているところ

このシーズンで得点を重ねるにはpowerを算出するhighwayという地形を抑えることが必要で、それを為すためには経済的・軍事的な優位に立たなければなりません。
その観点でシーズンを振り返ると、参加プレイヤーは順位ごとに以下のように分類できました。

  1. 上位グループ：経済・軍備が極めて充実しており、得点獲得に全力で取り組める

  2. 次点のグループ：経済・軍備が安定しており、継続して得点獲得ができる

  3. 経済、軍備、得点いずれかが安定せず、得点を継続的に伸ばせられないグループ

  4. 得点を行えないグループ

プログラミングゲームだけあって実装力がそのまま順位に反映されています。
上位グループは経済・軍事の両面で自動化が進んでおり、人間の労働力を高度な意思決定に投入できている印象がありました。
2,3のグループは現状維持は自動化できるものの、能動的な行動に手動の作業が発生しています。そのため、同時発生した複数のイベントに対処できず上位グループとの差が開いてしまっていました。
得点を行えなかったグループは経済・軍事で遅れをとったために近隣の強プレイヤーに攻め込まれたとき抵抗できず、リスポーン後は何もない状態から経済発展を行わなければならないためさらに悪い状態からのスタートという悪循環から逃れられなかったプレイヤーです。

わたしは2. 次点のグループに当てはまります。シーズン中盤までに経済の安定化と得点取得の実装を行い、そこからは近隣の同順位帯プレイヤーを妨害しつつ、順位帯の異なるプレイヤーと相互不干渉の同盟を結んで得点を進め、最終的なシーズン順位は9位でした。

わたしの利用していた仕様が"abusable bug"とされてアップデートで修正される様子


攻撃側のQuadが拠点を潰している様子

このゲームは最初はゲーム上の強さで押すこともできますが、だんだん拮抗してくるため最終的には実装したアルゴリズムによる勝負になります。相手方のロジックの穴を見つけどうやってそれを突くか、自分の実装の不備をいかに減らすか、というハッキング合戦です。

MMO

24時間365日デプロイされている、ゲームの本体マップです。
経済のランキングが月毎に集計されています。

Season3で実装したquadに対抗できるプレイヤーはMMO世界にはあまりいなかったため、軍事力で周囲を平定し拠点を構えることができました。

sectorの大半を占拠してエネルギー算出拠点とした

領土は防御を固めた本拠点と、あらゆる場所に即応できる前線という役割分担で広げています。
このゲームのユニット（creep）は寿命が短いため、活動範囲を広げるためには拠点の間隔を広く取る必要があり、一方でまばらに拠点を置いているだけでは各個撃破されてしまうためです。

BotArena

有志で行っているコミュニティマッチです。
この試合はコードをデプロイしたら人間の操作を禁止し、自動処理のみによって戦わせるというルールで行われます。

わたしのコードは経済の立ち上げはそれなりに早いものの、意思決定と例外処理に手動で対応する必要があるため中盤以降に攻め込まれるとそのままやられてしまいます。
意思決定には世界をあるがままに認識するだけでは足りず、長期的な視点で何が起きているのかという抽象度の高い理解をする必要があり、この部分がまだ実装できていません。

コードの進捗

コードは公開しておりこちらから閲覧できます。
アーキテクチャの変更をメジャーバージョン、ゲーム内メモリのマイグレーションが必要な変更をマイナーバージョンに据えて現在は6.7.37です。

OSとプロセス

元々わたしのbotは巨大なif-elseのブロックでシーケンシャルなロジックが組まれていました。
これは制御対象のユニット数が少ないうちは動いていましたが、スケールするに従って保守性が悪くなっていき、また例外処理にいちいち実装を書き換えないといけないなどの困難がありました。
この問題を解決するために、ゲームの実行中に動的に起動/停止ができる処理のまとまり（プロセス）と、プロセスを管理するOSというインターフェースをつくりました。
プロセスという単位に分割したことで共通処理と引数の境界が明確になり、例外的な事象も専用プロセスとして独立性を維持したまま実装しやすくなりました。
また、プロセスを横断的に管理できるようになったために、CPU時間の消費量ごとにプロセスの実行順を決めるなどの横断的な処理を行えるようになりました。

Quad

Creep（歩兵/作業者ユニット）単体の上限を超える能力を得るために、4体のcreepを隣接した状態で移動させるquadというテクニックがあります。
4体なのは、creepが最大強度で他creepを回復するには対象と隣接している必要があり、ムーア近傍で複数のユニットが互いに隣接できる最大数が4であるためです。
quadのフォーメーションが崩れると味方の支援範囲から外れたcreepに集中攻撃を受けて撃破されてしまうため、常にフォーメーションを組んだ状態で移動せねばならず、これは移動可能な経路が限定されることを意味しています。
また、汎用的なcreepよりも専門化させたものを生成する方が攻撃力が高くなるため、quad中のcreepには戦闘中に正面に立つべき前衛と援護を主体とした後衛が生まれ、常に前衛を敵方向に向けるために方向転換が必要です。
このため、quadを実装するにはフォーメーションを組んだ状態での経路探索と方向転換の仕組みを考える必要があります。

これらの仕組みを解決し任意の仕様のquadを派兵するプロセスを実装しました。
単体のcreepと比較して火力が2-4倍になるため、ゲームそのものの強さを当てにして実装を疎かにしているプレイヤーは相手になりません。

プレイヤーの間でquadは一種のオーバーテクノロジーとして扱われており、全体の合意には至っていないもののOSSとして公開することは控えるべきという考えの人間が多いようです。

経済の自動化

完全、完璧な自動化には至っていませんが、拠点選定と建築計画は自動処理を実装しました。

拠点の選定は地形しか見ていないため、建築ユニットが敵拠点を経路に含んでしまって全滅したり、敵拠点の隣に居を構えて全滅したりとかなり難があります。
これは完全自動試合用にないよりはマシかと思って実装した機能ですが、全滅しても延々とユニット生産を続けて資源を浪費するためない方がマシかもしれません。
課題が多々あるため自動試合以外ではキルしています。

建築計画は、配置の優位性は低いものの、計算量で比較すると他プレイヤーに比べよくできているようです。
A*経路探索アルゴリズムの変形で、その地形のなかで最も良い配置を行うため一定の計算量でそれなりの配置を生成できます。

2022年

1/15からSeason4が始まります。
このシーズンもMMO世界のエンドコンテンツを得点づけに用いる試合です。

今年は意思決定ロジックの自動化に向けて、まずは状況を整理して記録するアーキテクチャを作っていこうと思います。

この記事が気に入ったらサポートをしてみませんか？