国际象棋引擎的着法排序

Question

我的Python编程项目的第三部分。在这里找到它：这里。

自上次发布以来，我已经处理了置换表，并开始创建移动排序函数。

移动函数首先检查是否在开局书中有棋步可走，如果没有，则执行移动排序函数；最后，如果没有找到可行的棋步，则计算当前局面下的最佳移动。

目前为止，我已经完成了以下内容:

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函数检查当前位置的三件不同的事情：

1. negamax函数 - 搜索置换表
2. 导致将死的着法
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个是正确的。

我应该做哪些改动，才能让实现更简洁并正常工作呢？

- Bruno

Answer 1

好问题。 Andoma Python棋引擎 在 movegeneration.py 中使用了这个移动排序函数，我也在我的Ramses Chess引擎（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)

- LittleCoder