Take the 2-minute tour ×

Hi! I'm making a chess engine and as i'd like to implement iterative deepening, i need to find the principal variation (the sequence of moves the engine thinks are optimal). But, i've not found any pseudocode examples in the web in python and since my alphabeta function is recursive, i'm really having a hard time understanding it.

Could you please give me some hints or a pseudocode example how can this be done? Thank you very much.

Here's my alpha beta function, which just returns the valuation of the move, not the move itself:

def alphaBeta(self, board, rules, alpha, beta, ply, player):
    """ Implements a minimax algorithm with alpha-beta pruning. """
    if not ply:
        return self.positionEvaluation(board, rules, player)

    move_list = board.generateMoves(rules, player)

    if not len(move_list):
        return self.mateCheck(rules, board, player, ply)

    for move in move_list:
        board.makeMove(move, player)
        current_eval = -self.alphaBeta(board, rules, -beta, -alpha, ply - 1, board.getOtherPlayer(player))
        board.unmakeMove(move, player)

        if current_eval >= beta:
            return beta

        elif current_eval > alpha:
            alpha = current_eval

    return alpha
share|improve this question
Why are you using an alpha-beta search in an IDS? an ABS would use a heuristic to prune. An IDS wants to go as far as it can before applying such a heuristic. If you prune with a heuristic in ABS, you don't search deeper in that branch. Then, this is not an IDS anymore –  inspectorG4dget Oct 7 '12 at 8:45
I'm sorry but i don't understand what you mean, maybe i myself didn't express what i intended to do understandably. What i'm trying to accomplish with the principal variation is to improve the move-ordering for my search. I don't see why i can't do this with alpha-beta pruning. Here's a better explanation: chessprogramming.wikispaces.com/Principal+variation –  geekkid Oct 7 '12 at 11:07
Maybe I'm mistaken, but this is what I meant: Look at the last row of the tree in your wiki. Those scores come from either 1. game won/lost 2. some heuristic. If they came from (1), go ahead and alpha-beta prune. But if they came from (2), when you deepen the horizon (last row), then you'll have to apply a new heuristic to determine whether each branch should still be explored/pruned. But then, you either don't prune (IDS and not ABS) or prune (ABS and not IDS) –  inspectorG4dget Oct 7 '12 at 11:48

1 Answer 1

Go with NegaMax searching. Following is an example:

 function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
        foreach child of node
            val := -negamax(child, depth-1, -β, -α, -color)
            {the following if statement constitutes alpha-beta pruning}
            if val≥β
                return val
            if val≥α
        return α

When called, the arguments α and β should be set to the lowest and highest values possible for any node and color should be set to 1.

(* Initial call *)
negamax(origin, depth, -inf, +inf, 1)

You can always do alpha beta pruning with negamax

P.S: I have already implemented a online chess platform. If you wish to have a reference: check Chesshunt

You can always see the client side code, but the actual moves and ches game logic is implemented on server side.

share|improve this answer
I'm sorry, but i don't think i quite follow you. I have already implemented a negamax search with alpha beta pruning. What i'm looking for is a way to extract the principal variation, so i can use it to improve my move ordering. –  geekkid Oct 7 '12 at 11:03
You can keep evaluation with every parent node? –  Anshu Oct 7 '12 at 11:23
I don't understand your question , could you please explain it better, my english and my understanding of programming idioms is quite limited :d . What i'm trying to do with my principal variation is this: chessprogramming.wikispaces.com/principal+variation –  geekkid Oct 7 '12 at 11:39

Your Answer


