A basic observation about alphabeta search

[Fguy64]

OK, I wanted to revive a discussion from an earlier thread, but I forget which thread it was.

Anyways, the discussion was something about whether or not we could have list of moves from the root position that has the same eval, and choose randomly from that list as a way of injecting variety into engine play. Anyways, I was eventually convinced that it didn't work that way, because the nature of cutoffs means that the value actually assigned to sub-optimal moves was misleading. Ok fine with that.

It seems an analogous situation might be as follows.

Suppose for the purpose of discussion that you have an engine that features fixed-depth negamax/alphabeta and a straight-up capture search for quiescense, no other features.
Suppose also that Evaluate() consisted only of a material evaluation.

Then it follows that for any position in which there is no forcing line that leads to checkmate or a change in the material balance, then the engine will always play the first move it evaluates.

seems reasonable.

[xsadar]

OK, I wanted to revive a discussion from an earlier thread, but I forget which thread it was.

Anyways, the discussion was something about whether or not we could have list of moves from the root position that has the same eval, and choose randomly from that list as a way of injecting variety into engine play. Anyways, I was eventually convinced that it didn't work that way, because the nature of cutoffs means that the value actually assigned to sub-optimal moves was misleading. Ok fine with that.

It seems an analogous situation might be as follows.

Suppose for the purpose of discussion that you have an engine that features fixed-depth negamax/alphabeta and a straight-up capture search for quiescense, no other features.
Suppose also that Evaluate() consisted only of a material evaluation.

Then it follows that for any position in which there is no forcing line that leads to checkmate or a change in the material balance, then the engine will always play the first move it evaluates.

seems reasonable.

Ok, from what I understand, you are talking about a position where for the depth you search no captures checkmates or stalemates are possible. An example would be a two ply search (with no extensions, hash table, opening book or other search features) from the standard starting position. And from what I understand, you're talking about material only evaluation, where the way in which the pieces are arranged is not considered.

In that case, as I understand it, you are correct. The first move searched in such a case will always be the move actually played on the board, however wrong that move likely is, because all lines will result in the exact same evaluation.

[Fguy64]

OK, I wanted to revive a discussion from an earlier thread, but I forget which thread it was.

Anyways, the discussion was something about whether or not we could have list of moves from the root position that has the same eval, and choose randomly from that list as a way of injecting variety into engine play. Anyways, I was eventually convinced that it didn't work that way, because the nature of cutoffs means that the value actually assigned to sub-optimal moves was misleading. Ok fine with that.

It seems an analogous situation might be as follows.

Suppose for the purpose of discussion that you have an engine that features fixed-depth negamax/alphabeta and a straight-up capture search for quiescense, no other features.
Suppose also that Evaluate() consisted only of a material evaluation.

Then it follows that for any position in which there is no forcing line that leads to checkmate or a change in the material balance, then the engine will always play the first move it evaluates.

seems reasonable.

Ok, from what I understand, you are talking about a position where for the depth you search no captures checkmates or stalemates are possible. An example would be a two ply search (with no extensions, hash table, opening book or other search features) from the standard starting position. And from what I understand, you're talking about material only evaluation, where the way in which the pieces are arranged is not considered.

In that case, as I understand it, you are correct. The first move searched in such a case will always be the move actually played on the board, however wrong that move likely is, because all lines will result in the exact same evaluation.

I understand your post, but it seems to me that you are being unnecessarily limiting in your conditions. I didn't mean no captures are possible. I meant that for a given position and a given search depth, there are no forcing lines that lead to a change in the material balance, which is a significantly broader definition than "no captures are possible".

ok I should clarify that this works as long as the first move doesn't lead to a loss of material, or rather that there are no subsequent moves that lead to a loss of less material.

[hgm]

One way to introduce randomness is to add a small random term to every score in the root (a 'root bias'), so that you don't always pick the best move toplay, but sometimes a slightly less good (but more lucky) move. You have to be very careful that this tinering with scores does not wreck alpha-beta. So you have to decide how much you are going to add to the score before you search the move, and then move the window in the opposite way, to make sure that the in-wndow scores your search finds will be in-window scores in the real window after you add the random.

So where you would normally do

score = -Search(-beta, -alpha);

you can do

score = -Search(-beta+x, -alpha+x) + x;

For efficiency, it is better if you add the same root bias x to each move in every iteration. So assign a root bias to each move immediately after move generation, store it in an array, and then use it for that moe on each iteration. (This to prevent that you randomly change moves.)

The XQWLight engine does something similar and even simpler to : it adds a small random term (centered around 0) to alpha (and bestScore) directly after setting the best move. Then you don't have to fiddle with the widow, it is like adapting the score of all moves searched so far in hind-sight. This adds systematically larger random terms to early moves than to late moves, though.

A fundamentally different way of adding randomness is what I do in Joker: I add a pseudo-random term to each evaluation call. This term is derived from the hash key and the msec start time of the game. Apart from creating non-determinism this acts as a kind of poor-man's mobility evaluation. This should in theory improve playing strength. It would be very interesting to add such a radom term to the evaluation of your hypothetical material-only engine, and see how much better it does when you pit them against each other.

[Fguy64]

Cool thanks HG, I'll bookmark that for future reference. I guess originally way back when, it wasn't so much that I wanted randomness, rather if i had it it I may as well use it. Of course the flaw in my logic was that I didn't realize that my strategy may have been valid for plain old negamax, but once I introduced alpha-beta pruning that basis for random selection was gone.

regards.

[Uri Blass]

One way to introduce randomness is to add a small random term to every score in the root (a 'root bias'), so that you don't always pick the best move toplay, but sometimes a slightly less good (but more lucky) move. You have to be very careful that this tinering with scores does not wreck alpha-beta. So you have to decide how much you are going to add to the score before you search the move, and then move the window in the opposite way, to make sure that the in-wndow scores your search finds will be in-window scores in the real window after you add the random.

So where you would normally do

score = -Search(-beta, -alpha);

you can do

score = -Search(-beta+x, -alpha+x) + x;

For efficiency, it is better if you add the same root bias x to each move in every iteration. So assign a root bias to each move immediately after move generation, store it in an array, and then use it for that moe on each iteration. (This to prevent that you randomly change moves.)

The XQWLight engine does something similar and even simpler to : it adds a small random term (centered around 0) to alpha (and bestScore) directly after setting the best move. Then you don't have to fiddle with the widow, it is like adapting the score of all moves searched so far in hind-sight. This adds systematically larger random terms to early moves than to late moves, though.

A fundamentally different way of adding randomness is what I do in Joker: I add a pseudo-random term to each evaluation call. This term is derived from the hash key and the msec start time of the game. Apart from creating non-determinism this acts as a kind of poor-man's mobility evaluation. This should in theory improve playing strength. It would be very interesting to add such a radom term to the evaluation of your hypothetical material-only engine, and see how much better it does when you pit them against each other.

If you do not have mobility evaluation then maybe it can improve the playing strength but it is not clear to me.

Did you test it to find that it improves the playing strength for joker?

I think that it may reduce the playing strength because of worse order of moves and you may have more cases when move A in the hash is good at ramaining depth 1 to generate a cutoff but is not good at remaining depth 2 thanks to the random noise.

Uri

[xsadar]

OK, I wanted to revive a discussion from an earlier thread, but I forget which thread it was.

Anyways, the discussion was something about whether or not we could have list of moves from the root position that has the same eval, and choose randomly from that list as a way of injecting variety into engine play. Anyways, I was eventually convinced that it didn't work that way, because the nature of cutoffs means that the value actually assigned to sub-optimal moves was misleading. Ok fine with that.

It seems an analogous situation might be as follows.

Suppose for the purpose of discussion that you have an engine that features fixed-depth negamax/alphabeta and a straight-up capture search for quiescense, no other features.
Suppose also that Evaluate() consisted only of a material evaluation.

Then it follows that for any position in which there is no forcing line that leads to checkmate or a change in the material balance, then the engine will always play the first move it evaluates.

seems reasonable.

Ok, from what I understand, you are talking about a position where for the depth you search no captures checkmates or stalemates are possible. An example would be a two ply search (with no extensions, hash table, opening book or other search features) from the standard starting position. And from what I understand, you're talking about material only evaluation, where the way in which the pieces are arranged is not considered.

In that case, as I understand it, you are correct. The first move searched in such a case will always be the move actually played on the board, however wrong that move likely is, because all lines will result in the exact same evaluation.

I understand your post, but it seems to me that you are being unnecessarily limiting in your conditions. I didn't mean no captures are possible. I meant that for a given position and a given search depth, there are no forcing lines that lead to a change in the material balance, which is a significantly broader definition than "no captures are possible".

ok I should clarify that this works as long as the first move doesn't lead to a loss of material, or rather that there are no subsequent moves that lead to a loss of less material.

OK. I see what you're saying, and believe you are correct. I also forgot about the quiescence search, but the example of a two-ply search from the starting position should still work even though you will search some captures (of pawns) in the qsearch because black is not forced to make moves leading to those captures.

What I don't see is the usefulness of knowing this. Even if you know there are positions like this, how would you go about determining if the current position is such a position without doing pure minimax/negamax with no alpha-beta pruning.

HG's suggestion of adding a small random number to a material-only evaluation inside the evaluation function sounds like it might be an improvement to playing strength if you have material-only evaluation. But be aware, once your evaluation function gets more sophisticated it may hurt playing strength due to interference with other evaluation terms.

[mjlef]

OK, I wanted to revive a discussion from an earlier thread, but I forget which thread it was.

Anyways, the discussion was something about whether or not we could have list of moves from the root position that has the same eval, and choose randomly from that list as a way of injecting variety into engine play. Anyways, I was eventually convinced that it didn't work that way, because the nature of cutoffs means that the value actually assigned to sub-optimal moves was misleading. Ok fine with that.

It seems an analogous situation might be as follows.

Suppose for the purpose of discussion that you have an engine that features fixed-depth negamax/alphabeta and a straight-up capture search for quiescense, no other features.
Suppose also that Evaluate() consisted only of a material evaluation.

Then it follows that for any position in which there is no forcing line that leads to checkmate or a change in the material balance, then the engine will always play the first move it evaluates.

seems reasonable.

Ok, from what I understand, you are talking about a position where for the depth you search no captures checkmates or stalemates are possible. An example would be a two ply search (with no extensions, hash table, opening book or other search features) from the standard starting position. And from what I understand, you're talking about material only evaluation, where the way in which the pieces are arranged is not considered.

In that case, as I understand it, you are correct. The first move searched in such a case will always be the move actually played on the board, however wrong that move likely is, because all lines will result in the exact same evaluation.

I understand your post, but it seems to me that you are being unnecessarily limiting in your conditions. I didn't mean no captures are possible. I meant that for a given position and a given search depth, there are no forcing lines that lead to a change in the material balance, which is a significantly broader definition than "no captures are possible".

ok I should clarify that this works as long as the first move doesn't lead to a loss of material, or rather that there are no subsequent moves that lead to a loss of less material.

Two small comments:

1. a random eval (using a random number generator+material) will be able to beat the "only material" program. This is because of mobility. Positions leading to more available moves for one side, or less for the other side will be selected, since the max of a bunch of random numbers increased.
2. Someone with a simple, but very fast engine should think about playing each of the opening moves and see if any lead to a material loss or mate in a long search. For example, can we "prove" f2f4 really is a bad move? What is the fastest searcher available for this, and who has a quad free?

[bob]

One way to introduce randomness is to add a small random term to every score in the root (a 'root bias'), so that you don't always pick the best move toplay, but sometimes a slightly less good (but more lucky) move. You have to be very careful that this tinering with scores does not wreck alpha-beta. So you have to decide how much you are going to add to the score before you search the move, and then move the window in the opposite way, to make sure that the in-wndow scores your search finds will be in-window scores in the real window after you add the random.

So where you would normally do

score = -Search(-beta, -alpha);

you can do

score = -Search(-beta+x, -alpha+x) + x;

For efficiency, it is better if you add the same root bias x to each move in every iteration. So assign a root bias to each move immediately after move generation, store it in an array, and then use it for that moe on each iteration. (This to prevent that you randomly change moves.)

The XQWLight engine does something similar and even simpler to : it adds a small random term (centered around 0) to alpha (and bestScore) directly after setting the best move. Then you don't have to fiddle with the widow, it is like adapting the score of all moves searched so far in hind-sight. This adds systematically larger random terms to early moves than to late moves, though.

A fundamentally different way of adding randomness is what I do in Joker: I add a pseudo-random term to each evaluation call. This term is derived from the hash key and the msec start time of the game. Apart from creating non-determinism this acts as a kind of poor-man's mobility evaluation. This should in theory improve playing strength. It would be very interesting to add such a radom term to the evaluation of your hypothetical material-only engine, and see how much better it does when you pit them against each other.

I don't think that's needed. You get randomness just by using clock time to limit the search. If you do every search and just randomly search one extra node each move, games won't be repeated...

[xsadar]

One way to introduce randomness is to add a small random term to every score in the root (a 'root bias'), so that you don't always pick the best move toplay, but sometimes a slightly less good (but more lucky) move. You have to be very careful that this tinering with scores does not wreck alpha-beta. So you have to decide how much you are going to add to the score before you search the move, and then move the window in the opposite way, to make sure that the in-wndow scores your search finds will be in-window scores in the real window after you add the random.

So where you would normally do

score = -Search(-beta, -alpha);

you can do

score = -Search(-beta+x, -alpha+x) + x;

For efficiency, it is better if you add the same root bias x to each move in every iteration. So assign a root bias to each move immediately after move generation, store it in an array, and then use it for that moe on each iteration. (This to prevent that you randomly change moves.)

The XQWLight engine does something similar and even simpler to : it adds a small random term (centered around 0) to alpha (and bestScore) directly after setting the best move. Then you don't have to fiddle with the widow, it is like adapting the score of all moves searched so far in hind-sight. This adds systematically larger random terms to early moves than to late moves, though.

A fundamentally different way of adding randomness is what I do in Joker: I add a pseudo-random term to each evaluation call. This term is derived from the hash key and the msec start time of the game. Apart from creating non-determinism this acts as a kind of poor-man's mobility evaluation. This should in theory improve playing strength. It would be very interesting to add such a radom term to the evaluation of your hypothetical material-only engine, and see how much better it does when you pit them against each other.

I don't think that's needed. You get randomness just by using clock time to limit the search. If you do every search and just randomly search one extra node each move, games won't be repeated...

For most engines they won't be repeated all the way to the end, but there will be large portions of games repeated. That's part of the reason why you need so many opening positions for your testing.
However, in Fred's case where he currently has material-only eval, if he plays it against another engine with material-only eval my guess is that most games will be repeats. Also if I remember correctly, he currently only supports fixed depth play, so in that case, every game should be a repeat unless he sets it up for his engine to use depth but for his opponent to use time.