1file matchというのは下記の経緯で私が考案した初級者歓迎部門の新設案です。
1file match（仮）の参考資料 - 48's diary
1file match（仮）の参考資料２（数行でレートを1300以上上げる） - 48's diary
1file match（仮）の参考資料３（駒得評価関数） - 48's diary
思い付きで弄ってましたが短いサンプルプログラムを作るのは好きな方でプチ実験的なものは多数作っています。
前回、駒得評価関数を実装しましたがその際Min-Max法のサンプルは沢山あるとコメントしてますが適当なものを探しておきました。
Algorithms with Python / ミニマックス法 (nct9.ne.jp)
参考文献に松原先生の著書がある辺りがミソです。
で、自分で実装したものが以下です。
# 参考：ネガアルファ法 http://www.nct9.ne.jp/m_hiroi/light/pyalgo25.html
def negaalpha(depth, board, alpha, beta):
global nodes, start
if board.is_game_over(): # 負け局面は即リターン
return -30000, "resign"
if board.is_nyugyoku(): # 勝ち局面も即リターン
return 30000, "win"
if m := board.mate_move(3): # 三手詰みも即リターン
return 30000, move_to_usi(m)
if depth <= 0: # 残り探索深さがなくなれば評価値を返す
# global nodes
nodes += 1 # 評価した局面数をカウント
v = eval(board)
return v, ""
#
move = 0 # 以下のループが全部すり抜けたとき用の初期化
pvm = ""
legal_moves = list(board.legal_moves) # いわゆる合法手リスト
for m in legal_moves:
board.push(m)
if draw := board.is_draw():
v = [0,0,-28000,28000,-28000,28000][draw]
pv = ""
else:
v = -v
board.pop() # 将棋はループ用に手戻しするが，ゲームによっては盤面コピーして毎回捨てるほうが速い場合も
move = m
pvm = pv
if depth == SEARCH_DEPTH:
lap_time = time() - start + 1e-6
print('info nps {} time {} nodes {} score cp {} pv {}'.format(
def go():
if board.is_game_over():
return 'resign'
if board.is_nyugyoku():
return 'win'
if not board.is_check():
if (matemove:=board.mate_move_in_1ply()):
print('info score mate 1 pv {}'.format(m:=move_to_usi(matemove)))
return m
global nodes, start
nodes, start = 0, time()
lap_time = time() - start + 1.0e-6 # ０除算エラー対策で微小値を足してある
print("info time", int(lap_time * 1000), "depth", SEARCH_DEPTH, "nodes", nodes, "nps", int(nodes / lap_time), "score cp", int(value), "pv", move)
return move.split()[0]
実装したのはアルファベータ法の亜種と言うか実装では主流になっているネガアルファ法です。評価値を返す際にアルファベータも含めて符号を変えているのがミソですね。
ちょっと工夫しているのは探索途中の読み筋を表示してみたりしました。
そのために評価値と読み筋という二つの値を再帰的に渡しています。
また、探索ノード数や時間当たりのノード数なんかも慣例的に表示させているので同様の機能のためにglobalでノード数および時刻を保有しています。
今までは対局中GUIが味気ない感じでしたが、少しは探索過程が見られて楽しくなります。
---
追記：
先月山岡さんの法もアルファベータ法のサンプルを出されていましたので、ちょっと独自性を積むまでこちらは保留しておりました。
同様に御参考にしてみて下さい。こちらも実装はネガアルファ法の形です。
