Mesa(Python)を用いたスプラトゥーン(?)のシミュレーション

# Mesa(Python)を用いたスプラトゥーン(?)のシミュレーション

## はじめに

みなさんスプラトゥーンはご存知でしょうか？武器を装備して陣地に色を塗り、自分の陣地を広げていくゲームです。簡単に言うと陣取りのようなものです。

今回作るシミュレータを回した様子です。

![territory_map_step_0000.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134021/d3e6e21e-4270-b925-014e-765277aaac5c.png)

![territory_map_step_0100.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134021/7fbc602a-560b-0582-cdf4-a10c0ff3c58b.png)

![territory_map_step_0200.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134021/48057255-4b92-e397-270a-91aaba99efac.png)

![territory_map_step_1000.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134021/0ab070c7-0f5b-8e57-f2af-a2722dfa3116.png)

![territory_map_step_1100.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/134021/f569e0d6-0822-9d76-2b30-6e26b243401c.png)


実際にはランダムに動き回るだけではなく、それぞれの能力に応じてエージェントがお互いに競い合います。今回はエージェントにいくつかの要素を持たせてみました。

- NormalAgent: 各ステップ毎にランダムで１マス移動を行うモデル
- DoubleStepAgent: 一定の確率で2マス移動できるモデル. その代わり数ステップに1回移動ができない
- TerritoryExpanderAgent: 移動したマス以外に周囲のマスを自身の陣地とすることができる
- RandomTeleportAgent: 一定の確率で任意のマスにワープすることができます

これらのエージェント同士で競い合ってどのエージェントが勝つかシミュレーションを行います。なお、エージェントは合計20エージェント参加させ、どの能力をもったエージェントがどの数参加するかはわからないものとします。

またフィールドについては、通常のマス以外にワープパネルを用意し、他のワープパネルにランダムでワープすることができるものとします。

どのエージェントが勝つか予想しながら見てみてください。

Githubのリンクは以下です。

https://github.com/yngwie61/TerritoryGame


## 実装全体の概要説明
今回はPythonでエージェントベースモデル(ABM)のシミュレーション実装を行うときに使用できるライブラリであるmesaを利用します。

上記で説明した各エージェントはランダムウォークのエージェントを継承することで実装を行います。また、陣地(テリトリー)を管理するためのクラスも実装します。

## 実装
### 必要なライブラリのインポート

まず、必要なライブラリをインポートします。 mesa を使用してエージェントベースモデルを作成し、 matplotlib を使用してシミュレーション結果を視覚化します。

```

import random
import matplotlib.pyplot as plt
import numpy as np
from mesa import Agent, Model
from mesa.space import MultiGrid
from mesa.time import RandomActivation
from mesa.datacollection import DataCollector
import os

```
### テリトリーマネージャークラス

クラス名 `TerritoryManager`

このクラスは、エージェントのテリトリーを管理します。テリトリーマップの保持やワープパネルの管理を行います。

```python

class TerritoryManager:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.territory_map = {}
        self.warp_panels = set()
    
    def add_to_territory(self, pos, agent_id):
        self.territory_map[pos] = agent_id
    
    def is_warp_panel(self, pos):
        return pos in self.warp_panels

    def initialize_warp_panels(self, num_panels):
        while len(self.warp_panels) < num_panels:
            x = random.randrange(self.width)
            y = random.randrange(self.height)
            self.warp_panels.add((x, y))
    
    def get_territory_grid(self):
        territory_grid = np.zeros((self.width, self.height))
        for (x, y), agent_id in self.territory_map.items():
            territory_grid[x, y] = agent_id
        return territory_grid

```

メソッドの詳細
- __init__(self, width, height): 初期化メソッド。グリッドの幅と高さを受け取り、テリトリーマップとワープパネルのセットを初期化します
- add_to_territory(self, pos, agent_id): 指定された位置をエージェントのテリトリーとして追加します
- is_warp_panel(self, pos): 指定された位置がワープパネルかどうかをチェックします
- initialize_warp_panels(self, num_panels): ワープパネルを指定された数だけランダムに配置します
- get_territory_grid(self): テリトリーマップを2次元配列として取得します

### エージェントクラスの実装（継承元）

クラス名 `RandomWalker`
このクラスは、エージェントの基本的なランダム移動のロジックを提供します。このクラスは継承元で、各能力を持ったエージェントはこのクラスを継承して各能力を実装します。

エージェントクラスは以下のRandomActivationで説明されている通りで

https://mesa.readthedocs.io/en/latest/_modules/mesa/time.html

    It assumes that all agents have a `step` method.（すべてのエージェントが「step」メソッドを持っていることを前提としています。）

とされていますのでエージェントクラスの継承元にはstep関数を実装します。


```python
class RandomWalker(Agent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.unique_id = unique_id
        self.territory = set()

    def step(self):
        self.random_move()

    def random_move(self):
        pass

```

メソッドの詳細
- __init__(self, unique_id, model): 初期化メソッド。エージェントのIDとモデルを受け取り、テリトリーのセットを初期化します
- step(self): ステップごとに呼ばれるメソッド。 random_move メソッドを呼び出します
- random_move(self): ランダムな移動を行うメソッド。詳細な実装はサブクラスで行います

以後、継承先のクラスでもstepメソッド内部で実行されるrandom_moveに対し各エージェントの能力を実装していくものとします。

### エージェントクラスの実装(継承先)

クラス `NormalAgent`
このクラスは、エージェントがランダムに一歩ずつ移動するロジックを提供します

```python

class NormalAgent(RandomWalker):
    def random_move(self):
        possible_steps = self.model.grid.get_neighborhood(self.pos, moore=True, include_center=False)
        new_position = self.random.choice(possible_steps)
        self.model.grid.move_agent(self, new_position)
        if not self.model.territory_manager.is_warp_panel(new_position):
            self.territory.add(new_position)
            self.model.territory_manager.add_to_territory(new_position, self.unique_id)

```

クラス `DoubleStepAgent`
このクラスは、エージェントが二歩ずつ移動するロジックを提供します。

```python
class DoubleStepAgent(RandomWalker):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.move_counter = 0

    def random_move(self):
        self.move_counter += 1
        if self.move_counter % 6 == 0:
            return
        possible_steps = self.model.grid.get_neighborhood(self.pos, moore=True, include_center=False)
        new_position = self.random.choice(possible_steps)
        if random.random() < 0.7:
            possible_steps = self.model.grid.get_neighborhood(new_position, moore=True, include_center=False)
            new_position = self.random.choice(possible_steps)
        self.model.grid.move_agent(self, new_position)
        if not self.model.territory_manager.is_warp_panel(new_position):
            self.territory.add(new_position)
            self.model.territory_manager.add_to_territory(new_position, self.unique_id)

```

クラス `TerritoryExpanderAgent`
このクラスは、エージェントが自分のテリトリーを拡大するロジックを提供します

```python
class TerritoryExpanderAgent(RandomWalker):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.move_counter = 0

    def random_move(self):
        self.move_counter += 1
        if self.move_counter % 3 == 0:
            return
        possible_steps = self.model.grid.get_neighborhood(self.pos, moore=True, include_center=False)
        new_position = self.random.choice(possible_steps)
        self.model.grid.move_agent(self, new_position)
        if not self.model.territory_manager.is_warp_panel(new_position):
            self.territory.add(new_position)
            self.model.territory_manager.add_to_territory(new_position, self.unique_id)
            for neighbor in self.model.grid.get_neighborhood(new_position, moore=False, include_center=False):
                self.territory.add(neighbor)
                self.model.territory_manager.add_to_territory(neighbor, self.unique_id)

```

クラス `RandomTeleportAgent`
このクラスは、エージェントがランダムにテレポートするロジックを提供します

```python
class RandomTeleportAgent(RandomWalker):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.move_counter = 0
    
    def random_move(self):
        self.move_counter += 1
        if self.move_counter % 5 == 0:
            new_position = (self.random.randrange(self.model.grid.width), self.random.randrange(self.model.grid.height))
        
        possible_steps = self.model.grid.get_neighborhood(self.pos, moore=True, include_center=False)
        new_position = self.random.choice(possible_steps)
        self.model.grid.move_agent(self, new_position)
        if not self.model.territory_manager.is_warp_panel(new_position):
            self.territory.add(new_position)
            self.model.territory_manager.add_to_territory(new_position, self.unique_id)

```

### モデルクラスの実装

クラス `RandomWalkModel`
このクラスは、エージェントベースモデルの全体的なロジックを提供します。

```python
class RandomWalkModel(Model):
    def __init__(self, width, height, num_agents, num_warp_panels):
        super().__init__()
        self.num_agents = num_agents
        self.grid = MultiGrid(width, height, True)
        self.schedule = RandomActivation(self)
        self.territory_manager = TerritoryManager(width, height)
        self.territory_manager.initialize_warp_panels(num_warp_panels)

        self.datacollector = DataCollector(
            agent_reporters={"Territory": lambda a: list(a.territory)}
        )

        for i in range(self.num_agents):
            agent_type = random.choice([NormalAgent, DoubleStepAgent, TerritoryExpanderAgent, RandomTeleportAgent])
            a = agent_type(i, self)
            self.schedule.add(a)
            x = self.random.randrange(self.grid.width)
            y = self.random.randrange(self.grid.height)
            self.grid.place_agent(a, (x, y))
            self.territory_manager.add_to_territory((x, y), i)

    def step(self):
        self.datacollector.collect(self)
        self.schedule.step()
```

メソッドの詳細
- __init__(self, width, height, num_agents, num_warp_panels): 初期化メソッド。モデルのパラメータを設定し、エージェントを作成します
- step(self): ステップごとにデータを収集し、スケジュールを進めます

### シミュレーションの実行部分の実装
最後に、シミュレーションを実行し、結果を視覚化します。陣地を多く持つ順にエージェントを出力します。
以下にシミュレーションのパラメータを指定しています。

- 高さ100マス
- 横幅100マス
- 全試行回数10000
- エージェント数20
- 結果出力頻度100stepに1回出力
- ワープパネルの数20

```python
# Parameters
grid_width = 100
grid_height = 100
total_steps = 10000
num_agents = 20
territory_update_interval = 100
num_warp_panels = 20

# Create the model
model = RandomWalkModel(grid_width, grid_height, num_agents, num_warp_panels)

if not os.path.exists('territory_map'):
    os.makedirs('territory_map')

# Run the model for total_steps steps
for step in range(total_steps):
    model.step()

    if step % territory_update_interval == 0:
        territory_grid = model.territory_manager.get_territory_grid()

        plt.figure(figsize=(10, 8))
        plt.imshow(territory_grid, interpolation='nearest', cmap='tab20')
        plt.title(f'Territory Map at Step {step:04d}')
        plt.colorbar()
        plt.savefig(f'territory_map/territory_map_step_{step:04d}.png')
        plt.close()

        print(f"Step {step} completed.")

agent_territories = model.datacollector.get_agent_vars_dataframe().reset_index()
agent_territories['Territory Size'] = agent_territories['Territory'].apply(len)
top_100_agents = agent_territories.groupby('AgentID')['Territory Size'].max().nlargest(100)
print("Top 100 Agents with Largest Territories:")
for agent_id, count in top_100_agents.items():
    agent = next(a for a in model.schedule.agents if a.unique_id == agent_id)
    agent_type = type(agent).__name__
    print(f"Agent {agent_id} ({agent_type}): {count} cells")

print("Simulation complete.")

```

## おわりに

さて、手元で行ったシミュレーションの結果発表ですが・・・3回回してみました。

試行回数が終了した後のエージェントの陣地は以下。

```
1回目
Top 100 Agents with Largest Territories:
Agent 3 (TerritoryExpanderAgent): 4172 cells
Agent 12 (RandomTeleportAgent): 3920 cells
Agent 1 (DoubleStepAgent): 3888 cells
Agent 5 (TerritoryExpanderAgent): 3792 cells
Agent 7 (TerritoryExpanderAgent): 3785 cells
Agent 2 (DoubleStepAgent): 3711 cells
Agent 17 (RandomTeleportAgent): 3690 cells
Agent 18 (TerritoryExpanderAgent): 3666 cells
Agent 4 (NormalAgent): 3637 cells
Agent 16 (NormalAgent): 3622 cells
Agent 9 (TerritoryExpanderAgent): 3621 cells
Agent 13 (DoubleStepAgent): 3512 cells
Agent 14 (NormalAgent): 3501 cells
Agent 10 (RandomTeleportAgent): 3444 cells
Agent 0 (NormalAgent): 3409 cells
Agent 19 (NormalAgent): 3380 cells
Agent 8 (NormalAgent): 3300 cells
Agent 11 (TerritoryExpanderAgent): 3281 cells
Agent 15 (RandomTeleportAgent): 3172 cells
Agent 6 (NormalAgent): 3130 cells

2回目
Top 100 Agents with Largest Territories:
Agent 18 (TerritoryExpanderAgent): 4462 cells
Agent 4 (TerritoryExpanderAgent): 4303 cells
Agent 12 (TerritoryExpanderAgent): 4259 cells
Agent 6 (TerritoryExpanderAgent): 4127 cells
Agent 0 (RandomTeleportAgent): 4026 cells
Agent 2 (RandomTeleportAgent): 3922 cells
Agent 3 (TerritoryExpanderAgent): 3872 cells
Agent 5 (TerritoryExpanderAgent): 3828 cells
Agent 11 (DoubleStepAgent): 3745 cells
Agent 13 (RandomTeleportAgent): 3719 cells
Agent 9 (TerritoryExpanderAgent): 3711 cells
Agent 1 (NormalAgent): 3699 cells
Agent 10 (TerritoryExpanderAgent): 3670 cells
Agent 15 (RandomTeleportAgent): 3640 cells
Agent 7 (NormalAgent): 3632 cells
Agent 14 (DoubleStepAgent): 3591 cells
Agent 8 (RandomTeleportAgent): 3545 cells
Agent 17 (NormalAgent): 3436 cells
Agent 16 (RandomTeleportAgent): 3372 cells
Agent 19 (RandomTeleportAgent): 3248 cells

3回目
Top 100 Agents with Largest Territories:
Agent 14 (TerritoryExpanderAgent): 4171 cells
Agent 19 (DoubleStepAgent): 4033 cells
Agent 0 (DoubleStepAgent): 4028 cells
Agent 12 (TerritoryExpanderAgent): 4027 cells
Agent 17 (DoubleStepAgent): 4015 cells
Agent 16 (RandomTeleportAgent): 4002 cells
Agent 6 (TerritoryExpanderAgent): 3954 cells
Agent 11 (NormalAgent): 3897 cells
Agent 8 (DoubleStepAgent): 3883 cells
Agent 2 (RandomTeleportAgent): 3702 cells
Agent 18 (DoubleStepAgent): 3655 cells
Agent 13 (DoubleStepAgent): 3611 cells
Agent 1 (NormalAgent): 3570 cells
Agent 5 (NormalAgent): 3560 cells
Agent 3 (RandomTeleportAgent): 3479 cells
Agent 10 (NormalAgent): 3382 cells
Agent 4 (RandomTeleportAgent): 3312 cells
Agent 7 (RandomTeleportAgent): 3190 cells
Agent 9 (NormalAgent): 3147 cells
Agent 15 (NormalAgent): 3061 cells


```

となりました。

考察ですが、今回回した設定ではランダムウォークしか行わないNormalAgentは多少低めのスコアとなりました。一方で、TerritoryExpanderAgentは（みなさん予想通りかもしれませんが）多少スコアが高いと思われます。

次点としてRandomTeleportAgentでしょうか。やはり繋がった陣地しか拡大できない通常のエージェントに対して、ワープ機能は強いようです。

ランダムに2回行動ができるDoubleStepAgentは能力のメリット/デメリットはそこまでパッとしないですが、NormalAgentよりは高いスコアとなっています。

実際に能力を考えたときには気づかず、実際にシミュレーションを回してみてわかったことですが、

- TerritoryExpanderAgentについては陣地拡大に圧倒的に有利な能力をもっているので、2stepに1回しか動けない規制を入れても強いかなと思った。しかし、基本的な動きをランダムウォークにする場合には自分の陣地に戻る可能性もあるためそこまでハイスコアとはならないことがわかった
- RandomTeleportAgentについて、自分の陣地に移動することでロスが生まれることを多少軽減できると思われ、ノーマルのランダムウォークよりは高いスコアで安定していると考えられる。特にワープ率をあげすぎると陣地がほぼつながらず、陣地の広げ方が他のエージェントと比べて特殊になることが図をみてわかった

などがわかりました。ゲームの能力などを考えるときにもシミュレーションと実機プレイテストが非常に大事だと痛感いたしました。

## 参考

mesaのマニュアル

https://mesa.readthedocs.io/en/latest/overview.html