- 〇×ゲーム（三目並べ・Tic-Tac-Toe）の敵のAIのミニマックス法というアルゴリズムで作ります。
- 勉強のため、Pythonの標準モジュールを中心に使って自分でコードを書いていって理解を深めます。
ミニマックス法とは
英語ではMinimax algorithm。
ターン制のゲームなどでの敵AIでよく使われる、好ましい選択肢の算出用の探索アルゴリズムです。
〇×ゲーム（三目並べ）やオセロ、チェスなど様々なゲームのAIとして使うことができます。
取れる選択肢がどのくらい性能が良いのかを評価する評価関数を設け、なるべく「自分のターンでは評価が最大（max側）になる」選択肢を選択し、逆に「相手のターンでは自分の評価値が最小になる選択を相手は取ってくる」と想定して選択肢を選び、結果的に得られる評価値を取得するといったアルゴリズムになります。
各選択での評価値を得られるので、結果的にAI側がどの選択をすれば強いのかを計算することができます。
どんな計算なのか
説明のため、〇×ゲームで先攻がプレイヤー、後攻がミニマックス法を使ったAIで話を進めます。
また、以下のように各マスに番号を付けておきます（コードで対応する際の1次元の配列のインデックスにそのまま該当します）。
先攻で負けるケースはあまりありませんが、わざと先攻の〇（プレイヤー）側が負けるような以下のケースを考えます。
×（AI）側はどこを選ぶべきでしょう？答えは真ん中で、そうすると右上と左下の2つでリーチとなるのでAI側が勝利することができます。
この真ん中のマスを算出する際の計算を考えてみます。
AI側が取れる選択肢は以下の2, 4, 7, 8のマス（青い数字部分）となります。
これをゲーム木と呼ばれる選択肢の木の有向グラフで表現すると以下のようになります。
それぞれのAI側の選択の後には、プレイヤー側がとりうる選択肢が以下のように3つずつ、計12個が以下の画像のように存在します。青の数字をAI側の選択肢、赤の選択肢をプレイヤー側の選択肢にしてあります。
同様に最後の1マスまでゲーム木で表現すると以下のようになります。以降、小さい画像に関しては必要な場合はクリックしてご確認ください。
ここで対象の選択肢のリストを見てみると、4（真ん中）以外を選択すると真ん中の行で〇が揃ってしまうので×（AI）側が負けてしまうことが分かります。
ゲーム木の末端に勝敗を反映すると以下のようになります。
最初に4を選ぶ以外の選択はどう選択しても負けになるので、4を選んだ時のMinimaxの計算にフォーカスしてみます。
×（AI・青の数字）側のオレンジ色の枠部分の階層について考えてみます。
評価の指標として、勝ちを1ポイント・引き分けを0ポイント・分けを-1ポイントと評価するとしましょう。
前述したようにミニマックス法ではAI側の計算で評価が最大（max側）になる選択を取ります。つまり7の選択をすると（負けてしまって）評価値が最大にならないので7の選択肢を消します。
また、真ん中の2と8という選択肢の部分に関してはどちらを選択しても勝ちで評価値は一緒なので先頭の方の2を残します。
一つ上の〇の階層（プレイヤー・赤の数字）を見てみます。今度はプレイヤー側となるので評価値が最小（min）になるような選択（つまりAI側がなるべく負けるようになる選択）をするようにします。ただしこの例だとどこもAI側の勝利となる選択肢しか残っていないので勝ちの評価を上の階層に伝搬させます。
4を選んだ時には勝ちの分岐しかなくなったため、そのまま上まで勝ちの評価を伝搬させます。
結果的に2, 4, 7, 8それぞれにミニマックス法を反映すると、2 = -1（負け）, 4 = 1（勝ち）, 7 = -1（負け）, 8 = -1（負け）となり、AI側としては評価結果が最大になる選択肢を取ればいいので2を選択すれば良いということになります。
最小化の計算が上記の例だと微妙なので補足として以下のような数字などを割愛したシンプルな例を見ていきます。
プレイヤー側（赤の数字）部分では最小化（min側）を行う（AI側がなるべく負けるようにする）形で伝搬をさせるため、「左の勝ちと引き分けの分岐では引き分けを」「真ん中の負けと勝ちの分岐では負けを」「右の勝ちと負けの分岐では負けを」上の階層に渡すようになります。
つまりAI側の選択肢としては勝ちが無くなります。一番良い選択肢でも左の引き分けとなります（引き分け・負け・負けの中で評価値を最大化する形で、引き分けを選択）。
ミニマックス法の特徴
前述のように、算出にはゲーム木を使うため、下の階層にいくために再帰的に計算をする必要が出てきます。計算を行う最大の階層数増やす程精度が高くなりますが、その分計算量がたくさん必要になってきます（チェスなどで言うと、階層数が「何手先まで読むか」といったような感じになってきます。先をたくさん読めば読むほどたくさん計算が必要になります）。
また、相手が取れる選択肢が分からないとゲーム木が組めないため、そういった相手の選択肢が分かるいわゆる「完全情報ゲーム」と呼ばれるゲームにしか反映ができません（〇×ゲームやオセロ、チェスなど）。
たとえば手札がAI側から見えないといったような「不完全情報ゲーム」（相手が何の手札を持っているか分からないようなゲーム）と呼ばれるものではミニマックス法は使えません。
Pythonでの実装
実際に〇×ゲームとミニマックス法を勉強のためにPythonで書いていってみます。
今回使うもの
- Python 3.8.5
- VS Code
- Pylance（型チェック用）
※他の記事と同様に勉強のため基本的にPythonの標準モジュールを中心に使って対応していきます。
今回触れないもの
ベーシックなMinimax法を発展・計算の効率化などがされたもの（alpha-beta法など）は今回は触れません。
必要なもののimport
まずは利用するモジュールのimportを行います。
from __future__ import annotations
from typing import List, Tuple
from enum import Enum
from copy import deepcopy
annotationsはPython3.10以降でデフォルトになる型アノテーションの機能を利用するためにimportしています（今回の記事ではPython3.8.5を使っています）。
ListとTupleも型アノテーション用です。Python3.9からはimportが不要になります（listやtupleで直接アノテーションができる形に）。
deepcopy関数はミニマックス法の過程で算出のパターンを何度も盤面を元のものを利用したりするため、元の盤面の状態のものをディープコピーするために利用します。
〇×のマーク用のクラスを定義する
Enumを継承する形で、盤面上のマークを扱うためのクラスを定義します。〇をO、×をX、空のマスをEとして定数を定義しています。
class Mark(Enum):
"""
〇×ゲームの各マスの1つ分のマークの値を扱うクラス。
Attributes
----------
O : str
〇に該当するマーク。
X : str
×に該当するマーク。
E : str
マスにマークが設定されていない場合の値（empty）。
空のスペースが設定される。
"""
O = 'O'
X = 'X'
E = ' '
def get_opponent(self) -> Mark:
"""
相手側のセルの値を取得する。
Returns
-------
opponent : Piece
相手側のセルの値。〇であれば×が、×であれば〇が設定される。
空の値の場合はそのまま空の値が設定される。
"""
if self == Mark.O:
return Mark.X
if self == Mark.X:
return Mark.O
return Mark.E
def __str__(self) -> str:
"""
マークの文字を返却する。
Returns
-------
mark : str
定義されているいずれかのマークの文字。
"""
return self.value
get_opponentメソッドはターン切り替えの際のために利用します。現在〇であれば×を、現在×であれば〇を返却する挙動をします。
マスの位置を扱うクラスの定義
マスの位置を扱うクラスを追加していきます。以下の画像のように行列ではなく1次元で、0～8のインデックスで扱う形で進めます。
class Position:
def __init__(self, index: int) -> None:
"""
マスのインデックスを扱うクラス。インデックスは1次元で0～8の範囲で
以下のような位置が該当する。
0 1 2
3 4 5
6 7 8
Parameters
----------
index : int
対象のインデックス（0～8）。
Raises
------
ValueError
範囲外のインデックスが指定された場合。
"""
index_range: List[int] = list(range(0, 9))
if index not in index_range:
raise ValueError('指定されたインデックスが範囲外の値です : %s' % index)
self.index = index
def __eq__(self, obj: object) -> bool:
"""
他のPositionクラスと同値かどうかの比較を行う。
Parameters
----------
obj : *
比較対象のオブジェクト。
Returns
-------
result : bool
比較結果。対象がPositionクラスで、且つインデックスの
値が同じ場合にはTrueが設定される。
"""
if not isinstance(obj, Position):
return False
if self.index == obj.index:
return True
return False
def __repr__(self) -> str:
"""
文字列変換した際の表示値を返却する。
Returns
-------
repr_str : str
インデックスの値の文字が設定される。
"""
return repr(self.index)
クラスのインスタンス同士での比較を計算過程でするため、__eq__などのメソッドを追加しています。
〇×ゲームの盤面の状態などを扱うためのクラスの定義
続いて〇×ゲームの盤面用のクラスを追加していきます。〇×ゲーム（三目並べ）は英語でtic-tac-toeなのでクラス名はTicTacToeとしてあります。
class TicTacToe:
def __init__(self, turn: Mark, marks: List[Mark]=None) -> None:
"""
〇×ゲーム（tic-tac-toe）を扱うクラス。
Parameters
----------
turn : Mark
現在のターンのマーク。Mark.OもしくはMark.Xが必要になる。
marks : list of Mark, default None
現在の各マスに設定されているマークのリスト。1次元のリストで、
以下のような割り振りで0～8のインデックスで設定する。
0 1 2
3 4 5
6 7 8
デフォルト値が指定された場合には全てのマスが空の状態が
設定される。
"""
if marks is None:
marks = [Mark.E] * 9
self._turn = turn
self.marks = marks
基本的にこのクラスのインスタンスはターン切り替えや他のマスの選択の計算をする時などに都度インスタンスを生成する形で利用するため、次の1手が〇なのか×なのかのターンの識別用の値をコンストラクタで扱うようにします。
また、現在の盤面のマークの配置を扱うリストも同様にコンストラクタで属性に設定しています。こちらの値はNoneが設定された場合には9個の空のマーク（Mark.E）で初期化しています。
続いて特定のマスに新しい〇か×のマークを配置し、ターンの切り替えを行うメソッドを追加します。
def set_new_mark_and_change_turn(
self, position: Position) -> TicTacToe:
"""
特定のマスの位置に〇もしくは×のマークを設定する。
Notes
-----
設定されるマークはこのクラスに設定されているターンの属性に依存する。
Parameters
----------
position : Position
マークを設定する位置。
Raises
------
ValueError
すでにマークが設定されているマスの位置が指定された場合。
Returns
-------
new_tic_tac_toe : TicTacToe
マークの設定とターンの切り替え後の〇×ゲームのインスタンス。
※各探索でループで元のインスタンスも利用するため、
ディープコピーされたインスタンスが設定される。
"""
current_mark: Mark = self.marks[position.index]
if current_mark != Mark.E:
raise ValueError(
'対象のマスに既にマークが設定されています : '
f'position: {position}, mark: {current_mark}'
)
new_marks: List[Mark] = deepcopy(self.marks)
new_marks[position.index] = self._turn
new_turn: Mark = self._turn.get_opponent()
new_tic_tac_toe: TicTacToe = TicTacToe(
turn=new_turn, marks=new_marks)
return new_tic_tac_toe
引数に渡した〇×ゲームのインスタンスは，ゲーム木のグラフの別のノードの検証でも再利用するため、このメソッドで影響を出さないように盤面の状態をディープコピーして指定された位置へのマークの配置、ターンの切り替え（get_opponentによる、〇であれば×、×であれば〇への切り替え）を行い、変化させた後の新しい〇×ゲームのインスタンスを返却するようにしています。
元のインスタンスへは変更は加えていません。
プレイヤーやAIの、マーク配置箇所の選択用に、マークが配置されていない空の位置（Mark.E）のリスト取得用のメソッドと該当の位置が空のマスかどうかの判定用のメソッドを追加します。
def get_empty_positions(self) -> List[Position]:
"""
空いている（マークの設定されていない）マスの位置のリストを
取得する。
Returns
-------
empty_positions : list of Position
空いている（マークの設定されていない）マスの位置のリスト。
"""
empty_positions: List[Position] = []
for index, mark in enumerate(self.marks):
if mark != Mark.E:
continue
empty_positions.append(Position(index=index))
return empty_positions
def is_empty_position(self, position: Position) -> bool:
"""
指定された位置が空のマスかどうかの真偽値を取得する。
Parameters
----------
position : Position
判定対象の位置。
Returns
-------
result : bool
もし空のマスの位置であればTrueが設定される。
"""
empty_positions: List[Position] = self.get_empty_positions()
for empty_position in empty_positions:
if position == empty_position:
return True
return False
続いて勝利判定に使うための定数を設けます。勝利判定の基準となる3つの位置のセットを定義します。3つの位置（Position）の値を格納するタプルのリストで扱います。
_ConditionPositions = Tuple[Position, Position, Position]
_CONDITION_POSITIONS: List[_ConditionPositions] = [
(Position(0), Position(1), Position(2)),
(Position(3), Position(4), Position(5)),
(Position(6), Position(7), Position(8)),
(Position(0), Position(3), Position(6)),
(Position(1), Position(4), Position(7)),
(Position(2), Position(5), Position(8)),
(Position(0), Position(4), Position(8)),
(Position(2), Position(4), Position(6)),
]
_ConditionPositionsはこの型は他でも型アノテーションで利用するので、長くなりすぎたり重複した記述が多くなって煩雑なので、型エイリアスとして設定しています。
例えば(Position(0), Position(1), Position(2))という部分でいえば、0, 1, 2のインデックスは以下の画像のように上の行の三つの部分に該当します。
勝利判定用の処理を追加していきます。
@property
def is_player_win(self) -> bool:
"""
プレイヤー側が勝利したかどうか。
Returns
-------
result : bool
プレイヤー側が勝利しているかどうか。
"""
return self._is_target_mark_win(mark=Mark.O)
@property
def is_ai_win(self) -> bool:
"""
AI側が勝利したかどうか。
Returns
-------
result : bool
AI側が勝利しているかどうか。
"""
return self._is_target_mark_win(mark=Mark.X)
def _is_target_mark_win(self, mark: Mark) -> bool:
"""
指定されたマーク側が勝利しているかどうかの真偽値を取得する。
Parameters
----------
mark : Mark
判定対象のマーク。
Returns
-------
result : bool
勝利している場合にはTrueが設定される。
"""
for condition_positions in self._CONDITION_POSITIONS:
condition_satisfied: bool = \
self._is_condition_satisfied_positions(
condition_positions=condition_positions,
target_mark=mark)
if condition_satisfied:
return True
return False
def _is_condition_satisfied_positions(
self, condition_positions: _ConditionPositions,
target_mark: Mark) -> bool:
"""
条件を満たしている位置の組み合わせ（3つ同じマークが並んでいるか）が
存在するかどうかの真偽値を取得する。
Parameters
----------
condition_positions : _ConditionPositions
チェック対象の3つの位置の組み合わせを格納したタプル。
target_mark : Mark
対象のマーク。
Returns
-------
result : bool
条件を満たせばTrueが設定される。
"""
is_target_marks: List[bool] = []
for condition_position in condition_positions:
mark: Mark = self.marks[condition_position.index]
if mark == target_mark:
is_target_marks.append(True)
continue
is_target_marks.append(False)
return all(is_target_marks)
現在の盤面状況が、プレイヤー側が勝利しているか（is_player_win）もしくはAI側が勝利しているか（is_ai_win）の属性を設けています。
内部では先ほど用意したタプルの3つの位置の値が全て対象のマーク（プレイヤー側であれば〇、AI側であれば×）になっているかどうかで判定しています。
引き分け判定も追加していきます。こちらは勝利判定よりもシンプルです。
@property
def is_draw(self) -> bool:
"""
引き分けの状態かどうかの真偽値。
Returns
-------
result : bool
引き分けかどうかの真偽値。勝敗が付いていない状態で、
且つ空いているマスが無くなった状態でTrueとなる。
"""
empty_position_num: int = len(self.get_empty_positions())
if self.is_player_win:
return False
if self.is_ai_win:
return False
if empty_position_num != 0:
return False
return True
以下のような条件で判定がされます。
- プレイヤーもしくはAIが勝利していないこと。
- 空いているマスが⓪になっていること。
現在の盤面の状態の評価値を取るためのメソッドを追加していきます。評価関数に該当します。
def evaluate(self) -> int:
"""
AI側のマーク配置の選択結果の性能評価のための評価関数としてのメソッド。
Parameters
----------
target_mark : Mark
判定側となるマーク。〇側での評価をしたい場合には Mark.O を、
×側で評価をしたい場合には Mark.X を指定する。
Returns
-------
evaluation_value : int
評価結果の値。勝利している場合には1、敗北している場合には-1、
勝敗がついていない場合には0が設定される。
"""
if self.is_ai_win:
return 1
if self.is_player_win:
return -1
return 0
ミニマックス法の計算の説明で前述したように、AI側が勝っていれば1、プレイヤー側が勝っていれば（AI側が負けていれば）-1、それ以外（引き分けもしくは勝敗が付いていない段階）では0としています。
これは対象とするゲームによって様々な形に都度設定します。例えば四目並べで2つ揃えば10、3つ揃えば50、4つ揃えば200・・・みたいな評価の値を設定して、なるべく揃っている数を増やす形にするようなケースも出てきます。
最後に、プレイの過程を可視化するための文字列出力用のメソッドを追加しておきます。
def __str__(self) -> str:
"""
現在の各マスの内容の可視化用の文字列を返却する。
Returns
-------
info : str
現在の各マスの内容の可視化用の文字列。以下のような
フォーマットの文字列が設定される。
O| |X
-----
|O|X
-----
O|X|
"""
info: str = ''
for i in range(9):
if i % 3 == 0 and i != 0:
info += '\n-----\n'
if not info.endswith('\n') and i != 0:
info += '|'
info += str(self.marks[i])
return info
これでTicTacToeクラスをprint関数などに通すと、以下のように出力されるようになります。
O|X|O
-----
O|X|
-----
X| |
ミニマックス法のアルゴリズムの実装
ミニマックス法での探索が終了しているかのは判定用の関数の追加
計算方法の箇所で説明したように、ミニマックス法ではゲーム木による有向グラフで計算を行います。
このグラフの各ノードで、末端まで達したかどうかの判定を行うための関数を追加します。
ゲーム木の例で前述したものを利用すると、以下の画像のように「勝敗が付いたかどうか」もしくは「最後の空いているマスにマークが配置されたか」の部分が該当します。
def is_search_ended(
current_tic_tac_toe: TicTacToe, remaining_depth: int) -> bool:
"""
Minimaxによる探索が終了している状態かどうかの真偽値を取得する。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の盤面の状態を保持した〇×ゲームのインスタンス。
remaining_depth : int
残っている探索の深さ。最後の探索範囲に達している場合には0を指定する。
Returns
-------
result : bool
探索が終了している状態かどうかの真偽値。終了していればTrueが
設定される。盤面で勝敗が付いている（勝利もしくは引き分け）場合
もしくは指定され探索の木の深さにまで達している場合にTrueとなる。
"""
if current_tic_tac_toe.is_player_win:
return True
if current_tic_tac_toe.is_ai_win:
return True
if current_tic_tac_toe.is_draw:
return True
if remaining_depth == 0:
return True
return False
最大値（max）と最小値の計算の追加
ミニマックス法における選択肢の中で最大値を計算する処理を書いていきます。
途中で出てくる minimax 関数は次の節で書いていくのでまだここでは実装されていません。
def get_maximized_evaluation_value(
current_tic_tac_toe: TicTacToe, remaining_depth: int) -> int:
"""
Minimaxにおける、最大化された評価値の取得を行う。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
remaining_depth : int
残っている探索の深さ。最後の探索範囲に達している場合には0を指定する。
Returns
-------
maximized_evaluation_value : int
最大化された評価値。
"""
maximized_evaluation_value: int = -1
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
for empty_position in empty_positions:
new_tic_tac_toe = current_tic_tac_toe.set_new_mark_and_change_turn(
position=empty_position)
# 再帰的な次の階層への木の探索処理。次は最小化される形となるので、
# maximizing=Falseを設定する。また、残りの深さの指定は1つ分減算する。
evaluation_value: int = minimax(
current_tic_tac_toe=new_tic_tac_toe,
maximizing=False,
remaining_depth=remaining_depth - 1)
maximized_evaluation_value = max(
evaluation_value, maximized_evaluation_value)
return maximized_evaluation_value
def get_minimized_evaluation_value(
current_tic_tac_toe: TicTacToe, remaining_depth: int) -> int:
"""
Minimaxにおける、最小化された評価値の取得を行う。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
remaining_depth : int
残っている探索の深さ。最後の探索範囲に達している場合には0を指定する。
Returns
-------
minimized_evaluation_value : int
最小化された評価値。
"""
minimized_evaluation_value: int = 1
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
for empty_position in empty_positions:
new_tic_tac_toe = current_tic_tac_toe.set_new_mark_and_change_turn(
position=empty_position)
# 再帰的な次の階層への木の探索処理。次は最大化される形となるので、
# maximizing=Trueを設定する。また、残りの深さの指定は1つ分減算する。
evaluation_value: int = minimax(
current_tic_tac_toe=new_tic_tac_toe,
maximizing=True,
remaining_depth=remaining_depth - 1)
minimized_evaluation_value = min(
evaluation_value, minimized_evaluation_value)
return minimized_evaluation_value
これらの関数は minimax から呼ばれますが、この2つの関数内でも minimax を再帰的に呼び出しています。
これは、ゲーム木で各ノードでどんどん下にいかないと評価値が算出できない（勝敗が分からない）ためこのようになっています。
また、ミニマックス法が以下の画像の青と赤が交互に切り替わるように、最大値の算出と最小値の算出が順番に切り替わるアルゴリズムなので、 get_maximized_evaluation_value 関数で最大値を求めたら内部では次は最小値を求めるように minimax 関数を呼び出しています。逆に get_minimized_evaluation_value では内部では次は最大値を求めるように minimax 関数を読んでいます。
ミニマックス法のための関数の追加
いよいよミニマックス法の関数を追加していきます。ここまでの準備で必要なものは諸々書いてきているので、この節で追加になること自体は少なくシンプルです。
def minimax(
current_tic_tac_toe: TicTacToe, maximizing: bool,
remaining_depth: int) -> int:
"""
Minimaxのアルゴリズムを実行し、結果の評価値を取得する。
Notes
-----
- 呼び出し後、最大で指定された深さ分再帰的に実行される。
- AI側を前提としたコードになっている（マークは×側が利用される）。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
maximizing : bool
評価値を最大化するかどうかの真偽値。Falseの場合は逆に最小化
する処理が実行される。次のアクションがプレイヤー側であればFalse、
AI側であればTrueを指定する。
remaining_depth : int
探索の木の最大の深さ。多くする程計算に時間がかかるようになる。
最初に呼び出す際には〇×ゲームの場合には最大で8階層となるので、
8以内の値を指定する。再帰的に実行する際に、階層が深くなる度に
-1されていく形で値が設定される（0になった時点で探索が停止する）。
Returns
-------
evaluation_value : int
Minimax実行後の評価値。
"""
_is_search_ended: bool = is_search_ended(
current_tic_tac_toe=current_tic_tac_toe,
remaining_depth=remaining_depth)
if _is_search_ended:
# 探索が終了する条件（木の末端に達しているか勝敗が付いた場合）には
# 現在の盤面での評価値を返却する。
return current_tic_tac_toe.evaluate()
# 最大化する場合（AI側のターン想定の木の深さ）のケース。
if maximizing:
maximized_evaluation_value: int = get_maximized_evaluation_value(
current_tic_tac_toe=current_tic_tac_toe,
remaining_depth=remaining_depth,
)
return maximized_evaluation_value
# 最小化する場合（プレイヤー側のターン想定の木の深さ）のケース。
minimized_evaluation_value: int = get_minimized_evaluation_value(
current_tic_tac_toe=current_tic_tac_toe,
remaining_depth=remaining_depth,
)
return minimized_evaluation_value
まずはゲーム木の末端に達したかどうかを判定しています（is_search_ended部分）。
もし末端に達していれば、評価値を得られるのでevaluateメソッドで評価値を取得して対象のグラフの経路の計算を終えます。
もしまだ途中のノード（末端に達していない）場合には引数に指定された値に応じて最大値を取得して伝搬させていくのか、最小値を取得して伝搬させていくのか分岐させます。この最大値・最小値は前述の通りゲーム木で下の階層に行くたびに交互に切り替わります。
もっとも評価値の高い選択肢を求めるための関数の追加
ミニマックス法の関数は追加できましたが、追加でAI側で「どの選択肢を取るべきか」といった、各選択肢ごとの評価値を取ってどれがベストな選択なのかを算出する処理が必要になるため追加していきます。
以下の画像のように、ゲーム木の一番上の部分が該当します。画像の例で言えば、4つの選択肢それぞれにミニマックス法の関数を反映してみて、一番評価値の高い選択肢がどれなのかを計算します。
def find_best_position(
current_tic_tac_toe: TicTacToe,
max_depth: int) -> Tuple[Position, int]:
"""
空いているマスの中で、ベストな位置をMinimaxで算出する。
空いている各マスに対してMinimaxの実行がされ、評価値が最大の
マスの位置が返却される。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
max_depth : int
探索の木の最大の深さ。
Raises
------
ValueError
空いているマスが存在しない状態で実行された場合。
Returns
-------
best_position : Position
算出されたベストな位置。
best_evaluation_value : int
ベストな位置における評価値の最大値（-1, 0, 1のいずれかが
設定される）。
"""
best_evaluation_value: int = -1
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
if not empty_positions:
raise ValueError('空いているマスが存在しません。')
best_position: Position = empty_positions[0]
for empty_position in empty_positions:
current_loop_tic_tac_toe: TicTacToe = \
current_tic_tac_toe.set_new_mark_and_change_turn(
position=empty_position)
# 今回Minimaxで算出したいものがAI側（maximizing=True）なので、
# 探索自体は次の階層のプレイヤー側のところからとなるため、
# Minimaxでの最初のmaximizingの指定はFalseとなる。
evaluation_value: int = minimax(
current_tic_tac_toe=current_loop_tic_tac_toe,
maximizing=False,
remaining_depth=max_depth)
if evaluation_value <= best_evaluation_value:
continue
best_evaluation_value = evaluation_value
best_position: Position = empty_position
return best_position, best_evaluation_value
内容としては get_empty_positions 関数で取れる選択肢（画像の例だと2, 4, 7, 8のマス）を取得し、ループで回してそれぞれに対してミニマックス法の関数を実行し、得られた各評価値の中での最大値の位置などを返却しています。
プレイヤーの入力値を取得するための関数を追加
続いて、input関数を使ったプレイヤー側のターンのマーク設定位置取得処理を追加していきます。
def get_player_input_position(current_tic_tac_toe: TicTacToe) -> Position:
"""
プレイヤー側のマーク配置位置の入力を取得する。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
Returns
-------
players_selected_position : Position
プレイヤー側が選択したマーク配置位置。
"""
is_empty_position: bool = False
players_selected_position: Position = Position(index=0)
while not is_empty_position:
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
msg: str = (
'〇を配置したいマスのインデックスを選択してください'
'(選択可能なインデックス : %s):' % empty_positions
)
input_val: str = input(msg)
try:
input_index: int = int(input_val)
players_selected_position = Position(index=input_index)
except Exception:
continue
is_empty_position = current_tic_tac_toe.is_empty_position(
position=players_selected_position)
return players_selected_position
プレイヤーのターンにコンソールに以下のようなものが表示され、入力待ちの状態になります。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [1, 2, 5, 7, 8]):
whileループで、入力値が有効な値ではない場合（空いてないマスのインデックスや整数値ではない場合など）は再度入力待ちの状態になります。
ゲームプレイのための処理を追加
最後です。ゲームプレイの処理を書いていきます。
def _main():
"""
〇×ゲームの実行を行う。
"""
tic_tac_toe: TicTacToe = TicTacToe(turn=Mark.O)
while True:
# プレイヤー側のマーク配置の制御。
player_selected_position: Position = \
get_player_input_position(current_tic_tac_toe=tic_tac_toe)
print('-' * 20)
tic_tac_toe = tic_tac_toe.set_new_mark_and_change_turn(
position=player_selected_position)
if tic_tac_toe.is_player_win:
print('プレイヤー側が勝利しました。')
print(tic_tac_toe)
break
if tic_tac_toe.is_draw:
print('引き分けです。')
print(tic_tac_toe)
break
print(tic_tac_toe)
# AI側のマーク配置の制御。
print('AI側でマスを選択中です...')
ai_selected_position: Position
evaluation_value: int
ai_selected_position, evaluation_value = find_best_position(
current_tic_tac_toe=tic_tac_toe,
max_depth=8)
print(
f'AIは{ai_selected_position}のインデックスを選択しました'
f'（評価値 : {evaluation_value}）。')
tic_tac_toe = tic_tac_toe.set_new_mark_and_change_turn(
position=ai_selected_position)
if tic_tac_toe.is_ai_win:
print('AI側が勝利しました。')
print(tic_tac_toe)
break
if tic_tac_toe.is_draw:
print('引き分けです。')
print(tic_tac_toe)
break
print(tic_tac_toe)
if __name__ == '__main__':
_main()
やっていることは以下の通りです。
- ゲームが終了するまでwhileループで回し続ける。
- プレイヤー側でマークを配置したい位置の入力を求める。
- プレイヤー側の位置の選択結果に応じた〇マークの配置を行う。
- プレイヤー側の配置結果に応じて、プレイヤー側が勝利したか判定する。
- ゲームが引き分けになったかどうかを確認する。
- ゲームが終了していなかったら、AI側でミニマックス法で最適なマスの選択を行う。
- ミニマックス法で算出したマスに×マークの配置を行う。
- プレイヤー側と同様に、AI側が勝利したか、もしくは引き分けになったかを判定する。
- 都度、各フェーズで盤面をprint関数で出力する。
- もしゲームが終了していなければ、前述の流れをまた繰り返す。
なお、AI側は後攻としているので残りは8マスです。そのためmax_depth=8としており、ゲーム木で8階層の深さまで最大探索を行います（今回の〇×ゲームでは全てのパターンを計算しています）。
ミニマックス法で得られる評価値は-1, 0, 1のどれかです。後攻の方が不利なので、基本的に-1（負け）か0（引き分け）が多くなります。
実際に動かしてみる
実際にPythonスクリプトを実行して試してみましょう。
初手からAIに取っていじわるなことをしてみます。
覚えることは2つだけ！ 「○×ゲーム」の最も簡単な勝ち方を解説した動画が話題に
上記の記事によると、先攻は左上・右上・左下・右下に〇を配置すると、後攻側は真ん中を取らないと負けてしまうそうです。実際にその配置をしてみて後攻のAI側が真ん中を選択できるか試してみます。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [0, 1, 2, 3, 4, 5, 6, 7, 8]):0
O| |
-----
| |
-----
| |
AI側でマスを選択中です...
AIは4のインデックスを選択しました（評価値 : 0）。
O| |
-----
|X|
-----
| |
無事後攻のAIが真ん中を選択してきました。なお、最初の1回目は残っているマスが多い（ゲーム木が深い）ためAI側の計算で少し時間がかかります。2回目以降は段々さくっと終わるようになってきます。
次は1のインデックスを選択してみましょう。〇側がリーチとなるので後攻のAIは2のインデックスを選択しないと負けてしまいます。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [1, 2, 3, 5, 6, 7, 8]):1
O|O|
-----
|X|
-----
| |
AIは2のインデックスを選択しました（評価値 : 0）。
O|O|X
-----
|X|
-----
| |
×側が斜めでリーチになっているので、プレイヤー側は左下以外選択肢が無くなっています。そのため今度は左下の6のインデックスを選択してみます。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [3, 5, 6, 7, 8]):6
O|O|X
-----
|X|
-----
O| |
〇が左の列の縦方向でリーチになっているので、AI側は真ん中の行の左の列の3のインデックス以外選択肢が無くなります。
AI側でマスを選択中です...
AIは3のインデックスを選択しました（評価値 : 0）。
O|O|X
-----
X|X|
-----
O| |
無事想定通りの選択をAI側がやってくれています。
続いてプレイヤー側では真ん中の行で×がリーチになっているので、真ん中の行の右の5のインデックス以外選択肢がありませんので5を選択してみます。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [5, 7, 8]):5
O|O|X
-----
X|X|O
-----
O| |
AI側でマスを選択中です...
AIは7のインデックスを選択しました（評価値 : 0）。
O|O|X
-----
X|X|O
-----
O|X|
残りは8のインデックスのみです。引き分けとなりました。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [8]):8
引き分けです。
O|O|X
-----
X|X|O
-----
O|X|O
基本的に〇×ゲームでは先攻がミスしない限り、後攻は引き分けが一番良い結果となります。また、後攻もミスしなければ負けることはありません。無事引き分けになってくれたので、コードをミスしていてポンコツなAIにはなっていないようです。
実は，先攻も後攻も頑張れば必ず引き分けになることが知られています。どちらにも必勝法はありません。
マルバツゲームは引き分けになる
今度はわざとプレイヤーがミスするようなケースを試してみます。前述のミニマックスの計算の説明で例を上げたような盤面で進めます。具体的には、プレイヤー側が1, 3, 5のインデックスを選択していってみます。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [0, 1, 2, 3, 4, 5, 6, 7, 8]):1
|O|
-----
| |
-----
| |
AI側でマスを選択中です...
AIは0のインデックスを選択しました（評価値 : 0）。
X|O|
-----
| |
-----
| |
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [2, 3, 4, 5, 6, 7, 8]):3
X|O|
-----
O| |
-----
| |
AI側でマスを選択中です...
AIは4のインデックスを選択しました（評価値 : 0）。
X|O|
-----
O|X|
-----
| |
続いてプレイヤーが5を選択した時には、AI側が2もしくは6を選択すれば残りのゲーム木の内容的にAI側の勝ちが確定します（評価値が0から1になっていることが確認できます）。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [2, 5, 6, 7, 8]):5
X|O|
-----
O|X|O
-----
| |
AI側でマスを選択中です...
AIは2のインデックスを選択しました（評価値 : 1）。
X|O|X
-----
O|X|O
-----
| |
無事AI側が2のインデックスを選択し、評価値が1となりました（×のリーチが2つになったのでAI側の勝ちが確定）。
〇を配置したいマスのインデックスを選択してください(選択可能なインデックス : [6, 7, 8]):6
X|O|X
-----
O|X|O
-----
O| |
AI側でマスを選択中です...
AIは8のインデックスを選択しました（評価値 : 1）。
AI側が勝利しました。
X|O|X
-----
O|X|O
-----
O| |X
無事作れたようなので、本記事はこれで終わりです。お疲れさまでした！
コード全体
from __future__ import annotations
from typing import List, Tuple
from enum import Enum
from copy import deepcopy
class Mark(Enum):
"""
〇×ゲームの各マスの1つ分のマークの値を扱うクラス。
Attributes
----------
O : str
〇に該当するマーク。
X : str
×に該当するマーク。
E : str
マスにマークが設定されていない場合の値（empty）。
空のスペースが設定される。
"""
O = 'O'
X = 'X'
E = ' '
def get_opponent(self) -> Mark:
"""
相手側のセルの値を取得する。
Returns
-------
opponent : Piece
相手側のセルの値。〇であれば×が、×であれば〇が設定される。
空の値の場合はそのまま空の値が設定される。
"""
if self == Mark.O:
return Mark.X
if self == Mark.X:
return Mark.O
return Mark.E
def __str__(self) -> str:
"""
マークの文字を返却する。
Returns
-------
mark : str
定義されているいずれかのマークの文字。
"""
return self.value
class Position:
def __init__(self, index: int) -> None:
"""
マスのインデックスを扱うクラス。インデックスは1次元で0～8の範囲で
以下のような位置が該当する。
0 1 2
3 4 5
6 7 8
Parameters
----------
index : int
対象のインデックス（0～8）。
Raises
------
ValueError
範囲外のインデックスが指定された場合。
"""
index_range: List[int] = list(range(0, 9))
if index not in index_range:
raise ValueError('指定されたインデックスが範囲外の値です : %s' % index)
self.index = index
def __eq__(self, obj: object) -> bool:
"""
他のPositionクラスと同値かどうかの比較を行う。
Parameters
----------
obj : *
比較対象のオブジェクト。
Returns
-------
result : bool
比較結果。対象がPositionクラスで、且つインデックスの
値が同じ場合にはTrueが設定される。
"""
if not isinstance(obj, Position):
return False
if self.index == obj.index:
return True
return False
def __repr__(self) -> str:
"""
文字列変換した際の表示値を返却する。
Returns
-------
repr_str : str
インデックスの値の文字が設定される。
"""
return repr(self.index)
class TicTacToe:
def __init__(self, turn: Mark, marks: List[Mark]=None) -> None:
"""
〇×ゲーム（tic-tac-toe）を扱うクラス。
Parameters
----------
turn : Mark
現在のターンのマーク。Mark.OもしくはMark.Xが必要になる。
marks : list of Mark, default None
現在の各マスに設定されているマークのリスト。1次元のリストで、
以下のような割り振りで0～8のインデックスで設定する。
0 1 2
3 4 5
6 7 8
デフォルト値が指定された場合には全てのマスが空の状態が
設定される。
"""
if marks is None:
marks = [Mark.E] * 9
self._turn = turn
self.marks = marks
def set_new_mark_and_change_turn(
self, position: Position) -> TicTacToe:
"""
特定のマスの位置に〇もしくは×のマークを設定する。
Notes
-----
設定されるマークはこのクラスに設定されているターンの属性に依存する。
Parameters
----------
position : Position
マークを設定する位置。
Raises
------
ValueError
すでにマークが設定されているマスの位置が指定された場合。
Returns
-------
new_tic_tac_toe : TicTacToe
マークの設定とターンの切り替え後の〇×ゲームのインスタンス。
※各探索でループで元のインスタンスも利用するため、
ディープコピーされたインスタンスが設定される。
"""
current_mark: Mark = self.marks[position.index]
if current_mark != Mark.E:
raise ValueError(
'対象のマスに既にマークが設定されています : '
f'position: {position}, mark: {current_mark}'
)
new_marks: List[Mark] = deepcopy(self.marks)
new_marks[position.index] = self._turn
new_turn: Mark = self._turn.get_opponent()
new_tic_tac_toe: TicTacToe = TicTacToe(
turn=new_turn, marks=new_marks)
return new_tic_tac_toe
def get_empty_positions(self) -> List[Position]:
"""
空いている（マークの設定されていない）マスの位置のリストを
取得する。
Returns
-------
empty_positions : list of Position
空いている（マークの設定されていない）マスの位置のリスト。
"""
empty_positions: List[Position] = []
for index, mark in enumerate(self.marks):
if mark != Mark.E:
continue
empty_positions.append(Position(index=index))
return empty_positions
def is_empty_position(self, position: Position) -> bool:
"""
指定された位置が空のマスかどうかの真偽値を取得する。
Parameters
----------
position : Position
判定対象の位置。
Returns
-------
result : bool
もし空のマスの位置であればTrueが設定される。
"""
empty_positions: List[Position] = self.get_empty_positions()
for empty_position in empty_positions:
if position == empty_position:
return True
return False
_ConditionPositions = Tuple[Position, Position, Position]
_CONDITION_POSITIONS: List[_ConditionPositions] = [
(Position(0), Position(1), Position(2)),
(Position(3), Position(4), Position(5)),
(Position(6), Position(7), Position(8)),
(Position(0), Position(3), Position(6)),
(Position(1), Position(4), Position(7)),
(Position(2), Position(5), Position(8)),
(Position(0), Position(4), Position(8)),
(Position(2), Position(4), Position(6)),
]
@property
def is_player_win(self) -> bool:
"""
プレイヤー側が勝利したかどうか。
Returns
-------
result : bool
プレイヤー側が勝利しているかどうか。
"""
return self._is_target_mark_win(mark=Mark.O)
@property
def is_ai_win(self) -> bool:
"""
AI側が勝利したかどうか。
Returns
-------
result : bool
AI側が勝利しているかどうか。
"""
return self._is_target_mark_win(mark=Mark.X)
def _is_target_mark_win(self, mark: Mark) -> bool:
"""
指定されたマーク側が勝利しているかどうかの真偽値を取得する。
Parameters
----------
mark : Mark
判定対象のマーク。
Returns
-------
result : bool
勝利している場合にはTrueが設定される。
"""
for condition_positions in self._CONDITION_POSITIONS:
condition_satisfied: bool = \
self._is_condition_satisfied_positions(
condition_positions=condition_positions,
target_mark=mark)
if condition_satisfied:
return True
return False
def _is_condition_satisfied_positions(
self, condition_positions: _ConditionPositions,
target_mark: Mark) -> bool:
"""
条件を満たしている位置の組み合わせ（3つ同じマークが並んでいるか）が
存在するかどうかの真偽値を取得する。
Parameters
----------
condition_positions : _ConditionPositions
チェック対象の3つの位置の組み合わせを格納したタプル。
target_mark : Mark
対象のマーク。
Returns
-------
result : bool
条件を満たせばTrueが設定される。
"""
is_target_marks: List[bool] = []
for condition_position in condition_positions:
mark: Mark = self.marks[condition_position.index]
if mark == target_mark:
is_target_marks.append(True)
continue
is_target_marks.append(False)
return all(is_target_marks)
@property
def is_draw(self) -> bool:
"""
引き分けの状態かどうかの真偽値。
Returns
-------
result : bool
引き分けかどうかの真偽値。勝敗が付いていない状態で、
且つ空いているマスが無くなった状態でTrueとなる。
"""
empty_position_num: int = len(self.get_empty_positions())
if self.is_player_win:
return False
if self.is_ai_win:
return False
if empty_position_num != 0:
return False
return True
def evaluate(self) -> int:
"""
AI側のマーク配置の選択結果の性能評価のための評価関数としてのメソッド。
Parameters
----------
target_mark : Mark
判定側となるマーク。〇側での評価をしたい場合には Mark.O を、
×側で評価をしたい場合には Mark.X を指定する。
Returns
-------
evaluation_value : int
評価結果の値。勝利している場合には1、敗北している場合には-1、
勝敗がついていない場合には0が設定される。
"""
if self.is_ai_win:
return 1
if self.is_player_win:
return -1
return 0
def __str__(self) -> str:
"""
現在の各マスの内容の可視化用の文字列を返却する。
Returns
-------
info : str
現在の各マスの内容の可視化用の文字列。以下のような
フォーマットの文字列が設定される。
O| |X
-----
|O|X
-----
O|X|
"""
info: str = ''
for i in range(9):
if i % 3 == 0 and i != 0:
info += '\n-----\n'
if not info.endswith('\n') and i != 0:
info += '|'
info += str(self.marks[i])
return info
def is_search_ended(
current_tic_tac_toe: TicTacToe, remaining_depth: int) -> bool:
"""
Minimaxによる探索が終了している状態かどうかの真偽値を取得する。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の盤面の状態を保持した〇×ゲームのインスタンス。
remaining_depth : int
残っている探索の深さ。最後の探索範囲に達している場合には0を指定する。
Returns
-------
result : bool
探索が終了している状態かどうかの真偽値。終了していればTrueが
設定される。盤面で勝敗が付いている（勝利もしくは引き分け）場合
もしくは指定され探索の木の深さにまで達している場合にTrueとなる。
"""
if current_tic_tac_toe.is_player_win:
return True
if current_tic_tac_toe.is_ai_win:
return True
if current_tic_tac_toe.is_draw:
return True
if remaining_depth == 0:
return True
return False
def get_maximized_evaluation_value(
current_tic_tac_toe: TicTacToe, remaining_depth: int) -> int:
"""
Minimaxにおける、最大化された評価値の取得を行う。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
remaining_depth : int
残っている探索の深さ。最後の探索範囲に達している場合には0を指定する。
Returns
-------
maximized_evaluation_value : int
最大化された評価値。
"""
maximized_evaluation_value: int = -1
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
for empty_position in empty_positions:
new_tic_tac_toe = current_tic_tac_toe.set_new_mark_and_change_turn(
position=empty_position)
# 再帰的な次の階層への木の探索処理。次は最小化される形となるので、
# maximizing=Falseを設定する。また、残りの深さの指定は1つ分減算する。
evaluation_value: int = minimax(
current_tic_tac_toe=new_tic_tac_toe,
maximizing=False,
remaining_depth=remaining_depth - 1)
maximized_evaluation_value = max(
evaluation_value, maximized_evaluation_value)
return maximized_evaluation_value
def get_minimized_evaluation_value(
current_tic_tac_toe: TicTacToe, remaining_depth: int) -> int:
"""
Minimaxにおける、最小化された評価値の取得を行う。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
remaining_depth : int
残っている探索の深さ。最後の探索範囲に達している場合には0を指定する。
Returns
-------
minimized_evaluation_value : int
最小化された評価値。
"""
minimized_evaluation_value: int = 1
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
for empty_position in empty_positions:
new_tic_tac_toe = current_tic_tac_toe.set_new_mark_and_change_turn(
position=empty_position)
# 再帰的な次の階層への木の探索処理。次は最大化される形となるので、
# maximizing=Trueを設定する。また、残りの深さの指定は1つ分減算する。
evaluation_value: int = minimax(
current_tic_tac_toe=new_tic_tac_toe,
maximizing=True,
remaining_depth=remaining_depth - 1)
minimized_evaluation_value = min(
evaluation_value, minimized_evaluation_value)
return minimized_evaluation_value
def minimax(
current_tic_tac_toe: TicTacToe, maximizing: bool,
remaining_depth: int) -> int:
"""
Minimaxのアルゴリズムを実行し、結果の評価値を取得する。
Notes
-----
- 呼び出し後、最大で指定された深さ分再帰的に実行される。
- AI側を前提としたコードになっている（マークは×側が利用される）。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
maximizing : bool
評価値を最大化するかどうかの真偽値。Falseの場合は逆に最小化
する処理が実行される。次のアクションがプレイヤー側であればFalse、
AI側であればTrueを指定する。
remaining_depth : int
探索の木の最大の深さ。多くする程計算に時間がかかるようになる。
最初に呼び出す際には〇×ゲームの場合には最大で8階層となるので、
8以内の値を指定する。再帰的に実行する際に、階層が深くなる度に
-1されていく形で値が設定される（0になった時点で探索が停止する）。
Returns
-------
evaluation_value : int
Minimax実行後の評価値。
"""
_is_search_ended: bool = is_search_ended(
current_tic_tac_toe=current_tic_tac_toe,
remaining_depth=remaining_depth)
if _is_search_ended:
# 探索が終了する条件（木の末端に達しているか勝敗が付いた場合）には
# 現在の盤面での評価値を返却する。
return current_tic_tac_toe.evaluate()
# 最大化する場合（AI側のターン想定の木の深さ）のケース。
if maximizing:
maximized_evaluation_value: int = get_maximized_evaluation_value(
current_tic_tac_toe=current_tic_tac_toe,
remaining_depth=remaining_depth,
)
return maximized_evaluation_value
# 最小化する場合（プレイヤー側のターン想定の木の深さ）のケース。
minimized_evaluation_value: int = get_minimized_evaluation_value(
current_tic_tac_toe=current_tic_tac_toe,
remaining_depth=remaining_depth,
)
return minimized_evaluation_value
def find_best_position(
current_tic_tac_toe: TicTacToe,
max_depth: int) -> Tuple[Position, int]:
"""
空いているマスの中で、ベストな位置をMinimaxで算出する。
空いている各マスに対してMinimaxの実行がされ、評価値が最大の
マスの位置が返却される。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
max_depth : int
探索の木の最大の深さ。
Raises
------
ValueError
空いているマスが存在しない状態で実行された場合。
Returns
-------
best_position : Position
算出されたベストな位置。
best_evaluation_value : int
ベストな位置における評価値の最大値（-1, 0, 1のいずれかが
設定される）。
"""
best_evaluation_value: int = -1
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
if not empty_positions:
raise ValueError('空いているマスが存在しません。')
best_position: Position = empty_positions[0]
for empty_position in empty_positions:
current_loop_tic_tac_toe: TicTacToe = \
current_tic_tac_toe.set_new_mark_and_change_turn(
position=empty_position)
# 今回Minimaxで算出したいものがAI側（maximizing=True）なので、
# 探索自体は次の階層のプレイヤー側のところからとなるため、
# Minimaxでの最初のmaximizingの指定はFalseとなる。
evaluation_value: int = minimax(
current_tic_tac_toe=current_loop_tic_tac_toe,
maximizing=False,
remaining_depth=max_depth)
if evaluation_value <= best_evaluation_value:
continue
best_evaluation_value = evaluation_value
best_position: Position = empty_position
return best_position, best_evaluation_value
def get_player_input_position(current_tic_tac_toe: TicTacToe) -> Position:
"""
プレイヤー側のマーク配置位置の入力を取得する。
Parameters
----------
current_tic_tac_toe : TicTacToe
対象の現在の（盤面の状態の）〇×ゲームのインスタンス。
Returns
-------
players_selected_position : Position
プレイヤー側が選択したマーク配置位置。
"""
is_empty_position: bool = False
players_selected_position: Position = Position(index=0)
while not is_empty_position:
empty_positions: List[Position] = \
current_tic_tac_toe.get_empty_positions()
msg: str = (
'〇を配置したいマスのインデックスを選択してください'
'(選択可能なインデックス : %s):' % empty_positions
)
input_val: str = input(msg)
try:
input_index: int = int(input_val)
players_selected_position = Position(index=input_index)
except Exception:
continue
is_empty_position = current_tic_tac_toe.is_empty_position(
position=players_selected_position)
return players_selected_position
def _main():
"""
〇×ゲームの実行を行う。
"""
tic_tac_toe: TicTacToe = TicTacToe(turn=Mark.O)
while True:
# プレイヤー側のマーク配置の制御。
player_selected_position: Position = \
get_player_input_position(current_tic_tac_toe=tic_tac_toe)
print('-' * 20)
tic_tac_toe = tic_tac_toe.set_new_mark_and_change_turn(
position=player_selected_position)
if tic_tac_toe.is_player_win:
print('プレイヤー側が勝利しました。')
print(tic_tac_toe)
break
if tic_tac_toe.is_draw:
print('引き分けです。')
print(tic_tac_toe)
break
print(tic_tac_toe)
# AI側のマーク配置の制御。
print('AI側でマスを選択中です...')
ai_selected_position: Position
evaluation_value: int
ai_selected_position, evaluation_value = find_best_position(
current_tic_tac_toe=tic_tac_toe,
max_depth=8)
print(
f'AIは{ai_selected_position}のインデックスを選択しました'
f'（評価値 : {evaluation_value}）。')
tic_tac_toe = tic_tac_toe.set_new_mark_and_change_turn(
position=ai_selected_position)
if tic_tac_toe.is_ai_win:
print('AI側が勝利しました。')
print(tic_tac_toe)
break
if tic_tac_toe.is_draw:
print('引き分けです。')
print(tic_tac_toe)
break
print(tic_tac_toe)
if __name__ == '__main__':
_main()