Pythonで〇×ゲームのAIを一から作成する その50 局面に対する評価値の設定と計算

目次と前回の記事

これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

これまでに作成した AI

これまでに作成した AI の アルゴリズム は以下の通りです。

関数名	アルゴリズム
ai1 ai1s	左上から順 に 空いているマス を探し、最初に見つかったマス に 着手 する
ai2 ai2s	ランダム なマスに 着手 する
ai3 ai3s	真ん中 のマスに 優先的 に 着手 する 既に 埋まっていた場合 は ランダム なマスに 着手 する
ai4 ai4s	真ん中、隅 のマスの 順 で 優先的 に 着手 する 既に 埋まっていた場合 は ランダム なマスに 着手 する
ai5	勝てる場合 に 勝つ そうでない場合は ランダム なマスに 着手 する
ai6	勝てる場合 に 勝つ そうでない場合は 相手の勝利 を 阻止 する そうでない場合は ランダム なマスに 着手 する
ai7	真ん中 のマスに 優先的 に 着手 する そうでない場合は 勝てる場合 に 勝つ そうでない場合は 相手の勝利 を 阻止 する そうでない場合は ランダム なマスに 着手 する

基準となる ai2 との 対戦結果（単位は %）は以下の通りです。太字 は ai2 VS ai2 よりも 成績が良い 数値を表します。欠陥 の列は、アルゴリズム に 欠陥 があるため、ai2 との 対戦成績 が 良くても強い とは 限らない ことを表します。欠陥の詳細については、関数名のリンク先の説明を見て下さい。

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分	欠陥
ai1	78.1	17.5	4.4	44.7	51.6	3.8	61.4	34.5	4.1	あり
ai2	58.7	28.8	12.6	29.1	58.6	12.3	43.9	43.7	12.5
ai3	69.3	19.2	11.5	38.9	47.6	13.5	54.1	33.4	12.5
ai4	83.0	9.5	7.4	57.2	33.0	9.7	70.1	21.3	8.6	あり
ai5	81.2	12.3	6.5	51.8	39.8	8.4	66.5	26.0	7.4
ai6	88.9	2.2	8.9	70.3	6.2	23.5	79.6	4.2	16.2
ai7	95.8	0.2	4.0	82.3	2.4	15.3	89.0	1.3	9.7

局面に対する評価

ルール 1 ~ 4 までは、真ん中のマスや、隅のマスなど、行った 着手の種類 に対して 評価値 を 計算 しましたが、いずれも 着手した後 の 局面 の 状態 を全く 考慮に入れていません でした。少し考えればわかると思いますが、このような 局面 を 考慮に入れない ルールで、本当に強い AI を 作る ことは 不可能 です。今回の記事では、ルール 5 ~ 7 の、合法手を 着手した後 の 局面 に対する 評価値 の 計算 の方法について説明します。

評価値を利用した ルール 5 で着手を行う AI の定義

下記の ルール 5 を、評価値を利用 した アルゴリズム で 実装 するために、どのような評価値 を 設定 すれば良いかについて少し考えてみて下さい。

• 勝てる場合 に 勝つ
• そうでない場合は ランダム なマスに 着手 する

評価値の設定

ルール 5 では、「自分が 勝利した 局面」の 評価値 を、「自分が 勝利していない 局面」の 評価値より も 高く設定 する必要があります。また、勝利 する 合法手 が 存在しない 場合は ランダム なマスに 着手 するので、それら の 評価値 は すべて同じ値 を 設定 する 必要 があります。なお、勘違いしやすい 点ですが、「自分が 勝利していない 局面」は、「自分 が 敗北 した局面」と 同じ意味ではない 点に注意して下さい。具体的には、「自分が 敗北 した 局面」だけでなく、「ゲームが 続行中」と「引き分け」の 局面 を 含みます。

そこで、本記事では、下記の表 のように 評価値 を 設定 することにします。

局面の状況	評価値
自分 が 勝利 している	1
自分 が 勝利していない	0

評価値を利用したアルゴリズムの実装方法のおさらい

まず、評価値を利用 した アルゴリズム の 実装方法 の おさらい をします。

評価値を利用 した アルゴリズム では、以下 のような 処理 を行います。

1. 現在 の、自分の手番 の 局面 に対して、合法手 を 着手 した 局面 を すべて計算 する
2. それぞれの 合法手 を 着手 した 局面 に対して 評価値を計算 する
3. 最も評価値 が 高い 局面になる 合法手 の中から ランダム に 選択 する

手順 1 と 3 は、ai_by_score で行うので、実際に 記述 する 必要 があるのは、手順 2 の処理を行う 評価関数 の 実装 です。評価関数 の 仮引数 には、合法手 を 着手 した 局面 を表す Marubatsu クラス の インスタンス が 代入 され、それを使って 評価値 を 計算 します。

その 仮引数 の 名前 は どのような名前 をつけても かまいません が、本記事では mb という 名前を付ける ことにし、以後は、評価関数 の 説明 の中で、評価値 を 計算 する 局面 を表す Marubatsu クラス の インスタンス を mb と記述することにします。

自分が勝利したかどうかの判定

評価関数 で、mb の 局面 で 自分が勝利しているか どうかは、status 属性 が、自分のマーク を 表す値であるか どうかで 判定 することが できます が、mb は 相手の手番 の 局面 なので、手番 を表す mb.turn と mb.status を そのまま比較 しても、自分 が 勝利しているか どうかを 判定 することは できません。そこで、以前の記事で定義した ai5 では、下記のプログラムの 7 行目 のように、mb の status 属性 と、着手前 の 自分の手番 の 局面 を表す mb_orig の、turn 属性 が 等しいか どうかで、その 判定 を 行っています。

1  def ai5(mb_orig):
2      legal_moves = mb_orig.calc_legal_moves()
3      for move in legal_moves:
4          mb = deepcopy(mb_orig)
5          x, y = move
6          mb.move(x, y)
7          if mb.status == mb_orig.turn:
8              return move
9      return choice(legal_moves)

しかし、評価値 を 計算 する 評価関数 の 仮引数 には、合法手 を 着手後 の 局面 を表す mb しか存在しない ので、上記のように 着手前 の 局面 の 手番 と 比較 することは できません。本記事では 3 種類の方法を紹介しますが、評価関数の中 で、mb の 情報のみ を使って 自分 が 勝利しているか どうかを 判定する方法 について少し考えてみて下さい。

本記事では採用しませんが、評価関数 に、合法手 を 着手する前 の局面と、着手した後 の局面を 代入 する 2 の仮引数 を 設定 するという方法もあります。その場合は、ai_by_score の中で 評価関数 を 呼び出す 処理を 下記 のように 記述 します。

def ai_by_score(mb_orig, eval_func, debug=False, rand=True):
略
        score = eval_func(mb_orig, mb)
略

修正箇所

def ai_by_score(mb_orig, eval_func, debug=False, rand=True):
略
-       score = eval_func(mmb)
+       score = eval_func(mb_orig, mb)
略

そして、評価関数 を 下記 のように 定義 します。

def eval_func(mb_orig, mb):
    評価関数の処理を記述する

修正箇所

-def eval_func(mb):
+def eval_func(mb_orig, mb):
    評価関数の処理を記述する

本記事でこの方法を 採用しない理由 は、関数の 仮引数の数 が 多くなる と関数が 扱いづらく、分かりづらく なる点と、評価関数 の中で、手番以外 の 着手前 の局面の 情報 を使って 評価値 を 計算しない からです。ただし、上記の方法を利用してもプログラムは 正しく動作 するので、こちらを採用してもかまいません。

判定方法その 1（自分の手番を計算する方法）

〇×ゲーム は、自分の手番 と 相手の手番 が 交互 に 回ってくる ゲームなので、自分の手番 は、相手の手番 を表す mb.turn から 下記の式 で計算することができます。なお、この処理 は、move メソッド 内で、着手後 に 手番を入れ替える 処理と 同じ です。

Marubastu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE

従って、ルール 5 で 着手 を行う ai5s は、下記のプログラムで実装できます。

• 6 行目：相手の手番 を表す mb.turn から、自分の手番 を計算し、my_turn に 代入 する
• 7、8 行目：合法手を 着手後 の 局面の状態 を表す mb.status が、自分の手番 を表す my_turn と 等しい 場合は 自分が勝利 しているので、評価値 として 1 を 返す
• 9、10 行目：そうでなければ、評価値 として 0 を 返す

 1  from marubatsu import Marubatsu
 2  from ai import ai_by_score
 3
 4  def ai5s(mb, debug=False):
 5      def eval_func(mb):
 6          my_turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
 7          if mb.status == my_turn:
 8              return 1
 9          else:
10              return 0
11
12      return ai_by_score(mb, eval_func, debug=debug)

行番号のないプログラム

from marubatsu import Marubatsu
from ai import ai_by_score

def ai5s(mb, debug=False):
    def eval_func(mb):
        my_turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
        if mb.status == my_turn:
            return 1
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

動作の確認

ai5s が 正しく動作 するかどうかを 確認 するために、ai5 と 対戦 を行います。実行結果 から、ai5s を 正しく実装 できていることが 確認 できました。

from ai import ai_match, ai5, ai6, ai7

ai_match(ai=[ai5s, ai5])

実行結果（実行結果はランダムなので下記とは異なる場合があります）

ai5s VS ai5
count     win    lose    draw
o        6815    2770     415
x        2699    6846     455
total    9514    9616     870

ratio     win    lose    draw
o       68.2%   27.7%    4.2%
x       27.0%   68.5%    4.5%
total   47.6%   48.1%    4.3%

判定方法その 2（自分の手番を利用しない方法）

〇×ゲーム には、以下 のような 性質 があります。

• 〇 のプレイヤー が 勝利 するのは、〇 のプレイヤー が 着手 を行った 場合だけ である
• × のプレイヤー が 勝利 するのは、× のプレイヤー が 着手 を行った 場合だけ である

上記を 言い換える と、以下 のようになります。

• 〇 のプレイヤー が 着手 することで、× のプレイヤー が 勝利 することは 無い
• × のプレイヤー が 着手 することで、〇 のプレイヤー が 勝利 することは 無い
• 従って、自分 が 着手 することで、相手 が 勝利 することは 無い

上記 から、現在の局面 の 手番 と、合法手を 着手後の局面 の 状態 と mb.status 属性 の 値 の すべて の 組み合わせ を 表 にすると、下記のようになります。

現在の局面の手番	着手後の状態	mb.status の値
〇	〇 の勝ち	Marubatsu.CIRCLE
〇	引き分け	Marubatsu.DRAW
〇	決着がついていない	Marubatsu.PLAYING
×	× の勝ち	Marubatsu.CROSS
×	引き分け	Marubatsu.DRAW
×	決着がついていない	Marubatsu.PLAYING

上記の表で、現在の局面 の 手番 が 〇 の 場合 に、mb.status が Marubatsu.CROSS に なること が 無い 点に 注目 して下さい。この 性質 から、現在の局面 の 手番 が 〇 の場合に、着手後の局面 で 〇 が勝利 することを、下記 の 条件式 で 判定 することができます。

mb.status == Marubatsu.CIRCLE or mb.status == Marubatsu.CROSS

条件式 に、余計 な mb.status == Marubatsu.CROSS が 記述 されているのが変だと思うかもしれませんが、現在の局面 の 手番 が 〇 の 場合 に mb.status の 値 が Marubatsu.CROSS に なること は 無い いので、mb.status == Marubatsu.CROSS の 値 は 常に False になります。従って、現在の局面 の 手番 が 〇 の 場合 は、上記の式 は 下記の式 の 計算 を行います。

mb.status == Marubastu.CIRCLE or False

この 条件式 の 計算結果 は、下記 の 条件式 と 同じ値 になるので、先程の条件式 で、現在の局面 の 手番 が 〇 の 場合 に 正しい判定 を 行うことができる ことが 確認 できました。

mb.status == Marubastu.CIRCLE

具体的な説明は省略しますが、同様の理由 で、現在の局面 の 手番 が × の場合も、下記 の 同じ条件式 で × が勝利 することを 判定 することが できます。

mb.status == Marubatsu.CIRCLE or mb.status == Marubatsu.CROSS

従って、ai5s は下記のプログラムのように記述できます。

• 3 行目：上記の条件式 で、自分 が 勝利 していることを 判定 するように 修正 する

1  def ai5s(mb, debug=False):
2      def eval_func(mb):
3          if mb.status == Marubatsu.CIRCLE or mb.status == Marubatsu.CROSS:
4              return 1
5          else:
6              return 0
7
8      return ai_by_score(mb, eval_func, debug=debug)

行番号のないプログラム

def ai5s(mb, debug=False):
    def eval_func(mb):
        if mb.status == Marubatsu.CIRCLE or mb.status == Marubatsu.CROSS:
            return 1
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

修正箇所

def ai5s(mb, debug=False):
    def eval_func(mb):
-       my_turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
-       if mb.status == my_turn:
+       if mb.status == Marubatsu.CIRCLE or mb.status == Marubatsu.CROSS:
            return 1
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

動作の確認

ai5s が 正しく動作 するかどうかを 確認 するために、ai5 と 対戦 を行います。実行結果 から、ai5s を 正しく実装 できていることが 確認 できました。

from ai import ai_match, ai5

ai_match(ai=[ai5s, ai5])

実行結果（実行結果はランダムなので下記とは異なる場合があります）

ai5s VS ai5
count     win    lose    draw
o        6841    2736     423
x        2677    6879     444
total    9518    9615     867

ratio     win    lose    draw
o       68.4%   27.4%    4.2%
x       26.8%   68.8%    4.4%
total   47.6%   48.1%    4.3%

判定方法その 3（直前の手番を属性に代入して取っておく）

先程紹介した、判定方法その 1 と その 2 には以下のような 欠点 があります。

判定方法その 1 の欠点

判定方法 その 1 の、評価関数の中 で 自分の手番 を 計算 する 方法 は、自分の手番 の 情報 を使って 評価値を計算 する 評価関数 を定義する際に、下記 のプログラムを 毎回記述 する 必要 がある点が 面倒 です。また、実際 に ルール 6、7 の AI や、その後で 実装する予定 の AI でも、評価関数の中 で 自分の手番 の 情報 が 必要 になります。

my_turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE

判定方法その 2 の欠点

判定方法 その 2 の 方法 には、確かに 自分の手番 の 情報 を 計算 する 必要がない という 利点 がありますが、自分が勝利 することを 判定 する 条件式 を 求める までの 考え方（論理、ロジック）が 複雑 なため、以下のような欠点があります。

• 慣れないと 条件式 を 求める のが 大変
• プログラムの意味 が 分かりづらくなる
• 勘違いなど で、間違った論理 で 条件式 を 記述 することによる バグ が 発生しやすい

直前の手番を属性に代入して取っておく方法

自分が勝利 したことを 判定 するために 必要 な、自分の手番 の 情報 は、mb の 直前の局面 の 手番 の 情報 から 得る ことができますが、その 情報 は、直前の局面 の turn 属性 に 代入されています。従って、その情報 を、move メソッド で 手番 を 入れ替える処理 を 行う前 に、何らかの属性 に 代入 して 取っておく ことで、判定方法 その 1 のように、改めて その情報を 計算 する 必要 が なくなります。そこで、その 属性の名前 を、直前（last）の 手番（turn）の情報を 代入 することから、last_turn と 名付ける ことにします。

実は、この方法 は、move メソッド の中で、直前の着手 の 情報 を last_move という 属性 に 代入する のと 同じ考え方 なので、last_move と 同様の方法 で 実装 できます。具体的には、last_move の処理は、Marubatsu クラス の restart メソッド と、move メソッド で行われているので、それら の メソッド に last_turn の 処理を記述 します。

restart メソッドの修正

last_move 属性の 初期化処理 は、ゲームの初期化処理 を行う、下記の restart メソッドの 6 行目 で行われます。そこで、その次の 7 行目 に、last_turn 属性の 初期化処理 を 記述 します。ゲーム開始時 の 局面 より 前の局面 は 存在しない ので、None で 初期化 します。

1  def restart(self):
2      self.initialize_board()
3      self.turn = Marubatsu.CIRCLE     
4      self.move_count = 0
5      self.status = Marubatsu.PLAYING
6      self.last_move = -1, -1 
7      self.last_turn = None
8
9  Marubatsu.restart = restart

行番号のないプログラム

def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    self.status = Marubatsu.PLAYING
    self.last_move = -1, -1 
    self.last_turn = None

Marubatsu.restart = restart

修正箇所

def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    self.status = Marubatsu.PLAYING
    self.last_move = -1, -1 
+   self.last_turn = None

Marubatsu.restart = restart

move メソッドの修正

last_turn 属性の 更新 処理は、下記のプログラムのように、着手 を行う move メソッド の 3 行目 で、着手前 の 手番 を表す self.turn を 代入 します。この処理は、4 行目の、手番 を 次の手番 に 入れ替える 処理を 行う前 で行う 必要 がある点に 注意 して下さい。

1  def move(self, x, y):
2      if self.place_mark(x, y, self.turn):
3          self.last_turn = self.turn
4          self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
5          self.move_count += 1
6          self.status = self.judge()
7          self.last_move = x, y
8
9  Marubatsu.move = move

行番号のないプログラム

def move(self, x, y):
    if self.place_mark(x, y, self.turn):
        self.last_turn = self.turn
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        self.status = self.judge()
        self.last_move = x, y

Marubatsu.move = move

修正箇所

def move(self, x, y):
    if self.place_mark(x, y, self.turn):
+       self.last_turn = self.turn
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        self.status = self.judge()
        self.last_move = x, y

Marubatsu.move = move

ai5s の実装

上記の修正を行うことで、ai5s では、下記のプログラムの 3 行目 のように、last_turn 属性 を使って 自分が勝利 したことを 判定 できるようになります。

1  def ai5s(mb, debug=False):
2      def eval_func(mb):
3          if mb.status == mb.last_turn:
4              return 1
5          else:
6              return 0
7
8      return ai_by_score(mb, eval_func, debug=debug)

行番号のないプログラム

def ai5s(mb, debug=False):
    def eval_func(mb):
        if mb.status == mb.last_turn:
            return 1
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

修正箇所

def ai5s(mb, debug=False):
    def eval_func(mb):
-       if mb.status == Marubatsu.CIRCLE or mb.status == Marubatsu.CROSS:
+       if mb.status == mb.last_turn:
            return 1
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

動作の確認

ai5s が 正しく動作 するかどうかを 確認 するために、ai5 と 対戦 を行います。実行結果 から、ai5s を 正しく実装 できていることが 確認 できました。

ai_match(ai=[ai5s, ai5])

実行結果（実行結果はランダムなので下記とは異なる場合があります）

ai5s VS ai5
count     win    lose    draw
o        6885    2673     442
x        2698    6842     460
total    9583    9515     902

ratio     win    lose    draw
o       68.8%   26.7%    4.4%
x       27.0%   68.4%    4.6%
total   47.9%   47.6%    4.5%

ai5 と ai5s の計算時間の比較

前回の記事 で、「評価値を利用 した アルゴリズム」は、「それぞれの条件 を 順番に判定 し、最初 にみつかった 条件を満たす着手 を 選択 する」場合と 比較 して 処理 に 時間がかかる場合 があるという説明を行いました。

そこで、ai5 と ai5s の 処理時間 を 比較 することにします。

下記の、ai5 どうしの 対戦 の 処理時間 は、筆者のパソコンでは 約 28.5 秒 でした。

ai_match(ai=[ai5, ai5])

下記の、ai5s どうしの 対戦 の 処理時間 は、筆者のパソコンでは 約 30.7 秒 でした。

ai_match(ai=[ai5s, ai5s])

前回の記事では、ai1 ~ ai4 と、対応 する ai1s ~ ai4s の 処理時間 は 約 10 倍以上 の 差 がありましたが、ai5 と ai5s の 処理時間 の 差 は 数 % に過ぎません。その 理由 は、ai1 ~ ai4 が、Marubatsu クラス の インスタンス の 深いコピー を 作成 するという、時間がかかる処理 を 行っていない のに対して、ai5 は その処理 を 行っている からです。

ai5 のほうが、ai5s より も若干 処理時間 が 短い のは、ai5 は、自分が勝利す する 合法手 が 見つかった時点 は、その合法手 を 採用 して 残りの処理 を 行わない のに対して、ai5s は必ず すべて の 合法手 の 着手 を 行う からです。

ai5 と ai5s が選択する着手の違い

ai5 と ai5s は、対戦結果 からわかるように、どちらも 全く同じ強さ を持ちますが、状況によって、異なる方法 で 着手 を 選択 する 場合 が あります。具体的には、自分が勝利 できる 着手 が 複数存在 する 場合 に、それぞれの AI は、下記 の方法で 着手 を 選択 します。なお、それ以外 の 場合 は、どちらの AI も 同じ方法 で 着手 を 選択 します。

• ai5 は、最初 に 見つかった 、自分が勝利できる合法手を 選択 する
• ai5s は、自分が勝利できる合法手の中から、ランダム に 選択 する

ai5 の 処理速度 が ai5s より 速い理由 は、上記の 処理の違い によるものです。

下記は、上記の性質 を 確認 するプログラムで、〇 が勝利 できる 合法手 が 3 つ存在 する 局面 で、ai5 と ai5s で 10 回 ずつ 着手を選択 します。実行結果 からわかるように、ai5 は 常に同じ着手 を 選択 しますが、ai5s は 3 つ の 合法手 から ランダムに選択 します。

mb = Marubatsu()

mb.move(1, 1)
mb.move(1, 0)
mb.move(0, 0)
mb.move(2, 0)
mb.move(0, 1)
mb.move(1, 2)
print(mb)

print("ai5")
for i in range(10):
    print(ai5(mb))
    
print("ai5s")
for i in range(10):
    print(ai5s(mb))

実行結果（実行結果はランダムなので下記とは異なる場合があります）

Turn o
oxx
oo.
.X.

ai5
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
ai5s
(2, 2)
(2, 1)
(2, 1)
(0, 2)
(2, 2)
(2, 1)
(2, 2)
(2, 2)
(2, 1)
(2, 2)

処理時間 が 短くなる ことは ありません が、ai5s の 最後の行 の ai_by_score の 実引数 に、下記のように rand=False を 記述 することで、ai5 と 同様 に、最初にみつかった 自分が勝利できる 合法手 を 選択 する AI を定義 することが できます。

def ai5s(mb, debug=False):
略
    return ai_by_score(mb, eval_func, debug=debug, rand=False)

修正箇所

def ai5s(mb, debug=False):
略
-   return ai_by_score(mb, eval_func, debug=debug)
+   return ai_by_score(mb, eval_func, debug=debug, rand=False)

ai5 と ai5s のどちらを選択すべきか

ai5 と ai5s の どちらを選択すべきか については、それぞれ の AI の 利点 と 欠点 を見て 総合的に判断 する必要があります。例えば、処理速度 の 速さ が 非常に重要 な場合は、ai5 を 選択すべき ですが、実際 には先程示したように、ai5 と ai5s の 処理速度 の 差 は 数 % に過ぎないので、どちらを選択してもそれほど 処理速度 に 大きな差 は 生じません。

実装のしやすさ の観点でみると、ai5s のほうが 実装しやすい でしょう。

ai5 と ai5s は、どちらも AI の強さ という 観点 でみると、同じ強さ を持ちますが、人間と AI が 対戦 する場合は、結果が同じ である としても、ランダム性 のある 着手 を行う AI のほうが 好まれる のではないかと思います。同じ状況 で、必ず 同じ着手 しか行わない AI は、対戦していて つまらない と思いませんか？

上記以外にも、様々な観点 で 比較 することができます。状況 によって どのような性質 が 望ましいか は 変わる ので、結論 は 人それぞれ でしょう。どちらを選択 するかについては、自分で考えて下さい。

評価値を利用した ルール 6 で着手を行う AI の定義

ルール 6 は、ルール 5 に、相手の勝利を阻止 するという 条件 を 加えた ものです。下記の ルール 6 の 評価値 を どのように設定 すればよいかについて少し考えてみて下さい。

• 勝てる場合 に 勝つ
• そうでない場合は 相手の勝利 を 阻止 する
• そうでない場合は ランダム なマスに 着手 する

ルール 6 では、「自分が勝利 した局面」、「相手の勝利を阻止 した局面」、「それ以外 の局面」の 順 で 評価値 を 高く設定 する必要があります。そこで、下記の表 のように 評価値 を 設定 することにします。

局面の状況	評価値
自分が勝利している	2
相手の勝利を阻止した	1
それ以外の場合	0

上記のうち、自分が勝利 している 局面 に対して、2 の 評価値 を 設定 する 処理 は、ai5s と 同じ方法 で 記述 できるので、ai6s は、下記のようなプログラムで記述できます。

def ai6s(mb, debug=False):
    def eval_func(mb):
        if mb.status == mb.last_turn:
            return 2
        elif 相手の勝利を阻止したことを表す条件式:
            return 1
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

修正箇所

-def ai5s(mb, debug=False):
+def ai6s(mb, debug=False):
    def eval_func(mb):
        if mb.status == mb.last_turn:
-           return 1
+           return 2
+       elif 相手の勝利を阻止したことを表す条件式:
+           return 1
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

相手の勝利を阻止する着手を選択する別のアルゴリズム

ai6 では、最終的に下記のような、正攻法ではない、すこし ひねった考え方 で 相手の勝利を阻止 する 着手 を 選択 しました。忘れた方は、以前の記事の説明を見て復習して下さい。

「現在の局面 を 相手の手番 と みなし、合法手 の中で、相手が着手 して 勝利 する マス を、相手の勝利を阻止 する 着手 として 選択 する」

残念ながら、評価値 を 計算 する 評価関数 の 仮引数 には、現在の局面 に対して 合法手 を 着手 した 後 の 局面 のデータ しか代入されない ので、現在の局面 を 相手の手番 と みなす という 処理 を行うことは できません。また、上記の考え方 に 改良 する 前 の ルール 6 のアルゴリズム は、以前の記事で説明したように、着手の処理 を行う 数 が 多くなる ため、処理 に 大きな時間がかかる という 欠点 があります。

そこで、今回の記事では、評価値を利用 する アルゴリズム で、ルール 6 による 着手 を 効率よく選択 する 方法 を紹介します。

ルール 6 のアルゴリズムの問題点

下記は、現在の局面を相手の手番とみなすという、改良を行う前 の ルール 6 のアルゴリズム の再掲です。この中の、手順 3 が 相手の勝利を阻止 する 着手 を 選択 する処理です。

1. 現在の局面 の 合法手の一覧 から 順番 に 合法手 を 取り出し て 着手 を行う
2. 自分が勝利 する 合法手 があれば、それを採用 して 終了 する
3. 上記の 手順 1 で 着手 を行った それぞれの局面 に対して、下記の処理 を行う
   1. 合法手の一覧 から 順番 に 合法手 を 取り出し て 着手 を行う
   2. 相手が勝利 する 合法手 があれば、それを採用 して 終了 する
4. 上記の 手順 1 ~ 3 の 処理 が すべて終了 した時点で、自分が勝利 できる合法手も、相手が勝利 できる合法手も 存在しない ことが 確定 するので、ランダムな着手 を行う

このアルゴリズムの 処理 に 大きな時間 がかかる 理由 は、現在の局面 から、2 手分 の すべて の 合法手 の 組み合わせ で実際に 着手 を行う 必要 がある点にあります¹。そこで、上記のアルゴリズムを 改良 して、ai_by_score の処理が行う、現在の局面 から 1 手分 の 合法手 を 着手 した 局面の評価値だけ で 着手を選択 することができるようにします。

ルール 6 改の定義

ルール 6 の 2 つ目 の 条件 の 目的 は、「相手の勝利 を 阻止 する着手を行う」というものでしたが、これは、「相手 が 勝利できる 着手を 行わない」と 言い換える ことができます。また、具体的な方法はこの後で説明しますが、「相手 が 勝利できる 着手を 行わない」という条件は、1 手分 の 合法手 を 着手 した 局面 の 情報だけ から 判定 することが できます。

ルール 6 の 条件 2 を 変更 した下記のルールを、ルール 6 改 とする。

• 勝てる場合 に 勝つ
• そうでない場合は 相手 が 勝利できる 着手を 行わない
• そうでない場合は ランダム なマスに 着手 する

ただし、このような 条件の言い換え は、間違っている可能性がある ので、本当にそのように言い換えることができるかどうかについて 検証 して 確認 することにします。

表記が長いので、以後は「相手の勝利 を 阻止 する着手を行う」条件を「元の条件」、「相手 が 勝利できる 着手を 行わない」条件を「改良した条件」と 表記 することにします。

ルール 6 も、ルール 6 改 も、条件 1 の「勝てる場合に勝つ 」は 同じ なので、以後の説明は、自分が勝利していない局面 に対する 説明 です。

元の条件 は、「相手の勝利 を 阻止 する着手を行う」という 条件 ですが、この 条件を元 に、〇×ゲームの 局面 を 分類 すると、下記の 3 つに分類 することができます。そこで、この 3 つの それぞれの場合 で、両方の条件 で どのような着手 が 行われるか を 検証 します。

• 相手の勝利を阻止 する 合法手 が 存在しない 場合
• 相手の勝利を阻止 する 合法手 が 1 つ だけある場合
• 相手の勝利を阻止 する 合法手 が 2 つ以上 ある場合

相手の勝利を阻止する合法手が存在しない場合

元の条件 の場合は、条件を満たす合法手 が 存在しない ので、ルール 6 の 「そうでない場合は ランダム なマスに 着手 する」という 条件 3 が適用され、合法手 の中から ランダムな着手 を 選択 することになります。

相手の勝利を阻止 する 合法手 が 存在しない ということは、次の 相手の手番 で 相手が勝利 する ことがない ということを表します。従って、すべての合法手 が 改良した条件 である「相手 が 勝利できる 着手を 行わない」を満たすので、改良した条件 の場合も 合法手 の中から ランダムな着手 を 選択 することになります。

上記 から、どちらの条件も、同じ方法 で 着手を選択 することが 確認 できました。

相手の勝利を阻止する合法手が 1 つだけある場合

この場合の 局面 は、以下 のような 状況 の局面です。

• その合法手 を 選択 すると、次の相手の手番 で 相手が勝利 することは 無い
• その合法手 以外 を 選択 すると、次の相手の手番 で 相手 が 勝利できる

元の条件 の場合は、その合法手 を 選択する ことになります。

改良した条件 の場合は、その合法手以外 の合法手を 選択しない ので、やはり その合法手 を 選択 することになります。

上記 から、どちらの条件も、同じ方法 で 着手を選択 することが 確認 できました。

相手の勝利を阻止する合法手が 2 つ以上ある場合

この場合の 局面 は、以下 のような 状況 の局面です。下記からわかるように、どの合法手 に 着手 しても、次の相手の手番 で 相手が勝利 できます。

• 相手の勝利を阻止 する 合法手 中の どれを選択 しても、次の相手の手番 で 選択されなかった 別の 合法手 を 着手 して 相手 が 勝利できる
• その合法手 以外 を 選択 すると、次の相手の手番 で 相手 が 勝利できる

元の条件 の場合は、相手の勝利 を 阻止 する 合法手 の いずれか を 選択 します。ai6 の場合は、最初に見つかった合法手 を 選択 しますが、ランダムに選択しても構いません。

改良した条件 の場合は、条件を満たす合法手 は 存在しない ので、ルール 6 の 条件 3 が適用され、すべて の 合法手 の中から ランダムな着手 を 選択 することになります。

上記から、元の条件 と 改良した条件 で、選択される着手 が 異なる ことが 分かります。そのため、この 違い によって、AI の強さが変わる かどうかを 検証 する必要があります。

AI の強さが変わるかどうかの検証

相手の勝利を阻止 する 合法手 が 2 つ以上 ある場合に、元の条件 と、改良した条件 によって選択される着手の 違い は以下のようになります。

• 元の条件 の場合は、相手が勝利 する 合法手 に 着手 を行うので、相手の手番 で 相手 が 勝利できる 合法手の 数 が必ず 1 つ減る
• 改良した条件 の場合は、ランダムな着手 を行うので、相手の手番 で 相手 が 勝利できる 合法手の 数 が 1 つ減る 場合と、減らない 場合がある

相手の AI が、勝てる場合に勝つ という ルール で 着手 を 選択 する場合は、どちらの条件 でも 相手が勝利 することに変わりはありません。

一方、相手の AI が、勝てる場合に勝つ という ルール で 着手 を 選択しない 場合は、相手 が 勝利しない 着手を行う 可能性 が生じます。例えば、相手の AI が ランダムな着手 を行う場合は、相手 が 勝利できる 合法手の 数が多いほうが、相手が勝利 する 確率 が 高くなります。従って、必ず 相手が 勝利できる 合法手の 数が減る という、元の条件 のほうが、相手が勝利 する 確率 が 低くなる ことになります。そのことを 確認 するために、ai6s の 実装後 に、常にランダムな着手 を行う ai2 と ai6s で 対戦 することにします。

下記は、上記の考察をまとめたものです。

• 相手が「勝てる場合に勝つ」というルールを 持つ 場合は、ルール 6 と ルール 6 改 の AI は 同じ強さ を持つ
• 相手が「勝てる場合に勝つ」というルールを 持たない 場合は、ルール 6 のほうが ルール 6 改 より も ほんの少しだけ強い

ルール 6 改 のほうが 弱い場合がある のは 問題 だと 思う 人が いるかもしれません が、実際には このことはほとんど 問題にはなりません。その理由は、勝てる場合に勝つ という ルール が、〇× ゲームの 初心者 でも すぐに思いつく ような あまりにも簡単なルール であり、強い AI を作る際に、必須 となる ルール だからです。従って、ある程度強い AI であれば、「勝てる場合に勝つ」という ルール を 必ず持っている ので、そのようなルールを持たない 弱い AI に 多少弱く なっても 全く問題ない と考えることができます。

元の条件と改良した条件で AI の強さが変わらない理由

下記は、上記の 検証結果 を 表にまとめた ものです。

相手の勝利を阻止する合法手	着手の方法	強さへの影響
存在しない	同じ方法で着手を行う	なし
1 つだけ存在する	同じ方法で着手を行う	なし
2 つ以上存在する	異なる方法で着手を行う	ある程度相手が強ければ、 なしとみなすことができる

表から、すべての場合 で、どちらの方法 で 着手を選択 しても、基本的 には AI の強さ に 影響を及ぼさない ことが分かります。従って、元の条件 を、改良した条件 に 言い換えても、ルール 6 と 同じ強さ の AI を 実装できる ことが 確認 できました。

評価値の再設定

ルール 6 の条件 を 変更 したので、評価値 の 設定方法 もそれに合わせて 修正 する 必要 があります。ルール 6 改以前 の 条件 は、何らかの 条件を満たす 着手を 選択する というものでした。その場合は、条件を満たす 着手を行った 局面 の 評価値 を 高く 設定します。

一方、ルール 6 改 の 条件 2 は、何らかの 条件を満た す着手を 選択しない というものです。この場合は、条件を満たす 着手を行った 局面 の 評価値 を 低く 設定します。

従って、評価値 を下記の表のように 設定 することができます。なお、相手が勝利できる ということは、自分にとって 不利な状況 を表すので、評価値 には 負の値 である -1 を設定しました。また、それに合わせて、自分が勝利 している局面の 評価値 を 1 に修正 しました。

局面の状況	評価値
自分が勝利している	1
相手が勝利できる	-1
それ以外の場合	0

なお、表の 評価値の列 の数字は、大きい順 に並んでいた方が 分かりやすく、間違えにくくなる ので、そのように 行の順番 を 入れ替える ことにします。ただし、下記の表のように、単純に入れ替えてしまうと、「それ以外の場合」の行の 意味 が わからなくなる ので、その行の 説明 を 言い換える 必要があります。

局面の状況	評価値
自分が勝利している	1
それ以外の場合	0
相手が勝利できる	-1

「それ以外の場合」とは、「相手が勝利できない」という状況なので、下記の表のように修正すれば良いと思うかもしれませんが、下記の表 には 問題 があります。

局面の状況	評価値
自分が勝利している	1
相手が勝利できない	0
相手が勝利できる	-1

これまでの表 では、上にある行 のほうが 優先順位が高い 条件でしたが、上記の表は、「2 行目 > 4 行目 > 3 行目」の順で優先順位が高くなっており、ルールの 条件 の 優先順位 が 高い順 に 行 が 並んでいません。上記のような、条件の数が少ない場合は誤解は発生しないかもしれませんが、今後、条件の数 が 増えた場合 に、この 表を見て プログラムを 記述する と、優先順位 の 間違い による バグが発生 する 可能性が高く なります。そこで、下記の表のように、優先順位 を表す 列を追加 することにします。

優先順位	局面の状況	評価値
1	自分が勝利している	1
3	相手が勝利できない	0
2	相手が勝利できる	-1

次の相手の着手で相手が勝利するかどうかを判定する方法

上記のような 評価値 を 計算 するためには、相手の着手 で 相手 が 勝利できるか どうかを 判定 する必要があります。その方法について少し考えてみて下さい。

〇×ゲーム で、相手の着手 で 相手が勝利 するという 局面 は、縦 3 種類、横 3 種類、斜め 2 種類 の 計 8 種類 ある 一直線上 の 3 マス のうち、「相手のマークが配置 されている マスが 2 つ と、空白のマス が 1 つ ある」ものが 存在する場合 です。従って、そのことを判定 することで、相手の着手 で 相手が勝利できるか どうかを 判定 することが できます。

一直線上 の 3 マス に 配置 されている、自分のマーク の 数を数える 処理は、judge メソッド を 実装する際 に 定義 した is_same メソッド の 実装方法の一つ²として、以前の記事で紹介した 下記のプログラム の中で 記述 しました。is_same は、以前の記事 で説明した、差分で座標を計算 する アルゴリズム を使っているので、忘れた方は復習して下さい。

具体的には、is_same は、coord という 座標 の マスから始まり、dx、dy を 差分 とする 一直線上 の 3 つのマス に mark のマークが 配置 されている 数を数え、count という変数に 代入 する 処理 を行います。

def is_same(self, mark, coord, dx, dy):
    x, y = coord   
    count = 0
    for _ in range(self.BOARD_SIZE):
        if self.board[x][y] == mark:
            count += 1
        x += dx
        y += dy

    return count == self.BOARD_SIZE

count_marks の定義

is_same を 参考 にして、下記の メソッド を Marubatsu クラス に 定義 する事にします。

名前：マークの数 を 数える ので、count_marks という名前にする
処理：〇 のマーク、× のマーク、空のマス の それぞれの数 を 数える
入力：入力として、is_same と 同じ仮引数 を持つようにする。ただし、count_marks は すべてのマーク を 数える ので、仮引数 mark は 必要がない ので 削除 する
出力：それぞれ の 数えた数 を 要素 として持つ defaultdict を返す

それぞれ の 数を数える処理 は、以前の記事で紹介した、defaultdict を 利用した集計 と 同じ方法 で行うことができるので、count_marks は下記のプログラムのように定義できます。

• 5 行目：〇、×、空のマス を 数える ための ローカル変数 count を、既定値 が 0 の defaultdict で 初期化 する
• 7 行目：count の、(x, y) のマスの マーク を キー とする キーの値 を 1 増やす
• 11 行目：count を 返り値 として 返す

 1  from collections import defaultdict
 2
 3  def count_marks(self, coord, dx, dy):
 4      x, y = coord   
 5      count = defaultdict(int)
 6      for _ in range(self.BOARD_SIZE):
 7          count[self.board[x][y]] += 1
 8          x += dx
 9          y += dy
10
11       return count
12
13  Marubatsu.count_marks = count_marks

行番号のないプログラム

from collections import defaultdict

def count_marks(self, coord, dx, dy):
    x, y = coord   
    count = defaultdict(int)
    for _ in range(self.BOARD_SIZE):
        count[self.board[x][y]] += 1
        x += dx
        y += dy

    return count

Marubatsu.count_marks = count_marks

修正箇所（is_same との違いです）

from collections import defaultdict

-def is_same(self, mark, coord, dx, dy):
+def count_marks(self, coord, dx, dy):
    x, y = coord   
-   count = 0
+   count = defaultdict(int)
    for _ in range(self.BOARD_SIZE):
-       if self.board[x][y] == mark:
-           count += 1
+       count[self.board[x][y]] += 1
        x += dx
        y += dy

    return count

Marubatsu.count_marks = count_marks

下記は、いくつかの局面 に対して、一番上の行 の 3 マス に 配置 された 〇、×、空のマス の 数 を、count_marks で 数えた結果 を 表示 するプログラムです。count_marks に記述した 実引数 の 意味が分からない 方は、以前の記事を復習して下さい。実行結果 から、正しく数えている ことが 確認 できます。

mb = Marubatsu()

print(mb)
print(mb.count_marks((0, 0), 1, 0))

mb.move(0, 0)
print(mb)
print(mb.count_marks((0, 0), 1, 0))

mb.move(1, 0)
print(mb)
print(mb.count_marks((0, 0), 1, 0))

mb.move(2, 0)
print(mb)
print(mb.count_marks((0, 0), 1, 0))

実行結果

Turn o
...
...
...

defaultdict(<class 'int'>, {'.': 3})
Turn x
O..
...
...

defaultdict(<class 'int'>, {'o': 1, '.': 2})
Turn o
oX.
...
...

defaultdict(<class 'int'>, {'o': 1, 'x': 1, '.': 1})
Turn x
oxO
...
...

defaultdict(<class 'int'>, {'o': 2, 'x': 1})

なお、defaultdict を print で表示すると、下記 のように 表示 されます。上記の 実行結果 と 見比べて下さい。

defaultdict(既定値に関する情報, dict の情報)

ai6s の定義

8 種類 の 一直線上 の 3 マス の マークの数 を 数える方法 は、下記の Marubatsu クラスの is_winner メソッドと 同様の方法 で行うことができます。

    def is_winner(self):
        # 横方向と縦方向の判定
        for i in range(self.BOARD_SIZE):
            if self.is_same(player, coord=[0, i], dx=1, dy=0) or \
            self.is_same(player, coord=[i, 0], dx=0, dy=1):
                return True
        # 左上から右下方向の判定
        if self.is_same(player, coord=[0, 0], dx=1, dy=1):
            return True
        # 右上から左下方向の判定
        if self.is_same(player, coord=[2, 0], dx=-1, dy=1):
            return True

        # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
        return False

従って、ai6s は、is_winner を 参考 に、下記のプログラムのように記述できます。ただし、下記の 11、14、18、22 行目 の「次の相手の局面で相手が勝利できる」の 条件式 は 未完成 です。その 条件式 を どのように記述 すればよいかについて少し考えてみて下さい。

 1  def ai6s(mb, debug=False):
 2      def eval_func(mb):
 3          # 自分が勝利している場合は、評価値として 1 を返す
 4          if mb.status == mb.last_turn:
 5              return 1
 6
 7          # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
 8          # 横方向と縦方向の判定
 9          for i in range(mb.BOARD_SIZE):
10              count = mb.count_marks(coord=[0, i], dx=1, dy=0)
11              if 次の相手の局面で相手が勝利できる:
12                  return -1
13              count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
14              if 次の相手の局面で相手が勝利できる:
15                  return -1
16          # 左上から右下方向の判定
17          count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
18          if 次の相手の局面で相手が勝利できる:
19              return -1
20          # 右上から左下方向の判定
21          count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
22          if 次の相手の局面で相手が勝利できる:
23              return -1
24
25          # それ以外の場合は評価値として 0 を返す
26          return 0
27
28      return ai_by_score(mb, eval_func, debug=debug)

次の相手の手番 で 相手が勝利 できる 条件 は、一直線上 の 3 マス に 相手のマーク が 2 つ、空のマス が 1 つ の場合です。また、mb は 相手の手番 の 局面 なので、相手のマーク は、mb.turn に 代入 されています。従って、下記の 条件式 で 判定 できます。

if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:

この 条件式 を 当てはめる ことで、ai6s を下記のプログラムのように 定義 できます。

def ai6s(mb, debug=False):
    def eval_func(mb):
        # 自分が勝利している場合は、評価値として 1 を返す
        if mb.status == mb.last_turn:
            return 1

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1

        # それ以外の場合は評価値として 0 を返す
        return 0

    return ai_by_score(mb, eval_func, debug=debug)        

修正箇所

def ai6s(mb, debug=False):
    def eval_func(mb):
        # 自分が勝利している場合は、評価値として 1 を返す
        if mb.status == mb.last_turn:
            return 1

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
-           if 次の相手の局面で相手が勝利できる:
+           if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
-           if 次の相手の局面で相手が勝利できる:
+           if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
-       if 次の相手の局面で相手が勝利できる:
+       if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
-       if 次の相手の局面で相手が勝利できる:
+       if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1

        # それ以外の場合は評価値として 0 を返す
        return 0

    return ai_by_score(mb, eval_func, debug=debug)      

動作の確認

ai6s が 正しく動作 するかどうかを 確認 するために、ai6 と 対戦 を行います。ai6 は、「勝てる場合に勝つ」という ルール を 持つ ので、ai6 と ai6s は 同じ強さ を持つはずです。実行結果 から、ai6s を 正しく実装 できていることが 確認 できました。

ai_match(ai=[ai6s, ai6])

実行結果（実行結果はランダムなので下記とは異なる場合があります）

ai6s VS ai6
count     win    lose    draw
o        3161    1672    5167
x        1723    3114    5163
total    4884    4786   10330

ratio     win    lose    draw
o       31.6%   16.7%   51.7%
x       17.2%   31.1%   51.6%
total   24.4%   23.9%   51.6%

ai6 と ai6s が選択する着手の違い

先程説明したように、ai6 と ai6s は、「相手の勝利を阻止 する 合法手 が 2 つ以上 ある」場合は、異なる方法 で 着手 を行います。そのことを下記のプログラムで 確認 します。

実行結果 からわかるように、ai6 は、2 つ ある 相手の勝利を阻止 する 合法手 のうちの (2, 1) に 必ず着手 を行いますが、ai6s は、どこに着手 を行っても 相手の勝利 を 阻止できない ので、ランダムな着手 を行った結果、(1, 2) という、相手の勝利 を 阻止しない着手 も 行う ので、いずれの場合 でも 相手が勝利 することに 変わりはありません。

mb = Marubatsu()

mb.move(1, 1)
mb.move(1, 0)
mb.move(0, 0)
mb.move(2, 0)
mb.move(0, 1)
print(mb)

print("ai6")
for i in range(10):
    print(ai6(mb))
    
print("ai6s")
for i in range(10):
    print(ai6s(mb))

実行結果（実行結果はランダムなので下記とは異なる場合があります）

Turn x
oxx
Oo.
...

ai6
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
ai6s
(1, 2)
(2, 1)
(2, 1)
(2, 1)
(2, 2)
(1, 2)
(2, 1)
(0, 2)
(1, 2)
(2, 2)

なお、強さ という 観点 では、ai6 と ai6s は 同じ強さを 持ちますが、人間 と 対戦 した場合は、ai6s が、敗北 が 確実 になった場合に 最善を尽くさない、投げやりな着手 を行うように 見える かもしれません。人間の心理 として、負けるとわかってる場合 でも、最善を尽くさなければ、相手に失礼 だというものがあるからです。ai6s が ai6 と 同様の着手 を行うようにする方法については今後の記事で紹介します。

ai2 との対戦

さきほど、常にランダム な 着手 を行う ai2 に対しては、ai6s は ai6 より も 若干弱くなる という説明を行いましたので、そのことを下記のプログラムで 確認 することにします。

ai_match(ai=[ai7s, ai7])

実行結果（実行結果はランダムなので下記とは異なる場合があります）

ai6s VS ai2
count     win    lose    draw
o        8858     195     947
x        6937     912    2151
total   15795    1107    3098

ratio     win    lose    draw
o       88.6%    1.9%    9.5%
x       69.4%    9.1%   21.5%
total   79.0%    5.5%   15.5%

下記は、ai6 VS ai2 と ai6s VS ai2 の 対戦結果 を表にしたものです。実行結果 から、〇 を担当 する場合は 成績 は ほとんど変わりません が、× を担当 する場合は、ai6sのほう が ai6 より 少しだけ 敗率が 悪い ことが 確認 できます。このような結果になる 理由 は、おそらく 〇 を担当 する場合は、ルール 6 と ルール 6 改 の 違いが影響する ような 局面 が ほとんど生じない からだと 推測 されます。

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分	欠陥
ai6	88.9	2.2	8.9	70.3	6.2	23.5	79.6	4.2	16.2
ai6s	88.6	1.9	9.5	69.4	9.1	21.5	79.0	5.5	15.5

評価値を利用した ルール 7 で着手を行う AI の定義

ルール 7 は、下記のように、ルール 6 に、真ん中 のマスに 優先的 に 着手 するという 条件 を 加えた ものです。

• 真ん中 のマスに 優先的 に 着手 する
• 勝てる場合 に 勝つ
• そうでない場合は 相手の勝利 を 阻止 する
• そうでない場合は ランダム なマスに 着手 する

ai6s と 同様の方法 で 定義 できるように、ルール 7 の 条件 3 を下記のように 言い換えた、下記の ルール 7 改 で ai7s を 定義 する事にします。難しくはない と思いますが、評価値 を どのように設定 すればよいかについて少し考えてみて下さい。

• 真ん中 のマスに 優先的 に 着手 する
• 勝てる場合 に 勝つ
• そうでない場合は 相手 が 勝利できる 着手を 行わない
• そうでない場合は ランダム なマスに 着手 する

下記は ルール 7 改 の 評価値 の 設定 の 一例 です。

優先順位	局面の状況	評価値
1	真ん中のマスに着手している	2
2	自分が勝利している	1
4	相手が勝利できない	0
3	相手が勝利できる	-1

なお、以前の記事 で示したように、ルール 7 で 着手 を 行う 場合に、真ん中 のマスに 着手 した 時点 で 自分が勝利 することは あり得ない ので、下記の表のように、「真ん中のマスに着手 する」局面と、「自分が勝利している」局面の 評価値 を 同じ に 設定 しても 構いません。なお、本記事では上記の表で評価値を設定することにします。

優先順位	局面の状況	評価値
1	真ん中のマスに着手している	1
2	自分が勝利している	1
4	相手が勝利できない	0
3	相手が勝利できる	-1

ai7s の定義

下記は、ai7s を 定義 するプログラムです。特に 難しい点はない と思います。

• 4、5 行目：真ん中 のマスに 着手 した場合は、評価値 として 2 を 返す 処理を 追加 する

1  def ai7s(mb, debug=False):
2      def eval_func(mb):
3          # 真ん中のマスに着手している場合は、評価値として 2 を返す
4          if mb.last_move == (1, 1):
5              return 2
6    
以下は ai6s と同じなので省略       

行番号のないプログラム

def ai7s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 2 を返す
        if mb.last_move == (1, 1):
            return 2
    
        # 自分が勝利している場合は、評価値として 1 を返す
        if mb.status == mb.last_turn:
            return 1

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1

        # それ以外の場合は評価値として 0 を返す
        return 0

    return ai_by_score(mb, eval_func, debug=debug)      

修正箇所

-def ai6s(mb, debug=False):
+def ai7s(mb, debug=False):
    def eval_func(mb):
+       # 真ん中のマスに着手している場合は、評価値として 2 を返す
+       if mb.last_move == (1, 1):
+           return 2

以下は ai6s と同じなので省略

なお、ai7 では、その ブロックの中 で ai6 を呼び出す ことで、簡潔 なプログラムで 定義 することが できました が、ai6s の 評価関数 は、ローカル関数 として 定義 しているので、ai7s の ブロックの中 で、ai6s の 評価関数 を 利用 することは できません。そのため、ai7s を ai7 のように 簡潔に記述 することは できません。

ai7s を ai7 のように 簡潔に記述 する場合は、ai6s の 評価関数 を グローバル関数 として 定義 する必要があります。ただし、ai6s の 評価関数 は、ai6s と ai7s 以外 で 利用する予定はない ので、本記事ではグローバル関数で定義しません。

動作の確認

ai7s が 正しく動作 するかどうかを 確認 するために、ai7 と 対戦 を行います。実行結果 から、ai7s を 正しく実装 できていることが 確認 できました。

ai_match(ai=[ai7s, ai7])

実行結果（実行結果はランダムなので下記とは異なる場合があります）

ai7s VS ai7
count     win    lose    draw
o        2950     416    6634
x         417    2910    6673
total    3367    3326   13307

ratio     win    lose    draw
o       29.5%    4.2%   66.3%
x        4.2%   29.1%   66.7%
total   16.8%   16.6%   66.5%

本記事では確認しませんが、ai7s は、ai6s と 同様の理由 で、ai2 に対する成績 は、ai7 より も 若干悪く なります。興味がある方は実際に確認してみて下さい。

今回の記事のまとめ

今回の記事では、局面に対する評価値の 設定方法 と、計算方法 について 説明 し、ルール 5 ~ 7 の AI を 評価値を利用 した アルゴリズム で定義しました。その際に、ルール 6、7 の 条件 の一つを 言い換えた、ルール 6 改、7 改 を 定義 しました。

また、同じルール で 着手 を 選択 する AI でも、アルゴリズム の 違い によって、AI の強さ は 変わらない が、着手 の 選択方法 が 異なる場合がある ことを 説明 しました。

次回の記事では、評価値を利用 した アルゴリズム で、より強い AI を作成する方法について説明します。

本記事で入力したプログラム

以下のリンクから、本記事で入力して実行した JupyterLab のファイルを見ることができます。

以下のリンクは、今回の記事で更新した marubatsu.py です。

以下のリンクは、今回の記事で更新した ai.py です。

次回の記事

1. 実際には、途中 で 着手を選択 する 場合があり、その場合はすべての着手を行う必要はありませんが、多くの場合 で すべての着手 を 行う必要 があります ↩

2. 実際の Marubatsu クラスの is_same メソッドは、これとは別の方法で実装しています。 ↩