# Gain of Alpha Beta prunning

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

## Recommended Posts

Hi everybody. I have read, that using alpha-beta pruning if one would test the best move first, one would have to only examine the square root number of nodes in the minimax tree (too bad that I do not remember where I read this). OK, so if all nodes would have the value "0", every move would be the best. I wanted to test this and wrote the following test-programm (using NegaMax from http://www.seanet.com/~brucemo/topics/alphabeta.htm).
int SearchedNodes=0;
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
{
SearchedNodes++;
return 0;//Every Node has the value 0
}

int i=0;
while (i<1700)
{
i++;
int val = -AlphaBeta(depth - 1, -beta, -alpha);
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}

int main()
{
printf("Doing a 2ply search...\n");
//Sinve every node has the value 0, we can take -5 for -INFINITY and 5 for INFINITY
AlphaBeta(2,-5,5);
printf("Took %i nodes.\n",SearchedNodes);
printf("Doing a 3ply search...\n");
SearchedNodes=0;
AlphaBeta(3,-5,5);
printf("Took %i nodes.\n",SearchedNodes);
printf("Doing a 4ply search...\n");
SearchedNodes=0;
AlphaBeta(4,-5,5);
printf("Took %i nodes.\n",SearchedNodes);


This simulates (or is supposed to simulate) a game with 1700 possible moves on every Node. Output: Doing a 2ply search... Took 3399 nodes. Doing a 3ply search... Took 2891699 nodes. Doing a 4ply search... Took 5779999 nodes. The 2ply search looks fine to me. But the 3ply seatch ... should it not be in the area of sqrt(1700*1700*1700) ~ 70100 ? Is my source of information wrong? Or did I misunderstand something completly? What is wrong? Thanks!!! Nathan

##### Share on other sites
NC here.

It is wrong, because all nodes are of the same value. That is a problem.

##### Share on other sites
OK, then I give the nodes different values, the first will be the best:

int SearchedNodes=0;int AlphaBeta(int depth, int alpha, int beta){  if (depth == 0)    {      SearchedNodes++;      //The Higher "Searched Nodes" is, the lower the value of the nodes get      return 1000000000-SearchedNodes;    }  int i=0;  while (i<1700)    {      i++;      int val = -AlphaBeta(depth - 1, -beta, -alpha);      if (val >= beta)        return beta;      if (val > alpha)        alpha = val;    }  return alpha;}int main(){  printf("Doing a 2ply search...\n");  AlphaBeta(2,-1000000000,1000000000);  printf("Took %i nodes.\n",SearchedNodes);  printf("Doing a 3ply search...\n");  SearchedNodes=0;  AlphaBeta(3,-1000000000,1000000000);  printf("Took %i nodes.\n",SearchedNodes);  printf("Doing a 4ply search...\n");  SearchedNodes=0;  AlphaBeta(4,-1000000000,1000000000);  printf("Took %i nodes.\n",SearchedNodes);}

Output:

Doing a 2ply search...
Took 3399 nodes.
Doing a 3ply search...
Took 5778300 nodes.
Doing a 4ply search...
Took 8666600 nodes.

It even got worse!!!
Help!
(and thanks for any help)
Nathan

##### Share on other sites
LonelyStar,
1700*1700*1700*1700 > 1000000000
and your return value falls out of alpha-beta boundaries ...

Also, every two nodes you are at a min level, so your return value should alternate

return 100000000-SearchedNodes; // for max levels

with

return SearchedNodes; // for min levels

to simulate perfect ordering moves.

Try with 100 (instead of 1700) with your actual code to a level 7 or higher. You will notice one level increases by a factor of 100 and the next level does not increase (just a little bit, no order of magnitude). This shows up that good ordering adds almost nothing to the number of nodes, while bad ordering adds a factor of branching.

Hope it helps

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 13
• 76
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632968
• Total Posts
3009584
• ### Who's Online (See full list)

There are no registered users currently online

×