You will get randomness, especially on a program with hash tables and LMR just by scrambling the root move list ordering.
After each iteration slide the best move to the front of the list without changing the ordering of the other moves. I do this myself, but I do sort the moves first based on a 1 ply search with infinite alpha and beta - so if you sort you won't get as much randomness - although you might still get a little.
Modern chess programs are pretty chaotic, so I don't think lack of randomness is very likely even if you do nothing. Do you preseve hash tables between moves? That is good if you do for randomness.
xsadar wrote:
bob wrote:
hgm wrote: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.
hgm wrote: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.
You will get randomness, especially on a program with hash tables and LMR just by scrambling the root move list ordering.
After each iteration slide the best move to the front of the list without changing the ordering of the other moves. I do this myself, but I do sort the moves first based on a 1 ply search with infinite alpha and beta - so if you sort you won't get as much randomness - although you might still get a little.
Modern chess programs are pretty chaotic, so I don't think lack of randomness is very likely even if you do nothing. Do you preseve hash tables between moves? That is good if you do for randomness.
Don, I took the liberty of moving your top post to a bottom post, hope that's ok. Anyways, I see your point, no dispute, but I'm with Mike here, because my original conditions were very restrictive. I'll repeat them here.
fixed depth, straight up negamax/alphabeta, straight up capture qSearch with MVV/LVA move ordering. Evaluate() based on material only. Nothing else. No hash table.
So my original claim was for any given position and depth, in the absence of a line that forces checkmate/stalemate or a change in the material balance, the engine will always play the first move evaluated. And I'll take that a step further and say two identical engines playing at the same settings play the same game every time.
