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

Last updated at 2024-02-15Posted 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 を作成します。〇×ゲームがあまり強くない人は、〇×ゲームに 勝つ方法 について考えてみて下さい。また、〇×ゲームがある程度強い人は、その方法を ルール化 して下さい。

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

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

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

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

交互に 空いているマス に 自分のマーク を配置する
一度 マークが配置 されたマスは、ゲーム終了まで 変化しない
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 マス の マークのパターン を 一度調べるだけ で 同様の処理 を行うことができます。

8 種類 ある 直線上の 3 マス の マークのパターン を計算し、結果を登録する
登録した データの中 に、「自 0 敵 2 空 1」が あれば -1 を返す
登録した データの中 に、「自 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 を強くする という手法を取ります。

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

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

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

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

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

今回の記事のまとめ

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

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

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

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

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

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

次回の記事

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

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

目次と前回の記事

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

これまでに作成した AI

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

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

ルール 8 の定義

評価値の設定

ai8s の定義

ai2 と ai7s との対戦

ai8s のバグの原因

ai8s の修正方法 その 1

修正の確認

ai8s の修正方法 その 2

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

enum_markpats の実装の確認

dict と defaultdict の比較

dict 動詞の比較

defaultdict どうしの比較

dict と defaultdict の比較

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

enum_markpats を利用した ai8s の定義

動作の確認

ai8s と ai8s2 の処理速度の比較

ルールベースの AI の性質

今回の記事のまとめ

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

次回の記事

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

`ai8s` の定義

`ai2` と `ai7s` との対戦

`ai8s` のバグの原因

`ai8s` の修正方法その 1

`ai8s` の修正方法その 2

`enum_markpats` の実装の確認

`enum_markpats` を利用した `ai8s` の定義

`ai8s` と `ai8s2` の処理速度の比較