Musing on guesswork

[simont]

Games of hidden information are very weird in their randomness.

Minesweeper, of course, is well known to be annoying for its randomness, which is why I went to the effort of writing a version that didn't require random guesswork. When you have no choice but to take a risk, it's annoying to be wrong because it terminates your game.

But I've recently been sent an implementation of the puzzle/board game ‘Mastermind’ for my puzzle collection, and I've been finding that the annoying randomness works the other way in that: it's much more annoying to be right. When you've just constructed a guess which you've carefully designed to narrow down the possibilities and bring you one step nearer to the actual solution … it's terribly irritating if that guess turns out to be the exact answer. In a game played against an opponent, where each of you was scoring points for how quickly you solved the other's problems, this would at least be useful to you because you'd get a lot of points for it. But in a solo context, you're not really after the high scores; you're after the satisfaction of reasoning your way to the answer step by step, and to unexpectedly hit the right combination at an early stage rather spoils the fun.

Comments

[deliberateblank.livejournal.com]

Same approach: write a version which tracks how much information you could possibly have inferred from each existing move and swaps colours round so as to be compatible with previous revelations but to maximize the necessary chain of tests to reach a solution?

[gerald_duck]

That's not quite the same thing. In Mines, it is possible to lose, and Simon's innovation is to make sure (as a single step at the start of each game) that it never gives you a game that cannot be won without taking a risk of losing. In Guess, there is no risk of losing, but what you're proposing is to continue changing the solution as the game progresses so as to maximise how long it takes to deduce.

That continuous refinement step, if done in either Guess or Mines, would make the game deterministic: if you make the same sequence of guesses, or click the same sequence of spaces in the minefield, the solution will always be the same. I doubt this is a good idea.

Fundamentally, I suspect the real problem is just that Guess is a much simpler game than Mines.

[simont]

The game need not become deterministic. At any stage, there are some number of combinations not already ruled out by previous guesses; when the player makes a new guess you pick one of those at random, making sure it isn't the one they just guessed if possible, and you mark according to that. Then you winnow the list of possible combinations to eliminate those inconsistent with the new mark (with the result, of course, that the combination you just thought of will remain in the list).

I suppose you could take it a step further (as John might or might not have intended to imply) and deliberately choose a mark to return which will rule out the fewest of the combinations still in the list; that might run a greater risk of leading to determinism and would therefore presumably be undesirable. (Though it might still not become completely deterministic: in situations where there are two joint-nastiest marks you could return, you would probably still want to pick randomly.)

Perhaps a sensible middle ground would be to examine the full range of marks you could legitimately return for the current guess, rule out a few of the ones that provide tons and tons of information but leave most of them still present, then pick at random from them (possibly weighted by the number of combinations scoring each one). This might strike a plausible balance between avoiding determinism and also avoiding disappointingly short games (since being entirely right isn't the only danger - being almost entirely right is almost as bad).

I suspect I'm not actually going to get round to trying this, but I don't think it's fundamentally infeasible in principle. (Though I do agree with you that it's taking the idea quite a lot further than I did in Mines.)