目次と前回の記事

`ai11s` の問題点

AI が弱くなった場合の対処方法

同一局面の定義と扱い

試合経過の観察と検証

今回の記事のまとめ

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

次回の記事

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

これまでに作成した AI

問題の原因の絞り込み

問題が発生している可能性が高い試合の観察

棋譜の記録の実装

同一局面の定義

同一局面の種類

同一局面の性質と本記事での扱い

1 手目の検証

2 手目の検証

3 手目の検証

4 手目の検証

5 手目の検証

`ai10s` VS `ai11s` で行われる着手の選択のまとめ

上記のプログラムの問題点

棋譜の必要性

`restart` メソッドの修正

`move` メソッドの修正

棋譜の表示

棋譜によるゲームの経過の表示

指定した条件の試合経過を表示する関数の定義

回転による同一局面

線対称な同一局面

同一局面の一覧

評価値の確認

同一局面をまとめる

デバッグ表示にマークのパターンの数を表示する修正

ローカル関数のブロックの中の名前解決

global と nonlocal

評価値の計算方法の検証

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

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

ルール	アルゴリズム
ルール1	左上から順に空いているマスを探し、最初に見つかったマスに着手する
ルール2	ランダムなマスに着手する
ルール3	真ん中のマスに優先的に着手する既に埋まっていた場合はランダムなマスに着手する
ルール4	真ん中、隅のマスの順で優先的に着手する既に埋まっていた場合はランダムなマスに着手する
ルール5	勝てる場合に勝つそうでない場合はランダムなマスに着手する
ルール6	勝てる場合に勝つそうでない場合は相手の勝利を阻止するそうでない場合はランダムなマスに着手する
ルール6改	勝てる場合に勝つそうでない場合は相手が勝利できる着手を行わないそうでない場合はランダムなマスに着手する
ルール7	真ん中のマスに優先的に着手するそうでない場合は勝てる場合に勝つそうでない場合は相手の勝利を阻止するそうでない場合はランダムなマスに着手する
ルール7改	真ん中のマスに優先的に着手するそうでない場合は勝てる場合に勝つそうでない場合は相手が勝利できる着手を行わないそうでない場合はランダムなマスに着手する
ルール8	真ん中のマスに優先的に着手するそうでない場合は勝てる場合に勝つそうでない場合は相手が勝利できる着手を行わないそうでない場合は、次の自分の手番で勝利できるように、「自 2 敵 0 空 1」が 1 つ以上存在する局面になる着手を行うそうでない場合はランダムなマスに着手する
ルール9	真ん中のマスに優先的に着手するそうでない場合は勝てる場合に勝つそうでない場合は相手が勝利できる着手を行わないそうでない場合は、次の自分の手番で必ず勝利できるように、「自 2 敵 0 空 1」が 2 つ以上存在する局面になる着手を行うそうでない場合は、次の自分の手番で勝利できるように、「自 2 敵 0 空 1」が 1 つ存在する局面になる着手を行うそうでない場合はランダムなマスに着手する
ルール10	真ん中のマスに優先的に着手するそうでない場合は勝てる場合に勝つそうでない場合は相手が勝利できる着手を行わないそうでない場合は、次の自分の手番で必ず勝利できるように、「自 2 敵 0 空 1」が 2 つ以上存在する局面になる着手を行うそうでない場合は、以下の 2 つを総合的に判断して着手を行う次の自分の手番で勝利できるように、「自 2 敵 0 空 1」が 1 つ存在する局面になる着手を行う自分が有利になるように、「自 1 敵 0 空 2」が最も多い着手を行うそうでない場合はランダムなマスに着手する
ルール11	真ん中のマスに優先的に着手するそうでない場合は勝てる場合に勝つそうでない場合は相手が勝利できる着手を行わないそうでない場合は、次の自分の手番で必ず勝利できるように、「自 2 敵 0 空 1」が 2 つ以上存在する局面になる着手を行うそうでない場合は、以下の 3 つを総合的に判断して着手を行う次の自分の手番で勝利できるように、「自 2 敵 0 空 1」が 1 つ存在する局面になる着手を行う自分が有利になるように、「自 1 敵 0 空 2」が最も多い着手を行う相手が不利になるように、「自 0 敵 1 空 2」が最も少ない着手を行うそうでない場合はランダムなマスに着手する

基準となる ai2 との 対戦結果（単位は %）は以下の通りです。太字は ai2 VS ai2 よりも 成績が良い 数値を表します。欠陥の列は、アルゴリズム に欠陥があるため、ai2 との 対戦成績 が 良くても強い とは 限らない ことを表します。欠陥の詳細については、関数名のリンク先の説明を見て下さい。

関数名	o 勝	o 負	o 分	x 勝	x 負	x 分	勝	負	分	欠陥
`ai1` `ai1s`	78.1	17.5	4.4	44.7	51.6	3.8	61.4	34.5	4.1	あり
`ai2` `ai2s`	58.7	28.8	12.6	29.1	58.6	12.3	43.9	43.7	12.5
`ai3` `ai3s`	69.3	19.2	11.5	38.9	47.6	13.5	54.1	33.4	12.5
`ai4` `ai4s`	83.0	9.5	7.4	57.2	33.0	9.7	70.1	21.3	8.6	あり
`ai5` `ai5s`	81.2	12.3	6.5	51.8	39.8	8.4	66.5	26.0	7.4
`ai6`	88.9	2.2	8.9	70.3	6.2	23.5	79.6	4.2	16.2
`ai6s`	88.6	1.9	9.5	69.4	9.1	21.5	79.0	5.5	15.5
`ai7` `ai7s`	95.8	0.2	4.0	82.3	2.4	15.3	89.0	1.3	9.7
`ai8s`	98.2	0.1	1.6	89.4	2.5	8.1	93.8	1.3	4.9
`ai9s`	98.7	0.1	1.2	89.6	2.4	8.0	94.1	1.3	4.6
`ai10s`	97.4	0.0	2.6	85.6	2.6	11.7	91.5	1.3	7.2
`ai11s`	98.1	0.0	1.9	82.5	1.9	15.6	90.3	1.0	8.7	あり

前回の記事では、ルール 10 に、相手が 不利になる ように『「自 0 敵 1 空 2」が 最も少ない 着手を行う』という 条件を追加 した ルール 11 を定義しました。しかし、その ルール 11 を実装した ai11s と、ルール 10 を実装した ai10s を下記のプログラムで対戦させると、実行結果の 通算成績 から ai10s に 対して 弱くなる ことが分かりました。今回の記事では、そのようなことが起きる原因の 調べ方 について説明します。

from ai import ai_match, ai10s, ai11s

ai_match(ai=[ai11s, ai10s])

実行結果

ai11s VS ai10s
count     win    lose    draw
o        2206       0    7794
x           0    4968    5032
total    2206    4968   12826

ratio     win    lose    draw
o       22.1%    0.0%   77.9%
x        0.0%   49.7%   50.3%
total   11.0%   24.8%   64.1%

これまでは、作成した AI の 強さの確認 は、ai_match という関数で 別の AI と 複数回対戦 し、その 通算成績 を見ることで行ってきました。また、その結果が 想定した結果 と 異なる 場合は、プログラムの欠陥 を 探して修正する という方法で対処してきました。

前回の記事で説明したように、必要条件 や 十分条件 の性質を満たす条件であれば、ルール に 組み込む ことで、少なくとも AI が 弱くならない ことが 保証される ので、そのような条件 を 新しく組み込んだ AI が 弱くなった場合 は、プログラムの実装 が 間違っている ことを疑うという 対処法 が 有効な場合 が 多いでしょう。しかし、必要条件 でも 十分条件 でもない条件は、ルールに加えた 場合に、AI が 弱くなる可能性 があるので、AI が 弱くなった場合 は、条件そのもの の欠陥も 疑う必要 があります。

ルール 11 の条件の中で、必要条件 でも 十分条件 でもないものは 以下の通り です。

真ん中 のマスに 優先的 に着手する
以下の 3 つ の条件を 総合的 に判断して着手を行う
- 次の 自分の手番 で 勝利できる ように「自 2 敵 0 空 1」が 1 つ存在する 着手を行う
- 自分が 有利になる ように「自 1 敵 0 空 2」が 最も多い 着手を行う
- 相手が 不利になる ように「自 0 敵 1 空 2」が 最も少ない 着手を行う

この中で、「真ん中 のマスに 優先的 に着手する」という条件は、初期のルール で追加しており、実際にこの条件を ルールに組み込む ことによって AI が 強くなった ことが 確認できている ので、問題がある 可能性 は 低そう です。そこで、この条件 の検証は 後回し にし、残りの条件 に 問題がない ことが 分かった場合 に 改めて調べる ことにします。

3 つ の条件を 総合的 に判断して 着手を行う という条件に対する 評価値 は、それぞれの条件 に対して、下記の表 のように設定した 評価値の合計 で計算していますが、この 評価値 の 計算方法 が、強い AI のための条件として ふさわしくない可能性 があります。

局面の状況	評価値
「自 2 敵 0 空 1」が 1 つ存在する	`1`
「自 1 敵 0 空 2」が x 個存在する	`x`
「自 0 敵 1 空 2」が y 個存在する	`-y`

上記の 評価値 の 計算方法 に問題がある 可能性が高い ことが分かりましたが、この表を眺めているだけでは、どこに問題がある かを知ることは困難でしょう。その理由は、〇×ゲーム に 勝利するため に、『「自 2 敵 0 空 1」が 1 つ存在する』、『「自 1 敵 0 空 2」が x 個存在する』、『「自 0 敵 1 空 2」が y 個存在する』の 3 つの条件 の、それぞれの 重要度 が どれくらいであるか がはっきりと わからない からです。

はっきりとわからない理由 は、必要条件 でも、十分条件 でも ないから です。

そのような場合は、実装した AI が 行った対戦 の中で、問題が発生 している 可能性が高い試合 で 行われた着手 を観察することで 問題の原因 を探るという方法があります。

下記は、先程の ai11s VS ai10s の 対戦結果 を再掲したものです。よく見ると、ai11s が 〇を担当 した場合は、勝率が 約 20 %、敗率が 0 % となっているので、問題はなさそう です。一方、× を担当 した場合は、勝率が 0 %、敗率が 50 % となっており、何か 問題が発生 している 可能性が高い ことが 分かります。このことから、ai11s VS ai10s の試合で、ai11s が × を担当 して 負けた試合 を観察すれば良いことが分かります。

ai11s VS ai10s
count     win    lose    draw
o        2206       0    7794
x           0    4968    5032
total    2206    4968   12826

ratio     win    lose    draw
o       22.1%    0.0%   77.9%
x        0.0%   49.7%   50.3%
total   11.0%   24.8%   64.1%

ai11s VS ai10s で、ai11s が × を担当 して 負ける試合 は、mb.play(ai=[ai10s, ai11s]) を実行し、返り値 が ai11s の敗北 を表す Marubatsu.CIRCLE に なった場合 です。

そのような試合は、下記のプログラムのように、while 文 を使って ai11s が 負けるまで、mb.play(ai=[ai10s, ai11s]) を 繰り返し呼び出す という 処理を行う ことで観察することが できます。最後に 表示された試合 が、ai11s が 負けた試合 です。

今回の記事 では以後は、ai11s VS ai10s のように記述した場合は、先に記述 した ai11s が 〇を担当 して ai10s と 対戦を行う ことを表すことにします。

4 行目：while True による 無限ループ を記述する
5、6 行目：ai10s VS ai11s の対戦を行い、対戦の経過を 表示する。また、その返り値 が Marubatsu.CIRCLE だった場合は、ai11s が 負けている ので、break 文 を実行して 無限ループ から 抜ける

1  from marubatsu import Marubatsu
2
3  mb = Marubatsu()
4  while True:
5     if mb.play([ai10s, ai11s]) == Marubatsu.CIRCLE:
6          break

行番号のないプログラム

from marubatsu import Marubatsu

mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s]) == Marubatsu.CIRCLE:
        break

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

Turn o
...
...
...

Turn x
...
.O.
...

Turn o
...
.o.
..X

Turn x
O..
.o.
..x

Turn o
o.X
.o.
..x

Turn x
o.x
.oO
..x

Turn o
o.x
Xoo
..x

Turn x
o.x
xoo
O.x

Turn o
oXx
xoo
o.x

winner draw
oxx
xoo
oOx

Turn o
...
...
...

Turn x
...
.O.
...

Turn o
..X
.o.
...

Turn x
..x
.o.
O..

Turn o
..x
Xo.
o..

Turn x
..x
xo.
o.O

Turn o
.Xx
xo.
o.o

winner o
.xx
xo.
oOo

このプログラムで、〇が 絶対に勝利しない ような AI どうし の 対戦を行う と、無限ループ から 抜けられない ので、処理が 終わらなくなる 点に注意して下さい。

上記のプログラムを 何度か実行 すれば わかる と思いますが、上記のプログラムには、ai11s が 負けるまで 何度も 対戦を行う ので、運が悪い と ai11s が 負けていない試合 が 延々と表示 されてしまいます。実際に、上記の 実行結果 では、最初に 引き分け の試合が表示され、その次 に ai11s が 負ける試合 が表示されます。表示する 必要がある のは、ai11s が 負けた試合だけ なので、余計な表示 が行われるのは 望ましくありません。

上記の場合は、ai11s が 負ける可能性 が 50 % もある ので 運が悪くない限り、余計な試合 が 数多く表示 されることは ありません が、ai11s が 負ける可能性 が 低い場合 は、余計な試合 がものすごく 多く表示されてしまう ことになります。

そこで、上記の プログラム を修正し、ai11s が 負けた試合だけ を表示するようにします。どのように修正すれば良いかを少し考えてみて下さい。

余計な試合 を 表示しない ようにするために、下記のプログラムの 3 行目 のように、verbose=False を記述して play メソッドを 呼び出す という方法を 思いついた人 が いるかもしれません が、この方法 では、ai11s が 負けた試合 も 表示されなく なります。

mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        break

修正箇所

mb = Marubatsu()
while True:
-   if mb.play([ai10s, ai11s]) == Marubatsu.CIRCLE:
+   if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        break

実行結果

考え方 は 間違っていない のですが、残念ながら、下記のような理由で、verbose=False だけ では、ai11s が 負けた時だけ 試合経過を表示することは できません。

verbose=False は、ゲーム を 開始する前 に指定する必要がある
ai11s が 負けるか どうかは、ゲームが終了 するまで わからない

この 問題を解決 する 方法の一つ は、ゲームを 行う際 に、行われた着手 を 記録しておく という方法です。一般的 に、ゲーム で プレイヤー が行った 行動の記録 の事を棋譜と呼ぶので、本記事でも棋譜という 用語を使う ことにします。

棋譜を 記録しておく ことで、ゲームの終了後 に、新しいゲーム を開始し、その 棋譜通り に 着手を行う ことで、試合経過 を再現することが できます。

〇×ゲーム の棋譜を どのように記録 すればよいかについて少し考えてみて下さい。

まず、棋譜をどのような データ構造 で表現するかを 決める必要 があります。棋譜は、行われた着手 を 順番に並べた ものなので、着手を表す データ を要素として持つ list 使って表現することが できます。

棋譜は、〇×ゲーム に 関するデータ なので、Marubatsu クラスの インスタンス の属性に記録することにします。棋譜の英語は record なので、records という名前にします。

棋譜のような 記録したデータ を代入する 変数の名前 には、他にも history（履歴）や log（記録）などの名前が 良く使われます。

棋譜の 初期化 は、ゲーム の 開始時 に 行う必要 があるので、restart メソッドの中に その処理 を下記のように記述します。

8 行目：records 属性を、空の list で 初期化 する

1   def restart(self):
2       self.initialize_board()
3       self.turn = Marubatsu.CIRCLE     
4       self.move_count = 0
5       self.status = Marubatsu.PLAYING
6       self.last_move = -1, -1          
7       self.last_turn = None
8       self.records = []
9 
10  Marubatsu.restart = restart

行番号のないプログラム

def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    self.status = Marubatsu.PLAYING
    self.last_move = -1, -1          
    self.last_turn = None
    self.records = []

Marubatsu.restart = restart

修正箇所

def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    self.status = Marubatsu.PLAYING
    self.last_move = -1, -1          
    self.last_turn = None
+   self.records = []

Marubatsu.restart = restart

棋譜の更新は、着手の際 に 行う必要 があるので、move メソッドの中に その処理 を下記のように記述します。

8 行目：records 属性の要素に、着手した座標のデータを表す self.last_move を追加する。なお、この部分は、self.records.append((x, y)) と 記述しても良い

 1  def move(self, x, y):
 2      if self.place_mark(x, y, self.turn):
 3          self.last_turn = self.turn
 4          self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
 5          self.move_count += 1
 6          self.status = self.judge()
 7          self.last_move = x, y
 8          self.records.append(self.last_move)
 9           
10  Marubatsu.move = move

行番号のないプログラム

def move(self, x, y):
    if self.place_mark(x, y, self.turn):
        self.last_turn = self.turn
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        self.status = self.judge()
        self.last_move = x, y
        self.records.append(self.last_move)
            
Marubatsu.move = move

修正箇所

def move(self, x, y):
    if self.place_mark(x, y, self.turn):
        self.last_turn = self.turn
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        self.status = self.judge()
        self.last_move = x, y
+       self.records.append(self.last_move)
            
Marubatsu.move = move

上記のように修正することで、ai11s が 負けた時 の棋譜を、下記のプログラムで表示することが できるように なります。

3、4 行目：ai11s が 負けた時に 、棋譜が代入された mb.records を表示する

1  mb = Marubatsu()
2  while True:
3     if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
4          print(mb.records)
5          break

行番号のないプログラム

mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        print(mb.records)
        break

修正箇所

mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
+       print(mb.records)
        break

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

[(1, 1), (0, 2), (2, 0), (2, 1), (1, 0), (2, 2), (1, 2)]

棋譜には、行われた着手 が 順番に記録 されているので、for 文 と move メソッドを利用することで、下記のプログラムのように、ai11s が 負けた時 の 試合経過 を表示することができます。実行結果 から、負けた時 の 試合だけ が表示されることが確認できます。

4 行目：ai11s が 負けた試合 の棋譜を records に代入する
5 行目：棋譜を使って 負けた試合 を再現するために、restart メソッドを呼び出して、ゲーム を リセット する。なお、この処理 を 4 行目より前 に行っては いけない 点に注意する事。その理由は、restart メソッドによって棋譜が リセット されてしまうため、4 行目で records に 空の list が代入されてしまうことになるからである
6 行目：棋譜から順番に着手のデータを 取り出し 、x と y に代入する
7、8 行目：(x, y) のマスに着手を行い、その結果の ゲーム盤 を表示する

1  mb = Marubatsu()
2  while True:
3      if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
4          records = mb.records
5          mb.restart()
6          for x, y in records:
7              mb.move(x, y)
8              print(mb)
9          break

行番号のないプログラム

mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        records = mb.records
        mb.restart()
        for x, y in records:
            mb.move(x, y)
            print(mb)
        break

修正箇所

mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
+       records = mb.records
+       mb.restart()
+       for x, y in records:
+           mb.move(x, y)
+           print(mb)
        break

実行結果

Turn x
...
.O.
...

Turn o
X..
.o.
...

Turn x
x..
.o.
..O

Turn o
x..
.o.
.Xo

Turn x
x.O
.o.
.xo

Turn o
x.o
.o.
Xxo

winner o
x.o
.oO
xxo

特定の AI どうし の対戦で、指定した 結果になる 場合の 試合経過 を表示する際に、毎回上記 のような プログラムを記述する のは大変なので、上記の処理 を行う、下記のような関数を定義する事にします。

名前：試合経過（progress）を表示（show）するので show_progress とする
処理：指定した AI どうし の対戦で、指定した結果の 試合経過 を表示する
入力：仮引数 ai に対戦を行う AI を、winner に 試合結果 を代入する
出力：なし

show_progress は下記のプログラムのように定義します。

1 行目：仮引数 に ai と winner を記述する
2 ~ 10 行目：4 行目以外 は 元のプログラム と同じ
4 行目：play メソッドの 実引数 に ai=ai を記述するように修正し、play メソッドの 返り値 と仮引数 winner が 等しいか どうかを判定するように修正する

 1  def show_progress(ai, winner):
 2      mb = Marubatsu()
 3      while True:
 4          if mb.play(ai=ai, verbose=False) == winner:
 5              records = mb.records
 6              mb.restart()
 7              for x, y in records:
 8                  mb.move(x, y)
 9                  print(mb)
10              break

行番号のないプログラム

def show_progress(ai, winner):
    mb = Marubatsu()
    while True:
        if mb.play(ai=ai, verbose=False) == winner:
            records = mb.records
            mb.restart()
            for x, y in records:
                mb.move(x, y)
                print(mb)
            break

修正箇所

+def show_progress(ai, winner):
    mb = Marubatsu()
    while True:
-       if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
+       if mb.play(ai=ai, verbose=False) == winner:
            records = mb.records
            mb.restart()
            for x, y in records:
                mb.move(x, y)
                print(mb)
            break

ai10s VS ai11s で、ai11s が 負ける試合 は、下記のプログラムで表示できます。実行結果 から、ai11s が 負ける試合 が 正しく表示 できていることが確認できます。

show_progress([ai10s, ai11s], Marubatsu.CIRCLE)

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

Turn x
...
.O.
...

Turn o
X..
.o.
...

Turn x
x..
.o.
..O

Turn o
x..
.o.
.Xo

Turn x
x.O
.o.
.xo

Turn o
x.o
.o.
Xxo

winner o
x.o
.oO
xxo

なお、定義した show_progress は、ai.py に 記述する ことにします。

試合経過の観察を行う前に、同一局面 に関する定義と、その扱い について説明します。

〇×ゲーム の ゲーム盤 は、3 x 3 の 上下左右 が対象となる形状をしています。また、将棋やチェスとは異なり、ゲーム盤 に向きは 存在しません¹。そのようなゲーム盤は、ゲーム盤を 回転させたりする ことで、異なる局面 が 別の局面 と 一致する場合 があります。本記事では そのような局面 のことを 同一局面 と呼ぶことにします。

例えば、下図の 左の局面 を、時計回り に 90 度回転 させると、右の局面 に 一致する ので、この 2 つ は 同一局面 です。

〇×ゲーム の 同一局面 は、以下のように分類できます。

ある局面を 時計回り に 90 度ずつ回転 した局面は 同一局面 ですが、90 度 の回転を 4 回行う と 360 度 になって 元の局面 に もどる ので、回転による 同一局面 は 4 種類 ある事になります。それぞれのマスに 1 ~ 9 までの番号を 割り当てた 場合、回転による 同一局面 は下図の 1 行目 のようになります。なお、下図の 2 行目 は 同一局面 の 具体例 です。

ある直線に対して、両側の形 が 同じ図形 の事を 線対称 な図形と呼びます。線対称 な図形は、その 直線を軸 として、180 度ひっくり返す と、同じ形 の図形になります。

〇×ゲーム の場合は、真ん中のマス を通る、垂直、水平、左上から右下方向、右上から左下方向 の 4 種類 の 直線を軸 として、ゲーム盤 の表裏を ひっくり返した局面 が 同一局面 になります。下図は、左上の局面に対する、4 種類 の 線対称 な 同一局面 です。

上記から、〇×ゲーム では、ある局面 の 同一局面 は、最大で下図の 8 種類 です。

ただし、上記で「最大で」と記述したのは、8 種類 ある 同一局面 の いくつか が、完全に同じ局面 の 場合がある からです。例えば、下図の 1 行目 の局面に対する 同一局面 は 4 種類、2 行目 の局面に対する 同一局面 は 1 種類 しかありません。

〇×ゲームに限らず、ほとんどのゲーム では、同一局面 は、見た目は違う かもしれませんが、ゲームの勝敗 を 考える上 では、同じ局面 と みなす ことが できます。そこで、本記事 では 同一局面 に対しては、その中の 1 つ の 局面だけ を考慮することで、残りの 同一局面 に対する考慮を 行ったとみなす ことにします。

これまでは、AI どうし の試合の 勝敗の結果 しか 見てきませんでした が、試合の経過を観察し、検証を行うことで、AI が それぞれの局面 で、具体的 に どのように 着手を選択しているかが わかるようになります。また、その 検証を行う ことで、ルール の条件の 問題点 や、その問題点の 解決法 が わかるようになる 場合があります²。そこで、上記の ai10s VS ai11s の 試合経過 を観察し、a11s の 問題点 を検証することにします。

わかりやすいように、先程の 試合経過 を図で表現します。下図は、黄色のマス が着手を行ったマスを、上に表示 されているのはその 着手を行った AI を表します。

まず、ai10s と ai11s が それぞれの局面 に対して、どのような判断 に基づいて 着手を選択 したかについて検証することにします。

ルール 10 の 最も優先順位 が 高い条件 は、「真ん中 のマスに 優先的 に着手する」なので、1 手目 で ai10 は 必ず真ん中 の (1, 1) のマスに着手を 行うはず です。上記の試合でも、実際に そのような着手 が 行われています。

1 手目 で 真ん中のマス に着手が 行われた ので、以後は ai10s も ai11s も、最も高い 評価値が計算される 合法手を選択 します。

2 手目 で ai11s は (0, 0) のマスに着手していますが、このマスが 選択された理由 を、それぞれの 合法手 に着手した局面の 評価値 が どのように計算された かを、ルールに基づいて 実際に 調べる ことで検証することにします。

ai11s が、それぞれの 合法手 に対して計算する 評価値 は、下記のプログラムのように、実引数 に debug=True を記述して ai11s を 呼び出す ことで 表示する ことが できます。

2 行目：2 手目 を 着手する前 の局面を作る
3 行目：その局面 に対して、ai11s を、デバッグ表示を行う ように debug=True を 実引数に記述 して 呼び出す

mb = Marubatsu()
mb.move(1, 1)
ai11s(mb, debug=True)

実行結果

Start ai_by_score
Turn x
...
.O.
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn o
X..
.o.
...

score -1 best score -inf
UPDATE
  best score -1
  best moves [(0, 0)]
====================
move (1, 0)
Turn o
.X.
.o.
...

score -2 best score -1
====================
move (2, 0)
Turn o
..X
.o.
...

score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0)]
====================
move (0, 1)
Turn o
...
Xo.
...

score -2 best score -1
====================
move (2, 1)
Turn o
...
.oX
...

score -2 best score -1
====================
move (0, 2)
Turn o
...
.o.
X..

score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0), (0, 2)]
====================
move (1, 2)
Turn o
...
.o.
.X.

score -2 best score -1
====================
move (2, 2)
Turn o
...
.o.
..X

score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0), (0, 2), (2, 2)]
====================
Finished
best score -1
best moves [(0, 0), (2, 0), (0, 2), (2, 2)]

下記はそれぞれの 合法手 を 着手した際 の 評価値 です。

合法手	(0, 0)	(1, 0)	(2, 0)	(0, 1)	(2, 1)	(0, 2)	(1, 2)	(2, 2)
評価値	-1	-2	-1	-2	-2	-1	-2	-1

評価値 の 最大値 は -1 なので、評価値 が -1 である (0, 0)、(2, 0)、(0, 2)、(2, 2) の中から ランダム に着手が 選択される ことが分かります。そのことは、下記の 実行結果 の 最後の 2 行 からも確認できます。

best score -1
best moves [(0, 0), (2, 0), (0, 2), (2, 2)]

実際に 行われた着手 である (0, 0) は、その 4 つ の 候補の中 に 入っている ので、(0, 0) が 着手された理由 が確認できました。

2 手目 の 合法手 は、真ん中のマス を 除いた 8 マス がありますが、隅のマス に着手した場合は、ゲーム盤 を回転することで (0, 0) のマスに着手した場合と 同一局面 になります。同様に、辺のマスに着手した場合は、ゲーム盤 を回転することで (1, 0) のマスに着手した場合と 同一局面 になります。下図はそのことを表した図です。

また、実際に 隅に着手 した場合の 評価値 は すべて -1 に、辺に着手 した場合の 評価値 は すべて -2 になっていることから、同一局面 に対する 評価値 が 同じになる ことが確認できます。従って、上記の表 を、下記のように まとめる ことが できます。

合法手	評価値
隅の 4 マス	-1
辺の 4 マス	-2

ai11s(mb, debug=True) の 実行結果 の表示には、それぞれの 合法手 を着手した局面の 評価値 は 表示されます が、その評価値が どのように計算されたか は 表示されません。そこで、下記のプログラムのように、ai11s が 評価値 を 計算する際 に利用する、マークのパターン の数を表示するように ai11s を修正 することにします。

8、9 行目：仮引数 debug が True の場合に、count_markpats が計算した、マークのパターン を表示するように修正する

 1  from pprint import pprint
 2  from ai import ai_by_score
 3  from marubatsu import Markpat
 4
 5  def ai11s(mb, debug=False):
 6     def eval_func(mb):      
元と同じなので省略
 7         markpats = mb.count_markpats()
 8         if debug:
 9             pprint(markpats)
10          # 相手が勝利できる場合は評価値として -100 を返す
11          if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
12              return -100
元と同じなので省略

行番号のないプログラム

from pprint import pprint
from ai import ai_by_score
from marubatsu import Markpat

def ai11s(mb, debug=False):
    def eval_func(mb):      
        # 真ん中のマスに着手している場合は、評価値として 300 を返す
        if mb.last_move == (1, 1):
            return 300
    
        # 自分が勝利している場合は、評価値として 200 を返す
        if mb.status == mb.last_turn:
            return 200

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 100 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 100

        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        
        # 次の自分の手番で自分が勝利できる場合は評価値に 1 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += 1
        # 「自 1 敵 0 空 2」の数だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)]
        # 「自 0 敵 1 空 2」の数だけ、評価値を減算する
        score -= markpats[Markpat(last_turn=0, turn=1, empty=2)]
        
        # 計算した評価値を返す
        return score

    return ai_by_score(mb, eval_func, debug=debug)

修正箇所

from pprint import pprint
from ai import ai_by_score
from marubatsu import Markpat

def ai11s(mb, debug=False):
    def eval_func(mb):      
元と同じなので省略
        markpats = mb.count_markpats()
+       if debug:
+           pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
元と同じなので省略

上記の修正 を行うことで、先程と同じ 下記のプログラムを実行すると、評価値 を 表示する直前 に、マークのパターンの数 が表示されるようになります。

mb = Marubatsu()
mb.move(1, 1)
ai11s(mb, debug=True)

実行結果

略
move (0, 0)
Turn o
X..
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -inf
略

実行結果の全体（長いのでクリックして表示して下さい）

Start ai_by_score
Turn x
...
.O.
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn o
X..
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -inf
UPDATE
  best score -1
  best moves [(0, 0)]
====================
move (1, 0)
Turn o
.X.
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (2, 0)
Turn o
..X
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0)]
====================
move (0, 1)
Turn o
...
Xo.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (2, 1)
Turn o
...
.oX
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (0, 2)
Turn o
...
.o.
X..

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0), (0, 2)]
====================
move (1, 2)
Turn o
...
.o.
.X.

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (2, 2)
Turn o
...
.o.
..X

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0), (0, 2), (2, 2)]
====================
Finished
best score -1
best moves [(0, 0), (2, 0), (0, 2), (2, 2)]

ai9s、ai10s も下記のプログラムのように、同様の方法 で修正することにします。

ai9s（長いのでクリックして表示して下さい）

def ai9s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 4 を返す
        if mb.last_move == (1, 1):
            return 4
    
        # 自分が勝利している場合は、評価値として 3 を返す
        if mb.status == mb.last_turn:
            return 3

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値として -1 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -1
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 2 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 2
        # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            return 1
        # それ以外の場合は評価値として 0 を返す
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

修正箇所

def ai9s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 4 を返す
        if mb.last_move == (1, 1):
            return 4
    
        # 自分が勝利している場合は、評価値として 3 を返す
        if mb.status == mb.last_turn:
            return 3

        markpats = mb.count_markpats()
+       if debug:
+           pprint(markpats)
        # 相手が勝利できる場合は評価値として -1 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -1
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 2 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 2
        # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            return 1
        # それ以外の場合は評価値として 0 を返す
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)

ai10s（長いのでクリックして表示して下さい）

def ai10s(mb, debug=False):
    def eval_func(mb):      
        # 真ん中のマスに着手している場合は、評価値として 300 を返す
        if mb.last_move == (1, 1):
            return 300
    
        # 自分が勝利している場合は、評価値として 200 を返す
        if mb.status == mb.last_turn:
            return 200

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 100 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 100

        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        
        # 次の自分の手番で自分が勝利できる場合は評価値に 1 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += 1
        # 「自 1 敵 0 空 2」の数だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)]
        
        # 計算した評価値を返す
        return score

    return ai_by_score(mb, eval_func, debug=debug)

修正箇所

def ai10s(mb, debug=False):
    def eval_func(mb):      
        # 真ん中のマスに着手している場合は、評価値として 300 を返す
        if mb.last_move == (1, 1):
            return 300
    
        # 自分が勝利している場合は、評価値として 200 を返す
        if mb.status == mb.last_turn:
            return 200

        markpats = mb.count_markpats()
+       if debug:
+           pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 100 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 100

        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        
        # 次の自分の手番で自分が勝利できる場合は評価値に 1 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += 1
        # 「自 1 敵 0 空 2」の数だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)]
        
        # 計算した評価値を返す
        return score

    return ai_by_score(mb, eval_func, debug=debug)

下記は修正した ai11s の一部を再掲したプログラムです。先程は、下記のプログラムの 12 行目 の debug が、1 行目 の ai11s の 仮引数 debug と 同じものである として説明を行いましたが、12 行目 の debug は、グローバル関数 である ai11s の ブロックの中 に記述されてはいますが、同時に ローカル関数 である eval_func の ブロックの中 にも記述されています。そこで、ローカル関数の中 で行われる 名前解決 について説明します。

 1  def ai11s(mb, debug=False):
 2      def eval_func(mb):      
 3          # 真ん中のマスに着手している場合は、評価値として 300 を返す
 4          if mb.last_move == (1, 1):
 5              return 300
 6     
 7          # 自分が勝利している場合は、評価値として 200 を返す
 8          if mb.status == mb.last_turn:
 9              return 200
10
11          markpats = mb.count_markpats()
12          if debug:
13              pprint(markpats)
略

下図は、ai11s の グローバルスコープ と ローカルスコープ を図示したものです。図のように、グローバル関数 である ai11 の中 に定義された ローカル関数 eval_func に対しても ローカルスコープ が作られ、3 種類 の スコープ は 入れ子 の構造になります。

上図の、水色の ローカル関数 の ローカルスコープ内 での 名前解決 の手順は、難しそうに思えるかも しれませんが、実際には以前の記事で説明した 手順と同じ です。

ローカル関数 の ブロックの中 で 代入処理 が行われた場合は、以前の記事で説明した場合と同様に、その関数 の ローカル名前空間 が管理する名前に 値が代入 されます。

ローカル関数 の ブロックの中 で 変数の値 が参照された場合は、以前の記事で説明した 下記の手順 と 同じ手順 で 名前解決 が行われます。

名前が記述されている 式をスコープ とする 入れ子 になった 名前空間 のうち、最も内側にある 名前空間を選択する
選択した名前空間の中から 名前を探す
名前が 見つかった 場合は、その名前空間を使って、名前からオブジェクトを 対応づける
名前が 見つからなかった 場合は、一つ外側 の名前空間を選択して、手順 2 へ戻る
手順 4 で、外側の名前空間が 存在しない場合 は、NameError という エラーが発生 する

この手順 に従って、下記の 12 行目 の debug の 名前解決 は、下記の手順 で行われます。

12 行目 の debug をスコープとする 最も内側 の 名前空間 は、ローカル関数 eval_func の 名前空間 である
12 行目 の debug は、ローカル関数 eval_func の 名前空間 に 登録されていない
1 つ外側 の 名前空間 は、グローバル関数 ai11s が管理する 名前空間 である
ai11s の 仮引数 debug は ai11s の 名前空間 に 登録されている ので、名前がみつかる
ai11s の ローカル変数 debug の値を使って、12 行目 の処理が 行われる

 1  def ai11s(mb, debug=False):
 2      def eval_func(mb):      
 3          # 真ん中のマスに着手している場合は、評価値として 300 を返す
 4          if mb.last_move == (1, 1):
 5              return 300
 6     
 7          # 自分が勝利している場合は、評価値として 200 を返す
 8          if mb.status == mb.last_turn:
 9              return 200
10
11          markpats = mb.count_markpats()
12          if debug:
13              pprint(markpats)
略

グローバル変数 と ローカル変数 が 同じ名前 であっても 異なる変数 であるように、「グローバル関数 の ローカル変数」と、そのグローバル関数の中で定義された「ローカル関数 の ローカル変数」は、同じ名前 であっても 異なる変数 である。

例えば、上記のプログラムの場合、ai11s の ローカル変数 mb と、eval_func の ローカル変数 mb は 同じ名前 であっても、異なる変数 です。

「グローバル関数 の ローカル変数」と、そのグローバル関数の中で定義された「ローカル関数 の ローカル変数」の関係は、グローバル変数 と ローカル変数 の関係に 似ています。

global と nonlocal を使うと バグが発生しやすくなる ので、特別な理由 がない限り、あまり 使わないほうが良い でしょう。本記事 でも nonlocal を利用する 予定はない ので、この部分は 興味がない方 は 読み飛ばして も 構いません。

以前の記事で、関数のブロック の中で、global 変数名 を記述することで、その変数 が グローバル変数 と みなされるようになる ことを説明しました。

ローカル関数 の場合は、その外側に グローバル名前空間 と グローバル関数のローカル名前空間 があるので、global 変数名 だけでは、そのうちの グローバル名前空間 にしか 対応できません。そのため、Python では、nonlocal 変数名 を記述することで、その 変数名 を 一つ外側 の 名前空間に登録 された名前と みなす ことができるようになっています。

下記は global と nonlocal を利用した例です。処理の内容 は、コメント を見て下さい。

a = 1 # グローバル変数 a に 1 を代入する
b = 2 # グローバル変数 b に 2 を代入する

def x():
    def y():
        global b                 # b をグローバル変数とみなす
        print("global b =", b)   # グローバル変数 b を表示する

    def z():
        nonlocal b               # b を 1 つ外側の名前空間である x のローカル変数とみなす
        print("nonlocal b =", b) # x のローカル変数 b を表示する

    global a                # a をグローバル変数とみなす
    print("global a =", a)  # グローバル変数 a を表示する
    b = 3                   # 関数 x のローカル変数 b に 3 を代入する
    y()                     # ローカル関数 y を呼び出す
    z()                     # ローカル関数 z を呼び出す
      
x() # 関数 x を呼び出す

実行結果

global a = 1
global b = 2
nonlocal b = 3

global と nonlocal の詳細については、下記のリンク先を参照して下さい。

下記は、先程実行した ai11s(mb, debug=True) の 実行結果 を元に、それぞれの 合法手 に着手を行った局面の マークのパターン の数と、評価値 を 表にまとめた ものです。

表のそれぞれの意味は以下の通りです。なお、以後は、合法手 を表の 左の列の番号 を使って、合法手 1 のように表記することにします。

1 行目 では、マークのパターン 「自 x 敵 y 空 z」を「xyz」のように表記する
2 行目 は、それぞれの マークのパターン に対する 評価値 を表す
3 行目以降 の ゲーム盤の図 では、着手を行った 合法手 のマスを水色で表示する。また、同一局面 のうちの 1 つのみ を表示する

		「201」	「021」	「102」	「012」	評価値
	評価値	1：`+1` 2~：`100`	`-100`	1 つで `+1`	1 つで `-1`
1				2	3	-1
2				1	3	-2

表から、どの合法手 に着手しても、相手が有利 になる「自 0 敵 1 空 2」の数は同じですが、自分が有利 になる「自 1 敵 0 空 2」の数は、隅に着手 したほうが 多くなり、その結果、隅に着手したほうが 評価値 が 高くなる ことが分かりました。そのことは、下記の 実行結果 の 最後の 2 行 からも確認できます。従って、この局面 では、ai11s は 100 % 隅のマス に着手を行います。また、実際に ai11s は 隅のマス に着手を 行っています。

best score -1
best moves [(0, 0), (2, 0), (0, 2), (2, 2)]

このように、ai11s が 具体的 に どのように 評価値を 計算しているか を検証することで、ai11s が 選択した着手 の根拠が明確になります。また、その結果、AI が 意図通り の処理を行うことを確認できたり、不具合の原因 を発見したりすることができる場合があります。実際に、上記の場合は、意図通り の処理を 行っていること が確認できます。

本記事 の目的は、ai11s が選択する着手の検証ですが、ai10s の ルール は、ai11s の ルール に かなり似ている ので、ai10s が選択する着手も検証することにします。

2 手目 の検証と同様に、下記のプログラムで ai10s がそれぞれの 合法手 に対してどのような 評価値 を計算するかを表示し、その結果を 表にまとめる ことにします。

1、2 行目：2 手目 の (0, 0) の着手を行い、ai10s を 呼び出す。

mb.move(0, 0)
ai10s(mb, debug=True)

実行結果（長いのでクリックして開いてください）

Start ai_by_score
Turn o
X..
.o.
...

legal_moves [(1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (1, 0)
Turn x
xO.
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 3 best score -inf
UPDATE
  best score 3
  best moves [(1, 0)]
====================
move (2, 0)
Turn x
x.O
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 3
UPDATE
  best score 4
  best moves [(2, 0)]
====================
move (0, 1)
Turn x
x..
Oo.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 3 best score 4
====================
move (2, 1)
Turn x
x..
.oO
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 4
APPEND
  best moves [(2, 0), (2, 1)]
====================
move (0, 2)
Turn x
x..
.o.
O..

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 4
APPEND
  best moves [(2, 0), (2, 1), (0, 2)]
====================
move (1, 2)
Turn x
x..
.o.
.O.

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 4
APPEND
  best moves [(2, 0), (2, 1), (0, 2), (1, 2)]
====================
move (2, 2)
Turn x
x..
.o.
..O

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 5,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 5 best score 4
UPDATE
  best score 5
  best moves [(2, 2)]
====================
Finished
best score 5
best moves [(2, 2)]

下記は、上記の結果 を まとめた表 です。なお、ルール 10 は、「自 0 敵 2 空 1」に関する条件は ありません ので、先程の表と異なり、「012」の列は 存在しません。また、先程は、同一局面を 1 つにまとめると説明しましたが、同一局面 が 2 つの場合 は、両方表記 したほうが 分かりやすい 気がしましたので、下図では 同一局面 を 横に並べて表記 します。

		「201」	「021」	「102」	評価値
	評価値	1：`+1` 2~：`100`	`-100`	1 つで `+1`
1		1		2	3
2		1		3	4
3		1		3	4
4				5	5

表から、ai10s が実際に着手を行った、合法手 4 の (2, 2) に着手した場合の 評価値 が 5 で 最も高くなる ことが確認できました。そのことは、下記の 実行結果 の 最後の 2 行 からも確認できます。従って、この局面 では、ai10s は 100 % (2, 2) に着手を行います。

best score 5
best moves [(2, 2)]

合法手 4 には「自 2 敵 0 空 1」は 存在しません が、それが 1 つ存在 する 合法手 2、3 と比較して、自分が有利になる「自 1 敵 0 空 2」が 2 つ多い ので、合法手 4 を選択することは、ルール 10 の 意図通り と 言える でしょう。

これまで と同様に、下記のプログラムで ai11s がそれぞれの 合法手 に対して どのように 評価値を計算するかを表示し、その結果を 表にまとめます。

mb.move(2, 2)
ai11s(mb, debug=True)

実行結果（長いのでクリックして開いてください）

Start ai_by_score
Turn x
x..
.o.
..O

legal_moves [(1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2)]
====================
move (1, 0)
Turn o
xX.
.o.
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 4,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -2 best score -inf
UPDATE
  best score -2
  best moves [(1, 0)]
====================
move (2, 0)
Turn o
x.X
.o.
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -1 best score -2
UPDATE
  best score -1
  best moves [(2, 0)]
====================
move (0, 1)
Turn o
x..
Xo.
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 4,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -2 best score -1
====================
move (2, 1)
Turn o
x..
.oX
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1})
score -1 best score -1
APPEND
  best moves [(2, 0), (2, 1)]
====================
move (0, 2)
Turn o
x..
.o.
X.o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(2, 0), (2, 1), (0, 2)]
====================
move (1, 2)
Turn o
x..
.o.
.Xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1})
score -1 best score -1
APPEND
  best moves [(2, 0), (2, 1), (0, 2), (1, 2)]
====================
Finished
best score -1
best moves [(2, 0), (2, 1), (0, 2), (1, 2)]

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

表から、合法手 2 と 3 の 評価値 が -1 で 最も高い ことが分かります。そのことは、下記の 実行結果 の 最後の 2 行 からも確認できます。

best score -1
best moves [(2, 0), (2, 1), (0, 2), (1, 2)]

合法手 2 と 3 の着手はそれぞれ 2 通りずつ あるので、合法手 3 と 合法手 4 の着手が行われる確率は、それぞれ 2 / 4 = 50 % であることが分かります。従って、この局面 では、50 % の確率で、合法手 2 または 合法手 3 の着手が 行われる ことが分かります。実際の対戦 で ai11s が 合法手 3 の (1, 2) に 着手を行った のは、50 % の確率 で 行われた からです。

また、合法手 2 と 3 の 評価値 が同じになる理由は、「自 2 敵 0 空 1」と「自 1 敵 0 空 2」の数の合計が 等しい からであることが確認できました。これは、ルール 11 の 意図通り の計算です。

これまで と同様に、下記のプログラムで ai10s がそれぞれの 合法手 に対して どのように 評価値を計算するかを表示し、その結果を 表にまとめます。

mb.move(1, 2)
ai10s(mb, debug=True)

実行結果（長いのでクリックして開いてください）

Start ai_by_score
Turn o
x..
.o.
.Xo

legal_moves [(1, 0), (2, 0), (0, 1), (2, 1), (0, 2)]
====================
move (1, 0)
Turn x
xO.
.o.
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 2})
score 3 best score -inf
UPDATE
  best score 3
  best moves [(1, 0)]
====================
move (2, 0)
Turn x
x.O
.o.
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 3,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 100 best score 3
UPDATE
  best score 100
  best moves [(2, 0)]
====================
move (0, 1)
Turn x
x..
Oo.
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 3,
             Markpat(last_turn=2, turn=0, empty=1): 1,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 3 best score 100
====================
move (2, 1)
Turn x
x..
.oO
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 100 best score 100
APPEND
  best moves [(2, 0), (2, 1)]
====================
move (0, 2)
Turn x
x..
.o.
Oxo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1,
             Markpat(last_turn=2, turn=1, empty=0): 2})
score 3 best score 100
====================
Finished
best score 100
best moves [(2, 0), (2, 1)]

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

		「201」	「021」	「102」	評価値
	評価値	1：`+1` 2~：`100`	`-100`	1 つで `+1`
1				3	3
2		2		1	100
3		1		2	3
4		2		1	100
5		1		2	3

表から、ai10s は、最も評価値 が高い、合法手 2 と 4 の いずれかの着手 を行うことが分かり、そのことは、下記の 実行結果 の 最後の 2 行 からも確認できます。実際に ai10s はそのうちの片方である 合法手 2 を選択しました。

best score 100
best moves [(2, 0), (2, 1)]

合法手 2 または 4 の着手を行うことで、「自 2 敵 1 空 0」が 2 つ存在 するようになるので、次の手番 で ai10s が 必ず勝利 できるようになります。従って、この後 の ai11s の着手に 関わらず、この時点 で ai10s の 勝利が確定 し、実際の対戦 でも ai10s が勝利しています。そのため、この後 の 着手の検証 を 行う必要はない でしょう。

上記の検証 から、ai10s VS ai11s で行われる着手の選択は、下図のようになることが分かります。なお、同一局面 がある場合は、そのうちの一つ の 局面のみ を表示します。

図から わかる ように、ai10s VS ai11s では、3 手目まで は、必ず上図 と 同一局面 になるような着手が 行われます。4 手目 の ai11s の着手で、50 % の確率で 異なる着手 が選択されます。4 手目 で図の 上の着手 が 行われた場合 は、5 手目 で ai10s が 2 通り の着手を行う 可能性 がありますが、何れの場合 でも ai10s が 100 % 勝利 します。

上記から、以下の事 が分かります。

3 手目 までは、常に同一局面 になる着手が行われる
4 手目 で ai11s は、それぞれ 50 % の確率で 2 通り の着手を行う
4 手目 の ai11s が、図の 上の着手 を行った場合は、ai10s が 必ず勝利 する。

このことから、ai10s VS ai11s の対戦で、ai11s が敗北するのは、4 手目 で図の 上の着手 を 行う可能性がある ためであることが推測されます。

なお、4 手目 の ai11s の着手で、図の 下の着手 が行われた場合に どうなるか は、その検証をまだ 行っていない ので 現時点 では わかりません。

長くなったので今回の記事はここまでにします。次回の記事では、図の 下の着手 が行われた場合の検証と、ai11s が図の 上の着手 を 行わないようにする ことで、ai10s に 負けないよう に修正する方法について説明します。

今回の記事では、ai10s VS ai11s で ai11s が 負ける原因 を 調べるため に、試合の棋譜を記録するように Marubatsu クラスを修正しました。また、その後で、特定の AI どうし で、特定の結果 になる 試合経過 を 表示する関数 を定義しました。

また、その 関数を利用 して、ai10s VS ai11s で行われる着手が どのように選択されるか を検証し、ai11s が 敗北する原因 となる 可能性が高い着手 を発見しました。

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

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

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

1：+1
2~：100

将棋やチェスでは、それぞれの プレイヤー は、特定の方向 から ゲーム盤 を 見ます。そのため、ゲーム盤 を回転したりすると、同一局面 では なくなります ↩
もちろん、検証しても、問題点や解決法が わからない場合 もあります ↩