Minimax with alpha-beta pruning for chess

Question

I am creating a chess AI using the minimax method with alpha-beta pruning. I am trying to understand how the alpha-beta pruning works, but I can't get my head around it when it comes to chess where you set a certain search depth.

How do minimax with alpha-beta solve sacrificing a piece for advantage 2-3 moves ahead? Won't it just look at the position at the sacrifice and immediately discard that branch as bad, therefore missing the good "sacrifice"?

My code so far:

def minimax(board, depth, alpha, beta, maximizing_player):

    board.is_human_turn = not maximizing_player 

    children = board.get_all_possible_moves()

    if depth == 0 or board.is_draw or board.is_check_mate:
        return None, evaluate(board)

    best_move = random.choice(children)

    if maximizing_player:
        max_eval = -math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child)
            current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
            if current_eval > max_eval:
                max_eval = current_eval
                best_move = child
            alpha = max(alpha, current_eval)
            if beta <= alpha:
                break
        return best_move, max_eval

    else:
        min_eval = math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child)
            current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
            if current_eval < min_eval:
                min_eval = current_eval
                best_move = child
            beta = min(beta, current_eval)
            if beta <= alpha:
                break
        return best_move, min_eval

Answer 1

No. You have to go to the end of that branch to decide if it is bad.

pruning is done to help make the problem computationally feasible. But there are risks that you might have eliminated a better branch. That depends how far out you look and how good your algorithm is to assess the position before you trim it.

Cutting anything after only a few moves will lead to poor results in many cases. The farther you go the better the results.

Perfection is not possible.

You have to trade off time, complexity, and other factors to determine your optimum approach to deciding which branches, and how far you will go down that rabbit hole searching for the answer.

You can do everything at a small depth. You can do a few things at enormous depth. The best approach is in the middle somewhere , where you do enough branches far enough.

Answer 2

In alpha/beta pruning, you only prune when further search cannot affect the outcome. In particular this means there will be no loss of information when you transition from MinMax to alpha/beta. There is only upside to alpha/beta (in contrast to other, more aggressive pruning methods).

The fundamental idea of alpha/beta pruning is that once you discover a branch to be inferior, there's no sense in figuring out exactly how inferior.

Here's how we'll do it: (When not using NegaMax) You can think of alpha as the maximum of all white (maximizing) ancestor's max_eval, and beta as the minimum of all black (minimizing) ancestor's min_eval.

Now, say you're searching a white node, w, and you discover the max_eval to be larger than beta. White is maximizing, so we know that the value of w can only go up. Then we are guaranteed that the value of w is larger than beta.

This means that this (white) node must have a (black) ancestor with min_eval smaller than the value of w, by definition of beta. Let's think more about this: because that black ancestor has min_eval smaller than w, it is guaranteed the option of a move with value min_eval. But w has value larger than min_eval. That black ancestor will always choose the lower one, so it doesn't matter how much larger w is. From the perspective of that black ancestor, w and w+100 are the exact same: worse.

Then, there's no reason to continue searching w: it can't possibly affect the outcome of the algorithm, so we prune the tree.

This is the only situation in which the alpha/beta algorithm prunes: when the outcome of further search cannot possibly affect the result.

---

If all of that is confusing, I really don't blame you. This is a topic that deserves lots of pictures and a few pages of explanation, not a few paragraphs. imo there aren't any great resources online, but if you (or anyone else) would like to contact me, I have something that might be helpful.