Repetition-Zugzwang

[Desperado]

Hello everyone,

[d]8/5k2/8/4K3/4P3/8/8/8 w - - 0 1

The problem:

1.Kf5 Ke6 2. Ke5 Kf6 3. Kf5 Ke6 4. Ke5 -> draw!

1.
===

Of course this position is only one example for, i call it
_Repetition-Zugzwang_.

2.
===

pls assume the problem is produced somewhere in the tree
during the search, and is not a root position.

Because after 3.Kf5 Ke6 _4.Ke5_ is the only winning move,
which leads unfortunatelly to a repetitionDraw.

(because of that: _RepetitionZugzwang_)

trials:
====

- first i checked the repetition detection code, to be sure
it works like it should

- tried to fix that thing with a depth-parameter on evaluation
like it is usually done with mateScores.

- tried to Extend trivial endgames on a oneTime Repetition,
to work around that thing.

and some other things...

result:
=====

nothing helped

conclusion:
========

i am pretty sure, the problem is caused due to hashtables,
which seem to "workaround" the repetition detection.

Second, black isnt able to refute Kf5, or simply has no threat
to force white to make progress.

Well, for now i dont have any idea how to solve this.

any ideas ?

regards

[Roman Hartmann]

First make sure it is indeed the hash table that causes this problem. Disable the hash table (don't allow any cut-offs due hash table hits) and see if the position still fails.

I too had problems with draw scores polluting my hash table and I solved that by not storing any draw scores in the hash table. I don't need my hash table for repetition detection, I'm using a move stack to recognize draws.

Roman

[Desperado]

Thx Roman for reply.

1.
===
Actually it is the transtable. i switched it off, and ran my
testmatchSuite(trivial-endings). All results are like they should be,
against a prog with access to nalimov.

! even my KbnK endgame works now.

2.
===

ok, first step is done. Now pls let me understand, why
_not_ storing draws may help.
I dont see the relation between the given problem and draw scores.

it is more like not playing forced-lines because the draw is
put somehow over an artificial horizon caused by the transtable.

like:

depth(x) : (move)

depth(x+1): htb(returnWinningScore,_this is no drawScore_)
(artificial Horizon i am talking of)

depth(x+2): Depth With Draw Detection By Repetition NotReached

But if i miss sth. then what drawScores are you talking of ?

a: - draw on stage
b: - draw returned as searchResult
c: - a+b

thx in advance, Michael

[Roman Hartmann]

ok, first step is done. Now pls let me understand, why
_not_ storing draws may help.
I dont see the relation between the given problem and draw scores.

Let's say my rep-detection code finds a two-fold somewhere in the tree and stores this score in the TT. If this positions occurs later again the TT will return a draw score although the path to this position might be different.

But if i miss sth. then what drawScores are you talking of ?

Draw by repetition. I don't know if that is the problem you have now of course but it was the problem I had.

Roman

[hgm]

I still don't see the why this problem has anthing to do with repetitions or zugzwang. Kf5 is a silly move. Kd6 is the only move that makes progress in that position. That is true whether repetitions are counted as draws as well as when you were allowed to repeat forever.

From the position with K on f5 you can indeed win by playing Ke5. But if you are already on e5, that would always be slower. So why play it?

[Desperado]

Hello HG,

of course Kf5 is a silly move...

but

1. if a move _has to be done_ , in this case after 1.Kf5 Ke6 2.Ke5
it is _a kind of_ zugzwang. Maybe we should better use the term
singular move here.

2. i think it can always happen, this position only should illustrate
a class of problems.

in this example:

a: .... 11. Kf5 Ke6 12.Kd6 ..searchAndStoreToTrans

now somewhere else in the tree

b: 16. Kf5 (retrieveFromTrans)...

but here Ke6 may lead to a repetitionTrueCase.
so finally the singularMove cannot be played because
it leads to repetition.

maybe it is a thing of moveOrdering, but i am not only talking
of this simple KpK endgame above.

another example is in the KbnK endgame, to get the king out of the
safe corner.

[d]6k1/8/3N1K2/8/8/8/2B5/8 w - - 0 1

1.Nf7 Kf8 2.Nd6 Kg8 3.Nf7 Kf8 where at the end Nf7 after the movesequence is played out, the Nf7 isnt choosed again because
of repetition.

Michael

[Desperado]

Hello HG,

of course Kf5 is a silly move...

but

1. if a move _has to be done_ , in this case after 1.Kf5 Ke6 2.Ke5
it is _a kind of_ zugzwang. Maybe we should better use the term
singular move here.

2. i think it can always happen, this position only should illustrate
a class of problems.

in this example:

a: .... 11. Kf5 Ke6 12.Kd6 ..searchAndStoreToTrans

now somewhere else in the tree

b: 16. Kf5 (retrieveFromTrans)...

but here Ke6 may lead to a repetitionTrueCase.
so finally the singularMove cannot be played because
it leads to repetition.

maybe it is a thing of moveOrdering, but i am not only talking
of this simple KpK endgame above.

another example is in the KbnK endgame, to get the king out of the
safe corner.

[d]6k1/8/3N1K2/8/8/8/2B5/8 w - - 0 1

1.Nf7 Kf8 2.Nd6 Kg8 3.Nf7 Kf8 where at the end Nf7 after the movesequence is played out, the Nf7 isnt choosed again because
of repetition.

Michael

2 more thoughts on this:

1:

if you wouldnt score a mateValue with

score = lbound + cdp(currentDepth)

during the search, any engine might play silly moves
instead of going for mate, as long as the mate cannot be
refuted.

(as long the singular move cannot be refuted, the same
thing happens here !).

2:
because mateValues are absolut, these ones can
easily handeld with a depth paramter.
But in the given examples, there arent any absolut values.
So how to avoid search-degeneracy ?

so maybe 2 solutions come to my mind:

1: cleanup the scores in the hashtable before searching again

or

2: add/sub depth parameter when storing to trans,
to force playing the move as early as possible.

[Edmund]

I still don't see the why this problem has anthing to do with repetitions or zugzwang. Kf5 is a silly move. Kd6 is the only move that makes progress in that position. That is true whether repetitions are counted as draws as well as when you were allowed to repeat forever.

From the position with K on f5 you can indeed win by playing Ke5. But if you are already on e5, that would always be slower. So why play it?

The only reason I could see would be a "moves to go" Timecontrol and the intelligent engine running out of time makes a deliberate repetition to get more time on the clock.

[hgm]

Well, even after it has played the silly move, returning to e5 is only a first repetition, and not a draw yet. So it stll can win, and should play Ke5 without hesitation. (Only micro-Max with its simplified treatment of repetition detection, where it just puts all game positions in the hash with score 0, would not be able to see this.

If you have already done it twice, then you have bungled the game, and there is nothing you can do.

But the solution is not play the silly move that gets you into such trouble. Then you don't have to worry how to get out again.

2: add/sub depth parameter when storing to trans,
to force playing the move as early as possible.

Indeed. That is why my engines do not suffer from this kind of behavior. (As we discussed recently in the infinitely-delayed promotion thread). The delayed loss bonus takes care of that. Promotion in 11 ply is discredited more than promotion in 7 ply, and that is reflected in the hash-table score of a position with the King on f5 vs d6. So it does not matter if you have hash cutoffs or actually do the search, Kf7 will get a lower score than Kd6, because you will reach the same position (where you finally promote) through a longer path.

[metax]

I think I know what you mean. Your problem is that if you, in contradiction to the FIDE rules, already treat a two-fold repetition as a draw (which many engines do), the engine will score the position after 1.Kf5 Ke7 as a draw (zugzwang is indeed the wrong word here, which would have been singular move). I haven't got any kpk endgame recognizers and my engine's output for the position after 1.Kf5 Ke7 is the following:

Code: Select all

FEN: 8/4k3/8/5K2/4P3/8/8/8 w - - 2 2 

ChessMind:
  5/12	00:00	       2.135	16.000	+2,13	e4e5 Ke7d7 e5e6+ Kd7d6 Kf5f6 Kd6c7
  6/15	00:00	       3.629	28.000	+2,19	e4e5 Ke7d7 e5e6+ Kd7d6 Kf5f6 Kd6c7 Kf6e5
  7/16	00:00	       7.480	52.000	+2,11	e4e5 Ke7d7 e5e6+ Kd7d6 Kf5f6 Kd6c7 Kf6e5 Kc7d8
  8/22	00:	+1,95	e4e5 Ke7d7 e5e6+ Kd7e8 Kf5f6 Ke8f8 Kf6e5 Kf8e7 Ke5d5
  9/20	00:00	      34.261	182.000	+2,29	e4e5 Ke7d7 e5e6+ Kd7e8 Kf5e4 Ke8f8 Ke4f4 Kf8e7
 10/21	00:00	      44.890	220.000	+2,03	e4e5 Ke7d7 e5e6+ Kd7e8 Kf5e4 Ke8e7 Ke4d5 Ke7e8 Kd5d6 Ke8d8 Kd6e5
 11/24	00:00	      82.672	329.000	+1,93	e4e5 Ke7f7 Kf5g4 Kf7e6 Kg4f4 Ke6d7 Kf4e4 Kd7e6 Ke4d4 Ke6e7 Kd4d5
 12/24	00:00	     100.527	356.000	+1,93	e4e5 Ke7f7 Kf5g4 Kf7e6 Kg4f4 Ke6d7 Kf4e3 Kd7e6 Ke3e4 Ke6e7 Ke4d4 Ke7f7
 13/28	00:00	     122.374	390.000	+1,77	e4e5 Ke7f7 Kf5g4 Kf7e6 Kg4f4 Ke6f7 Kf4e3 Kf7e6
 14/26	00:00	     147.222	427.000	+1,77	e4e5 Ke7f7 Kf5g4 Kf7e6 Kg4f4 Ke6f7 Kf4e3 Kf7e6 Ke3d4 Ke6e7 Kd4c5 Ke7d7 Kc5d5 Kd7e7
 15/29	00:00	     174.074	462.000	 0,00	e4e5 Ke7f7 Kf5g4 Kf7e6 Kg4f4 Ke6f7 Kf4e3 Kf7e6 Ke3d4 Ke6e7 Kd4c5 Ke7d7 Kc5d5 Kd7e7 Kd5e4
 15/30+	00:00	     214.997	490.000	+1,28	Kf5g4
 16/32	00:00	     304.510	540.000	+1,35	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e7 Kd4c3 Ke7d6
 17/35	00:00	     397.556	591.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6
 18/36	00:00	     467.721	610.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2
 19/37	00:01	     555.034	634.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2
 20/39	00:01	     693.866	673.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1
 21/42	00:01	     850.682	698.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 22/43	00:01	   1.003.535	714.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 23/45	00:01	   1.167.131	733.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 24/48	00:02	   1.353.629	747.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 25/48	00:02	   1.562.949	764.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 26/54	00:02	   1.848.278	779.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 27/53	00:02	   2.152.442	792.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 28/56	00:03	   2.573.515	804.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 29/65	00:03	   2.907.070	813.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 30/66	00:04	   3.343.851	820.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 31/67	00:05	   3.991.617	827.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 32/71	00:05	   4.577.163	833.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 33/75	00:06	   5.386.342	835.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2
 34/76	00:07	   6.081.407	838.000	 0,00	Kf5g4 Ke7f6 Kg4f3 Kf6e5 Kf3e3 Ke5d6 Ke3d4 Kd6e6 Kd4c3 Ke6d6 Kc3d2 Kd6e5 Kd2e1 Ke5xe4 Ke1d2 Ke4f3 Kd2e1 Kf3g2 Ke1d2 Kg2h1 Kd2e1 Kh1g2

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.