in reply to Challenge: Optimal Bagels Strategy

I seem to recall that Knuth has written about this subject (Mastermind, but that seems essentially to be the same game, except that mastermind allows for repeats). IIRC, he has proven that (at least for a certain number of colours that positions), the best play after the first move is the one (or one of the ones) that minimizes the maximum number of possibles left, over all possible "pico/fermi/bagel" responses. I cannot remember what he said about first moves.

Replies are listed 'Best First'.
Re^2: Challenge: Optimal Bagels Strategy
by MidLifeXis (Monsignor) on Sep 28, 2009 at 14:34 UTC

    Not having repeats makes the job of the person with the code much simpler, at least I think it does. The work that the person guessing the code has to do would then be based on the size of V compared to P.

    If you call each "color" Cn, and take the first P characters from a randomly sorted alphabet of size V, you essentially have a code of ...

    C1, C2, C3, ..., Cp

    If my grey matter is working properly, it does not matter what characters the code maker chooses, other than as a psychological exercise against the choice of the initial selections.

    If I ignore defending against the choice of initial selections, the code maker really only has 315 puzzles to generate.

    (p=1,  v=1 ) .. (p=1,  v=36) => 36
(p=2,  v=2 ) .. (p=2,  v=36) => 35
...
(p=10, v=10) .. (p=10, v=36) => 27

((27 + 36) / 2) * 10 = 315

    [download]

    Now, that is not to say that the code maker will probably not be choosing '0', '01', '012', etc as the codes. It also does not mean that there will not be some carefully chosen sequences designed to test the robustness of certain types of implementations. :-)

    --MidLifeXis

    Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.

[reply]
[d/l]
Re^2: Challenge: Optimal Bagels Strategy
by Limbic~Region (Chancellor) on Oct 03, 2013 at 13:20 UTC
    JavaFan,
    Years after this post, I discovered that my daughter is now playing a simplified version of this game in her 2nd grade classroom. I have yet to find a more optimal strategy then Knuth's although the game isn't exactly the same.

    Cheers - L~R

[reply]

In Section Meditations