4

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"?

I thank you in advance for any clarifications or advice on improvements. Here is 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
  • 1
    Similar question here may help – Michael West Jan 8 at 18:08
  • Just a note: you've got repeating code under if and else. You can parameterize it and abstract into a function - will make it easier to work with. – postoronnim Jan 9 at 23:44
  • I know, thanks :) I think the reduced one is called negamax. But I am too lazy to change and try to get that to work with alpha-beta. – eligolf Jan 10 at 10:20
  • One good strategy is iterative deepening search, where you do the minimax algorithm at depth 1, then depth 2, etc, until running out of the time limit for thinking. On each iteration, you get an idea of which branches to spend more time on, since the resulting positions at a lesser depth seem good. – Inertial Ignorance Jan 11 at 8:48
2

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.

|improve this answer|||||
  • 1
    Thank you, that is what I suspected (and feared). – eligolf Jan 9 at 5:53
  • 1
    I'm not sure what type of pruning @yobamamama is refering to, but he seems to be implying that there is some type of trade off regarding alpha/beta pruning. This is false. There is no loss of information when transitioning from MinMax to alpha/beta pruning. See my answer. – Noah Caplinger Jan 11 at 15:03
  • I was trying to say the trade off is when where to prune. – yobamamama Jan 11 at 15:58
  • 1
    If you use alpha/beta pruning, there's no trade off. You're correct for null and late move pruning, but this question specifically asked about alpha/beta. – Noah Caplinger Jan 11 at 16:35
  • I defer to your answer. All is know is how I pruned way way back when long long ago. – yobamamama Jan 11 at 16:58
3

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.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.