I've had AB pruning implemented for a while now and I'm wondering if I really have it right. I've seen about 4 different implementations on the web (not style but actual behavior) and I'd like to be sure I'm doing it correctly. I also have searched the forums and the book I bought does it using negamax so it confused me a little. I'm not doing negamax since the game I'm doing this for does not have alternating turns. The function below is called from a higher level for each top level action of the tree w/ alpha set to MINUS_INFINITY and beta to PLUS_INFINITY. The 3 things I'm wondering is if the return value is correct when breaking out of the loop, are the pruning conditions correct (both the comparison and the use of >= and <= instead of < or >) and if you still set alpha or beta if the pruning condition is hit (some implementations I've seen do, some don't). Any insight would be greatly appreciated! (I've trimmed out a lot of the non-relevant code, debugging stuff etc)

static int
alphabeta_value( game_state* _game_state, ai_player* _ai, int _depth, int _start_turn, phase_id _start_phase, int _alpha, int _beta )
{
    int ret = 0;

    if ( _depth == _ai->max_tree_depth || _game_state->is_game_over() )
        return evaluate_board( _game_state, _ai );

    player_actions* actions = _game_state->get_ai_actions();
    player* a_player        = actions->action_list[0]->for_player;

    vector<action*>::iterator iter;
    vector<action*>::iterator iter_b = actions->action_list.begin();
    vector<action*>::iterator iter_e = actions->action_list.end();

    // sort_actions( _game_state, actions, _ai );

    for ( iter  = iter_b; 
          iter != iter_e;
          iter++ )
    {
        action* a = *iter;

        int undo_cookie;
        _game_state->execute_action( a, actions, &undo_cookie );

        bool stop_search = _game_state->has_reached_expiration( _start_turn, _start_phase );
        int val          = 0;

        if ( !stop_search )     /* go deeper */
            val = alphabeta_value( _game_state, _ai, _depth + 1, _start_turn, _start_phase, _alpha, _beta );

        else
            val = evaluate_board( _game_state, _ai );

        pop_state( _game_state, undo_cookie );

        if ( a_player == _ai ) 		//  maximize
        {
            if ( val > _alpha )		//  better score for MAX player
                _alpha = val;

            if ( _alpha >= _beta )
            {
		_ai->nodes_pruned++;
		break;
            }
        }

        else				//  minimize
        {
            if ( val < _beta )     	//  better score for MIN player
                _beta = val;

            if ( _beta <= _alpha )
            {		
		_ai->nodes_pruned++;
		break;
            }
        }
    }

    if ( a_player == _ai )
        ret = _alpha;

    else
        ret = _beta;

    return ret;
}

Your alpha-beta looks good... I can't speak to the specifics of about alpha-beta because I am looking for the same specific information that you are. I do have one question about your code... what does this line do?

bool stop_search = _game_state->has_reached_expiration( _start_turn, _start_phase

And why do you have it calling your scoring function when stop_search is true? Why not just call alphabeta_value again and have the termination code at the top handle the end-node score?

if ( _depth == _ai->max_tree_depth || _game_state->is_game_over() )
return evaluate_board( _game_state, _ai );


I believe the >= and <= are the proper way to go with alpha-beta pruning. Exactly why >= and <= are better I'm not sure... but if anything they will cause more cutoffs then < and > alone.

Quote: Original post by gfrommer
Your alpha-beta looks good... I can't speak to the specifics of about alpha-beta because I am looking for the same specific information that you are. I do have one question about your code... what does this line do?

bool stop_search = _game_state->has_reached_expiration( _start_turn, _start_phase

And why do you have it calling your scoring function when stop_search is true? Why not just call alphabeta_value again and have the termination code at the top handle the end-node score?

if ( _depth == _ai->max_tree_depth || _game_state->is_game_over() )
return evaluate_board( _game_state, _ai );


I believe the >= and <= are the proper way to go with alpha-beta pruning. Exactly why >= and <= are better I'm not sure... but if anything they will cause more cutoffs then < and > alone.

Hi there,

That line handles something specific to the type of game the AI is for. I was running into an issue with just having a pure depth cutoff allowed certain branches to get further into the game turn and favoring it so I had to put in an additional cutoff for a phase boundary so evaluations were apples to apples, it still isn't perfect unless I set the max_tree_depth very high to ensure the phase is cutoff first. The game is very similar to Magic the Gathering. Without the change the AI was favoring the equivalent of a "pass" so it could get to a further point in the game and score points.

That code could be put in the AB routine, I just have a lot of debugging stuff done in that area so it was easier to keep it out of the AB routine (I removed a bunch of non-essential code from my original post).

~telengard

Here's an example of one I found on the web that seems to contradict other implementations I've seen.

http://www.websters-online-dictionary.org/al/alpha-beta+pruning.html

and another that is different in some ways:

http://64.233.169.104/search?q=cache:D2zOEmioUMMJ:marathon.csee.usf.edu/~ryang/AI%2520Tutorial/tutorial6.doc+alpha+beta+pruning+minimax&hl=en&ct=clnk&cd=20≷=us

Quite confusing. :) If I had alternating turns I'd definitely be using negamax since 99% of stuff I see on the web is done that way.

I'm pretty sure I'm *not* doing it right in the above code. I went back to pure minimax and compared to running with and without pruning and I get different results, which if I understand correctly, should not happen.

~telengard