LoginSignup
0
0
@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その51　〇×ゲームに勝つための条件

Last updated at Posted at 2024-02-04

目次と前回の記事

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

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

これまでに作成した AI

これまでに作成した AI の アルゴリズム は以下の通りです。今回の記事から、左の列を「関数名」から「ルール」に変更しました。

ルール アルゴリズム
ルール1 左上から順 に 空いているマス を探し、最初に見つかったマス に 着手 する
ルール2 ランダム なマスに 着手 する
ルール3 真ん中 のマスに 優先的 に 着手 する
既に 埋まっていた場合 は ランダム なマスに 着手 する
ルール4 真ん中、隅 のマスの 順 で 優先的 に 着手 する
既に 埋まっていた場合 は ランダム なマスに 着手 する
ルール5 勝てる場合 に 勝つ
そうでない場合は ランダム なマスに 着手 する
ルール6 勝てる場合 に 勝つ
そうでない場合は 相手の勝利 を 阻止 する
そうでない場合は ランダム なマスに 着手 する
ルール6改 勝てる場合 に 勝つ
そうでない場合は 相手 が 勝利できる 着手を 行わない
そうでない場合は ランダム なマスに 着手 する
ルール7 真ん中 のマスに 優先的 に 着手 する
そうでない場合は 勝てる場合 に 勝つ
そうでない場合は 相手の勝利 を 阻止 する
そうでない場合は ランダム なマスに 着手 する
ルール7改 真ん中 のマスに 優先的 に 着手 する
そうでない場合は 勝てる場合 に 勝つ
そうでない場合は 相手 が 勝利できる 着手を 行わない
そうでない場合は ランダム なマスに 着手 する

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

関数名 o 勝 o 負 o 分 x 勝 x 負 x 分 勝 負 分 欠陥
ai1
ai1s 		78.1 17.5 4.4 44.7 51.6 3.8 61.4 34.5 4.1 あり
ai2
ai2s 		58.7 28.8 12.6 29.1 58.6 12.3 43.9 43.7 12.5
ai3
ai3s 		69.3 19.2 11.5 38.9 47.6 13.5 54.1 33.4 12.5
ai4
ai4s 		83.0 9.5 7.4 57.2 33.0 9.7 70.1 21.3 8.6 あり
ai5
ai5s 		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
ai6s 88.6 1.9 9.5 69.4 9.1 21.5 79.0 5.5 15.5
ai7
ai7s 		95.8 0.2 4.0 82.3 2.4 15.3 89.0 1.3 9.7

〇×ゲームに勝つ方法の考察の必要性

以前の記事で説明したように、ルールベース の AI は、「解決すべき問題 に対する、人間の知識 を ルール化 し、その ルールに基づいて AI が 判断を行う」という AI です。

従って、ルールベース で 強い AI を 作成 するためには、〇×ゲーム に関する 深い知識 が必要になります。ルール 5 の「勝てる場合に勝つ」と、ルール 6 の「相手の勝利を阻止する」は、〇×ゲームを少し遊べば 誰でも思いつく ルールだと思いますが、それ以上に強い AI を作成するためには、より深い 〇×ゲームの 知識が必要 になります。

今回の記事から、〇×ゲーム に 勝つ方法 を 考察 し、その 考察に基づいた AI を 作成 します。〇×ゲームがあまり強くない人は、〇×ゲームに 勝つ方法 について考えてみて下さい。また、〇×ゲームがある程度強い人は、その 方法 を ルール化 して下さい。

勝利するために必要な条件

ゲームに 強くなるため に 必要 な 最低限 の 考察 として、以下のようなものが挙げらるでしょう。そこで、まず、〇×ゲームで 勝つため に 必要な条件 について 考察 することにします。どのような条件が必要であるかについて少し考えてみて下さい。

  • ゲームに 勝つため の 条件
  • ゲームに 負けないため の 条件

〇×ゲームは、以下 の 性質 を持つゲームです。

  1. 交互 に 空いているマス に 自分のマーク を 配置 する
  2. 一度 マークが配置 された マス は、ゲーム終了まで 変化しない
  3. 8 種類 ある 直線上の 3 マス の いずれか に、自分のマーク が 3 つ並ぶ と 勝利 する

上記の 性質 3 から、自分 が 勝利できる 局面は、いずれか の 直線上の 3 マス が、以下の状態 になっている 必要がある ことがわかります。

  • 自分のマーク が 2 つ配置 されている
  • 空いているマス が 1 つある

直線上の 3 つのマス の 配置の状態 を 簡潔に表現 するために、以後は、「直線上の 3 マスに、自分のマーク が x 個、相手のマーク が y 個、空いている マスが z 個 ある」ことを、「自 x 敵 y 空 z」 のように 表記 することにしま

例えば、上記の場合は、「自 2 敵 0 空 1」と 表記 します。

上記の考察から、以下の事が分かります。

〇×ゲーム に 勝つため には、自分の手番 で 着手 を行った 結果、「自 2 敵 0 空 1」が 1 つ以上 存在する 局面になる着手を行う 必要 がある。

〇×ゲームは、直線上 の マスの数 が常に 3 なので、「自 x 敵 y 空 z」の x、y、z には、$x + y + z = 3$ という関係があります。これは、x、y、z のうち、2 つの値 が 決まる と、残り の 1 つの 値 が 自動的に決まる ということを表します。従って、「自 x 敵 y 空 z」は、その中の いずれか 1 つを削除 して「自 x 敵 y」のように 記述 しても かまいません が、本記事では わかりやすさ を重視して 3 つ を すべて記述 することにします。

余談ですが、複数 の 変数 のうち、自由（独立に）に変更 できる 変数 の 数 の事を 自由度 と呼びます。「自 x 敵 y 空 z」の場合の自由度は 2 です。

また、count_marks の処理を、いずれかの 2 つの数 だけを 数える ように 修正 することも 可能 ですが、そのように修正するとかえって プログラムが複雑 になるので、修正しないほうが良い でしょう。

ルール 8 の定義

もちろん、上記の条件 を満たすような 着手 を行っても、次の相手の手番で 邪魔をされる場合がある ので 自分の勝ち が 確定 するわけでは ありません が、少なくとも 上記の 条件を満たす着手 を 行わなければ、自分が勝利 することは あり得ません。

そこで、上記 を満たす 着手 を 優先的に行う という 条件 を ルール 7 改 に加えた 下記の ルール 8 を考えることにします。なお、上記の条件 を 満たしても、その次の 相手の手番 で 相手が勝利 しては 意味がない ので、上記の条件 は、「相手 が 勝利できる 着手を 行わない」という 条件より も 優先順位を低く する 必要 があります。

  • 真ん中 のマスに 優先的 に 着手 する
  • そうでない場合は 勝てる場合 に 勝つ
  • そうでない場合は 相手 が 勝利できる 着手を 行わない
  • そうでない場合は、次 の 自分の手番 で 勝利できる ように、「自 2 敵 0 空 1」が 1 つ以上 存在する 局面になる着手を行う
  • そうでない場合は ランダム なマスに 着手 する

ルール 8 の 評価値 をどのように 設定 すればよいかについて少し考えてみて下さい。

評価値の設定

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

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

上記の表に、ルール 8 の『「自 2 敵 0 空 1」が 1 つ以上 存在する』 という 新しい条件 を 追加 した状態の 評価値を設定 する必要があります。

下記の表は、ルール 8 の 条件の優先順位 に注意しながら 評価値 を 設定 した例です。上 2 つ の 評価値 は、新しい条件の追加に合わせて 修正 しました。

優先順位 局面の状況 評価値
1 真ん中のマスに着手している 3
2 自分が勝利している 2
4 「自 2 敵 0 空 1」が 1 つ以上存在する 1
5 「自 2 敵 0 空 1」が存在しない 0
3 相手が勝利できる -1

ai8s の定義

局面に 「自 2 敵 0 空 1」が 1 つ以上存在するか どうかは、前回の記事で定義した count_marks メソッドで 計算 できるので、ai8s は、下記のように定義できます。

  • 7、8 行目：真ん中 のマスに着手した時の 評価値 を 3 に 修正 する
  • 11、12 行目：自分が勝利 している場合の 評価値 を 2 に 修正 する
  • 23、24、28、29、34、35、40、41 行目：相手 が 勝利できない 局面で、次 の 自分の手番 で 自分 が 勝利できる かどうかを、「自 2 敵 0 空 1」であるかどうかで 判定 し、その場合は 評価値 として 1 を 返す。mb は 相手の手番 の局面であり、自分の手番 は、mb.last_turn に 代入 されている点に 注意 すること
 1  from ai import ai_by_score
 2  from marubatsu import Marubatsu
 3
 4  def ai8s(mb, debug=False):
 5      def eval_func(mb):
 6          # 真ん中のマスに着手している場合は、評価値として 3 を返す
 7          if mb.last_move == (1, 1):
 8              return 3
 9   
10          # 自分が勝利している場合は、評価値として 2 を返す
11          if mb.status == mb.last_turn:
12              return 2
13
14          # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
15          # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
16          # 横方向と縦方向の判定
17          for i in range(mb.BOARD_SIZE):
18              count = mb.count_marks(coord=[0, i], dx=1, dy=0)
19              # 「自 0 敵 2 空 1」の場合は相手が勝利できる
20              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
21                  return -1
22              # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
23              elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
24                  return 1
25              count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
26              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
27                  return -1
28              elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
29                  return 1
30          # 左上から右下方向の判定
31          count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
32          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
33              return -1
34          elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
35              return 1
36          # 右上から左下方向の判定
37          count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
38          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
39              return -1
40          elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
41              return 1
42
43          # それ以外の場合は評価値として 0 を返す
44          return 0
45
46      return ai_by_score(mb, eval_func, debug=debug)
行番号のないプログラム 
from ai import ai_by_score
from marubatsu import Marubatsu

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

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
            elif count[mb.last_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
            elif count[mb.last_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
        elif count[mb.last_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
        elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return 1

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

    return ai_by_score(mb, eval_func, debug=debug)
修正箇所 
from ai import ai_by_score
from marubatsu import Marubatsu

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

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
+           elif count[mb.last_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
+           elif count[mb.last_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
+       elif count[mb.last_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
+       elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+           return 1

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

    return ai_by_score(mb, eval_func, debug=debug)

ai2 と ai7s との対戦

基準となる ai2 と、これまで に作成した 最強の AI である ai7s と対戦することにします。まず、下記のプログラムで ai2 と対戦します。

from ai import ai_match, ai2, ai7s

ai_match(ai=[ai8s, ai2])

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

ai8s VS ai2
count     win    lose    draw
o        9726     148     126
x        8608     854     538
total   18334    1002     664

ratio     win    lose    draw
o       97.3%    1.5%    1.3%
x       86.1%    8.5%    5.4%
total   91.7%    5.0%    3.3%

下記は、ai7 VS ai2 と ai8s VS ai2 の対戦結果の表です。ai2 に対して、ai8s のほうが、ai7 より 勝率が高くなる ことが確認できますが、よく見ると、敗率も高く なっています。ルール 8 の 条件 4 の 追加 で 敗率が高くなる のは 何かが変 です。

関数名 o 勝 o 負 o 分 x 勝 x 負 x 分 勝 負 分 欠陥
ai7 95.8 0.2 4.0 82.3 2.4 15.3 89.0 1.3 9.7
ai8s 97.3 1.5 1.3 86.1 8.5 5.4 91.7 5.0 3.3

次に、ai7s と 対戦 を行います。実行結果から、強くしたはず の ai8s が ai7 に 対して 大きく負け越している 点が 変 です。これは、ルール 8 に 欠陥がある か、ai8s が ルール 8 を 正しく実装できていない かの どちらか が 原因 です。ルール 8 を 見直しても 、特に 間違い は なさそう なので、ai8s に バグがある 可能性が高く、実際に ai8s には バグがあります。それが何であるかについて少し考えてみて下さい。

ai_match(ai=[ai8s, ai7s])

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

ai8s VS ai7s
count     win    lose    draw
o        2563    3392    4045
x          92    7373    2535
total    2655   10765    6580

ratio     win    lose    draw
o       25.6%   33.9%   40.5%
x        0.9%   73.7%   25.4%
total   13.3%   53.8%   32.9%

ai8s のバグの原因

下記は、ai8s の 一部を抜粋 したものです。5 ～ 9 行目 のプログラムに バグがある ので、バグがどこにあるかが分からなかった方はその部分を探してみて下さい。

1        # 横方向と縦方向の判定
2        for i in range(mb.BOARD_SIZE):
3            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
4            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
5            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
6                return -1
7            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
8            elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
9                return 1

バグが発生 する 具体的な局面 を例に 説明 します。例えば 下図左 の 〇 の手番 の局面で、ルール 8 で 着手を選択 する場合の事を考えてみて下さい。その場合は、まず、最初の合法手 として、下図右 の 赤い 〇 に 着手 した局面に対して、上記の処理 を行って 評価値を計算 することになります。

上図右 の 局面 に対して上記のプログラムを実行すると、下記 の 処理 が行われます。

  • 2 行目：i に 0 が 代入 されて for 文 の ブロックが実行 される
  • 3 行目：上図右の 上の行 の「〇〇　」の マークの数 を 数え、結果 の「〇 2 × 0 空 1」を表すデータ count に 代入 する。元の局面 は 〇 の手番 なので、これは「自 2 敵 0 空 1」を表すデータである
  • 5 行目：count の内容が、敵 が 勝利できる、「自 0 敵 2 空 1」ではない ので、条件式 が False になる
  • 8、9 行目：count の内容が、次 の 自分の手番 で 自分 が 勝利できる、「自 2 敵 0 空 1」なので、条件式 が True になり、評価値 として 1 を返り値として 返す

上図右 の 局面 は、相手 が 勝利できる ので、評価値 として -1 を 返す必要 がありますが、上記の手順で処理が行われるため、1 が 評価値 として 返り ます。従って、上図右 の局面になるような 着手 を 行うべきではない のに、ai8s はそのマスに 着手 してしまう 可能性 が 生じます。これが、ai8s が ai7 に負け越す原因 です。

下記のプログラムは、上図左 の局面に対して、ai8s で デバッグ表示 を行いながら 着手を選択 するプログラムです。実行結果 から、実際に 上図右 の局面の 評価値 として 1 が 計算 されていることが分かります。

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

ai8s(mb, debug=True)

実行結果

Turn o
o..
xX.
o..

Start ai_by_score
Turn o
o..
xX.
o..

legal_moves [(1, 0), (2, 0), (2, 1), (1, 2), (2, 2)]
====================
move (1, 0)
Turn x
oO.
xx.
o..

score 1 best score -inf
UPDATE
  best score 1
  best moves [(1, 0)]
====================
move (2, 0)
Turn x
o.O
xx.
o..

score 1 best score 1
APPEND
  best moves [(1, 0), (2, 0)]
====================
move (2, 1)
Turn x
o..
xxO
o..

score 0 best score 1
====================
move (1, 2)
Turn x
o..
xx.
oO.

score -1 best score 1
====================
move (2, 2)
Turn x
o..
xx.
o.O

score -1 best score 1
====================
Finished
best score 1
best moves [(1, 0), (2, 0)]

また、残りの合法手 に着手した局面の 評価値 は、下記 のように 計算 されます。

  • (2, 0)：(1, 0) と 同様の手順 で計算が行われ、1 が 計算 される
  • (2, 1)：「自 0 敵 2 空 1」も「自 2 敵 0 空 1」も 存在しない ので 0 が 計算 される
  • (1, 2)、(2, 2)：「自 0 敵 2 空 1」のみが存在 するので、-1 が 計算 される

結果 として、最善手 の 一覧 に (1, 0) と (2, 0) のマスが 計算 され、その いずれか のマスに 着手 が 行われます が、その次 の 相手の手番 で 相手が (2, 1) に 着手 して 勝利 することが できてしまいます。本当は、(2, 1) に 着手 することで 相手の勝利 を 阻止できていた ので、ai8s が 間違った 着手を 選択する ことが 確認 できました。

このようなバグが発生した理由について少し考えてみてください。

ai8s の修正方法 その 1

このバグは、ai8s が、下記 の ルール 8 の表の、優先順位 が 3 と 4 の 条件 を 繰り返し処理の中 の if 文 で まとめて判定 しているため、繰り返しの途中 で 優先順位 が 4 の条件が、3 の条件 よりも優先 されてしまう 場合がある事 が 原因 です。従って、優先順位 が 3 の条件が、4 の条件 より も 必ず優先される ようにすることで バグを修正 することができます。その方法について少し考えてみて下さい。

優先順位 局面の状況 評価値
1 真ん中のマスに着手している 3
2 自分が勝利している 2
4 「自 2 敵 0 空 1」が 1 つ以上存在する 1
5 「自 2 敵 0 空 1」が存在しない 0
3 相手が勝利できる -1

記述は大変 ですが、最も単純 な方法は、下記のプログラムのように、優先順位 が 3 の条件の 判定 が 終了してから、優先順位 が 4 の条件の 判定を行う というものです。

  • 13 ~ 27 行目：相手 が 勝利できるか どうか だけ を 判定 するように 修正 する
  • 31 ~ 45 行目：次 の 自分の手番 で 自分 が 勝利できるか を 判定 する

比べて見ればわかると思いますが、13 ～ 27 行目 と、31 ～ 45 行目 のプログラムは、条件式 と、return 文 の 返り値 を 除けば 、全く同じ処理 を行います。

 1  def ai8s(mb, debug=False):
 2      def eval_func(mb):
 3          # 真ん中のマスに着手している場合は、評価値として 3 を返す
 4          if mb.last_move == (1, 1):
 5              return 3
 6    
 7          # 自分が勝利している場合は、評価値として 2 を返す
 8          if mb.status == mb.last_turn:
 9              return 2
10
11          # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
12          # 横方向と縦方向の判定
13          for i in range(mb.BOARD_SIZE):
14              count = mb.count_marks(coord=[0, i], dx=1, dy=0)
15              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
16                  return -1
17              count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
18              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
19                  return -1
20          # 左上から右下方向の判定
21          count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
22          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
23              return -1
24          # 右上から左下方向の判定
25          count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
26          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
27              return -1
28
29          # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
30          # 横方向と縦方向の判定
31          for i in range(mb.BOARD_SIZE):
32              count = mb.count_marks(coord=[0, i], dx=1, dy=0)
33              if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
34                  return 1
35              count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
36              if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
37                  return 1
38          # 左上から右下方向の判定
39          count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
40          if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
41              return 1
42          # 右上から左下方向の判定
43          count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
44          if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
45              return 1            
46
47          # それ以外の場合は評価値として 0 を返す
48          return 0
49
50      return ai_by_score(mb, eval_func, debug=debug)
行番号のないプログラム 
def ai8s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 3 を返す
        if mb.last_move == (1, 1):
            return 3
    
        # 自分が勝利している場合は、評価値として 2 を返す
        if mb.status == mb.last_turn:
            return 2

        # 相手の手番で相手が勝利できる場合は評価値として -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

        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return 1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return 1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return 1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return 1            

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

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

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
-           elif count[mb.last_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
-           elif count[mb.last_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
-       elif count[mb.last_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
-       elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
-           return 1

        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
+       for i in range(mb.BOARD_SIZE):
+           count = mb.count_marks(coord=[0, i], dx=1, dy=0)
+           if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+               return 1
+           count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
+           if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+               return 1
+       # 左上から右下方向の判定
+       count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
+       if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+           return 1
+       # 右上から左下方向の判定
+        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
+       if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+           return 1            

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

    return ai_by_score(mb, eval_func, debug=debug)

修正の確認

修正したプログラムが 正しく動作 するかを 確認 するために、再び ai2 と ai7s との対戦を行います。まず、基準となる ai2 と 対戦 します。

ai_match(ai=[ai8s, ai2])

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

ai8s VS ai2
count     win    lose    draw
o        9824      14     162
x        8938     249     813
total   18762     263     975

ratio     win    lose    draw
o       98.2%    0.1%    1.6%
x       89.4%    2.5%    8.1%
total   93.8%    1.3%    4.9%

下記は、ai7 VS ai2 と ai8s VS ai2 の対戦結果の表です。今度 は ai2 に対して、ai8s のほうが、ai7 より 勝率が高く なり、敗率 は ほぼ変わらない ので、正しく修正 された 可能性が高い ことが 確認 できます。

関数名 o 勝 o 負 o 分 x 勝 x 負 x 分 勝 負 分 欠陥
ai7 95.8 0.2 4.0 82.3 2.4 15.3 89.0 1.3 9.7
ai8s 98.2 0.1 1.6 89.4 2.5 8.1 93.8 1.3 4.9

続いて、ai7s との 対戦 を行います。実行結果 から、通算成績 では、ai8s の 勝率 の方が 敗率より高い ので、ai8s は ai7s に 対して 強い ことが 確認 できました。

ai_match(ai=[ai8s, ai7s])

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

ai8s VS ai7s
count     win    lose    draw
o        3343     393    6264
x         388    2884    6728
total    3731    3277   12992

ratio     win    lose    draw
o       33.4%    3.9%   62.6%
x        3.9%   28.8%   67.3%
total   18.7%   16.4%   65.0%

ai8s の修正方法 その 2

先程 の ai8s では、以下 のような 手順 で 処理 を行いました。

  • 8 種類ある 直線上の 3 マス に「自 0 敵 2 空 1」が 存在する 場合は -1 を返す
  • 8 種類ある 直線上の 3 マス に「自 2 敵 0 空 1」が 存在する 場合は 1 を返す

上記の 2 つの処理 は、同じような、かなり長い プログラムを 記述 する必要があるので 大変 です。そこで、上記の 2 つの処理 を 1 つにまとめる ことにします。また、1 つにまとめる ことで、処理時間 が 半分になる という 利点 が得られます。どのようにすればまとめることができるかについて、少し考えてみて下さい。

マークの数のパターンを列挙する関数の定義

説明 を 簡潔にする ために、以後は、「自 2 敵 0 空 1」のような、直線上に配置 された マーク の 配置状況 の事を、「マークのパターン」と 表記 します。

ルール 8 で 評価値 を 計算 する際に 必要な処理 は、「自 0 敵 2 空 1」と「自 2 敵 0 空 1」という 2 種類 の マークのパターン が 存在するか を 調べる という処理です。

先ほどのプログラムでは、それらが 存在するか を 調べる ために、8 種類 ある 直線上の 3 マス の マークのパターン を調べるという処理を、2 回に分けて 行いました。それに対して、下記のアルゴリズムでは、8 種類 ある 直線上の 3 マス の マークのパターン を 一度調べるだけ で 同様の処理 を行うことができます。

  1. 8 種類 ある 直線上の 3 マス の マークのパターン を計算し、結果 を 登録 する
  2. 登録 した データの中 に、「自 0 敵 2 空 1」が あれば -1 を 返す
  3. 登録 した データの中 に、「自 2 敵 0 空 1」が あれば 1 を 返す

別の言葉で説明すると、特定 の マークのパターン が 存在するか どうかを 調べる際 に、マークのパターンごと に 8 種類 ある 直線上の 3 マス を 調べ直す の ではなく、調べた結果 を 登録 しておくことで、一度調べるだけ で済むということです。

そこで、Marubatsu クラスに 上記 の 手順 1 の 処理 を行う、以下のような メソッド を 定義 することで、Marubatsu クラスの インスタンス に対して、局面に存在 する マークのパターン の 一覧 を 計算できる ようにします。

名前：マーク（mark）の パターン（pattern）を 列挙（enumerate）するので、enum_markpats という名前にします
処理：インスタンスの 局面 の マークのパターン を 列挙 する
入力：なし
出力：マークのパターン を 列挙 した データ を 返り値 として 返す

マークのパターン を 列挙 する データ型 として、真っ先に思いつくのは list ではないかと思います。そこで、今回の記事では、list を利用 して enum_markpat を下記のプログラムのように定義することにします。行っている処理は、ai8s の中の 処理 と あまり変わらない ので、それほど難しくはないと思います。

  • 2 行目：マークのパターン を 列挙 した データ を 代入 するローカル変数 markpats を 空の list で 初期化 する
  • 5 ~ 15 行目：8 種類 ある 直線上の 3 マス の マークのパターン を、これまでと同様の方法で 計算 する
  • 7、9、12、15 行目：計算したそれぞれの マークのパターン を、marks_pats の 要素 として 追加 する
  • 17 行目：markpats を 返り値 として 返す 
 1  def enum_markpats(self):
 2      markpats = []    
 3
 4      # 横方向と縦方向の判定
 5      for i in range(self.BOARD_SIZE):
 6          count = self.count_marks(coord=[0, i], dx=1, dy=0)
 7          markpats.append(count)
 8          count = self.count_marks(coord=[i, 0], dx=0, dy=1)
 9          markpats.append(count)
10      # 左上から右下方向の判定
11      count = self.count_marks(coord=[0, 0], dx=1, dy=1)
12      markpats.append(count)
13      # 右上から左下方向の判定
14      count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
15      markpats.append(count)
16
17      return markpats
18
19  Marubatsu.enum_markpats = enum_markpats
行番号のないプログラム 
def enum_markpats(self):
    markpats = []    
 
    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
        count = self.count_marks(coord=[0, i], dx=1, dy=0)
        markpats.append(count)
        count = self.count_marks(coord=[i, 0], dx=0, dy=1)
        markpats.append(count)
    # 左上から右下方向の判定
    count = self.count_marks(coord=[0, 0], dx=1, dy=1)
    markpats.append(count)
    # 右上から左下方向の判定
    count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
    markpats.append(count)

    return markpats

Marubatsu.enum_markpats = enum_markpats

ai8s の場合と異なり、計算した マークのパターン は、markpats の 要素に追加するだけ なので、上記のプログラムを下記のように 簡潔に記述 することもできます。本記事では、下記の記述を採用しますが、好きな方を採用して構いません。

def enum_markpats(self):
    markpats = []    
 
    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
        markpats.append(self.count_marks(coord=[0, i], dx=1, dy=0))
        markpats.append(self.count_marks(coord=[i, 0], dx=0, dy=1))
    # 左上から右下方向の判定
    markpats.append(self.count_marks(coord=[0, 0], dx=1, dy=1))
    # 右上から左下方向の判定
    markpats.append(self.count_marks(coord=[2, 0], dx=-1, dy=1))

    return markpats

Marubatsu.enum_markpats = enum_markpats
修正箇所 
def enum_markpats(self):
    markpats = []    

    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
-       count = self.count_marks(coord=[0, i], dx=1, dy=0)
-       markpats.append(count)
+       markpats.append(self.count_marks(coord=[0, i], dx=1, dy=0))
-       count = self.count_marks(coord=[i, 0], dx=0, dy=1)
-       markpats.append(count)
+       markpats.append(self.count_marks(coord=[i, 0], dx=0, dy=1))
    # 左上から右下方向の判定
-   count = self.count_marks(coord=[0, 0], dx=1, dy=1)
-   markpats.append(count)
+   markpats.append(self.count_marks(coord=[0, 0], dx=1, dy=1))
    # 右上から左下方向の判定
-   count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
-   markpats.append(count)
+   markpats.append(self.count_marks(coord=[2, 0], dx=-1, dy=1))
    
    return markpats

Marubatsu.enum_markpats = enum_markpats

enum_markpats の実装の確認

下記のプログラムは、いくつかの局面 に対して、enum_markpats メソッドを呼び出し て 計算 した、マークのパターン を 列挙 した データを表示 しています。なお、分かりやすく表示 するために、表示 には以前の記事で紹介した pprint を利用します。

実行結果 から、それぞれの局面 に対して、enum_markpats が、8 種類 ある 直線上の 3 マス の マークのパターン を 要素 とする list を返す ことが 確認 できます。

from pprint import pprint
mb = Marubatsu()

print(mb)
pprint(mb.enum_markpats())

mb.move(1, 1)
print(mb)
pprint(mb.enum_markpats())

mb.move(0, 0)
print(mb)
pprint(mb.enum_markpats())

mb.move(1, 0)
print(mb)
pprint(mb.enum_markpats())

実行結果

Turn o
...
...
...

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

[defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
Turn o
X..
.o.
...

[defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
Turn x
xO.
.o.
...

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

dict と defaultdict の比較

list など の、シーケンス型 の 要素の中 に 特定の値 の要素が 存在するか どうかは、in 演算子 を使って 判定 することが できます。また、in 演算子 は、== 演算子 を使って、同じ値であるか どうかを 判定 します。enum_markpats は、defaultdict を 要素 とする list を返す ので、defaultdict に対する == 演算子 の 処理 について説明します。

dict 動詞の比較

まず、dict どうし を == 演算子 で 比較 した場合の 処理 について説明します。

dict どうし を == 演算子 で 比較 した場合は、同一 の キー と キーの値 の 組み合わせ を持つ場合のみ 計算結果 が True になります。以下にいくつかの 具体例 を示します。

  • a と b は 同一 の キーとキーの値 の 組み合わせ を持つので、True になる
  • a と c は 異なる の キーとキーの値 の 組み合わせ を持つので、False になる
  • a と d は、一部の キーとキーの値 が異なるので False になる
  • a と e のように、両方に存在 する キーとキーの値 の 組み合わせ が同じだが、一部の キー が 片方 の dict にしか存在しない 場合は False になる
  • a と f のように、キー の 記述の順番 が 異なっていても、同一 の キーとキーの値 の 組み合わせ を持つ場合は True になる
a = {"x": 1, "y": 2}
b = {"x": 1, "y": 2}
c = {"z": 1}
d = {"x": 1, "y": 3}
e = {"x": 1}
f = {"y": 2, "x": 1}

print(a == b)
print(a == c)
print(a == d)
print(a == e)
print(a == f)

実行結果

True
False
False
False
True

defaultdict どうしの比較

defaultdict どうし の 比較 は、dict どうし の 比較 と 同じ なので説明は省略します。

dict と defaultdict の比較

dict と defaultdict の 比較 も dict どうし の 比較 と 同様 で、下記のプログラムのように、同一 の キーとキーの値 の 組み合わせ を持つ場合は True になります。

from collections import defaultdict

a = {"x": 1, "y": 2}
b = defaultdict(int)
b["x"] = 1
b["y"] = 2
print(a == b)

実行結果

True

従って、enum_markpats の 要素の中 に、「自 2 敵 0 空 1」が存在するかどうかは、下記のプログラムのように、「自 2 敵 0 空 1」を表す {Marubatsu.CIRCLE: 2, Marubatsu.CROSS: 0, Marubatsu.EMPTY: 1 } が 存在するか どうかで 判定できるはず と 考える人が多い かもしれません、実行 すると False が 表示 されてしまいます。

実行結果 に表示される markpats の 要素の中 には、確かに「自 2 敵 0 空 1」を表す defaultdict(<class 'int'>, {'o': 2, '.': 1}) が 表示されている のに、False になる のは 理由があります。その理由について説明します。

print(mb)
markpats = mb.enum_markpats()
pprint(markpats)
print({Marubatsu.CIRCLE: 2, Marubatsu.CROSS: 0, Marubatsu.EMPTY: 1} in markpats)

実行結果

Turn x
xO.
.o.
...

[defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'o': 2, '.': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
False

dict と defaultdict の比較の際の注意点

勘違いしやすい 点として、下記の場合 は、True にならない 点に 注意が必要 です。

  • dict に、比較する defaultdict の 規定値 が 代入 されている キーが存在 する
  • 比較する defaultdict は、その キー を 一度も参照していない

具体例を挙げて説明します。下記のプログラムは、a に "x" というキーの値に 1 を、"y" というキーの値に b の規定値 である 0 を 代入 した dict を代入します。

b の 規定値 が 0 の defaultdict には、"x" というキーの値に 1 を 代入 します。

  • 5、6 行目：a と b を 表示 すると、a では "x" と "y" の キーとキーの値 が 表示 されるが、b では、"y" という キー を 一度も参照していない ので、"x" の キーとキーの値 のみ 表示 されまる
  • 7 行目：上記のように、a と b は 同じキーとキーの値 の 組み合わせ を 持たない ので、a == b は False になる
  • 9、11 行目：a["y"] と b["y"] を比較すると、b["y"] には、既定値 である 0 が 自動的に代入 されるので、True になる。そのことは、11 行目 で 確認 できる
  • 12 行目：b には "y" という キーが存在するようになった ので、True になる
 1  a = {"x": 1, "y": 0}
 2  b = defaultdict(int)
 3  b["x"] = 1
 4
 5  print("a", a)
 6  print("b", b)
 7  print("a == b", a == b)
 8
 9  print('a["y"] == b["y"]', a ["y"] == b["y"])
10  print("a", a)
11  print("b", b)
12  print("a == b", a == b)
行番号のないプログラム 
a = {"x": 1, "y": 0}
b = defaultdict(int)
b["x"] = 1

print("a:", a)
print("b:", b)
print("a == b:", a == b)

print('a["y"] == b["y"]', a ["y"] == b["y"])
print("a:", a)
print("b:", b)
print("a == b:", a == b)

実行結果

a: {'x': 1, 'y': 0}
b: defaultdict(<class 'int'>, {'x': 1})
a == b: False
a["y"] == b["y"] True
a: {'x': 1, 'y': 0}
b: defaultdict(<class 'int'>, {'x': 1, 'y': 0})
a == b: True

先程、{Marubatsu.CIRCLE: 2, Marubatsu.CROSS: 0, Marubatsu.EMPTY: 1 } in markpats が False になったのは、markpats の defaultdict(<class 'int'>, {'o': 2, '.': 1}) という 要素 に Marubatsu.CROSS という キーが存在しない からです。

従って、enum_markpats の 要素の中 に、「自 2 敵 0 空 1」が存在するかどうかは、下記のプログラムのように、{Marubatsu.CIRCLE: 2, Marubatsu.EMPTY: 1 } が 存在するか どうかで 判定 する 必要 があり、今度は 実行結果 に True が表示 されます。

print(mb)
markpats = mb.enum_markpats()
print({ Marubatsu.CIRCLE: 2, Marubatsu.EMPTY: 1 } in markpats)

実行結果

Turn x
xO.
.o.
...

[defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'o': 2, '.': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
True

dict と defaultdict を、== 演算子 で 比較 することが できる。

ただし、dict の キーの値 が defaultdict の 規定値 であっても、defaultdict の そのキー が 一度も参照されていない 場合は、等しい と みなされい。

enum_markpats を利用した ai8s の定義

enum_markpats メソッドを 利用 することで、ルール 8 の AI を下記のプログラムのように 簡潔 に 定義できる ようになります。なお、この後で、実装した AI が 正しく動作するか どうかを 確認 するために、ai8s と対戦を行います。そこで、下記のプログラムでは、ai8s と 区別 できるように、ai8s2 という 名前 で関数を 定義 しています。なお、ai8s からの修正箇所がかなり多いので、修正箇所は省略します。

  • 11 行目：enum_markpats メソッドを呼び出して、マークのパターン を 列挙 した list を 計算 し、markpats に 代入 する
  • 13、14 行目：「自 0、敵 2、空 1」の マークのパターン が 存在する 場合は、相手が勝利できる局面なので、-1 を 評価値 として 返す
  • 16、17 行目：「自 2、敵 0、空 1」の マークのパターン が 存在する 場合は、次 の 自分の手番 で 自分 が 勝利できる 局面なので、1 を 評価値 として 返す
  • 20 行目：すべての条件 を 満たさない 場合は、0 を 評価値 として 返す 
 1  def ai8s2(mb, debug=False):
 2     def eval_func(mb):
 3         # 真ん中のマスに着手している場合は、評価値として 2 を返す
 4         if mb.last_move == (1, 1):
 5             return 3
 6   
 7         # 自分が勝利している場合は、評価値として 1 を返す
 8         if mb.status == mb.last_turn:
 9             return 2
10
11         markpats = mb.enum_markpats()
12         # 相手が勝利できる場合は評価値として -1 を返す
13         if {mb.turn: 2, Marubatsu.EMPTY: 1} in markpats:
14             return -1
15         # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
16         elif {mb.last_turn: 2, Marubatsu.EMPTY: 1} in markpats:
17             return 1
18         # それ以外の場合は評価値として 0 を返す
19         else:
20             return 0
21
22     return ai_by_score(mb, eval_func, debug=debug)
行番号のないプログラム 
def ai8s2(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 2 を返す
        if mb.last_move == (1, 1):
            return 3
    
        # 自分が勝利している場合は、評価値として 1 を返す
        if mb.status == mb.last_turn:
            return 2

        markpats = mb.enum_markpats()
        # 相手が勝利できる場合は評価値として -1 を返す
        if {mb.turn: 2, Marubatsu.EMPTY: 1} in markpats:
            return -1
        # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
        elif {mb.last_turn: 2, Marubatsu.EMPTY: 1} in markpats:
            return 1
        # それ以外の場合は評価値として 0 を返す
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

動作の確認

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

ai_match(ai=[ai8s2, ai8s])

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

ai8s2 VS ai8s
count     win    lose    draw
o        3339     412    6249
x         405    3389    6206
total    3744    3801   12455

ratio     win    lose    draw
o       33.4%    4.1%   62.5%
x        4.0%   33.9%   62.1%
total   18.7%   19.0%   62.3%

ai8s と ai8s2 の処理速度の比較

先程説明したように、ai8s は特定の マークのパターン が あるか どうかを 判定 する処理を 2 回 行っているので、その処理を 1 回 しか行わない ai8s2 より も処理に 時間がかかる ことが 予想 されます。そこで、実際に ai8s どうし と、ai8s2 どうし で 対戦 を行い、処理時間 を 比較 することにします。

下記の ai8s どうし の対戦は、筆者のパソコンでは 49.1 秒 かかりました。

ai_match(ai=[ai8s, ai8s])

下記の ai8s2 どうし の対戦は、筆者のパソコンでは 45.5 秒 かかりました。

ai_match(ai=[ai8s2, ai8s2])

予想に反して 処理時間 は 10% 程度 しか変わりませんでしたが、ai8s2 のほう が 処理時間 が 短い ことは 確認 できました。処理時間が 大きく変わらない理由 は、ai8s は マークのパターン が 見つかった時点 で 処理を中断 するのに対し、ai8s は 必ずすべて の マークのパターン を 計算する からです。

これで ai8s は 用済み なので、ai8s を破棄 して、ai8s2 の 名前 を ai8s に変更 します。

ルールベースの AI の性質

ルールベースの AI の作成をかなり進めてきましたので、ここで、以前の記事で説明した ルールベース の AI の 性質 について具体例を元に 説明 します。

ルール 5、6 で付け加えた「勝てる場合 に 勝つ」と「相手 が 勝利できる 着手を 行わない」という 2 つの条件 は、以前の記事で 検証 したように、その条件を満たすような着手を行うことで、AI が 絶対に強くなる ことが 保証 されています。

一方、ルール 3 の「真ん中 のマスに 優先的 に 着手 する」は、以前の記事で、有利である可能性が高い ことの 考察 は行いましたが、その条件を満たす着手がどのような場合でも 最善手である という 証明 までは 行っていません。それは、今回の ルール 8 で付け加えた 条件 でも 同様 です。例えば、一般的 にはそのルールに従うと 有利になる が、特定の局面 ではそのルールに従うと 不利になる ような 局面 が 存在するかも しれません。

そのような、厳密 に 強くなること が 保証されていない ルールで AI を 実装しても大丈夫なのか と思う人がいると思いますが、厳密 に 強くなること が 保証される ような ルールを作成 することは 不可能 な 場合が多い のが 現実 です。

そのことは、オセロ、将棋、囲碁のような、ある程度以上 複雑なゲーム を遊んだことがある人であれば、どのような局面 でも 適用できる、絶対に強い手 を 選択できるルール が ほとんど存在しない ことから理解できるのではないでしょうか。

従って、ルールベース で AI を作成 する際には、本記事でこれまでに行ったように、下記のような 試行錯誤 で AI を強くする という手法を取ります。

  1. 有効だと考えられる ルールを 考案 する
  2. そのルールを 実装した AI を 作成 する
  3. 他の AI と対戦 させた 結果 から 有効であるか どうかを 判断 する
  4. 有効であれば採用 し、そうでなければ破棄 する
  5. 可能であれば、対戦結果などから作成した ルール の性質 を 考察 することでゲームの 知識を深め、次のルール を 作成 する際の 参考 にする

ルールベース で AI を作成 する際には、以下 のような 難しさ があります。下記のうちのいくつかは、本記事で体験済です。

  • 最初は 思いついたルールで AI が どんどん強くなっていく が、次第 に AI の 強さ がほとんど 向上しなくなっていく
  • ルールの アイディアが尽きてくる と、新しいルール を 考える のが 困難になる
  • 特定のルール に のみ強い というルールを、一般的に強い ルールであると 勘違い してしまうと、強くしたつもりが 実際には弱くなる 場合がある
  • ルール の 数が多くなる と、複数のルールの間で 矛盾が生じる ようになり、ルール間の 優先順位 などの 整合性を取る ことが 困難 になる
  • ルール の 数が多くなる と、ルール を 単独で適用 すると 強くなる が、複数のルール を 組み合わせる と逆に 弱くなってしまう ような 状況が生じる

従って、最近 の AI は 人間 が ルールを考える というルールベースではなく、AI が 自動的 に ルール を 発見 する、機械学習 という手法を使ったものが主流になっています。〇×ゲームの AI を機械学習で作成する方法については、今後の記事で紹介します。

なお、〇×ゲーム は、単純 なゲームなので、ルールベース でも 最強の AI を作る ことが 可能 なので、引き続きルールベースで 〇×ゲームの AI を作成します。

今回の記事のまとめ

今回の記事では、ゲームに 勝つため に 必要な条件 を 考察 し、ルール 8 を 定義 しました。また、ルール 8 を 実装 するために、マークのパターン を 列挙 する 関数を定義 しました。

今回の記事では、マークのパターン の 列挙 を list を使って行いましたが、次回の記事では、list 以外 の方法で マークのパターン を 列挙 する 方法 について説明します。

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

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

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

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

次回の記事

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0