Make engine stop repeating moves in a clearly won position

[hgm]

Ah, like that, instead of going deeper you "pretend" the move to have a value already. Thanks.

There is no pretense here. The game ends at that point, because either you or the opponent can claim a draw there. So alpha-beta pruning says there is no need to search other options than claiming the draw; whatever the result of that would be, one of the players would always avoid it by claiming the draw. The situation is very much like running into a stalemate; you don't search any deeper there eiter, it is "game over".

[Edit] Oh, I see you already came to exactly that conclusion in a later posting.

[hgm]

I will now ask a dumb question, but it would point to the exact issue I had with repetitions.
Do you update history ply (repetition half move) in UCI when GUI sends position startpos moves e2e4 e7e5 ...?

The PLY is changing only from root of the search, so during search ply can be 6, 7 ... etc and when the search ends PLY is 0 again because every time we are making the move we say PLY++ evaery time we are taking move back we are saying PLY--.

In some of my engines I keep the game history in the same array as the current search branch, at negative index. So ply == 0 still is the root, and its repKey is in gameHist[0]. But gameHist[-1] is the key of the forelast posiiton of the game, etc. Every time a move is made in the game I insert ithe key of the new position at 0, shifting the old game history one down.

As I am often dealing with variants where all moves are reversible (because captured pieces can be dropped back in play), and it is a pain to have to loop through the entire game in every node, I often use entirely different methods for detecting repettions. One method uses two small hash tables (one for wtm, one for btm) large enough to hold a maximum-length game. MakeMove puts the key of the new position into the table; if the entry to which it maps is occupied, it just steps sequentially through the table until it finds an empty one. If in that process (which commonly finds an empty entry on the first try) it finds an entry that already contais the key you want to store, you have a repetition. On UnMake, I mark the entry that held the key again as empty.

In principle you can clear the entire table on an irreversible move at game level. If you want to exclude null-move-spanning repeat loops, you can store the ply level together with the key, and remember the ply of the latest null move, to see how it compares.

Another method is the one I already described of micro-Max: just alter the score of the TT entry for the root position into a draw, and put its depth at max, so it will satisfy any hash probe. (The root already has an 'exact' bound type.) If you use a depth-preferred scheme for replacement, this automatically guarantees these entries will never be overwritten. So any attempt to repeat them in search will result in a hash hit with a draw score. You cannot exclude null-move-spanning repeats with this method, though.

[mvanthoor]

Ah, like that, instead of going deeper you "pretend" the move to have a value already. Thanks.

There is no pretense here. The game ends at that point, because either you or the opponent can claim a draw there. So alpha-beta pruning says there is no need to search other options than claiming the draw; whatever the result of that would be, one of the players would always avoid it by claiming the draw. The situation is very much like running into a stalemate; you don't search any deeper there eiter, it is "game over".

[Edit] Oh, I see you already came to exactly that conclusion in a later posting.

Yes, I know there is no pretense. That is why pretend is in quotes. What I meant was the fact that you never actually evaluate the position using the evaluation function. You assign the value directly, and thus "pretend" to have evaluated the position as exactly draw. Maybe I should have been clearer, and maybe it isn't even the best explanation, but for me, it works

Since I've finally written the a/b function I finally -understand- it (or at least, start to understand it); so I now know what to do is when someone says "run function X on the move and if the value is below 0, then skip the move"... that sort of thing. It took some time for some things to actually click, but it -is- my first (real) chess engine ever... from scratch... in a programming language I started using only when I started this program. So I'm not ashamed having to sometimes say "I don't understand this"; but I won't continue development unless I do understand exactly what's happening, so I can verify if the implementation is correct or not.

[hgm]

Nothing beats doing it yourself as a learning experience!

At the time of my first chess program it was a revelation for me to discover how deep alpha-beta is ingrained in the thinking of a human chess player. When I was watching what the engine was thinking about (it constantly showed the current tree branch in the display), at some point I though: "This is insane! It already knows it has a move at the root that comes out about equal, and it has just search a branch where it sees that the current branch will make it end at least a Pawn down... And it is still wasting enormous amounts of time on that refuted branch now. What incredibly stupid!" It turned out that my home-brewn Search routine did not take account of the so-called 'deep cutoffs': I had only considered raising of alpha by the moves in the node, always starting it at -INF instead of inheriting a start value from the parent. Chess players tend to know very well when a move is refuted, and when not!

And yes, when the rules specify a game result, this replaces the eavluation score. On finding yourself checkmated, you 'pretend' the evaluation is -32000 (or something like that), even when the heuristic eval says you are a queen ahead. Actually it is more the reverse: the heuritic evaluation pretends to be an indicator for the future result of the game. Checkmate and draw detection knows.

[maksimKorzh]

Ok Marcel, now I clearly see that you didn't miss the point. Your history struct is just a matter of implementation. So if you update it then it's a real mystery for me why rustic repeats moves.

Now it doesn't repeat moves anymore. I wrote my own implementation of is_repetition. It just searches the history backwards, until it either finds a repeat (historic zobrist is the same as the one from the board coming in), or it hits a history where half-move-clock is 0 (the move creating that position captured a piece, or moved a pawn, so searching further back is not necessary.)

I also implemented Ras's suggestion to not return a DRAW (as VICE also does), but to immediately set the eval_score in alpha/beta to DRAW, instead of recursing deeper into the tree. This is better, because when you encounter the repeat, you don't need to go any deeper. (And it also saves nodes). Why? Because:

If you're up in evaluation, the later alpha/beta check will discard this move as it is not better (0 is worse than being up X point).
If you're down in evaluation, the engine will try to play this repetition (as 0 is better dan being down X points)

And it works: if I now repeat positions on the board while Rustic is analyzing, it DOESN'T suggest a repeating move when it analyzes for the side that is up, but it DOES if it's analyzing for the side that is down.

So I changed both the is_repeat implementation, and the place where it is called.

I don't argue that writing software without global variables is better for production. And trust me I know how to make a struct in C that mimics class behavior via encapsulating function pointers. I just want to say that global variables helped me to understand the logic of repetition detection in the simplest way possible.

OK, if you know this already, then it saves me a lot of typing.

Cool, I'm glad you made it working!

[Ras]

Yeah! Btw., remember that the draw checking should only happen on fully legal moves. While the history repeat could not happen on illegal ones, the "insufficient material" check could evaluate to "true" if some capture leads to insufficient material, but the capture is not actually possible because it would put/leave the moving side's king in check.

[abulmo2]

In some of my engines I keep the game history in the same array as the current search branch, at negative index. So ply == 0 still is the root, and its repKey is in gameHist[0]. But gameHist[-1] is the key of the forelast posiiton of the game, etc. Every time a move is made in the game I insert ithe key of the new position at 0, shifting the old game history one down.

In C or C++ you can have negative indexes because you manipulate pointers instead of a true array. I doubt you can do that in Rust or other modern language. There are also some modern languages where negative indexing means indexing from the end of the array. Even in C/C++ directly manipulating pointers might not be such a good idea. Of course it can lead to bugs and does so too often, but it may also prevent the compiler to fully optimize your code.

[mvanthoor]

Cool, I'm glad you made it working!

Yeah! Btw., remember that the draw checking should only happen on fully legal moves. While the history repeat could not happen on illegal ones, the "insufficient material" check could evaluate to "true" if some capture leads to insufficient material, but the capture is not actually possible because it would put/leave the moving side's king in check.

Thanks for your help both I've been testing Rustic against Nero 6.1 (CCRL 1450) and Pulse 1.7.2 (CCRL 1650).

Earlier, Nero 6.1 would manage to draw games in a position that was won for Rustic, because Rustic wouldn't detect repeats correctly. Now that it does, Nero 6.1 doesn't have a chance; Rustic completely destroys Nero by scoring 70 to 80% against it in several 20 game matches. That would put Rustic 150 - 240 Elo above Nero (assume +200). Before this fix, Rustic scored about 50% against Nero.

Now Rustic itself pulls the same stunt against Pulse 1.7.2 (CCRL 1650): it draws games it should have lost, because Pulse doesn't detect draws correctly. In 50 games, Rustic scored a 26 - 24 win (at a time control of 5 seconds per move). That is a score of 52%, or +14 Elo; but in a 2 minute/game + 2 sec/move bullet match it scored 60% in 20 games (+71 Elo)

The engine hasn't played a lot of games yet, and Arena's opening book isn't optimal (it has weird 2-move openings... or I have a wrong setting somewhere). I have to create my own engine pool and a proper 4 or 6 move opening book next week for a proper test. I don't think I'm too far off the mark when I say that fixing this repetition issue gained +/- 200 Elo, and that the engine, without any features but MVV/LVA + PSQT is now at a rating of CCRL 1650; but probably with 50 Elo error bars.

[hgm]

In C or C++ you can have negative indexes because you manipulate pointers instead of a true array. I doubt you can do that in Rust or other modern language. There are also some modern languages where negative indexing means indexing from the end of the array. Even in C/C++ directly manipulating pointers might not be such a good idea. Of course it can lead to bugs and does so too often, but it may also prevent the compiler to fully optimize your code.

In C I just implement this by a preprosessor macro:

Code: Select all

int rawHist[1000];
#define gameHist (rawHist + 500)

Then rawList behaves exactly like it was an int array with index running form -500 to +500.

[abulmo2]

Even in C/C++ directly manipulating pointers might not be such a good idea. Of course it can lead to bugs and does so too often.

In C I just implement this by a preprosessor macro:

Code: Select all

int rawHist[1000];
#define gameHist (rawHist + 500)

Then rawList behaves exactly like it was an int array with index running form -500 to +500.

I guess you meant gameHist and from -500 to 499.
Technically in C, gameHist is a pointer and rawHist an array.
Just to illustrate what I said earlier, see this example:

Code: Select all

#include <stdio.h>

int rawHist[1000];
#define gameHist (rawHist + 500)

int main(void) {
	printf("rawHist size = %zd\n", sizeof rawHist);
	printf("gameHist size = %zd\n", sizeof gameHist);
	printf("gameHist %d\n", gameHist[500]);
	printf("rawHist %d\n", rawHist[1000]);
}

When compiled with clang all warning on, you get the following messages:

Code: Select all

foo.c:8:41: warning: sizeof on pointer operation will return size of 'int *' instead of 'int [1000]' [-Wsizeof-array-decay]
        printf("gameHist size = %zd\n", sizeof gameHist);
                                               ^~~~~~~~
foo.c:4:27: note: expanded from macro 'gameHist'
#define gameHist (rawHist + 500)
                  ~~~~~~~ ^
foo.c:10:25: warning: array index 1000 is past the end of the array (which contains 1000 elements) [-Warray-bounds]
        printf("rawHist %d\n", rawHist[1000]);
                               ^       ~~~~
foo.c:3:1: note: array 'rawHist' declared here
int rawHist[1000];
^
2 warnings generated.

Clang warns about the array decayed into a pointer, and is able to find the array is used out of bounds, but not the pointer. Your trick may look smart (and myself I used it quite often), but it is somewhat dangerous.