Jump to content
  • Advertisement
Sign in to follow this  
telengard

AB pruning sanity check

This topic is 3725 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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;
}

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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&gl=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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!