目次と前回の記事

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

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

これまでに作成した AI

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

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

基準となる 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.3	11.9	6.8	52.2	39.4	8.5	66.8	25.6	7.6

ルールその 6（相手の勝利を阻止する）

弱い AI に対してどれだけ 大幅に有利 な AI を作成 しても 強い AI を 作った ことには なりません。例えば、じゃんけん で パーしか出さない AI は、じゃんけんで グーしか出さない AI に 100% 勝利 しますが、誰もそのような AI が 強いとは思わない でしょう。そのため、強い AI を作成する際には、対戦相手 として 強い AI を想定する必要があります。

前回の記事で、自分が 勝てる時 に勝つという ルール 5 が ある場合 と ない場合 では、ある場合のほう が 強くなる¹ ことを示しました。従って、対戦相手 として 強い AI を想定する場合は、自分だけ でなく、相手も ルール 5 で着手する ことを想定する必要があります。

例えば、下図（数字のマスは 空いているマス を表します）の 〇の手番 の局面で、1 以外 のマスに着手を行うと、次の 相手の手番 で × が 1 に着手を行うと × が勝利 するので、〇が次の × の手番 で 負けない ようにするためには 必ず 1 に着手 する必要があります。

そこで、ルール 5 に、次の相手の手番 で 相手が勝つ ことが可能な着手を 行わない ルールを 加えた、下記の ルール 6 で ai6 を実装することにします。下記の 手順 2 を 別の言葉 で表現すると、「相手が 勝利するマス に 自分で着手 して邪魔をする」のようになります。

勝てるマス が存在すれば、そこに着手 する
そうでなければ、合法手 を着手した局面のうち、次の 相手の手番 で、相手が着手 すると 相手が勝利 するマスが 存在すれば 、そこに着手 して邪魔をする
上記のいずれでもなければ ランダム なマスに着手する

ルールの手順に関する注意点

上記の 手順 1 と 2 を 入れ替え ては いけない 点に注意して下さい。その理由は、勝てる場合 に 勝っておけば、相手の手番 が来ることはないからです。例えば、下図の 〇の手番 の局面で、上記の ルール 6 を適用 した場合は、2 のマスに着手して 〇の勝利 になりますが、上記の 手順 1 と 2 を 入れ替えたルール では、次の × 手番 で 1 に × が着手 すると × の勝利 になるので、1 に着手 してしまい、勝利を逃してしまう ことになります。

別の言葉で説明すると、ルール 6 の 手順 1 と 2 の 順番を入れ替えた場合 は、自分の勝ちより も、相手の勝利の邪魔 を優先することになります。

上記を 当たり前 だと思う人が いるかも しれませんが、ルールの数 が多くなったり、ルール の条件が複雑な場合は、ルール の手順の順番を 正しく決める ことが 難しく なります。個々の手順は 間違っていなくても、手順の順番 を 間違ってしまう と、間違ったルール になってしまうので、手順の順番に 注意する必要 があることを忘れないで下さい。

ルール 6 の AI が、ルール 5 の AI よりも 強くなる ことは ほぼ自明 で、簡単に検証できる ので省略します。気になる方は、ルール 5 の検証 と同様に 表を書いて検証 してみて下さい。

合法手が 1 つしかない場合の処理

ルール 6 は、相手の 勝利を阻止 することが目的ですが、合法手 が 1 つ しかない場合は、相手の手番 が 回ってこない ので、次の 相手の手番 を考慮する ルール 6 を適用することは できません。従って、ai6 の先頭に、下記のプログラムを 記述する必要 があります。

4、5 行目：組み込み関数 len を使って、legal_moves の 要素の数 を計算することで、合法手の数 を計算し、その数 が 1 の場合は、legal_moves[0] を返す

1  def ai6(mb_orig):
2      legal_moves = mb_orig.calc_legal_moves()
3      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
4      if len(legal_moves) == 1:
5          return legal_moves[0]
6      # 以下、ルール 6 の処理を記述する

合法手 が 1 つ しかない場合は、5 行目に return legal_moves を記述すれば良いと 思う人 が いるかもしれません が、legal_moves は list なので、要素が 1 つ しかない場合でも、その 要素を参照 する場合は、インデックス を指定して、return legal_moves[0] のように 記述する必要 がある点に注意して下さい。

上記の 4、5 行目 を記述することで、合法手 が 1 つ しかない場合は、ai6 は ルール 6 を 適用しない ことになります。従って、以後の ルール 6 に関する処理では、説明がなくても、合法手 が 2 つ以上ある場合 の 処理を行う と考えて下さい。

前回の記事で説明したように、合法手 が 1 つ しかない場合は、どのようなルール であっても、選択できる 合法手は同じ なので、合法手 が 1 つ しかない場合に ルール 6 を適用しても、 選択される合法手 は 常に同じ です。従って、本記事では省略しませんが、上記のプログラムの 4、5 行目 は省略することが できます。

ただし、前回の記事で説明したように、プログラムを修正 する際などで バグの原因 に なりやすい ので、意味がわからず に省略するのは 避けたほうが良い でしょう.

ルール 6 の実装方法

相手が勝利 できるマスは、以下のような 条件のマス です。

そのマスが相手の 合法手（空いているマス）である
その マスを含む 一直線上の 3 マスのうち、2 マス に 相手のマークが配置 されている ものがある

上記の条件 を 満たすマス を探すプログラムを記述する方法は、それほど 簡単ではありません ので、今回の記事では、上記とは別 の、これまでに記述 したプログラムを うまく利用 できる、下記のような 考え方 で ルール 6 を実装することにします。なお、上記の条件 を満たすマスが あるかどうか を判定する方法については、今後の記事で紹介します。

自分の手番 で、着手することで勝利できる 合法手 を 調べる処理 は ai5 で 実装済
ということは、相手の手番 で、着手することで 相手が勝利 できる 合法手 も 同様の方法 で 調べる ことが できる

ルール 6 のアルゴリズム

ルール 6 は、下記の アルゴリズム で実装することができます。下記のアルゴリズムのうち、手順 1、2、4 は、ルール 5 の アルゴリズム と同じです。異なる のは、手順 3 ですが、手順 1、2 と、手順 3-1、3-2 で行う 処理の内容 が、手番が 自分と相手 で 異なる ことを 除けば、まったく同じ処理 を行うことに注目して下さい。

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

わかりづらい と思った人のために、ルール 6 の アルゴリズム の 処理の実例 を紹介します。上記の説明の意味が良くわかった人はこの部分は飛ばしてもらっても構いません。

ルール 6 のアルゴリズムの処理の例 1

下図の場合の 処理の手順 を示します。図の 数字のマス は、空いているマス を表します。

手順 1、2 で、上図の 現在の局面 に対して、1 ~ 5 の順で〇の着手を行う
2 に着手 した時点で、〇が勝利 するので、2 のマスを採用して終了する

採用された 2 のマス に 〇が着手 することで、下図のように 〇が勝利 します。

ルール 6 のアルゴリズムの処理の例 2

下図の場合の 処理の手順 を示します。

手順 1、2 で、上図の 現在の局面 に対して、1 ~ 5 の順で〇の着手を行う
どのマス に着手を行っても〇は 勝利しない ので、手順 3 へ 進む
上図の 1 に着手した 下図の局面 に対して、下図の 2 ~ 5 の順で × の着手を行う。なお、図の 青いマス は、直前に着手が行われたマスを表す

どのマス に着手を行っても × は 勝利しない ので、現在の局面 の 2 に着手した 下図の局面 に対して、下図の 1、3 ~ 5 の順で × の着手を行う

1 に着手 した時点で、× が勝利 するので、1 のマスを採用して終了する

採用された 1 のマス に 〇が着手 することで、下図のように × の勝利 を阻止します。

ルール 6 のアルゴリズムの処理の例 3

下図の場合の 処理の手順 を示します。

手順 1、2 で、上図の 現在の局面 に対して、1 ~ 5 の順で〇の着手を行う
どのマス に着手を行っても〇は 勝利しない ので、手順 3 へ 進む
上図の 1 ~ 5 に着手した下図の それぞれの局面 に対して、順番に、下図の それぞれ の空いている 1 ~ 5 の順で × の着手を行う

すべての局面 で どのマス に着手を行っても × は 勝利しない ので 手順 3 が終了 する
手順 4 が実行され、現在の局面 の 1 ~ 5 の中から ランダムなマス を採用する

`ai6` の実装

下記は、先程のアルゴリズムを再掲したものです。

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

先ほど説明したように、手順 1、2 と、手順 3-1、3-2 で行う 処理の内容 は、手番が 自分と相手 で 異なる ことを 除けば、まったく同じ処理 を行うので、 ai6 は、下記のプログラムのように実装することができます。

6 ~ 15 行目：上記の 手順 1、2 の処理を行う部分で、この部分は、合法手 が 1 つ しかない場合の 8、9 行目 の 処理を除けば、ai5 と同じ
18 ~ 24 行目：18 行目 のプログラムが実行されるということは、元の局面 である mb_orig に対して、move に着手を行った mb の局面で、自分が 勝利していない 場合である。その場合は、手順 3-1、3-2 の処理を、6 ~ 15 行目 と 同様の方法 で行う。6 ~ 15 行目 と、18 ~ 24 行目 の違いは以下の通り
- 合法手 が 1 つ しかない場合の 処理がない
- mb_orig → mb
- legal_moves → next_legal_moves
- move → next_move
- mb → next_mb

 1 from random import choice
 2 from copy import deepcopy
 3
 4  def ai6(mb_orig):
 5      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 6      legal_moves = mb_orig.calc_legal_moves()
 7      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 8      if len(legal_moves) == 1:
 9         return legal_moves[0]
10      for move in legal_moves:
11          mb = deepcopy(mb_orig)
12          x, y = move
13          mb.move(x, y)
14          if mb.status == mb_orig.turn:
15              return move
16          # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
17          # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
18          next_legal_moves = mb.calc_legal_moves()       
19          for next_move in next_legal_moves:
20              next_mb = deepcopy(mb)                
21              x, y = next_move
22              next_mb.move(x, y)
23              if next_mb.status == mb.turn:
24                  return next_move
25        
26      return choice(legal_moves)

行番号のないプログラム

from random import choice
from copy import deepcopy
 
def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)

修正箇所

from random import choice
from copy import deepcopy

-def ai5(mb_orig):
+def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
+       next_legal_moves = mb.calc_legal_moves()       
+       for next_move in next_legal_moves:
+           next_mb = deepcopy(mb)                
+           x, y = next_move
+           next_mb.move(x, y)
+           if next_mb.status == mb.turn:
+               return next_move
        
    return choice(legal_moves)

6 ~ 15 行目 と、18 ~ 24 行目 の処理は よく似ている ので、これまでのプログラムで行ってきたように、for 文 による 繰り返し処理 で まとめる ことができるように 思えるかもしれません が、18 ~ 24 行目 の処理は、6 行目の for 文の中 に 入れ子で記述 されているため、この 2 つの処理 を for 文 による 繰り返し処理 でうまく まとめる ことは 困難です。このような場合は、再起呼び出し という方法を使って まとめる ことが できます が、その方法については今後の記事で紹介します。

本当は、前回の記事のように、mb.play(ai=[ai6, ai2]) を実行して ai2 と対戦した 結果を表示 することで、ai6 を 正しく実装できているか どうかを 確認すべき なのですが、ルール が 複雑になる と、ランダムな着手 を行う ai2 と 対戦しても、なかなか ルール を 正しく実装できたこと を 確認できる局面 が 訪れない可能性が高く なります。そのような場合は、mb.play(ai=[ai6, None]) や、mb.play(ai=[None, ai6]) を実行して、自分で ルール を 正しく実装できているか どうかを 確認できる ような 局面に誘導 して 確認する と良いでしょう。本記事では確認作業を省略しますが、気になる方 は 実際に確認 して下さい。

他の方法 として、実装した AI と 他の AI で 複数回対戦 し、意図通り の成績になることを 確認する ことで、正しく実装 できていると 推測する という方法もあります。ルール が複雑になって 確認が困難 な場合などで、この方法で 確認作業 を代用することがありますが、意図通りの成績 になっても、正しく実装 されているとは 限らない 点に 注意が必要 です。

`ai2` との対戦

ai6 が実装できたので、下記のプログラムで、基準となる ai2 と対戦します。なお、ai6 は、deepcopy や move メソッドを 何度も実行 する必要があるので、処理に時間がかかります。そのため、筆者のパソコンでは処理に 約 80 秒 の時間が かかりました。

同じプログラム でも、コンピュータの CPU の性能、メモリの量、同時に実行 している アプリケーション など、さまざまな理由 で処理にかかる時間は 異なり ます。

from ai import ai_match, ai2, ai3, ai4, ai5

ai_match(ai=[ai6, ai2])

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

ai6 VS ai2
count     win    lose    draw
o        8797     147    1056
x        6772     675    2553
total   15569     822    3609

ratio     win    lose    draw
o       88.0%    1.5%   10.6%
x       67.7%    6.8%   25.5%
total   77.8%    4.1%   18.0%

80 秒 は長いので、下記のプログラムのように、1000 回 の対戦を行ってみました。実行には 10000 回の 1/10 の 約 8 秒 かかりましたが、10000 回 の 対戦結果 と比較して ほとんど 結果は 変わらない ので 1000 回 でも 問題はない でしょう。以前の記事では 1 分で行える回数としましたが、今後は時間がかかる場合は、1000 回 で 対戦を行う ことにします。

ai_match(ai=[ai6, ai2], match_num=1000)

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

ai6 VS ai2
count     win    lose    draw
o         876      16     108
x         679      58     263
total    1555      74     371

ratio     win    lose    draw
o       87.6%    1.6%   10.8%
x       67.9%    5.8%   26.3%
total   77.8%    3.7%   18.6%

下記は、上記の結果（10000 回のほう）を表に加えたものです。

関数名	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.0	1.5	10.6	67.7	6.8	25.5	77.8	4.1	18.0

表から、ai6 は、他のどの AI より も基準となる ai2 に 対して強いことがわかります。また、〇を担当 した場合、× を担当 した場合、通算の場合の敗率は いずれも 7 % 以下 なので、相手の勝利 を阻止する ルール 6 の効果が表れていることが確認できます。

ルール 6 で負ける場合がある理由

相手の勝利 を阻止する ルール なのに、負ける場合がある 点について疑問に思った方がいるかもしれません。そのような方は、負ける場合がある 理由について少し考えてみて下さい。

具体的には、以下の 2 つの条件 を満たす局面では、ルール 6 でも 負ける ことになります。

下図のように、どのマスに着手しても自分が 勝つことができない
下図の 黄色のマス のように、次の手番で 相手が勝利できる マスが 2 つ以上 ある

下図では、片方のマス しか邪魔を できない ので、相手の勝利 を 阻止できません。

なお、上記のような局面になってしまった場合は、ルール 6 に限らず、どのようなルール を使っても 相手の勝利 を阻止することは 不可能 です。

`ai6` のバグの修正

プログラミングに 慣れている方 は既に 気がづいているかも しれませんが、実は ai6 には、ルール 6 を 正しく実装できていない というバグがあります。正直に言うと、筆者は、最初は 正しいつもり で上記の ai6 を実装し、後からバグ がある事に 気が付きました。ルール 6 と、ai6 のプログラムを 見比べて、どこが間違っているかについて考えてみて下さい。

なお、上記で バグのある ai6 で ai2 と 対戦を行った のは、バグを修正 することで、ai6 VS ai2 の成績が 向上する ことを 示したい からです。

バグの原因

下記は、先程のアルゴリズムを再掲したものです。

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

バグの原因は、ai6 が、手順 2 を 正しく実装していない 点にあります。

上記の 手順 2 の「自分が勝利 する 合法手 があれば、それを採用 して終了する」は、合法手 を すべて調べた結果 の事を表しています。従って、手順 3 は、手順 1、2 の処理が完了した後で行う必要があります。しかし、ai6 では、合法手 を すべて調べた後ではなく、合法手を 一つ調べるたび に、手順 3 の処理 を行っています。

この違い が どのように影響 するかを、下図の局面 で説明します。

ルール 6 のアルゴリズムの処理を正しく行った場合

手順 1、2 で、上図の 最初の局面 に対して、1 ~ 5 の順で〇の着手を行う
4 に着手 した時点で、〇が勝利 するので、4 のマスを採用して終了する

採用された 4 のマス に 〇が着手 することで、下図のように 〇が勝利 します。

ルール 6 のアルゴリズムを間違って実装した `ai6` の場合

手順 1、2 で、上図の 最初の局面 に対して、1 ~ 5 の順で〇の着手を行う
1 に着手した場合、下図のように、〇は 勝利していない。ai6 は 手順 1、2 の処理が すべて終了する前 に、下図の局面 で、手順 3 の処理を行う（この処理が間違い）

上図で、3 に着手 した時点で、× が勝利 するので、3 のマスを採用して終了する

採用された 3 のマス に 〇が着手 することで、下図のように × の勝利 を阻止します。

上記のように、間違った処理 を行う ai6 は、〇の勝利 を逃す結果になります。

`ai6` のバグの内容

上記から、ai6 のバグを 言葉で表現 すると、以下のようになります。

以下の 2 つの条件 が 同時に満たされる局面 で、自分が勝利せず に 相手の勝利を阻止 してしまう 場合がある

自分の着手 で 自分が勝利 できる 合法手 がある
いずれか の 自分の着手 の後の 相手の着手 で、相手が勝利 できる 合法手 がある

`ai6` の修正

バグの原因は、手順 1、2 の処理を すべて行う前 に 手順 3 を行う ことにあります。そこで、手順 1、2 の処理を 先に行ってから、手順 3 の 処理を行う ようにすることで、ai6 の バグを修正 することができます。また、手順 3 の処理は、自分が勝利 する 合法手 が 存在しない 場合に 行う処理 です。従って、手順 3 は、下記のプログラムのように、修正前 の ai6 のプログラムから、手順 2 の処理を削除したプログラムで記述できます。

7 ~ 12 行目：この 繰り返し処理 の中で、手順 1、2 の処理 のみを行う ように修正する
14 ~ 26 行目：元の ai6 の 繰り返し処理 の中から、手順 2 の「自分が勝利 する 合法手 があれば、それを採用 して終了する」処理を削除したプログラムを記述する

14 ~ 26 行目 のプログラムが、修正前 の ai6 のプログラムから、手順 2 の処理を行う、下記の 11、12 行目 のプログラムを削除したものと同じであることを確認して下さい。

 1  def ai6(mb_orig):
 2      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 3      legal_moves = mb_orig.calc_legal_moves()
 4      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 5      if len(legal_moves) == 1:
 6          return legal_moves[0]
 7      for move in legal_moves:
 8          mb = deepcopy(mb_orig)
 9          x, y = move
10          mb.move(x, y)
11          if mb.status == mb_orig.turn:
12              return move
13      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
14      for move in legal_moves:
15          mb = deepcopy(mb_orig)
16          x, y = move
17          mb.move(x, y)
18          # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
19          # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
20          next_legal_moves = mb.calc_legal_moves()       
21          for next_move in next_legal_moves:
22              next_mb = deepcopy(mb)                
23              x, y = next_move
24              next_mb.move(x, y)
25              if next_mb.status == mb.turn:
26                  return next_move
27        
28      return choice(legal_moves)

行番号のないプログラム

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)

修正箇所

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
+   for move in legal_moves:
+       mb = deepcopy(mb_orig)
+       x, y = move
+       mb.move(x, y)
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)

修正後の `ai6` と `ai2` の対戦

修正後 の ai6 で、ai2 と改めて対戦を行うことにします。

ai_match(ai=[ai6, ai2], match_num=1000)

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

ai6 VS ai2
count     win    lose    draw
o         889      22      89
x         703      62     235
total    1592      84     324

ratio     win    lose    draw
o       88.9%    2.2%    8.9%
x       70.3%    6.2%   23.5%
total   79.6%    4.2%   16.2%

下記は、修正前 と 修正後 の ai6 と、ai2 で対戦した場合の成績を表にしたものです。

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分	欠陥
`ai6` 前	88.0	1.5	10.6	67.7	6.8	25.5	77.8	4.1	18.0	あり
`ai6` 後	88.9	2.2	8.9	70.3	6.2	23.5	79.6	4.2	16.2

表から、バグを修正 した結果、すべての場合で勝率が 2% 程 することがわかります。

なお、成績が ほんの少し しか向上しない理由の検証は省略しますが、おそらくバグが 勝敗に影響 するような局面が ほとんど出現しない からだと思います。興味と余裕がある方は、実際に検証してみて下さい。

`ai6` の改良その 1（重複する処理を省く）

下記は、先程修正した ai6 の一部を抜粋したプログラムです。よく見ると、2 ~ 5 行目 と、9 ~ 12 行目 で 全く同じ処理 が記述されているため、同じ処理 を 2 度行う という無駄が生じています。また、その部分で行われる deepcopy による データの深いコピー や、move メソッドで 勝敗判定 を行う処理は、それなりに 時間がかかる ので、そのような処理を 2 回 も行うことで、プログラムの処理に、余計な時間 がかかってしまいます。

実際に 筆者のパソコン で ai_match(ai=[ai6, ai6], match_num=1000) を実行すると、同じ処理 を 2 回行わない がバグのある 修正前 では 8.4 秒、修正後 では 9.4 秒 かかりました。

 1  def ai6(mb_orig):
略
 2      for move in legal_moves:
 3          mb = deepcopy(mb_orig)
 4          x, y = move
 5          mb.move(x, y)
 6          if mb.status == mb_orig.turn:
 7              return move
 8      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
 9      for move in legal_moves:
10          mb = deepcopy(mb_orig)
11          x, y = move
12          mb.move(x, y)
略

改良の方法

上記のプログラムの 2 行目 の 繰り返し処理 と、9 行目 の 繰り返し処理 には、同一の for move in legal_moves: という記述が行われています。また、2 ~ 7 行目 の処理を実行しても繰り返し処理の 反復可能オブジェクト に記述されている legal_moves の値は 変化しない ので、2 行目 と 9 行目 の 繰り返し処理 では、どちらも 同じ値 が順番に legal_moves から 取り出され て move に代入 されます。

それぞれ の for 文 の ブロック の 3 ~ 5 行目 と、10 ~ 12 行目 では 同一の処理 が行われるので、2 行目 の for 文 の ブロック の 5 行目 の処理で計算される mb の値 と、9 行目 の for 文 の ブロック の 12 行目 の処理で計算される mb の値 は、move に代入された値が 同じであれば、必ず 同じ内容 になります。

上記から、2 行目 の for 文 の n 回目 の繰り返し処理の 5 行目 で計算される mb と、9 行目 の for 文 の n 回目 の繰り返し処理の 12 行目 で計算される mb の値は、同じ内容 になります。従って、5 行目 で計算した mb を list に記録しておくことで、10 ~ 12 行目 の処理を行う代わりに、記録した list から 対応するデータ を 取り出して利用 することができます。

別の言葉で説明すると、手順 3 で 必要となる、「現在の局面 に対して それぞれ の 合法手 を着手した局面」は、手順 1、2 の処理を行う際に、計算する ので、その時 にそれらの局面を list に記録 しておき、手順 3 で 再利用できる ということです。

改良版の `ai6` の実装

下記は、そのような処理を行うように ai6 を改良したプログラムです。

7 行目：8 行目 の for 文 の 繰り返し処理 の中の 11 行目 で計算した mb を記録するための list を代入する mb_list を、空の list で 初期化 する
12 行目：mb_list の要素に mb を追加 して記録する
16 行目：元の for 文の代わりに、mb_list から順番に要素を 取り出し、mb に代入するという、for 文 による 繰り返し処理 を行う。この 16 行目 の処理で、先程の 改良前 の 9 ~ 12 行目 と 同じ処理 が行われる（そのことは、下記の 修正箇所 で 確認できる）

 1  def ai6(mb_orig):
 2      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 3      legal_moves = mb_orig.calc_legal_moves()
 4      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 5      if len(legal_moves) == 1:
 6          return legal_moves[0]
 7      mb_list = []
 8      for move in legal_moves:
 9          mb = deepcopy(mb_orig)
10          x, y = move
11          mb.move(x, y)
12          mb_list.append(mb)
13          if mb.status == mb_orig.turn:
14              return move
15      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
16      for mb in mb_list:
17          # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
18          # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
19          next_legal_moves = mb.calc_legal_moves()       
20          for next_move in next_legal_moves:
21              next_mb = deepcopy(mb)                
22              x, y = next_move
23              next_mb.move(x, y)
24              if next_mb.status == mb.turn:
25                  return next_move
26        
27      return choice(legal_moves)

行番号のないプログラム

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    mb_list = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        mb_list.append(mb)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
    for mb in mb_list:
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)

修正箇所

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
+   mb_list = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
+       mb_list.append(mb)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
-   for move in legal_moves:
-       mb = deepcopy(mb_orig)
-       x, y = move
-       mb.move(x, y)
+   for mb in mb_list:
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)

下記は、改良後 に ai6 VS ai2 に対戦を行うプログラムです。実行結果 は 修正前 と ほぼ同じ ですが、処理時間 は、筆者のパソコンでは 9.4 秒 から 8.5 秒 に短縮されました。

ai_match(ai=[ai6, ai2], match_num=1000)

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

ai6 VS ai2
count     win    lose    draw
o         896      15      89
x         702      60     238
total    1598      75     327

ratio     win    lose    draw
o       89.6%    1.5%    8.9%
x       70.2%    6.0%   23.8%
total   79.9%    3.8%   16.4%

`ai6` の改良その 2（アルゴリズムの改良）

下記は ルール 6 の アルゴリズム を再掲したものです。実は、下記の アルゴリズム を、より 効率の良い ものに改良することが できます。その方法について少し考えてみて下さい。

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

上記の アルゴリズム の 手順 3 では、現在の局面 に対して、合法手 を着手した それぞれ の局面に対して、相手の合法手 を すべて着手 しています。そのため、例えば 現在の局面 の 合法手 が n 通り だった場合、最大² で n * (n - 1) 通り³ の着手を行う必要があります。

理由はこの後で詳しく説明しますが、手順 3 は、下記のような 効率のよい アルゴリズムに 置き換える ことができます。

3. 現在の局面 を 相手の手番 と みなす
　　1. 現在の局面 の 合法手の一覧 から順番に 合法手 を 取り出し て着手を行う
　　2. 相手が勝利 する 合法手 があれば、それを採用 して終了する

このアルゴリズムであれば、例えば 現在の局面 の 合法手 が n 通り だった場合、最大で n 通り しか着手を行う 必要がなくなる ので、処理の時間 を短縮することができます。

下記の表は 合法手の数 と、それぞれのアルゴリズムで必要となる 着手の数 の 最大値 です。表から、合法手 の数が 多いほど、必要な着手の 最大値 を 大幅に減らす ことができることが分かります。また、〇× ゲーム は、最初の 合法手 の数が 9 で、1 手ごと に合法手の数が 1 ずつ減る ので、表の合計を計算することで 1 試合当たり で必要となる 着手の計算回数 の 最大値 を 見積もる ことができます。表から 改良版のアルゴリズム では、合計が 約 1/5 になるので、かなりの 計算時間 の削減を期待できるでしょう。

合法手の数	2	3	4	5	6	7	8	9	合計
元のアルゴリズム	2	6	12	20	30	42	56	72	240
改良版のアルゴリズム	2	3	4	5	6	7	8	9	44

上記は概算に すぎない ので、正確ではない 点に注意して下さい。例えば、上記の計算では、ゲームが 8 手以内 で決着する場合を 考慮していません。

上記のアルゴリズムが 正しい理由 について少し考えてみて下さい。

改良版のアルゴリズムが正しい理由

〇× ゲーム は 下記の性質 があるゲームです。

一度 マークを配置したマス は、その 内容が変更される ことは 決してない
一度の手番で自分の マークを配置できるマス は 1 マスだけ である
自分と相手の手番は 交互に回ってくる

上記の性質 から、自分の手番 の局面の 合法手 に、次の 相手の手番 で 相手が着手 することで 相手が勝利するか どうかは、以下の場合を除いて変化 することは ありません。

自分の着手 で 自分が勝利 する（相手の手番 が 回ってこない）
自分がそのマスに 着手する（相手がそのマスに 着手できない）

例えば、下図の局面で、〇が 2 に着手 すると 〇が勝利 し、1 に着手 すると次の 相手の × の手番 で × は 1 に着手できません が、それ以外 の どの合法手 に 〇が着手 しても、1 に × が着手 して × が勝利 します。

手順 3 の処理を実行するということは、現在の局面 で〇がどの 合法手に着手 しても 勝利できない ことが確定したということなので、上記の 条件 1 が 満たされる ことは ありません。また、手順 3 の意図は、相手がそのマスに着手することで、相手が勝利するか どうかを 調べる ことなので、上記の 条件 2 は考慮に入れる必要は ありません。

従って、改良前 の 手順 3 の処理を行う際に、自分は上記の 条件 1、2 以外 の合法手に 着手した局面 で、相手が 勝利できるか どうかを判定しますが、先ほど説明したように、条件 1、2 以外 のマスに着手を行った場合は、相手の着手 による勝利に影響を 与えません。

改良前 の 手順 3 で、自分の着手 が、相手の着手 による勝利に 影響を与えない ということは、自分が 着手しない場合 でも 相手の勝利 に 影響を与えない ということなので、手順 3 で、現在の局面 を 相手の手番 と考えても 相手の勝利 を 調べる ことが できます。以上が、改良した アルゴリズム 3 によって、ルール 6 の処理を行うことができる理由です。

具体例による説明

言葉の説明だけでは わかりづらい と思いますので、具体例 を挙げて説明します。

下図の局面 で、次の 相手の × の手番 で、相手が 1 に着手した場合に、× が勝利するか どうかを判定することを考えてみて下さい。

この局面 では、〇は 合法手 の 1 ~ 5 のどのマスに着手しても 勝利できず、手順 1、2 で処理が終了することはないので、手順 3 の処理が 行われます。

手順 3 では、上図の局面 で、1 ~ 5 の それぞれ のマスに 〇が着手 を行った下図の それぞれの局面 で、× が勝利 できる 合法手 が あるかどうか を調べます。

次に、手順 3 で × が 1 のマスに着手して 勝利できるか どうかを どのように判定 しているかを考えてみて下さい。

手順 3 では、上図の 2 ~ 4 の局面で、実際に 1 のマスに × が着手 を行った、下図の 2 ~ 4 の局面の状態を 調べる ことで、その判定を行います。しかし、下図からわかるように、現在の局面 で、〇が 1 以外 の 2 ~ 4 のどのマスに着手を行っても、その次の × の手番 で × が 1 に着手を行うと × が勝利します。

このようなことが起きるのは、先ほど説明した 〇× ゲームの性質 が原因です。

〇が 1 以外 のどの合法手に着手しても × の勝利 に 影響を与えない ということは、〇の着手 が、× の勝利 に 影響しない という事を意味します。従って、下図の「着手なし」のように、現在の局面 で〇が 着手を行わず に × が 1 に着手 を行っても、× が勝利 します。

上記は、× が着手 することで × が勝利 する 1 のマス についての説明ですが、着手しても × が勝利しない、2 ~ 4 のマスについても、同様の理由 で、現在の局面 で〇が 着手を行わなくても、× が勝利しない という結果に影響を与えることは ありません。気になる方は、上記のような図を書いて確認してみて下さい。

上記の事から、手順 3 の処理で、〇が 着手を行う必要がない、すなわち、現在の局面 を 相手の手番 の局面と みなして 処理を行っても良いことがわかります。

改良版のアルゴリズムを使った `ai6` の実装

下記のプログラムは、改良版 のアルゴリズムで ai6 を実装したプログラムです。

mb_list に関する処理は 必要が無くなった ので削除した
16 行目：legal_moves に対する 繰り返し処理 を行うように修正する
18 行目：mb の手番を 入れ替える
19 行目：入れ替えた手番 を enemy_turn に代入して とっておく
20、21 行目：相手の手番 で 合法手 に着手を行う
22、23 行目：相手が勝利 していた場合は、その 合法手 を 返り値 として返す

なお、元のプログラム では、相手の手番 の局面を表す mb を コピー した mb_next に対して着手を行っていたので、22 行目では 相手の手番 を mb.turn のように記述できました。一方、改良版 では mb に対して着手を行うので、mb.turn は 自分の手番 になります。そのため、19 行目 で 相手の手番 を enemy_turn に代入して記録しておく必要があります。

 1  from marubatsu import Marubatsu
 2 
 3  def ai6(mb_orig):
 4      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 5      legal_moves = mb_orig.calc_legal_moves()
 6      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 7      if len(legal_moves) == 1:
 8          return legal_moves[0]
 9      for move in legal_moves:
10          mb = deepcopy(mb_orig)
11          x, y = move
12          mb.move(x, y)
13          if mb.status == mb_orig.turn:
14              return move
15      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
16      for move in legal_moves:
17          mb = deepcopy(mb_orig)
18          mb.turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
19          enemy_turn = mb.turn
20          x, y = move
21          mb.move(x, y)
22          if mb.status == enemy_turn:
23              return move
24       
25      return choice(legal_moves)

行番号のないプログラム

from marubatsu import Marubatsu

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        mb.turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
        enemy_turn = mb.turn
        x, y = move
        mb.move(x, y)
        if mb.status == enemy_turn:
            return move
       
    return choice(legal_moves)

修正箇所

from marubatsu import Marubatsu

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
-   mb_list = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
-       mb_list.append(mb)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
-   for mb in mb_list:
+   for move in legal_moves:
-       # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
-       # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
-       next_legal_moves = mb.calc_legal_moves()       
-       for next_move in next_legal_moves:
-           next_mb = deepcopy(mb)                
-           x, y = next_move
-           next_mb.move(x, y)
-           if next_mb.status == mb.turn:
-               return next_move
+       mb = deepcopy(mb_orig)
+       mb.turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
+       enemy_turn = mb.turn
+       x, y = move
+       mb.move(x, y)
+       if mb.status == enemy_turn:
+           return move
       
    return choice(legal_moves)

下記は、修正後 の ai6 と ai2 で対戦を行うプログラムです。実行結果 は 修正前 と ほぼ同じ ですが、処理時間 は、筆者のパソコンでは 8.5 秒 から 2.8 秒 に、大幅に短縮 されました。これは、約 1/3 の短縮なので、先程の概算の 1/5 ほどは 短縮されていません が、実際に アルゴリズムの改良 によって 処理時間 を かなり短縮 できることが確認できました。

このように、同じ処理 を行う場合でも、アルゴリズム によって、処理の速度 が 大きく変わる 場合があります。ただし、初心者の方が、今回の記事で紹介したようなアルゴリズムを自分で考えるのは難しいでしょう。自分で 効率の良いアルゴリズム を 考える ためには、さまざまなアルゴリズム を体験して勉強する必要があります。本記事でさまざなアルゴリズムを紹介しているのはそのためです。

実行時間が短縮されたので、以後は 10000 回 の 対戦を行う ことにします。

ai_match(ai=[ai6, ai2], match_num=1000)

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

ai6 VS ai2
count     win    lose    draw
o         896      17      87
x         692      56     252
total    1588      73     339

ratio     win    lose    draw
o       89.6%    1.7%    8.7%
x       69.2%    5.6%   25.2%
total   79.4%    3.6%   17.0%

他の AI との対戦

他の ai3、ai4、ai5、と自分自身と対戦してみます。

ai_match(ai=[ai6, ai3])

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

ai6 VS ai3
count     win    lose    draw
o        8685     147    1168
x        6193     577    3230
total   14878     724    4398

ratio     win    lose    draw
o       86.9%    1.5%   11.7%
x       61.9%    5.8%   32.3%
total   74.4%    3.6%   22.0%

ai_match(ai=[ai6, ai4])

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

ai6 VS ai4
count     win    lose    draw
o        9240     373     387
x        6615    2903     482
total   15855    3276     869

ratio     win    lose    draw
o       92.4%    3.7%    3.9%
x       66.1%   29.0%    4.8%
total   79.3%   16.4%    4.3%

ai_match(ai=[ai6, ai5])

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

ai6 VS ai5
count     win    lose    draw
o        8878     228     894
x        6549    1372    2079
total   15427    1600    2973

ratio     win    lose    draw
o       88.8%    2.3%    8.9%
x       65.5%   13.7%   20.8%
total   77.1%    8.0%   14.9%

ai_match(ai=[ai6, ai6])

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

ai6 VS ai6
count     win    lose    draw
o        3091    1693    5216
x        1765    3127    5108
total    4856    4820   10324

ratio     win    lose    draw
o       30.9%   16.9%   52.2%
x       17.6%   31.3%   51.1%
total   24.3%   24.1%   51.6%

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

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分
`ai6` VS `ai2`	88.9	2.2	8.9	70.3	6.2	23.5	79.6	4.2	16.2
`ai6` VS `ai3`	86.9	1.5	11.7	61.9	5.8	32.3	74.4	3.6	22.0
`ai6` VS `ai4`	92.4	3.7	3.9	66.1	29.0	4.8	79.3	16.4	4.3
`ai6` VS `ai5`	88.8	2.3	8.9	65.5	13.7	20.8	77.1	8.0	14.9
`ai6` VS `ai6`	30.9	16.9	52.2	17.6	31.3	51.1	24.3	24.1	51.6

上記の結果 から、以下のような考察を行いました。

ai6 は、これまでに作成 した すべての AI に対して 大きく勝ち越す ので、ルール 6 の効果が 非常に大きい ことが確認できる
ai4 に対して、勝率が高い ので、ai4 には 欠陥がありそう であることが 再確認 できる
ai6 の 通算の勝率 は、相手が ai5 のほうが ai3 より高い ので、ai6 を基準 とした強さは、ai3 > ai5 のように見えるかもしれないが、敗率は ai5 のほうが ai3 よりかなり大きい ので、ai6 を基準 とした強さは、ai3 < ai5 であると考察できる
自分自身 との対戦では、約 50 % で 引き分け になるので、〇× ゲーム は、強い AI どうし が対戦すると、引き分け の 可能性 が 高くなる ゲームであることが推測できる

ルールその 7（ルール3 とルール 6 の併用）

ルール 3 と ルール 6 は、完全に 異なるアプローチ のルールなので、両方のルールを併用することが できます。そこで、両方のルールを併用した下記の ルール 7 を考えます。

真ん中 のマスが 空いていれば、そこに着手 する（ルール 3）
勝てるマス が存在すれば、そこに着手 する（ルール 6）
そうでなければ、合法手 を着手した局面のうち、次の 相手の手番 で、相手が着手 すると 相手が勝利 するマスが 存在すれば 、そこに着手 して邪魔をする（ルール 6）
上記のいずれでもなければ ランダム なマスに着手する

この ルール 7 で着手を行う ai7 は、下記のように 簡単に記述 することができます。

2、3 行目：(1, 1) のマスが 空いている 場合に、(1, 1) を 返り値 として返す（ルール 3）
4 行目：ルール 6 で着手を選択する、ai6(mb) を 呼び出し 、その 返り値 を返す

def ai7(mb):
    if mb.board[1][1] == Marubatsu.EMPTY:
        return 1, 1
    return ai6(mb):

`ai2` との対戦

下記のプログラムで、基準となる ai2 との対戦を行います。

ai_match(ai=[ai7, ai2])

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

ai7 VS ai2
count     win    lose    draw
o        9578      22     400
x        8227     240    1533
total   17805     262    1933

ratio     win    lose    draw
o       95.8%    0.2%    4.0%
x       82.3%    2.4%   15.3%
total   89.0%    1.3%    9.7%

下記は、上記の結果を表に加えたものです。

関数名	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

表から、ai7 の成績は、ai6 よりも 大幅に向上 することがわかります。従って、ルール 3 と ルール 6 を併用することが 有効である ことがわかりました。

他の AI との対戦

ai3、ai4、ai5、ai6 と 自分自身 と対戦してみます。

ai_match(ai=[ai7, ai3])

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

ai7 VS ai3
count     win    lose    draw
o        9580      19     401
x        6130     582    3288
total   15710     601    3689

ratio     win    lose    draw
o       95.8%    0.2%    4.0%
x       61.3%    5.8%   32.9%
total   78.5%    3.0%   18.4%

ai_match(ai=[ai7, ai4])

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

ai7 VS ai4
count     win    lose    draw
o       10000       0       0
x        6581    2934     485
total   16581    2934     485

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x       65.8%   29.3%    4.9%
total   82.9%   14.7%    2.4%

ai_match(ai=[ai7, ai5])

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

ai7 VS ai5
count     win    lose    draw
o        9540      36     424
x        8109     543    1348
total   17649     579    1772

ratio     win    lose    draw
o       95.4%    0.4%    4.2%
x       81.1%    5.4%   13.5%
total   88.2%    2.9%    8.9%

ai_match(ai=[ai7, ai6])

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

ai7 VS ai6
count     win    lose    draw
o        3024     431    6545
x         706    1556    7738
total    3730    1987   14283

ratio     win    lose    draw
o       30.2%    4.3%   65.5%
x        7.1%   15.6%   77.4%
total   18.6%    9.9%   71.4%

ai_match(ai=[ai7, ai7])

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

ai7 VS ai7
count     win    lose    draw
o        2989     414    6597
x         397    3039    6564
total    3386    3453   13161

ratio     win    lose    draw
o       29.9%    4.1%   66.0%
x        4.0%   30.4%   65.6%
total   16.9%   17.3%   65.8%

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

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分
`ai7` VS `ai2`	95.8	0.2	4.0	82.3	2.4	15.3	89.0	1.3	9.7
`ai7` VS `ai3`	95.8	0.2	4.0	61.3	5.8	32.9	78.5	3.0	18.4
`ai7` VS `ai4`	100.0	0.0	0.0	65.8	29.3	4.9	82.9	14.7	2.4
`ai7` VS `ai5`	95.4	0.4	4.2	81.1	5.4	13.5	88.2	2.9	8.9
`ai7` VS `ai6`	30.2	4.3	65.5	7.1	15.6	77.4	18.6	9.9	71.4
`ai7` VS `ai7`	29.9	4.1	66.0	4.0	30.4	65.6	16.9	17.3	65.8

上記の結果 から、以下のような考察を行いました。

ai7 は、ai5 以前 の AI に 対して は 圧倒的な強さ を持つため、ルール 6 は 強い AI を作成する際に 非常に重要 である 可能性 が高い
ai7 は、ai6 に対して通算の勝率が 敗率より高い ので、真ん中 のマスに 優先的に着手 することが有効であることが確認できる
ai7 が 〇を担当 した場合で、ai6 と ai7 に対する成績が ほぼ同じ になるが、その理由は以前の記事で説明した理由と同じである
ai7 VS ai6 や ai7 VS ai7 は、引き分け率 が 約 50% の ai6 VS ai6 より もさらに 引き分け率 が高いので、やはり、〇× ゲーム は、強い AI どうし が対戦すると、引き分け の 可能性 が 高くなる ゲームであるという推測が 正しい可能性 が高くなった
ai7 が 〇を担当 した場合は ai4 に対する勝率が 100% になるので、ai4 は、× を担当 する場合に 致命的な欠陥 があることが 再確認 できた

ルール 3 とルール 6 の順番

先程の ルール 7 では、ルール 3 を 適用した後 で ルール 6 を適用していますが、下記のように、その 順番を逆 にしたルールも考えられます。

勝てるマス が存在すれば、そこに着手 する（ルール 6）
そうでなければ、合法手 を着手した局面のうち、次の 相手の手番 で、相手が着手 すると 相手が勝利 するマスが 存在すれば 、そこに着手 して邪魔をする（ルール 6）
真ん中 のマスが 空いていれば、そこに着手 する（ルール 3）
上記のいずれでもなければ ランダム なマスに着手する

今回の記事の最初で、ルールの手順の順番を 変える と、結果が 変化する場合がある ので注意する必要があると説明しましたが、ルール 7 の場合は、ルール 3 と ルール 6 を適用する順番を 変えても、結果は 変化しません。その理由について考えてみて下さい。

ルール 3 によって着手が行われる条件

ルール 3 によって着手が行われる条件は、真ん中のマス が 空いている ことです。従って、真ん中 のマスが 空いていない場合 は、ルール 3 によって着手は 行われません。

ルール 6 によって着手が行われる条件

ルール 6 によって着手が行われる条件は、次の 自分の着手 で 自分が勝利できる か、次の 相手の着手 で 相手が勝利できる 場合です。

〇× ゲーム では、自分のマーク を 3 つ並べる ことで 勝利する ので、〇も × も、1、2 回目 の着手で勝利することは あり得ません。従って、〇と × の 1 回目 の着手で、ルール 6 が適用されることは ありません。

〇の 1 回目の着手の場合

上記から、〇の 1 回目 の着手で、ルール 6 が適用されることは ありません。従って、ルール 3 と ルール 6 を適用する順番は、〇の 1 回目 の着手に影響を 与えません。

〇の 1 回目 の着手では、真ん中 のマスは 必ず空いている ので、ルール 3 が適用されて 真ん中 のマスに着手が行われます。

× の 1 回目の着手の場合

同様の理由 で、× の 1 回目 の着手で、ルール 6 が適用されることは ありません。従って、ルール 3 と ルール 6 を適用する順番は、× の 1 回目 の着手に影響を 与えません。

真ん中 のマスが 空いている 場合は ルール 3 が適用されて 真ん中 のマスに着手が行われ、空いていない場合はランダムなマスに着手が行われます。その結果 として、× の 1 回目 の 着手の後 では、必ず真ん中 のマスが 空ではなくなります。

2 回目以降の着手の場合

上記の事から、2 回目以降 の着手では、〇の場合 も、× の場合 も 真ん中 のマスが 空いていない ので、ルール 3 が適用されることは ありません。従って、ルール 3 と ルール 6 を適用する順番は、2 回目以降 の着手に影響を 与えません。

以上から、すべての場合 で、ルール 3 と ルール 6 を適用する順番は、ルール 7 の着手に影響を 与えない ことがわかります。

今回の記事のまとめ

今回は、以下の表のようなアルゴリズムの ai6 を実装しました。また、これまでに作成 した ルール 3 と ルール 6 を 組み合わせ た ai7 を実装し、その 2 つのルール を 組み合わせる ことで かなり強い AI を作成することができたことを確認しました。

まだ 最強ではありません が、ai7 は それなりに強い AI になっていると思いますので、実際に mb.play(ai=[None, ai7]) と mb.play(ai=[ai7, None]) を実行して ai7 と対戦 して、その 強さを確認 してみて下さい。

関数名	アルゴリズム
`ai6`	勝てる場合に勝つそうでない場合は相手の勝利を阻止するそうでない場合はランダムなマスに着手する
`ai7`	真ん中のマスが空いていればそこに着手するそうでない場合は、勝てる場合に勝つそうでない場合は相手の勝利を阻止するそうでない場合はランダムなマスに着手する

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

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

今回の記事では、marubatsu.py は修正していないので、marubatsu_new.py はありません。

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

次回の記事

正確には、強さが変わらない場合もあります ↩
最大としたのは、× が勝利 する合法手が 見つかった時点 で手順 3 の 処理が終了 するからです ↩
合法手 が 1 つ の場合は 1 * 0 = 0 になると思う人がいるかもしれませんが、今回の記事の最初の方で説明したように、合法手 が 1 つ しかない場合は、ルール 6 は 適用しません ↩