Alpha-Beta cutoff

Question

I understand the basics of this search, however the beta cut-off part is confusing me, when beta <= value of alphabeta I can either return beta, break, or continue the loop.

• return beta doesn't seem to work properly at all, it returns the wrong players move for a different state of the board (further into the search tree)

• break seems to work correctly, it is very fast but it seems a bit TOO fast

• continue is a lot slower than break but it seems more correct...I'm guessing this is the right way but pseudocode on google all use 'break' but because this is pseudocode I'm not sure what they mean by 'break'

Answer 1

Just for the fun of it I'm going to guess that you're talking about Minimax with Alpha-Beta cutoff, where

ALPHA-BETA cutoff is a method for reducing the number of nodes explored in the Minimax strategy. For the nodes it explores it computes, in addition to the score, an alpha value and a beta value.

Here is a page that describes this method and also provides a link to a C program that implements this method. Hopefully something here helps you with your problem, if I'm totally off with my guess please give more detail in your question.

    function MINIMAX(N) is
    begin
       if N is a leaf then
           return the estimated score of this leaf
       else
           Let N1, N2, .., Nm be the successors of N;
           if N is a Min node then
              return min{MINIMAX(N1), .., MINIMAX(Nm)}
           else
              return max{MINIMAX(N1), .., MINIMAX(Nm)}
      end MINIMAX;

Answer 2

Beta cutoffs occur when the branch you are currently searching is better for your opponent than one you've already searched. It was once explained to me as follows:

suppose are fighting with your enemy, and you consider a number of your choices.

After fully searching the best possible outcome of your first choice (throwing a punch), you determine the result is your opponent will eventually poke you in the eye. We'll call this beta... the best your opponent can do so far. Obviously, you would like to find a result that does better.

Now we consider your next option (running away in disgrace). When exploring your opponents first possible reply, we find that the best possible outcome is you are shot in the back with a gun. This is where a beta cutoff is triggered... we stop searching the rest of your opponents moves and return beta, because we really don't care if you find in searching his other replies he can also nuke you... you would already opt for the poke in the eye from the previous option.

Now specifically what this means is your program should return beta... if it doesn't work, you should compare to an alpha-beta search algorithm elsewhere.