Start_python’s diary

ふたり暮らし

アラフィフ夫婦のフリーランスプラン

Python ミニマックス法で五目並べに挑戦します(AIプログラミング 第8回)

はじめに

まず、5×5の盤面での「五目並べ」を作成してみます。前回の「三目並べ」を少し変更するだけで完成しました。それほど難しくはなかったです。

 

実行してみましたが時間がかかりすぎます。メモリ不足でフリーズしてしまいました。

 

3手先まで読むようにプログラムを変更しました。(深さを3に変更しました)

上手く動きました。(5手先までで時間がかかって待つのは限界です)

5×5の盤面での五目並べは引き分けにしかなりません。(勝敗が付かないです)

 

次に、5×5の盤面での「四目並べ」を作成しました。5手先まで読むようにしています。そこそこいい勝負?はするのですがかなり弱いです。できれば7手先まで読ませるようにしたいです。

 

アルファベータ法を学ぶ

アルファベータ法とは、基本的にミニマックス法と同じですが計算しなくても同じ結果かそれ以下になる結果の部分を省略して処理時間を短縮する手法です。

 

9手先まで読ませても時間はかかりますがなんとか動きました。結果はコンピュータが先手でも引き分けになりました。

 

7手先まで読ませるプログラムだと処理時間は短くなっていい感じです。結果も引き分けになり、先手後手どちらでもコンピュータが負けることはありません。

 

 

四目並べ(盤面は5×5)のソースコード

class main():

    def __init__(self):
        # 盤面の初期化
        self.board = ["  "] * 25
        # 先攻後攻(「1」以外は後攻になる)
        self.my_turn = input("先攻 1 : 後攻 2 >> ") == "1"

        print(' 1| 2| 3| 4| 5')
        print('--------------')
        print(' 6| 7| 8| 9|10')
        print('--------------')
        print('11|12|13|14|15')
        print('--------------')
        print('16|17|18|19|20')
        print('--------------')
        print('21|22|23|24|25')

        # ゲーム開始
        self.state = "プレイ中"
        while self.state == "プレイ中":
            if self.my_turn:
                # プレイヤーの入力
                while True:
                    try:
                        value = int(input('あなたの番です >> ')) - 1
                        if self.board[value] == "  ":
                            # 「value」に置く
                            self.board[value] = " o"
                            # 勝敗の判定
                            self.check_state()
                            # ターン交代
                            self.my_turn = not(self.my_turn)
                            break
                        else:
                            print('そこには打てません')
                    except:
                        print('入力し直してください')
            else:
                # AIの入力
                print("AI")
                # 1手目だけ手助け
                if self.board[12] == "  ":
                    self.board[12] = " x"
                elif self.board[0] != " o" and self.board[6] == "  ":
                    self.board[6] = " x"
                else:
                    # 何手先まで読むか
                    self.n = 7
                    # ミニマックス法で最良の手を探索
                    value = self.max_value(0, -10, 10)
                    # 「最良の手」に打つ
                    self.board[value] = " x"
                # 勝敗の判定
                self.check_state()
                # ターン交代
                self.my_turn = not(self.my_turn)


            # 盤面を表示する
            print('{0[0]}|{0[1]}|{0[2]}|{0[3]}|{0[4]}'.format(self.board))
            print('--------------')
            print('{0[5]}|{0[6]}|{0[7]}|{0[8]}|{0[9]}'.format(self.board))
            print('--------------')
            print('{0[10]}|{0[11]}|{0[12]}|{0[13]}|{0[14]}'.format(self.board))
            print('--------------')
            print('{0[15]}|{0[16]}|{0[17]}|{0[18]}|{0[19]}'.format(self.board))
            print('--------------')
            print('{0[20]}|{0[21]}|{0[22]}|{0[23]}|{0[24]}'.format(self.board))

        # 結果を表示する
        print(self.state)


    # 勝敗の判定
    def check_state(self):
        for i in range(5):
            if self.board[i:20:5] == [" o"," o"," o"," o"] \
            or self.board[i+5:25:5] == [" o"," o"," o"," o"] \
            or self.board[5*i:5*i+4] == [" o"," o"," o"," o"] \
            or self.board[5*i+1:5*i+5] == [" o"," o"," o"," o"] \
            or self.board[0:19:6] == [" o"," o"," o"," o"] \
            or self.board[1:20:6] == [" o"," o"," o"," o"] \
            or self.board[5:24:6] == [" o"," o"," o"," o"] \
            or self.board[6:25:6] == [" o"," o"," o"," o"] \
            or self.board[3:16:4]  == [" o"," o"," o"," o"] \
            or self.board[4:17:4]  == [" o"," o"," o"," o"] \
            or self.board[8:21:4]  == [" o"," o"," o"," o"] \
            or self.board[9:22:4]  == [" o"," o"," o"," o"]:
                self.state = "あなたの勝ちです"
                return
        for i in range(4):
            if self.board[i:20:5] == [" x"," x"," x"," x"] \
            or self.board[i+5:25:5] == [" x"," x"," x"," x"] \
            or self.board[5*i:5*i+4] == [" x"," x"," x"," x"] \
            or self.board[5*i+1:5*i+5] == [" x"," x"," x"," x"] \
            or self.board[0:19:6] == [" x"," x"," x"," x"] \
            or self.board[1:20:6] == [" x"," x"," x"," x"] \
            or self.board[5:24:6] == [" x"," x"," x"," x"] \
            or self.board[6:25:6] == [" x"," x"," x"," x"] \
            or self.board[3:16:4]  == [" x"," x"," x"," x"] \
            or self.board[4:17:4]  == [" x"," x"," x"," x"] \
            or self.board[8:21:4]  == [" x"," x"," x"," x"] \
            or self.board[9:22:4]  == [" x"," x"," x"," x"]:
                self.state = "AIの勝ちです"
                return

        if all(state != "  " for state in self.board):
            self.state = "引き分けです"
            return

        self.state = "プレイ中"



    # ミニマックス法で探索
    def max_value(self, depth, alpha, beta):
        # 勝敗がついた場合
        if self.state != "プレイ中" or depth >= self.n:
            # 評価点を出す
            return self.evaluate(depth)

        best_value = 0
        value = -1000

        #for i in range(25):
        for i in [12, 6, 7, 8, 13, 18, 17, 16, 11, 0, 1, 2, 3, 4, 9, 14, 19, 24, 23, 22, 21, 20, 15, 10, 5]:
            # 「i」が空の場合
            if self.board[i] == "  ":
                # 「i」に打つ
                self.board[i] = " x"
                # 勝敗の判定
                self.check_state()
                # ターン交代
                self.my_turn = not(self.my_turn)
                # 相手のターンへ
                child_value = self.min_value(depth+1, alpha, beta)
                # 1つ前の手に戻す
                self.board[i] = "  "
                # ターン交代
                self.my_turn = not(self.my_turn)

                # 相手の手がβ値より大きい場合、これ以上の探索はしない(for文を抜ける)
                if beta <= child_value:
                    return child_value

                # 良い手が見つかった場合
                if child_value > value:
                    value = child_value
                    best_value = i
                    # α値の更新
                    alpha = child_value
                if depth == 0:
                    # 評価点を表示する
                    print("(打つ場所:",i+1,"評価点:",child_value,")")

        if depth == 0:
            return best_value
        else:
            return value


    # 相手のターン
    def min_value(self, depth, alpha, beta):
        # 勝敗がついた場合
        if self.state != "プレイ中" or depth >= self.n:
            # 評価点を出す
            return self.evaluate(depth)

        value = 1000

        for j in [12, 6, 7, 8, 13, 18, 17, 16, 11, 0, 1, 2, 3, 4, 9, 14, 19, 24, 23, 22, 21, 20, 15, 10, 5]:
            # 「j」が空の場合
            if self.board[j] == "  ":
                # 「j」に打つ
                self.board[j] = " o"
                # 勝敗の判定
                self.check_state()
                # ターン交代
                self.my_turn = not(self.my_turn)
                # コンピュータのターンへ
                child_value = self.max_value(depth+1, alpha, beta)
                # 1つ前の手に戻す
                self.board[j] = "  "
                # ターン交代
                self.my_turn = not(self.my_turn)

                # コンピュータの手がα値より小さい場合、これ以上の探索はしない(for文を抜ける)
                if alpha >= child_value:
                    return child_value

                # 良い手が見つかった場合
                if child_value < value:
                    value = child_value
                    # β値の更新
                    beta = child_value

        if depth == 0:
            return best_value
        else:
            return value
        
    # 評価点
    def evaluate(self, depth):
        if self.state == "AIの勝ちです":
            self.state = "プレイ中"
            return 10 - depth
        elif self.state == "あなたの勝ちです":
            self.state = "プレイ中"
            return depth - 10
        else:
            self.state = "プレイ中"
            return 0


if __name__ == '__main__':
    for i in range(3):
        main()

ミニマックス法の「再帰関数」部分をコンピュータの手とプレイヤーの手の2つに分けました。「アルファベータ法」を利用するのに分けた方がわかりやすいです。

 

for j in [12, 6, 7, 8, 13, 18, 17, 16, 11, 0, 1, 2, 3, 4, 9, 14, 19, 24, 23, 22, 21, 20, 15, 10, 5]:

「アルファベータ法」だと早めに良い手が見つかると処理時間が短縮できるので、真ん中のほうから先に読ませるように変更しました。

 

 

まとめ

アルファベータ法の理解が追い付いてないのでまだ処理時間の短縮は可能なのかもしれないですが、とてもじゃないですけど通常の「五目並べ」をミニマックス法で全通りを読み切るのは不可能な気がしてきました。

 

ミニマックス法での「五目並べ」作成はあきらめました。「アルファベータ法」以上のアルゴリズムが見つかればまた挑戦するかもしれません。

 

 

↓よかったらポチッとしていってください。

にほんブログ村 IT技術ブログ Pythonへ
にほんブログ村