(連続企画)Pythonで将棋ソフト制作2のその5-ミニマックス法の補足
将棋ソフト作成の連続企画の一つです。
上記の動画で作成したソースコードです。
ミニマックス法で実装したものです。
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()