Sign in to follow this  

Gain of Alpha Beta prunning

This topic is 4733 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

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 this post


Link to post
Share on other sites
Guest Anonymous Poster
NC here.


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

Share this post


Link to post
Share on other sites
Thanks for your answer, NC.
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

This topic is 4733 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this