Repetition check

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Repetition check

Post by hgm » Fri Mar 29, 2013 9:50 am

Fairy-Max used to recognize repetitions only if they were of positions occurring in the game history (which are locked into the hash table with maximum draft and score = 0). I now tried to improve on that by marking nodes that are in the current search path in the hash table, and returning a zero score when you hit on such a node:

Code: Select all

Search(int depth)
{
  hash = &hashTable[key];
  if(hash->signature == key) { // hit
    if(hash->depth & 128) return 0; // '128' bit flags repetition
    ... // other hash-hit stuff (check bounds and move)
    hash->depth |= 128; // mark entry as being searched
  }
  ...
  for&#40;iterDepth=startDepth; iterDepth<=depth, iterDepth++) &#123; // IID loop
    ...
    hash->signature = key;
    hash->depth = iterDepth | 128; // hash store
  &#125;
  hash->depth &= ~128; // unmark when leaving node
  return bestScore;
&#125;
As the draft of a marked entry is perceived as >= 128 (depth is an unsigned char field in the hash entry), it is effectively protected from replacement, so this should be a quite reliable way to detect repetitions of tree positions. In case of a hash miss the IID starts with a d=1 iteration, (in which it should not be able to reach the current position again), and at the end of it it creates the hash entry for the node, marked as 'busy', so that by the time it does reach a depth where it could repeat the position, it will be marked and recognized.

All simple enough, and (except perhaps speedwise) I don't see any reason why this should not work exactly the same as the more conventional looping over a stack of visited hash keys to detect a repetition.

It seems, however, that the version that does this is seriously crushed by the old one (some 100 Elo weaker?) When I remove the setting of the 'busy' flag in the initial probe this disappears, but I have the feeling that this is merely because I render the mechanism almost completely ineffective: in stable regions of the tree each node would already have been searched at a one-lower depth because of the iterative deepening in the root, and the IID loop would in fact not be a loop at all, but just executed once for the final depth, as all preceding iterations would have been satisfied from the hash probe. So you would mark the node as 'busy' only when you are done with it, and clear the flag immediately afterwards.

It is hard for me to believe that checking for repetitions of tree positions would hurt you this much. But I see it also in time-to-depth of simple end-game positions (where hashing has the biggest impact), like KPK. The original version shoots up to depth 23, and in the same time the one that checks repetitions can reach only depth 12 with about as many nodes. It is as if the repetition checking completely wrecks the hash table.

But this cannot be right, right? I don't actually mess with the score in the entry for the repeated nodes, I just hide a flag in their depth which is later removed. This should be fully equivalent to testing the repetition from a list of hash keys, and returning a 0 score based on that, without touching the hash entry. The only hash entries that could be affected are these of the parent node, when their natural score would be negative, and the possibility to repeat is offered due to a preceding clumsy manouevre of the winning side. But that would be exactly the same in the list-of-keys method.

So this really puzzles me. I cannot find a fault in the implementation, and the whole thing is so simple that one would not expect one. Is it essential to not store scores of nodes that found a move to a repeat in the hash table? I heard of people suppressing storing of 0 scores, which always struck me as a nasty kludge, because 0 scores could arise from the normal evaluation as well. And could this really be worth 100 Elo? :shock:

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetition check

Post by hgm » Fri Mar 29, 2013 10:52 am

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

Some actual data on the above test position:

Code: Select all

Original Fairy-Max &#40;4.8S&#41;
 26	+8.20	10.9M	0&#58;18.73	e1f2 e8f8 f2e3 f8g7 e3d4 g7f6 d4e4 f6e6 
 25	+1.85	4.4M	0&#58;08.19	e1f2 e8f8 f2e3 f8e7 
 24	+1.86	4.0M	0&#58;07.43	e1f2 e8d7 f2e3 d7e7 e3f4 e7e6 f4e4 e6d6 e4f5 
 23	+1.86	3.6M	0&#58;06.83	e1f2 e8d7 f2e3 d7e7 e3f4 e7e6 f4e4 e6d6 e4d4 
 22	+1.87	3.0M	0&#58;05.72	e1f2 e8d7 f2e3 d7e7 e3f4 e7d6 f4f5 d6e7 e2e4 
 21	+1.90	2.0M	0&#58;04.15	e1f2 e8d7 f2e3 d7d6 e3d4 d6e6 e2e4 e6d6 e4e5 d6e6 d4e4 e6e7 e4f5 e7d7 
 20	+1.93	1.3M	0&#58;02.88	e1f2 e8d7 f2e3 d7d6 e3d4 d6e6 e2e4 e6d6 e4e5 d6e7 d4e4 e7e6 
 19	+1.51	761909	0&#58;01.94	e1f2 e8d7 f2e3 d7d6 e3f4 d6e6 e2e3 e6f6 e3e4 f6g6 e4e5 g6g7 f4f5 g7f7 e5e6 f7e7 f5e5 e7e8 e5e4 
 18	+1.48	612798	0&#58;01.66	e1f2 e8d7 f2e3 d7d6 e3f4 d6e6 e2e4 e6f6 e4e5 f6e6 f4e4 e6e7 e4f5 
 17	+1.44	478310	0&#58;01.39	e1f2 e8d7 f2e3 d7d6 e3f4 d6d5 e2e4 d5d6 f4f5 d6e7 e4e5 e7f7 f5f4 
 16	+1.44	322845	0&#58;01.10	e1f2 e8d7 f2e3 d7d6 e3f4 d6d5 e2e4 d5d6 f4f5 d6c5 
 15	+1.32	220508	0&#58;00.88	e1f2 e8d7 f2e3 d7d6 e3d4 d6c6 e2e4 c6d6 e4e5 d6e6 d4e4 e6e7 e4f5 e7f7 e5e6 
 14	+0.94	180226	0&#58;00.74	e1f2 e8d7 f2e3 d7d6 e3d4 d6c6 e2e4 c6d6 e4e5 d6e6 d4e4 
 14	+0.80	140703	0&#58;00.59	e1d1 e8e7 e2e4 e7e6 d1e2 
 14	+0.79	127866	0&#58;00.54	e1f1 e8e7 e2e4 e7f7 f1e2 f7e6 e2f2 e6f6 f2e3 
 13	+0.85	110176	0&#58;00.47	e1f1 e8e7 e2e4 e7e6 f1e2 e6e5 
 13	+0.83	99812	0&#58;00.43	e2e3 e8f7 e1e2 f7f6 e3e4 f6e6 e2f2 e6e5 f2e3 
 12	+0.80	88763	0&#58;00.38	e2e3 e8f7 e1d2 f7e6 e3e4 e6e5 d2e3 e5f6 e3f2 f6e6 
 12	+0.71	72541	0&#58;00.30	e1f2 
 12	+0.70	69094	0&#58;00.28	e1f2 e8e7 f2e3 e7f6 e3f4 f6e6 e2e4 e6f6 e4e5 f6e6 f4e4 e6e7 
 11	+0.87	47144	0&#58;00.18	e1f2 e8e7 f2f3 e7e6 f3f4 e6d5 e2e4 d5d4 e4e5 d4d5 
 10	+0.82	35746	0&#58;00.15	e1f2 e8e7 f2f3 e7f6 f3g4 f6e5 g4g5 e5e4 g5f6 e4f4 
 10	+0.75	30842	0&#58;00.13	e1f1 e8f7 e2e4 f7e6 f1e2 e6e5 e2f3 
  9	+0.75	26114	0&#58;00.11	e1f1 e8f7 f1f2 f7f6 e2e4 f6e5 f2f3 
  9	+0.66	20762	0&#58;00.09	e1d2 e8d8 e2e4 d8d7 d2d3 d7e6 
  8	+0.90	10710	0&#58;00.06	e1d2 e8e7 d2d3 e7e6 d3e4 e6f6 e2e3 f6e6 
  7	+0.94	8916	0&#58;00.06	e1d2 e8e7 d2d3 e7f6 d3d4 f6f5 
  7	+0.83	5931	0&#58;00.03	e1f2 e8e7 e2e4 e7e6 f2e3 e6e5 e3f3 
  7	+0.81	5386	0&#58;00.01	e1f1 e8e7 e2e4 e7f6 f1g2 f6e6 
  7	+0.77	3874	0&#58;00.01	e1d1 e8e7 e2e4 e7e6 d1d2 e6e5 d2e3 
  6	+0.74	2188	0&#58;00.00	e1d1 e8e7 e2e4 e7e6 d1d2 e6e5 
  6	+0.73	1912	0&#58;00.00	e1f2 e8e7 e2e4 e7e6 f2e3 e6e5 
  5	+0.92	1029	0&#58;00.00	e1f2 e8e7 e2e4 e7e6 f2e3 
  5	+0.71	759	0&#58;00.00	e1d1 e8e7 e2e4 e7e6 d1e2 
  4	+0.75	429	0&#58;00.00	e1d1 e8e7 e2e4 e7e6 
  4	+0.71	364	0&#58;00.00	e1f1 e8e7 e2e4 e7e6 
  4	+0.60	293	0&#58;00.00	e1d2 e8e7 e2e4 e7e6 
  3	+0.90	192	0&#58;00.00	e1d2 e8e7 e2e4 
  3	+0.84	158	0&#58;00.00	e1f2 e8e7 e2e4 
  3	+0.64	126	0&#58;00.00	e1f1 e8e7 e2e4 
  3	+0.59	89	0&#58;00.00	e1d1 e8e7 e2e4 
  2	+0.78	35	0&#58;00.00	e1d1 e8e7 
  2	+0.74	17	0&#58;00.00	e1f2 e8e7 
  1	+0.84	9	0&#58;00.00	e1f2 
It sees the promotion at 26 ply (10M nodes, 18 sec). Then the improved version, with the marking of the hash entry as 'busy' on the initial probe (if it was a hit) suppressed:

Code: Select all

Max-Plus without rep-detect
 27	+8.15	44.5M	0&#58;21.56	e1d2 e8f8 d2d3 f8e7 d3e4 e7e6 e2e3 e6f6 e4f4 f6g6 f4e5 g6f7 
 26	+8.18	28.9M	0&#58;14.47	e1d2 e8f8 d2d3 f8e7 d3e4 e7e6 e2e3 e6f6 e4d5 f6e7 d5e5 e7d7 e5f6 d7e8 e3e4 e8f8 e4e5 f8g8 f6e7 g8g7 e7d7 g7g6 e5e6 
 25	+8.19	21.5M	0&#58;11.12	e1d2 e8f8 d2d3 f8e7 d3e4 e7e6 e2e3 e6f6 e4d5 f6e7 d5e5 e7f7 e5d6 f7g7 
 24	+8.15	17.9M	0&#58;09.50	e1d2 e8f8 d2d3 f8e7 d3e4 e7e6 e2e3 e6f6 e4d5 f6e7 d5e5 e7d7 e5f6 
 23	+2.01	16.7M	0&#58;08.91	e1d2 e8f8 d2d3 f8e7 d3e4 e7e6 e4d4 
 22	+2.04	13.1M	0&#58;07.17	e1d2 e8e7 d2d3 e7f7 d3d4 f7e6 d4e4 e6f6 e4d4 
 21	+2.08	8.9M	0&#58;05.16	e1d2 e8e7 d2d3 e7d7 d3d4 d7c6 e2e3 c6d6 e3e4 d6c6 e4e5 c6c7 d4d5 c7d7 
 20	+1.94	5.0M	0&#58;03.22	e1d2 e8e7 d2d3 e7f6 d3d4 f6e6 d4e4 e6f7 e4f5 f7g7 e2e4 g7h6 e4e5 h6h7 f5f6 
 19	+1.49	2.8M	0&#58;02.12	e1d2 e8e7 d2d3 e7f6 d3d4 f6e6 e2e3 e6d7 d4d5 d7e8 e3e4 e8e7 
 18	+1.45	2.0M	0&#58;01.66	e1d2 e8e7 d2d3 e7f6 d3d4 f6e6 e2e4 e6d6 e4e5 d6e6 d4e4 e6f7 e4d5 
 17	+1.44	1.3M	0&#58;01.28	e1d2 e8e7 d2d3 e7e6 d3d4 e6f6 e2e4 f6e6 e4e5 e6e7 d4d5 e7f7 e5e6 f7e7 
 16	+1.47	664681	0&#58;00.89	e1d2 e8e7 d2d3 e7d6 d3d4 d6c6 e2e4 c6d6 e4e5 d6e6 d4e4 e6f7 e4d5 f7g6 e5e6 g6f6 
 15	+1.47	493640	0&#58;00.75	e1d2 e8e7 d2d3 e7f6 d3d4 f6e6 e2e4 e6d6 e4e5 d6e6 d4e4 
 14	+1.34	338013	0&#58;00.58	e1d2 e8e7 d2d3 e7e6 d3d4 e6d6 e2e4 d6e6 e4e5 e6f5 d4d5 f5f4 e5e6 f4f5 
 13	+0.91	217974	0&#58;00.42	e1d2 e8e7 d2d3 e7e6 e2e4 e6f6 d3e2 f6e5 e2e3 e5f6 e3f2 f6e5 f2e3 
 13	+0.82	178473	0&#58;00.36	e1f2 e8e7 e2e4 e7f6 f2e3 f6e5 e3f3 e5e6 f3g4 e6e5 g4f3 
 12	+0.79	142429	0&#58;00.29	e1f2 e8e7 e2e4 e7f6 f2e3 f6e5 e3f3 e5e6 f3f4 e6f6 
 12	+0.75	96280	0&#58;00.21	e1d2 e8e7 e2e4 e7f6 d2c3 f6g6 c3d3 g6f7 
 11	+0.87	62438	0&#58;00.15	e1d2 e8e7 e2e4 e7d6 d2d3 d6e5 d3e3 e5d6 e3d4 
 11	+0.83	54557	0&#58;00.13	e1d1 e8d7 e2e4 d7e6 d1e2 e6f6 e2d2 
 10	+0.81	46857	0&#58;00.12	e1d1 e8d7 e2e4 d7e7 d1c2 e7d6 
 10	+0.79	40515	0&#58;00.11	e1d2 e8e7 d2c3 e7e6 e2e4 e6e5 c3d3 
  9	+0.79	29940	0&#58;00.10	e1d2 e8e7 d2d3 e7e6 e2e3 e6e5 d3c3 
  9	+0.66	23396	0&#58;00.09	e1f2 e8f7 f2e3 f7g6 e3e4 g6g5 e4e5 g5g4 e2e4 
  8	+0.89	11006	0&#58;00.05	e1f2 e8e7 f2e3 
  8	+0.88	9490	0&#58;00.05	e1d2 e8e7 d2e3 e7e6 e3e4 e6f6 e2e3 f6e6 
  8	+0.81	7007	0&#58;00.04	e1d1 e8d7 e2e4 d7e7 d1c2 e7f6 c2d3 f6e5 
  7	+0.83	5398	0&#58;00.03	e1d1 e8d7 e2e4 d7d6 d1d2 d6e6 
  7	+0.82	4449	0&#58;00.03	e1d2 e8e7 d2e3 e7e6 e3e4 
  6	+0.77	1831	0&#58;00.00	e1d2 e8e7 e2e4 e7e6 d2d3 e6e5 
  6	+0.65	1421	0&#58;00.00	e1f2 e8e7 e2e4 e7e6 f2e3 e6e5 
  5	+0.92	834	0&#58;00.00	e1f2 e8e7 e2e4 e7e6 f2e3 
  5	+0.81	529	0&#58;00.00	e1d2 e8e7 e2e4 e7e6 d2e3 
  4	+0.87	344	0&#58;00.00	e1d2 e8e7 e2e4 e7e6 
  4	+0.76	152	0&#58;00.00	e1d1 e8d7 e2e4 d7e6 
  3	+0.86	84	0&#58;00.00	e1d1 e8e7 e2e4 
  3	+0.80	45	0&#58;00.00	e1f2 e8e7 e2e4 
  2	+0.76	10	0&#58;00.00	e1f2 e8e7 
  1	+0.79	5	0&#58;00.00	e1f2 
This one takes 14 sec to reach 26 ply, but it already sees the promotion at 24 ply. (9.5 sec, but 18M nodes. It counts nodes differently, though.) It has a more advanced replacement scheme (shallowest of two in stead of always replace), but this was with 128 MB hash, and the entire tree for this simple end-game will easily fit in that, so that replacement is hardly an issue.

But now with marking of the hash entry as busy in the initial probe hit (uncommenting the hash->depth |= 128):

Code: Select all

Max-Plus with repetition detect
 13	+0.93	20.4M	0&#58;19.70	e1d2 e8e7 e2e4 e7e6 d2e3 e6e5 e3f3 e5f6 f3f4 f6e6 e4e5 e6d5 f4f5 
 12	+0.77	12.9M	0&#58;12.99	e1d2 e8e7 e2e4 e7e6 d2d3 e6e5 d3e3 e5d6 e3f4 d6e6 e4e5 e6d5 
 12	+0.76	8.7M	0&#58;08.83	e2e3 e8e7 e1e2 e7d6 e3e4 d6e6 e2d3 e6d6 d3d4 d6e6 e4e5 e6f5 
 12	+0.61	6.7M	0&#58;06.95	e2e4 e8e7 e1e2 e7d6 e2f3 d6e5 f3e3 e5f6 e3d4 f6g5 d4e5 g5g4 
 11	+0.86	4.3M	0&#58;04.64	e2e4 e8d7 e1d2 d7e6 d2e3 e6e5 e3f3 e5d4 f3f4 d4d3 e4e5 
 11	+0.84	3.4M	0&#58;03.67	e2e3 e8e7 e1e2 e7d6 e3e4 d6e6 e2d3 e6e5 d3e3 e5f6 e3f4 
 11	+0.73	2.6M	0&#58;02.90	e1f2 e8e7 e2e4 e7e6 f2f3 e6f6 f3f4 f6e6 e4e5 e6d5 f4f5 
 11	+0.65	1.7M	0&#58;02.04	e1d1 e8f7 e2e4 f7e6 d1e2 e6f6 e2f3 f6g5 f3e3 g5g4 e3d4 
 10	+0.77	786157	0&#58;01.08	e1d1 e8e7 e2e4 e7f6 d1e2 f6e6 e2d3 e6e5 d3e3 e5f6 
 10	+0.66	507430	0&#58;00.78	e1f2 e8e7 e2e4 e7f6 f2f3 f6e5 f3e3 e5d6 e3f4 d6c5 
  9	+0.90	197780	0&#58;00.44	e1f2 e8d7 f2f3 d7e6 f3f4 e6d5 e2e3 d5e6 e3e4 
  8	+0.93	88832	0&#58;00.34	e1f2 e8e7 e2e4 e7e6 f2f3 e6e5 f3e3 e5e6 
  8	+0.91	54565	0&#58;00.23	e1d1 e8e7 e2e4 e7d6 d1e2 d6e6 e2d3 e6e5 
  7	+0.76	32284	0&#58;00.21	e1d1 e8d7 e2e4 d7e6 d1e2 e6e5 e2e3 
  7	+0.75	25461	0&#58;00.21	e2e3 e8e7 e1e2 e7e6 e3e4 e6e5 e2e3 
  7	+0.73	14767	0&#58;00.10	e1d2 e8d7 d2d3 d7d6 d3d4 d6e6 e2e4 
  6	+0.93	2943	0&#58;00.05	e1d2 e8e7 e2e4 e7e6 d2e3 e6e5 
  5	+0.90	1687	0&#58;00.05	e1d2 e8e7 e2e4 e7e6 d2d3 
  5	+0.81	762	0&#58;00.05	e1f2 e8e7 e2e4 e7e6 f2e3 
  4	+0.90	174	0&#58;00.05	e1f2 e8e7 e2e4 e7e6 
  3	+0.94	85	0&#58;00.05	e1f2 e8e7 e2e4 
  3	+0.88	67	0&#58;00.05	e1f1 e8e7 e2e4 
  3	+0.74	49	0&#58;00.04	e2e3 e8e7 e1e2 
  2	+0.76	21	0&#58;00.04	e2e3 e8e7 
  2	+0.70	14	0&#58;00.04	e1f1 e8e7 
  2	+0.62	10	0&#58;00.04	e1f2 e8e7 
  1	+0.79	5	0&#58;00.04	e1f2 
In nearly the same time as where the other reached 27 ply, it now reaches only 13. It also reports only half the nodes.

In the mean time I have also tried suppressing hash store if bestScore = 0, but this does hardly alter anything.

User avatar
Codesquid
Posts: 138
Joined: Tue Aug 23, 2011 8:25 pm
Location: Germany
Contact:

Re: Repetition check

Post by Codesquid » Fri Mar 29, 2013 11:12 am

Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.
nanos gigantium humeris insidentes

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetition check

Post by hgm » Fri Mar 29, 2013 11:38 am

In this position (Pawns + Kings only) it should not do null moves. (Except for check detection, testing if a QS after null move returns a +INF score. But a position with a +INF score can never occur in the path to the current node; it would always abort the branch there and then.)

In general you have a good point, though, as Fairy-Max can do two null moves in a row (or in fact any number of null moves). Perhaps this is the main reason for the 100 Elo drop, and not the fact that it loses some depth in the very late end-game. Any null move of a side that is ahead can be refuted by another null move, as this now causes a repeat. This effectively disables null-move pruning. So the combination of double null move and null-spanning repeats could be a disastrous combination.

Unfortunately the scheme with the hash flag cannot easily recognize if the repeat was null-move spanning. But I can check if the Elo loss disappears when I disable pruning by a 'null after null'.

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetition check

Post by hgm » Fri Mar 29, 2013 1:34 pm

OK, I solved the mystery. There was an unfavorable interaction between the 'busy' flag and the existing hash store code. The latter suppressed overwriting entries with draft 99, because these are the positions from the game history locked into the hash. But because of the micro-Max ancestry this was coded as if(depth < 99) in stead of if(depth != 99), to save one character. But setting the busy flag makes the depth >= 128, so that the position would not be saved in the hash even by the node searching it. So effectively this was disabling the hash table completely.

The issue of automatic repeat after double null moves is still a serious one, however. This cannot be tolerated.

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetition check

Post by hgm » Fri Mar 29, 2013 2:31 pm

With the fix and disabling null-move pruning after null move, it now seems reasonably even. (Only 45 games so far, but before I was seeing scores like 11-1 in some of the playing agents...)

There is of course no big Elo gain from this (it could plan for a perpetual and even sacrifice material for it, or see it coming, but how often will that opportunity arise?). Nevertheless it is a big deal for me to have full repetition detection, because this prevents crashing due to stack overflow in positions where mutual perpetual check is possible (so that the check extension extends indefinitely). So with it I can safely run games with Nightriders, or where white and black have different King types, so that the Kings could start chasing each other. With an orthodox King versus a Royal Knight virtually all games crashed sooner or later.

User avatar
lucasart
Posts: 3040
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Repetition check

Post by lucasart » Fri Mar 29, 2013 2:32 pm

Codesquid wrote:Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.
This is interesting. Are you suggesting that it's best to xor something in the zobrist key when doing/undoing a null move, to make sure that there won't be any repetition between positions before/after the null move? The null move does change the zobrist via the turn of play already.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Repetition check

Post by Sven » Fri Mar 29, 2013 2:55 pm

lucasart wrote:
Codesquid wrote:Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.
This is interesting. Are you suggesting that it's best to xor something in the zobrist key when doing/undoing a null move, to make sure that there won't be any repetition between positions before/after the null move? The null move does change the zobrist via the turn of play already.
But the latter does not prevent detecting a repetition of a previous position with the same side to move. In fact you will usually check every second hash key only since there is no point in checking for a repetition of positions with the opponent to move, so the effect of changing the turn when making the null move is not relevant here.

Isn't the typical solution to set the half move clock to 0 when making a null move? That makes the null move irreversible for the 50 moves rule, and implicitly also for repetition checks if your hash key comparison loop does not go back further than the value of the half move clock.

Sven

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetition check

Post by hgm » Fri Mar 29, 2013 3:13 pm

I think what Lucas was proposing is to invalidate the incremental key, so that no position in the sub-tree after that will ever match. This is not recommended, however, if you want to use that same key for hash probing too.

When you do a linear search through a key stack, you can simply stop when you pass the first null move, as you mention. When you have a special hash table for repeat keys, as I sometimes do, you can store the ply number with the key, and keep a global variable to hold the ply number of the last null move, and then compare the two to see if the repeat was null-spanning. With the Fairy-max implementation in the hash table this is a bit difficult, though: in case the repeat would be null-spanning, you would still want to have the hash draft available to decide if you can take a normal cutoff. So you cannot use the draft field in the hash entry to store the ply number in stead. And adding an extra field in millions of entries that would be used just in a few dozen would be very wasteful.

So for now I guess I will live with null-spanning repeats, which according to Bob was even a winner. As long as you don't allow double null move.

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Repetition check

Post by bob » Fri Mar 29, 2013 7:12 pm

Sven Schüle wrote:
lucasart wrote:
Codesquid wrote:Does Fairymax do nullmoves? Repetition information carried over from before the null move seems problematic.
This is interesting. Are you suggesting that it's best to xor something in the zobrist key when doing/undoing a null move, to make sure that there won't be any repetition between positions before/after the null move? The null move does change the zobrist via the turn of play already.
But the latter does not prevent detecting a repetition of a previous position with the same side to move. In fact you will usually check every second hash key only since there is no point in checking for a repetition of positions with the opponent to move, so the effect of changing the turn when making the null move is not relevant here.

Isn't the typical solution to set the half move clock to 0 when making a null move? That makes the null move irreversible for the 50 moves rule, and implicitly also for repetition checks if your hash key comparison loop does not go back further than the value of the half move clock.

Sven
We had this discussion last year. And the net result was that it is BETTER to leave repetition detection on through null-moves. I don't remember the exact Elo numbers, but I suppose one might be able to do a search to find the thread...

Post Reply