13
$\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$
6
  • $\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, 2016 at 14:00
  • $\begingroup$ I never wondered about this before, but now I'm wondering about it. Eagerly awaiting a definitive response. $\endgroup$ Nov 3, 2016 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$ Nov 3, 2016 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$ Nov 3, 2016 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, 2016 at 14:21

1 Answer 1

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$
3
  • $\begingroup$ Thanks. Do you also happen to know the best pattern for 5 and 6 holes? 11222 or 11223? $\endgroup$ Nov 3, 2016 at 16:44
  • 1
    $\begingroup$ @MagnusBakke I think that depends on the number of colors but xxyyy for normal cases. $\endgroup$
    – kaine
    Nov 3, 2016 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$ Nov 3, 2016 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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