「十六式いろは」のあれこれ

コンピュータ将棋ソフトのエンジン「十六式いろは」の開発者のブログです。

(連続企画)Pythonで将棋ソフト制作2のその5-ミニマックス法の補足

www.youtube.com

将棋ソフト作成の連続企画の一つです。
上記の動画で作成したソースコードです。
ミニマックス法で実装したものです。

main.py

# 1手先読み版からミニマックス法版-修正の解説が必要
# 実ステップ数: 275

import cshogi
import random
import time
# 文字列の検索のために正規表現を使う。
import re
# リストのコピー用
import copy


# 定数
TSUMI_SCORE = 32000  # 詰み等の評価値の基準。(指し手がない時の評価値)
# 3以上だと1手で10秒以上待たされる。(4だと数分以上)
DEPTH_LIMIT = 2  # 読みの深さ
LOG_FILTER = 1000  # 値が大きいほどログの出力が減る。デフォルト:1000

# グローバル変数
global_my_turn = "先手"  # 自分(このエンジン)の手番。"先手"か"後手"の文字列。
global_start_time = time.perf_counter()  # 計測用の変数
global_search_count = 0  # 探索数


def koma_count(board):
    """局面内の各駒の数を数え、dict形式で返す。

    cshogiの局面における、先手と後手の各駒の数をカウントする。
    王以外の駒すべてが含まれる。

    Args:
        board: cshogi.Board型で、評価対象の局面。

    Returns:
        dict形式。各駒とその数。
        例:
        {'先手の歩': 7, '先手の香': 2, '先手の桂': 1, '先手の銀': 3,
         '先手の角': 0, '先手の飛': 1, '先手の金': 1, '先手のと': 1,
         '先手の杏': 0, '先手の圭': 0, '先手の全': 0, '先手の馬': 0,
         '先手の竜': 0, '先手持ち駒の歩': 0, '先手持ち駒の香': 0,
         '先手持ち駒の桂': 0, '先手持ち駒の銀': 0, '先手持ち駒の角': 0,
         '先手持ち駒の飛': 1, '先手持ち駒の金': 1, '後手の歩': 5,
         '後手の香': 2, '後手の桂': 2, '後手の銀': 0, '後手の角': 2,
         '後手の飛': 0, '後手の金': 1, '後手のと': 0, '後手の杏': 0,
         '後手の圭': 0, '後手の全': 0, '後手の馬': 0, '後手の竜': 0,
         '後手持ち駒の歩': 5, '後手持ち駒の香': 0, '後手持ち駒の桂': 1,
         '後手持ち駒の銀': 1, '後手持ち駒の角': 0, '後手持ち駒の飛': 0,
         '後手持ち駒の金': 1} 

    """

    board_str = str(board)  # 局面の文字列化
    # cshogiのソースコードposition.cppに駒の種類が書いている。
    koma_cnt = {"先手の歩": 0}  # 初期化
    # 先手
    koma_cnt["先手の歩"] = board_str.count("+FU")
    koma_cnt["先手の香"] = board_str.count("+KY")
    koma_cnt["先手の桂"] = board_str.count("+KE")
    koma_cnt["先手の銀"] = board_str.count("+GI")
    koma_cnt["先手の角"] = board_str.count("+KA")
    koma_cnt["先手の飛"] = board_str.count("+HI")
    koma_cnt["先手の金"] = board_str.count("+KI")
    koma_cnt["先手のと"] = board_str.count("+TO")
    koma_cnt["先手の杏"] = board_str.count("+NY")
    koma_cnt["先手の圭"] = board_str.count("+NK")
    koma_cnt["先手の全"] = board_str.count("+NG")
    koma_cnt["先手の馬"] = board_str.count("+UM")
    koma_cnt["先手の竜"] = board_str.count("+RY")

    # 先手の持ち駒
    # マッチした場合はgroup()でマッチ文字列取得、なければ空文字列
    line_str = re.search(r"P\+.*\n", board_str)
    if line_str:
        line_str = line_str.group()
    else:
        line_str = ""
    koma_cnt["先手持ち駒の歩"] = line_str.count("FU")
    koma_cnt["先手持ち駒の香"] = line_str.count("KY")
    koma_cnt["先手持ち駒の桂"] = line_str.count("KE")
    koma_cnt["先手持ち駒の銀"] = line_str.count("GI")
    koma_cnt["先手持ち駒の角"] = line_str.count("KA")
    koma_cnt["先手持ち駒の飛"] = line_str.count("HI")
    koma_cnt["先手持ち駒の金"] = line_str.count("KI")

    # 後手
    koma_cnt["後手の歩"] = board_str.count("-FU")
    koma_cnt["後手の香"] = board_str.count("-KY")
    koma_cnt["後手の桂"] = board_str.count("-KE")
    koma_cnt["後手の銀"] = board_str.count("-GI")
    koma_cnt["後手の角"] = board_str.count("-KA")
    koma_cnt["後手の飛"] = board_str.count("-HI")
    koma_cnt["後手の金"] = board_str.count("-KI")
    koma_cnt["後手のと"] = board_str.count("-TO")
    koma_cnt["後手の杏"] = board_str.count("-NY")
    koma_cnt["後手の圭"] = board_str.count("-NK")
    koma_cnt["後手の全"] = board_str.count("-NG")
    koma_cnt["後手の馬"] = board_str.count("-UM")
    koma_cnt["後手の竜"] = board_str.count("-RY")

    # 後手の持ち駒
    # マッチした場合はgroup()でマッチ文字列取得、なければ空文字列
    line_str = re.search(r"P-.*\n", board_str)
    if line_str:
        line_str = line_str.group()
    else:
        line_str = ""
    koma_cnt["後手持ち駒の歩"] = line_str.count("FU")
    koma_cnt["後手持ち駒の香"] = line_str.count("KY")
    koma_cnt["後手持ち駒の桂"] = line_str.count("KE")
    koma_cnt["後手持ち駒の銀"] = line_str.count("GI")
    koma_cnt["後手持ち駒の角"] = line_str.count("KA")
    koma_cnt["後手持ち駒の飛"] = line_str.count("HI")
    koma_cnt["後手持ち駒の金"] = line_str.count("KI")

    return koma_cnt


def komadoku_evaluate(koma_cnt):
    """
    その局面の駒得による評価値を計算する。

    Args:
        koma_cnt(dict): 各駒とその数

    Returns:
        phase_value (int): その局面の駒得による評価値

    """
    # ★盤上の駒と持ち駒の差を少なくした。
    koma_value = {"先手の歩": 95,
                  "先手の香": 195,
                  "先手の桂": 295,
                  "先手の銀": 495,
                  "先手の角": 795,
                  "先手の飛": 895,
                  "先手の金": 595,
                  "先手のと": 595,
                  "先手の杏": 595,
                  "先手の圭": 595,
                  "先手の全": 595,
                  "先手の馬": 1195,
                  "先手の竜": 1295,
                  "先手持ち駒の歩": 105,
                  "先手持ち駒の香": 205,
                  "先手持ち駒の桂": 305,
                  "先手持ち駒の銀": 505,
                  "先手持ち駒の角": 805,
                  "先手持ち駒の飛": 905,
                  "先手持ち駒の金": 605,
                  "後手の歩": -95,
                  "後手の香": -195,
                  "後手の桂": -295,
                  "後手の銀": -495,
                  "後手の角": -795,
                  "後手の飛": -895,
                  "後手の金": -595,
                  "後手のと": -595,
                  "後手の杏": -595,
                  "後手の圭": -595,
                  "後手の全": -595,
                  "後手の馬": -1195,
                  "後手の竜": -1295,
                  "後手持ち駒の歩": -105,
                  "後手持ち駒の香": -205,
                  "後手持ち駒の桂": -305,
                  "後手持ち駒の銀": -505,
                  "後手持ち駒の角": -805,
                  "後手持ち駒の飛": -905,
                  "後手持ち駒の金": -605}

    phase_value = 0  # 出力する評価値を初期化
    for key in koma_cnt.keys():
        # 駒の種類 * その駒の数
        phase_value += koma_value[key] * koma_cnt[key]

    return phase_value


def order_list(move_lst):
    """
    cshogiから返ってきた合法手のリストをオーダリングする。

    今のところ、とりあえずランダム。
    これで、アルファベータカットしても
    事前にシャッフルしているので、ランダムで指す。

    Args:
        move_lst(int list): 合法手のリスト

    Returns:
        int list: オーダリング(並べ替えた)した合法手のリスト

    """

    random.shuffle(move_lst)

    return move_lst


def lap_time():
    """
    処理にかかった時間を返す。

    Returns:
        int: 処理にかかったミリ秒。

    """
    temp = int((time.perf_counter() - global_start_time)*1000)
    # この関数の戻り値で除算するのでゼロを避ける。
    if temp == 0:
        temp = 1
    
    return temp


def usi_output(score_lst):
    """
    USIプロトコルの出力をする。

    Args:
        score_lst (複合list): 読み筋リスト、評価値、のリスト
            (例)
            [ [524418, 1252401], 650 ]

    Returns:
        None.

    """
    output = f"info time {lap_time()} depth { len(score_lst[0]) } "
    output += f"nodes {global_search_count} nps {int(global_search_count*1000/lap_time())} "
    # 評価値の部分
    output += "score "
    if global_my_turn == "先手":
        if score_lst[1] == TSUMI_SCORE:
            output += "mate +"
        elif score_lst[1] == -TSUMI_SCORE:  # 後手番
            output += "mate -"
        else:
            output += f"cp {score_lst[1]} "
    # 出力時は、自分が後手の場合は評価値を反転する。
    else:  # "後手"
        if score_lst[1] == TSUMI_SCORE:
            output += "mate -"
        elif score_lst[1] == -TSUMI_SCORE:  # 後手番
            output += "mate +"
        else:
            output += f"cp {-score_lst[1]} "
    # 読み筋
    # 読み筋のリストが空っぽならpvを出力しない。
    if len(score_lst[0]) > 0:
        output += "pv"
        for move in score_lst[0]:
            output += " " + cshogi.move_to_usi(move)
    print(output, flush=True)


def evaluation(board):
    """
    評価関数。

    Args:
        board (cshogi.Board): cshogiでの局面

    Returns:
        evaluation_value (int): 評価値

    """
    # 駒割りの評価値計算。
    koma_cnt = koma_count(board)
    evaluation_value = komadoku_evaluate(koma_cnt)

    return evaluation_value

def max_level(board, depth, yomisuji_lst):
    """
    ミニマックス法のMax(先手)側の処理。

    Args:
        board (cshogi.Board): cshogiでの局面
        depth (int): 現在の読みの深さ
        move_lst (int list): 合法手のリスト。cshogiの数字。

    Returns:
        複合list: 読み筋リスト、評価値、のリスト
            (例)
            [ [524418, 1252401], 650 ]
    """
    # 探索数(グローバル変数)書き換える必要があるので宣言する。
    global global_search_count
    
    # 読み筋(指し手は数字)、評価値
    max_score_lst = [yomisuji_lst, -TSUMI_SCORE-1 ]
    
    # 探索をするので探索数を追加する。
    global_search_count += 1
    
    # 合法手をリスト化する。
    move_lst = list(board.legal_moves)
    
    # 先読みの次の指し手がない(詰み(mate))のときの評価値を返す。
    if len(move_lst) == 0:
        score = -TSUMI_SCORE  # 評価値の最小値(後手の勝ち)
        return [yomisuji_lst, score]
    
    # 探索を終える。(これ以上深く探さない)
    # 終端条件
    if depth == DEPTH_LIMIT:
        # 限界の深さでの評価値。
        # 評価関数を使い、局面から評価値を計算して返す。
        # 今は駒割りのみ。
        score = evaluation(board)
        return [yomisuji_lst, score]
    
    # 探索をする。
    # 合法手をオーダリングする。
    else:
        move_lst = order_list(move_lst)
        
        # 合法手のそれぞれの手を指して確認する。
        for move_str in move_lst:
            # 先読みの手を指す。
            board.push(move_str)
            
            # 現在の読み筋yomisuji_lstに、先読みの次の一手を
            # 加えて、min_levelに送り次の先読みをする。
            yomisuji_next_lst = yomisuji_lst + [move_str]
            
            # 次の手(後手番)を考える
            score_lst = min_level(board, depth+1, yomisuji_next_lst)
            
            # 手を戻す。
            board.pop()
            
            # より評価値が良い手が見つかった。読み筋と評価値を保存する。
            if score_lst[1] > max_score_lst[1]:
                max_score_lst = copy.deepcopy(score_lst)
            
            # ログ出力。一部出力しない。出力数を制限する。
            if global_search_count % LOG_FILTER == 0:
                usi_output(score_lst)
            
        # 先手の最高値のリストを返す。
        return max_score_lst




def min_level(board, depth, yomisuji_lst):
    """
    ミニマックス法のMin(後手)側の処理。

    Args:
        board (cshogi.Board): cshogiでの局面
        depth (int): 現在の読みの深さ
        move_lst (int list): 合法手のリスト。cshogiの数字。

    Returns:
        複合list: 読み筋リスト、評価値、のリスト
            (例)
            [ [524418, 1252401], 650 ]
    """
    # 探索数(グローバル変数)書き換える必要があるので宣言する。
    global global_search_count
    
    # 読み筋(指し手は数字)、評価値
    min_score_lst = [yomisuji_lst, TSUMI_SCORE+1 ]
    
    # 探索をするので探索数を追加する。
    global_search_count += 1
    
    # 合法手をリスト化する。
    move_lst = list(board.legal_moves)
    
    # 先読みの次の指し手がない(詰み(mate))のときの評価値を返す。
    if len(move_lst) == 0:
        score = TSUMI_SCORE  # 評価値の最大値(先手の勝ち)
        return [yomisuji_lst, score]
    
    # 探索を終える。(これ以上深く探さない)
    # 終端条件
    if depth == DEPTH_LIMIT:
        # 限界の深さでの評価値。
        # 評価関数を使い、局面から評価値を計算して返す。
        # 今は駒割りのみ。
        score = evaluation(board)
        return [yomisuji_lst, score]
    
    # 探索をする。
    # 合法手をオーダリングする。
    else:
        move_lst = order_list(move_lst)
        
        # 合法手のそれぞれの手を指して確認する。
        for move_str in move_lst:
            # 先読みの手を指す。
            board.push(move_str)
            
            # 現在の読み筋yomisuji_lstに、先読みの次の一手を
            # 加えて、min_levelに送り次の先読みをする。
            yomisuji_next_lst = yomisuji_lst + [move_str]
            
            # 次の手(先手番)を考える
            score_lst = max_level(board, depth+1, yomisuji_next_lst)
            
            # 手を戻す。
            board.pop()
            
            # より評価値が良い手が見つかった。読み筋と評価値を保存する。
            if score_lst[1] < min_score_lst[1]:
                min_score_lst = copy.deepcopy(score_lst)
            
            # ログ出力。一部出力しない。出力数を制限する。
            if global_search_count % LOG_FILTER == 0:
                usi_output(score_lst)
            
        # 後手の最高値(最小値)のリストを返す。
        return min_score_lst


def main():
    """
    ここから処理を開始する。

    Returns:
        None.

    """
    # グローバル変数
    global global_my_turn  # 手番
    global global_start_time  # 計測開始時刻に関する数値。
    
    while True:
        input_cmd = input()

        # USIプロトコル対応の将棋GUI(将棋所)に
        # エンジン登録するときに通信する処理。
        #
        # 普通にprintを使うと、改行はしてくれるので
        # 将棋エンジンを作る場合、問題なし。
        # バッファリングさせない(フラッシュさせる)ために
        # printの引数に「flush=True」を使う。
        if input_cmd == "usi":
            # ソフト名
            print("id name 16-168ui_03-1_min-max", flush=True)
            # 開発者名
            print("id author R.Sueyoshi", flush=True)
            print("usiok", flush=True)

        # 対局準備
        if input_cmd == "isready":
            # 設定の読み込みが必要ならここで処理する。
            print("readyok", flush=True)

        # 対局開始の合図
        if input_cmd == "usinewgame":
            pass

        # 局面の受け取り
        # 平手はstartpos
        # 例)
        # position startpos moves 7g7f 3c3d 2g2f
        # 最初の8文字を使う。
        if input_cmd[0:8] == "position" or input_cmd[0:1] == "a" or input_cmd[0:1] == "w" or input_cmd[0:1] == "b":
            # startposで局面が送られてくるとき
            cmd_lst = list(input_cmd.split(" "))  # スペース区切りのリスト。
            # 例1)position startpos
            if len(cmd_lst) == 2:
                global_my_turn = "先手"
            # 例2)position startpos moves 7g7f 8d8e
            else:
                if (len(cmd_lst)-2) % 2 == 1:
                    global_my_turn = "先手"
                else:
                    global_my_turn = "後手"

            # 局面にセットする。
            # cmd_lst[-1:][0]は最後の文字列(相手の手等)
            if cmd_lst[0] == "a":  # 裏コマンド、平手をセットする。
                board = cshogi.Board()

            elif cmd_lst[0] == "w":  # 裏コマンドその2。指し手生成祭(後手)
                # 「指し手生成祭」の局面
                b_phase = "l6nl/5+P1gk/2np1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL w GR5pnsg 1"
                #b_cmd_lst = list(b_phase.split(" "))  # スペース区切りのリスト。
                board = cshogi.Board(b_phase)  # 指定局面のセット
                # 手番の確認
                global_my_turn = "後手"
            
            elif cmd_lst[0] == "b":  # 裏コマンドその3。指し手生成祭の派生(先手)
                # 「指し手生成祭」の局面
                b_phase = "l6nl/5+P1gk/2np1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL b GR5pnsg 1"
                #b_cmd_lst = list(b_phase.split(" "))  # スペース区切りのリスト。
                board = cshogi.Board(b_phase)  # 指定局面のセット
                # 手番の確認
                global_my_turn = "先手"

            elif cmd_lst[1] == "startpos":  # 平手
                board = cshogi.Board()
                # 送られてきた局面まで局面をセットしなおす。
                if len(cmd_lst) > 2:
                    for i in range(3, len(cmd_lst)):
                        board.push_usi(cmd_lst[i])  # 指す

            # sfenで局面が送られてくるとき
            elif cmd_lst[1] == "sfen":  # 指定局面
                sfen_str = (cmd_lst[2] + " " + cmd_lst[3] +
                            " " + cmd_lst[4] + " " + cmd_lst[5])
                # 例1)position sfen lnsgkgsnl/1r5b1/p1ppppppp/1p7/9/7P1/PPPPPPP1P/1B5R1/LNSGKGSNL b - 1
                if len(cmd_lst) == 6:
                    if cmd_lst[3] == "b":
                        global_my_turn = "先手"
                    else:
                        global_my_turn = "後手"
                # 例2)position sfen lnsgkgsnl/1r5b1/p1ppppppp/1p7/9/7P1/PPPPPPP1P/1B5R1/LNSGKGSNL b - 1 moves 7g7f 8d8e
                else:
                    if (len(cmd_lst)-6) % 2 == 1 and cmd_lst[3] == "b":
                        global_my_turn = "先手"
                    # ★以下、追加修正
                    elif (len(cmd_lst)-6) % 2 == 0 and cmd_lst[3] == "w":
                        global_my_turn = "先手"
                    elif (len(cmd_lst)-6) % 2 == 1 and cmd_lst[3] == "w":
                        global_my_turn = "後手"
                    elif (len(cmd_lst)-6) % 2 == 0 and cmd_lst[3] == "b":
                        global_my_turn = "後手"
                    else:
                        global_my_turn = "先手"  # ここは通らない想定

                board = cshogi.Board(sfen_str)
                # 送られてきた局面まで局面をセットしなおす。
                if len(cmd_lst) > 6:
                    for i in range(7, len(cmd_lst)):
                        board.push_usi(cmd_lst[i])  # 指す

            else:
                # 想定外の時はエンジンを終了する。
                print("エラー:受信コマンド想定外")
                break

        # 思考開始の合図
        # 最初の3文字を使う。
        if input_cmd[0:2] == "go":
            # 自分の次の手を考えさせる。
            
            # 計測開始
            global_start_time = time.perf_counter()

            # 王手をかけられたとき
            # 詰みのとき(負け)
            if len(list(board.legal_moves)) == 0:
                print("bestmove resign", flush=True)
            
            else:
                # 次の一手を将棋所等の将棋GUIに伝える。
                # 探索。次の一手を探索する。
                # 合法手リストに評価値を付けて、評価順に並べ替える。
                # move_lst_searchedは、指し手と評価値のリスト。
                # 1手先を考える(自分・うい)、評価値は最大になる手。
                # 先手番、後手番で探索の仕方(関数)を変える。
                # 先手番用の探索の仕方(関数)
                if global_my_turn == "先手":
                    move_lst_searched = max_level(board, 0, [])
                else:  # 後手
                    move_lst_searched = min_level(board, 0, [])
                
                # このエンジンが優勢と思えば、先手でも後手でも評価値は正の値
                # 劣勢と思えば、先手でも後手でも評価値は負の値
                # だから、後手の時は評価値を反転させる必要がある。
                # また評価値が最大値の時「mate」を伝える。
                
                # 確認のときに、速く指すことを防ぐため
                #time.sleep(1)
                
                # 深さ(何手先まで読んだか)を修正する。
                #関数化したusi_output()
                usi_output(move_lst_searched)
                print("bestmove", cshogi.move_to_usi(
                    move_lst_searched[0][0]), flush=True)
        
        # 1ゲームが終わった場合
        if input_cmd[:8] == "gameover":
            # コマンド受付を終了しない。
            continue
        
        # エンジン停止の合図
        if input_cmd == "quit":
            # コマンド受付を終了する。
            break

    # エンジンを終了させる。
    quit()


# main関数の実行
main()