[Retros] happy prime new year

[Francois Labelle]

Hi Noam and Andrew,

I could extend my list of queue problems past 20, but instead I was more 
interested in doing the same thing in one-sided chess. I think it's a 
more basic question that should be answered first because a two-sided 
problem is the combination of two one-sided problems and a subtraction 
(due to interaction between the two colors), which is a lot more complex.

Here it is: for each number n, I found a shortest linear extension 
problem with n solutions, and I give one of the solutions (because I 
think that it is more readable than a FEN for short games).

1: (empty game)
2: 1. b4 2. d4
3: 1. b4 2. d4 3. Bh6
4: 1. b4 2. d3 3. Be3 4. Bxa7
5: 1. d4 2. Bh6 3. e4 4. Bd3
6: 1. b4 2. d4 3. f4
7: 1. Nc3 2. d3 3. Be3 4. Rc1 5. Bxa7
8: 1. b4 2. d4 3. Bh6 4. d5
9: 1. d4 2. e4 3. Be3 4. Ba6 5. Bxb7
10: 1. b4 2. d3 3. Be3 4. Bxa7 5. b5
11: 1. d4 2. Bh6 3. g4 4. d5 5. g5
12: 1. b4 2. d4 3. Bh6 4. g4
13: 1. d4 2. e3 3. Qf3 4. Bd3 5. Qxb7 6. d5
14: 1. d4 2. e4 3. Be3 4. Bd3 5. d5
15: 1. b4 2. c4 3. Qa4 4. Qxa7 5. c5
16: 1. d4 2. Bh6 3. e4 4. Bd3 5. e5
17: 1. c3 2. Qb3 3. f4 4. Qxb7 5. b4 6. Qxa8 7. Qf3
18: 1. d4 2. Bh6 3. e4 4. Bd3 5. d5
19: 1. c4 2. Nc3 3. Qa4 4. e4 5. Qxa7 6. Qe3
20: 1. b4 2. d3 3. Be3 4. f4 5. Bxa7
21: 1. Nc3 2. d4 3. Be3 4. Rc1 5. d5 6. Bxa7
22: 1. d4 2. Bh6 3. Qd3 4. g4 5. Qg3 6. g5
23: 1. Nc3 2. e4 3. Qh5 4. Ba6 5. Nce2 6. Bxb7
24: 1. b4 2. d4 3. f4 4. h4
25: 1. b4 2. d4 3. Bh6 4. e4 5. Bd3
26: 1. Nc3 2. d3 3. Be3 4. Rc1 5. Nd5 6. Bxa7
27: 1. d4 2. e4 3. Be3 4. Bd3 5. Ke2 6. d5
28: 1. e4 2. Ba6 3. c4 4. f4 5. Qf3 6. Bxb7
29: 1. e3 2. Qf3 3. Bb5 4. g4 5. Qxb7 6. Qxa8 7. Qg2
30: 1. b4 2. d4 3. Bh6 4. e4 5. Bb5
31: 1. Nf3 2. e4 3. Ba6 4. Ne5 5. Nc4 6. Bxb7 7. Bxa8
32: 1. d4 2. e4 3. Be3 4. Qg4 5. Bd3 6. Qxg7
33: 1. Na3 2. c4 3. Qa4 4. Nc2 5. Qxa7 6. c5
34: 1. d4 2. Bh6 3. g4 4. Bg2 5. Bxb7 6. g5 7. Bxa8
35: 1. d4 2. e4 3. Be3 4. Ba6 5. d5 6. Bxb7
36: 1. b4 2. d3 3. Be3 4. Qc1 5. Kd2 6. Bxa7
37: 1. d4 2. e4 3. Be3 4. Bb5 5. Qd3 6. e5
38: 1. d4 2. Bh6 3. e4 4. Bb5 5. Qd3 6. d5
39: 1. c4 2. Qa4 3. e4 4. Qxa7 5. c5 6. Ba6 7. Qxa8
40: 1. b4 2. d4 3. Bh6 4. e4 5. d5
41: 1. Nc3 2. g4 3. Bg2 4. Kf1 5. Bxb7 6. Nd5 7. Bxa8
42: 1. Nc3 2. b4 3. d3 4. Be3 5. Rc1 6. Bxa7
43: 1. d4 2. Nd2 3. e3 4. Qh5 5. Bd3 6. Ke2 7. Ndf3
44: 1. Nf3 2. d3 3. Be3 4. Qc1 5. Bxa7 6. Nfd2 7. f3
45: 1. c4 2. Qa4 3. d4 4. Bh6 5. Qxa7 6. c5
46: 1. Nh3 2. e3 3. Qf3 4. Kd1 5. Be2 6. Re1 7. Qxb7
47: 1. Nc3 2. e4 3. Qh5 4. Ba6 5. Nce2 6. Bxb7 7. Bxa8
48: 1. b4 2. d4 3. Be3 4. Qd3 5. d5 6. Bxa7
49: 1. c4 2. Nc3 3. Qa4 4. e4 5. Qxa7 6. Na4 7. Qxa8
50: 1. Nc3 2. e4 3. Ba6 4. e5 5. Ne4 6. Bxb7 7. Bxa8

I was impressed by the power of chess to express posets because each 
integer from 1 to 50 can be achieved, and furthermore, the length of the 
game almost always matches the theoretical minimum for any poset, given 
by http://oeis.org/A160371 . The only difference in the list is n=44 
which can be done with a mathematical poset of size 6, but requires 7 
chess moves.

Broadening to queue problems gives slightly more power, with 9 problems 
that can be achieved in one fewer move than the list above:

13: 1. d4 2. Bh6 3. f4 4. d5 5. f5
17: 1. d3 2. Be3 3. Bxa7 4. e4 5. Qg4 6. Qxg7
29: 1. c4 2. Qa4 3. e4 4. Qxa7 5. c5 6. Bb5
31: 1. Nc3 2. d3 3. Be3 4. Bxa7 5. e4 6. Nce2
34: 1. d3 2. Be3 3. Bxa7 4. e4 5. Qh5 6. e5
44: 1. Nf3 2. e4 3. Ne5 4. Qh5 5. f4 6. Kf2
47: 1. Nf3 2. d4 3. e3 4. Bb5 5. Nfd2 6. Qh5
49: 1. Nh3 2. d4 3. Bh6 4. f4 5. Nf2 6. f5
50: 1. d4 2. Bh6 3. f4 4. Nf3 5. d5 6. f5

I know that you two like interesting mathematical structures, and my 
brute force approach probably makes use of unremarkable posets and 
queues most of the time, but I hope that you found the results 
interesting nonetheless.


Noam Elkies wrote:
> Looks nice.  "No check protection" -- do you then run the same
> computation twice, once normally and the other time allowing checks
> to be ignored, and then extract the positions that have the same
> lengths and enumerations either way?

In this case there were only 11 positions with many similar positions 
(only about 4 essentially different ways), so I looked at them manually. 
If I had to deal with more positions then eventually it would be worth 
writing a program to automate.


andrew buchanan wrote:
>
> (4) How many plies does your general analysis of proof games extend 
> these days? I am aware that applying constraints intelligently allows 
> you to go a bit further too in some cases.

For general proof games I reached ply 11 this January. My list of all 
positions reachable after 11 plies is heavily compressed and takes 1.45 
TB of disk space, so I don't think I'll compute ply 12 anytime soon.

     François

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://pairlist1.pair.net/pipermail/retros/attachments/20170130/f18c5478/attachment.html>