# 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.

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

_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 on other sites
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 on other sites
Quote:
 Original post by gfrommerYour 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 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

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5
JoeJ
14

• 14
• 10
• 23
• 9
• 32
• ### Forum Statistics

• Total Topics
632631
• Total Posts
3007534
• ### Who's Online (See full list)

There are no registered users currently online

×