Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その56　棋譜の記録と、問題のある試合経過の検証

Last updated at Posted at 2024-02-22

目次と前回の記事

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

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

これまでに作成した AI

これまでに作成した 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 あり

ai11s の問題点

前回の記事では、ルール 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 の 強さの確認 は、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 メソッドの修正

棋譜 の 初期化 は、ゲーム の 開始時 に 行う必要 があるので、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 メソッドの修正

棋譜 の 更新 は、着手の際 に 行う必要 があるので、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 の 上下左右 が 対象 となる 形状 をしています。また、将棋やチェスとは異なり、ゲーム盤 に 向き は 存在しません1。そのようなゲーム盤は、ゲーム盤を 回転させたりする ことで、異なる局面 が 別の局面 と 一致する場合 があります。本記事では そのような局面 のことを 同一局面 と呼ぶことにします。

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

同一局面の種類

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

回転による同一局面

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

線対称な同一局面

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

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

同一局面の一覧

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

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

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

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

試合経過の観察と検証

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

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

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

1 手目の検証

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

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

2 手目の検証

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 種類 の スコープ は 入れ子 の 構造 になります。

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

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

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

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

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

  1. 12 行目 の debug をスコープとする 最も内側 の 名前空間 は、ローカル関数 eval_func の 名前空間 である
  2. 12 行目 の debug は、ローカル関数 eval_func の 名前空間 に 登録されていない
  3. 1 つ外側 の 名前空間 は、グローバル関数 ai11s が管理する 名前空間 である
  4. ai11s の 仮引数 debug は ai11s の 名前空間 に 登録されている ので、名前がみつかる
  5. 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

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 が 意図通り の処理を行うことを 確認 できたり、不具合の原因 を 発見 したりすることができる場合があります。実際に、上記 の場合は、意図通り の処理を 行っていること が 確認 できます。

3 手目の検証

本記事 の 目的 は、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 の 意図通り と 言える でしょう。

4 手目の検証

これまで と 同様 に、下記のプログラムで 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)]

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

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

表から、合法手 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 の 意図通り の 計算 です。

5 手目の検証

これまで と 同様 に、下記のプログラムで 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 で行われる 着手 の 選択 は、下図 のようになることが分かります。なお、同一局面 がある場合は、そのうちの一つ の 局面のみ を 表示 します。

図 から わかる ように、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. 将棋やチェスでは、それぞれの プレイヤー は、特定の方向 から ゲーム盤 を 見ます。そのため、ゲーム盤 を 回転 したりすると、同一局面 では なくなります ↩

  2. もちろん、検証しても、問題点や解決法が わからない場合 もあります ↩

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

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?