combining 2 alpha/beta pairs

[flok]

Hi,

Let's say I have 2 alpha/beta-value pairs. I would like to consolidate them into one pair. E.g. a1 + b1 and a2 + b2.
ar and br will be the result variables.

Should I then do (for side == rootSide):

Code: Select all

     ar = a2
     br = b2

     if a1 > a2
                   ar = a1

and for side != rootSide:

Code: Select all

     ar = a2
     br = b2

     if b1 < b2
                    br = b1

?



Regards

[lucasart]

I don't understand your question. What do you mean by consolidate two aplha beta pairs ?

Also, what do you want to use this operation for ?

I've never had to do anything like that in my engines, so I'm a bit puzzled...

[flok]

I don't understand your question. What do you mean by consolidate two aplha beta pairs ?

Please disrecard the question, I did something stupid.

Something I'm not entirely sure of:
Can I compare the score at different ply depths (of the same color) when determing alpha/beta? And would it make sense?

[flok]

Something I'm not entirely sure of:
Can I compare the score at different ply depths (of the same color) when determing alpha/beta? And would it make sense?

Also: when doing iterative deepening, can I use the score of the previous selected move as the alpha value for the next iteration?

[lucasart]

Something I'm not entirely sure of:
Can I compare the score at different ply depths (of the same color) when determing alpha/beta? And would it make sense?

Also: when doing iterative deepening, can I use the score of the previous selected move as the alpha value for the next iteration?

OK let's say you do a search at depth 1 with a full window (root node)

Code: Select all

score = search(depth=1, alpha=-inf, beta=+inf)

Let's say that score = 50cp. Now you do a search at depth 2 with alpha=50:

Code: Select all

score = search(depth=2, alpha=+50, beta=+inf)

(i) if the score > 50, you can trust this result, and you have gained a bit of pruning (more beta cutoffs) because of this reduced window.
(ii) if the score is <= 50, it cannot be trusted. So you could research the full window:

Code: Select all

score = search(depth=2, alpha=-inf, beta=+inf)

and now you get a correct score.

This scheme is clearly not optimal, but if you devise a better one, the tradeoff (benefit of (i) versus cost of (ii)) can be significantly positive. It's called Aspiration Windows:
http://chessprogramming.wikispaces.com/ ... on+Windows

A simple scheme could be something like that:
(0) search the wull window at depth 1 and get score(1).
(1) set alpha=score(1)-100cp and beta=score(1)+100cp, and search depth=2 with that window:
(i) if score is within the bounds: all good, proceed to the next iteration (set depth=3 and go to (1)).
(ii) if score <= alpha, then set alpha=-inf and retry (go back to (1))
(iii) if score >= beta, then set beta=+inf and retry (go back to (1))

You can already do some experiments with that, and see how to improve it. It's just a basic aspiration algorithm, to give you an idea.

[flok]

A simple scheme could be something like that:
(0) search the wull window at depth 1 and get score(1).
(1) set alpha=score(1)-100cp and beta=score(1)+100cp, and search depth=2 with that window:
(i) if score is within the bounds: all good, proceed to the next iteration (set depth=3 and go to (1)).
(ii) if score <= alpha, then set alpha=-inf and retry (go back to (1))
(iii) if score >= beta, then set beta=+inf and retry (go back to (1))

Am I right that ii and iii can also happen somewhere deeper in the tree and not neccessarily at the top?
Shall I then:
- completely redo the iteration?
- ignore this move?
- re-search this part of the tree with wider a/b?

Or can this only happen when my alpha/beta code is broken somewhere else?

[bob]

A simple scheme could be something like that:
(0) search the wull window at depth 1 and get score(1).
(1) set alpha=score(1)-100cp and beta=score(1)+100cp, and search depth=2 with that window:
(i) if score is within the bounds: all good, proceed to the next iteration (set depth=3 and go to (1)).
(ii) if score <= alpha, then set alpha=-inf and retry (go back to (1))
(iii) if score >= beta, then set beta=+inf and retry (go back to (1))

Am I right that ii and iii can also happen somewhere deeper in the tree and not neccessarily at the top?
Shall I then:
- completely redo the iteration?
- ignore this move?
- re-search this part of the tree with wider a/b?

Or can this only happen when my alpha/beta code is broken somewhere else?

Are you using PVS? If so, 99+% of the tree is searched with the window {alpha, alpha+1}. You can't relax either bound. If you fail low you back up alpha. If you fail high you back up beta. With one exception.

If you are inside a node, you search the first move with the alpha/beta bounds passed in. If they are x,x+1, the above applies perfectly. However, if beta > alpha+1, then when you search internal branches using alpha,alpha+1, and you fail high, you DO need to search again with alpha,beta (original beta passed in to you).

That is classic PVS. I suppose you could ALWAYS research a second time if you fail high on alpha, alpha+1, but if alpha+1 == beta, you are going to fail high again, albeit very quickly thanks to the tt probe at the next node.

[flok]

Hi,

Are you using PVS? If so, 99+% of the tree is searched with the window {alpha, alpha+1}. You can't relax either bound. If you fail low you back up alpha. If you fail high you back up beta. With one exception.
If you are inside a node, you search the first move with the alpha/beta bounds passed in. If they are x,x+1, the above applies perfectly. However, if beta > alpha+1, then when you search internal branches using alpha,alpha+1, and you fail high, you DO need to search again with alpha,beta (original beta passed in to you).
That is classic PVS. I suppose you could ALWAYS research a second time if you fail high on alpha, alpha+1, but if alpha+1 == beta, you are going to fail high again, albeit very quickly thanks to the tt probe at the next node.

I'm not using PVS yet.

While pondering on your explanation I realized that my question might be a little, well, comes from thinking the wrong way. If I understand it right (now), A/B are only used as hints. So it is technically not wrong to either ignore or enlarge them (and re-do the move).

[Sven]

Hi,

Are you using PVS? If so, 99+% of the tree is searched with the window {alpha, alpha+1}. You can't relax either bound. If you fail low you back up alpha. If you fail high you back up beta. With one exception.
If you are inside a node, you search the first move with the alpha/beta bounds passed in. If they are x,x+1, the above applies perfectly. However, if beta > alpha+1, then when you search internal branches using alpha,alpha+1, and you fail high, you DO need to search again with alpha,beta (original beta passed in to you).
That is classic PVS. I suppose you could ALWAYS research a second time if you fail high on alpha, alpha+1, but if alpha+1 == beta, you are going to fail high again, albeit very quickly thanks to the tt probe at the next node.

I'm not using PVS yet.

While pondering on your explanation I realized that my question might be a little, well, comes from thinking the wrong way. If I understand it right (now), A/B are only used as hints. So it is technically not wrong to either ignore or enlarge them (and re-do the move).

Bob was thinking about PVS. You were thinking about aspiration windows, and whether the same mechanism would apply to inner nodes. These are two very different issues.

In plain alpha-beta search without PVS (and also without nullmove, LMR, ...) there is no re-search at inner nodes, only at the root when using aspiration windows and the search with the initial bounds fails high or low. At inner nodes, failing high with one move leads to an immediate cutoff, and failing low with one move means "nothing" as long as there are more moves left to search. You must not change the window in either of these cases, this has potential to turn the size of your tree into that of a full minimax tree (i.e. O(BF ^ N) instead of O(BF ^(N/2))). So a clear "no", alpha and beta are not only used as hints, they are an essential part of the algorithm, you won't get nearly as many cutoffs when seeing them only as a "hint".

Sven

[flok]

In plain alpha-beta search without PVS (and also without nullmove, LMR, ...) there is no re-search at inner nodes, only at the root when using aspiration windows and the search with the initial bounds fails high or low. At inner nodes, failing high with one move leads to an immediate cutoff, and failing low with one move means "nothing" as long as there are more moves left to search. You must not change the window in either of these cases, this has potential to turn the size of your tree into that of a full minimax tree (i.e. O(BF ^ N) instead of O(BF ^(N/2))). So a clear "no", alpha and beta are not only used as hints, they are an essential part of the algorithm, you won't get nearly as many cutoffs when seeing them only as a "hint".

I think I understand.
Is it possible to have all moves in a node to fail low? And what action should be taken then?


thanks