Mastermind-robot

CDW · Sep 10, 2006

Eine Aufgabe von Chris:

Schreibe ein Computerprogramm, das Mastermind spielt. Es soll nach einem Code fragen und diesen dann versuchen zu knacken. (Das Programm spielt beide Spieler, also der Anwender soll nicht die lästigen Bewertungen eingeben müssen, aber natürlich darf der "lösende Teil" des Programms nicht direkt auf den Code zugreifen!)
Es muss jede mögliche Kombination knacken können!
Das Programm soll die einzelnen Zeilen und die jeweilige Bewertung auch anzeigen.

Spielregeln: Es werden keine 'Löcher' und keine doppelten Farben benutzt. Es gibt acht Farben und vier Positionen. Das Brett hat 10 Zeilen. Die Bewertung der Versuche gibt nur die Zahl der schwarzen und weißen Pins an, nicht, auf welche Position sie sich beziehen.

Viel Spass

Chrisiaut · Sep 11, 2006

für alle dies ned kennen: http://de.wikipedia.org/wiki/Mastermind

lagalopex · Sep 12, 2006

Original von CDW
Spielregeln: Es werden keine 'Löcher' und keine doppelten Farben benutzt. Es gibt acht Farben und vier Positionen. Das Brett hat 10 Zeilen. Die Bewertung der Versuche gibt nur die Zahl der schwarzen und weißen Pins an, nicht, auf welche Position sie sich beziehen.

Dürfen Löcher bzw doppelte Farben beim Lösen benutzt werden?
Wäre es sinnvoll, acht Farben vorher festzulegen? (normalerweise gibts ja nur 6...) Der Einfachheit halber kann man ja auch Zeichen oder Ziffern benutzen...

merker · Sep 14, 2006

Hallo,

im obigen "wiki"-Link steht, dass zur Strategie "logisches Denkvermögen" und "Kombinationsgabe" gehören. Allerdings sehe ich keinen Unterschied zwischen "Kombinationsgabe" und "Raten mit rel. hoher Trefferquote".

Deshalb als Anhang dabei eine Lösung die auf einer Bruteforce-Methode beruht.

Möglich ist das weil die Spielregeln von "Mastemind" cracker-technisch gesehen zwei schwere Bugs enthalten :

Bei 8 Farben mit Wiederholung gibt es nur 8 ^ 4 = 4096 Kombinationen. Schon die Eingabe einer beliebigen Zahl reduziert die Kombinationen um 75 %.

Beispiel :

code : 3712 (Zahlen repräsentieren die Farben ( 1..8 ))
1. eingabe : 2761
Das Spiel gibt zurück : sw-- (schwarz,weiss,leer,leer)

Nun umgekehrt :

code : 2761
1. eingabe : 3712
Das Spiel gibt zurück : sw--

"vorwärts" und "rückwärts" bringt das gleiche Ergebnis (sw--).

Viel Spass mit dem Anhang. Diesmal ist es eine "echte C++ -State-Of-The-Art- Konsole" :

eingeben code : 4567
--------------------
1. versuch : 1234 w--- 0976
2. versuch : 6178 ww-- 0228
3. versuch : 5851 w--- 0055
4. versuch : 7562 ssw- 0005
5. versuch : 7365 sww- 0002
6. versuch : 7546 swww 0001
7. versuch : 4567 ssss 0001

nochmal (0:ja,1:nein) ?

Chris · Sep 14, 2006

Habe ganz vergessen meine Lösung mit anzugeben. Hab mal ein Programm geschrieben, daß einfach nach Brute-Force-Manier vorgeht und den Code knackt und dann noch eins, das beweist, daß alle Kombinationen mit dem Algorithmus lösbar sind (indem es einfach alle Kombinationen als Startwert vorgibt und dann ne Schleife laufen lääst).
Das Programm beginnt mit einer Kombination (0-1-2-3), lässt sie bewerten und "zählt" dann durch: Erhöht zuerst mal die letzte Ziffer um 1 und checkt dann, ob das Ergebnis mit der Bewertung der Vorhergehenden konsistent ist, indem es die vorhergehenden nach dem neuen Versuch bewertet und diese Bewertung mit der ursprünglichen vergleicht. Wenn diese gleich sind, ist neue Kombination konsistent und er macht sie dann. Sind sie nicht gleich, "zählt" es weiter...
Geschrieben habe ich das ganze mit ziemlich elementaren Befehlen in Pascal.

Dürfen Löcher bzw doppelte Farben beim Lösen benutzt werden?
Wäre es sinnvoll, acht Farben vorher festzulegen? (normalerweise gibts ja nur 6...) Der Einfachheit halber kann man ja auch Zeichen oder Ziffern benutzen...

Klar kannst du auch eine "erweiterte" Version schreiben... Das Originalspiel geht meines Wissens mit acht Farben; natürlich ist es sinnvoll, diese mit Zahlen durchzunummerieren. (Hoffe ich habe die Frage richtig verstanden!)

(Wo kann man eigentlich dieses "Hide" im Post eingügen?)
durch [ SPOILER ="titel"] hidecode [ /SPOILER] (editiert von CDW)

Code:

program Mastermind;
uses crt;
var code:array[0..3] of byte; { Der versteckte Code }
allesSchwarz:array[0..1] of byte; { Referenz für 4 Schwarze und 0 weiße }
brett:array[0..9,0..3] of byte; { Das Brett }
antworten:array[0..9,0..1] of byte; { Platz für Bewertungen }
i,line,m,below,p,q:byte;
gefunden,voll,raus,firstright,gleiche:boolean;


procedure Einlesen; { Begrüßung // Einlesen des versteckten Codes }
var eingabeok:boolean;
istzahl:boolean;
j:integer;
begin
writeln('-------------------------------------------------');
writeln('| Mastermind v0.2 |');
writeln('| author: Chris |');
writeln('| Published under GNU/GPL in current version |');
writeln('-------------------------------------------------');

repeat
writeln('Enter your hidden code (4 separate values');
writeln('from 0 to 7, no equal values!):');
write('#0: '); readln(code[0]);
write('#1: '); readln(code[1]);
write('#2: '); readln(code[2]);
write('#3: '); readln(code[3]);

eingabeok:=true;

{ Checke, ob alle Zahlen korrekt sind }
for i:=0 to 3 do
begin
istzahl:=false;
if code[i]=0 then istzahl:=true;
if code[i]=1 then istzahl:=true;
if code[i]=2 then istzahl:=true;
if code[i]=3 then istzahl:=true;
if code[i]=4 then istzahl:=true;
if code[i]=5 then istzahl:=true;
if code[i]=6 then istzahl:=true;
if code[i]=7 then istzahl:=true;
if istzahl=false then eingabeok:=false;
end;

{ Checke, dass keine gleichen dabei sind }
for i:=0 to 3 do for j:=0 to 3 do
if (code[i]=code[j]) and (i<>j) then eingabeok:=false;

until eingabeok=true;
end;


procedure AntwortenNull;
var j:integer;
begin
for i:=0 to 9 do
for j:=0 to 1 do
antworten[i,j]:=0;
end;


procedure Schreibe(znr:integer);
begin
writeln(znr,' || ',brett[znr,0],' ',brett[znr,1],' ',brett[znr,2],' ',brett[znr,3],' || white: ',antworten[znr,0],', black: ',antworten[znr,1]);
end;



procedure ErsteZeileSchreiben;
begin
for i:=0 to 4 do
brett[0,i]:=i;
end;


procedure bewerte(znr:integer);
var j:integer;
begin
for i:=0 to 3 do
begin

for j:=0 to 3 do
if (brett[znr,i]=code[j]) and (i<>j) then inc(antworten[znr,0]); { weiße setzen }

if brett[znr,i]=code[i] then inc(antworten[znr,1]); { schwarze setzen }

end;
end;


function konsistent(znr:integer):boolean;
var testantwort:array[0..1] of integer;
j,k,r,znrbelow:integer;
begin
konsistent:=true;
znrbelow:=znr-1;

for k:=0 to znrbelow do
begin

for r:=0 to 1 do testantwort[r]:=0;

{ Vergleiche kte Zeile mit dem in znr übergebenen Vorschlag }
for i:=0 to 3 do
begin
for j:=0 to 3 do
if (brett[k,i]=brett[znr,j]) and (i<>j) then inc(testantwort[0]); { weiße setzen }

if brett[k,i]=brett[znr,i] then inc(testantwort[1]); { schwarze setzen }
end;


for i:=0 to 1 do
if testantwort[i]<>antworten[k,i] then konsistent:=false; { Vergleiche }


end;
end;


{ Hauptprogramm }
begin
Einlesen; { Liest 'code' ein }
AntwortenNull; { Setzt alle Elemente der Antwortmatrix auf 0 }
ErsteZeileSchreiben; { Schreibt 0 1 2 3 in die erste Zeile }
allesSchwarz[0]:=0; { Setzt die Referenz für die Lösung }
allesSchwarz[1]:=4;

bewerte(0);
Schreibe(0);

{ Checke, ob schon die erste richtig war }
firstright:=true;
for i:=0 to 1 do
if antworten[0,i]<>allesSchwarz[i] then firstright:=false;


if firstright=false then
begin


line:=0;


repeat

inc(line);
below:=line-1;

{ Vorherige Zeile übernehmen }
for m:=0 to 3 do brett[line,m]:=brett[below,m];

raus:=false;
gefunden:=false;
voll:=false;

repeat

repeat
{ Durchlaufen }
inc(brett[line,3]);

{ Überträge }
if brett[line,3]=8 then
begin
brett[line,3]:=0;
inc(brett[line,2]);
end;
if brett[line,2]=8 then
begin
brett[line,2]:=0;
inc(brett[line,1]);
end;
if brett[line,1]=8 then
begin
brett[line,1]:=0;
inc(brett[line,0]);
end;
if brett[line,0]=8 then
begin
brett[line,0]:=0;
end;

{ Checken ob welche gleich sind }
gleiche:=false;
for p:=0 to 3 do for q:=0 to 3 do
if (brett[line,p]=brett[line,q]) and (p<>q) then gleiche:=true;

until gleiche=false;

until konsistent(line)=true;

bewerte(line);
Schreibe(line);


{ Gucken, obs schon die Lösung ist }
gefunden:=true;
for i:=0 to 1 do
if antworten[line,i]<>allesSchwarz[i] then gefunden:=false;

{ ...oder ob das Brett voll ist }
if line=9 then voll:=true;

if voll=true then raus:=true;
if gefunden=true then raus:=true;

until raus=true;

if voll=true then writeln('Das Brett ist voll.');
if gefunden=true then writeln('Got it in line ',line,'! :)')
else writeln('Didnt get it. :(');

end

else writeln('Got it in the first line! ;)');


end.

Output:

Code:

-------------------------------------------------
| Mastermind v0.2                               |
| author: Chris       |
| Published under GNU/GPL in current version    |
-------------------------------------------------
Enter your hidden code (4 separate values
from 0 to 7, no equal values!):
#0: 6
#1: 4
#2: 3
#3: 2
0 || 0   1   2   3 || white: 2, black: 0
1 || 1   0   4   5 || white: 1, black: 0
2 || 2   3   5   6 || white: 3, black: 0
3 || 3   2   6   4 || white: 4, black: 0
4 || 4   6   3   2 || white: 2, black: 2
5 || 6   4   3   2 || white: 0, black: 4
Got it in line 5! :)

Ook! · Dez 27, 2008

Nicht perfekt... aber hat Spaß gemacht

Code:

from random import choice
from itertools import count

def initialCombs():
   def hasNoDoubles(comb):
      return not any(map(lambda i: comb.count(i) > 1, range(8)))
   return [ "%s%s%s%s" % (a,b,c,d) for a in range(8) for b in range(8) for c in range(8) for d in range(8) if hasNoDoubles([a,b,c,d]) ]

def rateComb(comb, number):
   black, white = 0, 0
   for i in range(4):
      if comb[i] == number[i]: 
         black += 1
      elif comb[i] in number:
         white += 1
   return (black, white)

def solve(answer, combs):
   def statistics(idx, comb, black, white):
      print "%i >> %s: %s%s%s" % (idx+1, " ".join(comb), black*'s', white*'w', (4-(black+white))*'-')
   for idx in count():
      comb = list(choice(combs))
      black, white = rateComb(comb, answer)
      combs = removeByRating(combs, comb, black, white)
      statistics(idx, comb, black, white)
      if black == 4:
         return "=> Loesung gefunden!"

def removeByRating(combs, number, black, white):
   return filter(lambda c: rateComb(c, number) == (black, white), combs)

if __name__ == "__main__":
   print solve(raw_input("Geheime Kombination: "), initialCombs())

Code:

Geheime Kombination: 4567
1 >> 7 3 2 5: ww--
2 >> 1 2 3 6: w---
3 >> 0 7 4 2: ww--
4 >> 5 6 7 0: www-
5 >> 4 5 6 7: ssss
=> Loesung gefunden!

Blöde Einrückung, hehe...

EDIT:
Danke für den Hinweis - habe den Code angepasst, sollte nun passen :]

Lesco · Dez 27, 2008

Original von Ook!
[..]

Wenn ich deinen Code richtig verstanden habe, machst du es dir zu einfach, da man nur die Anzahl der schwarzen/weißen Pins erhält, und nicht die Positionen dazu.

Hier meine Lösung in Haskell(funktioniert in dieser Fassung nur ohne doppelte Farben, benötigt sonst 2 kleine Änderungen):

Code:

import Control.Monad
import Data.Char
import Data.Map as M
import Data.List as L
import System.Random

checkAnswer :: Map Int Int -> Map Int Int -> (Int,Int)
checkAnswer code answer = let correctPos = filterWithKey (\k a -> code ! k == a) answer
                              remainingAnswer = answer M.\\ correctPos
                              remainingCode = code M.\\ correctPos
                              correctCols = filterWithKey (\k a -> not . M.null $ M.filter (==a) remainingCode) remainingAnswer
                          in (size correctPos,size correctCols)

initialCombs :: [Map Int Int]
initialCombs = [fromList $ zip [0..] [a,b,c,d] | a <- [0..7], b <- [0..7], c <- [0..7], d <- [0..7],
                                                 a /= b, a /= c, a /= d, b /= c, b /= d, c /= d]

--returns the number of exact matches in m and n
exactMatches m n = size $ filterWithKey (\k v -> m ! k == v) n
--returns the number of value matches on different positions in m and n
valMatches m n = size $ filterWithKey (\k v -> not . M.null $ filterWithKey (\k' v' -> k' /= k && v == v') m) n

--correct code is passed along as a parameter but is accessed only by the checking function
tryComb :: Map Int Int -> Map Int Int -> [Map Int Int] -> IO ()
tryComb a code combs =  do
  let res@(b,w) = checkAnswer code a
  putStrLn $ "Trying answer: " ++ show (toList a) ++ " - " ++ show res
  case b of
    4 -> putStrLn $ "Solution found "++show (toList a)
    otherwise -> do
      let newcombs = L.filter (\c -> exactMatches a c == b && valMatches a c == w) combs
      putStrLn $ "Remaining combinations: "++show (length newcombs)
      n <- randomRIO (0,length newcombs - 1)
      tryComb (newcombs !! n) code newcombs 
  
main :: IO ()
main = do
  putStrLn "Enter code"
  code <- L.map digitToInt `liftM` getLine
  ind <- randomRIO (0,length initialCombs - 1)
  tryComb (initialCombs !! ind) (fromList $ zip [0..] code) initialCombs

Beispiel:

Code:

Enter code
1703
Trying answer: [(0,3),(1,2),(2,6),(3,7)] - (0,2)
Remaining combinations: 504
Trying answer: [(0,7),(1,5),(2,3),(3,0)] - (0,3)
Remaining combinations: 44
Trying answer: [(0,5),(1,3),(2,7),(3,1)] - (0,3)
Remaining combinations: 3
Trying answer: [(0,4),(1,7),(2,5),(3,3)] - (2,0)
Remaining combinations: 2
Trying answer: [(0,1),(1,7),(2,0),(3,3)] - (4,0)
Solution found [(0,1),(1,7),(2,0),(3,3)]

CDW · Dez 28, 2008

Code:

:-use_module(library(lists)).
:-use_module(library(sets)).  %SWI: auskommentieren/ignorieren.
:-use_module(library(clpfd)).

combo(C):-C=[_,_,_,_],domain(C,1,8)/*%SWI: C ins 1..8*/,all_different(C),labeling([ff],C).

cmp(X,Y,Z):- X=:=Y -> Z=1 ; Z=0.
check(Org,ToCheck,W,B):-intersection(Org,ToCheck,Ws),
        length(Ws,WTmp),maplist(cmp,Org,ToCheck,BList),!,sumlist(BList,B),W is WTmp-B.

solve(Sol,Sol,_,[Sol]):- write('Loesung: '),write(Sol),nl.
solve(Sol,Try,SolSet,[Try|Path]):-check(Sol,Try,W,B),   
        findall(Combo,(member(Combo,SolSet),check(Try,Combo,W,B),Combo\=Try),
		[NTry|NewSolSet]),
        statistic([NTry|NewSolSet],Try,W,B),solve(Sol,NTry,NewSolSet,Path),!.

statistic(Set,Try,W,B):- length(Set,L),
	format('Versuch: ~q,w:~k,b:~k verbl. Moeglichkeiten: ~d\n', [Try,W,B,L]).

bot(Solution,Path):-
        findall(Combo,combo(Combo),[Try|SolSet]),solve(Solution,Try,SolSet,Path),!.

10 Zeilen Begrenzung wurde allerdings nicht eingebaut, da der Bot perfekt spielt

und alles unter 10 Zeilen löst.

es gibt insgesamt 1680 Kombinationen (8!/(8-4)!) bzw:

Code:

| ?- findall(C,combo(C),Cs),length(Cs,Gesamt).
Cs = [[1,2,3,4],[1,2,3,5],[1,2,3,6],[1,2,3,7],[1,2,3,8],[1,2,4,3],[1,2,4,5],[1,2,4|...],[1,2|...],[1|...]|...],
Gesamt = 1680 ?

Anzahl der Lösungen/längste Lösung:

Code:

  time2(findall((Len),(combo(C),bot(C,Sol),length(Sol,Len)),Sols)),length(Sols,AnzLoes),sort(Sols,Sorted),last(Sorted,Laengste),sumlist(Sols,Sum),AverageNum is Sum/AnzLoes.
 65.813 sec.

Sorted = [1,2,3,4,5,6,7],
Laengste = 7,
AnzLoes = 1680,
AverageNum = 4.90297619047619 ?

D.h Anzahl der Lösungen==Anzahl der Kombinationen, wobei die längste Lösung 7 Schritte beinhaltet.

Code:

 | ?- bot([8,1,7,2],Loesung).
Versuch: [1,2,3,4],w:2,b:0 verbl. Moeglichkeiten: 504
Versuch: [2,1,5,6],w:1,b:1 verbl. Moeglichkeiten: 84
Versuch: [2,3,6,7],w:2,b:0 verbl. Moeglichkeiten: 18
Versuch: [3,1,7,5],w:0,b:2 verbl. Moeglichkeiten: 1
Loesung: [8,1,7,2]
Loesung = [[1,2,3,4],[2,1,5,6],[2,3,6,7],[3,1,7,5],[8,1,7,2]] ? 
yes
% 3
| ?- bot([4,5,6,7],Loesung).
Versuch: [1,2,3,4],w:1,b:0 verbl. Moeglichkeiten: 288
Versuch: [2,5,6,7],w:0,b:3 verbl. Moeglichkeiten: 5
Versuch: [2,5,6,8],w:0,b:2 verbl. Moeglichkeiten: 2
Versuch: [3,5,6,7],w:0,b:3 verbl. Moeglichkeiten: 1
Loesung: [4,5,6,7]
Loesung = [[1,2,3,4],[2,5,6,7],[2,5,6,8],[3,5,6,7],[4,5,6,7]] ? 
yes