alpha beta pruning

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

alpha beta pruning

Postby Folkert van Heusden » 19 Jul 2013, 10:04

Hello,

It is more than a year since I worked on my chess program and I'm trying to get back into it. I had an idea for paralyzing search trees so I got the sources of my chess program from svn!
While looking through the code I noticed that when I reach the bottom of the tree, I do evaluate(currentSide). So I invoke the evaluation seen from the side from who's move it is. I'm not entirely sure if that is correct. I did some googling but no example is explicit about it.
Given the alpha/beta pruning example from http://en.wikipedia.org/wiki/Alpha_beta_pruning, should I evaluate "seen from the root side point of view" or "seen from the side who's move it is at that ply"? I tried to reason it for myself but I did not come to a conclusion.


regards
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands

Re: alpha beta pruning

Postby Robert Pope » 19 Jul 2013, 14:54

Do it from the side on-move at the leaf, with a positive score for the side making the last move in the tree. Otherwise, when you take the max score, you will be choosing the worst score for the root if the color is different. You can get around that by sending a separate flag to keep track of whether to min or max, but you are adding extra complexity that way.

Actually, this is the difference in implementation between minimax and negamax. Nega- is much cleaner:
http://chessprogramming.wikispaces.com/Evaluation
Robert Pope
 
Posts: 39
Joined: 08 Apr 2006, 17:27

Re: alpha beta pruning

Postby Folkert van Heusden » 19 Jul 2013, 15:13

Robert,

Robert Pope wrote:Do it from the side on-move at the leaf


so, e.g. (pseudocode):

Code: Select all
int search(int depth, PlayerColor current_color)
{
     if (depth == 0)
          return evaluate(current_color);

     return search(depth - 1, to_opponent_color(current_color));
}


with a positive score for the side making the last move in the tree.


but that I don't understand.
If you mean the side making the last move, it would be

Code: Select all
int search(int depth, PlayerColor root_color, PlayerColor current_color)
{
     if (depth == 0)
          return evaluate(to_opponent_color(root_color));

     return search(depth - 1, to_opponent_color(current_color));
}


right?

Otherwise, when you take the max score, you will be choosing the worst score for the root if the color is different.


Code: Select all
int search(int depth, PlayerColor root_color, PlayerColor current_color)
{
     if (depth == 0)
          return evaluate(root_color);

     return search(depth - 1, to_opponent_color(current_color));
}


?

You can get around that by sending a separate flag to keep track of whether to min or max, but you are adding extra complexity that way.


Yeah, well, in the current fase of the program that is not my focus. First get it to work, then optimize.

Actually, this is the difference in implementation between minimax and negamax. Nega- is much cleaner:
http://chessprogramming.wikispaces.com/Evaluation


Is it also faster?


Thanks!

Folkert.
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands

Re: alpha beta pruning

Postby Robert Pope » 19 Jul 2013, 17:13

I would guess the difference in speed is pretty similar, but the Nega- version should be slightly faster. Instead of passing color up the stack in 1,000,000 calls to Search(), you do a check once in Evaluate() at each leaf and do "return Score" or "return -Score".

If you look at the source for TSCP, it should be pretty easy to see the standard way to handle it.
Robert Pope
 
Posts: 39
Joined: 08 Apr 2006, 17:27

Re: alpha beta pruning

Postby Folkert van Heusden » 19 Jul 2013, 18:59

Robert Pope wrote:I would guess the difference in speed is pretty similar, but the Nega- version should be slightly faster. Instead of passing color up the stack in 1,000,000 calls to Search(), you do a check once in Evaluate() at each leaf and do "return Score" or "return -Score".
If you look at the source for TSCP, it should be pretty easy to see the standard way to handle it.


I'll look at it.

And regarding that evaluation: which of the colors should I use? See my previous reply.


regard
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands

Re: alpha beta pruning

Postby Robert Pope » 19 Jul 2013, 19:56

Use the color that is on-move at the time of evaluation. Then whether you return Evaluate() or -Evaluate() depends on your specific coding, but it will be obvious if it is wrong. (e.g. a one-ply search with a mobility and material evaluation would come up a2 instead of e4)
Robert Pope
 
Posts: 39
Joined: 08 Apr 2006, 17:27

Re: alpha beta pruning

Postby Folkert van Heusden » 19 Jul 2013, 22:31

Robert Pope wrote:Use the color that is on-move at the time of evaluation. Then whether you return Evaluate() or -Evaluate() depends on your specific coding, but it will be obvious if it is wrong. (e.g. a one-ply search with a mobility and material evaluation would come up a2 instead of e4)


Hmmm.
If I pick the root side as color, then only then something sensible comes out of it:

color/depth/move
b/1 e7-e6
b/4 e7-e6
b/5 e7-e5
w/1 e2-e3
w/4 e2-e3
w/5 e2-e4

using the evaluation-time-color:

color/depth/move
b/1 g8-h6
b/4 e7-e5
b/5 b8-c6
w/1 g1-h3
w/4 e2-e4
w/5 g1-f3
User avatar
Folkert van Heusden
 
Posts: 29
Joined: 17 May 2007, 13:21
Location: gouda, netherlands


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Google [Bot] and 3 guests

cron