python - 国际象棋引擎的移动顺序

Question

我的 Python 编程项目的第 3 部分。找到它here .

自上一篇文章以来，我已经设法计算出换位表并开始创建移动排序函数。

着法函数首先检查开局书籍中是否有着法，如果没有则执行着法排序函数，最后如果没有找到着法，则计算该位置的最佳着法。

这是我目前所拥有的:

def domove(depth):
try:
    move = chess.polyglot.MemoryMappedReader("C:/Users/bruno/Desktop/chess/books/pecg_book.bin").weighted_choice(board).move()
    move = chess.polyglot.MemoryMappedReader("C:/Users/bruno/Desktop/chess/books/human.bin").weighted_choice(board).move()
    move = chess.polyglot.MemoryMappedReader("C:/Users/bruno/Desktop/chess/books/computer.bin").weighted_choice(board).move()
    movehistory.append(move)
    return move
except:
    orderMoves(move)
    bestMove = move
    movehistory.append(bestMove)
    return bestMove

finally:
    bestMove = chess.Move.null()
    bestValue = -9999
    alpha = -10000
    beta = 10000
    for move in board.legal_moves:
        make_move(move)
        boardValue = -alphabeta(-beta, -alpha, depth-1)
        if boardValue > bestValue:
            bestValue = boardValue
            bestMove = move
        if( boardValue > alpha ):
            alpha = boardValue
        unmake_move()
    movehistory.append(bestMove)
    return bestMove

orderMoves 函数在当前位置检查 3 个不同的东西:

1. negamax 函数 - 搜索转置表
2. 导致将死的 Action
3. 赢得素材的捕获

.

def orderMoves(board, bestValue, material, move):
try:
    negamax(board)
    bestMove = move
    movehistory.append(bestMove)
    return bestMove
    
except:    
    for move in board.legal_moves:
        if board.is_checkmate():
            bestValue
    return bestValue
    
finally:
    for move in board.legal_moves:
        if move == board.is_capture():
            if newmaterial >= material:
                newmaterial = material
        return bestValue

negamax 函数通过存储和查找以前存储的哈希值来工作。

def negamax(node, depth, alpha, beta, score, bestValue):
alphaOrig = alpha

EXACT = score
LOWERBOUND = alpha
UPPERBOUND = beta

## Transposition Table Lookup; node is the lookup key for ttEntry
ttEntry = transpositionTableLookup(node)
if ttEntry.is_valid is True :
    if ttEntry.depth >= depth:
        if ttEntry.flag == EXACT :
            return ttEntry.value
        elif ttEntry.flag == LOWERBOUND:
            alpha = max(alpha, ttEntry.value)
        elif ttEntry.flag == UPPERBOUND:
            beta = min(beta, ttEntry.value)

    if alpha >= beta:
        return ttEntry.value

elif depth == 0 or node == terminal_node():
    return bestValue

childNodes = domove(node)
childNodes = orderMoves(childNodes)
bestValue = -99999

for child in childNodes:
    bestValue = max(bestValue, -negamax(child, depth - 1, -beta, -alpha))
    alpha = max(alpha, bestValue)
    if alpha >= beta:
        break

##Transposition Table Store; node is the lookup key for ttEntry 
    ttEntry.value = bestValue
    if bestValue <= alphaOrig:
        ttEntry.flag = UPPERBOUND
    if bestValue >= beta:
        ttEntry.flag = LOWERBOUND
    else:
        ttEntry.flag = EXACT
        ttEntry.depth = depth   
        transpositionTableStore(node, ttEntry)
        return bestValue

可能有更好的方法来实现此功能，但这是我能做到的最好的方法。在运行代码测试几个小时后，结果与我没有移动排序时的结果相同。 24个测试位置中有7个是正确的。

我可以做哪些更改以获得更清晰的实现并使其正常工作？

Answer 1

好问题。Andoma Python chess engine在 movegeneration.py 中使用此移动排序函数，我也将其用于我的 Ramses Chess engine (Python) :

def get_ordered_moves(board: chess.Board) -> List[chess.Move]:
    """
    Get legal moves.
    Attempt to sort moves by best to worst.
    Use piece values (and positional gains/losses) to weight captures.
    """
    end_game = check_end_game(board)

    def orderer(move):
        return move_value(board, move, end_game)

    in_order = sorted(
        board.legal_moves, key=orderer, reverse=(board.turn == chess.WHITE)
    )
    return list(in_order)