12
$\begingroup$

For a given number of positions/holes and a given number of colors, which initial guess eliminates the most possibilities for the solution at a minimum?

For 4 positions, it's AABB. What is it for 5, or 6 positions?

Edit I made another minor decision making improvement, and I've let it run many thousands of times now. It's been somewhere between 4.469 and 4.470. Scrolling up, I still see brief periods where the average is +/- 0.004, so I suppose it could eventually settle at 4.478, but I find it unlikely that it would ever go that high, so I consider my goal of beating Knuth reached, but only for 4 holes, for which I already know the best initial guess.

I'm removing the background stuff and leaving the question that hasn't been answered precisely.

$\endgroup$
  • $\begingroup$ Pretty sure the wiki is just arbitrarily picking 1 and 2, as long as two unequal items are selected I don't see why it would matter which you would pick. $\endgroup$ – dcfyj Nov 3 '16 at 14:00
  • $\begingroup$ I never wondered about this before, but now I'm wondering about it. Eagerly awaiting a definitive response. $\endgroup$ – Dan Russell Nov 3 '16 at 14:09
  • 3
    $\begingroup$ 300 runs is so low that your 4.5 seems to be in the 4.478's error margin. $\endgroup$ – Bogdan Alexandru Nov 3 '16 at 14:10
  • $\begingroup$ I'll try not checking if the candidate guess is also an eligible solution, to see if the average increases. That's the average that should be 4.478. I read just now that other algorithms do the same check I'm doing, and those get even lower averages, apparently. $\endgroup$ – Magnus Bakke Nov 3 '16 at 14:20
  • 1
    $\begingroup$ "Lexical order" or lexicographical order is just a generalisation of dictionary order to whatever alphabet you have at your disposal (in this case, numbers). $\endgroup$ – Lawrence Nov 3 '16 at 14:21
5
$\begingroup$

Any first move is equal, as long as it follows the pattern XXYY.

The way you number the holes in the first move is only a base reference point for the subsequent moves.

So, choose an arbitrary first move, name those first choices as they are named at the start of the stragey and then apply the complete strategy.

The article basically says "start with 1122, since it's proven to be better than 1123 or 1234".

What this means is: choose any two and go with those, instead of choosing three or all four.

$\endgroup$
  • $\begingroup$ Thanks. Do you also happen to know the best pattern for 5 and 6 holes? 11222 or 11223? $\endgroup$ – Magnus Bakke Nov 3 '16 at 16:44
  • 1
    $\begingroup$ @MagnusBakke I think that depends on the number of colors but xxyyy for normal cases. $\endgroup$ – kaine Nov 3 '16 at 20:43
  • 1
    $\begingroup$ @MagnusBakke I do not know the optimal strategy for 5 moves, maybe this link helps: groups.google.com/forum/#!topic/alt.math.recreational/…. I was mainly answering your question regarding the differences between different starting moves. $\endgroup$ – Bogdan Alexandru Nov 3 '16 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.