A few general questions...

[voyagerOne]

1. How can you get an exact score for each root move? (So you can sort them for the next iteration)
The obvious way is to reset alpha beta to infinity window for each root move, however...this will slow down the search quite a bit...

2. When you do a null widow search and it failed so you have to re-search with a bigger window. Does research mean to go back to the first root move?

3. When implementing SEE, don't you have to considered discover checks? (i.e. pawn can't capture Queen because King is enprise)

Thanks in advance!

Bill
mytopcoder.com/gmol

[micron]

1. How can you get an exact score for each root move? (So you can sort them for the next iteration)
The obvious way is to reset alpha beta to infinity window for each root move, however...this will slow down the search quite a bit...

You might do that for preliminary ordering of the root moves, for instance a full window depth 0 search allows you to sort on scores very quickly. Then in iterative deepening you merely shift the best move after each iteration to the head of the list, for the next iteration, without sorting.

2. When you do a null widow search and it failed so you have to re-search with a bigger window. Does research mean to go back to the first root move?

No. Just re-search the move that failed.

3. When implementing SEE, don't you have to considered discover checks? (i.e. pawn can't capture Queen because King is enprise)

That would make SEE unbearably slow. You have to accept that SEE is an imperfect tool.

[Evert]

1. How can you get an exact score for each root move? (So you can sort them for the next iteration)
The obvious way is to reset alpha beta to infinity window for each root move, however...this will slow down the search quite a bit...

You can use an aspiration window, but basically yes, that's how you do it. And yes, it will slow down the search a lot.
It's generally also not worthwhile, in the sense that all you want to know is the best move (maybe best 2-3 moves in the case of analysis), of the rest you only need to know that they're worse.

2. When you do a null widow search and it failed so you have to re-search with a bigger window. Does research mean to go back to the first root move?

I use PVS. When I search a move with a null-window and/or with reduced depth and it does not fail low, I research without reductions and with the full window (if this is a PV node; otherwise the top window is already a null window and there's no point). This is to "confirm" the fail high.
Actually, I see that I probably misunderstood what you asked. No, you don't go back to the first move. You only research the current move. If you think about it, you already know the exact score for the first move, it will not (should not!) change if you research with a different window.

3. When implementing SEE, don't you have to considered discover checks? (i.e. pawn can't capture Queen because King is enprise)

You can do pin detection in SEE. It will be more accurate, but it will also be slower. The question is whether it's worth the slowdown, which is something you have to test.
You should then perhaps also consider that knight takes defended pawn may be a losing capture, but because of a discovered check the other side can't take the knight. Or not; I have a feeling this sort of thing doesn't occur often enough to justify the extra cost in computation time.

[Don]

1. How can you get an exact score for each root move? (So you can sort them for the next iteration)
The obvious way is to reset alpha beta to infinity window for each root move, however...this will slow down the search quite a bit...

You are going to slow down the search regardless of what you do.

If you are using PVS search, you search only the first move with an infinite window. If you want correct scores you can relax but not "open all the way" the window for the next set of moves. A very simple procedure is to search the second move with a small window around the best score found so far and research just that move if it fails in either direction. Since you EXPECT each move to be weaker than the previous you do not need to relax it on the positive side. Of course if it fails you research it as you would in PVS.

In this way you are still essentially using the PVS framwork, but instead of search with zero width window you just search with "small width window."

You might use 25 as your margin as a first attempt - to be tuned later:

alpha-25, alpha

or in negamax framework:

sc = -search( -alpha, -(alpha-25), ... )


It really makes no sense to do this if you just want performance because this will slow you down substantially, but it might pay off to do this just for the first 2 or 3 iterations to get a good move ordering. You might also do it if you are using multiPV of course.

2. When you do a null widow search and it failed so you have to re-search with a bigger window. Does research mean to go back to the first root move?

3. When implementing SEE, don't you have to considered discover checks? (i.e. pawn can't capture Queen because King is enprise)

Thanks in advance!

Bill
mytopcoder.com/gmol

[voyagerOne]

Thanks all for your input!

So a few more things to clear the cobwebs for me...

When I hear the word "research" does that mean to research the current root node?

Let say there are 12 root moves... and we get a fail high on root move #4. So we start over our search again at move #4 resting all its children to their 1st move with the adjusted window.....correct?


Why is the null window set to alpha, alpha -1.... why not just alpha, alpha?

Why do one use this logic to test if it failed high score > alpha && score < beta? What's wrong with just score>alpha?

[hgm]

Let say there are 12 root moves... and we get a fail high on root move #4. So we start over our search again at move #4 resting all its children to their 1st move with the adjusted window.....correct?

You re-search move #4. Presumably this will produce a score > alpha (if there was no search instability), so you will increase alpha, and search moves 5-12 with a null window at this increased alpha.

Why is the null window set to alpha, alpha -1.... why not just alpha, alpha?

Because in the usual meaning alpha and beta are the first values on either side outside the window. Setting both to alpha would be inconsistent, and would lead to an immediate cutoff in any search you start with this such a window. (Because you actually should have taken the cutoff in the parent node already, as you increased alpha >= beta.

Why do one use this logic to test if it failed high score > alpha && score < beta? What's wrong with just score>alpha?

When the null-window score already returns a value >= beta, there is no need to research with a larger window. The exact same tree would be searched, returning the exact same score >= beta, causing a cutoff. So you might as well take the cutoff immediately, without first duplicating all the work.

[Don]

Thanks all for your input!

So a few more things to clear the cobwebs for me...

When I hear the word "research" does that mean to research the current root node?

Typically you do a "test search" sometime called a scout search to determine if a move is as good as the one you currently consider best. It does not have to be just the root move, it is done recursively at just about any node.

if the search fails low, you don't care and you can move on because you have "proved" that it sucks.

If the search fails high, it means that the move is BETTER than you expected and you must search it again but with a larger window. You could use infiinte here since you don't really know how good it is. Generally the score returned can be viewed as a lower bound so you can start with alpha set to that score, but beta could be anything but you might want to just search it -inf +inf until it's all debugged before getting too clever.

Let say there are 12 root moves... and we get a fail high on root move #4. So we start over our search again at move #4 resting all its children to their 1st move with the adjusted window.....correct?

Yes. Only move 4 is searched again with an adjusted window.

Why is the null window set to alpha, alpha -1.... why not just alpha, alpha?

It's the interval between the 2 scores that is important. 18, 19 has NO integers between 18 and 19 so it is "zero width"

Also, beta should ALWAYS be above alpha or you have a bug. It should never be less or equal.

And finally, a zero width window ALWAYS fails, that is why it's often called a "scout" search, it's only purpose is to find out which side of the window the score is, and usually you are just trying to verify that the position is not as good.

Don't forget that a score >= beta is a failure - a common bug is to say:

if (score > beta) { do something ... }

That's a bug and should be:

if (score >= beta)

It's the same with alpha:

if (score < alpha) { is a bug }

if (score <= alpha) { fail low }

With negamax, just think of it without negamax first, then swap positions, negate and use parenthesis:

sc = -search( -beta, -alpha )

with window think like this:

sc = search( alpha-5, alpha + 5)
then rewrite it to:

sc = -search( -(alpha+5), -(alpha-5) );

which is equivalent to:

sc = -search( -alpha - 5, -alpha + 5 );


To answer your question specifically, why alpha, alpha -1?

alpha is the score that you must beat to have an impact on the tree, often it's the best move at this node. After searching the first move, you EXPECT all the others to be worse, so you want to set up a window that will fail low unless you improve on alpha. It's not good enough to find another move that is equal to alpha since it's just a waste of time so you must add 1 point.

So your window should be: alpha, alpha+1 because sc <= alpha is a fail low. To turn this into negamax you search:

sc = -search( -(alpha+1), -alpha );

which is equivalent to:

sc = -search( -alpha - 1, -alpha );

Why do one use this logic to test if it failed high score > alpha && score < beta? What's wrong with just score>alpha?

I think that was answered, but fail high is just sc >= beta. If you are not using a zero width window you want to know if the score returned is BETWEEN the 2 bounds so the test would be:

sc > alpha && sc < beta

Because

sc == alpha is a fail low and sc == beta is a fail high.

Always remember, it's the scores BETWEEN alpha and beta that matter, not alpha and beta themselves.

By the way, if alpha and beta are the same, it's logically inconsistent because if a score is returned that is equal to alpha AND beta then it has failed high AND it has failed low - which is illogical.

[voyagerOne]

Thank you H.G. and Don for the quick and concise reply! This will help me tremendously.

Last quick questions...

Due to odd-even effect: I usually get a delta around 0.25. To correct this should I simply add a tempo penalty to even out the odd-even scores?

Will this be beneficial for null/asp windows, null moves, razoring, etc...or will it not matter?

Also, how much can I expect to save once I implement PVS search properly?

Right now my Engine can only go up to Depth 8 in a reasonable amount time. I am just using plain alpha/beta pruning only. No null moves, futility, razoring, TT, etc.

You can see for yourself: www.mytopcoder.com/gmol

Thanks so much in advance!

[Don]

Thank you H.G. and Don for the quick and concise reply! This will help me tremendously.

Last quick questions...

Due to odd-even effect: I usually get a delta around 0.25. To correct this should I simply add a tempo penalty to even out the odd-even scores?

That's what we do. Be conservative with this tempo but it should give you a small rating boost if you pick the right value. Use a smaller value in the endgame.

Will this be beneficial for null/asp windows, null moves, razoring, etc...or will it not matter?

For komodo it's built in to the evaluation function so we don't think about it. It should give you a minor speed boost.

Also, how much can I expect to save once I implement PVS search properly?

Save over what? Pure alpha beta?

I am guessing from memory, but it might be something like 30% speedup.

Right now my Engine can only go up to Depth 8 in a reasonable amount time. I am just using plain alpha/beta pruning only. No null moves, futility, razoring, TT, etc.

You can see for yourself: www.mytopcoder.com/gmol

Thanks so much in advance!

The 2 BIG search things are futility pruning and null move pruning. Both are very simple to implement.

TT should probably be the next thing, but that is complicated and hard to get right. The issue with TT is that it's not just a simple hash table - the context matters a lot and the context is the alpha and beta window when the node was searched. Depth is also part of the context.

A very good treatment of Hash tables is Bruce Morelands tutorial on them, which you can find in Chessprogramming wiki. Very readable and easy to understand.

Don

[voyagerOne]

You ROCK Don! Thanks again!