Pythonで〇×ゲームのAIを一から作成する その181 反復深化と例外に関する処理

目次と前回の記事

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

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

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
test.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

反復深化

ここまでの記事で、深さ制限探索 で最善手を選択する AI が、深さの上限を増やすことで強くなる 事について説明しましたが、実際には一般的に 深さの上限を増やす ことで 処理時間が大きく増えて しまうという問題があります。例えば深さが $d$、リーフノード以外のノードが $n$ 個の子ノードを持つ 平衡木 の場合は、深さが 1 増えるごと に リーフノードの数が $\boldsymbol{n}$ 倍 になります。

なお、〇× ゲームや囲碁などのようにゲーム盤のマスを埋めていくようなゲームでは、深さが深いノードほど子ノードの数が少なくなりますが、深さが増えるごとにリーフノードの数が数倍に増えていく点では変わりはありません。

〇× ゲームのようなノードの数が少ないゲーム木の場合はゲーム木と同じ深さを上限とした深さ制限探索を行うことができますが、多くのゲーム では ノードの数が多すぎる ため 現実的ではありません。

深さの上限を見積もることの問題点

一般的には AI が着手を計算する際 には 制限時間 が設けられます。理想的 には与えられた 制限時間内 で計算できる、最も大きな深さの上限 で計算を行いたいのですが、以下の理由から 最も大きな深さの上限 を 見積もって計算を行う という手法には 問題があります。

• ミニマックス法や αβ 法で計算を行う際に必要となる 処理時間 は、計算の対象となる ゲーム木の性質 によって 大きく異なる ため、深さの上限から 処理時間を 正確に見積もることは不可能 である
• ミニマックス法や αβ 法では、計算が完全に終了するまで答えが得られない。そのため、例えばこの深さの上限であれば制限時間内に計算が終わると見積もって計算を始めた結果、計算が終わる前に制限時間が過ぎて処理を中断 してしまうと、答えがまったく得られない ことになってしまう

ゲーム木の性質によって処理時間が異なる ことを、〇× ゲームで ゲーム開始時の局面から 1 回着手 を行った局面に対する ミニマックス法 による計算の 処理時間の比較 を行うことで示すことにします。行われる計算は、〇× ゲームのゲーム木のルートのノードのそれぞれの 子ノードをルートノード とする 部分木に対する計算 です。

また、行う計算は深さの制限を行わないミニマックス法ですが、ゲーム開始時の局面から 1 回だけ着手を行った局面は 最大で後 8 回着手 を行うことができるので、実質的に 深さの上限を 8 とした ミニマックス法 と同じ計算が行われます。

下記はそのような計算を行い、計算を行った 部分木のノードの数を表示 するプログラムです。実行結果から 四隅、四辺、真ん中 に着手を行った場合で ノードの数が異なる ことから、それぞれの 処理時間が異なることが推測 されます。

• 5 行目：ゲーム開始時の局面を計算する
• 6 行目：ゲーム開始時の局面のそれぞれの合法手に対する繰り返し処理を行う
• 6、7 行目：ゲーム開始時の局面をコピーして合法手を着手する
• 8 行目：着手した合法手を表示する
• 9 行目：ミニマックス法の計算を行う ai_mmdfs_all の実引数に calc_score=True を記述¹して mb のノードのミニマックス値を計算するようにし、debug=True を記述することで計算したノードの数を表示するようにする

 1  from marubatsu import Marubatsu
 2  from ai import ai_mmdfs_all
 3  from copy import deepcopy
 4  
 5  mborig = Marubatsu()
 6  for x, y in mborig.calc_legal_moves():
 7      mb = deepcopy(mborig)
 8      mb.move(x, y)
 9      print(f"move: ({x}, {y})")
10      ai_mmdfs_all(mb, debug=True, calc_score=True)

行番号のないプログラム

from marubatsu import Marubatsu
from ai import ai_mmdfs_all
from copy import deepcopy

mborig = Marubatsu()
for x, y in mborig.calc_legal_moves():
    mb = deepcopy(mborig)
    mb.move(x, y)
    print(f"move: ({x}, {y})")
    ai_mmdfs_all(mb, debug=True, calc_score=True)

実行結果

move: (0, 0)
count = 59705
move: (1, 0)
count = 63905
move: (2, 0)
count = 59705
move: (0, 1)
count = 63905
move: (1, 1)
count = 55505
move: (2, 1)
count = 63905
move: (0, 2)
count = 59705
move: (1, 2)
count = 63905
move: (2, 2)
count = 59705

time モジュールによる時間の計測

上記では 計算したノードの数 を表示することで 処理時間が異なる ことを 推測 しましたが、推測にすぎないので実際に 処理時間を計測して表示 することにします。

これまでは %%timeit や %timeit を利用して特定のセルに記述されたプログラムや、関数の処理時間を計測して表示してきましたが、反復深化ではこの後で説明するように 制限時間を過ぎた場合に処理を中断する処理 が必要なので、今回の記事では time モジュール を利用して 処理時間の計測 を行います。

time モジュールは時間に関する以下のような関数が定義されたモジュールです。関数名のリンクはその関数を説明する公式のドキュメントへのリンクです。

関数	意味
time	1970 年 1 月 1 日からの秒数を返す
perf_counter	パフォーマンスカウンター（performance counter）と呼ばれる短い時間間隔を計測するために利用できる最も精度が高い2数値を返す。返り値の数値の単位は秒
sleep	実引数に記述した秒数が経過するまで何も行わない

処理時間を計測 したい 処理の前後 で time や perf_counter を呼び出し、前後の返り値の差を計算 することで 処理時間を秒単位で計測 することができます。

下記のプログラムでは 1 秒で行われる sleep(1) という処理を time と perf_counter で計測しています。なお、time と perf_counter による処理時間の計測には 若干の誤差が発生 するので実行結果は毎回下記と同じにはなりませんが、ほぼ 1 に近い値 が表示されます。

from time import time, perf_counter, sleep

starttime = time()
sleep(1)
endtime = time()
print(endtime - starttime)

starttime = perf_counter()
sleep(1)
endtime = perf_counter()
print(endtime - starttime)

実行結果（誤差が発生するため、下記の実行結果と若干異なる場合があります）

1.0005824565887451
1.0006438996642828

time よりも perf_counter のほうが精度が高い ので time は 現在の日付や時刻を計測 する目的で利用し、処理時間を計測 する場合は perf_counter を利用 すると良いでしょう。

time モジュールには現在の年月日と時刻を文字列で表示するなど、上記以外にも様々な関数が用意されています。詳細は下記のドキュメントを参照して下さい。

下記は先ほどのプログラムを perf_counter を利用して 処理時間を計測して表示 するように修正したプログラムです。

for x, y in mborig.calc_legal_moves():
    mb = deepcopy(mborig)
    mb.move(x, y)
    print(f"move: ({x}, {y})")
    starttime = perf_counter()
    ai_mmdfs_all(mb, debug=True, calc_score=True)
    endtime = perf_counter()
    print(f"time: {endtime - starttime:4.2f} ms")

修正箇所

for x, y in mborig.calc_legal_moves():
    mb = deepcopy(mborig)
    mb.move(x, y)
    print(f"move: ({x}, {y})")
+   starttime = perf_counter()
    ai_mmdfs_all(mb, debug=True, calc_score=True)
+   endtime = perf_counter()
+   print(f"time: {endtime - starttime:4.2f} ms")

実行結果（コンピュータの性能などによって処理時間は下記と異なる場合があります）

move: (0, 0)
count = 59705
time: 3.02 ms
move: (1, 0)
count = 63905
time: 3.15 ms
move: (2, 0)
count = 59705
time: 2.94 ms
move: (0, 1)
count = 63905
time: 3.21 ms
move: (1, 1)
count = 55505
time: 2.63 ms
move: (2, 1)
count = 63905
time: 3.14 ms
move: (0, 2)
count = 59705
time: 2.85 ms
move: (1, 2)
count = 63905
time: 3.11 ms
move: (2, 2)
count = 59705
time: 2.93 ms

下記は四隅、辺、真ん中に着手した場合の count、処理時間の平均、count あたりの処理時間の平均 をまとめた表で、処理時間が 同じではない ことが確認できます。また、count 当たりの処理時間の平均 がいずれも ほぼ同じ になることから、処理時間 が count に比例する ことが確認できます。

	count	処理時間の平均	count 当たりの処理時間
四隅	59705	2.94 ms	0.049 μs
辺	63905	3.15 ms	0.049 μs
真ん中	55505	2.63 ms	0.047 μs

反復深化のアルゴリズム

深さの上限を正確に見積もることができない問題を解決する手法の一つに 反復深化（iterative deepening）があります。反復深化では下記のようなアルゴリズムで深さ制限探索の計算を行います。ただし、深さの上限を $\boldsymbol{d}$ と表記することにします。

1. 時間の計測を開始する
2. $d = 1$ とする
3. 深さの上限を $d$ とした深さ制限探索を開始する
4. 深さ制限探索の処理の最中で制限時間になった場合は、即座に処理を終了する
5. $d$ に 1 を加えて手順 3 へ戻る
6. 最も深い深さの上限で計算された深さ制限探索の結果を採用する

上記のアルゴリズムを別の言葉で説明すると以下のようになります

• 深さの上限 を 1 から 1 つずつ増やしながら 深さ制限探索を 制限時間になるまで 行う
• ただし、深さ制限探索の途中で 制限時間になった場合 は 処理即座に終了 する
• 制限時間内で 最も大きな深さの上限 で計算された値を採用する

反復深化の利点と欠点

制限時間内で処理を行うことができる 深さの上限を見積もって計算を行う という手法には、見積もりが間違っていて 制限時間内に計算が終了しなかった場合 は 計算結果が得られない という問題がありました。

一方、反復深化は深さの上限を 1 から増やしながら制限時間が来るまで計算を行うため、必ず何らかの深さの上限 での 計算結果を得る ことができます。

他の反復深化の 利点 としては、制限時間を設定するだけ で、自動的に 制限時間に 見合った深さの上限 で計算が行われる点が挙げられます。

一方で、反復深化には 最も大きな深さの上限以外 の深さ制限探索の 計算結果が利用されない ので 無駄が生じる という 欠点 があります。例えば、深さの上限が $d$ の深さ制限探索の結果が採用された場合は、それより前に行われた深さの上限が $1$ ~ $d - 1$ の深さ制限探索の結果は利用されないので無駄な計算となります。ただし、この欠点は αβ 法に対する反復深化 ではうまく 解消 することができます。その理由については次回の記事で説明します。

参考までに反復深化の Wikipedia と Chess programming wiki のリンクを下記に示します。

反復深化を利用した最善手を計算するアルゴリズム

反復深化 を利用したノード $N$ の局面の 最善手を計算 するアルゴリズムを下記に示します。ただし、計算する 最善手 を代入する変数を bestmove、深さ制限探索での 深さの上限 を代入する変数を maxdepth と表記することにします。

1. 初期設定として以下の処理を行う
   • 処理時間の計測を開始する
   • bestmove に $N$ の局面の合法手の中からランダムに選択して代入する³
   • maxdepth = 1 とする
2. 深さの上限を maxdepth とした深さ制限探索を開始する
3. 深さ制限探索の処理の最中で制限時間になった場合は、即座に深さ制限探索の処理を中断して手順 5 へ移動する
4. 深さ制限探索の終了後に以下の処理を行う
   • 深さ制限探索で計算した最善手を bestmove に代入する
   • maxdepth に 1 を加算する
   • 手順 2 に戻る
5. 反復深化の処理が完了する。この時点で bestmove には深さの上限を maxdepth - 1 として計算された最善手が代入されている

反復深化の実装

上記の 反復深化のアルゴリズム で 最善手を計算する関数を定義 します。ミニマックス法で反復深化を行うメリットは特にないので、αβ 法 に対して反復深化を行う ai_ab_iddfs という関数を定義することにします。Wikipedia では 反復深化深さ優先探索（iterative deepening depth first search）と説明されているので その頭文字を関数名 としました。

この関数は、αβ 法による深さ制限探索 を行う ai_abs_dls を利用して反復深化の処理を行うので、仮引数 は 以下の点を除いて ai_abs_dls と同じ とします。

• 制限時間 を秒単位で代入する仮引数 timelimit を追加 する
• ai_abdfs_itd は ai_by_mmscore を利用せずに定義 するので、ai_by_mmscore のラッパー関数の仮引数の中で必要となる 仮引数 share_tt と analyze を追加 する
• 仮引数 tt は share_tt を追加したことで 必要がなくなるので削除 する。share_tt と tt について忘れた方は 以前の記事を復習すること
• 仮引数 calc_count に関しては次回の記事で対応することにするので 削除する

反復深化のアルゴリズムでは 深さ制限探索の処理の最中で制限時間になった場合 は、即座に深さ制限探索の処理を中断する必要 がありますが、そのためには ai_abs_dls を修正する必要がある ので、下記のプログラムでは 深さ制限探索の処理の開始時 に 制限時間を超えていた場合 に 処理を中断 することにして、その点については後で修正することにします。

下記は ai_abdfs_itd の定義です。

• 4 行目：上記で説明した仮引数を持つ関数として ai_ab_iddfs を定義する。timelimit はデフォルト値を 10 とするデフォルト引数とした
• 6 行目：処理を開始した時点の時間を perf_counter で計算して starttime に代入する
• 7 行目：timelimit に starttime を加算した値を timelimit_pc に代入する。この処理によって perf_counter で計算した値が timelimit_pc を超えた場合に制限時間を過ぎたことが判定できるようになる
• 8 行目：最善手を mb の合法手の中からランダムに選択する
• 9 行目：深さの上限を 0 から 1 ずつ増やしながら繰り返し処理を行う。なお、この深さの上限 は、mb の 子ノードに対して行う深さ制限探索の深さの上限 なので、1 ではなく 0 から増やす必要がある 点に注意すること。また、〇× ゲームの ゲーム木の深さの最大値は 9 なので、mb の局面をルートノードとする 部分木の深さ は 9 - mb.move_count で計算できる。それ以上の値 を深さの上限に設定しても 答えは変わらない ので その値までの繰り返し処理を行う ようにした
• 10、11 行目：深さの上限を maxdepth とする深さ制限探索を行う前に制限時間を超えていた場合は繰り返しの処理を中断する
• 12、13 行目：仮引数で設定した値を実引数に記述して ai_abs_dls を呼び出す
• 14 ~ 17 行目：analyze=True を実引数に記述して呼び出した場合の処理を記述する。この場合は最善手の一覧から最善手をランダムに選択し、debug=True が記述されていた場合は深さの上限、ここまでの処理時間、最善手、最善手の一覧を表示する
• 18 ~ 20 行目：analyze=False を実引数に記述して呼び出した場合の処理を記述する
• 21、22 行目：処理時間を表示し、最善手を返り値として返す

 1  from ai import dprint, ai_abs_dls
 2  import random
 3  
 4  def ai_ab_iddfs(mb, debug=False, timelimit=10, eval_func=None, eval_params={},
 5                  use_tt=False, share_tt=False, analyze=False):
 6      starttime = perf_counter()
 7      timelimit_pc = starttime + timelimit
 8      bestmove = random.choice(mb.calc_legal_moves())
 9      for maxdepth in range(9 - mb.move_count):
10          if perf_counter() >= timelimit:
11              break
12          result = ai_abs_dls(mb, maxdepth=maxdepth, eval_func=eval_func, eval_params=eval_params,
13                              use_tt=use_tt, share_tt=share_tt, analyze=analyze)
14          if analyze:
15              candidate = result["candidate"]
16              bestmove = random.choice(candidate)
17              dprint(debug, f"maxdepth: {maxdepth}, time: {perf_counter() - starttime:6.2f} ms, bestmove: {bestmove}, candidate: {candidate}")
18          else:
19              bestmove = result
20              dprint(debug, f"maxdepth: {maxdepth}, time: {perf_counter() - starttime:6.2f} ms, bestmove: {bestmove}")
21      dprint(debug, f"totaltime: {perf_counter() - starttime: 6.2f} ms")
22      return bestmove

行番号のないプログラム

from ai import dprint, ai_abs_dls
import random

def ai_ab_iddfs(mb, debug=False, timelimit=10, eval_func=None, eval_params={},
               use_tt=False, share_tt=False, analyze=False):
    starttime = perf_counter()
    timelimit += starttime
    bestmove = random.choice(mb.calc_legal_moves())
    for maxdepth in range(9 - mb.move_count):
        if perf_counter() >= timelimit:
            break
        result = ai_abs_dls(mb, maxdepth=maxdepth, eval_func=eval_func, eval_params=eval_params,
                            use_tt=use_tt, share_tt=share_tt, analyze=analyze)
        if analyze:
            candidate = result["candidate"]
            bestmove = random.choice(candidate)
            dprint(debug, f"maxdepth: {maxdepth}, time: {perf_counter() - starttime:6.2f} ms, bestmove: {bestmove}, candidate: {candidate}")
        else:
            bestmove = result
            dprint(debug, f"maxdepth: {maxdepth}, time: {perf_counter() - starttime:6.2f} ms, bestmove: {bestmove}")
    dprint(debug, f"totaltime: {perf_counter() - starttime: 6.2f} ms")
    return bestmove

ai_abdfs_itd の検証

下記はゲーム開始時の局面に対して下記の設定で ai_ab_iddfs によって 反復深化で最善手の計算 を行うプログラムです。

• 制限時間を 10 秒とする
• 置換表を利用しない
• 静的評価関数として弱解決の AI である ai14s を利用する
• 実引数に debug=True、analyze=False を記述する

from ai import ai14s

eval_params= {"minimax": True}
mb = Marubatsu()
print(ai_ab_iddfs(mb, timelimit=10, debug=True, eval_func=ai14s,
                  eval_params=eval_params, analyze=False))

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

maxdepth: 0, time:   0.00 ms, bestmove: (1, 1)
maxdepth: 1, time:   0.03 ms, bestmove: (1, 1)
maxdepth: 2, time:   0.07 ms, bestmove: (1, 1)
maxdepth: 3, time:   0.15 ms, bestmove: (1, 1)
maxdepth: 4, time:   0.48 ms, bestmove: (1, 1)
maxdepth: 5, time:   1.26 ms, bestmove: (1, 1)
maxdepth: 6, time:   2.57 ms, bestmove: (1, 1)
maxdepth: 7, time:   4.06 ms, bestmove: (1, 2)
maxdepth: 8, time:   5.68 ms, bestmove: (0, 1)
totaltime:   5.68 ms
(0, 1)

実行結果から処理を 10 秒以内の約 5.68 秒で完了 できたので、0 から 8 までの深さの上限で深さ制限探索が行われ、その中の最大の 深さの上限が 8 の場合で計算された 最善手が返り値として返された ことが確認できます。

下記は 制限時間を 2 秒 として反復深化を行うプログラムです。実行結果から 深さの上限を 6 とした場合の計算を完了した時点で 制限時間の 2 秒を超えた ので 深さの上限を 6 とした場合で計算された 最善手が返り値として返された ことが確認できます。また、深さの上限を 7、8 とする計算は 行われなかった ことも確認できます。

print(ai_ab_iddfs(mb, timelimit=2, debug=True, eval_func=ai14s, 
                  eval_params=eval_params, analyze=False))

実行結果

maxdepth: 0, time:   0.00 ms, bestmove: (1, 1)
maxdepth: 1, time:   0.01 ms, bestmove: (1, 1)
maxdepth: 2, time:   0.07 ms, bestmove: (1, 1)
maxdepth: 3, time:   0.21 ms, bestmove: (1, 1)
maxdepth: 4, time:   0.48 ms, bestmove: (1, 1)
maxdepth: 5, time:   1.22 ms, bestmove: (1, 1)
maxdepth: 6, time:   2.61 ms, bestmove: (1, 1)
totaltime:   2.61 ms
(1, 1)

深さの上限を 7、8 とした場合の計算結果の検証

反復深化による処理とは直接関係ない のですが、最初の計算結果で 深さの上限を 7、8 とした場合の 最善手が (1, 1) 以外となる場合がある 点が気になった人はいないでしょうか。その理由を検証するために、下記のプログラムで 制限時間を 10 秒 に戻し、analyze=True とした場合の計算を行ってみることにします。

print(ai_ab_iddfs(mb, timelimit=10, debug=True, eval_func=ai14s,
      eval_params=eval_params, analyze=True))

実行結果

maxdepth: 0, time:   0.00 ms, bestmove: (1, 1), candidate: [(1, 1)]
maxdepth: 1, time:   0.02 ms, bestmove: (1, 1), candidate: [(1, 1)]
maxdepth: 2, time:   0.05 ms, bestmove: (1, 1), candidate: [(1, 1)]
maxdepth: 3, time:   0.13 ms, bestmove: (1, 1), candidate: [(1, 1)]
maxdepth: 4, time:   0.39 ms, bestmove: (1, 1), candidate: [(1, 1)]
maxdepth: 5, time:   1.22 ms, bestmove: (1, 1), candidate: [(1, 1)]
maxdepth: 6, time:   2.60 ms, bestmove: (1, 1), candidate: [(1, 1)]
maxdepth: 7, time:   4.15 ms, bestmove: (2, 1), candidate: [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
maxdepth: 8, time:   5.75 ms, bestmove: (0, 1), candidate: [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
totaltime:   5.75 ms
(0, 1)

実行結果から、深さの上限が 6 以下 の場合は 最善手として (1, 1) のみ が計算されているのに対して、深さの上限が 7、8 の場合は 8 つのすべての合法手が最善手 として計算されていることがわかります。このようなことが起きる理由について少し考えてみて下さい。

深さの上限が 7 の場合は 静的評価関数 ai14s は以下の局面に対して近似値を計算します。

• ルートノードから 7 手目以内 の 決着がついた局面 に対して計算する
• ルートノードから 8 手目の局面 に対して計算する

ai14s は 決着がついた局面 に対して局面の状況を正しく表現する 正確な評価値を計算 することができるので、7 手目以内の局面 に対しては 正確な評価値を計算 します。

一方、ゲーム開始時から 8 手目の局面 は直前で × が着手 を行った局面で、ai14s はその 評価値の計算方法 から 以下の判定を正確に行う ことができます。

• × が勝利しているか
• 次の 〇 の手番で 〇 が勝利できるかどうか

× が勝利していない場合 は 次の 9 手目が最後の着手 になるので 9 手目を着手した局面 は必ず ゲームの決着がついた局面 になります。従って、次の 〇の 手番で 〇 が勝利できるかどうかを判定できる ということは、9 手目を着手した局面が 〇 の勝利 か 引き分け であるかを 正しく判定できる ということを意味します。そのため、ai14s は 8 手目の局面 に対して 局面の状況 が 〇 の必勝の局面、× の必勝の局面、引分の局面 のいずれかであることを 正確に判定 することができます。

上記から 深さの上限を 8 とした場合は、深さ制限探索の計算の中で 静的評価関数 ai14s は 常に正確な評価値を計算 します。

静的評価関数 が計算する すべてのノード に対して 正確な評価値が計算される 場合は 深さを制限しない探索と同じ計算 が行われるので、計算される値は 正確なミニマックス値 となります。〇× は ゲーム開始時の局面 では すべての合法手が最善手 なので、先程の 深さの上限を 8 とした場合の計算結果では すべての合法手の一覧が最善手 となります。

深さの上限を 9 とした場合は、9 手目の局面 が 必ず決着がついた局面 になるので、同様の理由で 正確なミニマックス値が計算 され、すべての合法手の一覧が最善手 となります。

深さの上限を 6 以下 とした場合は 静的評価関数 ai14s が計算するノードの 評価値を正確に計算できない場合 があります。具体的な検証は長くなるので行いませんが、そのような場合は ai14s が計算する 近似値の性質 からゲーム開始時の局面に対して (1, 1) のみが最善手として計算 されるようです。興味がある方はそのようになる理由を検証してみて下さい。

置換表を利用する場合の検証

下記は use_tt=True を記述して 置換表を利用する場合 で反復深化を行うプログラムです。なお、analyze=True は削除しました。実行結果から、置換表の利用 によって 処理時間が大幅に減る ことが確認できます。

print(ai_ab_iddfs(mb, timelimit=10, debug=True, eval_func=ai14s,
                  eval_params=eval_params, use_tt=True))

実行結果

maxdepth: 0, time:   0.00 ms, bestmove: (1, 1)
maxdepth: 1, time:   0.02 ms, bestmove: (1, 1)
maxdepth: 2, time:   0.07 ms, bestmove: (1, 1)
maxdepth: 3, time:   0.15 ms, bestmove: (1, 1)
maxdepth: 4, time:   0.31 ms, bestmove: (1, 1)
maxdepth: 5, time:   0.62 ms, bestmove: (1, 1)
maxdepth: 6, time:   1.05 ms, bestmove: (1, 1)
maxdepth: 7, time:   1.47 ms, bestmove: (1, 2)
maxdepth: 8, time:   1.91 ms, bestmove: (0, 2)
totaltime:   1.91 ms
(0, 2)

下記はさらに share_tt=True を記述して 置換表を共用 する場合で反復深化を行うプログラムです。実行結果から、置換表の共用 によって 処理時間がさらに大幅に減る ことが確認できました。

print(ai_ab_iddfs(mb, timelimit=10, debug=True, eval_func=ai14s,
                  eval_params=eval_params, use_tt=True, share_tt=True))

実行結果

maxdepth: 0, time:   0.00 ms, bestmove: (1, 1)
maxdepth: 1, time:   0.00 ms, bestmove: (1, 1)
maxdepth: 2, time:   0.01 ms, bestmove: (1, 1)
maxdepth: 3, time:   0.02 ms, bestmove: (1, 1)
maxdepth: 4, time:   0.05 ms, bestmove: (1, 1)
maxdepth: 5, time:   0.11 ms, bestmove: (1, 1)
maxdepth: 6, time:   0.18 ms, bestmove: (1, 1)
maxdepth: 7, time:   0.25 ms, bestmove: (1, 2)
maxdepth: 8, time:   0.31 ms, bestmove: (0, 1)
totaltime:   0.31 ms
(0, 1)

深さ制限探索の途中で制限時間を超えた場合の処理

上記では 深さ制限探索の途中 で 制限時間を超えた場合 に 処理を中断してない ので、残りの処理に時間がかかるような場合は 制限時間を大幅に超えてしまう可能性 が生じます。そこで、深さ制限探索の途中 であっても制限時間を超えた場合は 即座に処理を中断する ように修正することにします。

そのためには、深さ制限探索を行う ai_abs_dls に 制限時間を代入 する 仮引数を追加 し、制限時間を超えた場合 に 処理を中断する処理を記述 する必要があります。どのような処理を記述すれば良いかについて少し考えてみて下さい。

ai_abs_dls の処理では、ローカル関数 ab_search を 何度も再帰呼び出し することで処理を行っています。ab_search が行う処理の中で 再帰呼び出し以外 の処理はそれほど 処理時間を必要としない ので、ab_search が呼び出された際 に 制限時間を超えているかを判定 し、超えている場合に残りの処理をすべて中断する処理 を記述するという方法が考えられます。

非推奨だが昔使われていた方法

再帰呼び出しに限らず、関数呼び出しを何度も行う処理の途中 で 残りの処理を中断する方法 として、昔は 下記のような方法が 実際に良く使われていました。この手法はわかりづらいので お勧めはしません が、全く使われなくなったというわけではないと思いますので、参考までにその方法を紹介することにします。

• 関数の処理の途中 で残りの 処理の中断が必要 になった際に、処理の中断が行われた ことを表す、通常の処理 が行われた場合と 区別できる ような 特別な値 を 返り値として返す
• 関数の処理の途中 で 他の関数 を呼び出した際の 返り値 としてその 特別な値が返ってきた場合 は、残りの処理を中断する必要があるのでその 特別な値を返り値として返す

例えば、ai_search は 通常は 返り値として 数値型のデータを返す ので、制限時間を超えた際 に 数値型と区別できる None を返す という方法が考えられます。下記はそのように ai_abs_dls を修正したプログラムです。

• 4 行目：デフォルト値を None とする仮引数 timelimit_pc を追加する。この timelimit_pc は制限時間の秒数ではなく、この値を perf_counter() が超えた場合 に 制限時間を超えたことを表す値 である点に注意すること（その理由は下記のノートで説明する）。代入された値が None の場合 はこれまで通り 制限時間がない ものとする
• 10、11 行目：timelimit_pc が None でない場合で、制限時間を超えている場合は None を返り値として返すように修正する
• 17 ~ 19、29 ~ 31 行目：ab_search を再帰呼び出しする際に、その返り値を abscore に代入するように修正し、返り値が None の場合は None を返すように修正する
• 20、29 行目：abscore が None でない場合はこれまで通りの処理を行うように修正する

 1  from ai import ai_by_mmscore
 2  
 3  @ai_by_mmscore
 4  def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
 5                 eval_params={}, use_tt=False, tt=None, calc_count=False):
 6      count = 0
 7      def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
 8          nonlocal count
 9  
10          if timelimit_pc is not None and perf_counter() >= timelimit_pc:
11              return None       
元と同じなので省略
12          if mborig.turn == Marubatsu.CIRCLE:
13              score = float("-inf")
14              for x, y in legal_moves:
15                  mb = deepcopy(mborig)
16                  mb.move(x, y)
17                  abscore = ab_search(mb, depth + 1, tt, alpha, beta)
18                  if abscore is None:
19                      return None
20                  score = max(score, abscore)
21                  if score >= beta:
22                      break
23                  alpha = max(alpha, score)
24          else:
25              score = float("inf")
26              for x, y in legal_moves:
27                  mb = deepcopy(mborig)
28                  mb.move(x, y)
29                  abscore = ab_search(mb, depth + 1, tt, alpha, beta)
30                  if abscore is None:
31                      return None
32                  score = min(score, abscore)
33                  if score <= alpha:
34                      break
35                  beta = min(beta, score)   
元と同じなので省略 
36     score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)

行番号のないプログラム

from ai import ai_by_mmscore

@ai_by_mmscore
def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
               eval_params={}, use_tt=False, tt=None, calc_count=False):           
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count

        if timelimit_pc is not None and perf_counter() >= timelimit_pc:
            return None       
        count += 1
        if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
            return eval_func(mborig, calc_score=True, **eval_params)
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                abscore = ab_search(mb, depth + 1, tt, alpha, beta)
                if abscore is None:
                    return None
                score = max(score, abscore)
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                abscore = ab_search(mb, depth + 1, tt, alpha, beta)
                if abscore is None:
                    return None
                score = min(score, abscore)
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = float("-inf")
    max_score = float("inf")
    
    if tt is None:
        tt = {}
    score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    return score

修正箇所

from ai import ai_by_mmscore

@ai_by_mmscore
-def ai_abs_dls(mb, debug=False, maxdepth=1, eval_func=None,
+def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
               eval_params={}, use_tt=False, tt=None, calc_count=False):                        
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count

+       if timelimit_pc is not None and perf_counter() >= timelimit_pc:
+           return None       
元と同じなので省略
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = max(score, ab_search(mb, depth + 1, tt, alpha, beta))
+               abscore = ab_search(mb, depth + 1, tt, alpha, beta)
+               if abscore is None:
+                   return None
+               score = max(score, abscore)
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
-               score = min(score, ab_search(mb, depth + 1, tt, alpha, beta))
+               abscore = ab_search(mb, depth + 1, tt, alpha, beta)
+               if abscore is None:
+                   return None
+               score = min(score, abscore)
                if score <= alpha:
                    break
                beta = min(beta, score)   
元と同じなので省略     
    score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
元と同じなので省略     

制限時間を表す仮引数に制限時間を表す秒数を代入するようにしない理由の一つは、反復深化の処理の中 で 何度も ai_abs_dls の呼び出しが行われる からです。ai_abs_dls を呼び出すたびに処理時間が必要となるため、次の ai_abs_dls を呼び出す際に残りの制限時間の秒数を計算し直す必要が生じます。

他の理由としては、@ai_by_mmscore のラッパー関数の中でも同様に mb のそれぞれの子ノードに対して ai_abs_dls が複数回呼び出されるというものがあり、制限時間の秒数を計算し直すためには @ai_by_mmscore を修正する必要が生じます。

一方で、仮引数 timilimit_pc に制限時間の時点での perf_counter() の値を仮引数に代入する場合は、そのような処理を行う必要はありません。

上記の修正後に下記のプログラムで、制限時間を設けず に ゲーム開始時の局面 に対して 深さの上限を 9 として ai_abs_dls で近似値のミニマックス値を計算すると、実行結果のように正しい値である 0.0 が表示 されます。また、その際に筆者のコンピューターでは 約 1 秒の処理時間 がかかることがわかります。

starttime = perf_counter()
print(ai_abs_dls(mb, maxdepth=9, eval_func=ai14s, eval_params=eval_params, calc_score=True))
print(perf_counter() - starttime)

実行結果

0.0
0.9793322999030352

そこで下記のプログラムのように timelimit_pc=starttime + 0.5 を記述して 制限時間を 0.5 秒 として処理を行うようにしたところ、実行結果のように None が表示 され、0.5 秒で処理が行われた ことが確認できます。

starttime = perf_counter()
print(ai_abs_dls(mb, maxdepth=9, timelimit_pc=starttime + 0.5, eval_func=ai14s, 
                 eval_params=eval_params, calc_score=True))
print(perf_counter() - starttime)

実行結果

None
0.5002430994063616

例外による実装方法

上記のような実装方法は、筆者の記憶では 2000 年頃までは良く使われていたのではないかと思いますが、以下のような 欠点がある ので 現在ではあまり使われていない と思います。

• 処理の中断が必要になった場合 に、通常の処理の返り値 と 区別できる ような 特別な返り値 を考えて返す必要がある。また、そのことにより返り値の 意味がわかりづらくなる
• 関数呼び出しを行う際 に 返り値をチェック して 処理の中断を行う処理を記述 する必要がある点が 面倒 なだけでなく わかりづらい
• 処理の中断を行う処理 を、処理の中断が必要となった以外の場所 で記述する必要がある点が 面倒 で、記述忘れ による バグが発生しやすい

処理を中断 する別の手法として、例外（exception）を発生 させるという手法があります。プログラムの処理中に何らかの理由でそれ以上の 処理を続けられなくなった時 に 例外を発生させる ことで 処理を中断 することができます。

Python では エラーが発生 した際に 例外が利用 されています。Python には あらかじめ定義 された様々な 組み込み例外が定義 されており、下記のように エラーが発生するようなプログラムを実行 すると、エラーが発生した時に 例外を発生する処理が実行 されて プログラムが中断 します。JupyterLab のセルで実行したプログラムで 例外が発生 すると、どこで例外が発生した か、例外の名称、例外が発生した 原因を表すメッセージ などが表示されます。

下記は list の 存在しないインデックス の要素を表示するプログラムです。実行結果には 例外が発生した場所、インデックスに関するエラーを表す IndexError という 組み込み例外の名称 と、list index out of range という メッセージが表示 されます。

a = []
print(a[10])

実行結果

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[13], line 2
      1 a = []
----> 2 print(a[10])

IndexError: list index out of range

例外は raise 文 によって 発生させる ことができます。下記は、IndexError を発生 させるプログラムです。raise 文 では 例外の名前を記述 し、() の中に文字列を記述 するこで実行結果のようにエラーの原因を表す メッセージを表示 することができます。

なお、() を記述し、その中に実引数を記述することができることからわかるように、Python の 例外 は クラスとして定義 されています。

raise IndexError("人為的に発生させたエラー")

実行結果

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[14], line 1
----> 1 raise IndexError("人為的に発生させたエラー")

IndexError: 人為的に発生させたエラー

例外についての詳細は下記のリンク先を参照して下さい。

ai_abs_dls の修正

汎用的な目的 で利用できる 例外 として RuntimeError があるので、制限時間を超えた場合 に RuntimeError を発生 させるように ai_abs_dls を修正 することにします。修正箇所 は先ほど修正した ai_abs_dls からの修正ではなく、その 修正を行う前の ai_abs_dls からの修正 です。先ほどの修正と異なり 修正箇所 は 仮引数 timelimit_pc の追加 と、時間制限を超えた場合に例外を発生させる処理だけ で、それ以外の部分を修正する必要はありません。

• 2 行目：timelimit_pc を仮引数として追加する
• 7、8 行目：時間制限を超えた場合は RuntimeError を発生させるように修正する。その際に "time out" というメッセージを表示するようにした

1  @ai_by_mmscore
2  def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None, 
3                 eval_params={}, use_tt=False, tt=None, calc_count=False):           
4      count = 0
5      def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
6          nonlocal count
7          if timelimit_pc is not None and perf_counter() >= timelimit_pc:
8              raise RuntimeError("time out")
元と同じなので省略        
9      score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
元と同じなので省略

行番号のないプログラム

@ai_by_mmscore
def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
               eval_params={}, use_tt=False, tt=None, calc_count=False):           
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        if timelimit_pc is not None and perf_counter() >= timelimit_pc:
            raise RuntimeError("time out")
        
        count += 1
        if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
            return eval_func(mborig, calc_score=True, **eval_params)
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, depth + 1, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, depth + 1, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = float("-inf")
    max_score = float("inf")
    
    if tt is None:
        tt = {}
    score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    return score

修正箇所

@ai_by_mmscore
-def ai_abs_dls(mb, debug=False, maxdepth=1, eval_func=None,
+def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
               eval_params={}, use_tt=False, tt=None, calc_count=False):           
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
+       if timelimit_pc is not None and perf_counter() >= timelimit_pc:
+           raise RuntimeError("time out")
元と同じなので省略        

上記の修正後に先程と同じ下記のプログラムを実行すると、制限時間を設けていない ので 先程と同様の処理 が行われます。

starttime = perf_counter()
print(ai_abs_dls(mb, maxdepth=9, eval_func=ai14s, eval_params=eval_params, calc_score=True))
print(perf_counter() - starttime)

実行結果

0.0
1.0038612000644207

一方下記のプログラムで先ほどと同様に 制限時間を 0.5 秒 とした場合は、実行結果のように RuntimeError と time out というメッセージが表示 されるようになります。なお、処理が中断された のでその後の 処理時間を計測して表示する処理は行われません。

starttime = perf_counter()
print(ai_abs_dls(mb, maxdepth=9, timelimit_pc=starttime + 0.5, eval_func=ai14s, 
                 eval_params=eval_params, calc_score=True))
print(perf_counter() - starttime)

実行結果

---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
Cell In[17], line 2
      1 starttime = perf_counter()
----> 2 print(ai_abs_dls(mb, maxdepth=9, timelimit_pc=starttime + 0.5, eval_func=ai14s, 
      3                  eval_params=eval_params, calc_score=True))
略
Cell In[15], line 8
      6 nonlocal count
      7 if timelimit_pc is not None and perf_counter() >= timelimit_pc:
----> 8     raise RuntimeError("time out")
     10 count += 1
     11 if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
     
RuntimeError: time out

例外処理を利用した ai_ab_iddfs の修正

例外が発生した場合 は、以前の記事で説明した 例外処理を記述 することで、プログラムの中断を行わず に 処理を続行 することができます。以前の記事では 任意の例外が発生した場合 の処理を下記のように記述すると説明しました。

try:
    プログラム
except:
    try のブロックで例外が発生した時に行う処理

下記のように記述することで、特定の例外が発生した場合 の処理を記述することができます。また、except 例外の種類 を複数記述 することで、複数の例外に対する処理 を 個別に記述 することもできます。なお、except 例外の種類 を記述しなかった例外が発生 した場合は通常通りプログラムの 処理が中断 されます。

try:
    プログラム
except 例外の名前:
    try のブロックで例外が発生した時に行う処理

この例外処理を利用することで、ai_ab_iddfs を下記のプログラムのように修正することができます。

• 1 行目の timelimit は制限時間を表す秒数のまま変更する必要はない点に注意すること
• 6 ~ 12 行目：例外処理を利用して ai_abs_dls を呼び出し、時間制限を超えて RuntimeError が発生した場合は "time out" というメッセージを表示し、 break 文で繰り返し処理を中断するように修正する
• 7 行目：実引数に制限時間を表す timelimit_pc=timelimit_pc を記述するように修正した

 1  def ai_ab_iddfs(mb, debug=False, timelimit=10, eval_func=None, eval_params={}, use_tt=False, share_tt=False, analyze=False):
 2      starttime = perf_counter()
 3      timelimit_pc = starttime + timelimit
 4      bestmove = random.choice(mb.calc_legal_moves())
 5      for maxdepth in range(9 - mb.move_count):
 6          try:
 7              result = ai_abs_dls(mb, maxdepth=maxdepth, timelimit_pc=timelimit_pc,
 8                                  eval_func=eval_func, eval_params=eval_params,
 9                                  use_tt=use_tt, share_tt=share_tt, analyze=analyze)
10          except RuntimeError:
11              dprint(debug, "time out")
12              break
元と同じなので省略

行番号のないプログラム

def ai_ab_iddfs(mb, debug=False, timelimit=10, eval_func=None, eval_params={}, use_tt=False, share_tt=False, analyze=False):
    starttime = perf_counter()
    timelimit_pc = starttime + timelimit
    bestmove = random.choice(mb.calc_legal_moves())
    for maxdepth in range(9 - mb.move_count):
        try:
            result = ai_abs_dls(mb, maxdepth=maxdepth, timelimit_pc=timelimit_pc,
                                eval_func=eval_func, eval_params=eval_params,
                                use_tt=use_tt, share_tt=share_tt, analyze=analyze)
        except RuntimeError:
            dprint(debug, "time out")
            break

        if analyze:
            candidate = result["candidate"]
            bestmove = random.choice(candidate)
            dprint(debug, f"maxdepth: {maxdepth}, time: {perf_counter() - starttime:6.2f} ms, bestmove: {bestmove}, candidate: {candidate}")
        else:
            bestmove = result
            dprint(debug, f"maxdepth: {maxdepth}, time: {perf_counter() - starttime:6.2f} ms, bestmove: {bestmove}")
    dprint(debug, f"totaltime: {perf_counter() - starttime: 6.2f} ms")
    return bestmove

修正箇所

def ai_ab_iddfs(mb, debug=False, timelimit=10, eval_func=None, eval_params={}, use_tt=False, share_tt=False, analyze=False):
    starttime = perf_counter()
    timelimit_pc = starttime + timelimit
    bestmove = random.choice(mb.calc_legal_moves())
    for maxdepth in range(9 - mb.move_count):
+       try:
+           result = ai_abs_dls(mb, maxdepth=maxdepth, timelimit_pc=timelimit_pc,
+                               eval_func=eval_func, eval_params=eval_params,
+                               use_tt=use_tt, share_tt=share_tt, analyze=analyze)
+       except RuntimeError:
+           dprint(debug, "time out")
+           break
元と同じなので省略

上記の修正後に下記のプログラムで先程と同様に 制限時間を 10 秒 として計算を行うと、先程と同様の結果 になります。

print(ai_ab_iddfs(mb, timelimit=10, debug=True, eval_func=ai14s,
                  eval_params=eval_params, analyze=False))

実行結果

maxdepth: 0, time:   0.00 ms, bestmove: (1, 1)
maxdepth: 1, time:   0.01 ms, bestmove: (1, 1)
maxdepth: 2, time:   0.05 ms, bestmove: (1, 1)
maxdepth: 3, time:   0.18 ms, bestmove: (1, 1)
maxdepth: 4, time:   0.44 ms, bestmove: (1, 1)
maxdepth: 5, time:   1.24 ms, bestmove: (1, 1)
maxdepth: 6, time:   2.69 ms, bestmove: (1, 1)
maxdepth: 7, time:   4.23 ms, bestmove: (2, 2)
maxdepth: 8, time:   5.83 ms, bestmove: (2, 2)
totaltime:   5.83 ms
(2, 2)

一方、下記のプログラムで 制限時間を 3 秒 として計算を行うと、先程と異なり 深さの上限が 6 の処理の最中に制限時間を超える ため処理が中断され、深さの上限が 5 の場合の最善手 が返り値として返るようになります。また、"time out" と表示されることから 制限時間で処理が中断されたこと と、処理時間が 3 秒であったこと が実行結果から確認できます。

print(ai_ab_iddfs(mb, timelimit=3, debug=True, eval_func=ai14s,
                  eval_params=eval_params, analyze=False))

実行結果

maxdepth: 0, time:   0.00 ms, bestmove: (1, 1)
maxdepth: 1, time:   0.02 ms, bestmove: (1, 1)
maxdepth: 2, time:   0.07 ms, bestmove: (1, 1)
maxdepth: 3, time:   0.15 ms, bestmove: (1, 1)
maxdepth: 4, time:   0.41 ms, bestmove: (1, 1)
maxdepth: 5, time:   1.18 ms, bestmove: (1, 1)
maxdepth: 6, time:   2.56 ms, bestmove: (1, 1)
time out
totaltime:   3.00 ms
(1, 1)

今回の記事のまとめ

今回の記事では 反復深化 について説明し、αβ 法による反復深化 を行う ai_ab_iddfs を実装しました。

反復深化は 制限時間まで深さの上限を増やしながら計算 を行うため、制限時間内で計算できた 最も大きな深さの上限での計算結果を得る ことができます。一方で、それより小さな深さの上限で行う計算 に 無駄な処理時間が費やされる のがもったいないと感じる人がいるかもしれません。次回の記事ではその点についての説明を行います。

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

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
ai.py	本記事で更新した ai_new.py

次回の記事

1. calc_score=True を記述しないと、mb のそれぞれの子ノードに対するミニマックス値を計算して最善手を計算するという処理が行われるので、mb をルートノードとするゲーム木のノードの数は計算されません ↩

2. 公式のドキュメントには highest resolution と表記されているので、直訳すると「最も解像度（highest）が高い」としたほうが良いかもしれませんが、精度の方がわかりやすいと思いましたのでそのように表記しました ↩

3. この処理は、深さの上限を 1 とした深さ制限探索を制限時間内に行うことができない場合の処理です。ただし、通常は深さの上限を 1 とした深さ制限探索の処理はほぼ一瞬で終わるので、この処理で bestmove に代入された合法手が最善手として採用されることはまずないでしょう ↩