alpha beta pruning

[Folkert van Heusden]

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

[Robert Pope]

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

[Folkert van Heusden]

Robert,

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.

[Robert Pope]

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.

[Folkert van Heusden]

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

[Robert Pope]

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)

[Folkert van Heusden]

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