Pythonで〇×ゲームのAIを一から作成する その45 勝てる場合に勝つAIと、浅いコピーと深いコピー

目次と前回の記事

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

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

これまでに作成した 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 を作成することにします。

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

ルール 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 という 意味 を表します。

1. 自分が勝利 する → ゲームの 決着がつく
2. ゲームの 決着がつく → mb.status が Marubatsu.PLAYING と 異なる値 になる
3. 従って、自分が勝利 する → mb.status が Marubatsu.PLAYING と 異なる値 になる
4. 従って、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 つ目の処理を行う アルゴリズム は いくつかあります が、今回の記事では、データ を コピー（複製）する、以下のようなアルゴリズムを紹介します。他のアルゴリズムについては、今後の記事で紹介する予定です。

1. move メソッドで 着手を行う前 に、mb を コピーしたデータ を 作成 する
2. 複製したデータ に対して 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. コピー元 と コピー先 で、一部の属性 を 共有したい 場合は 利用できない

上記の 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 です。

次回の記事

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

2. dict という 名前 は、組み込み関数 として 使われている ので、仮引数の名前 を data にしました ↩