はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

Go言語入門＋アルゴリズム脳の強化のためにGolangとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

6問目（問題20)

20. Valid Parentheses

• 問題内容(日本語訳)

文字列を考えるsだけで文字を含む'('、')'、'{'、'}'、'['と']'、入力文字列が有効であるかどうかを決定。

入力文字列は、次の場合に有効です。

1. 開いたブラケットは、同じタイプのブラケットで閉じる必要があります。
2. 開いたブラケットは正しい順序で閉じる必要があります。

Example 1:

  Input: s = "()"
  Output: true

Example 2:

  Input: s = "()[]{}"
  Output: true

Example 3:

  Input: s = "(]"
  Output: false

Example 4:

  Input: s = "([)]"
  Output: false

Example 5:

  Input: s = "{[]}"
  Output: true

考え方

1. stack配列と辞書(map)を用意する。
2. mapには対応する記号を入力
3. 文字列を一文字ずつ見ていき、括弧の始まりならstackに追加し、閉じ括弧ならstackの直近のものを取り出して合っているかどうか確認。

説明

1. stackとdict(map)を定義する。
2. dict = {"]":"[", "}":"{", ")":"("}
3. for文で文字を一文字ずつみていきます。

• 解答コード

class Solution:
    def isValid(self, s):
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return stack == []

​ if char in dict.values():　で括弧始まりかどうか

​ elif char in dict.keys(): 　で括弧終わりかどうか

​ popで最新のstackの文字を取得

​ appendでstackに代入です。

• Goでも書いてみます！

  func isValid(s string) bool {
    stack := make([]rune, 0)
    m := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    for _, c := range s {
        switch c {
        case '(', '{', '[':
            stack = append(stack, c)
        case ')', '}', ']':
            if len(stack) == 0 || stack[len(stack)-1] != m[c] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
  }

こちらのコードは少し難しいですが、Goで文字列を一文字ずつ見るためにこのコードになりました。

​ for _, c := range s のループ処理では文字列stringsを一文字ずつ読み取ります。その時cはrune型になるのでmapやスタックもrune型で定義しました。

せっかくGolang書いてるからswitich文で処理を書きました。

• 自分メモ(Go)

文字列を一文字ずつ見るとrune

スライスにappend(固定長でないのでok)

AtCoder Beginner Contest 184 参戦記

ABC でC問題解けなかったの初めて…….

ABC184A - Determinant

1分で突破. 書くだけ.

a, b = map(int, input().split())
c, d = map(int, input().split())

print(a * d - b * c)

ABC184B - Quizzes

3分で突破. 書くだけ.

N, X = map(int, input().split())
S = input()

result = X
for c in S:
    if c == 'o':
        result += 1
    elif c == 'x':
        if result != 0:
            result -= 1
print(result)

ABC184C - Super Ryuma

突破できず. 頭真っ白になりました.

ABC184D - increment of coins

突破できず. 入出力例でも TLE したり、NaN になったりと上手く行かず.

ABC184E - Third Avenue

CとDを諦めてから始めたので何分かかったのか不明. 56分未満なのは確か. 見るからに難しそうなところが何もなく、何か罠があるのかと思いながら実装したけど、何も罠はなかった(笑). ワープだけは繰り返しトライするとヤバそうだったので、一回しかトライしないようにしたけど、これは見え見えすぎて罠ではないな(笑).

from collections import deque

INF = 10 ** 9

H, W = map(int, input().split())
a = [input() for _ in range(H)]

d = {}
for h in range(H):
    for w in range(W):
        c = a[h][w]
        if c in 'SG':
            d[c] = (h, w)
        elif c in '.#':
            continue
        else:
            if c in d:
                d[c].append((h, w))
            else:
                d[c] = [(h, w)]

not_warped = {}
for c in 'abcdefghijklmnopqrstuvwxyz':
    not_warped[c] = True


def move(h, w, p):
    c = a[h][w]
    if c == '#':
        return
    if t[h][w] > p:
        t[h][w] = p
        q.append((h, w))


t = [[INF] * W for _ in range(H)]
h, w = d['S']
t[h][w] = 0
q = deque([(h, w)])
while q:
    h, w = q.popleft()
    c = a[h][w]
    p = t[h][w] + 1
    if 'a' <= c <= 'z' and not_warped[c]:
        for nh, nw in d[c]:
            if t[nh][nw] > p:
                t[nh][nw] = p
                q.append((nh, nw))
        not_warped[c] = False
    if h != 0:
        move(h - 1, w, p)
    if h != H - 1:
        move(h + 1, w, p)
    if w != 0:
        move(h, w - 1, p)
    if w != W - 1:
        move(h, w + 1, p)

h, w = d['G']
if t[h][w] == INF:
    print(-1)
else:
    print(t[h][w])

import datetime
import pathlib
import re
from urllib.parse import urljoin

import pandas as pd
import pdfplumber
import requests
from bs4 import BeautifulSoup


def fetch_file(url, dir="."):

    r = requests.get(url)
    r.raise_for_status()

    p = pathlib.Path(dir, pathlib.PurePath(url).name)
    p.parent.mkdir(parents=True, exist_ok=True)

    with p.open(mode="wb") as fw:
        fw.write(r.content)
    return p


def days2date(s):

    y = dt_now.year

    days = re.findall("[0-9]{1,2}", s)

    if len(days) == 2:
        m, d = map(int, days)
        return pd.Timestamp(year=y, month=m, day=d)
    else:
        return pd.NaT


def wareki2date(s):

    m = re.search("(昭和|平成|令和)([ 0-9元]{1,2})年(\d{1,2})月(\d{1,2})日", s)

    if m:

        year, month, day = [1 if i == "元" else int(i.strip()) for i in m.group(2, 3, 4)]

        if m.group(1) == "昭和":
            year += 1925
        elif m.group(1) == "平成":
            year += 1988
        elif m.group(1) == "令和":
            year += 2018

        return datetime.date(year, month, day)

    else:
        return dt_now.date


url = "https://www.pref.aichi.jp/site/covid19-aichi/"

headers = {
    "User-Agent": "Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; rv:11.0) like Gecko"
}

JST = datetime.timezone(datetime.timedelta(hours=+9), "JST")
dt_now = datetime.datetime.now(JST)

r = requests.get(url, headers=headers)
r.raise_for_status()

soup = BeautifulSoup(r.content, "html.parser")

dfs = []
dt_text = ""

for tag in soup.find("span", text="▶ 愛知県内の発生事例").parent.find_all(
    "a", href=re.compile(".pdf$")
)[::-1]:

    link = urljoin(url, tag.get("href"))

    path_pdf = fetch_file(link)

    with pdfplumber.open(path_pdf) as pdf:

        for page in pdf.pages:

            if page.page_number == 1:

                dt_text = page.within_bbox((0, 80, page.width, 90)).extract_text()

            table = page.extract_table()

            df_tmp = pd.DataFrame(table[1:], columns=table[0])

            dfs.append(df_tmp)

df = pd.concat(dfs).set_index("No")

df["発表日"] = df["発表日"].apply(days2date)

df.dropna(subset=["発表日"], inplace=True)

# 年代と性別を分割
df_ages = df["年代・性別"].str.extract("(.+)(男性|女性)").rename(columns={0: "年代", 1: "性別"})

df = df.join(df_ages)


dt_update = wareki2date(dt_text)

path_csv = pathlib.Path(dt_update.strftime("%Y%m%d") + ".csv")

df.to_csv(path_csv, encoding="utf_8_sig")

1. はじめに

　画像の前処理の技術力向上のためにこちらを実践　画像処理100本ノック!!
とっかかりやすいようにColaboratoryでやります。
目標は２週間で完了できるようにやっていきます。丁寧に解説します。質問バシバシください！
001 - 010 は右のリンク　　画像処理100本ノック!!(001 - 010)丁寧にじっくりと
011 - 020 は右のリンク　　画像処理100本ノック!!(011 - 020)序盤戦

2. 前準備

ライブラリ等々を以下のように導入。

# ライブラリをインポート
from google.colab import drive
import numpy as np
import matplotlib.pyplot as plt
import cv2
from google.colab.patches import cv2_imshow

# 画像の読み込み
img = cv2.imread('画像のパス/imori.jpg')
img_noise = cv2.imread('画像のパス/imori_noise.jpg')
img_dark = cv2.imread('画像のパス/imori_dark.jpg')
img_gamma = cv2.imread('画像のパス/imori_gamma.jpg')
# グレースケール画像
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
gray_noise = cv2.cvtColor(img_noise, cv2.COLOR_BGR2GRAY)
gray_dark = cv2.cvtColor(img_dark, cv2.COLOR_BGR2GRAY)
# 画像保存用
OUT_DIR = '出力先のパス/OUTPUT/'

3.解説

Q.21. ヒストグラム正規化

ヒストグラム正規化を実装せよ。
ヒストグラムは偏りを持っていることが伺える。 例えば、0に近い画素が多ければ画像は全体的に暗く、255に近い画素が多ければ画像は明るくなる。 ヒストグラムが局所的に偏っていることをダイナミックレンジが狭いなどと表現する。 そのため画像を人の目に見やすくするために、ヒストグラムを正規化したり平坦化したりなどの処理が必要である。
このヒストグラム正規化は濃度階調変換(gray-scale transformation) と呼ばれ、[c,d]の画素値を持つ画像を[a,b]のレンジに変換する場合は次式で実現できる。 今回はimori_dark.jpgを[0, 255]のレンジにそれぞれ変換する。

A21

def hist_normalization(img, a=0, b=255):
    """
    ヒストグラム正規化
    params
    ----------------------------
    param1: numpy.ndarray形式のimage
    param2: ヒストグラムレンジの最小値
    param3: ヒストグラムレンジの最大値

    returns
    ----------------------------
    numpy.ndarray形式のimage
    """
    # ヒストグラム(rgb)の最大値・最小値の値
    c = img.min()     # 60
    d = img.max()    # 141

    # コピー
    out = img.copy()

    # 正規化
    out = (b - a) / (d - c) * (out - c) + a
    out[out < a] = a
    out[out > b] = b
    out = out.astype(np.uint8)
    return out

# 画像の高さ、幅、色を取得
H, W, C = img_dark.shape

# ヒストグラム正規化
out = hist_normalization(img_dark)

# ヒストグラムを表示する
plt.hist(out.ravel(), bins=255, rwidth=0.8, range=(0, 255))
plt.savefig("img21.png")
plt.show()

画像もかなり鮮明になった。

参考: ヒストグラム その2: ヒストグラム平坦化

Q.22. ヒストグラム操作

ヒストグラムの平均値をm0=128、標準偏差をs0=52になるように操作せよ。
これはヒストグラムのダイナミックレンジを変更するのではなく、ヒストグラムを平坦に変更する操作である。
平均値m、標準偏差s、のヒストグラムを平均値m0, 標準偏差s0に変更するには、次式によって変換する。

A22

def hist_mani(img, m0=128, s0=52):
    """
    ヒストグラムの平均値をm0=128、標準偏差をs0=52になるように操作

    params
    --------------------------------------
    param1: numpy.ndarray形式のimage
    param2: 平均値
    param3: 標準偏差

    returns
    --------------------------------------
    numpy.ndarray形式のimage
    """
    # 平均値
    m = np.mean(img)
    # 標準偏差
    s = np.std(img)

    # 画像のコピー
    out = img.copy()

    # 計算式通りに計算
    out = s0 / s * (out - m) + m0
    out[out < 0] = 0
    out[out > 255] = 255
    out = out.astype(np.uint8)

    return out

# ヒストグラムを操作
out = hist_mani(img_dark)

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans22_1.jpg', out)
# 画像を表示
cv2_imshow(out)
cv2.waitKey(0)
cv2.destroyAllWindows()

# ヒストグラムを表示する
plt.hist(out.ravel(), bins=255, rwidth=0.8, range=(0, 255))
plt.savefig("img22_2.png")
plt.show()

参考: ヒストグラム その2: ヒストグラム平坦化

Q.23. ヒストグラム平坦化

ヒストグラム平坦化を実装せよ。
ヒストグラム平坦化とはヒストグラムを平坦に変更する操作であり、上記の平均値や標準偏差などを必要とせず、ヒストグラム値を均衡にする操作である。
これは次式で定義される。 ただし、S ... 画素値の総数、Zmax ... 画素値の最大値、h(z) ... 濃度zの度数

A23

def hist_equal(img, z_max=255):
    """
    ヒストグラム平坦化

    params
    --------------------------------------
    param1: numpy.ndarray形式のimage
    param2:  画素値の最大値

    returns
    --------------------------------------
    numpy.ndarray形式のimage
    """

    # 画像の高さ、幅、色を取得
    H, W, C = img.shape
    # 画素値の総数(画像高さx画像幅x色数)
    S = H * W * C * 1.     # 49152.0
    # 画像のコピー
    out = img.copy()

    # 濃度の度数
    sum_h = 0.

    # 画像の濃度0~255までそれぞれの度数
    for i in range(256):
        # 濃度が一致する箇所
        ind = np.where(img==i)
        # 一致した濃度の度数
        sum_h += len(img[ind])
        # ヒストグラム値を均衡(計算式参照)
        z_prime = z_max / S * sum_h
        out[ind] = z_prime

    out = out.astype(np.uint8)

    return out

# ヒストグラムを操作
out = hist_equal(img)

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans23_1.jpg', out)
# 画像を表示
cv2_imshow(out)
cv2.waitKey(0)
cv2.destroyAllWindows()

# ヒストグラムを表示する
plt.hist(out.ravel(), bins=255, rwidth=0.8, range=(0, 255))
plt.savefig("img23_2.png")
plt.show()

参考: ヒストグラム その2: ヒストグラム平坦化

Q.24. ガンマ補正

imori_gamma.jpgに対してガンマ補正(c=1, g=2.2)を実行せよ。
ガンマ補正とは、カメラなどの媒体の経由によって画素値が非線形的に変換された場合の補正である。 ディスプレイなどで画像をそのまま表示すると画面が暗くなってしまうため、RGBの値を予め大きくすることで、ディスプレイの特性を排除した画像表示を行うことがガンマ補正の目的である。
非線形変換は次式で起こるとされる。 ただしxは[0,1]に正規化されている。 c ... 定数、g ... ガンマ特性(通常は2.2)

そこで、ガンマ補正は次式で行われる。

A24

def gamma_correction(img, c=1, g=2.2):
    """
    ガンマ補正・・・画像の明るさを調整する方法

    params
    --------------------------------------
    param1: numpy.ndarray形式のimage
    param2: 定数
    param3: ガンマ特性

    returns
    --------------------------------------
    numpy.ndarray形式のimage
    """

    # 画像のコピー
    out = img.copy().astype(np.float)
    # 255で割る(Iinに変換)
    out /= 255.
    # ガンマ補正の式
    out = (1/c * out) ** (1/g)

    # 255をかける
    out *= 255
    out = out.astype(np.uint8)

    return out

# ガンマ補正
out = gamma_correction(img_gamma)

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans24.jpg', out)
# 画像を表示
cv2_imshow(out)
cv2.waitKey(0)
cv2.destroyAllWindows()

参考: Pythonやってみる！

Q.25. 最近傍補間

最近傍補間により画像を1.5倍に拡大せよ。
最近傍補間(Nearest Neighbor)は画像の拡大時に最近傍にある画素をそのまま使う手法である。 シンプルで処理速度が速いが、画質の劣化は著しい。
次式で補間される。 I' ... 拡大後の画像、 I ... 拡大前の画像、a ... 拡大率、[ ] ... 四捨五入

A25

"""
最近傍補間
cv2.resize(src, dsize[, interpolation])
src     入力画像
dsize   変更後の画像サイズ
interpolation   補間法(最近傍補間ならcv2.INTER_NEAREST)
"""
# 最近傍補間
# 変更後の画像サイズ：　img.shape>>>(高さ、幅、色)
out = cv2.resize(
    img, (int(img.shape[1]*1.5), int(img.shape[0]*1.5)), interpolation=cv2.INTER_NEAREST)

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans25.jpg', out)
# 画像を表示
cv2_imshow(out)
cv2.waitKey(0)
cv2.destroyAllWindows()

参考: 【Python/OpenCV】画像の拡大・縮小（最近傍補間法、バイリニア補間法、バイキュービック補間法）

Q.26. Bi-linear補間

Bi-linear補間により画像を1.5倍に拡大せよ。
Bi-linear補間とは周辺の４画素に距離に応じた重みをつけることで補完する手法である。 計算量が多いだけ処理時間がかかるが、画質の劣化を抑えることができる。

A26

"""
バイリニア補間法（Bi-linear interpolation）は、周囲の4つの画素を用いた補間法
cv2.resize(src, dsize[, interpolation])
src     入力画像
dsize   変更後の画像サイズ
interpolation   補間法(バイリニア補間ならcv2.INTER_LINEAR)
"""
# バイリニア補間法
# 変更後の画像サイズ：　img.shape>>>(高さ、幅、色)
out = cv2.resize(
    img, (int(img.shape[1]*1.5), int(img.shape[0]*1.5)), interpolation=cv2.INTER_LINEAR)

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans26.jpg', out)
# 画像を表示
cv2_imshow(out)
cv2.waitKey(0)
cv2.destroyAllWindows()

参考: 【Python/OpenCV】画像の拡大・縮小（最近傍補間法、バイリニア補間法、バイキュービック補間法）

Q.27. Bi-cubic補間

Bi-cubic補間により画像を1.5倍に拡大せよ。
Bi-cubic補間とはBi-linear補間の拡張であり、周辺の16画素から補間を行う。

A27

"""
バイキュービック補間法では、周囲16画素の画素値を利用
cv2.resize(src, dsize[, interpolation])
src     入力画像
dsize   変更後の画像サイズ
interpolation   補間法(バイキュービック補間ならcv2.INTER_CUBIC)
"""
# バイキュービック補間
# 変更後の画像サイズ：　img.shape>>>(高さ、幅、色)
out = cv2.resize(
    img, (int(img.shape[1]*1.5), int(img.shape[0]*1.5)), interpolation=cv2.INTER_CUBIC)

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans27.jpg', out)
# 画像を表示
cv2_imshow(out)
cv2.waitKey(0)
cv2.destroyAllWindows()

参考: 【Python/OpenCV】画像の拡大・縮小（最近傍補間法、バイリニア補間法、バイキュービック補間法）

Q.28. アフィン変換(平行移動)

アフィン変換を利用して画像をx方向に+30、y方向に-30だけ平行移動させよ。
アフィン変換とは3x3の行列を用いて画像の変換を行う操作である。

A28

"""
アフィン変換
cv2.warpAffine(src, M, dsize[, dst[, flags[, borderMode[, borderValue]]]])
第一引数に元画像（NumPy配列ndarray）、
第二引数に2 x 3の変換行列（NumPy配列ndarray）、
第三引数に出力画像のサイズ（タプル）を指定する。
"""
# 画像の高さ、幅、色を取得
H, W, C = img.shape
# 平行移動[[1,0,横方向への移動量],[0,1,縦方向への移動量]]の2x3行列
M = np.float64([[1, 0, 30], [0,1,-30]])
# アフィン変換
out = cv2.warpAffine(img, M, (W, H))

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans28.jpg', out)
# 画像を表示
cv2_imshow(out)
cv2.waitKey(0)
cv2.destroyAllWindows()

参考: 【Python/OpenCV】アフィン変換で画像の回転

Q.29. アフィン変換(拡大縮小)

アフィン変換を用いて、(1)x方向に1.3倍、y方向に0.8倍にリサイズせよ。
また、(2) (1)の条件に加えて、x方向に+30、y方向に-30だけ平行移動を同時に実現せよ。

A29

def affine_expand(img, ratio_x, ratio_y):
    """
    アフィン変換で拡大

    params
    -------------------------------
    param1: numpy.ndarray形式のimage
    param2: x方向の比率
    param3: y方向の比率

    returns
    -------------------------------
    numpy.ndarray形式のimage
    """
    # 画像の高さ、幅
    H, W = img.shape[:2]
    # xy座標をnp.float32型
    src = np.array([[0.0, 0.0],[0.0, 1.0],[1.0, 0.0]], np.float32)
    # x, yそれぞれ比率をかける
    dest = src.copy()
    dest[:,0] *= ratio_x
    dest[:,1] *= ratio_y
    """
    アフィン変換の変換行列を生成: cv2.getAffineTransform(src, dest)
    src: 変換前の3点の座標
    dest: 変換後の3点の座標をNumPy配列ndarrayで指定
    """
    affine = cv2.getAffineTransform(src, dest)
    """
    アフィン変換
    cv2.warpAffine(src, M, dsize[, dst[, flags[, borderMode[, borderValue]]]])
    第一引数に元画像（NumPy配列ndarray）、
    第二引数に2 x 3の変換行列（NumPy配列ndarray）、
    第三引数に出力画像のサイズ（タプル）を指定する。
    INTER_LANCZOS4 – 8×8 の近傍領域を利用するLanczos法での補間
    """
    return cv2.warpAffine(img, affine, (int(W*ratio_x), int(H*ratio_y)), cv2.INTER_LANCZOS4) # 補間法も指定できる


# アフィン変換で拡大
out = affine_expand(img, 1.3, 0.8)
# 平行移動[[1,0,横方向への移動量],[0,1,縦方向への移動量]]の2x3行列
H, W = out.shape[:2]
M = np.float64([[1, 0, 30], [0,1,-30]])
out2 = cv2.warpAffine(out, M, (W, H))

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans29_1.jpg', out)
cv2.imwrite(OUT_DIR + 'ans29_2.jpg', out2)

# 画像を表示
cv2_imshow(out)
cv2_imshow(out2)
cv2.waitKey(0)
cv2.destroyAllWindows()

参考: 完全に理解するアフィン変換

Q.30. アフィン変換(回転)

(1)アフィン変換を用いて、反時計方向に30度回転させよ。
(2) アフィン変換を用いて、反時計方向に30度回転した画像で中心座標を固定することで、なるべく黒い領域がなくなるように画像を作成せよ。 （ただし、単純なアフィン変換を行うと画像が切れてしまうので、工夫を要する。）

A30

def affin_rotate(img, x, y, theta, scale):
    """
    アフィン変換で回転

    params
    -------------------------------
    param1: numpy.ndarray形式のimage
    param2: 回転軸のx座標
    param3: 回転軸のy座標
    param4: 回転角
    param5: 回転角度・拡大率

    returns
    -------------------------------
    numpy.ndarray形式のimage
    """

    """
    2次元回転を表すアフィン変換
    cv2.getRotationMatrix2D(center, angle, scale)
    center: 回転の原点となる座標
    angle: 回転の角度（ラジアンではなく度degree）
    scale: 拡大・縮小倍率。
    """
    # 回転変換行列の算出
    R = cv2.getRotationMatrix2D((x, y), theta, scale)
    """
    アフィン変換
    cv2.warpAffine(src, M, dsize[, dst[, flags[, borderMode[, borderValue]]]])
    第一引数に元画像（NumPy配列ndarray）、
    第二引数に2 x 3の変換行列（NumPy配列ndarray）、
    第三引数に出力画像のサイズ（タプル）を指定する。
    cv2.INTER_CUBIC: バイキュービック
    """
    # アフィン変換 
    dst = cv2.warpAffine(img, R, gray.shape,
                        flags=cv2.INTER_CUBIC)

    return dst

# 画像の中心座標
oy, ox = int(img.shape[0]/2), int(img.shape[1]/2)

# 反時計方向に30度回転
out1 = affin_rotate(img, 0, 0, 30, 1)
# 反時計方向に30度回転した画像で中心座標を固定
out2 = affin_rotate(img, ox, oy, 30, 1)

# 結果を保存する
cv2.imwrite(OUT_DIR + 'ans30_1.jpg', out1)
cv2.imwrite(OUT_DIR + 'ans31_2.jpg', out2)

# 画像を表示
cv2_imshow(out1)
cv2_imshow(out2)
cv2.waitKey(0)
cv2.destroyAllWindows()

参考: Python, OpenCVで幾何変換（アフィン変換・射影変換など）
参考: 【Python/OpenCV】アフィン変換で画像の回転

感想

レベルが徐々に上がっているように感じる。可能な限りOpenCVでの実装を心がける。

・行単位のコメントは、#に続けて記述

# Hello, world!を表示
print "Hello, world!"

・複数行にまたがるコメントアウト
'''(シングルクォーテーション3つ）あるいは"""（ダブルクォーテーション3つ）で囲まれた部分が
コメントアウトされる

'''
この行はコメントです。
この行もコメントです。
'''

はじめに

ここではWebスクレイピングで『Web上の画像を一括で保存する方法』について紹介します。

注意
著作権で保護されている場合や著作権的にはOKだが利用規約でスクレイピングを禁止している場合、損害賠償請求などの可能性があるのでしっかり著作権法や利用規約を理解した上でWebスクレイピングを行いましょう。

目次

1. Webスクレイピングを行う方法
2. 実際に画像を保存してみる
3. 抽出の流れ
4. まとめ
5. おまけ
6. 参考

1. Webスクレイピングを行う方法

Webスクレイピングを行うためには「Ruby」や「PHP」、「Javascript」など様々な言語で可能ですが、今回はPythonの『Beautiful Soup』を用いた方法を紹介します。

2. 実際に画像を保存してみる

① pipでbeautifulsoup4をインストールする

pip install beautifulsoup4

② Webスクレイピングを行うサイトを決める
※今回は『いらすとや』の画像をダウンロードしていきます。
https://www.irasutoya.com/search/label/%E3%83%93%E3%82%B8%E3%83%8D%E3%82%B9

③ 一覧ページから各画像リンクページURLを取得する

url = "https://www.irasutoya.com/search/label/%E3%83%93%E3%82%B8%E3%83%8D%E3%82%B9"
# 画像ページのURLを格納するリストを用意
link_list = []
response = urllib.request.urlopen(url)
soup = BeautifulSoup(response, "html.parser")
# 画像リンクのタグをすべて取得
image_list = soup.select('div.boxmeta.clearfix > h2 > a')
# 画像リンクを1つずつ取り出す
for image_link in image_list:
    link_url = image_link.attrs['href']
    link_list.append(link_url)

④ 画像ファイルのタグをすべて取得する

for page_url in link_list:
    page_html = urllib.request.urlopen(page_url)
    page_soup = BeautifulSoup(page_html, "html.parser")
    # 画像ファイルのタグをすべて取得
    img_list = page_soup.select('div.separator > a > img')

⑤ imgタグを1つずつ取り出し、画像ファイルのURLを取得する

for img in img_list:
    # 画像ファイルのURLを取得
    img_url = (img.attrs['src'])
    file_name = re.search(".*/(.*png|.*jpg)$", img_url)
    save_path = output_folder.joinpath(file_name.group(1))

⑥ 画像ファイルのURLからデータをダウンロード

try:
   # 画像ファイルのURLからデータを取得
   image = requests.get(img_url)
   # 保存先のファイルパスにデータを保存
   open(save_path, 'wb').write(image.content)
   # 保存したファイル名を表示
   print(save_path)
except ValueError:
   print("ValueError!")

手順としては以上です。

↓　↓　実行結果　↓　↓

3. 抽出の流れ

手順③～⑤が少しイメージしづらいと思ったので、大まかな抽出の流れを作成してみました。

また、今回のソースはGithubにも掲載してありますので、下記からご参照ください。
https://github.com/miyazakikna/SaveLocalImageWebScraping.git

4. まとめ

ここではPythonのBeatiful Soupを使って画像を一括で保存する方法について解説しました。
今回はいらすとやの画像を取得しましたが、他のサイトでも基本的に同じ要領で画像がダウンロードできるかと思いますので、是非活用してみてください。

5. おまけ

画像ダウンロード後、ファイル名を一括で変更する方法はこちら↓↓
【仕事効率化】Pythonでファイル名を一括変更する方法

6. 参考

・Pythonで画像スクレイピングをしよう
・webスクレイピングで画像収集

概要

小プロセスを含め、killをするためのツールです。python用です。
（pythonのプロセスで縛りを掛けています。）
検証はlinuxのみしてあります。

使い方は、
そのまま実行すると、小プロセスを持つ親プロセスの一覧が表示されるので、
（例としてproc_01.py proc_02.pyの小プロセスを持つプログラムが実行中とします。）

$ python terminate_children_process.py

python 関連の小プロセスを持つprocess一覧
コマンドラインにPIDを指定すると、小プロセスを含めてterminate します。
{'pid': 26727, 'cmdline': ['python', 'proc_01.py']}
{'pid': 26747, 'cmdline': ['python', 'proc_02.py']}

終了させたいpidを指定し再び実行します。

$ python terminate_children_process.py 26747

terminate 子プロセス　26849
terminate 子プロセス　26850
terminate 子プロセス　26851
terminate  親プロセス　26747

ソース(terminate_children_process.py)

#terminate_children_process.py
import sys
import psutil

if len(sys.argv)==1:
    #python 関連の小プロセスを持つprocessの表示
    print("python 関連の小プロセスを持つprocess一覧")
    print("コマンドラインにPIDを指定すると、小プロセスを含めてterminate します。")

    PROCNAME = "python"
    for proc in psutil.process_iter([ "pid"  ,  'cmdline'  ]):
        if proc.name()[:len(PROCNAME)] == PROCNAME:
            p = psutil.Process(proc.pid)
            if len(p.children()) >0:
                print(proc.info)

else:
    #指定したPIDとその小プロセスを含めてterminate

    target_pid=int(sys.argv[1])
    p = psutil.Process(target_pid)

    #子のterminate
    pid_list=[pc.pid for pc in p.children(recursive=True)] 
    for pid in pid_list:
        psutil.Process(pid).terminate ()
        print("terminate 子プロセス　{}" .format(pid))

    #親のterminate
    p.terminate ()
    print("terminate  親プロセス　{}" .format(target_pid))

参考

psutil documentation

はじめに

Python + Selenium + Chromeでよく使うオプションをメモ

環境情報

• python： 3.9.0
• chrome： 86.0.4240.198
• selenium： 3.141.0

Python + Selenium + Chromeでよく使うオプション

from selenium import webdriver

options = webdriver.chrome.options.Options()
# 画面を非表示
options.add_argument('--headless')
# 必須らしい
options.add_argument('--disable-gpu')
# サイズ指定
options.add_argument('--window-size=1920,1080')
# コンテナの権限不足回避
options.add_argument('--no-sandbox')
# 画像を読み込まない
options.add_argument('--blink-settings=imagesEnabled=false')
# 通知を無効
options.add_argument('--disable-desktop-notifications')
# 拡張機能を無効
options.add_argument('--disable-extensions')
# SSLを無視
options.add_argument('--ignore-certificate-errors')
# Webセキュリティを無効
options.add_argument('--disable-web-security')

driver = webdriver.Chrome(chrome_options=options)

概要

Pythonでのアスタリスク(*)の使われ方が、よくわからなかったので調べた。
リファレンスでの説明を確認した。

この記事のポイントは、リファレンスで、どこで説明されているかを示したこと。あと、関数の引数でのアスタリスクは有名だが、引数だけで、極端な使い方の特殊がされているわけでない、ことを示したい（ したい）と感じたため。

引用は、すべて、
https://docs.python.org/ja/3.7/reference/

結果

使い方１（乗算演算）

使い方２（べき乗演算）

使い方３（引数リストのアンパック）

使い方４（辞書のアンパック）

例↓。これは、あまり使う可能性がない。

>>>
>>> ff = {'a':1,'b':2}
>>> gg = {**ff,'c':3}
>>> gg
{'a': 1, 'b': 2, 'c': 3}
>>>

使い方５（イテラブルのアンパック）

例↓。これは、使うことがあるかも。

>>>
>>> (hh,*ii)=1,2,3,4,5,6
>>> ii
[2, 3, 4, 5, 6]
>>>

まとめ

特にありません。
コメントなどあれば、お願いします。

はじめに

selenium + python + chrome でChromeDriverのバージョンエラーに悩まされたので、対処方法をメモ

環境情報

• python： 3.9.0
• chrome： 86.0.4240.198
• selenium： 3.141.0

Chromeバージョンに合ったChromeDriverを自動インストールする方法

下記のように設定すると、Chromeバージョンに合ったChromeDriverが自動インストールされます！

import requests
from selenium import webdriver
from webdriver_manager.utils import chrome_version
from webdriver_manager.chrome import ChromeDriverManager

version = chrome_version()
url = 'http://chromedriver.storage.googleapis.com/LATEST_RELEASE_' + version
response = requests.get(url)

driver = webdriver.Chrome(executable_path=ChromeDriverManager(response.text).install())

はじめに

selenium + python + chrome でファイルダウンロードを行う方法をメモ

環境情報

• python： 3.9.0
• chrome： 86.0.4240.198
• selenium： 3.141.0

ファイルダウンロード設定

下記のように設定すると、【ダウンロード先のパス】にダウンロードされます！

from selenium import webdriver
from selenium.webdriver.chrome.options import Options

options = Options()
driver = webdriver.Chrome(chrome_options=options)

driver.command_executor._commands["send_command"] = (
    "POST",
    '/session/$sessionId/chromium/send_command'
)
params = {
    'cmd': 'Page.setDownloadBehavior',
    'params': {
        'behavior': 'allow',
        'downloadPath': 【ダウンロード先のパス】
    }
}
driver.execute("send_command", params=params)

この記事の内容

MeCabやBeautiful Soupのインポートから、WEBスクレイピングし口コミ、レビューを抽出。それをwordcloudにし、どんな事が書かれているのか可視化してやろう！という内容です。

できるようになること

例えばトリップアドバイザーの「口コミ」これをワードクラウド（頻出単語≒多くの人がわざわざ口コミで言及しているトピック、の可視化）ができます。
東京タワーとスカイツリー、東京タワーと通天閣の可視化などして比較すると差異が見えて面白いかも。。。という発想です。

赤枠の「口コミ」から、こんなものを作ります。

参考にさせていただいたサイト、記事

初めてWEBスクレイピングに挑戦し、wordcloudまで作ったのですが、その際に参考にさせていただいたサイトを先に紹介させていただきます。
レビューサイトをスクレイピングして単語数を調査する
【初心者向け】PythonでWebスクレイピングをやってみる
PythonでMeCabを利用する方法を現役エンジニアが解説【初心者向け】
wordcloud を Windows で Anaconda / Jupyter で使う（Tips）

ライブラリのインストール

まずは必要なライブラリのインストールから行います。（すでに入ってる方は飛ばしてください。）
ちなみに私の環境はWindows 10、Anaconda(jupyter)で行ってます。

Beautiful Soup、request、wordcloud

Ancaonda Promptを起動し、Beautiful Soupとrequestをインストールします。

conda install beautifulsoup4
conda install request
conda install -c conda-forge wordcloud

MeCab

公式サイトから「Binary package for MS-Windows」をダウンロードし、インストールします。これなら辞書が最初から入っています。慣れてきたら他の辞書に変えても良いでしょう。
インストール途中で文字コードを聞かれますが、「UTF-8」に！他はそのままでOK。
インストールが終わったら、環境変数の設定を行います。
・（おそらくタスクバー左下に合う検索窓で）「システムの詳細」と検索
・「環境変数」を選択
・システム環境変数の「Path」を選択
・編集をクリックし、新規を選択
・「C:\Program Files (x86)\MeCab\bin」と入力
・OKを選択し、画面を閉じる
PythonでMeCabを利用する方法を現役エンジニアが解説【初心者向け】 さんに手順が書いてありますので、そちらもぜひご覧ください。

ここから本番

ここまでで下準備は終わったので、ここからコードを書いていきます。
まずはインポート

import requests
from bs4 import BeautifulSoup
import re
import pandas as pd

ここまでできたら、スクレイピングしたいサイトに行きます。
今回の例ではTrip advisorの東京タワーのページ。
以下の2つを確認します。
・URL
・HTMLのどこにスクレイピングしたいもの（今回は口コミ）があるか。

まずURLはそのまま見ればわかるので、説明は省略します。
後者は「F12」を押しデベロッパーツールを起動します。

上記のようなウィンドウが表示されます。
ここから口コミがどこに、どのように格納されているかを確認します。

確認方法は簡単で、「Shift + Ctrl + C」をクリックした後、記事の口コミ部分をCLICKします。
すると、先のウィンドウで該当部分が選択されます。

口コミはqのclass「IRsGHomP」に格納されていることがわかります。

あとはコード上でこのURL、場所を指定しスクレイピングを実行します。

# スクレイピングした口コミをdf_listに格納していく
df_list = [] 
# 20ページ分スクレイピング行う。
pages = range(0, 100, 5)

for page in pages:
#　1ページ目と2ページ目以降で若干URLが異なるのでIFで分岐
    if page == 0:
        urlName = 'https://www.tripadvisor.jp/Attraction_Review-g14129730-d320047-Reviews-Tokyo_Tower-Shibakoen_Minato_Tokyo_Tokyo_Prefecture_Kanto.html'
    else:
        urlName = 'https://www.tripadvisor.jp/Attraction_Review-g14129730-d320047-Reviews-or' + str(page) + '-Tokyo_Tower-Shibakoen_Minato_Tokyo_Tokyo_Prefecture_Kanto.html'

    url = requests.get(urlName)
    soup = BeautifulSoup(url.content, "html.parser")

# HTMLの中からタグqのClass 'IRsGHoPm'を指定
    review = soup.find_all('q', class_ = 'IRsGHoPm')

# 抜き出した口コミを順番に格納
    for i in range(len(review)):
        _df = pd.DataFrame({'Number':i+1,
                            'review':[review[i].text]})

        df_list.append(_df)

ここまで行うと、df_listには以下が入っているはずです。

df_review = pd.concat(df_list).reset_index(drop=True)
print(df_review.shape)
df_review

wordcloudの作成

まずはMeCabやWordCloudのインポート

import MeCab
import matplotlib.pyplot as plt
from wordcloud import WordCloud

レビューサイトをスクレイピングして単語数を調査するを参考にさせて頂き、コードを記入。

# MeCab準備
tagger = MeCab.Tagger()
tagger.parse('')

# 全テキストデータを結合
all_text= ""
for s in df_review['review']:
    all_text += s

node = tagger.parseToNode(all_text)

# 名詞を抽出しリストに
word_list = []
while node:
    word_type = node.feature.split(',')[0]
    if word_type == '名詞':
        word_list.append(node.surface)
    node = node.next

# リストを文字列に変換
word_chain = ' '.join(word_list)

あとはwordcloudを実行すればokです。

# ストップワード（除外するワード）の作成
stopwords = ['']

# ワードクラウド作成
W = WordCloud(width=500, height=300, background_color='lightblue', colormap='inferno', font_path='C:\Windows\Fonts\yumin.ttf', stopwords = set(stopwords)).generate(word_chain)

plt.figure(figsize = (15, 12))
plt.imshow(W)
plt.axis('off')
plt.show()

すると下記のように作成されます。

ただ、「の」や「こと」「ため」とうは不要なので除こうと思います。
そこで、上記のストップワードの出番です。

# ストップワード（除外するワード）の作成
stopwords = ['の', 'こと', 'ため']

# ワードクラウド作成
W = WordCloud(width=500, height=300, background_color='lightblue', colormap='inferno', font_path='C:\Windows\Fonts\yumin.ttf', stopwords = set(stopwords)).generate(word_chain)

plt.figure(figsize = (15, 12))
plt.imshow(W)
plt.axis('off')
plt.show()

すると下記のようになります。

何かわかるような、何もわからんような。。。
スカイツリーと比較している人が多いのか、「スカイツリーも見えます」という人が多いのか、、とはいえ「スカイツリー」が東京タワー利用者の関心の対象となっていることは間違いなさそうです。
そこでスカイツリーの口コミもワードクラウドにしたものが下記です。

こちらは「エレベーター」や「チケット」など東京タワーではあまり言及のなかった（文字の大きくなかった）ワードが目立ちます。また「東京タワー」は目立ちません。このあたりは東京タワーとスカイツリーの差異と言えそうです。

おわり。

補足

Open Workなど企業の口コミサイトで、自社と競合を比べてみたりしても面白いかもしれませんし、
札幌ドーム、東京ドーム、名古屋ドーム、大阪ドーム、福岡ドームの五大ドームの口コミ比較もなど、類似施設を比較することで見えてくるものもありそうです。
ちなにみOpen Workのスクレイピングはheaderの設定が必要です。
詳細は下記をご参照ください。
【Python】スクレイピングで403 Forbidden：You don’t have permission to access on this serverが出た際の対処法

Twitter Developerの登録はこちらを参照：2度目のTwitter Developer登録で苦労した話
初めての登録なら苦労はしないはず．

アクセストークンを手に入れよう

プロジェクト作成

Twitter Developerに申請済みのアカウントにログイン後，ダッシュボードにアクセス．
まだProjectがなくまっさらの状態なので，+ Create Project からプロジェクトを作成する．

この後入力する情報は以下の通り．
1. プロジェクト名（自由入力）
2. 自分の立場（選択式）
3. プロジェクトの説明（自由入力）
4. App名（自由入力）

プロジェクト名とは別にアプリ名も決める必要がある．
例：プロジェクト名は「TestProject」，アプリ名は「MyTestApp」のような命名にするなど

自分の立場は，Twitter Developerに登録する際と同じ選択肢．
今回のプロジェクトに最も見合う立場を選択しよう．

またアプリ名は既に存在するアプリとかぶると使用できない．

無事アプリ名が決まると以下の画面に遷移する．
これらの情報は後から確認できるので，まずは App settings から設定に移ろう．

権限の設定

App settingsをクリックすると，作成したプロジェクトのページに遷移する．
ここからTweepyで使用するtokenを手に入れるための設定を行う．
まずはAppsの作成したアプリにある歯車をクリック．

アプリの画面に遷移するので，App permissionsのEditからアプリの権限を変更する．

TweepyからつぶやくためにはWriteの権限が必要であるため，Read and WriteもしくはRead + Write + Direct Messagesを選択する．セーブも忘れずに．

トークンの取得

次にアプリの画面のKeys and tokensに移動する．

API key & secretは，View Keysから何度でも確認できる．
しかしセキュリティの問題で約1年経過すると確認できなくなるため，手元にメモを残すのを忘れずに．

Access token & secretは1度生成したあと確認し直すことはできないので注意．
メモを取り忘れた／なくした場合，無効化もしくは再生成しかできない．

Tweepyでpythonからつぶやく

ここからはpythonに移行する．
pip install tweepy でtweepyをインストールしておく．

tweet.py

import tweepy

Consumer_key = '取得したApi key'
Consumer_secret = '取得したAPI Key secret'
Access_token = '取得したAccess token'
Access_secret = '取得したAccess token secret'

# OAuth handler を作成する
auth = tweepy.OAuthHandler(Consumer_key, Consumer_secret)
# OAuth handler にアクセストークンを伝える
auth.set_access_token(Access_token, Access_secret)
# APIを作成する
api = tweepy.API(auth_handler=auth)

# ツイート
api.update_status('APIでツイートしています。')

これだけ！

tokenのベタ書きは危なくない？

もしこのプログラムをGitにあげるとなると，秘密にすべきトークンが全世界に筒抜けになってしまう．
かといってコードが複雑になるとGit管理もしたくなるもの……。

解決策の1つとして，環境変数にトークンを書き込んでしまおう！がある．

Windowsの場合は設定から環境変数の追記が可能．
macの場合，bashを使用しているなら.bashrcに，zshを使用しているなら.zshrcに，以下の4行を書き込む．
（xxxxは各自のkeyに変更．'(クォーテーション)や"(ダブルクォーテーション)は必要ない．）
その後ターミナル上で source ~/.bashrc もしくは source ~/.zshrcで設定を反映させる．

.bashrc/.zshrc

export TWITTER_CK=xxxx
export TWITTER_CS=xxxx
export TWITTER_AT=xxxx
export TWITTER_AS=xxxx

無事環境変数に反映できたら，先程のプログラムを以下のように書き換える．

tweet2.py

import tweepy
import os

Consumer_key = str(os.getenv('TWITTER_CK'))
Consumer_secret = str(os.getenv('TWITTER_CS'))
Access_token = str(os.getenv('TWITTER_AT'))
Access_secret = str(os.getenv('TWITTER_AS'))

# OAuth handler を作成する
auth = tweepy.OAuthHandler(Consumer_key, Consumer_secret)
# OAuth handler にアクセストークンを伝える
auth.set_access_token(Access_token, Access_secret)
# APIを作成する
api = tweepy.API(auth_handler=auth)

# ツイート
api.update_status('APIでツイートしています。')

これで公開しても安全！

• 〇×ゲーム（三目並べ・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()

参考サイト・参考文献

• Classic Computer Science Problems in Python
• L12. Search for Decisions in Games ゲーム木の探索
• ミニマックス法 - Wikipedia
• 5分で覚えるAI Minimax（ミニマックス）法とalpha-beta法
• What is the Minimax Algorithm? - Artificial Intelligence
• 覚えることは2つだけ！　「○×ゲーム」の最も簡単な勝ち方を解説した動画が話題に
• マルバツゲームは引き分けになる

順列をすべて列挙するプログラムを各言語で書きました。10, 20, 30, 40 の4つの要素があったとして次のような出力をします。要素が $ n $ 個あれば、 $ n! $ 行の出力をします。出力するところになにか処理を書けば順列の全探索ができます。

 10 20 30 40
 10 20 40 30
 10 30 20 40
 10 30 40 20
 10 40 20 30
 10 40 30 20
 20 10 30 40
 20 10 40 30
...

書いた言語：

• ライブラリ使用: C++, Scala, Ruby, Python
• 独自実装: C言語, Java, JavaScript, Elixir

経緯：

AtCoderのABC183 C - Travelでは順列の列挙が必要でした。順列列挙のアルゴリズムがわからず、競技中は無理やり書いてACは取れたのですが、解説を読むともっとスマートなアルゴリズムがありました。しかもいくつかの言語では順列を列挙するライブラリも標準装備されていました。

悔しかったので各言語で順列を全部列挙するプログラムを書いたものです。

参考：

• AtCoder公式の解説

C++

C++には next_permutation という関数があります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int len = 4;
  vector<int> vec(len);
  for (int i = 0; i < len; i++) vec[i] = 10 * (i+1);
  do {
    for (int i = 0; i < len; i++) cout << " " << vec[i];
    cout << endl;
  } while (next_permutation(vec.begin(), vec.end()));
}

Scala

Scalaには permutations というメソッドがあります。

object Main extends App {
  val len = 4;
  val seq = (1 to len).map(10 * _);
  seq.permutations.foreach { seq =>
    println(" " + seq.mkString(" "));
  }
}

Ruby

Rubyには permutation というメソッドがあります。

len = 4
arr = (1 .. len).map do |i|
  10 * i
end
arr.permutation do |arr|
  puts(" " + arr.join(" "))
end

Python

Pythonには itertools.permutations という関数があります。

import itertools

len = 4
lst = [10 * (i+1) for i in range(len)]
for lst2 in itertools.permutations(lst):
    print(" " + " ".join(map(str, lst2)))

C言語

C++の next_permutation を自分で実装しています。（ほとんどAtCoderの解説そのままです）

#include <stdio.h>

int next_permutation(int *arr, int len) {
  int left = len - 2;
  while (left >= 0 && arr[left] >= arr[left+1]) left--;
  if (left < 0) return 0;
  int right = len - 1;
  while (arr[left] >= arr[right]) right--;
  { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
  left++;
  right = len - 1;
  while (left < right) {
    { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
    left++;
    right--;
  }
  return 1;
}

int main() {
  int len = 4;
  int arr[len];
  for (int i = 0; i < len; i++) arr[i] = 10 * (i+1);
  do {
    for (int i = 0; i < len; i++) printf(" %d", arr[i]);
    printf("\n");
  } while (next_permutation(arr, len));
}

Java

C言語で実装した next_permutation と同じ実装です。

class Main {
  public static boolean nextPermutation(int[] arr) {
    int len = arr.length;
    int left = len - 2;
    while (left >= 0 && arr[left] >= arr[left+1]) left--;
    if (left < 0) return false;
    int right = len - 1;
    while (arr[left] >= arr[right]) right--;
    { int t = arr[left]; arr[left] = arr[right];  arr[right] = t; }
    left++;
    right = len - 1;
    while (left < right) {
      { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
      left++;
      right--;
    }
    return true;
  }

  public static void main(String[] args) {
    int len = 4;
    var arr = new int[len];
    for (int i = 0; i < len; i++) {
      arr[i] = 10 * (i+1);
    }
    do {
      var sb = new StringBuilder();
      for (int i = 0; i < len; i++) {
        sb.append(String.format(" %d", arr[i]));
      }
      System.out.println(sb);
    } while (nextPermutation(arr));
  }
}

JavaScript

C言語やJavaで実装した next_permutation と同じ実装です。

function next_permutation(arr) {
    const len = arr.length;
    let left = len - 2;
    while (left >= 0 && arr[left] >= arr[left+1]) left--;
    if (left < 0) return false;
    let right = len - 1;
    while (arr[left] >= arr[right]) right--;
    { const t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
    left++;
    right = len - 1;
    while (left < right) {
        { const t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
        left++;
        right--;
    }
    return true;
}

const len = 4;
const arr = [];
for (let i = 0; i < len; i++) arr.push(10 * (i+1));
do {
    let str = "";
    for (let i = 0; i < len; i++) str += " " + arr[i];
    console.log(str);
} while (next_permutation(arr));

Elixir

C言語やJavaでの実装とは異なるアルゴリズムです。 next_permutation と違って、順列の全パターンを始めに作成しています。

defmodule Main do
  def permutations([]), do: [[]]
  def permutations(list) do
    for elem <- list, p <- permutations(list -- [elem]), do: [elem | p]
  end

  def main do
    len = 4
    list = (1 .. len) |> Enum.map(fn x -> 10 * x end)
    permutations(list) |> Enum.each(fn l ->
      IO.puts(" " <> Enum.join(l, " "))
    end)
  end
end