Repetition-Zugzwang

[Desperado]

ok, for now i fixed my problems like that...

i simply changed...

Code: Select all

//--------valueToTrans------------------
//--------------------------------------

VAL_T valueToTT(VAL_T value,PLY_T cdp)
	{
		  if (value < -mateScore) value -= cdp;
	 else if (value > +mateScore) value += cdp;

     return(value);
	}

//--------valueFromTrans----------------
//--------------------------------------

VAL_T valuefrTT(VAL_T value,PLY_T cdp)
	{
		  if(value < -mateScore) value += cdp;
	 else if(value > +mateScore) value -= cdp;

	 return(value);
	}

into...

Code: Select all

#define WINNINGSCORE 300
#define LOSINGSCORE -300

//--------valueToTrans------------------
//--------------------------------------

VAL_T valueToTT(VAL_T value,PLY_T cdp)
	{
		  if (value < LOSINGSCORE)  value -= cdp;
	 else if (value > WINNINGSCORE) value += cdp;

     return(value);
	}

//--------valueFromTrans----------------
//--------------------------------------

VAL_T valuefrTT(VAL_T value,PLY_T cdp)
	{
		  if(value < LOSINGSCORE)  value += cdp;
	 else if(value > WINNINGSCORE) value -= cdp;

	 return(value);
	}

This seem to make sure that my engine is making progress during
search.Further winning+losing score can be a flexible value.
A similar idea would be sth. like

Code: Select all

if(value < -mateScore)...
else if(value > mateScore)...
else if(moveIsPromotion)...

or

Code: Select all

else if(scoreJump)...

Well in other words, always if the positional score does not dominate
the evaluation (that s what i have in mind), the transValue gets
the "progress-information" dependent on depth parameter.

What do you think ?

Michael

[hgm]

However, this is not a problem in real games because your engine will never enter the position after 1.Kf5 _because_ it is scored a draw (well, the draw score is only shown in the upper iterations if you have no recognition code in, but the score is lower than the promotion seen after 1.Kd6.

Exactly, that is the crux. The assumption first-rep = draw is a self-justifying assumpion. There are plenty positions (+ history) where it does not work, but you won't get in those from the opening position when you make that assumption. So it is safe to make it.

But then you should not complain that things goes disastrously wrong when you actally start in such an 'unreachable' position.

I am not sure if what you describe above would work. The first solution you give only seems to address the TT, while in principle the problem of preferring the detour would also exist in a plain search without TT. Except that sometimes iterative deepening would save you, because you find the quickest path first, and then stick with it out of conservatism. But as the infinitely-delayed promotion showed, this does not aways save you.

Also, comparing to a fixed score threshold for both sides might not work. E.g. if you are already at +300 in the root, and do a fixed-depth search, wouldn't you simply shift the score of all branches by the same amount? If so, that wuld have no effect on move choice at all.

I would still prefer the normal delayed-loss bonus, e.g.

Code: Select all

Search(alpha, beta)
{
  e = Eval();
  if(alfa < e) alpha = floor(e+(alpha-e)/0.97);
  if(beta < e) beta = ceiling(e+(beta-e)/0.97);

  // normal Search code

  if(bestScore < e) bestScore = e + (bestScore-e)*0.97;
  return betsScore;
}

[Michel]

But then you should not complain that things goes disastrously wrong when you actally start in such an 'unreachable' position.

The position is not really unreachable. Situations like this may and do occur in analysis of games played between humans.

The human may play Kf5 accidentally before realizing it makes no progress and Kd6 is the way to go. If you start analysis after Kf5 some engines will think the game is draw since they encounter a first repetition after Kf7 Ke5 Kf7 and score that position as draw.

[hgm]

Indeed. But I think that should be considered an engine bug. Proper procedure is to only count the first repetition of a tree position as draw. For a position from the game history, only the third occurrence should be counted as draw. Then the problem you describe cannot occur.

[Desperado]

...

start in such an 'unreachable' position.

...

sorry, but i dont really understand why this position
is an _unreachable_ position.

========================================================



ex:

first path:

18. Ke5 (search) ...
18. ... drawOnRepetition,transCheck,loopmovelist->return(score)(Kf7)

- all moves are loosing
- store loosing value to trans.



another path:

16. Ke5 (search) ...
16. ... drawOnRepetition(false),transCheck(true)->return(score)


well, because black has the first claim on draw, white cant
do anything against.That would require in the above example
that black indicates to play Kf7, like

18. ... Kf7 19.drawOnRepetition(true)
or
17. ... Kf7 18.drawOnRepetition(true)

therefore it also doesnt matter if it is an 2,3,x-fold repetition.

========================================================

gamehistory: 1.Kf5 Ke7 2. Ke5 Kf7 3. Kf5 Ke7 4. ...


root: Ke5(search) ...
ply1: ... drawOnRepetition(false),transCheck(true)->return(score).

required:

root: Ke5(search) ...
ply1: ... loopmovelist ! to detect Kf7 as drawOnRepetition


and now ? missed to loop the movelist,which is necessary to detect
the repetition draw.This can of course happen everywhere in the
tree.But is of course a disaster here near the root.

...

Also, comparing to a fixed score threshold for both sides might not work. E.g. if you are already at +300 in the root, and do a fixed-depth search, wouldn't you simply shift the score of all branches by the same amount? If so, that wuld have no effect on move choice at all.

...

Well, i think it is shifting all branches by the same amount.
And that is desired (at least for my first thoughts).
I dont want to influence the moveChoice on a certain ply.

The _relative_ (static,dynamic) evaluation of different positions should
be the same as without that code.

This approach should handle identical positions on different
plies, which in late endgames occure very often.(think about going
for mate).

Let us think of a queen promotion in a Kpk endgame. So the static
evaluation might be between 50-150 centipawns. After a promotion
the static eval is about 900.

So the logic is: do promote in 20 instead of 30 -> (880 instead of 870)
like : go for mate in 20 instead of 30

of course, there is a lot of room to work on that idea.
Especially the scoreJump idea.

static eval: 80 [-100,500]
movlistscores:

- +30
- +40
- -15
- 400 (400-staticEval ->320 -> scoreJump)

now finding this position somewhere else in the tree
having a singular move, try to play it as early as you can...
and because 400-depth is still far away from the
other evaluations(30,40,-15), that would not destroy
the search result.

Well, at least i keep that in mind, and will have a close look
on your proposal.


regards, Michael

[hgm]

ex:

first path:

18. Ke5 (search) ...
18. ... drawOnRepetition,transCheck,loopmovelist->return(score)(Kf7)

- all moves are loosing
- store loosing value to trans.



another path:

16. Ke5 (search) ...
16. ... drawOnRepetition(false),transCheck(true)->return(score)


well, because black has the first claim on draw, white cant
do anything against.That would require in the above example
that black indicates to play Kf7, like

18. ... Kf7 19.drawOnRepetition(true)
or
17. ... Kf7 18.drawOnRepetition(true)

therefore it also doesnt matter if it is an 2,3,x-fold repetition.

========================================================

gamehistory: 1.Kf5 Ke7 2. Ke5 Kf7 3. Kf5 Ke7 4. ...


root: Ke5(search) ...
ply1: ... drawOnRepetition(false),transCheck(true)->return(score).

required:

root: Ke5(search) ...
ply1: ... loopmovelist ! to detect Kf7 as drawOnRepetition


and now ? missed to loop the movelist,which is necessary to detect
the repetition draw.This can of course happen everywhere in the
tree.But is of course a disaster here near the root.

I am not sure if I undrstand your notation, so I will have to puzzle some more on this before I can make a sensible comemnt.

Well, i think it is shifting all branches by the same amount.
And that is desired (at least for my first thoughts).
I dont want to influence the moveChoice on a certain ply.

Anything that won't affect the move choice seems pointless. The problem is that your program chooses the wrong move (Kf5 in stead of Kd6). If is already prefers Kd6 over Kf5 you don't have a problem, and there is no reason to do anything. And if it prefers Kf5, it will continue to do that if you don't influence the move choice...

The _relative_ (static,dynamic) evaluation of different positions should
be the same as without that code.

This approach should handle identical positions on different
plies, which in late endgames occure very often.(think about going
for mate).

Let us think of a queen promotion in a Kpk endgame. So the static
evaluation might be between 50-150 centipawns. After a promotion
the static eval is about 900.

So the logic is: do promote in 20 instead of 30 -> (880 instead of 870)
like : go for mate in 20 instead of 30

of course, there is a lot of room to work on that idea.
Especially the scoreJump idea.

static eval: 80 [-100,500]
movlistscores:

- +30
- +40
- -15
- 400 (400-staticEval ->320 -> scoreJump)

now finding this position somewhere else in the tree
having a singular move, try to play it as early as you can...
and because 400-depth is still far away from the
other evaluations(30,40,-15), that would not destroy
the search result.

Well, at least i keep that in mind, and will have a close look
on your proposal.

If I understand your score-jump idea correctly, it is exactly what the delayed-loss bonus does: if the jump is in the branch, the score after the jump is propagated towards the root, causing a large difference between the search score and the eval in all nodes between root and jump. And in all that nodes of the side tht is going to get hit, the bonuc is then added. Thus effectively you count out the number of moves between the root and the score jump.

The delayed loss bonus also takes care that mate-in-N is preferred over mate-in-(N+1), but it is more general than that, and works on every score jump. By making it a fraction of the score jump, as in the example (where it is 3%), you automatically put the emphasis on the most important event within the horizon. I.e. when it sees the mate, moving that one move forward will likely outweigh the importance of speeding up the promotion 4 moves, and when you have the promotion within the horizon, speeding that up would outweigh the urgence to get the Pawn to 7th rank.

[Desperado]

...
am not sure if I undrstand your notation, so I will have to puzzle some more on this before I can make a sensible comemnt.
...

well, all i want to make clear is, that the move Ke5 _never_
can have a draw score.

if we examine it for the first time(by search) the move Kf7
cannot be a draw claim.(and simply all moves are loosing)
If we have already examined Ke5
the TT will hold the winning(losing) score, which will avoid to
detect the repetition. Kf7 and all other moves on that depth
wont be searched anymore, so no draw detection is possible.
(the losingScore of Kf7 becomes a draw score, the
search wont recognize that)

...Anything that won't affect the move choice seems pointless. ...

Kd5,Kf5,Kd6 are winning moves, while Kd6 leads to the
key position. Because all this moves will lead to the key position
by transposition, they all get the same evaluation from TT.

a: affecting moveChoice
=

Of course, now the move choice has to be influenced in a way
that the key position is reached as early as possible, which
can be done with your proposal, or the way i try to go.

so you are right, the move choice has to be affected.

b: not affecting moveChoice
=

What i had in mind was more like the scoreJump example.
In this case i dont want to change the move choice. So
i dont want that the score of 400 drops under the second
best score.So somewhere, nearer to the root case _a:_
will occur.

cheers, Michael

[Desperado]

PS:

...
am not sure if I undrstand your notation, so I will have to puzzle some more on this before I can make a sensible comemnt.
...

well, all i want to make clear is, that the move Ke5 _never_
can have a draw score.

if we examine it for the first time(by search) the move Kf7
cannot be a draw claim.(and simply all moves are loosing)
If we have already examined Ke5
the TT will hold the winning(losing) score, which will avoid to
detect the repetition. Kf7 and all other moves on that depth
wont be searched anymore, so no draw detection is possible.
(the losingScore of Kf7 becomes a draw score, the
search wont recognize that)

so, if Ke5 never can have a draw score, the score of Kf5
never can drop, because the sequence Kf5...Ke5 is not to
avoid by black.

(
- i think, as long as you dont have a static moveOrdering scheme
that prefers Kd6, this cannot be avoided, just a thought.
- Or the search needs the ability like delayed-loss-bonus or
sth similar, which would instruct the search to promote
as early as possible in this case with the move Kd6
)

[hgm]

well, all i want to make clear is, that the move Ke5 _never_
can have a draw score.

if we examine it for the first time(by search) the move Kf7
cannot be a draw claim.(and simply all moves are loosing)
If we have already examined Ke5
the TT will hold the winning(losing) score, which will avoid to
detect the repetition. Kf7 and all other moves on that depth
wont be searched anymore, so no draw detection is possible.
(the losingScore of Kf7 becomes a draw score, the
search wont recognize that)

OK, clear. I think that is good, and that TT scores always should reflect the score in case the position was 'premordial'. In Joker I make explicit effort to keep scores that are contaminated by rep-draws out of the table.

But that makes it indeed impossible to use rep-draws as a means to force the engine into making progress. Unless you refrain from doing hash cutoffs in the PV, as some engines do. Then it can never plan a PV that goes trugh a repetition, as it apparently does when it plays Kf4 an sees it as a winning move.

Kd5,Kf5,Kd6 are winning moves, while Kd6 leads to the
key position. Because all this moves will lead to the key position
by transposition, they all get the same evaluation from TT.

And from the search...

And that is both wrong! This is a major deficiency of minimax. If two different paths led to the same position, and one is long and the other short, they should _not_ get the same score. The score of the shorter path should be better for the winning side, (and thus automatically worse for the losing side). In the TT, but also in the search. The TT is merey a technical device to speed up the search, it should simply store the scores that a search would deliver.

Engines that understant that, will bungle games in won positions because they postpone progress forever. Rep-draws or 50-move rule can sometimes come to the rescue, but in the presence of hashing, they are unreliable kludges for this at best. And even if they could be made 100% reliable, they will lead to moronic play, like the Ktulu-Joker game in Leiden last year, where Ktulu needed 100 moves to win KQQK. (And half a year later, it was not so lucky, and drew in KQBK.)

Short paths to a win should be preferred (i.e. have higher score, because move selection is purely done by score). Minimax does not do that.

[Desperado]

And that is both wrong!

...

This is a major deficiency of minimax.

...

Short paths to a win should be preferred (i.e. have higher score, because move selection is purely done by score). Minimax does not do that.

Of course this is a major deficiency of minimax, that is why
we discuss the current thread, and to find a good solution
for it

sorry, i dont understand what you mean with "this is both wrong!"
(perhaps my english is too bad )

if we would have a asymetric plain minimax search, where
all paths end up with the position Kd6, all moves would get
back the same score !?. Through TT we create an artificial
horizon which is doing the same(for Ke5). AND of course this should not
happen.

Naturally making progress is also a matter of search.
But in this case a plain search would use the safty break
because it has no artificial horizon, so it would examine
the repetition.(while the TT pruns it away).

Because i know that my engine is doing progress (TT switched off),
i am interested now in a mechanism that doesnt allow the TT
to push desired results over any kind of horizon.
That is the real problem i see here.

Michael