Zenn
🍩

絶対に負けない三目並べを作る

2022/09/23に公開
Python
ゲーム
アルゴリズム
tech

三目並べはきっと誰でも遊んだことのある他愛無い遊びですが、「じゃあプログラムで三目並べの AI を作ってください」と言われると意外と悩む人もいるのではないでしょうか。今回はそんな三目並べの絶対負けない AI を作る方法について、コードをいちから書いて実装したいと思います。

実装については三目並べが囲碁や将棋と異なり、比較的パターン数が少ないため全盤面の探索を行い、勝てる(負けない)パターンを見つけることで最良の手を打つようにします。つまり乱択アルゴリズムではなく、決定的であるということです。

さて、三目並べですが、ゲームに対する認識の齟齬がないように条件をあらかじめ整理したいと思います。一般的なルールでは次のような条件になっているかと思われます。

  1. ゲーム盤は 3x3 のマス目からなる
  2. O または X が先攻となり交互に空いているゲーム盤のマスに印をつけていく
  3. タテ・ヨコ・ナナメに同じ印が3つ並んだら、その印のプレイヤーが勝利する
  4. 印を置ける箇所がなくなったら引き分けとなる

この条件が提示されたときに、次に我々がしなければならないことは、どうすれば勝てる(負けない)かを考えることです。それには具体的な盤面を考えてみましょう。

どうやれば絶対に勝てる(負けない)かを考える

初手を考える

方策を考えるときには図に書き起こすと発想が浮かびやすくなります。ということで三目並べの最初の盤面について考えてみたいと思います。

Fig.1           Fig.2          Fig.3
+---+---+---+   +---+---+---+  +---+---+---+
| X |   |   |   |   |   |   |  |   | X |   |
+---+---+---+   +---+---+---+  +---+---+---+
|   |   |   |   |   | X |   |  |   |   |   |
+---+---+---+   +---+---+---+  +---+---+---+
|   |   |   |   |   |   |   |  |   |   |   |
+---+---+---+   +---+---+---+  +---+---+---+

Fig.1, 2, 3 は X が先攻としてを置いた取りうる盤面の組み合わせです。回転・反転を含めればこの三種類になるのでこの3パターンについて考えてみます。

Fig.1, 2 は直感的に良さそうな配置に見えます。これはタテ・ヨコ・ナナメのどの方向にも勝利の目が見えるからです。一方で Fig.3 はナナメの線が死んでおり、明らかに Fig.1, 2 よりは劣る手だと判断できます。ですが、Fig.1 と Fig.2 を比較したときにどちらがより有利なのかはぱっと見ではわかりません。これにはもう少しゲームを進めてみないと有利不利を判定できません。

Fig.4           Fig.5
+---+---+---+   +---+---+---+
| 1 | X | X |   | X | O | X |
+---+---+---+   +---+---+---+
| 2 | O | O |   |   | X |   |
+---+---+---+   +---+---+---+
| X | 3 | O |   |   | O |   |
+---+---+---+   +---+---+---+

少しゲームが進んだ盤面 Fig.4 を考えてみます。1 に X を置けば勝利しますが、2 や 3 に置くと次の O の手番で敗北することが予想されます。なのであと一手で勝てるような状況になったら、それを判定して的確なマスに印を配置すればいいように思えます。

しかしそうなると、あと一手で勝てる状況というのはあと二手で勝てる状況に依存した状況であり、
あと二手で勝てる状況というのはあと三手で勝てる状況です。最終的には初手の状況に依存していることになります。困りました。勝利する(負けない)ためにはなにもヒントがない初手を考えないといけないことに気づいてしまいました！

それにあと一手で勝てる状況というのは罠もあります。Fig.5 の O は自分が勝つことだけを考えた結果、負けない状況を作り出すことに失敗しています。

勝ち負けがわかる状況を考える

ここで発想を変えてみます。逆に究極的に勝ち負けが判定できるのはどの場合でしょうか？もっと言えば、どんな盤面なら手の評価ができるでしょうか？確実なのは勝利した盤面・敗北した盤面です。

Fig.6           Fig.7
+---+---+---+   +---+---+---+
| X | X | X |   | O | X | O |
+---+---+---+   +---+---+---+
|   | O |   |   | O | X | X |
+---+---+---+   +---+---+---+
| O |   | X |   | X | O | X |
+---+---+---+   +---+---+---+

Fig.6 は X が勝利した盤面で、Fig.7 は決着が付かなかった盤面です。これであればすでに結果が決まっているので良い手かどうか評価できます。便宜的に Fig.6 では X が勝利しているのでスコア 1、Fig.7 では引き分けなのでスコア 0 とします。そして図にはありませんが逆に O が勝利した場合はスコア -1 とします。

さてこのスコアを使って手の良さを評価できないでしょうか？

Fig.8           Fig.9-A         Fig.9-B
+---+---+---+   +---+---+---+   +---+---+---+
| X | O | X |   | X | O | X |   | X | O | X |
+---+---+---+   +---+---+---+   +---+---+---+
| A | O | B |   | X | O | O |   |   | O | X |
+---+---+---+   +---+---+---+   +---+---+---+
| O | X | X |   | O | X | X |   | O | X | X |
+---+---+---+   +---+---+---+   +---+---+---+

Fig.8 は X があと一手で勝てる盤面で、A に置けば最終的に Fig.9-A に、B に置けば Fig.9-B の盤面になります。Fig.9-A は引き分けのためスコア 0 で Fig.9-B は X の勝利でスコア 1 です。

すると Fig.9-A と Fig.9-B は Fig.8 の盤面から派生しているので、Fig.8 のスコアは Fig.9-A と Fig.9-B に依存していることになります。なので Fig.8 から最良の手を打つために派生した盤面のスコアの中から最良の値をとって、1 とします。

同じように Fig.8 の前の盤面、その前の盤面…と最後の手から遡って最初の手までスコアを計算することで、各盤面で一番有利な選択肢を取らせることができ、絶対に勝てる(負けない)手が打てそうです。さいわい三目並べはゲームが長く続いても 9 手で終わるので、すべての盤面を列挙することができ、乱数に依存しない決定的な方策を打ち出せます。それではこれからコードを書いていきましょう。

実装する

Python を使って実装していきます。ここではオブジェクト指向とドメイン駆動的なスタイルを取り入れてそれぞれの箇所で注目したい事柄に集中できるようなコードにしています。

Domain Model: 印

ドメインモデルとはある概念や領域において着目すべきデータやシステムのことです。今回は三目並べなので少なくとも O X といった印と 3x3 のマスからなる盤面が必要です。まずはこのふたつをコードに落とし込んでみましょう。

三目並べの印は O と X の二種類ですが、盤面には O も X も置かれていないことがあるので、印がないことを表す印 N を導入します。すると Enum を使って次のようなコードが書けます。

import enum

class Mark(enum.Enum):
    O = enum.auto()
    N = enum.auto()
    X = enum.auto()

また、O と X にゲーム盤上での表示テキスト glyph と勝利したときのスコア score プロパティを作ります。Python の列挙体はクラスなのでメソッドを定義するだけです。

class Mark(enum.Enum):
    O = enum.auto()
    N = enum.auto()
    X = enum.auto()

    @property
    def glyph(self) -> str:
        return {self.O: 'O', self.N: ' ', self.X: 'X'}[self]

    @property
    def score(self) -> int:
        return {self.O: -1, self.N: 0, self.X: 1}[self]

Mark.X の値を出力してみましょう。それぞれコメントに書かれたとおりの表示がされるはずです。

print(Mark.X)           # Mark.X
print(Mark.X.glyph)     # X
print(Mark.X.score)     # 1

Domain Model: 盤面

次に盤面を考えます。盤面には 3x3 のあわせて 9 マス分の印を置ける場所があります。まずはその入れ物を作ります。

from typing import *

class Board:
    def __init__(self):
        # なにも印が置かれていない盤面
        self.marks = [Mark.N for _ in range(9)]

marks は 9 要素の Marks インスタンスからなる配列で、その添字と盤面は Fig.10 のような対応関係になっています。

Fig.10
+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

そしてゲームの終了条件を追加します。終了条件は次のふたつです。

  1. 印を置けるマスがなくなった
  2. X または O が勝利した

ゲーム終了を判定するには、印を置けるマスを取得するプロパティ empty_slots と盤面のスコアを取得するプロパティ score があれば良さそうです。なのでこのふたつを定義し、さらにゲーム終了か判定する gameover プロパティも追加します。

class Board:
    :
    @property
    def empty_slots(self) -> Set[int]:
        return {index for index, mark in enumerate(self.marks) if mark == Mark.N}
    
    @property
    def score(self) -> int:
        if self.marks[0] == self.marks[1] == self.marks[2]:
            return self.marks[0].score
        if self.marks[3] == self.marks[4] == self.marks[5]:
            return self.marks[3].score
        if self.marks[6] == self.marks[7] == self.marks[8]:
            return self.marks[6].score
        if self.marks[0] == self.marks[3] == self.marks[6]:
            return self.marks[0].score
        if self.marks[1] == self.marks[4] == self.marks[7]:
            return self.marks[1].score
        if self.marks[2] == self.marks[5] == self.marks[8]:
            return self.marks[2].score
        if self.marks[0] == self.marks[4] == self.marks[8]:
            return self.marks[0].score
        if self.marks[2] == self.marks[4] == self.marks[6]:
            return self.marks[2].score
        return Mark.N.score
    
    @property
    def gameover(self) -> bool:
        return not self.empty_slots or self.score != Mark.N.score

便利のために現在の盤面を表示する print() メソッドも用意しましょう。

    def print(self) -> None:
        print('+---+---+---+')
        print('| {} | {} | {} |'.format(*[marks.glyph for marks in self.marks[0:3]]))
        print('+---+---+---+')
        print('| {} | {} | {} |'.format(*[marks.glyph for marks in self.marks[3:6]]))
        print('+---+---+---+')
        print('| {} | {} | {} |'.format(*[marks.glyph for marks in self.marks[6:9]]))
        print('+---+---+---+')

Board の動きを確認してみます。

board = Board()
board.marks[2] = Mark.X
board.print()

+---+---+---+
|   |   | X |
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

盤面の基本的な動作はこれで良さそうです。

Domain Model: 盤面の木構造

すべての盤面を列挙するには、どの盤面でどこに印を置いてどの盤面になったかの情報を組み立てる必要があります。Fig.11 は最初の盤面で、Fig.12-A は位置 4 に X を置いた結果の盤面、Fig.12-B は 2 に置いた結果です。

Fig.11          Fig.12-A        Fig.12-B
+---+---+---+   +---+---+---+   +---+---+---+
|   |   |   |   |   |   |   |   |   |   | X |
+---+---+---+   +---+---+---+   +---+---+---+
|   |   |   |   |   | X |   |   |   |   |   |
+---+---+---+   +---+---+---+   +---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+   +---+---+---+   +---+---+---+

これを表現するために、最初の盤面から次の盤面、そしてさらに次の盤面へとアクセスできる構造を実現する BoardNode を新しく作ります。

class BoardNode:
    def __init__(self, board: Board, turn: Mark):
        self.board = board      # 現在の盤面    
        self.turn = turn        # どっちの手番か？
        self.children = {}      # keyに印を置いた位置、valueに結果のBoardNode
        self.score = None       # この盤面のスコア

Service: すべての盤面の列挙

これでドメインモデルの準備は整いました。最初のなにも置かれていない盤面から開始して、すべての盤面の組み合わせを探索する時間がきました。基本的な方策は次のとおりです。

  • 空の盤面を用意する
  • ゲームが終了していなければ (*):
    • 盤面の置けるマスに対して:
      • それぞれ置いた結果の盤面を作成し、盤面の子として追加する
      • 追加した子に対して * を行う

実装としてはこれだけです。見慣れない deque (double-ended queue; 両端キュー)を使っていますが、これは先頭・末尾要素の追加・削除が O(1) (定数時間) で済む list の仲間で、今回の用途に適しています。

import collections

class CreateBoardTreeService:
    def handle(self) -> BoardNode:
        # 最初の盤面のノードをXの手番として作成する
        root = BoardNode(Board(), Mark.X)
        # キューに入れる
        queue = collections.deque([root])
        # キューに探索すべき要素がある限り
        while queue:
            # キューの先頭の要素を取得する
            node = queue.popleft()
            if not node.board.gameover:
                # 空きマスに対して
                for index in node.board.empty_slots:
                    # 現在の盤面をコピーして印を置く
                    next_board = node.board.copy()
                    next_board.marks[index] = node.turn
                    # 新しいノードを作成して手番を交代する
                    next_node = BoardNode(next_board, node.turn.flip())
                    # 現在のノードの子として追加する
                    node.children[index] = next_node
                    # キューの最後に新しいノードを追加する
                    queue.append(next_node)
        return root

そういえば Board.copy() と Mark.flip() を定義していませんでした。このふたつは次のような定義になります。前にも書いたように、そのとき着目すべき事柄に集中するために、処理に名前をつけて単純化するのは大事なことです。

class Board:
    :
    def copy(self) -> 'Board':
        board = self.__class__()
        board.marks = self.marks.copy()
        return board

class Mark:
    :
    def flip(self) -> 'Mark':
        return {self.O: self.X, self.N: self.N, self.X: self.O}[self]

これで全盤面を列挙できました。試してみましょう。

root = CreateBoardTreeService().handle()
root.children[0].board.print()
root.children[0].children[4].board.print()

+---+---+---+
| X |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+
+---+---+---+
| X |   |   |
+---+---+---+
|   | O |   |
+---+---+---+
|   |   |   |
+---+---+---+

良さそうですね。

Service: すべての盤面のスコアを求める

盤面が列挙できたので、それぞれの盤面のスコアを求めます。先ほどはキューによる幅優先探索が良いと言っておきながら、今度は簡単のために深さ優先探索で使われる再帰によってスコアを計算します。BoardNode.calc_score() を定義し、CreateBoardTreeService.handle() の最後にスコアを求めるコードを追加しました。

class CreateBoardTreeService:
    def handle(self) -> BoardNode:
        root = BoardNode(Board(), Mark.X)
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            if not node.board.gameover:
                for index in node.board.empty_slots:
                    next_board = node.board.copy()
                    next_board.marks[index] = node.turn
                    next_node = BoardNode(next_board, node.turn.flip())
                    node.children[index] = next_node
                    queue.append(next_node)
        # 空の盤面のスコアを求める
        root.calc_score()
        return root

class BoardNode:
    :
    def calc_score(self) -> int:
        if self.score is None:
            # スコアがまだ算出されていないなら子のスコアから算出する
            if self.board.gameover:
                # ただしゲームが終了していたらそのときのスコアとする
                self.score = self.board.score
            else:
                # まだゲームが継続している
                if self.turn == Mark.X:
                    # Xにとって最良のスコアを求める
                    self.score = max(child.calc_score() for child in self.children.values())
                if self.turn == Mark.O:
                    # Oにとって最良のスコアを求める
                    self.score = min(child.calc_score() for child in self.children.values())
        return self.score

calc_score() は現在の盤面のスコアを決定するために再帰的に子のスコアを要求しにいきます。
最終的にはゲーム終了の盤面に行きつき、そのときのスコア -1, 0, 1 が手に入ります。X の場合は子の盤面の中で最大のスコア、O の場合は最小のスコアを採用します。

すると自動的に前の盤面のスコアも定まり、それを繰り返すことで、結果的にすべての盤面のスコアが手に入ることになります。そして X であれば一番高いスコアの盤面になるように、O であれば一番低いスコアの盤面になるような手を打てば絶対に勝てる(負けない)ようになります。

Fig.13          Fig.14-A        Fig.14-B
+---+---+---+   +---+---+---+   +---+---+---+
| X |   |   |   | X |   |   |   | X | * |   |
+---+---+---+   +---+---+---+   +---+---+---+
|   | O |   |   |   | O |   |   | * | O | * |
+---+---+---+   +---+---+---+   +---+---+---+
|   |   | X |   | O |   | X |   |   | * | X |
+---+---+---+   +---+---+---+   +---+---+---+

View/Controller: 対戦用インタフェースを作成する

最後に実際に絶対負けない三目並べ AI と戦うための対話型インタフェースを作りましょう。今回はプレイヤーが先攻の場合を考えます。すると次のようなアルゴリズムが考えられるでしょう。

  1. スコア計算済みのルートノードを取得する
  2. 手番を X (プレイヤー)にする
  3. 繰り返す:
    1. 盤面を表示する
    2. X の手番なら:
      1. 0 から 8 の数字のうちから手を選択する
    3. O の手番なら:
      1. スコアが一番小さくなる手を選択する
    4. 手を使って次の盤面を取得する
    5. ゲームが終了した:
      1. X が勝利なら:「X の勝利」と表示する
      2. O が勝利なら:「O の勝利」と表示する
      3. 引き分けなら:「引き分け」と表示する
      4. ゲームを終了する
    6. 手番を交代する

「スコアが一番小さくなる手を選択する」の実装をしていませんでした。スコアが一番小さい手の一覧を取得する argmin() を BoardNode に追加します。

class BoardNode:
    :
    def argmin(self) -> Sequence[int]:
        score = min(child.calc_score() for child in self.children.values())
        return [index for index, child in self.children.items() if score == child.calc_score()]

複数の手で同じスコアを持つ場合があるので、その場合はランダムで決定します。

import random

class GameController:
    def __init__(self):
        self.root = CreateBoardTreeService().handle()

    def handle(self) -> None:
        node = self.root
        turn = Mark.X
        while True:
            # 現在の盤面を表示する
            node.board.print()
            if turn == Mark.X:
                # プレイヤーの手番
                index = self.get_index()
            else:
                # AIの手番
                index = random.choice(node.argmin())
            # 選択した盤面にする
            node = node.children[index]
            # ゲームが終了したか判定
            if node.board.gameover:
                node.board.print()
                if node.board.score != Mark.N.score:
                    print('{} Win'.format(turn.glyph))
                else:
                    print('draw')
                break
            # 手番を交代する
            turn = turn.flip()
    
    def get_index(self) -> int:
        while True:
            try:
                return int(input('> '))
                break
            except ValueError:
                pass

GameController().handle()

これで三目並べ完成です！何回かプレイしてみると絶対に勝てないことがわかりますし、プレイヤーが愚かな手を指すと負けてしまうこともわかります。

おまけ: 永続化する

CreateBoardTreeService を使えば不敗の三目並べモデルを作って戦わせることができるようになりました。しかし全探索をしている都合上、ゲームをするたびに毎回数秒待たされることになる上に、毎回計算結果は同じです。そこで、最低限必要なデータだけを抽出し、JSON ファイルなどに書き出して、次からはそれを読み込んで使うといったことが想定できます。

よくよく考えれば木構造を作ったのはスコアを算出するためであって、実際には最良の手だけがわかっていればよく、木構造からどの手が最良かという値と、先攻が O と X どちらであるかだけ分かれば十分なはずです。

Fig.6
+---+---+---+
| X | X | X |
+---+---+---+
|   | O |   |
+---+---+---+
| O |   | X |
+---+---+---+

Fig.6 を再掲します。このゲームは X が先攻で、進むべき手は 0, 8, 4, 2, 6, 1 です。この情報を構造化した JSON として定義することで、毎回無駄な計算を省くことができます。実装は特に記載しませんが、興味があれば挑戦してみてください。

Discussion