LoginSignup
0
0

Pythonで〇×ゲームのAIを一から作成する その46 相手の勝利を阻止するAI

Last updated at Posted at 2024-01-18

目次と前回の記事

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

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

これまでに作成した 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 は、じゃんけんで グーしか出さない AI100% 勝利 しますが、誰もそのような AI が 強いとは思わない でしょう。そのため、強い AI作成 する際には、対戦相手 として 強い AI想定 する必要があります。

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

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

78.png

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

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

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

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

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

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

ルール 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_moveslist なので、要素1 つ しかない場合でも、その 要素を参照 する場合は、インデックス指定 して、return legal_moves[0] のように 記述する必要 がある点に 注意 して下さい。

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

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

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

ルール 6 の実装方法

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

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

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

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

ルール 6 のアルゴリズム

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 手順 1、2 で、上図の 現在の局面 に対して、1 ~ 5着手 を行う
  • どのマス着手 を行っても 勝利しない ので、手順 3 へ 進む
  • 上図の 1 ~ 5着手 した 下図それぞれの局面 に対して、順番 に、下図の それぞれ の空いている 1 ~ 5×着手 を行う
  • すべての局面どのマス着手 を行っても ×勝利しない ので 手順 3 が終了 する
  • 手順 4 が実行され、現在の局面1 ~ 5 の中から ランダムなマス採用 する

ai6 の実装

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

  1. 現在の局面合法手の一覧 から 順番合法手取り出し着手 を行う
  2. 自分が勝利 する 合法手 があれば、それを採用 して 終了 する
  3. 上記の 手順 1着手 を行った それぞれの局面 に対して、下記の処理 を行う
    1. 合法手の一覧 から 順番合法手取り出し着手 を行う
    2. 相手が勝利 する 合法手 があれば、それを採用 して 終了 する
  4. 上記の 手順 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_origmb
    • legal_movesnext_legal_moves
    • movenext_move
    • mbnext_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 は、deepcopymove メソッドを 何度も実行 する必要があるので、処理時間 がかかります。そのため、筆者のパソコンでは処理に 約 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 のプログラムを 見比べて、どこが間違っているかについて考えてみて下さい。

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

バグの原因

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

  1. 現在の局面合法手の一覧 から 順番合法手取り出し着手 を行う
  2. 自分が勝利 する 合法手 があれば、それを採用 して 終了 する
  3. 上記の 手順 1着手 を行った それぞれの局面 に対して、下記の処理 を行う
    1. 合法手の一覧 から 順番合法手取り出し着手 を行う
    2. 相手が勝利 する 合法手 があれば、それを採用 して 終了 する
  4. 上記の 手順 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)

修正後の ai6ai2 の対戦

修正後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 行目計算 した mblist記録 しておくことで、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. 現在の局面合法手の一覧 から 順番合法手取り出し着手 を行う
  2. 自分が勝利 する 合法手 があれば、それを採用 して 終了 する
  3. 上記の 手順 1着手 を行った それぞれの局面 に対して、下記の処理 を行う
    1. 合法手の一覧 から 順番合法手取り出し着手 を行う
    2. 相手が勝利 する 合法手 があれば、それを採用 して 終了 する
  4. 上記の 手順 1繰り返しが終了 した時点で、自分が勝利 できる合法手も、相手が勝利 できる合法手も 存在しない ことが 確定 するので、ランダムな着手 を行う

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

理由はこの後で詳しく説明しますが、手順 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 マスだけ である
  • 自分と相手の 手番交互に回ってくる

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

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

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

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

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

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

具体例による説明

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

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

82.png

この局面 では、合法手 の 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)

下記は、修正後ai6ai2対戦 を行うプログラムです。実行結果修正前ほぼ同じ ですが、処理時間 は、筆者のパソコンでは 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 との対戦

他の ai3ai4ai5、と自分自身と対戦してみます。

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 を考えます。

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

この ルール 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 との対戦

ai3ai4ai5ai6自分自身対戦 してみます。

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〇を担当 した場合で、ai6ai7 に対する 成績ほぼ同じ になるが、その理由は以前の記事で説明した理由と同じである
  • ai7 VS ai6ai7 VS ai7 は、引き分け率約 50%ai6 VS ai6 より もさらに 引き分け率高い ので、やはり、〇× ゲーム は、強い AI どうし対戦 すると、引き分け可能性高くなる ゲームであるという 推測正しい可能性高く なった
  • ai7〇 を担当 した場合は ai4 に対する 勝率100% になるので、ai4 は、× を担当 する場合に 致命的な欠陥 があることが 再確認 できた

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

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

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

今回の記事の最初で、ルールの 手順順番変える と、結果変化する場合がある ので 注意 する 必要 があると説明しましたが、ルール 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 です。

次回の記事

  1. 正確には、強さが変わらない場合もあります

  2. 最大 としたのは、× が勝利 する合法手が 見つかった時点 で手順 3 の 処理が終了 するからです

  3. 合法手1 つ の場合は 1 * 0 = 0 になると思う人がいるかもしれませんが、今回の記事の最初の方で説明したように、合法手1 つ しかない場合は、ルール 6適用しません

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
0
0