monta@cmu-cs-g.ARPA (Peter Monta) (03/08/85)
> Guessing "wrong" answers in Mastermind can indeed get you to the answer > sooner than guessing only right answers. > - Joel McCormack {ihnp4 decvax ucbvax allegra}!decwrl!joel This is an important point, which took me some time to realize. I worked on a near-isomorph of MasterMind called Jotto as part of a cognitive psychology course---I finally wrote a program very similar to the description of the exhaustive table-generating program. Jotto is 26-color, 5-position MasterMind, duplicate colors permitted, guess feedback only the number of pegs (no distinction between black and white). Of course, the colors are letters, guesses are five-letter words, and feedback is a number from 0 to 5. Guesses are restricted to valid five-letter words, as are targets. My thought is that the right thing to maximize is the *information* obtained from each guess. Suppose you guess a word. The act of guessing partitions the set of all possibilities into six blocks---those with 0 letters in common with the guess, those with 1 letter in common, etc. When the opponent tells you the disposition of your guess, he gives you information in the amount of the entropy of this partition. Assuming that the targets are equally probable, the entropy is the sum over blocks of P*log P, where P is the cardinal of the block. The program would simply iterate through its dictionary, guessing the entry that maximized the entropy of the partition it induced. The technique should be applicable to any MasterMind-like game; in fact, it should do even better with black and white pegs, since this would increase the number of blocks. Peter Monta ARPA: monta@cmu-cs-g UUCP: ...!rochester!cmu-cs-pt!cmu-cs-g!monta
lambert@boring.UUCP (03/09/85)
Jim Davis writes: > The next move should be chosen so as to minimize the size of the largest > set of posibilities remaining after the reply to that move. Peter Monta writes: > My thought is that the right thing to maximize is the *information* > obtained from each guess. The right heuristic depends on whether you try to maximize the worst-case or the average number of guesses required. In playing against an opponent, where the player first to hit the solution wins, the second seems more appropriate--unless you know that s/he/it follows the first strategy. But if you know that your opponent is very near the solution, desparate guesses may be better than steadily gathering information. There is an amusing variant of Jotto etc. in which a player does not have to freeze the initial position, as long as the answers given are consistent with *some* initial position. This can, in principle, also be done in the original game, in which case it is cheating. For a human player, it is hard to play this "Floating" Jotto to his/her advantage, since it is hard not to make mistakes. For a program, it is quite feasible: keep a list of initial positions that are still open, and when posed a question, divide the items in the list into classes, depending on the answer required for each item, and give the answer corresponding to the largest class (which then becomes the new list). -- Lambert Meertens ...!{seismo,philabs,decvax}!lambert@mcvax.UUCP CWI (Centre for Mathematics and Computer Science), Amsterdam
gjk@talcott.UUCP (Greg Kuperberg) (03/10/85)
> There is an amusing variant of Jotto etc. in which a player does not have > to freeze the initial position, as long as the answers given are consistent > with *some* initial position. This can, in principle, also be done in the > original game, in which case it is cheating. For a human player, it is > hard to play this "Floating" Jotto to his/her advantage, since it is hard > not to make mistakes. For a program, it is quite feasible: keep a list of > initial positions that are still open, and when posed a question, divide > the items in the list into classes, depending on the answer required for > each item, and give the answer corresponding to the largest class (which > then becomes the new list). ... > Lambert Meertens This is only feasible for a small number of holes. Suppose the computer had to deal with, say, twenty holes and ten colors. Clearly remembering all 100,000,000,000,000,000,000 combinations is at once impossible and overkill. Is there any good way to represent appropriate subsets of the space of MasterMind combinations? (good as in computation time for winning the game, that is) --- Greg Kuperberg harvard!talcott!gjk "2*x^5-10*x+5=0 is not solvable by radicals." -Evariste Galois.