虚無のゲーム「ルドー」を実装し先手有利説を検証

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

最近YouTubeのゲーム実況を見ることが多いです。
  
最初はスプラトゥーンの実況が多かったのですが、Google様のレコメンドのせいで他のゲームの実況も見るようになり、おかげで何をするにも時間が足りない今日この頃です。

そんなゲーム実況にはAmoung usやApexなど色々なゲームがある中で、今回取り上げるのは[「ルドー」](https://en.wikipedia.org/wiki/Ludo_(board_game))というゲームです。
  
  <div class="separator" style="clear: both;"><a href="https://1.bp.blogspot.com/-NXd8zSNsJkc/YFn3y9OCXhI/AAAAAAAAF2M/jo1aVkqlexMWpaSke5m1ZZD7sjcR4cMhACLcBGAsYHQ/s693/%25E3%2582%25B9%25E3%2582%25AF%25E3%2583%25AA%25E3%2583%25BC%25E3%2583%25B3%25E3%2582%25B7%25E3%2583%25A7%25E3%2583%2583%25E3%2583%2588%2B2021-03-23%2B23.14.11.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="600" data-original-height="543" data-original-width="693" src="https://1.bp.blogspot.com/-NXd8zSNsJkc/YFn3y9OCXhI/AAAAAAAAF2M/jo1aVkqlexMWpaSke5m1ZZD7sjcR4cMhACLcBGAsYHQ/s600/%25E3%2582%25B9%25E3%2582%25AF%25E3%2583%25AA%25E3%2583%25BC%25E3%2583%25B3%25E3%2582%25B7%25E3%2583%25A7%25E3%2583%2583%25E3%2583%2588%2B2021-03-23%2B23.14.11.png"/></a></div>
  
  
  
詳しくは後ほど軽いルール説明をするのですが、このルドー、なかなかに時間のかかる上に運ゲー要素が強く、
  
ちょっとググると、
    
<div class="separator" style="clear: both;"><a href="https://1.bp.blogspot.com/-BuBhMjgJiwo/YFqOvFz-uSI/AAAAAAAAF2Y/VL9qPP0cB7IZKTcckSZT4i6JTL0-wZrdwCLcBGAsYHQ/s699/%25E3%2582%25B9%25E3%2582%25AF%25E3%2583%25AA%25E3%2583%25BC%25E3%2583%25B3%25E3%2582%25B7%25E3%2583%25A7%25E3%2583%2583%25E3%2583%2588%2B2021-03-24%2B9.58.00.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="600" data-original-height="232" data-original-width="699" src="https://1.bp.blogspot.com/-BuBhMjgJiwo/YFqOvFz-uSI/AAAAAAAAF2Y/VL9qPP0cB7IZKTcckSZT4i6JTL0-wZrdwCLcBGAsYHQ/s600/%25E3%2582%25B9%25E3%2582%25AF%25E3%2583%25AA%25E3%2583%25BC%25E3%2583%25B3%25E3%2582%25B7%25E3%2583%25A7%25E3%2583%2583%25E3%2583%2588%2B2021-03-24%2B9.58.00.png"/></a></div>  
  
 という検索クエリがサジェストされます。どうやら虚無で終わらないゲームのようです。

この記事の趣旨は、「そんな虚無ゲーのルドーを自分でやるのは面倒だけど、確かめてみたい仮説がある！」という動機によりPythonでシミュレータを実装して実験してみる、という内容です。

それでは行ってみましょう。

## ルドーとは

もともとはヨーロッパの伝統あるボードゲームのようです。

自分が知ったのはニンテンドースイッチ「世界のアソビ大全51」のゲーム実況ですが、ググってみると自分と同じく日本語の記事はほぼニンテンドースイッチ経由で知った方が書かれていますね。

詳しいルール説明は他の記事を参考にしていただければと思いますが、簡単に言うと、

* サイコロを振ってゴールを目指すすごろく
* 自分の全部のコマをゴールさせれば勝ち
* 6が出ないとスタートラインにすら立てない
* 相手とピッタリ重なると相手をスタートに戻せる
* 一方通行で進む方向は選べない

というゲームで、戦略の絡む部分が少ない運ゲー、かつ

* 6が出ないとスタートラインにすら立てない
* 相手とピッタリ重なると相手をスタートに戻せる

といった、「自分でどうにかできる部分が少ないのに、やってきたことが簡単に無に帰す」という性質が、虚無ゲーと名高い原因でしょう。

ニンテンドースイッチ「世界のアソビ大全51」の中でも平均ゲーム時間が最も長いのに、合計プレイ時間は上位に入ってこないという、「一度遊んで満足する」タイプのゲームみたいです。

今回はそんなルドーを自分でプレイせずに楽しむ記事になります。

ルドーの説明などの記事:

* [世界のアソビ大全51に入っているルドーは虚無を詰め合わせた素晴らしいゲームなのでみんなやりましょう。 - ただの雑記](https://hanbunningen.hatenablog.com/entry/2020/06/06/222015)
* [ルドーという終わらない地獄の虚無、アソビ大全51で平均プレイ時間が長い1位に](https://ga-m.com/n/rudo-owaranai-jigoku-kyomu-game-asobi-51-play/)

## 今回検証する仮説

進行方向が一方通行なので、複数のコマがフィールドに出ている場合にどちらのコマを動かすか、ぐらいの戦略しかなく、ほぼ運ゲーなルドーですが、
今回持ってきた説は

> ルドー先手有利説

です！
  
単純に戦略が少なくサイコロの目が重要ならば手数が増える先手が有利なのでは？という単純な理由です。

Pythonによりルドーのシミュレーションを行うコードを実装し、プレイヤーの行動順序によって勝率に差があるかを検証する実験を行いました。

## ソースコード

シミュレーションのためのコードです。(興味のない方は飛ばしてください)

Pythonで実装しました。

BoardクラスとGameクラス、Agentクラスがメインになります。(Agentについては後述)

```python
class Board:
    def __init__(self, n_pieces, n_players, len_myway):
        self.starts = [n_pieces for _ in range(n_players)]
        self.positions = []
        self.goals = [[] for _ in range(n_players)]
        self.len_myway = len_myway
        self.len_total = len_myway*n_players
        self.n_pieces = n_pieces
        self.n_players = n_players

def depart(self, player):
        if self.starts[player] <= 0:
            raise Exception(f"No piece remain in respawn of player {player}")
        self.starts[player] -= 1
        self.positions.append(self.create(player, 0))

def respawn(self, position):
        self.positions.remove(position)
        self.starts[position.player] += 1

def create(self, player, step):
        return Position(self.len_myway * player+step, player)

def move(self, coordinate, step):
        searched_pos_list = self.search_by_coordinate(coordinate)
        if not searched_pos_list:
            raise Exception(
                f"Specified coordinate {coordinate} does not exist.")

position = searched_pos_list[0]
        temp_coordinate = position.coordinate+step
        goal_coordinate = position.player*self.len_myway
        goal_coordinate = goal_coordinate if goal_coordinate > 0 else self.len_total

if position.coordinate < goal_coordinate <= temp_coordinate:
            # ゴールゾーンにはいる
            available_goals = set(range(self.n_pieces)) - \
                set(self.goals[position.player])
            cands = [
                goal for goal in available_goals if temp_coordinate-goal_coordinate >= goal]
            if cands:
                dest = max(cands)
                self.goals[position.player].append(dest)
            else:
                print("Cannot enter goals.")
                return
        else:
            # publicゾーンを移動
            new_coordinate = temp_coordinate % self.len_total
            result = self.search_by_coordinate(new_coordinate)
            if result and result[0].player != position.player:
                # 衝突
                for opponent in result:
                    self.respawn(opponent)

new_position = Position(new_coordinate, position.player)
            self.positions.append(new_position)

# 前のを削除
        self.positions.remove(position)

def search_by_coordinate(self, coordinate):
        result = []
        for position in self.positions:
            if position.coordinate == coordinate:
                result.append(position)
        return result

def search_by_player(self, player):
        return [position for position in self.positions if position.player == player]

def move_piece_in_goal(self, position, player, roll):
        if position not in self.goals[player]:
            raise Exception(
                f"{position} does not exist in Player {player}'s goal.")

available_goals = set(range(self.n_pieces))-set(self.goals[player])
        cands = [goal for goal in available_goals if position+roll >= goal]
        if cands:
            dest = max(cands)
            self.goals[player].append(dest)
            self.goals[player].remove(position)

def apply(self, action):
        """actionを適用する."""
        if action.target.__class__.__name__ == "Position":
            # 公道にいるコマがターゲットの場合
            self.move(action.target.coordinate, action.roll)
        elif type(action.target) == int:
            # goalにいるコマがターゲットの場合
            self.move_piece_in_goal(action.target, action.player, action.roll)
        elif action.target == "depart":
            # スタートする
            self.depart(action.player)
        else:
            raise Exception("Invalid action target.")

```

```python
class Game:
    def __init__(self, board, agents_class_list, max_turn, max_roll=6, min_roll=1, depart_roll=6, shuffle_agent=True, verbose=False):
        if board.n_players != len(agents_class_list):
            raise Exception("The number of players does not match.")
        self.board = board
        if shuffle_agent:
            random.shuffle(agents_class_list)

self.agents = [agent_cls(i)
                       for i, agent_cls in enumerate(agents_class_list)]
        self.max_roll = max_roll
        self.min_roll = min_roll
        self.max_turn = max_turn
        self.depart_roll = depart_roll
        self.verbose = verbose

def play(self):
        for turn in range(self.max_turn):
            print(f"[Turn {turn+1}]")
            turn_agent = 0
            while (turn_agent < len(self.agents)):
                roll = self.roll()
                agent = self.agents[turn_agent]
                action = agent.choose_action(
                    self.board, roll, self.depart_roll)
                if not action:
                    print(f"Player {agent.player_idx} passed.")
                else:
                    print(action)
                    self.board.apply(action)

if self.verbose:
                    self.board.print_board()

if len(set(self.board.goals[agent.player_idx])) == self.board.n_pieces:
                    print(f"Player {agent.player_idx} finished!!")
                    return {"status": "finished", "turn": turn+1, "winner_idx": agent.player_idx, "winner_agent": agent.__class__.__name__}
                if roll != self.depart_roll:
                    turn_agent += 1

return {"status": "ongoing", "turn": turn+1, "winner_idx": None, "winner_agent": None}

def roll(self):
        return random.randint(self.min_roll, self.max_roll)
```

呼び出し側ではgameにboardとagentを渡してplayメソッドを呼びます。

ざっと書いたのでもう少しいい設計でかけそうですが、今回はこの辺でよしとしました。

```python
def simulate(agents,n_trials,n_pieces, len_myway,max_turn, n_players):
    winners_idx=[]
    winners_agent=[]
    turns=[]
    for i in range(n_trials):
        board=Board(n_pieces=n_pieces,n_players=len(agents),len_myway=len_myway)
        game=Game(board=board,agents_class_list=agents,max_turn=max_turn)
        result=game.play()
        winners_idx.append(result["winner_idx"])
        winners_agent.append(result["winner_agent"])
        turns.append(result["turn"])
        
    df=pd.DataFrame()
    df["winner_idx"]=winners_idx
    df["winner_agent"]=winners_agent
    df["turn"]=turns
    return df
```

本記事では読みやすさのため省略しましたが、Boardクラスにデバッグ用の盤面表示メソッドを作って可視化しながら実装しました。

しばらくデータ分析関連のコードしか書いていなかったので、競プロチックなコードを久しぶりに書きましたね...

今回使ったコードはGitHubに置いてあります。

[GitHub - habroptilus/ludo](https://github.com/habroptilus/ludo)

## ランダムCPU×4 で実験

まず、とりうる行動の中からランダムに行動するagentを作ります。

Agentクラスを継承し、`choose_action`メソッドを実装していきます。

```python
class Agent:
    def __init__(self, player_idx):
        self.player_idx = player_idx

def choose_action(self, board, roll, depart_roll):
        raise Exception("Not implemeted error.")

class RandomAgent(Agent):
    """実行できるものの中からランダムに実行する."""

def choose_action(self, board, roll, depart_roll):
        choices = []
        # positionを追加
        choices += board.search_by_player(self.player_idx)

# goalのうち、もう動かせないものを除外して残りを追加
        goals = board.goals[self.player_idx]
        temp = board.n_pieces
        while True:
            if temp in goals:
                goals.remove(temp)
                temp -= 1
            else:
                break

choices += goals
        if (roll == depart_roll and board) and board.starts[self.player_idx] > 0:
            choices.append("depart")

if not choices:
            # パス
            return None
        chosen_target = random.choice(choices)
        return Action(player=self.player_idx, target=chosen_target, roll=roll)
```

1000回シミュレーションし、行動順ごとに一位抜けの回数を記録した結果がこちらです。

|行動順序|一位の回数|
|----|----|
|2|    273|
|1|    249|
|3|    245|
|0|    233|

あれ、ほとんど差がなさそうです。

念のため行動順によって勝率に差がないという仮説を帰無仮説とし、有意水準5%で適合度のカイ2乗検定をします。

```python
from scipy.stats import chisquare

chisquare(f_obs=df["winner_idx"].value_counts().values, f_exp=[n_trials/ n_players ] * n_players)

```

```
p値 = 0.3372041599563994 > 0.05
```

となり、帰無仮説を棄却できませんでした。

当初たてていた仮説である「勝率に行動順序は影響する」は立証できなかったことになります。

## シンプルロジックCPU : ランダム=2:2で実験

次にたてた仮説は、

> ランダムAgentが弱すぎて先手に有利な盤面が来てもチャンスを活かしきれてない説

です。

この説を検証するため、簡単に思いつくロジックをいれたSimpleLogicAgentを作りました。

```python
class SimpleLogicAgent(Agent):
    """以下の優先順位で実行する.

:6がでてスタートできるならスタートさせる
    :相手を踏めるなら踏む.
    :ゴールできるならゴールする.
    :公道にいるのをランダムに進める
    :ゴールにいて進めるものがあるなら進める
    """

def choose_action(self, board, roll, depart_roll):
        # 6がでてスタートできるならスタートさせる
        if (roll == depart_roll) and (board.starts[self.player_idx] > 0):
            return Action(player=self.player_idx, target="depart", roll=roll)

# 相手を踏めるなら踏む
        my_pieces = board.search_by_player(self.player_idx)
        for piece in my_pieces:
            searched = board.search_by_coordinate(
                (piece.coordinate+roll) % board.len_total)
            for target in searched:
                if target.player != self.player_idx:
                    # 踏める相手がいる
                    return Action(player=self.player_idx, target=piece, roll=roll)

# ゴールできるならゴールする.
        goal_entrance_coor = (
            board.len_total + self.player_idx*board.len_myway-1) % board.len_total
        for piece in my_pieces:
            if piece.coordinate+roll > goal_entrance_coor:
                return Action(player=self.player_idx, target=piece, roll=roll)

# 公道にいるのをランダムに進める
        if my_pieces:
            return Action(player=self.player_idx, target=random.choice(my_pieces), roll=roll)

# goalのうち、もう動かせないものを除外して残りのコマをランダムに選んで動かす
        goals = board.goals[self.player_idx]
        temp = board.n_pieces
        while True:
            if temp in goals:
                goals.remove(temp)
                temp -= 1
            else:
                break
        if goals:
            return Action(player=self.player_idx, target=random.choice(goals), roll=roll)

# 全て該当しない場合はパスする
        return None

```

docstringに書いてあるとおり、優先順位をつけて上から該当する行動があればそれを実行するというものです。

ゲーム実況系YouTuberさんがやっているのをみてなんとなくこうじゃないかと考えて実装してみました。

* 6を出さないとスタートできないので6を出した時は優先的にスタートに立たせる
* 相手を踏んでスタートに戻らせることができるなら積極的に攻撃する

など、ある程度人間に近いロジックになったかと思います。

このSimpleLogicAgentを使って行動順序と勝率の関係をみる前に、まずはこのSimpleLogicAgentと先ほど使ったRandomAgentを2人ずついれて4人で1000回戦ってもらいました。

その結果がこちらです。

|Agent|勝利回数|
|----|----|
|SimpleLogicAgent    |997|
|RandomAgent         |  3|

かなり簡単なルールベースの戦略ですが、ランダムには圧勝しています。

## シンプルロジックCPU×4 で実験

最後に、SimpleLogicAgent4人で1000回試合をして勝率をみてみます。
  
RandomAgentの時は行動順序によって勝率に有意な差がありませんでしたが、今回はどうでしょうか。

|行動順序|一位の回数|
|----|----|
|0|    413|
|3|    229|
|1|    191|
|2|    167|

先手の勝率がかなり高いです！

適合度検定もRandomAgentの時と同様に行うと、

```
pvalue=3.344338567294904e-32 < 0.05
```

となり、有意水準5%で帰無仮説が棄却されました。
                                   
ランダムAgentが弱すぎて先手に有利な盤面が来てもチャンスを活かしきれてない説、立証です。

ランダムだと行動順序によって勝率に有意な差はありませんでしたが、ある程度人間に近いロジックの人だと、先手有利になるのでしょうか。

## まとめ

* ランダムに行動する場合はプレイヤー順で有利不利がなかった
* ある程度まともなAgentにすると先手プレイヤーが有利だった
* 簡単なロジックでもランダムよりはかなり強い

簡単なロジックでもランダムと勝率に差が出るにもかかわらず運ゲーと呼ばれてしまうのは、簡単なロジックまでは誰でも思いつくがここから差がつかない、というのが原因かと考えられます。

今回は調べられなかったですが、Agent同士の相性、順序なども影響しそうです。
実際には、他にも勝ちそうなプレイヤーの邪魔をするような傾向もあると思われるので、対人同士でのプレイにおける行動順序による影響は実験結果よりも緩和されそうです。

Agentクラスを継承して実装することで新しく考えたロジックを試すことができるので、もう自分で虚無を味わうことなくルドーを楽しめますね！

最後までお読みいただきありがとうございました。

このブログを検索

ぐぐりらにっき

虚無のゲーム「ルドー」を実装し先手有利説を検証

コメント

コメントを投稿

虚無のゲーム「ルドー」を実装し先手有利説を検証

この記事をシェアする

コメント

コメントを投稿