selady@VMS.HUJI.AC.IL (ELAD YAACOBY) (01/17/91)
I am sure you are all familiar with the popular game Master Mind. Well I am working on algorithms to have the computer play Master Mind with 4 pegs and 0-9 different possiblieties per peg. I have a few suggestions but am looking for something more efficient. Anybody out there have any suggestion? Please reply by mail SELADY@VMS.HUJI.AC.IL Thanks in Advance, Elad
tensi@informatik.tu-muenchen.de (Thomas Tensi) (01/24/91)
In article <684@shum.huji.ac.il> selady@VMS.HUJI.AC.IL (ELAD YAACOBY) writes: > I am sure you are all familiar with the popular game Master Mind. Well I am > working on algorithms to have the computer play Master Mind with 4 pegs and > 0-9 different possiblieties per peg. I have a few suggestions but am looking > for something more efficient. Anybody out there have any suggestion? Hi Elad, If I correctly understand your request, you want to program a Master Mind code breaker who finds out a code where hints are given by you. This is one of the problems given in a book I read some years ago with approximately the title "100 programming exercises for experienced programmers" (I could be heavily wrong with that title ...). If you're especially interested in the book, I can find out the exact reference. The algorithmic idea (based on Don E. Knuth) is as follows (sorry, this is a bit mathematical, but I hope the idea will come out): Call the set of all codes allowed A (e.g. all 4-permutations of the numbers 0-9). At a certain phase of the game there are still some codes possible. Call this set P. Now the idea is to loop through all codes in A. Let's consider code c in A. There are several possible results you might get for this code (no pegs, 1 white peg, 1 black peg, 1 white and 1 black and so on). For each result the set of possible codes is additionally restricted. Now for each result count the number of codes still possible and take the maximum value among them and call it max(c). (Idea: As you don't know what the result will be, be pessimistic about it!). I.e. when you try code c, the adversary will give you some hint and after that there are at most max(c) codes still possible (if she's a bad girl she might even change the code consistently...). Now the best thing is to find the code x among all allowed (!) codes A which minimizes max(c) for c in A. This takes very long as there are 3 loops involved (pseudocode follows): minimum:=MaxInt; BestCode:=junk; FOR x:=FirstCode TO LastCode DO begin (* try all allowed codes *) MaximumRemaining:=0; FOR result:=NoPegs TO FourBlackPegs DO begin (* try all results *) count:=0; FOR p:=FirstCode TO LastCode DO begin (* only consider codes currently still possible *) IF CodeIsStillPossible(p) THEN begin (* now assume you try <x>, and get <result>, is <p> still possible after that? *) IF CodeIsPossibleAfterResultForX(p, x, result) THEN begin count:=count+1 END (* IF *) END (* IF *) END (* FOR *); (* count contains the number of codes possible after <result> for code <x> *) IF count>MaximumRemaining THEN begin MaximumRemaining:=count END (* IF *) END (* FOR *); IF MaximumRemaining<minimum THEN begin minimum:=MaximumRemaining; BestCode:=x END (* IF *) END (* FOR *) (* <BestCode> minimizes the number of remaining codes for all possible results *) > Please reply by mail SELADY@VMS.HUJI.AC.IL I did this, but maybe others are interested in the solution. > Thanks in Advance, You're welcome. > Elad Thomas Tensi ------------------------------------------------------------------------------ Thomas Tensi, Institut fuer Informatik, Technische Univ. Muenchen, Arcisstr. 21, 8000 Muenchen 2, Germany | E-Mail: | tensi@lan.informatik.tu-muenchen.dbp.de (X.400) | tensi%lan.informatik.tu-muenchen.dbp.de@relay.cs.net (arpa/csnet) | tensi%lan.informatik.tu-muenchen.dbp.de@unido.uucp (uucp) | tensi%lan.informatik.tu-muenchen.dbp.de@ddoinf6.bitnet (bitnet)