Analysis

I created a script to analyse starting moves, to find out the minimum number of moves required to win against CheaterMind. Comparing notes with Knuth's paper, I found that I had made a mistake somewhere, because my analysis was reporting that 1123 (in Knuth's parlance) was the optimal starting move (needing 5 moves), and all others (including Knuth's proclaimed champion, 1122) needed 6 moves.

I dug a bit and noticed that my algorithm started the same as his when analysing 1122, but at the stage at which it would narrow down to 46 possibilites, there were many guesses that could produce that result. My algorithm was taking 3211 instead of 2234, because it was taking the first guess it came across with 46 possibilites, and my ordering was apparently different from Knuth's. So I modified it to take last guess instead, but that turned out to be 2344, still not Knuth's choice, and still taking 6 moves to win. It turns out this is because my ordering is not simply a reversal of Knuth's.

Rather than change my ordering completely, which I probably will eventually do, I decided to take a shortcut and make a value function based on Wikipedia's mention that "Knuth follows the convention of choosing the guess with the least numeric value e.g. 2345 is lower than 3456."

Hooray! My algorithm now reported that an opening move of 1122 did, in fact, allow someone to win within 5 moves. It's an open question, for me, as to why the mere convention followed here makes a difference. But it clearly does--I just don't understand it intuitively quite yet.

Anyway, this is where it got even more interesting. With my modified algorithm in place, I re-ran the analysis...which said that 1122 is a great opener, but equally great are 1123 and 1234. Knuth's paper specifically mentions these as not being able to guarantee 5-move wins, although he admits that "it is probably possible to fix [1123]" and only that "when the first test pattern is 1234 it appears impossible to guarantee a win in five." (Emphasis mine.) I believe my algorithm shows that it's indeed possible to fix 1123, and furthermore that appearances may have been misleading. It's hard to tell, though, because the paper does not go into quite enough detail how he arrived at these latter two analyses.

So, is it possible that Knuth's conclusions weren't complete, and that what my revised algorithm reports is actually true? If not, the next step is finding where exactly my algorithm is incorrect.