Make engine stop repeating moves in a clearly won position

[mvanthoor]

You were doing exactly the opposit from what was required. In ply 20 was irreversible, and you are now after 26, you should test after 20-25. Not after 0-19. The 0-19 are guaranteed to never be the same as 26, because 20 was irreversible. And that is what 'irreversible' means: you cannot recreate a position before it.

Yes, I know. I should take some more breaks from coding to keep my head on straight.

[Ras]

PS: If I put the call to is_repetition directly after make() (in the move loop), the engine instantly returns with minus infinity,

That's probably because you shouldn't return 0 as value from the loop at that point - only skip the usual recursive evaluation and use 0 as "value for this move". Means, instead of going deeper, you'd end up at the point after your recursion where alpha-raise / beta-cutoff is evaluated.

[mvanthoor]

PS: If I put the call to is_repetition directly after make() (in the move loop), the engine instantly returns with minus infinity,

That's probably because you shouldn't return 0 as value from the loop at that point - only skip the usual recursive evaluation and use 0 as "value for this move". Means, instead of going deeper, you'd end up at the point after your recursion where alpha-raise / beta-cutoff is evaluated.

So you mean to skip the move ("continue" the loop as you do if make() returns that the move is not legal), or break the loop ("break") ending up right AFTER the loop? I assume you mean the first, because the alpha/beta stuff is evaluated within the loop.

Thus, right after a successful make():

Code: Select all

if is_draw(&board) {
	continue;
}

In that case, the repeating move will obviously not be made, which is good. Should have thought about that myself.

[Ras]

So you mean to skip the move ("continue" the loop as you do if make() returns that the move is not legal)

No, I meant that you usually have something like this in your node loop:

Code: Select all

for all moves in the node:
make_move
t = recursion(...)
unmake_move
if (t > alpha) do_something
if (t >= beta) do_cutoff

So what you'd do now is:

Code: Select all

for all moves in the node:
make_move
if (draw_detected)
    t = 0 (or contempt if you have that)
else
    t = recursion(...)
unmake_move
if (t > alpha) do_something
if (t >= beta) do_cutoff

[mvanthoor]

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

This way you could play it, if you're down in eval. With my suggestion above to just skip it, that would not be possible; the engine wouldn't be able to repeat even if it would have been the best option.

[maksimKorzh]

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

This way you could play it, if you're down in eval. With my suggestion above to just skip it, that would not be possible; the engine wouldn't be able to repeat even if it would have been the best option.

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--.

Now with what in VICE is called history ply (or repetition index in BBC) it goes the same like ply, e.g.

make_move()
ply++;
history_ply++

take_back()
ply--;
history_ply--;

BUT!

When we parse moves from GUI we are also calling make_move() function to obtain the board state for the given position and in this case we need to make sure that ply remains 0 while history_ply actually gets updated.

e.g. in VICE every time make_move() is applied to make a move from GUI we have:
if (parse_move())
make_move()
ply = 0

So when the new search begins ply would be zero, while history ply would be equal to the number of half moves made during the game.

Let's say we have an example:
GUI says: position startpos moves e2e4 e7e5 g1f3 b8c6
now what would be the value of history ply?
it would be equal to 4 because we made exactly 4 half plies (every time move is made we should do history_ply++)

Now if for some reason you DO NOT DO THAT in your engine then the behavior would be exactly like you've described in the initial question.
I had that nasty bug in BBC until Pedro Castro kindly explained me what I was trying to explain now.

Obviously this might not be your case, but anyway there is a miserable chance that my experience can help.
This repetition detection is something everyone assumes but nobody explains like Pedro explained to me ones)

SUMMARY: make sure you're searching for repetition (and obviously storing them as well) in regards to ALL GAME HISTORY and not only from the root of the search. If you don't take care of all game history - no matter where and how you detect repetitions - they would get detected only within a current search, e.g. there won't be a repetition in PV, but no repetition in PV doesn't obviously mean that there would be no repetition in the game!
Hope it makes sense. But again like, I'm 99% sure you know that)

[mvanthoor]

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 ...?
...

Hi Maksim,

This is somewhat difficult to answer for me, because VICE uses several variables that are called either history or ply. What I can remember from the video's, it at least has "ply", "history_ply", and "hisPly".

I think, but don't know for sure, that one of them is the history move counter. VICE saves the board history in an array (as C doesn't have anything like vectors), and the array is (probably) 1024 elements long. Because you need to know the last element in the array, you need an extra variable.

So, when "position startpos moves e2e4 e7e5 g1f3 b8c6" comes in, you set up the starting position and then execute 4 moves. You will then have 4 insertions in the history array. The first one will be the starting position, saved just before making e4. The second is the one just before e5, and so on. To debug the repetition stuff while writing and testing it, I wrote a "history" command for my engine. This is the output after "position startpos moves e2e4 e7e5 g1f3 b8c6"

Code: Select all

position startpos moves e2e4 e7e5 g1f3 b8c6
board

8   r . b q k b n r
7   i i i i . i i i
6   . . n . . . . .
5   . . . . i . . .
4   . . . . I . . .
3   . . . . . N . .
2   I I I I . I I I
1   R N B Q K B . R

    A B C D E F G H

Zobrist key:        adeee2b02d37b641
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    2
Full-move number:   3

history
0  | ply: 1 zk: 819aa694337673fb ac: 0 cperm: KQkq ep: - hmc: 0 fmn: 1 mat: 3960/3960, psqt: -70/-70 next: e2e4
1  | ply: 2 zk: f2d5cb52ebcbf58b ac: 1 cperm: KQkq ep: e3 hmc: 0 fmn: 1 mat: 3960/3960, psqt: 0/-70 next: e7e5
2  | ply: 3 zk: c4a44c03dd9cd443 ac: 0 cperm: KQkq ep: e6 hmc: 0 fmn: 2 mat: 3960/3960, psqt: 0/0 next: g1f3
3  | ply: 4 zk: 7e7bb5d54330e612 ac: 1 cperm: KQkq ep: - hmc: 1 fmn: 2 mat: 3960/3960, psqt: 15/0 next: b8c6

As you can see, spot 0 in the array contains the starting position, where ply 1 is played (e2e4). So that zobrist key starting with 819aad is the one from the starting position.

Thus... there are 4 elements in the history after "position startpos moves e2e4 e7e5 g1f3 b8c6", which is logical as you played 4 moves.

So yes, you have to increment one of those ply or history variables each time you execute a move coming in with the position UCI command, but in VICE, I I don't know which one it is. (When making the move repetition video, BlueFever gets the variables mixed up himself initially, so I understood it the wrong way and made my implementation backwards.)

In my case, I don't have to worry about this, because I created a History struct around the array. This struct holds a "count" variable, and it has a "push()" method. When I add another history, i just do "history.push(current_game_state)", and the array counting variable increments itself.

It basically works the same way as it does in VICE, but the array and the counter variable are in one struct, m managed by some functions attached to that struct. See https://github.com/mvanthoor/rustic/blo ... history.rs

So when I make a move with make(), it gets "pushed" into the array and the counter increments; when i then unmake() a move, it gets decremented because during unmake, the history is "popped". (The move is not actually deleted from the array, only the counter is decremented.)

The difference is that you need to take two things into account:
- You have to increment the history counter when moves are actually made (with position...)
- The history counter is then at a certain value...
- And during search, you indeed have to increment and decrement it yourself. So when you start searching after the first 4 "position..." moves are made, you increment the counter with each move searched, decrement it during takeback, and when you actually MAKE your best move, you increment it again, because you now made 5 moves.

Because the history counter is wrapped in that "History" struct and incremented and decremented during push() and pop(), all of this stuff is automatic in Rustic. Believe me when I tell you that writing software without global variables is easier.... and there is a way to do it, even in C. If you want, I'll post about that later.

[maksimKorzh]

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 ...?
...

Hi Maksim,

This is somewhat difficult to answer for me, because VICE uses several variables that are called either history or ply. What I can remember from the video's, it at least has "ply", "history_ply", and "hisPly".

I think, but don't know for sure, that one of them is the history move counter. VICE saves the board history in an array (as C doesn't have anything like vectors), and the array is (probably) 1024 elements long. Because you need to know the last element in the array, you need an extra variable.

So, when "position startpos moves e2e4 e7e5 g1f3 b8c6" comes in, you set up the starting position and then execute 4 moves. You will then have 4 insertions in the history array. The first one will be the starting position, saved just before making e4. The second is the one just before e5, and so on. To debug the repetition stuff while writing and testing it, I wrote a "history" command for my engine. This is the output after "position startpos moves e2e4 e7e5 g1f3 b8c6"

Code: Select all

position startpos moves e2e4 e7e5 g1f3 b8c6
board

8   r . b q k b n r
7   i i i i . i i i
6   . . n . . . . .
5   . . . . i . . .
4   . . . . I . . .
3   . . . . . N . .
2   I I I I . I I I
1   R N B Q K B . R

    A B C D E F G H

Zobrist key:        adeee2b02d37b641
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    2
Full-move number:   3

history
0  | ply: 1 zk: 819aa694337673fb ac: 0 cperm: KQkq ep: - hmc: 0 fmn: 1 mat: 3960/3960, psqt: -70/-70 next: e2e4
1  | ply: 2 zk: f2d5cb52ebcbf58b ac: 1 cperm: KQkq ep: e3 hmc: 0 fmn: 1 mat: 3960/3960, psqt: 0/-70 next: e7e5
2  | ply: 3 zk: c4a44c03dd9cd443 ac: 0 cperm: KQkq ep: e6 hmc: 0 fmn: 2 mat: 3960/3960, psqt: 0/0 next: g1f3
3  | ply: 4 zk: 7e7bb5d54330e612 ac: 1 cperm: KQkq ep: - hmc: 1 fmn: 2 mat: 3960/3960, psqt: 15/0 next: b8c6

As you can see, spot 0 in the array contains the starting position, where ply 1 is played (e2e4). So that zobrist key starting with 819aad is the one from the starting position.

Thus... there are 4 elements in the history after "position startpos moves e2e4 e7e5 g1f3 b8c6", which is logical as you played 4 moves.

So yes, you have to increment one of those ply or history variables each time you execute a move coming in with the position UCI command, but in VICE, I I don't know which one it is. (When making the move repetition video, BlueFever gets the variables mixed up himself initially, so I understood it the wrong way and made my implementation backwards.)

In my case, I don't have to worry about this, because I created a History struct around the array. This struct holds a "count" variable, and it has a "push()" method. When I add another history, i just do "history.push(current_game_state)", and the array counting variable increments itself.

It basically works the same way as it does in VICE, but the array and the counter variable are in one struct, m managed by some functions attached to that struct. See https://github.com/mvanthoor/rustic/blo ... history.rs

So when I make a move with make(), it gets "pushed" into the array and the counter increments; when i then unmake() a move, it gets decremented because during unmake, the history is "popped". (The move is not actually deleted from the array, only the counter is decremented.)

The difference is that you need to take two things into account:
- You have to increment the history counter when moves are actually made (with position...)
- The history counter is then at a certain value...
- And during search, you indeed have to increment and decrement it yourself. So when you start searching after the first 4 "position..." moves are made, you increment the counter with each move searched, decrement it during takeback, and when you actually MAKE your best move, you increment it again, because you now made 5 moves.

Because the history counter is wrapped in that "History" struct and incremented and decremented during push() and pop(), all of this stuff is automatic in Rustic. Believe me when I tell you that writing software without global variables is easier.... and there is a way to do it, even in C. If you want, I'll post about that later.

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.

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.

[mvanthoor]

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.

[mvanthoor]

PS: getting this fix indeed caused a massive jump in strength.

Previously Rustic would throw away lots of won games against Nero 6.1 (Elo 1450), and it scored around 50% because of a massive list of draws.
Now it clobbers Nero 6.1 with infinite results (= wins every game).

Yesterday I had Rustic play a match of idiotic-bullet chess against ShallowBlue: 5 seconds per move.
It scored 4 out of 10 (40%), which would tentatively put Rustic at 1640 Elo. (I know the number of games is very small, but it was just a quick test to see if Rustic could actually win won games against an opponent 250 Elo stronger than Nero. And yes, it can.)

So this fix brought about 200 Elo.

Please note that Shallow Blue has a laundry list of features... including a TT (which doesn't seem to give it a lot of speed) and a tapered evaluation, and that Rustic only has material count and a PSQT. And, it seems, compared to ShaloowBlue, a MASSIVE 20x speed advantage. (Rustic reaches the same depths as ShallowBlue without having any search optimizations yet; and certainly not a TT.)

I wonder what the results will be when I start adding features

At least, I'm going to try and postpone adding a TT and extending the evaluation as long as possible to see how far I can get with only bare search speed. Then I'll add a tapered eval. Basically, the same way Roland did it with PeSTO.