目次と前回の記事

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

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

これまでに作成した AI

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

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

基準となる 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	あり

ルールその 5（勝てる場合に勝つ）

ルール 3、4 は、有利だと 思われる マスに 優先的 に着手するというアプローチでしたが、ルール 5 では、別の観点 の ルール を考えてみることにします。

〇× ゲーム を 何回か遊べば すぐにわかると思いますが、自分の手番 の 合法手 の中で 勝利できる マスが存在する場合は、その マスに着手 すれば その時点で勝ち になるので、絶対にそこに 着手すべき です。しかし、ルール 3、4 では、勝てる場合 でも 別のマスに着手 する 場合がある ため、多くの場合 で 勝てる試合 を 逃して しまいます。

そこで、以下の ルール 5 で着手を行う ai5 を作成することにします。

勝てるマス が存在すれば、そこに着手 する
勝てるマス が 存在しなければ、ランダム なマスに着手する

ルール 5 の検証

この ルール 5 によって、基準となる ai2 より強くなる かどうかについて検証します。

勝てるマスが存在 する場合に、そこに 必ず着手する場合 と、ランダムに着手する場合 を比較すると、以下の表のようになります。

	結果
必ず着手する場合	100% 勝利
ランダムに着手する場合	勝利、敗北、引き分けのいずれか

表からわかるように、ランダムに着手する 場合でも 勝利する可能性 があるので、必ず着手する 場合のほうが、結果が良くなる とは 限りません が、ランダムに着手する 場合の ほうが、必ず着手する 場合より結果が 悪くなる ことはないことがわかります。

上記から、ルール 5 によって実装された ai5 と 他の AI が対戦した場合の 通算成績 は、ai2 が 同じ AI と対戦した 通算成績 と比較すると、必ず良い成績（または同等の成績）になることがわかります。従って、一般的 に ai5 のほうが、ai2 より も強いと言えます。

上記のルール の AI を実装するためには、着手することで勝利できる 合法手があるか どうかを判定する必要があります。その判定方法について少し考えてみて下さい。

着手することで勝利できる合法手を調べる方法

Marubatsu クラスは、move メソッドで着手を行った際に、ゲームが 決着したか どうかを判定して status 属性 に代入するという処理を行います。従って、着手することで勝利できる 合法手 は、実際に 合法手 を順番に着手した際の status 属性 によって 調べる ことができます。そこで、下記のプログラムのように ai5 を実装することにします。

5 行目：for 文 の 反復可能オブジェクト に legal_moves を記述することで、合法手 を 順番に取り出し てローカル変数 move に代入するという 繰り返し処理 を行う
6、7 行目：ローカル変数 move から x 座標 と y 座標 を 取り出し て x と y に代入し、mb の move メソッド を 呼び出し て (x, y) のマスに着手を行う
8、9 行目：mb の status 属性 が、手番を表す mb.turn と等しい 場合に、勝利している と判定できるので、その場合はローカル変数 move を着手する座標として返す
10 行目：勝利できる 合法手 が存在する場合は、9 行目の return 文 が実行されることで、関数の処理 が終了するので、繰り返し処理 が終了した時点で、勝利できる 合法手 が 存在しない ことが確定する。その場合は、ランダムな着手 を表す座標を返す

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

行番号のないプログラム

from random import choice

def ai5(mb):
    legal_moves = mb.calc_legal_moves()
    for move in legal_moves:
        x, y = move
        mb.move(x, y)
        if mb.status == mb.turn:
            return move
    return choice(legal_moves)

修正箇所（ai2 との比較です）

from random import choice

-def ai2(mb):
+def ai5(mb):
    legal_moves = mb.calc_legal_moves()
+   for move in legal_moves:
+       x, y = move
+       mb.move(x, y)
+       if mb.status == mb.turn:
+           return move
    return choice(legal_moves)

次に、下記のプログラムで ai5 が 正しく実装されたか どうかを確認します。なお、2 行目では、後で利用する予定の ai_match、ai3、ai4 を ついでにインポート しています。

実行結果から、以下の 2 点 が おかしい ことがわかります。

「( 1 , 2 ) のマスにはマークが配置済です」という エラーメッセージが表示 される
その後で、いきなり 8 つのマス に着手が行われた ゲーム盤が表示 される

このようなおかしな結果になった理由について少し考えてみて下さい。

from marubatsu import Marubatsu
from ai import ai_match, ai2, ai3, ai4

mb = Marubatsu()
mb.play(ai=[ai5, ai2])

実行結果

Turn o
...
...
...

( 1 , 2 ) のマスにはマークが配置済です
winner o
oxo
xox
oX.

バグの原因の調査

バグの原因 を 調べる 方法の一つに、プログラムの処理で利用する 変数の値 が変化する際に、その値 を表示するという方法があります。ai5 の場合は、下記の場合で print を使って変化した 変数の値 を print で表示すると良いでしょう。なお、このような バグの調査や修正 のために行う表示の事を、デバッグ表示 と呼びます。

3、5 行目：代入によって legal_moves と move の値が変化した直後で、print でその 変数の値 を表示する
8、9 行目：7 行目の move メソッドの処理で、ゲーム盤 の状況と、10 行目の式 で利用する mb.status と mb.turn の 値が変化 するので、それらの値 を表示する

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

行番号のないプログラム

def ai5(mb):
    legal_moves = mb.calc_legal_moves()
    print("legal_moves", legal_moves)
    for move in legal_moves:
        print("move", move)
        x, y = move
        mb.move(x, y)
        print(mb)
        print("status", mb.status, "turn", mb.turn)
        if mb.status == mb.turn:
            return move
    return choice(legal_moves)

修正箇所

def ai5(mb):
    legal_moves = mb.calc_legal_moves()
+   print("legal_moves", legal_moves)
    for move in legal_moves:
+       print("move", move)
        x, y = move
        mb.move(x, y)
+       print(mb)
+       print("status", mb.status, "turn", mb.turn)
        if mb.status == mb.turn:
            return move
    return choice(legal_moves)

上記では、ai5 の 処理の中 で利用する、値が変化 する変数を すべて表示 していますが、そのような変数の 数が多い 場合は、すべての変数 を表示すると、表示が多くなりすぎて わかりづらく なります。そのような場合は、バグの原因 となる 可能性の高い 変数に 絞って表示 すると良いでしょう。

次に、改めて play メソッドを実行して、ai5 で行われた 処理の経過 を確認します。

mb.play(ai=[ai5, ai2]);

実行結果

Turn o
...
...
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
move (0, 0)
Turn x
O..
...
...

status playing turn x
move (1, 0)
Turn o
oX.
...
...

status playing turn o
略

1 回目の繰り返し処理の調査

実行結果の legal_moves の行の表示から、9 つ の すべてのマス が 合法手 になっていることが確認できます。この部分 には 問題はなさそう です。

下記は、ai5 の 4 行目の、for move in legal_moves: の 1 回目 の 繰り返し処理 で表示された 実行結果 の抜粋です。実行結果 から、以下の処理 が行われたことが分かります。

合法手 として (0, 0) が 取り出され、(0, 0) のマスに着手が行われる
(0, 0) に 〇が配置 される
ゲームの 決着がついていない ので、mb.status に "playing" が代入される
実行結果 から、mb.turn に "x" が代入される

move (0, 0)
Turn x
O..
...
...
status playing turn x

明らかに、〇は 勝利しておらず、実際に 10 行目の if mb.status == mb.turn: の 条件式 は False になるので、この後で、次の 合法手 に対する 繰り返し処理 が実行されます。

実は、この時点で ai5 の処理には バグがある ことがわかりますが、初心者 がそのことに 気づく ことは 難しい と思います。そのバグについては この後 で判明することになるので、現時点 では 気づかなかったことにして 話を進めます。興味がある方は、どこにどのようなバグがあるかについて少し考えてみて下さい。

2 回目の繰り返し処理の調査

下記は、ai5 の 4 行目の、for move in legal_moves: の 2 回目 の 繰り返し処理 で表示された 実行結果 の抜粋です。実行結果 から、以下の処理 が行われたことが分かります。

合法手 として (1, 0) が 取り出され、(1, 0) のマスに着手が行われる
(1, 0) に × が配置 される
ゲームの 決着がついていない ので、mb.status に "playing" が代入される
実行結果 から、mb.turn に "o" が代入される

この 実行結果 から、先程のバグのうちの片方の原因が何であるかがわかります。それが何であるかについて少し考えてみて下さい。

move (1, 0)
Turn o
oX.
...
...

status playing turn o

合法手 として、(0, 0) の次の (1, 0) が 取り出される 点は 正しい のですが、ゲーム盤に 2 つ の マークが配置 される点が 間違って います。その原因は、1 回目の繰り返し処理で、(0, 0) のマスに着手を 行った後 で、続けて 2 回目の繰り返し処理で (1, 0) のマスに着手を行っているからです。この後 で、このような処理が 繰り返された結果、いきなり 8 つのマス に着手が行われた ゲーム盤が表示 されるという バグが発生 することになります。

このバグを解決するためには、繰り返しのたび に、ゲーム盤 の状態を、ai5 を 実行した時 の状態に戻す必要があります。

バグの一つである「いきなり 8 つのマス に着手が行われた ゲーム盤が表示 される」点の 原因が判明 しましたが、「( 1 , 2 ) のマスにはマークが配置済です」という エラーメッセージが表示 される原因がまだ 判明していない ので、引き続き 調査を続ける ことにします。

7 回目の繰り返し処理の調査

3 ~ 6 回目 の 繰り返しの処理 の 実行結果 を調査した所、上記で発見した、続けて マークが配置される点を 除けば、特に 不審な処理 が行われている点は 見つけられませんでした ので、その説明は省略し、その次の繰り返し処理を調査します。

下記は、ai5 の 4 行目の、for move in legal_moves: の 7 回目 の 繰り返し処理 で表示された 実行結果 の抜粋です。実行結果 から、以下の処理 が行われたことが分かります。

合法手 として (0, 2) が 取り出され、(0, 2) のマスに着手が行われる
(0, 2) に 〇が配置 される
斜め方向 に〇が配置されるので、〇が勝利 し、mb.status に "o" が代入される
実行結果 から、mb.turn に "x" が代入される

move (0, 2)
winner o
oxo
xox
O..

status o turn x

〇が勝利する ので、次の 10 行目の if mb.status == mb.turn: の 条件式 が True になり、11 行目で ai5 の 返り値 として move に代入された (0, 2) が 返されるはず です。しかし、実際には、上記の 実行結果 の直後に、move (1, 2) が表示されることから、この 条件式 が False になり、次の 8 回目 の 繰り返し処理 が開始されてしまうというバグが発生することが判明します。このようなバグが発生する理由について少し考えてみて下さい。

if mb.status == mb.turn: の 条件式 が False になる理由は、上記の 7 回目 の 実行結果 の status o turn x からわかるように、7 回目 の 繰り返し処理 によって、mb.turn に x が代入されるからです。また、そのようなことが起きる原因は、move メソッドを実行すると、手番が 入れ替わってしまう ためです。従って、このバグは、10 行目 の if 文の 条件式 で、mb.status と mb.turn を比較するの ではなく、mb.status と、着手を 行う前 の mb.turn を比較するようにすることで修正することができます。

上記が、先ほどの「1 回目の繰り返し処理の調査」の最後で説明した、初心者 が 発見しづらいバグ です。なお、「( 1 , 2 ) のマスにはマークが配置済です」という エラーメッセージが表示 される原因がまだ 判明していない ので、引き続き 調査を続ける ことにします。

よくある論理の間違い

以下のような 考え方 で、修正するという方法を考えた方がいるかもしれません。

下記は 間違った 考え方なので、背景を赤く しています。

〇× ゲーム で、自分が勝利する ということは、〇の手番 であっても、× の手番 であっても、ゲームの 決着がつく ということである
決着がついた場合 は、mb.status の値 が Marubatsu.PLAYING では なくなる
従って、10 行目を if mb.status != Marubatsu.PLAYING: のように修正することで 自分が勝利 したことを判定することができる

実際に 10 行目を if mb.status != Marubatsu.PLAYING: に修正しても、プログラムは 正しく動作 しますが、上記の 考え方 は 間違っています。何が間違っているか、そして 間違っている にもかかわらず 正しく動作する理由 について、少し考えてみて下さい。

間違いの理由

アルゴリズム を 考える 時に、よくある間違い が、上記のような 論理的 な 勘違い です。上記の考え方 の場合は、以下のような論理で話を進めています。なお、下記の A → B という表記は、A が成り立つ場合 は B が成り立つ という、A ならば B という意味を表します。

自分が勝利 する → ゲームの 決着がつく
ゲームの 決着がつく → mb.status が Marubatsu.PLAYING と 異なる値 になる
従って、自分が勝利 する → mb.status が Marubatsu.PLAYING と 異なる値 になる
従って、mb.status が Marubatsu.PLAYING と 異なる値 になる → 自分が勝利 する

上記の 1、2 は 正しい論理 です。また、3 は 論理学 の 三段論法 という 正しい論理 です。

しかし、A ならば B という論理が 正しい場合 でも、その逆の B ならば A は 正しいとは限らない ので 4 は 間違った論理 です。例えば、「大谷選手は野球選手である」は 正しい ですが、「野球選手は大谷選手である」は 正しい とは 限りません。慣れていても、逆が正しい という 間違った論理 で 話を進める ことは よくある ので、気を付ける必要 があります。

上記の 考え方 で、具体的に 間違っている部分 は、自分の着手 によって 決着がついた場合 に、自分が勝利 しているとは 限らない という点です。具体的には、最後のマス に着手した際に、引き分け になる場合があります。10、11 行目 の処理の意図は、着手することで勝利する 合法手 を返すというものですが、10 行目を if mb.status != Marubatsu.PLAYING: のように修正すると、引き分け という、勝利しない 合法手を 返り値 として返すという、本来の意図 とは 異なる処理 が行われてしまいまう 可能性 が生じてしまいます。

なお、A ならば B が 成り立つ 場合に、対偶の B でないならば A でない は 常に成り立ちます。逆や対偶などの関係は 論理学 の基礎で、アルゴリズム を 正しく記述 するための 必須の知識 です。説明が長くなるので本記事でそれらの詳しい説明は行いませんが、不安な方はしっかりと勉強して 理解しておく ことを 強くお勧め します。

間違っていても正しく動作する理由

考え方 が 間違っていても正しく動作 する理由は、以下の通りです。

本来の意図 とは 異なる処理 が行われるのは、引き分け になる 場合だけ である
〇× ゲーム で 引き分けになる のは、空いているマス が 1 つ、すなわち 合法手 が 1 つ しか存在しない 場合だけ である
合法手 が 1 つ の場合は、どのような AI であっても、選択できる 合法手は同じ である。従って、本来の意図 とは 異なる処理 が行われても、選択される 合法手 は 変わらない

つまり、本来の意図 とは 異なる処理 が行われているにもかかわらず、プログラムが 正しく動作 する理由は、〇×ゲームの性質 が たまたまそうなっている という、偶然の結果 に過ぎないということです。

ある程度プログラミングに上達した方が、上記の 正しく動作する理由 をちゃんと 理解した上 で、10 行目に if mb.status != Marubatsu.PLAYING: を記述するのは 問題はありません が、初心者 の方などで、理由はよくわからない が、うまくいく という理由でそのように記述するのは、後で プログラムを修正 する際などで バグの原因 に なりやすい ので、避けたほうが良い と思います。本記事ではこの記述は採用しません。

また、正しく動作 する理由が 理解できている 場合でも、複雑な論理 で行われる処理は 時間がたつ と 忘れてしまう可能性 が 非常に高くなる ので、そのような場合は、コメント を記述して、そのことを 説明しておいたほうが良い でしょう。

8 回目の繰り返し処理の調査

下記は、ai5 の 4 行目の、for move in legal_moves: の 8 回目 の 繰り返し処理 で表示された 実行結果 の抜粋です。実行結果 から、以下の処理 が行われたことが分かります。

合法手 として (1, 2) が 取り出され、(１, 2) のマスに着手が行われる
(1, 2) に × が配置 される
7 回目の繰り返し処理の結果、斜め方向 に〇が既に配置されているので、〇が勝利 し、mb.status に "o" が代入される
実行結果 から、mb.turn に "o" が代入される

move (1, 2)
winner o
oxo
xox
oX.

status o turn o

8 回目の繰り返しで、(1, 2) のマスに着手を行った結果、(1, 2) に × のマークが配置されます。その結果、× が勝利することは ありません が、7 回目 の〇の (0, 2) への着手によって斜め方向に〇が並んでおり、〇が勝利 しているため、mb.status に "o" が代入 されます。また、8 回目の × の着手 が行われたので、〇の 手番になる ので、mb.status に o が代入されます。従って、10 行目の if mb.status == mb.turn: の 条件式 が True になり、11 行目で ai5 の 返り値 として、move に代入された (1, 2) が 返されます。

play メソッドは、ai5 の 返り値 である (1, 2) のマスに着手を行いますが、上記の実行結果からわかるように、(1, 2) のマスには、ai5 の処理で 既に x が 配置済 です。そのため、「( 1 , 2 ) のマスにはマークが配置済です」という エラーメッセージが表示 されます。

この エラーメッセージ は、ai5 の処理によって、ゲーム盤 に 合法手 が すべて着手 されてしまうことが原因なので、先程の「繰り返しのたび に、ゲーム盤 の状態を、ai5 を 実行した時 の状態に戻す」という方法で修正することが できます。

バグの修正方法

上記の調査によって、バグの原因 と下記の 修正方法 がわかりました。

繰り返しのたび に、ゲーム盤 の状態を、ai5 を 実行した時 の状態に戻す
if 文 の 条件式 で、mb.status と mb.turn を比較するの ではなく、mb.status と、着手を 行う前 の mb.turn を比較するようにする

まず、上記の 1 つ目 の修正を行うことにします。1 つ目の処理を行う アルゴリズム は いくつかあります が、今回の記事では、データ を コピー（複製）する、以下のようなアルゴリズムを紹介します。他のアルゴリズムについては、今後の記事で紹介する予定です。

move メソッドで 着手を行う前 に、mb を コピーしたデータ を作成する
複製したデータ に対して move メソッドで着手を行う

ai5 の 仮引数 である mb に 対して着手を行うの ではなく、繰り返しのたびに、mb を コピー し、コピーしたデータに 対して着手を行うことで、繰り返しのたび に、ゲーム盤 の状態を、ai5 を 実行した時 の状態に戻すことができます。

上記の処理を行うためには、データ を コピー する必要がありますが、データ の コピー には 2 種類 があり、正しく 使い分ける必要 があるので、そのことを説明します。

データのコピー（複製）と copy モジュール

以前の記事で説明したように Python の 代入文 は、データ を共有するという処理を行うので、1 つの代入文だけ で list や dict などの 複合データ型 の データ の コピー を行うことは できません。忘れた方は、以前の記事の プログラム A と B について復習して下さい。

疑似的な複製が行われる 数値型、文字列型、論理型 などのデータは、1 つの代入文だけ で コピー（複製）と 同等の処理 を行うことができます。

データ の コピーの処理 を 自分で記述 することは可能ですが、Python には データ を コピー するための copy という モジュール があるので、それを利用すると良いでしょう。

copy モジュール には 浅いコピー を行う copy と 深い（deep）コピー を行う deepcopy という関数が定義されており、状況に応じて 適切に 使い分ける必要 があります。

copy モジュールの詳細については、下記のリンク先を参照して下さい。

「複合オブジェクト」と「複合データ型」の用語の統一

上記のリンク先では、「複合オブジェクト」は、以下のように説明されています。

「リストやクラスインスタンスのような 他のオブジェクト を 含むオブジェクト」

これは、以前の記事で下記のように定義した「複合データ型」と意図は ほぼ同じ です。

「Python の 任意のデータ型 を、複数組み合わせて データを表現する データ型」

以前の記事を執筆した際には、「複合オブジェクト」という用語を見つけられなかったので、「複合データ型」という用語を定義して使いましたが、本家のドキュメントに 同じ意図 の用語があることが今回わかったので、以後は「複合オブジェクト」の方を使用します。

浅いコピー

上記のリンク先では、copy モジュール の、copy という名前の関数が行う、浅いコピー という処理は、下記のように説明されています。

「浅いコピー（shallow copy）は 新たな複合オブジェクト を作成し、その後（可能な限り）元のオブジェクト中 に見つかった オブジェクト に対する参照を挿入します」

copy による 浅いコピー で行われる処理の ポイント は以下の通りです。

見た目 は コピー元 と 同じデータ が作成される
任意の データ型 のデータを コピーできる
- オブジェクト の場合は、コピー元 と 同じ属性 を持つ オブジェクト が作成される
- list の場合は、コピー元 と 同じ要素 を持つ list が作成される
- dict の場合は、コピー元 と 同じキーの値 を持つ dict が作成される
ただし、浅いコピー で コピー された データ の属性（要素、キーの値）は、複製されるの ではなく、代入文 と 同様の方法 で共有される

上記の性質の中の、3 つ目 の性質が 非常に重要 なので、具体例を挙げて説明します。その際に、dict で説明すると わかりやすい と思いましたので、dict で説明します。

浅いコピーで行われる処理

実引数 に記述した dict の 浅いコピー を作成して 返す関数 を 自分で記述 する場合は、下記のようなプログラムになります¹。

1 行目：コピー元 の dict を代入する 仮引数 の名前を data² とする
2 行目：data の 浅いコピー を代入する new_dict を 空の dict で 初期化 する
3 行目：items メソッド を使って、data のキーと キーの値 を 順番に取り出して、key と value に代入するという for 文 による 繰り返し処理 を行う
4 行目：new_dict の key という キーの値 に value を代入することで、data と new_dict の 同じ名前 のキーが、同じデータ を共有するようにする
5 行目：data の 浅いコピー が代入された new_dict を 返り値 として返す

def copy_dict(data):
    new_dict = {}
    for key, value in data.items():
        new_dict[key] = value
    return new_dict

下記のプログラムは、dict が代入された a を copy_dict を使って 浅いコピー を行い、b に代入 しています。その結果、3、4 行目 では、a と b で 同じ表示 が行われます。

a = { "c": 1, "d": [2, 3] }
b = copy_dict(a)
print(a)
print(b)

実行結果

{'c': 1, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]}

次に、下記のプログラムの 1 行目で、b["c"] に 5 を代入しても、実行結果から、a["c"] の値は 変化しない ので、a と b の値は独立しているように 見えるかもしれません。

b["c"] = 5
print(a)
print(b)

実行結果

{'c': 1, 'd': [2, 3]}
{'c': 5, 'd': [2, 3]}

しかし、下記のプログラムの 1 行目で b["d"][0] に 6 を代入すると、実行結果のように a["d"][0] の値も 6 に変化してしまいます。これは、先ほど説明したように、a["d"] と b["d"] が、同じデータ を共有しているからです。この現象の原因は、以前の記事で説明した プログラム A と B の違いと同様です。

b["d"][0] = 6
print(a)
print(b)

実行結果

{'c': 1, 'd': [6, 3]}
{'c': 5, 'd': [6, 3]}

浅いコピーによってコピーされた場合の図

下図の左は、浅いコピー が行われた直後の a と b を、下図の右は、その後で b["c"] = 5 と b["d"][0] = 6 を実行した直後の a と b の状態を表しています。

`copy` 関数による浅いコピー

この性質は、下記のプログラムのように、自作の copy_dict の代わりに、copy モジュール の copy 関数 を利用しても同様です。なお、copy_dict と copy の違いは、copy_dict が dict のみ を コピーできる のに対し、copy は 任意のデータ を コピーできる 点です。

from copy import copy

a = { "c": 1, "d": [2, 3] }
b = copy(a)
print(a, b)
b["c"] = 5
print(a, b)
b["d"][0] = 6
print(a, b)

実行結果

{'c': 1, 'd': [2, 3]} {'c': 1, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]} {'c': 5, 'd': [2, 3]}
{'c': 1, 'd': [6, 3]} {'c': 5, 'd': [6, 3]}

浅いコピーの性質

上記のことから、list、dict、オブジェクト などの、複合オブジェクト を 浅いコピー で コピー した場合は、以下の点に注意する必要があります。

すべて の 属性の値（要素、キーの値）に、疑似的な複製 が行われる データ が代入されている場合は、データ が 完全にコピー されたと みなしても良い
疑似的な複製 が 行われない データが代入されている 属性の値（要素、キーの値）は複製されず、コピー元 のデータと共有が行われる

`Marubatsu` クラスのインスタンスの浅いコピー

copy によって、下記のプログラムの 2 行目のように、Marubatsu クラスの インスタンス である mb のような オブジェクト に対する 浅いコピー を行うことが できます。そのため、3、4　行目のように、コピー元 の mb と、浅いコピー が行われた mb2 の ゲーム盤 を表示すると 同じ内容 が表示されます。

mb = Marubatsu()
mb2 = copy(mb)
print(mb)
print(mb2)

実行結果

Turn o
...
...
...

Turn o
...
...
...

しかし、mb.board と mb2.board は同じ 2 次元配列を表す list を共有するので、下記のプログラムのように、move メソッドを使って mb のゲーム盤の (0, 0) のマスに着手を行うと、下記の実行結果のように、mb2 のゲーム盤の (0, 0) にも着手が行われてしまいます。

そのため、ai5 で mb を コピー して、同じ内容 だが、独立した ゲーム盤 を持つ データ を作成するという目的で copy を利用することは できません。

mb.move(0, 0)
print(mb)
print(mb2)

実行結果

Turn x
O..
...
...

Turn o
o..
...
...

なお、上記の実行結果で、mb のゲーム盤には turn x が、mb2 のゲーム盤には turn o が表示される理由は、mb.turn と mb2.turn には 疑似的な複製 が行われる 文字列型 のデータが代入されているので、mb.turn の値を変更しても、mb2.turn は 変化しない からです。

深いコピー

複合オブジェクト を コピー する際に、共有を一切 行わず に、すべて の属性（要素、キーの値）を コピー する処理の事を 深い（deep）コピー、または 完全なコピー と呼びます。深いコピー は、copy モジュール の、deepcopy という名前の関数で行うことができます。

なお、深いコピー が 行う処理 は、これまでの記事で説明していない 再起呼び出し という記述が必要となるので、具体的なプログラムは紹介しません。再起呼び出しについては必要になった時点で紹介します。

下記は、先程のプログラムの copy を deepcopy に変えて、深いコピー を行うようにしたものです。実行結果から、b["c"][0] に 6 を代入しても、a["c"][0]" の値が 変化しない ので、b は a を 完全にコピー した、a とは 独立したデータ であることが確認できます。

1  from copy import deepcopy
2
3  a = { "c": 1, "d": [2, 3] }
4  b = deepcopy(a)
5  print(a, b)
6  b["c"] = 5
7  print(a, b)
8  b["d"][0] = 6
9  print(a, b)

行番号のないプログラム

from copy import deepcopy

a = { "c": 1, "d": [2, 3] }
b = deepcopy(a)
print(a, b)
b["c"] = 5
print(a, b)
b["d"][0] = 6
print(a, b)

修正箇所

-from copy import copy
+from copy import deepcopy

a = { "c": 1, "d": [2, 3] }
-b = copy(a)
+b = deepcopy(a)
print(a, b)
b["c"] = 5
print(a, b)
b["d"][0] = 6
print(a, b)

実行結果

{'c': 1, 'd': [2, 3]} {'c': 1, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]} {'c': 5, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]} {'c': 5, 'd': [6, 3]}

下図は、上記のプログラムで 深いコピー を 行った直後 の状況を表します。

下図は、b["c"] = 5 と b["d"][0] = 6 を実行した直後の状況を表します。

深いコピーによる `mb` のコピー

deepcopy を利用することで、下記のプログラムのように、ゲーム盤のデータを代入する board 属性 を含め、mb が管理する すべての属性 を 完全にコピー することができます。下記の 6、7 行目 のプログラムの実行結果の表示からわかるように、先ほどと異なり、mb に対して (0, 0) に着手を行っても、mb2 で着手は 行われません。

1  mb = Marubatsu()
2  mb2 = deepcopy(mb)
3  print(mb)
4  print(mb2)
5  mb.move(0, 0)
6  print(mb)
7  print(mb2)

行番号のないプログラム

mb = Marubatsu()
mb2 = deepcopy(mb)
print(mb)
print(mb2)
mb.move(0, 0)
print(mb)
print(mb2)

修正箇所

mb = Marubatsu()
-mb2 = copy(mb)
+mb2 = deepcopy(mb)
print(mb)
print(mb2)
mb.move(0, 0)
print(mb)
print(mb2)

実行結果

Turn o
...
...
...

Turn o
...
...
...

Turn x
O..
...
...

Turn o
...
...
...

浅いコピーと深いコピーの使い分け

どのような場合でも深いコピーを使えば良いと思う人がいるかもしれませんが、深いコピー には、下記のような欠点があるので、状況に応じて使い分ける必要 があります。

コピーする データ の サイズ が 大きい 場合は、浅いコピー と比較して 時間がかかる
コピー元 と 同じ大きさ の データ が 新しく作られる ため、コピーする データ の サイズ が 大きい 場合は コンピューター の メモリ がその分だけ必要になる
コピー元 と コピー先 で、一部の属性 を 共有したい 場合は 利用できない

上記の 1、2 から 浅いコピー の方が、処理の時間 が短く、必要な メモリの量 も 少ない ので、浅いコピー で 十分な場合 は 浅いコピー を 使ったほうが良い でしょう。

上記の 3 から、コピー元 のデータと、コピー先 のデータの間で、一部の属性 を 共有したい 場合などでは、深いコピーではなく、浅いコピー を 利用する必要 があります。

慣れないうち は、浅いコピー と 深いコピー の 使い分け が わかりづらい と思いますので、本記事では データ を コピーする際 には、どちらを使うべきか について説明します。

`ai5` の修正

下記は、ai5 のバグの 修正方法 を再掲したものです。

繰り返しのたび に、ゲーム盤 の状態を、ai5 を 実行した時 の状態に戻す
if 文 の 条件式 で、mb.status と mb.turn を比較するの ではなく、mb.status と、着手を 行う前 の mb.turn を比較するようにする

1 つ目 の修正を行うためには、ゲーム盤 を 完全にコピー するために、deepcopy を使って 深いコピー を行う必要があります。

2 つ目 の修正で必要となる、着手を 行う前 の手番のデータは、コピー元 の データ の turn 属性 に代入されています。

従って、ai5 は、下記のプログラムのように修正することができます。なお、先程 デバッグ表示 のために挿入した print は削除しました。

1、2 行目：元（original）の mb であることを表すようにするために、仮引数 の名前を mb_orig に修正し、2 行目 の mb を mb_orig に修正する
4 行目：deepcopy を使って、mb_orig の 深いコピー を作成し、mb に代入する
7 行目：mb.status は、着手を行う前 の手番と比較する必要があるので、mb.turn を、着手前 の手番を表す mb_orig.turn に修正する

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

行番号のないプログラム

def ai5(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    return choice(legal_moves)

修正箇所

-def ai5(mb):
+def ai5(mb_orig):
-   legal_moves = mb.calc_legal_moves()
+   legal_moves = mb_orig.calc_legal_moves()
    for move in legal_moves:
+       mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
-       if mb.status == mb.turn:
+       if mb.status == mb_orig.turn:
            return move
    return choice(legal_moves)

改めて play メソッドを実行して、ai5 の処理を確認します。実行結果から、〇の 4 回目 で、勝利できる (1, 1) の 着手を行う ことが確認できます。実行結果は ランダム なので、不安な方は、何度か実行 して、意図した処理が行われる ことを確認して下さい。

mb.play(ai=[ai5, ai2]);

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

Turn o
...
...
...

Turn x
...
...
.O.

Turn o
...
...
.oX

Turn x
...
...
Oox

Turn o
.X.
...
oox

Turn x
.xO
...
oox

Turn o
Xxo
...
oox

winner o
xxo
.O.
oox

`ai2` との対戦

ai5 が実装できたので、下記のプログラムで、基準となる ai2 と対戦します。なお、筆者のパソコン では、10000 回の対戦を行うと、約 16 秒 かかりました。あまり 時間がかかる ようであれば、対戦の回数 を 減らして ください。

ai_match(ai=[ai5, ai2])

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

ai5 VS ai2
count     win    lose    draw
o        8133    1189     678
x        5218    3937     845
total   13351    5126    1523

ratio     win    lose    draw
o       81.3%   11.9%    6.8%
x       52.2%   39.4%    8.5%
total   66.8%   25.6%    7.6%

下記は、上記の結果を基準となる 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

表から、ai5 は、ai2 に 対して、ai4 より は 若干弱い が、ai1 より も強い AI であることが わかります。また、ルール 3 の説明をした際の、ai5 は ai2 より も 必ず強くなる という考察が 正しいこと が、対戦の結果 から確認できました。

`ai3` と `ai4` との対戦

これまでに作成した ai3、ai4 と対戦して、強さを比較 することにします。

ai_match(ai=[ai5, ai3])

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

ai5 VS ai3
count     win    lose    draw
o        7240    1989     771
x        3936    5282     782
total   11176    7271    1553

ratio     win    lose    draw
o       72.4%   19.9%    7.7%
x       39.4%   52.8%    7.8%
total   55.9%   36.4%    7.8%

ai_match(ai=[ai5, ai4])

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

ai5 VS ai4
count     win    lose    draw
o        6050    3663     287
x        2718    7073     209
total    8768   10736     496

ratio     win    lose    draw
o       60.5%   36.6%    2.9%
x       27.2%   70.7%    2.1%
total   43.8%   53.7%    2.5%

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

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分
`ai5` VS `ai3`	72.4	19.9	7.7	39.4	52.8	7.8	55.9	36.4	7.8
`ai4` VS `ai3`	83.1	9.4	7.4	27.4	70.1	2.5	55.2	39.8	5.0
`ai5` VS `ai4`	60.5	36.6	2.9	27.2	70.7	2.1	43.8	53.7	2.5

`ai5` VS `ai3` と `ai4` VS `ai3` による考察

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

ai5 VS ai3 の 通算成績 では、ai5 の勝率が 55.9%、敗率が 36.4% となっているため、ai5 は、ai3 に 対して かなり強そう である
ai4 VS ai3 の 通算成績 と ほぼ同じ成績 なので、ai3 に 対しては、ai4 と ai5 は ほぼ同じ強さ を持つ
ai5 VS ai3 は、ai4 VS ai3 の場合と 異なり、× の手番 を担当する際に、極端に弱い ということはないので、ai5 には、ai4 のような欠陥はない

従って、ai5 は ai3 に 対して、ai4 と 同等の強さ を持ち、なおかつ ai4 のような欠陥を 持たない ことがわかり、ルール 5 の 効果が大きい ことが考察できます。

上記の考察は、筆者の考察 に すぎない ので、他の観点 から 別の考察 を行うことも可能です。興味がある方は、別の観点から考察を行ってみて下さい。

`ai5` VS `ai4` と `ai2` VS `ai2` による考察

次に、ai5 VS ai4 との 対戦結果 を考察します。

通算成績 は ai4 のほうが良いので、ルール 5 は、ルール 4 に対して 相性が悪い ことがわかります。ただし、〇を担当 した場合は強いが、× を担当 した場合は弱いような、担当した マーク によって強さが 大きく異なる場合 があるので、通算成績 だけでなく、〇を担当 した場合と、× を担当 した場合の それぞれの成績 に対する考察が必要です。

〇×ゲーム は、〇を担当 したほうが有利なゲームなので、ai5 が 〇や × を担当 した場合の 結果だけ を見ても、その 成績が良いか どうかを 判断できない ので、それらの成績を評価するためには、何らかの指標 が必要になります。

例えば、テストの点数 で 90 点 を取った場合に、平均点 が 50 点 の場合と、95 点 の場合で、その点が 良い点 であるかどうか評価が 大きく変わり ます。

そこで、テストの平均点のような指標として、ランダムな着手 を行う ai2 VS ai2 の 〇を担当 した場合の成績と、× を担当 した場合の成績を 利用する ことにします。もちろん、この指標が〇× ゲームの本当の〇と × の 有利さ を表している 保証はありません が、現時点 では他に 有力な指標 がないので、今回の記事ではこの指標を使うことにします。

例えば、ある AI が 〇を担当 した際の成績が、ai2 VS ai2 で、ai2 が 〇を担当 した際の成績よりも 良ければ、その AI は、対戦相手の AI に対して、〇を担当 した場合の相性が 通常より も良いと判断することにします。

下記は、ai5 VS ai4 と ai2 VS ai2 の成績を表にしたものです。

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分
`ai5` VS `ai4`	60.5	36.6	2.9	27.2	70.7	2.1	43.8	53.7	2.5
`ai2` VS `ai2`	58.7	28.8	12.6	29.1	58.6	12.3	43.9	43.7	12.5

上記の表から、ai5 VS ai4 について、以下のような考察を行いました。

ai5 が 〇を担当 した場合の成績と指標となる成績は、勝率は 60.5% と 58.7% で 2% ほど高いが、敗率も 36.6% と 28.8% で 8 % ほど高い。従って、総合的 にみると、指標より も成績が 少し悪い と考察できる
ai5 が × を担当 した場合の成績と指標となる成績は、勝率は 1.9% 低く、敗率は 12.1% も高い。従って、通常より も 成績が悪い と考察できる

上記から、通算成績だけでなく、〇を担当 した場合も、× を担当 した場合も、ai5 は ai4 に 対して 通常より も 相性が悪い ことが考察できました。また、× を担当 した場合の方が 〇を担当 した場合よりも相性がさらに悪いということも考察できます。

今回の記事のまとめ

今回は、以下の表のようなアルゴリズムの ai5 を実装し、他の AI と対戦することで、ai5 の強さを検証しました。また、ai5 を実装するために必要な、浅いコピー と 深いコピー について説明しました。

関数名	アルゴリズム
`ai5`	勝てる場合に勝つそうでない場合はランダムなマスに着手する

ai5 は ai4 に 対しては弱いですが、ai4 VS ai3 の場合と 異なり、どちらの手番 でも ai3 に 対して強く、ai4 のような欠陥を 持たない ことが確認できました。

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

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

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

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

次回の記事

このプログラムは、まだ説明していない dict 内包表記 で記述することができますが、浅いコピー の中で 代入処理 が行われることを明確にするために、わざと dict 内包表記 を 使わない方法 で記述しています。dict 内包表記については、今後の記事で説明する予定です ↩
dict という名前は、組み込み関数 として 使われている ので、仮引数の名前 を data にしました ↩