1file match（仮）の参考資料４（ネガアルファ法）

1file matchというのは下記の経緯で私が考案した初級者歓迎部門の新設案です。

思い付きで弄ってましたが短いサンプルプログラムを作るのは好きな方でプチ実験的なものは多数作っています。

前回、駒得評価関数を実装しましたがその際Min-Max法のサンプルは沢山あるとコメントしてますが適当なものを探しておきました。

Algorithms with Python / ミニマックス法 (nct9.ne.jp)

参考文献に松原先生の著書がある辺りがミソです。

で、自分で実装したものが以下です。

MIN_VALUE = -32000
MAX_VALUE = 32000
SEARCH_DEPTH = 4
 
# 参考：ネガアルファ法 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, ""
    #
    value = alpha # MIN_VALUEでもいいんだけど
    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, pv = negaalpha(depth - 1, board, -beta, -value) # depthを一つ減らしてαβを符号を変えて入れ替えるのがミソ
            v = -v
        board.pop() # 将棋はループ用に手戻しするが，ゲームによっては盤面コピーして毎回捨てるほうが速い場合も
        if value < v: # ネガマックス法 : 大きな値を選ぶ
            value = v
            move = m
            pvm = pv
            if depth == SEARCH_DEPTH:
                lap_time = time() - start + 1e-6
                print('info nps {} time {} nodes {} score cp {} pv {}'.format(
                    int(nodes / lap_time), int(lap_time * 1000), nodes, value, move_to_usi(move)+" "+pvm), flush=True)
        if value >= beta: break # ネガアルファ法 : 規定値外があれば打ち切る
    return value, move_to_usi(move)+" "+pvm

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()
    value, move = negaalpha(SEARCH_DEPTH, board, MIN_VALUE, MAX_VALUE)
    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が味気ない感じでしたが、少しは探索過程が見られて楽しくなります。

---

追記：

先月山岡さんの法もアルファベータ法のサンプルを出されていましたので、ちょっと独自性を積むまでこちらは保留しておりました。

同様に御参考にしてみて下さい。こちらも実装はネガアルファ法の形です。

tadaoyamaoka.hatenablog.com