Website founded by Milan Velimirović in 2006
20:23 UTC
 
MatPlus.Net Forum General 50 moves/3 repeats from starting position 



You can only view this page!
  (1) Posted by Hauke Reddmann [Thursday, Sep 3, 2020 09:27]  50 moves/3 repeats from starting position This came up in my arbiters course in a case.
Believe it or not, some arbiter on an international
tournament declared a game drawn after 75 moves!
Somehow he misunderstood the 75 move rule... (facepalm)
Quickly, a discussion came up about the theoretic
possibility of a threefold repeat instead when the
players only move knights and rooks. I said that
such a game can take far longer than 75 moves before
a threefold repeat occurs. But how long? (Assume that
the 50/75 move rule does NOT hold.)
A quick Fermi calculation says 2*2*2*2*30*30*3, but
the exact value will be difficult to obtain without
a program, due to the collisions.   (2) Posted by Joost de Heer [Thursday, Sep 3, 2020 12:12]  Don't forget the counter reset after someone moves a rook. There are 4 resets possible, and after every reset you get double the positions that can be repeated.   (3) Posted by Jakob Leck [Thursday, Sep 3, 2020 19:58]  What would Fermi say to your calculation, Hauke? ;)
For the possible number of positions take the 2^4 positions of the rooks. Then there are 36 possible squares for the knights, two of which have to be excluded for each side because of checks. Thus we have to multiply by (34 choose 2)=34*33/2 and (32 choose 2)=32*31/2 and we get n=4452096 positions. Note that this number is slightly off because positions where knights of one colour occupy the squares which are already excluded for the other side because of checks are not treated properly. Also note that through a parity argument each position already determines who is to move. Say that half of the positions are white to move, then we can play through all of them in about n/2 moves and before getting to a threfold repetition we can play through them twice, thus we can make about 4.4 million moves, well above the 75move mark. :)
But then, of course, there are the collisions you mention, which make things difficult...   (4) Posted by Hauke Reddmann [Friday, Sep 4, 2020 10:34]  Jakob, you're entirely right with the OO based remark,
which I forgot since the question occurred within the
50/75 move rule. Where it has no relevance, see other
thread :)   (5) Posted by Andrew Buchanan [Friday, Sep 4, 2020 20:21]  Building on what Joost and Jakob said here, and also discussions with Jakob, thank you.
The rooks give us 1+2+4+8+16 = 31 times the number of positions. None of the knights can deliver check, because the response must be a capture. There are 32 squares which either colour knight can occupy successfully and 4 squares which can only be occupied by one colour knight. Call these 4 squares mono squares. So the total number of knight arrangements is:
C(32,4)*6 [0 S on mono, 6 perms of 4 S.]
+4*C(32,3)*3 [1 S on mono, 3 perms of 3 S.]
+2*C(32,2) [2 friendly S on mono, 1 perm of the other 2 S.]
+4*C(32,2)*2 [2 opposed S on mono, 2 perms of the other 2 S.]
+4*C(32,1) [3 S on mono, 1 perm of the other S.]
+1 [4 S on mono.]
Then divide by 2 because we want double moves, and multiply by 2 because each position can occur twice safely.
This gives an upper bound of 31 * 280,369 = 8,691,439.0 moves.
However, the actual number is not quite this big, for two reasons:
(1) There are a few blocked positions where one guy's pieces (knights + prebudged rooks) are retroblocked, and parity says this guy just moved. In principle could tot these all up exactly.
(2) What would be harder I suspect is discovering if one can construct a "hamiltonian path" (= grandiose version of knight's tour) across all or most of these positions twice. Sufficient criteria for an arbitrary graph to be hamiltonian involve *much* greater connectivity than we have here. As the graph is bipartite, and there may be more positions with one parity than the other. Nevertheless my lazy intuition is that if we lob off a few positions we could indeed get a very large hamiltonian graph.   (6) Posted by Hauke Reddmann [Saturday, Sep 5, 2020 10:06]  @Andrew: the trouble that the positions might not be connected
by a Hamiltonian path was exactly what kept me from writing a
quick FORTRAN program :)   No more posts 
MatPlus.Net Forum General 50 moves/3 repeats from starting position 


