Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
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を一から作成する　その62　条件の統合と乱数の種によるプログラムの再現性

Last updated at Posted at 2024-03-14

目次と前回の記事

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

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

これまでに作成した 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」が 最も少ない 着手を行う
そうでない場合は ランダム なマスに 着手 する
ルール12 真ん中 のマスに 優先的 に 着手 する
そうでない場合は 勝てる場合 に 勝つ
そうでない場合は 相手 が 勝利できる 着手を 行わない
そうでない場合は、次 の 自分の手番 で 必ず勝利できる ように、「自 2 敵 0 空 1」が 2 つ以上存在する 局面になる着手を行う
そうでない場合は、斜め方向 に 〇×〇 が 並び、他の 6 マス が 空のマス の場合に、いずれか の 辺のマス に着手を行う
そうでない場合は、以下 の 3 つを 総合的に判断 して着手を行う
  • 次 の 自分の手番 で 勝利できる ように、「自 2 敵 0 空 1」が 1 つ存在する 局面になる着手を行う
  • 自分 が 有利になる ように、「自 1 敵 0 空 2」が 最も多い 着手を行う
  • 相手 が 不利になる ように、「自 0 敵 1 空 2」が 最も少ない 着手を行う
そうでない場合は ランダム なマスに 着手 する

ルール 11、12 で 評価値を計算 する際の パラメータ は以下の通りです。

ai11s
ver 1		 ai11s
ver 2		 ai11s ver 3
ai12s
「自 2 敵 0 空 1」が 1 つの場合の評価値 1 2 2
「自 1 敵 0 空 2」が 1 つあたりの評価値 1 1 0.5
「自 0 敵 1 空 2」が 1 つあたりの評価値 -1 -1 1

基準となる 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 ver 1 98.1 0.0 1.9 82.5 1.9 15.6 90.3 1.0 8.7 あり
ai11s ver 2 98.8 0.0 1.2 87.7 2.4 10.0 93.2 1.2 5.6
ai11s ver 3 99.1 0.0 0.9 87.7 0.8 11.5 93.4 0.4 6.2
ai12s 98.9 0.0 1.1 88.2 0.0 11.8 93.5 0.0 6.5

前回の記事のおさらい

前回の記事で、ルールベースの AI として、ai12s という、弱解決の AI が完成しました。

今回の記事から、ルールベースの AI に関するいくつかの 補足説明 を行います。

ルールの条件の統合

ルールベースの AI は、ルール の 条件 が増えれば 増えるほど、複雑になる ため、わかりづらく なったり、複数の条件 の間で 矛盾が生じたりする ようになります。そのため、なるべく 条件の数 が 少ない ほうが 望ましい と言えるので、複数の条件 の中で、一つにまとめる ことが できる ものがあれば、それらを 統合 したほうが 良いでしょう。

ルール 12 の条件の統合

実は、ルール 12 の 条件 の中の、最初の「真ん中 のマスに 優先的 に 着手 する」という 条件 は、ルール 12 の 下記の条件 があれば 削除 しても 真ん中 のマスに 優先的 に 着手 が 行われる ので、下記の条件 に 統合 することが できます。

  • 次 の 自分の手番 で 勝利できる ように、「自 2 敵 0 空 1」が 1 つ存在する 局面になる着手を行う
  • 自分 が 有利になる ように、「自 1 敵 0 空 2」が 最も多い 着手を行う
  • 相手 が 不利になる ように、「自 0 敵 1 空 2」が 最も少ない 着手を行う

統合できる理由 について 説明 します。

ai12s の修正と確認

まず、下記 のプログラムのように、ai12s から、「真ん中 のマスに 優先的 に 着手 する」という 条件を処理 する 部分を削除 します。以後は、修正前 の ai12s を ai12s ver1、修正後 を ai12s ver 2 と 表記 することにします。

from marubatsu import Markpat, Marubatsu
from ai import ai_by_score
from pprint import pprint

def ai12s(mb, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):      
        # ここにあった、真ん中のマスに着手した場合に評価値として 400 を返す処理を削除する
        
        # 自分が勝利している場合は、評価値として 300 を返す
        if mb.status == mb.last_turn:
            return 300
元と同じなので省略
プログラム全体 
from marubatsu import Markpat, Marubatsu
from ai import ai_by_score
from pprint import pprint

def ai12s(mb, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):      
        # 自分が勝利している場合は、評価値として 300 を返す
        if mb.status == mb.last_turn:
            return 300

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 200 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 200
        
        # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が
        # 配置されている場合は評価値として 100 を返す
        if mb.board[1][1] == Marubatsu.CROSS and \
           (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
            mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
           (mb.board[1][0] == Marubatsu.CROSS or \
            mb.board[0][1] == Marubatsu.CROSS or \
            mb.board[2][1] == Marubatsu.CROSS or \
            mb.board[1][2] == Marubatsu.CROSS) and \
           mb.move_count == 4:
            return 100              

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

    return ai_by_score(mb, eval_func, debug=debug)
修正箇所 
from marubatsu import Markpat, Marubatsu
from ai import ai_by_score
from pprint import pprint

def ai12s(mb, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):      
        # 真ん中のマスに着手している場合は、評価値として 400 を返す
-       if mb.last_move == (1, 1):
-           return 400
            
        # 自分が勝利している場合は、評価値として 300 を返す
        if mb.status == mb.last_turn:
            return 300
元と同じなので省略

次に、ai12s ver 2 が、真ん中のマス に 優先的 に 着手を行う ことを 検証 します。そのためには、〇 の手番 と × の手番 の それぞれを担当 する場合の 最初の手番 である、ゲーム開始時 の 局面 と、2 手目 の 局面 について 調べる必要 が あります。

ゲーム開始時の局面での ai12s ver 2 の合法手の選択の検証

ゲーム開始時 に ai12s ver 2 が 選択 する 合法手 を 下記 のプログラムで 検証 します。

mb = Marubatsu()
ai12s(mb, debug=True)
実行結果（長いのでクリックして開いてください） 
Start ai_by_score
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..
...
...

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

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

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

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

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

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

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

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

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

下記は、上記の結果 を まとめた表 です。なお、表の それぞれの合法手 には 1 つの局面 の 図 しか 表記 していませんが、合法手 2 と 3 にはそれぞれ 4 つの同一局面 が 存在 します。

「201」 「021」 「102」 「012」 評価値
評価値 1：+2
2~：200 		-100 1 つで
+0.5 		1 つで
-1
1 4 2
2 隅のマス
 3 1.5
3 辺のマス
 2 1

上記の表 から、真ん中 の (1, 1) のマスを表す 合法手 1 の 評価値 が 2 で 最も高くなる ことがわかります。そのことは、下記の 実行結果 の 最後の 2 行 からも 確認 できます。

best score 2.0
best moves [(1, 1)]

また、下記の性質 から、ai12s ver 2 の パラメータ を どのように設定 しても、真ん中のマスを 表す 合法手 1 の 評価値のみ が 最も高くなる ことが わかります。

  • 3 つの合法手 はいずれも、「自 1 敵 0 空 2」の マークのパターンのみ が 存在 する
  • 「自 1 敵 0 空 2」の マークのパターン の 数 は、合法手 1 のみ が 最も大きい
  • 以前の記事 で説明したように、「自 1 敵 0 空 2」の マークのパターン の パラメータ は、正の値 である 必要がある

上記から、ai12s ver 2 は、〇 の 最初の手番 である ゲーム開始時 の 局面 で、真ん中のマス に 優先的 に 着手を行う ことが 確認 できました。

2 手目の局面での ai12s ver 2 の合法手の選択の検証

2 手目の局面 は、同一局面 を 考慮 すると、下記の 3 種類 の 局面 が あります。

このうち、左の局面 は、真ん中 のマスに マークが配置済 なので 検証する必要 は ありません ので、残りの 2 つ の局面で 検証 を行います。

1 手目で隅のマスに 〇 が配置された場合

まず、下記 のプログラムで、1 手目 で 隅のマス に 〇 が配置 された場合を 検証 します。

mb = Marubatsu()
mb.move(0, 0)
ai12s(mb, debug=True)
実行結果（長いのでクリックして開いてください） 
Start ai_by_score
Turn x
O..
...
...

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

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

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

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 4,
             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): 1})
score -1.5 best score -1.0
====================
move (1, 1)
Turn o
o..
.X.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             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})
score -0.5 best score -1.0
UPDATE
  best score -0.5
  best moves [(1, 1)]
====================
move (2, 1)
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): 2})
score -2.0 best score -0.5
====================
move (0, 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): 2,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1.0 best score -0.5
====================
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): 2})
score -2.0 best score -0.5
====================
move (2, 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): 2,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1.0 best score -0.5
====================
Finished
best score -0.5
best moves [(1, 1)]

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

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

上記の表 から、真ん中 の (1, 1) のマスを表す 合法手 3 の 評価値 が -0.5 で 最も高くなる ことが わかります。そのことは、下記の 実行結果 の 最後の 2 行 からも 確認 できます。

best score -0.5
best moves [(1, 1)]

また、下記の性質 から、ai12s ver 2 の パラメータ を どのように設定 しても、真ん中のマスを 表す 合法手 3 の 評価値のみ が 最も高くなる ことが わかります。

  • 3 つ の 合法手 は いずれも、「自 1 敵 0 空 2」と「自 0 敵 1 空 2」の マークのパターンのみ が 存在 する
  • 「自 1 敵 0 空 2」の マークのパターン の 数 は、合法手 3 のみ が 最も大きい
  • 以前の記事 で説明したように、「自 1 敵 0 空 2」の マークのパターン の パラメータ は、正の値 である 必要がある
  • 「自 0 敵 1 空 2」の マークのパターン の 数 は、合法手 3 が 最も小さい
  • 以前の記事 で説明したように、「自 0 敵 1 空 2」の マークのパターン の パラメータ は、負の値 である 必要がある

上記の性質 の中で、「自 1 敵 0 空 2」の マークのパターン の 数 が 最大 になる 合法手 が、合法手 3 のみ であるという 性質 が 特に重要 です。この性質 が なければ、合法手 3 以外 の 合法手 も 評価値が最大 になる 可能性が生じる からです。

1 手目で辺のマスに 〇 が配置された場合

次に、下記 のプログラムで、1 手目 で 辺のマス に 〇 が配置 された場合を 検証 します。

mb = Marubatsu()
mb.move(1, 0)
ai12s(mb, debug=True)
実行結果（長いのでクリックして開いてください） 
Start ai_by_score
Turn x
.O.
...
...

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

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 4,
             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): 1})
score 0.0 best score -inf
UPDATE
  best score 0.0
  best moves [(0, 0)]
====================
move (2, 0)
Turn o
.oX
...
...

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

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

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

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 4,
             Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 2})
score -1.0 best score 0.5
====================
move (0, 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): 2,
             Markpat(last_turn=1, turn=0, empty=2): 3})
score -0.5 best score 0.5
====================
move (1, 2)
Turn o
.o.
...
.X.

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 5,
             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): 1})
score -0.5 best score 0.5
====================
move (2, 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): 2,
             Markpat(last_turn=1, turn=0, empty=2): 3})
score -0.5 best score 0.5
====================
Finished
best score 0.5
best moves [(1, 1)]

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

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

上記の表 から、真ん中 の (1, 1) のマスを表す 合法手 3 の 評価値 が 0.5 で 最も高くなる ことがわかります。そのことは、下記の 実行結果 の 最後の 2 行 からも 確認 できます。

best score 0.5
best moves [(1, 1)]

また、下記の性質 から、ai12s ver 2 の パラメータ を どのように設定 しても、真ん中のマスを 表す 合法手 3 の 評価値のみ が 最も高くなる ことが わかります。

  • 3 つ の 合法手 は いずれも、「自 1 敵 0 空 2」と「自 0 敵 1 空 2」の マークのパターンのみ が 存在 する
  • 「自 1 敵 0 空 2」の マークのパターン の 数 は、合法手 3 が 最も大きい
  • 以前の記事 で説明したように、「自 1 敵 0 空 2」の マークのパターン の パラメータ は、正の値 である 必要がある
  • 「自 0 敵 1 空 2」の マークのパターン の 数 は、合法手 3 が 最も小さい
  • 以前の記事 で説明したように、「自 0 敵 1 空 2」の マークのパターン の パラメータ は、負の値 である 必要がある
  • 「自 1 敵 0 空 2」の マークのパターン の 数 が 最大 で、なおかつ「自 0 敵 1 空 2」の マークのパターン の 数 が 最小 なのは、合法手 3 のみ である

上記の性質 は、先程の「1 手目 で 隅のマス に 〇 が配置 された場合」の 性質 と 似ているように見える かもしれませんが、下記 の点で 異なります。

  • 「自 1 敵 0 空 2」の マークのパターン の 数 が 最大 である 合法手 が 複数ある
  • 最後の性質 が 追加 されている

最後の性質 を 追加 したのは、この性質 が なければ、合法手 3 以外 の 合法手 も 評価値が最大 になる 可能性が生じる からです。

以上 の 検証 から、ai12s ver 2 は、× の手番 である 2 手目 の 局面 で、真ん中 の マス に 優先的 に 着手を行う ことが 確認 できました。

先程示したように、1 手目の局面 でも 真ん中 の マス に 優先的 に 着手を行う ので、ai12s ver 2 は、常に真ん中のマス に 優先的 に 着手を行う ことが わかりました。

従って、ルール 12 から「真ん中 のマスに 優先的 に 着手 する」という 条件 を 削除しても、同じ合法手 が 選択される ので、この条件 は 削除 しても かまいません。

ルール 12 改の定義

ルール 12 から「真ん中 のマスに 優先的 に 着手 する」という 条件 を 削除 した、下記のルールを、ルール 12 改 と 定義 する事にします。

順位 条件 種類
1 勝てる場合 に 勝つ 十分条件
2 相手 が 勝利できる 着手を 行わない 必要条件
3 「自 2 敵 0 空 1」が 2 つ以上存在 する着手を行う 十分条件
4 斜め方向 に 〇×〇 が 並び、他の 6 マス が 空のマス の
場合は、いずれか の 辺のマス に着手を行う		 十分条件
5 「自 2 敵 0 空 1」が 1 つ存在 する着手を行う
「自 1 敵 0 空 2」が 最も多い 着手を行う
「自 0 敵 1 空 2」が 最も少ない 着手を行う
6 ランダム なマスに 着手 する

また、それぞれ の 条件 に対する 評価値 は 下記 のようになります。

順位 局面の状況 個別 評価値
1 自分が勝利している 300
3 「自 2 敵 0 空 1」が 2 つ以上存在する 200
4 片方 の 斜め方向 に 〇×〇 が 並び、いずれか の
辺 の 1 つのマスのみ に × が配置 されている		 100
5 「自 2 敵 0 空 1」が 1 つ存在する
「自 1 敵 0 空 2」が x 個存在する
「自 0 敵 1 空 2」が y 個存在する 		2 (0～2)
0.5 * x (0～4)
-y (-8~0)		 -8～6
2 相手が勝利できる -100

ai12s ver 2 が弱解決の AI であることの確認

ai12s ver 2 が 弱解決の AI であることを 確認 するために、下記 のプログラムで、ランダムな着手 を行う ai2 と 対戦 させてみます。

from ai import ai_match, ai2

ai_match(ai=[ai12s, ai2])

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

ai12s VS ai2
count     win    lose    draw
o        9905       0      95
x        8803       0    1197
total   18708       0    1292

ratio     win    lose    draw
o       99.1%    0.0%    0.9%
x       88.0%    0.0%   12.0%
total   93.5%    0.0%    6.5%

実行結果 から、敗率 が 0 % であることが 確認 できたので、ai12s ver 2 は 弱解決の AI である 可能性が高い ことが わかりました。

下記は 上記 の 対戦結果 に、ai12s ver 1 VS ai2 の 対戦結果 を 加えた ものです。対戦成績 は ほぼ同じ なので、ai12s ver 1 と ai12s ver 2 は 同じ合法手 を 選択 する AI である 可能性 が 非常に高い ことが 確認 できました。

関数名 o 勝 o 負 o 分 x 勝 x 負 x 分 勝 負 分
ai12s ver 1 98.9 0.0 1.1 88.2 0.0 11.8 93.5 0.0 6.5
ai12s ver 2 99.1 0.0 0.9 88.0 0.0 12.0 93.5 0.0 6.5

最善手の優劣

これまでの説明では、局面 に 最善手 が 複数存在 した場合は、それらの中 から 同じ確率 で 平等 に、ランダム に 最善手 を 選択 していました。しかし、複数 の 最善手 が 存在 した場合に、その中で 優劣 は 存在しない と 考えて良いでしょうか？最強の AI を 作成 するという 目的だけ を 考える のであれば、最善手 の間に 優劣 は ありません が、別の観点 から 見ると、最善手 の 間 で 優劣 が 存在 する場合が あります。本記事では、必勝の局面 と 必敗の局面 の 2 つの場合1 での、複数の最善手 の間の 違い について説明します。

なお、ここでいう 最善手 とは、演繹法 による 条件 によって、最善手 であることが 保証されている ものの事です。ヒューリスティックスな条件 によって 求められた、評価値 が 最も高い合法手 の事 ではない 点に 注意 して下さい。

必勝の局面での最善手の差異

ルール 12 改 の 条件 の中で、「勝てる場合 に 勝つ」と、『「自 2 敵 0 空 1」が 2 つ以上存在 する着手を行う』という 条件 は、それら を満たす 合法手を選択 することで、必ず勝利できる ので、いずれも 必勝の局面 で 最善手 を 選択 するという 条件 です。ai12s ver 2 では、それらに対する 評価値 を、先程示した表のように、300、200 という、異なる値 を 設定 していたので、それらの条件 を満たす 合法手 が どちらも存在 する場合は、評価値 が 高い 「勝てる場合 に 勝つ」ほうの 合法手 が 選択される ことになります。

しかし、どちらの条件 による 合法手 も 最善手である ことに 変わりはない ので、同じ評価値 を 設定 しても、弱解決の AI であることは 変わりません。そのことを示す ために、その 2 つの条件 の 評価値 を 同じ値 にして ランダムな AI と 対戦 してみることにします。

ai12s の修正

上記の 2 つの 評価値 を 修正 する際に、毎回 ai12s の プログラム を 変更 するのは 大変 なので、「勝てる場合 に 勝つ」と、『「自 2 敵 0 空 1」が 2 つ以上存在 する着手を行う』に対する 評価値 も、パラメータ として 実引数 で 設定できる ように ai12s を 修正する ことにします。また、せっかくなので、他の評価値 も 実引数 で 設定 できるようにします。

それぞれの パラメータを代入 する 仮引数 の名前は、下記 のように 命名 しました。

局面の状況 仮引数の名前 仮引数の名前の由来
自分が勝利している score_victory 勝利を表す victory
「自 2 敵 0 空 1」が
2 つ以上存在する		 score_sure_victory 必勝を表す sure victory
片方 の 斜め方向 に 〇×〇 が
並び、いずれか の 辺 の 1 つの
マスのみ に × が配置 されている		 score_special 特殊を表す special
相手が勝利できる score_defeat 敗北を表す defeat

下記は、上記の 仮引数 を、これまでのパラメータ を デフォルト値 として持つ デフォルト引数 として 追加 した ai12s のプログラムです。

  • 1、2 行目：上記の 仮引数 を デフォルト引数 として追加する
  • 7、14、17、28：返り値 の 値 を 仮引数 に 修正 する
 1  def ai12s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
 2            score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):  3  
 4      def eval_func(mb):         
 5          # 自分が勝利している場合
 6          if mb.status == mb.last_turn:
 7              return score_victory
 8
 9          markpats = mb.count_markpats()
10          if debug:
11              pprint(markpats)
12          # 相手が勝利できる場合
13          if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
14              return score_defeat
15          # 次の自分の手番で自分が必ず勝利できる場合
16          elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
17              return score_sure_victory
18        
19          # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
20          if mb.board[1][1] == Marubatsu.CROSS and \
21             (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
22              mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
23             (mb.board[1][0] == Marubatsu.CROSS or \
24              mb.board[0][1] == Marubatsu.CROSS or \
25              mb.board[2][1] == Marubatsu.CROSS or \
26              mb.board[1][2] == Marubatsu.CROSS) and \
27             mb.move_count == 4:
28              return score_special       
以下同じなので略
行番号のないプログラム 
def ai12s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):         
        # 自分が勝利している場合
        if mb.status == mb.last_turn:
            return score_victory

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return score_defeat
        # 次の自分の手番で自分が必ず勝利できる場合
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return score_sure_victory
        
        # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
        if mb.board[1][1] == Marubatsu.CROSS and \
           (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
            mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
           (mb.board[1][0] == Marubatsu.CROSS or \
            mb.board[0][1] == Marubatsu.CROSS or \
            mb.board[2][1] == Marubatsu.CROSS or \
            mb.board[1][2] == Marubatsu.CROSS) and \
           mb.move_count == 4:
            return score_special    

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

    return ai_by_score(mb, eval_func, debug=debug)
修正箇所 
-def ai12s(mb, score_201=2, score_102=0.5, score_012=-1, debug=False):    
+def ai12s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
+          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):         
        # 自分が勝利している場合
        if mb.status == mb.last_turn:
-           return 300
+           return score_victory

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
-           return -100
+           return score_defeat
        # 次の自分の手番で自分が必ず勝利できる場合
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
-           return 200
+           return score_sure_victory
        
        # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
        if mb.board[1][1] == Marubatsu.CROSS and \
           (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
            mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
           (mb.board[1][0] == Marubatsu.CROSS or \
            mb.board[0][1] == Marubatsu.CROSS or \
            mb.board[2][1] == Marubatsu.CROSS or \
            mb.board[1][2] == Marubatsu.CROSS) and \
           mb.move_count == 4:
-           return -100
+           return score_special    
以下同じなので略

ランダムな AI との対戦

下記 のプログラムで、「自分が勝利 している場合」の 評価値 を、『「自 2 敵 0 空 1」が 2 つ以上存在 する場合』の 評価値 と 同じ 200 に 設定 して、ランダムな AI である ai2 と対戦 してみることにします。以後は、このパラメータ の AI を ai12s ver 3 と 表記 します。

ai_match(ai=[ai12s, ai2], params=[{ "score_victory": 200 }, {}])

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

ai12s VS ai2
count     win    lose    draw
o        9577       0     423
x        8686       0    1314
total   18263       0    1737

ratio     win    lose    draw
o       95.8%    0.0%    4.2%
x       86.9%    0.0%   13.1%
total   91.3%    0.0%    8.7%

実行結果 から、敗率が 0 % であることが 確認 できたので、ai12s ver 3 は 高確率 で 弱解決の AI であると考えることができます。

下記は、これまで の ai12s VS ai2 の 対戦結果 を 加えた ものです。

関数名 o 勝 o 負 o 分 x 勝 x 負 x 分 勝 負 分
ai12s ver 1 98.9 0.0 1.1 88.2 0.0 11.8 93.5 0.0 6.5
ai12s ver 2 98.9 0.0 1.1 88.7 0.0 11.3 93.8 0.0 6.2
ai12s ver 3 95.8 0.0 4.2 86.9 0.0 13.1 91.3 0.0 8.7

上記 の表から、ai12s ver 3 では、それ 以前のバージョンより も 引き分け率 が 高くなる ことがわかります。ai12s ver 3 と、それ 以前のバージョン の 違い は 異なる最善手 を 選択 する 場合がある 点ですが、最善手 を 選択 することに 変わりはない ので、上記のように、引き分け率 が 多くなる のは 明らかに変 です。

実は、この現象 は、筆者 にとっても 想定外の現象 でした。原因 を 調べてみた 所、「自分が勝利 している場合」の 評価値 を、『「自 2 敵 0 空 1」が 2 つ以上存在 する場合』の 評価値 を 同じ値にする ことによって、思わぬバグが発生する ことが わかりました。

この バグの原因 を 調べる方法 は、プログラム の デバッグ の 具体例 として 参考になる のではないかと思いましたので、最善手 の 優劣 の話は、次回の記事 で行うことにし、今回の記事 では、予定を変更 してこのようなことが起きる 原因を検証 することにします。

ai12s ver 3 VS ai2 の検証

以前の記事で説明したように、ランダムな AI は、世の中 に 存在 する すべての AI が 選択する着手 と、まったく同じ着手 を 選択する可能性 があります。そのため、ランダムな AI と 何度も対戦する ことで、理論上 は すべての AI と 1 回以上対戦 することが できます。

従って、ランダムな AI である ai2 と 何度も対戦 した際に、ai12s ver 3 のほうが、ai12s ver 2 より も 引き分け率 が 増えた ことは、ai12s ver 2 が 対戦 すると 勝利 するが、ai12s ver 3 が 対戦 すると 引き分け になる AI が いくつか存在する ことを 意味 します。

そのような AI を 作る ことが できれば、その AI と ai12s ver 2 や ai12s ver 3 との 対戦経過 の 違い を 検証 することで、引き分け が 増えた原因 を 調べる ことが できます。

そのような AI は、下記の手順 で 見つける ことが できます。

  1. 世の中に存在 する AI の中 から ランダム に AI を 一つ選択 する
  2. ai12s ver 2 VS その AI の 対戦 を行い 結果を記録 する
  3. ai12s ver 3 VS その AI の 対戦 を行い 結果を記録 する
  4. 手順 2 と 3 の 対戦結果 が 同じ場合 は 手順 1 に 戻る
  5. 対戦結果 が 異なる場合 は、その AI が 求める AI である

ランダムな AI と 対戦する ということは、世の中に存在 する AI の中 から ランダム に AI を 一つ選択 して 対戦する ことを 意味する ので、上記の 手順 1、2 は ai2 と対戦 することで、簡単に行う ことが できます。しかし、ai2 は 対戦 を 行うたび に、ランダム に AI を 選択し直す ので、残念ながら ai2 と対戦 することで 手順 3 を 行うこと は できません。

この問題 を 解決 するためには、プログラムの再現性 について 理解 する 必要 が あります。

ランダムな処理とプログラムの再現性

一般的に、ランダムな処理 を 行わない プログラムは、行う処理 に 関係する条件 が 同じ状態 でプログラムを 実行 した場合は、毎回同じ処理 を 行います。例えば、下記 の 1 + 2 は ランダムな処理 を 行わない ので、2 回実行 しても、画面に 必ず 3 が表示 されます。

print(1 + 2)
print(1 + 2)

実行結果

3
3

下記の add という 関数 は、ランダムな処理 を 行わないの で、下記 のプログラムのように、同じ実引数 を 記述 して 呼び出す と、必ず同じ数値 が 表示 されます。

def add(x, y):
    print(x + y)

add(1, 2)
add(1, 2)

実行結果

3
3

このような、同じ条件 で 実行 すると、必ず同じ処理 が行われる プログラム のことを、再現性がある プログラムと 呼びます。

ランダムな処理 を 行わない プログラムであっても、例えば 時間を表示 するプログラムのような 場合 などでは、一見すると 条件 が 同じように見える にも関わらず、毎回異なる表示 が 行われる 場合が あります。しかし、その場合は、プログラム を 実行する時間 という 条件が異なる ので、異なる処理 が 行われます。

なお、上記 の add という 関数 は、時間 に 関する処理 を 行わない ので、実行する時間 が 異なっても、毎回 同じ処理 が 行われます。

一方、ai2 のように、ランダムな処理 を 行う プログラムは、下記 のプログラムのように、実行するたびに 異なる処理 が 行われます。

mb = Marubatsu()
print(ai2(mb))
print(ai2(mb))

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

(1, 1)
(1, 2)

このような 同じ条件 で 実行 しても 毎回異なる処理 を行う プログラム の事を、再現性のない プログラムと 呼びます。

なお、プログラム では 乱数 を使って ランダムな処理 を 行う ので、以後は ランダムな処理を行うプログラム の事を、乱数を使ったプログラム と 表記 することにします。

プログラムの再現性の重要性

バグが発生 した場合は、その バグの原因 を 検証 して 取り除く必要 があります。バグ を 修正 するには 様々な方法 が あります が、プログラム を 見ても 原因が 良くわからない場合 は、前回の記事で ai11s の バグの原因 を 調べる するために ai2 VS ai11s の 検証 を行ったように、バグが発生 する 状況 を 再現 して 検証する という 方法 が 良く使われます。

その際に、再現性のある プログラム であれば、バグが発生 した場合と 同じ条件 でその プログラムを実行 すると 同じバグ が 発生 するので、バグの原因 を 検証 することが できます。

一方、乱数 を 使ったプログラム には、一般的に 再現性がない ため、バグが発生 した 場合 に、その バグの原因 を 検証 することが 難しい という 問題 があります。その 理由 は、特定の乱数 が 発生した場合だけ で エラーが発生する ような バグ の場合は、もう一度 その プログラム を 実行 しても、その エラーが発生しない可能性が高い からです。

例えば、100 万分の 1 の 確率 で バグが発生する ような プログラム があった場合に、バグの原因 を 検証 しようと思っても、再び 同じバグが発生 するまで、そのプログラムを 約 100 万回 も 実行する必要 が あります。

乱数の種を使った、再現性のある乱数を利用するプログラム

乱数を利用 するプログラムにも 再現性 を 持たせる ことが できれば、上記の問題 を 解決 することが できます。また、先ほどの 手順 2 と 3 で、ai12s ver 2 と ai12s ver 3 が、手順 1 で ランダムに選択 した 同一の AI と 対戦 することが できるよう に なります。

乱数 と 再現性 は 矛盾 する要素だと 思う人 が いるかもしれません が、ここでいう 再現性とは、一度発生 させた 複数の乱数 と、全く同じパターン の 乱数 を 何度でも発生 させて 利用する ことが できる という 意味 での 再現性 です。

例えば、サイコロ を 10 回 振った際の 出目 を 記録 しておき、次 に サイコロ を 振る必要 が 生じた際 に、過去 に 振ったサイコロ の 出目 を 再利用 するということに 相当 します。

このような 乱数 の 再現性 は、乱数の種 を 利用 することで 実現 することが できます。乱数の種 の 意味 と 使い方 を 理解 するために、乱数の仕組み について 説明 します。

乱数の仕組み

コンピューター が 発生 させる 乱数 は、実は 本当の意味 での 乱数ではなく、計算 によって 求められた、乱数のように見える 疑似乱数 と呼ばれるものです。それに対して、本当の意味 での でたらめな数 のことを、真の乱数 と呼びます。残念ながら、数学 の 計算 は、同じデータ に対して 同じ計算 を行うと、同じ計算結果 が 得られる ため、コンピュータ は 計算 によって 真の乱数 を 発生 させることは できません。

真の乱数 を 発生 させるためには、特別な装置（ハードウェア） が 必要 ですが、一般的なコンピュータ には そのような装置 は 備わっていません。

疑似乱数 の 最も簡単 な 作り方 の 一つ に、下記 の 手順 で 乱数を計算 する、線形合同法 という アルゴリズム があります。興味がある方は、下記に線形合同法のリンクを紹介しますので、そちらを見て下さい。

  1. 整数 $A$、$B$、$M$ を 何らかの値 で 定める。ただし、$M > A$、$M > B$、$A > 0$、$B >= 0$ で、 $A$、$B$、$M$ は 定数2である

  2. 乱数の種 と呼ばれる 整数 $X_0$ を 決める。これは、任意の値 を 設定 しても 良い

  3. 以下 の 計算式 で 乱数 $X_n$ を 計算 する。mod は 余り を 計算する という 演算子 である

    $X_{n+1} = (A × X_n + B)　mod　M$

具体例 を挙げます。

$A = 5、B = 0、M = 7、X_0 = 1$ とした場合、下記 の 手順 で、5、4、6、2、3、1、5、4、6、2、3、1、・・・ という 乱数 を 次々に計算 することが できます。

$X_1 = 5 × 1　mod　7 = 5　mod　7 = (0 × 7 + 5)　mod　7 = 5$
$X_2 = 5 × 5　mod　7 = 25　mod　7 = (3 × 7 + 4)　mod　7 = 4$
$X_3 = 5 × 4　mod　7 = 20　mod　7 = (2 × 7 + 6)　mod　7 = 6$
$X_4 = 5 × 6　mod　7 = 30　mod　7 = (4 × 7 + 2)　mod　7 = 2$
$X_5 = 5 × 2　mod　7 = 10　mod　7 = (1 × 7 + 3)　mod　7 = 3$
$X_6 = 5 × 3　mod　7 = 15　mod　7 = (2 × 7 + 1)　mod　7 = 1$
$X_7 = 5 × 1　mod　7 = 5　mod　7 = (0 × 7 + 5)　mod　7 = 5$
・・・以下 同様 の 計算 が 繰り返される

下記は、上記の乱数 を 計算 する プログラム です。実行結果 から、上記と同じ乱数 が 計算 できていることが わかります。

A = 5
B = 0
M = 7
X = 1
for _ in range(10):
    X = A * X % M
    print(X, end=",")

実行結果

5,4,6,2,3,1,5,4,6,2,

この例 から わかるよう に、線形合同法 によって 計算 された 疑似乱数 には、同じパターン の 乱数 が 繰り返される という 周期性 が あります。ただし、$M$ を 大きな値 にすることで、周期性 があることが わかりづらい、長い周期 の 疑似乱数 を 計算できます。

線形合同法 は、計算 が 簡単 なため 計算時間 が 短く、コンピューターの性能 が今のコンピューターと比較して 何万分の一以下 だった 2000 年以前 の頃は 良く使われていました が、疑似乱数 の 品質が悪い、偏った乱数 が 作られてしまう という 欠点 があるので、最近 では あまり使われません。Python の random モジュール など、最近 の プログラム言語 では もっと複雑な計算式 で、品質の良い疑似乱数 を 計算 する 関数 が 用意されています。

参考までに、乱数に関する Wikipedia のリンクを紹介します。

乱数の種

線形合同法 の $X_0$ のように、乱数 を 計算 する際に、最初 に 任意の数値 として 設定できる値 のことを、乱数の種 と呼び、どのような疑似乱数 の アルゴリズム であっても、疑似乱数 を 計算し始める際 に、何らかの値 を 設定する必要 が あります。疑似乱数 は、乱数の種 を 元 に 計算 して 作られる ので、同じ乱数の種 から 計算 された 疑似乱数 は、毎回 同じパターン の 疑似乱数 を 発生 させます。つまり、乱数の種 を使うことで、乱数 を 使った プログラムに 再現性 を 持たせる ことが できる ようになります。

乱数の種の設定方法

Python の random モジュール には、乱数の種 を 設定 する seed という 関数 があり、この関数の 実引数 に 乱数の種 を表す 整数 を記述して呼び出すことで、乱数の種 を 設定 することが できます。また、同じ乱数の種 を 設定 することで、その後 で 発生 する 乱数 が 毎回同じパターン になるという、乱数 の 再現性 を 実現 することが できます。

具体例 を挙げます。random モジュール には、指定した範囲 の 整数 の 乱数 を 発生 させる randint という 関数 が 定義 されており、例えば randint(1, 6) を 実行 すると、1 から 6 までの ランダムな整数 を、サイコロの ように 発生 させることが できます。

下記 は、1 ~ 6 までの 整数の乱数 を 10 回 計算して 表示する という 処理 を、乱数の種 を 設定せず に 3 回、その後 で 乱数の種 に 0 を 設定 した後で、3 回 行うプログラムです。

実行結果 から、乱数の種 を 設定しない場合 は 毎回異なる 10 個の 疑似乱数 が 表示 されますが、乱数の種 を 0 に 設定した後 で 表示 される 疑似乱数 は、3 回 とも 全く同じパターン になることが 確認 できます。

import random

for i in range(3):
    for j in range(10):
        print(random.randint(1, 6), end=",")
    print()

for i in range(3):
    random.seed(0)
    for j in range(10):
        print(random.randint(1, 6), end=",")
    print()

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

5,4,2,2,4,1,5,6,5,2,
4,3,5,1,6,5,6,5,5,3,
1,1,2,3,2,3,2,4,2,4,
4,4,1,3,5,4,4,3,4,3,
4,4,1,3,5,4,4,3,4,3,
4,4,1,3,5,4,4,3,4,3,

上記 のプログラムで、これまで のプログラムと 同様 に、seed と randint を下記のプログラムのように 個別 に インポートしない理由 は、この後 のプログラムで、seed という 名前 の 変数 を 利用するため です。

from random import seed, randint

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

乱数の種を設定しない場合に行われる処理

これまで のプログラムでは、乱数の種 を 設定せず に、乱数を発生 させてきましたが、それにも関わらず、ランダムな AI である ai2 が 毎回異なる合法手 を 選択 するのは おかしい と 思った人 は いないでしょうか？

乱数の種 を 設定しない 場合は、プログラム を 実行した時間 を 整数 に 変換した値 を使って、random モジュール を インポート した 時点 で 乱数の種 が 自動的に設定 されます。そのため、異なる時間 で 実行した場合 は、異なる乱数の種 が 設定される ため、プログラム を 実行するたび に 毎回異なるパターン の 乱数が発生する という 仕組み になっています。

従って、乱数 の 計算 に 再現性 を 求めない場合 は、乱数の種 を 設定 しては いけません。

上記からわかるように、乱数 を 利用するプログラム は、プログラム を 実行した時間 が 全く同じ であれば、同じパターン の 乱数を発生 するので、再現性のある プログラムです。ただし、全く同じ時間 に プログラムを実行 することは 現実的 にはほぼ 不可能 なので、実質的 には 再現性のない プログラムと 考えて良い でしょう。

乱数の種を使った AI どうしの対戦の再現

下記 のプログラムは、ai12s ver 2 VS ai2 の 対戦 を、乱数の種 を 設定せず に 3 回 行い、その後で 乱数の種 に 0 を設定 して 3 回行う プログラムです。

mb = Marubatsu()

for i in range(3):
    mb.play(ai=[ai2, ai2])

for i in range(3):
    random.seed(0)
    mb.play(ai=[ai2, ai2])
実行結果（長いのでクリックして開いてください） 
Turn o
...
...
...

Turn x
...
O..
...

Turn o
..X
o..
...

Turn x
..x
oO.
...

Turn o
.Xx
oo.
...

Turn x
Oxx
oo.
...

Turn o
oxx
oo.
.X.

winner o
oxx
oo.
.xO

Turn o
...
...
...

Turn x
..O
...
...

Turn o
..o
..X
...

Turn x
O.o
..x
...

Turn o
o.o
..x
..X

winner o
oOo
..x
..x

Turn o
...
...
...

Turn x
...
..O
...

Turn o
...
..o
..X

Turn x
...
.Oo
..x

Turn o
X..
.oo
..x

winner o
x..
Ooo
..x

Turn o
...
...
...

Turn x
...
...
O..

Turn o
...
...
oX.

Turn x
O..
...
ox.

Turn o
o..
X..
ox.

Turn x
o..
x..
oxO

Turn o
o..
x.X
oxo

Turn x
o.O
x.x
oxo

winner x
o.o
xXx
oxo

Turn o
...
...
...

Turn x
...
...
O..

Turn o
...
...
oX.

Turn x
O..
...
ox.

Turn o
o..
X..
ox.

Turn x
o..
x..
oxO

Turn o
o..
x.X
oxo

Turn x
o.O
x.x
oxo

winner x
o.o
xXx
oxo

Turn o
...
...
...

Turn x
...
...
O..

Turn o
...
...
oX.

Turn x
O..
...
ox.

Turn o
o..
X..
ox.

Turn x
o..
x..
oxO

Turn o
o..
x.X
oxo

Turn x
o.O
x.x
oxo

winner x
o.o
xXx
oxo

実行結果 から、最初 の 3 回 の 対戦 の 試合経過 は 毎回異なります が、その後の 3 回 の 対戦 は、全く同じ試合経過 で 対戦 が行われることが 確認 できます。

従って、乱数の種 によって ランダムな AI の 対戦 を 再現できる ことが 確認 できました。

play メソッドの修正

ランダムな AI の 対戦 を 再現する際 に、random.seed を 呼び出してから、play メソッドを 呼び出す のは 面倒 なので、play メソッドの 仮引数 に 乱数の種 を 代入 するように 修正 し、実際の 乱数の種 の 設定 は、play メソッドの 中で行う ようにします。

そのようにする 場合は、仮引数 を 下記 のように 設定 するのが 一般的 です。仮引数 を デフォルト引数 にすることで、その 仮引数 に 対応する実引数 を 記述するか どうかで、関数 が 行う処理 の 再現性 の 有無 を 選択 することが できる ように なります。

  • 仮引数 の 名前 を 種（seed）を表す seed とする
  • 仮引数 を、デフォルト値 が None の デフォルト引数 にする
  • 仮引数 に 代入 された 値 が None 以外 の場合に、その値 を使って 乱数の種 を 設定 し、None の場合 は 何もしない

下記は、乱数の種 を 設定できる ように、play メソッドを 修正 したプログラムです。

  • 1 行目：デフォルト値 に None を 設定 した デフォルト引数 seed を 追加 する
  • 3、4 行目：seed が None でない 場合は、seed を 乱数の種 として 設定 する
1  def play(self, ai, params=[{}, {}], verbose=True, seed=None):
2      # seed が None でない場合は、seed を乱数の種として設定する
3      if seed is not None:
4          random.seed(seed)
元と同じなので略
5
6  Marubatsu.play = play
行番号のないプログラム 
def play(self, ai, params=[{}, {}], verbose=True, seed=None):
    # seed が None でない場合は、seed を乱数の種として設定する
    if seed is not None:
        random.seed(seed)

    # 〇×ゲームを再起動する
    self.restart()
    # ゲームの決着がついていない間繰り返す
    while self.status == Marubatsu.PLAYING:
        # ゲーム盤の表示
        if verbose:
            print(self)
        # 現在の手番を表す ai のインデックスを計算する
        index = 0 if self.turn == Marubatsu.CIRCLE else 1
        # ai が着手を行うかどうかを判定する
        if ai[index] is not None:
            x, y = ai[index](self, **params[index])
        else:
            # キーボードからの座標の入力
            coord = input("x,y の形式で座標を入力して下さい。exit を入力すると終了します")
            # "exit" が入力されていればメッセージを表示して関数を終了する
            if coord == "exit":
                print("ゲームを終了します")
                return       
            # x 座標と y 座標を要素として持つ list を計算する
            xylist = coord.split(",")
            # xylist の要素の数が 2 ではない場合
            if len(xylist) != 2:
                # エラーメッセージを表示する
                print("x, y の形式ではありません")
                # 残りの while 文のブロックを実行せずに、次の繰り返し処理を行う
                continue
            x, y = xylist
        # (x, y) に着手を行う
        try:
            self.move(int(x), int(y))
        except:
            print("整数の座標を入力して下さい")

    # 決着がついたので、ゲーム盤を表示する
    if verbose:
        print(self)
    return self.status

Marubatsu.play = play
修正箇所 
def play(self, ai, params=[{}, {}], verbose=True, seed=None):
    # seed が None でない場合は、seed を乱数の種として設定する
    if seed is not None:
        random.seed(seed)
元と同じなので略

Marubatsu.play = play

下記 のプログラムは、先程と同様 に ai12s ver 2 VS ai2 の 対戦 を、乱数の種 を 設定せず に 1 回 行い、その後 で 乱数の種 に 0 を設定 して 2 回行う プログラムです。

mb = Marubatsu()

for i in range(3):
    mb.play(ai=[ai2, ai2])

for i in range(3):
    mb.play(ai=[ai2, ai2], seed=0)
修正箇所 
mb = Marubatsu()

for i in range(3):
    mb.play(ai=[ai2, ai2])

for i in range(3):
-   random.seed(0)
-   mb.play(ai=[ai2, ai2])
+   mb.play(ai=[ai2, ai2], seed=0)
実行結果（長いのでクリックして開いてください） 
Turn o
...
...
...

Turn x
...
...
.O.

Turn o
...
..X
.o.

Turn x
...
.Ox
.o.

Turn o
.X.
.ox
.o.

Turn x
.x.
.ox
.oO

Turn o
.xX
.ox
.oo

Turn x
.xx
Oox
.oo

winner x
Xxx
oox
.oo

Turn o
...
...
...

Turn x
.O.
...
...

Turn o
.o.
..X
...

Turn x
.o.
..x
O..

Turn o
.o.
..x
o.X

Turn x
.o.
..x
oOx

winner x
.oX
..x
oox

Turn o
...
...
...

Turn x
...
.O.
...

Turn o
.X.
.o.
...

Turn x
.x.
.o.
.O.

Turn o
Xx.
.o.
.o.

Turn x
xx.
.oO
.o.

Turn o
xx.
.oo
.oX

Turn x
xx.
.oo
Oox

winner x
xxX
.oo
oox

Turn o
...
...
...

Turn x
...
...
O..

Turn o
...
...
oX.

Turn x
O..
...
ox.

Turn o
o..
X..
ox.

Turn x
o..
x..
oxO

Turn o
o..
x.X
oxo

Turn x
o.O
x.x
oxo

winner x
o.o
xXx
oxo

Turn o
...
...
...

Turn x
...
...
O..

Turn o
...
...
oX.

Turn x
O..
...
ox.

Turn o
o..
X..
ox.

Turn x
o..
x..
oxO

Turn o
o..
x.X
oxo

Turn x
o.O
x.x
oxo

winner x
o.o
xXx
oxo

Turn o
...
...
...

Turn x
...
...
O..

Turn o
...
...
oX.

Turn x
O..
...
ox.

Turn o
o..
X..
ox.

Turn x
o..
x..
oxO

Turn o
o..
x.X
oxo

Turn x
o.O
x.x
oxo

winner x
o.o
xXx
oxo

先程と同様 に、最初 の 3 回 の 試合経過 は 毎回異なります が、その後 の 3 回 の 試合経過 は 毎回必ず同じに なることが 確認 できます。

ai12s ver 2 VS ai2 と ai12s ver 3 VS ai2 の違いの表示

先程紹介した、ランダムな AI である ai2 と対戦 した際に、ai12s ver 2 と 対戦 すると 勝利 するが、ai12s ver 3 と 対戦 すると 引き分け になる AI を見つける 下記 の アルゴリズム は、乱数の種 を使って 記述 することができます。どのようなプログラムを記述すれば良いかについて少し考えてみて下さい。

  1. 世の中に存在 する AI の中 から ランダム に AI を 一つ選択 する
  2. ai12s ver 2 VS その AI の 対戦 を行い 結果を記録 する
  3. ai12s ver 3 VS その AI の 対戦 を行い 結果を記録 する
  4. 手順 2 と 3 の 対戦結果 が 同じ場合 は 手順 1 に 戻る
  5. 対戦結果 が 異なる場合 は、その AI が 求める AI である

上記の 手順 1 ~ 3 は、下記 のような方法で 処理を行う ことができます。

手順 処理の方法
手順 1 これまで に 選択していない、乱数の種 を 1 つ選択する
手順 2、3 対戦 を 行う前 に、手順 1 で 選択 した 乱数の種 を 設定する

手順 1 で 選択 する 最初 の 乱数の種 は 何でも構わない ので、本記事 では 0 を選択 することにします。また、手順 1 で その後 に 選択 する 乱数の種 には、直前 に 選択 した 乱数の種 に 1 を足した値 を 選択 するという方法が 最も簡単 でしょう。1 を足す ことで、これまでに選択した どの乱数の種より も 大きな値になる ので、これまでに選択 した 乱数の種 とは、必ず異なる値 を 選択 することが できます。

下記は 上記の処理 を行うプログラムです。

  • 1 行目：乱数の種 を 代入 する変数 seed を 0 で初期化 する（手順 1）
  • 3 ~ 11 行目：答え が 見つかる まで 無限に繰り返す
  • 4 行目：seed に 代入 された 乱数の種 で 、ai12s ver 2 VS ai2 の 対戦 を 対戦経過 を 表示せず に（verbose=False）行い、結果 を winner1 に 代入 する（手順 2）
  • 5、6 行目：seed に 代入 された 乱数の種 で 、ai12s ver 3 VS ai2 の 対戦 を 対戦経過 を 表示せず に（verbose=False）行い、結果 を winner2 に 代入 する（手順 3）
  • 7 ~ 10 行目：それぞれの 対戦結果 が 異なる場合 に、その乱数の種 で ai12s ver 2 VS ai2 と ai12s ver 3 VS ai2 の 対戦経過 を 表示 し、無限ループ から 抜ける（手順 5）
  • 11 行目：乱数の種 に 1 を足す（手順 1）。ここで while 文 の ブロックが終了 しているので、4 行目 に 戻り、次の繰り返し処理 が 行われる（手順 4）
 1  seed = 0
 2  mb = Marubatsu()
 3  while True:
 4      winner1 = mb.play(ai=[ai12s, ai2], seed=seed, verbose=False)
 5      winner2 = mb.play(ai=[ai12s, ai2], params=[{"score_victory": 200}, {}], \
 6                        seed=seed, verbose=False)
 7      if winner1 != winner2:
 8          mb.play(ai=[ai12s, ai2], seed=seed)
 9          mb.play(ai=[ai12s, ai2], params=[{"score_victory": 200}, {}], seed=seed)
10          break
11      seed += 1
行番号のないプログラム 
seed = 0
mb = Marubatsu()
while True:
    winner1 = mb.play(ai=[ai12s, ai2], seed=seed, verbose=False)
    winner2 = mb.play(ai=[ai12s, ai2], params=[{"score_victory": 200}, {}], \
                      seed=seed, verbose=False)
    if winner1 != winner2:
        mb.play(ai=[ai12s, ai2], seed=seed)
        mb.play(ai=[ai12s, ai2], params=[{"score_victory": 200}, {}], seed=seed)
        break
    seed += 1

実行結果

Turn o
...
...
...

Turn x
...
.O.
...

Turn o
...
.oX
...

Turn x
..O
.ox
...

Turn o
..o
.ox
..X

winner o
..o
.ox
O.x

Turn o
...
...
...

Turn x
...
.O.
...

Turn o
...
.oX
...

Turn x
..O
.ox
...

Turn o
..o
.ox
..X

Turn x
..o
.ox
.Ox

Turn o
..o
.ox
Xox

Turn x
O.o
.ox
xox

Turn o
oXo
.ox
xox

winner draw
oxo
Oox
xox

下図 は、上記 の プログラム で 発見 した、結果 が 異なる ai12s ver 2 VS ai2 と ai12s ver 3 VS ai2 の 試合経過 を 上下に並べた ものです。図 から、4 手目まで の 試合経過 は 同じ であり、5 手目 で ai11s ver 2 と ver 3 が 選択 する 合法手 が 異なったため、試合の結果 が 異なる ように なった ことが わかりました。

従って、5 手目 で ai12s ver 3 が 行う着手 を 検証すればよい ことが わかりました。

記事が長くなったので、その検証は次回の記事で行うことにします。

今回の記事のまとめ

今回の記事では、ルール の 条件の統合 について 説明 し、実際に ルール 12 の 条件の 1 つ を 統合 することが できる ことを 示しました。

また、必勝の局面 での 最善手 を 見つける ための、異なる条件 の 評価値 を 同じ にした ai12 ver 3 で ai2 と 対戦 を行った結果、バグが発生 しました。その バグの原因 を 見つけるため に、プログラム の 再現性 と、乱数の種 について 説明 し、問題 が 発生 した 可能性 が 高い局面 を 見つけました。

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

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

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

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

次回の記事

  1. 本記事では説明は省略しますが、引き分けの局面 でも 同様 です ↩

  2. 一度決めた後 は、常に同じ値 を 使い続ける値 の事です ↩

1
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
1
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?