Mu-Tsun Tsai's Retrograde Analysis WebsiteWelcome to my website on retroanalysis!This website is under construction, and currently it hosts only my most recent research project on "mushikui reconstruction". Mushikui ReconstructionThe word "mushikui" came from the mushikuizan puzzle, and it's a Japanese term meaning "eaten by bugs".Mushkikui reconstruction is a type of chess game resconstruction task, proposed by me on the retro mailling list in 2011. In each problem, solvers are given a game score, written in PGNep format (explained below), but all the characters are concealed by "*" symbols, so that only the length of the representation of each move is known to the solvers. The task for the solvers is then to recover the entire game score based solely on these informations. All the problems need to have a unique solution in order to be considered as valid. NotationThe format I'm using in mushikui reconstruction is what I call the "PGNep" format, which stands for "PGN spec" + "ep". This means that everything in this format is the same as described in the PGN spec document, with only one exception being that I use "ep" to denote en passant move. The main reason why I choose my format this way is because most people in this field seems to get used to put "ep" whenever they write a game score, so I believe this format will make things more "natural" to the people in this field.Summary of this format:
(2011.5.18.1)
1.** ** 2.**** **** 3.** ***** 4.** ***** 5.**** ** 6.****** **** 7.*****
1.d4 c5 2.dxc5 Qa5+ 3.b4 Qxb4+ 4.c3 Qxc3+ 5.Nxc3 b5 6.cxb6ep axb6 7.Qxd7+ All the problems on this webpage have a unique solution, and are computer checked. I don't consider any sequence that doesn't have a unique solution, even if it does force something, for example its final position or certain moves, etc. Some of my compositions
(2011.5.17.1) This one was my very first mushikui composition, but it's pretty tough to solve.
1.** ** 2.**** **** 3.**** **** 4.*** ***** 5.**** ** 6.** **** 7.*** ***** 8.**** **** 9.*** **** 10.***** ***** 11.*** ***** 12.****
(2011.5.17.2) For those who haven't seen this type of problem, this one could be a bit tricky.
1.** ** 2.**** **** 3.**** **** 4.*** **** 5.*** ***** 6.**** ***** 7.****
(2011.5.18.2)
1.** ** 2.**** ** 3.****** **** 4.** ***** 5.** **** 6.**** ***** 7.**** ****
(2011.5.19) Although being very long, this one is actually relatively easy.
1.*** ** 2.**** **** 3.*** **** 4.**** ***** 5.**** *** 6.***** **** 7.** *** 8.*** ***** 9.*** **** 10.*** ***** 11.***** ** 12.**** **** 13.***** **** 14.***** *** 15.***** *** 16.*** ** 17.***** ** 18.***** *** 19.** ***** 20.**** **** 21.*** ** 22.** ***** 23.**** **** 24.*** ***** 25.**** ** 26.*** **** 27.** **** 28.** ****
(2011.5.19) Very tough!
1.*** ** 2.**** ** 3.***** **** 4.*** ***** 5.**** **** 5.**** **** 7.**** *** 8.**** **** 9.*** ***** 10.***** **** 11.** **** 12.** ***** 13.**
(2011.5.22)
1.** *** 2.**** **** 3.** ** 4.****** **** 5.** ***** 6.** ***** 7.*** ***** 8.**** ** 9.***** *** 10.***** ** 11.******* *** 12.******
(2011.5.23) "Cradle to Grave". A long, challenging problem, but still with reasonable difficulty for human solvers.
1.** *** 2.** *** 3.** **** 4.***** ** 5.*** *** 6.** ** 7.**** ***** 8.** ***** 9.** ***** 10.**** ***** 11.*** *** 12.***** ***** 13.**** ** 14.**** ** 15.***** ** 16.***** *** 17.***** **** 18.**** **** 19.*** **** 20.**** ** 21.****** ** 22.** ****** 23.**** ** 24.*** ****** 25.****** **** 26.**** **** 27.***** *** 28.** ** 29.***** **** 30.**** *** 31.***** ****
(2011.5.25)
1.** ** 2.**** ** 3.** **** 4.** ***** 5.** ***** 6.** *** 7.***** ** 8.***** *** 9.***** *** 10.***** *** 11.*****
(2011.5.26.1) I think this one is impossible for human solvers.
1.** *** 2.**** ** 3.*** **** 4.**** **** 5.*** *** 6.***** ***** 7.**** ***** 8.**** **** 9.** ***** 10.*** ***** 11.*** ***** 12.**** *** 13.** ***** 14.** **** 15.***** **** 16.** **** 17.*** **** 18.*** ***** 19.**** ***** 20.****
(2011.5.26.2) Very easy to solve.
1.** ** 2.**** **** 3.** ***** 4.** ***** 5.*** **** 6.**** ***** 7.***
(2011.5.27) Definitely impossible for human solvers. Even for computers, the running time is almost like forever. This is the first time I use parallel computing just for handling a single problem, and still it took a whole day to finish checking the validity of this one, using the older version of my program. With the new version, it only takes less than 40 seconds to check this one, but still this one remains the toughest problem for computer programs so far.
1.** ** 2.*** **** 3.**** ** 4.**** *** 5.**** **** 6.** **** 7.***** ** 8.***** ** 9.***** *** 10.***** *** 11.***** *** 12.**** ***** 13.*** ******* 14.*** ** 15.***** **
(2011.6.5) "7/11". After Mario Richter. Current record holder for (1) most number of consecutive question mark (2) highest question mark density.
1.? ? 2.? ? 3.**** ? 4.******* ***** 5.? ***** 6.?
(2011.6.8.1) Not for human.
1.** ** 2.*** ** 3.***** *** 4.** ****** 5.**** **** 6.***** **** 7.*** ***** 8.**** ** 9.***** ** 10.***** *** 11.****** *** 12.***** *** 13.**** ** 14.*****
(2011.6.8.2) Not for human.
1.** ** 2.*** ** 3.***** *** 4.** ****** 5.**** **** 6.***** **** 7.*** ***** 8.**** ** 9.** ** 10.***** ** 11.***** *** 12.****** *** 13.**** **** 14.***** *** 15.***** **** 16.*** ***** 17.**
(2011.6.9) Probably not for human.
1.*** ** 2.** **** 3.**** ** 4.****** ***** 5.**** **** 6.***** **** 7.**** ** 8.***** ** 9.***** **** 10.** *****
(2011.6.11) Recommended!
1.** *** 2.**** ** 3.**** **** 4.***** **** 5.*** **** 6.******
6...*** 7.**** ** 8.******* **** 9.** *** 10.******* *** 11.***** ****
(2011.6.15) Requested by DreamYeh.
1.** ** 2.**** **** 3.** ***** 4.** ***** 5.**** ** 6.**** *** 7.**** ** 8.****** **** 9.***** *** 10.******* *** 11.*** *****
(2011.6.16.1) Easy.
1.*** ** 2.**** **** 3.*** **** 4.**** ***** 5.**** *** 6.***** **** 7.*** *** 8.** ***** 9.*** **** 10.*** ***** 11.***** ** 12.***** ** 13.***** **** 14.**** *** 15.** ** 16.***** **** 17.*** ** 18.***** **** 19.**** *** 20.*****
(2011.6.16.2) Pretty tough for human, but not impossible.
1.*** ** 2.** ** 3.*** ***** 4.*** ***** 5.*** ** 6.*** **** 7.***** **** 8.*** *** 9.***** ** 10.** ***** 11.*** ***** 12.**** **** 13.**** **** 14.*** **** 15.*** ***** 16.** *** 17.*** ***** 18.** ** 19.** *** 20.**** ** 21.******* *** 22.*** *** 23.******* *** 24.**** *** 25.*** ***** 26.** **** 27.**** *** 28.**** *** 29.****** ** 30.** ** 31.**** ***** 32.**** ***** 33.**** ** 34.*** **** 35.*** ****** 36.*** ** 37.**** *** 38.**** *****
(2011.7.12.1) Not for human.
1.** ** 2.*** **** 3.**** *** 4.***** *** 5.** *** 6.** ** 7.******* ***** 8.*** **** 9.***** ***** 10.*** ** 11.***** ** 12.**** **** 13.*****
(2011.7.12.2) Not for human.
1.** ** 2.*** **** 3.**** *** 4.***** **** 5.** ***** 6.**** ***** 7.** ***** 8.**** **** 9.**** **** 10.***** *** 11.*** **** 12.***** **** 13.***** *** 14.** ** 15.**** ** 16.******* **** 17.*****
(2011.7.12.3) Not for human.
1.** ** 2.*** ** 3.** ****** 4.*** ***** 5.** **** 6.**** ***** 7.***** **** 8.*** **
9.*** **** 10.** ******* 11.***** **** 12.** ** 13.**** ** 14.******* **** 15.*** *** 16.*** ******* 17.*** ** 18.** **** 19.** *******
(2011.7.12.4) Probably not for human.
1.** ** 2.*** ** 3.** ******* 4.**** ***** 5.*** ** 6.***** ** 7.*** *** 8.**** ***** 9.**
(2011.7.13) Very tough for human.
1.** ** 2.*** *** 3.**** ***** 4.**** ***** 5.*** **** 6.*** ** 7.***** ***** 8.*** ***** 9.*** *** 10.***** **** 11.**
(2012.7.8) NOT for human.
1.** ** 2.** ** 3.** ** 4.**** **** 5.****** ** 6.**** **** 7.***** *****
8.**** **** 9.**** ***** 10.**** *** 11.**** ***** 12.** ****
13.**** *** 14.**** ** 15.***** ***** 16.**** *** 17.***** *** 18.*** ***
19.*** ***** 20.**** ***** 21.*** *** 22.**** *** 23.***** ****
24.***** *** 25.***** *** 26.**** **** 27.***** **** 28.** ** 29.** ** 30.** **
31.** **** 32.**** **** 33.*** **** 34.** **** 35.**** *** 36.** **** 37.** ***
38.**** *** 39.*** **** 40.**** *** 41.*** *** 42.***** *** 43.***** ****
Some theoriesUsing the old version of the checking program I wrote, I examine all the possible mushikui sequences up to six single moves. Among them, only two will force a unique solution:
(2011.5.19, M.-T. Tsai + Computer) All the valid sequences up to 6 single moves:
Later, Mario Richter (2011.5.26) first determined all the valid sequences with 7 or 8 single moves that doesn't contain a disambiguation move. After I rewrite my program, I then completely determined all the remaining valid sequences. The results are shown below. Each of them is a pretty good puzzle to human!
(2011.6.4, M. Richter + M.-T. Tsai + Computer) All the valid sequences with 7 single moves:
(2011.6.5, M. Richter + M.-T. Tsai + Computer) All the valid sequences with 8 single moves:
All valid sequences with 9 or 10 single moves is later completely determined as well. See the data page for details. In my opinion, I think a problem of this type is more enjoyable when it consists of a lot of stages, with each stage having a unique solution on its own. For example, Problem (2011.5.19) above can actually be decomposed as follows: In this decomposition, the end of each line represents a stage that has a unique solution. Totally it has 20 stages and 56 single moves, so I shall define its "stage density" to be 20/56. This is the mushikui sequence I know so far that has the highest stage density. Sometimes, it is possible to replace some of the moves by question marks "?", to indicated that the move is completely unknown, not even the length of the representation of that move, but still forces a unique solution. For example, the shortest one that allows a question mark is 1.*** ? 2.**** ****, whose solution is still 1.Nc3 d5 2.Nxd5 Qxd5. Another example is 1.? ? 2.**** **** 3.? ***** 4.**, whose solution is 1.d4 c5 2.dxc5 Qa5+ 3.b4 Qxb4+ 4.c3. This one has 3 question marks and 7 single moves, so I shall define its "question mark density" to be 3/7. Some open questsHere I shall propose several open quests for everybody. In the following, by "sequence" I mean a mushikui sequences with a unique solution. The "length" of a sequence could mean one of the following: number of single moves, or number of stars "*".
Problems by other composers
(2011.5.25) by DreamYeh
1.** ** 2.*** **** 3.***** **** 4.*** **** 5.*** ***** 6.**** ***** 7.**** ** 8.***** *****
(2011.5.25) by DreamYeh
1.** ** 2.*** **** 3.**** **** 4.*** **** 5.*** ***** 6.**** *** 7.**** ***** 8.***** ******
|