Move ordering for chess engine

Question

Part 3 of my python programming project. Find it here.

Since the last post, I've managed to get work out the transposition tables and started creating the move ordering function.

The move function starts by checking if there's a move in the opening books, if there isn't one then it executes the move ordering function and lastly if there was no move found, it calculates the best move in the position.

This is what I have so far:

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

The orderMoves function checks for 3 different things in the current position:

negamax function - searches the transposition tables
Moves that lead to checkmate
Captures that win material

.

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

The negamax function works via storing and looking up previously stored hashes.

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

There's probably a better way of implementing this function, but this was the best I could manage. After testing this for a few hours of running the code, the results were the same as when I didn't have move ordering. 7 out of the 24 test positions were correct.

What changes could I make to get a cleaner implementation and make it work properly?

score 1 · Answer 1 · answered Dec 08 '21 at 14:10

Great question. The Andoma Python chess engine uses this move ordering function in movegeneration.py, that I've also use for my 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)

Move ordering for chess engine

1 Answers1