Hi,
ich suche für mein Mastermindspiel ein paar Lösungsalgorithmen, sprich der NPC soll den von mir vorgegebenen Farbcode ermitteln.
Durch das stöbern in Wikipedia bin ich auf 2 Algorithmen gestoßen:
Danke im Vorraus
Hast du irgendwelche eigenen Ansätze, oder suchst du nur eine Komplettlösung (für eine mögliche Hausaufgabe oder so… ohne das unterstellen zu wollen 
)
ich fange nächstes semester mein studium an und wollte nur schon mal ein bisschen in java einsteigen
Ja, … nur weil du eine fertige Java- oder Pseudocodeumsetzung von genau diesen Algorithmen zu suchen scheinst…
Aber ist ja egal: Hast du schonmal versucht, die auf Basis der Beschreibung auf Wikipedia selbst umzusetzen?
Ja habe ich
bin im moment mit der Liste für Permutationen mit 0 Duplikaten fertig. Allerdings hab ich keine Ahnung wie ich eine Liste mit 1,2 oder 3 Duplikaten ansetzen soll.
Mit dem an anderer Stelle schon erwähnten CombinationIterable kann man da was basteln. Ist nur schnell hingeschrieben (insbesondere der Teil der die Responses berechnet) aber hilft vielleicht…
import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class MasterMind
{
public static void main(String args[])
{
MasterMind mm = new MasterMind();
String real = "cfca";
System.out.println("Real "+real);
while (true)
{
String guess = mm.makeGuess();
Point response = computeResponse(real, guess);
System.out.println("Guess "+guess+" response "+response);
if (guess.equals(real))
{
break;
}
mm.provideResponse(response);
}
System.out.println("Done");
}
private static final Map<String, String> guessFourMap = new HashMap<String, String>();
static
{
guessFourMap.put("acfb", "dcad");
guessFourMap.put("aebf", "edfd");
guessFourMap.put("aefb", "eacc");
guessFourMap.put("afbe", "bfcd");
guessFourMap.put("bafe", "eadc");
guessFourMap.put("beaf", "edae");
guessFourMap.put("befa", "eeda");
guessFourMap.put("eabf", "fdfb");
guessFourMap.put("aadb", "babd");
guessFourMap.put("abae", "bbcc");
guessFourMap.put("aeaf", "cffd");
guessFourMap.put("cafa", "fdfa");
guessFourMap.put("aaee", "dddf");
}
private int guessCounter = 0;
private String lastGuess = null;
private List<String> currentList = null;
public MasterMind()
{
List<String> completeList = createCompleteList();
List<List<String>> categories = splitByNumberOfDuplicates(completeList);
currentList = new ArrayList<String>();
for (List<String> category : categories)
{
Collections.sort(category);
currentList.addAll(category);
}
//System.out.println("Current list: ");
//for (String s : currentList)
//{
// System.out.println(s);
//}
}
public String makeGuess()
{
guessCounter++;
switch (guessCounter)
{
case 1: lastGuess = "abcd"; break;
case 2: lastGuess = "bcde"; break;
case 3: lastGuess = "cdef"; break;
case 4:
lastGuess = currentList.get(0);
String value = guessFourMap.get(lastGuess);
if (value != null)
{
lastGuess = value;
}
break;
default:
lastGuess = currentList.get(0);
}
return lastGuess;
}
public void provideResponse(Point response)
{
List<String> toRemove = new ArrayList<String>();
for (String possible : currentList)
{
Point possibleResponse = computeResponse(possible, lastGuess);
if (!response.equals(possibleResponse))
{
//System.out.println("Response for "+possible+" would be "+possibleResponse);
toRemove.add(possible);
}
}
currentList.removeAll(toRemove);
//System.out.println("Remaining possibilities: "+currentList);
}
public static Point computeResponse(String real, String guess)
{
// Not very elegant (i.e.: a hack)
List<Character> realList = toCharList(real);
List<Character> guessList = toCharList(guess);
int rightColorAndRightPosition = 0;
for (int i=0; i<real.length(); i++)
{
if (guess.charAt(i) == real.charAt(i))
{
rightColorAndRightPosition++;
realList.set(i, null);
guessList.set(i, null);
}
}
int rightColorAndWrongPosition = 0;
for (int i=0; i<real.length(); i++)
{
Character guessChar = guessList.get(i);
int index = realList.indexOf(guessChar);
if (guessChar != null && index != -1)
{
realList.set(index, null);
rightColorAndWrongPosition++;
}
}
return new Point(rightColorAndRightPosition, rightColorAndWrongPosition);
}
private static List<Character> toCharList(String s)
{
List<Character> result = new ArrayList<Character>();
for (int i=0; i<s.length(); i++)
{
result.add(s.charAt(i));
}
return result;
}
private static List<String> createCompleteList()
{
List<String> result = new ArrayList<String>();
String input[] = { "a", "b", "c", "d", "e", "f" };
CombinationIterable<String> ci = new CombinationIterable<String>(4, input);
for (String sa[] : ci)
{
String string = "";
for (String s : sa)
{
string += s;
}
result.add(string);
}
return result;
}
private static List<List<String>> splitByNumberOfDuplicates(List<String> list)
{
List<List<String>> result = new ArrayList<List<String>>();
for (int i=0; i<4; i++)
{
result.add(new ArrayList<String>());
}
for (String string : list)
{
int duplicates = countDuplicates(string);
List<String> target = result.get(duplicates);
target.add(string);
}
return result;
}
private static int countDuplicates(String s)
{
int count = 0;
for (int i=1; i<s.length(); i++)
{
if (s.charAt(i) == s.charAt(i-1))
{
count++;
}
}
return count;
}
private static class CombinationIterable<T> implements Iterable<T[]>
{
private T input[];
private int sampleSize;
private int numElements;
public CombinationIterable(int sampleSize, T... input)
{
this.sampleSize = sampleSize;
this.input = input.clone();
numElements = (int) Math.pow(input.length, sampleSize);
}
public Iterator<T[]> iterator()
{
return new Iterator<T[]>()
{
private int current = 0;
private int chosen[] = new int[sampleSize];
public boolean hasNext()
{
return current < numElements;
}
public T[] next()
{
@SuppressWarnings("unchecked")
T result[] = (T[]) java.lang.reflect.Array.newInstance(
input.getClass().getComponentType(), sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result** = input[chosen**];
}
increase();
current++;
return result;
}
private void increase()
{
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.length - 1)
{
chosen[index]++;
return;
}
else
{
chosen[index] = 0;
index--;
}
}
}
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a combination");
}
};
}
}
// private static void testResponses()
// {
// testResponse("abcd", "fbdf");
// testResponse("abcd", "abcd");
// testResponse("aabb", "aaab");
// testResponse("aaaa", "bbbb");
// testResponse("dcba", "abcd");
// }
//
// private static void testResponse(String real, String guess)
// {
// System.out.println("real: "+real+" guess: "+guess+" response: "+computeResponse(real, guess));
// }
//
}
(ICH mache gerne Hausaufgaben 
)
[QUOTE=Marco13]
(ICH mache gerne Hausaufgaben )[/QUOTE]
Da fühlt man sich wieder so jung…
Super, Dankeschön
Siehst du denn ne Möglichkeit das zugreifen auf den gesuchten Schlüssel zu verhindern? (computeResponse())
Ich habe das ganze mal versucht umzusetzen, indem ich einfach die nicht in Frage kommenden Antworten aus meiner Liste lösche.
Bsp:
gesucht : e e f a
Versuch: a f e e
Dann wäre das Ergebnis ja weiß = 3, schwarz = 0 (3 richtige Farben sind enthalten und keine an der Richtigen Stelle). Also sortiert man alle Kombinationen aus, die an der ersten Stelle ein a, an der zweiten ein f an der dritten ein e und an der vierten ein e haben.
Das ganze mache ich dann wenn weiß und schwarz gleich 0 sind und einmal wenn schwarz 0 ist.
Mit dieser Methode komme ich allerdings immer auf < 50 Versuche und es sollten ja maximal 6 sein.
Nun, auf der Wiki-Seite stehen ja die Regeln beschrieben, und das sich der Herr Knuth dort ausgedacht hat kommt ja (wenn ich das richtig gesehen habe) mit 5 Zügen aus. Wie viele Züge man mindestens/höchstens/durchschnittlich braucht, wenn man den „naiven“ Ansatz wählt, den du beschrieben hast, weiß ich nicht.
Siehst du denn ne Möglichkeit das zugreifen auf den gesuchten Schlüssel zu verhindern? (computeResponse())
Irgendwo muss die Antwort herkommen. Man könnte sie auch vom Menschen an der Konsole eingeben lassen…
Ist jemand von euch ne Methode bekannt, die relativ wenig Züge braucht, welche das ganze ohne auf den Schlüssel zuzugreifen schafft?
Was ich beschrieben habe greift nicht auf den Schlüssel zu. Lösch’ die Methode, und gib’ die Antworten per Hand ein, dann findet er die Lösung auch in 6 Zügen.
Du vergleichst doch mit dem schlüssel in der methode computeResponse und sortierst auf dem Weg die Liste aus.
oder habe ich da deine Funktion falsch verstanden? Du vergleichst doch ob eine Farbe im Schlüssel enthalten ist und sortierst auf diesem Weg aus.
Die ‘response’ ist in diesem Beispiel einfach ein Point, der verwendet wird, um 2 ints zu speichern: Die Anzahl der richtigen Farben+Position, und die Anzahl der richtigen Farben. Das ist ja das, was man dem Computer (also dem NPC) geben muss, und auf Basis dessen er seinen nächsten “guess” berechnet. Die Methode “computeResponse”, die dort dabei ist, wird NUR verwendet, um diese Response auszurechnen. NUR die Response wird dann dem Computer gegeben, aber die echte Lösung bekommt er NICHT. Die ‘computeResponse’-Methode ist auch static, d.h. der Computer “kann” sich da gar nichts merken. Man könnte die Methode ‘computeResponse’ wie gesagt in eine eigene Klasse auslagern, oder ganz wegnehmen. Intern verwendet der Computerspieler zwar auch eine computeResponse-Methode, aber die errechnet in diesem Fall nur mögliche Antworten auf mögliche echte Kombinationen.
Wenn man’s drauf anlegt: So hat die MasterMindComputerPlayer-Klasse nur noch zwei public-Methoden
Nichts wo er die echte Kombination übergeben bekommt:
// By Marco13 for http://forum.byte-welt.de/showthread.php?p=16589#post16589
import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class MasterMindTest
{
public static void main(String args[])
{
MasterMindComputerPlayer mm = new MasterMindComputerPlayer();
String real = "cfca";
System.out.println("Real "+real);
while (true)
{
String guess = mm.makeGuess();
Point response = computeResponseWithoutTellingTheComputerPlayerTheRealCombination(real, guess);
System.out.println("Guess "+guess+" response "+response);
if (guess.equals(real))
{
break;
}
mm.provideResponse(response);
}
System.out.println("Done");
}
public static Point computeResponseWithoutTellingTheComputerPlayerTheRealCombination(String real, String guess)
{
// Not very elegant (i.e.: a hack)
List<Character> realList = toCharList(real);
List<Character> guessList = toCharList(guess);
int rightColorAndRightPosition = 0;
for (int i=0; i<real.length(); i++)
{
if (guess.charAt(i) == real.charAt(i))
{
rightColorAndRightPosition++;
realList.set(i, null);
guessList.set(i, null);
}
}
int rightColorAndWrongPosition = 0;
for (int i=0; i<real.length(); i++)
{
Character guessChar = guessList.get(i);
int index = realList.indexOf(guessChar);
if (guessChar != null && index != -1)
{
realList.set(index, null);
rightColorAndWrongPosition++;
}
}
return new Point(rightColorAndRightPosition, rightColorAndWrongPosition);
}
private static List<Character> toCharList(String s)
{
List<Character> result = new ArrayList<Character>();
for (int i=0; i<s.length(); i++)
{
result.add(s.charAt(i));
}
return result;
}
}
class MasterMindComputerPlayer
{
private static final Map<String, String> guessFourMap = new HashMap<String, String>();
static
{
guessFourMap.put("acfb", "dcad");
guessFourMap.put("aebf", "edfd");
guessFourMap.put("aefb", "eacc");
guessFourMap.put("afbe", "bfcd");
guessFourMap.put("bafe", "eadc");
guessFourMap.put("beaf", "edae");
guessFourMap.put("befa", "eeda");
guessFourMap.put("eabf", "fdfb");
guessFourMap.put("aadb", "babd");
guessFourMap.put("abae", "bbcc");
guessFourMap.put("aeaf", "cffd");
guessFourMap.put("cafa", "fdfa");
guessFourMap.put("aaee", "dddf");
}
private int guessCounter = 0;
private String lastGuess = null;
private List<String> currentList = null;
public MasterMindComputerPlayer()
{
List<String> completeList = createCompleteList();
List<List<String>> categories = splitByNumberOfDuplicates(completeList);
currentList = new ArrayList<String>();
for (List<String> category : categories)
{
Collections.sort(category);
currentList.addAll(category);
}
//System.out.println("Current list: ");
//for (String s : currentList)
//{
// System.out.println(s);
//}
}
public String makeGuess()
{
guessCounter++;
switch (guessCounter)
{
case 1: lastGuess = "abcd"; break;
case 2: lastGuess = "bcde"; break;
case 3: lastGuess = "cdef"; break;
case 4:
lastGuess = currentList.get(0);
String value = guessFourMap.get(lastGuess);
if (value != null)
{
lastGuess = value;
}
break;
default:
lastGuess = currentList.get(0);
}
return lastGuess;
}
private static Point computeResponse(String real, String guess)
{
// Not very elegant (i.e.: a hack)
List<Character> realList = toCharList(real);
List<Character> guessList = toCharList(guess);
int rightColorAndRightPosition = 0;
for (int i=0; i<real.length(); i++)
{
if (guess.charAt(i) == real.charAt(i))
{
rightColorAndRightPosition++;
realList.set(i, null);
guessList.set(i, null);
}
}
int rightColorAndWrongPosition = 0;
for (int i=0; i<real.length(); i++)
{
Character guessChar = guessList.get(i);
int index = realList.indexOf(guessChar);
if (guessChar != null && index != -1)
{
realList.set(index, null);
rightColorAndWrongPosition++;
}
}
return new Point(rightColorAndRightPosition, rightColorAndWrongPosition);
}
private static List<Character> toCharList(String s)
{
List<Character> result = new ArrayList<Character>();
for (int i=0; i<s.length(); i++)
{
result.add(s.charAt(i));
}
return result;
}
public void provideResponse(Point response)
{
List<String> toRemove = new ArrayList<String>();
for (String possible : currentList)
{
Point possibleResponse = computeResponse(possible, lastGuess);
if (!response.equals(possibleResponse))
{
//System.out.println("Response for "+possible+" would be "+possibleResponse);
toRemove.add(possible);
}
}
currentList.removeAll(toRemove);
//System.out.println("Remaining possibilities: "+currentList);
}
private static List<String> createCompleteList()
{
List<String> result = new ArrayList<String>();
String input[] = { "a", "b", "c", "d", "e", "f" };
CombinationIterable<String> ci = new CombinationIterable<String>(4, input);
for (String sa[] : ci)
{
String string = "";
for (String s : sa)
{
string += s;
}
result.add(string);
}
return result;
}
private static List<List<String>> splitByNumberOfDuplicates(List<String> list)
{
List<List<String>> result = new ArrayList<List<String>>();
for (int i=0; i<4; i++)
{
result.add(new ArrayList<String>());
}
for (String string : list)
{
int duplicates = countDuplicates(string);
List<String> target = result.get(duplicates);
target.add(string);
}
return result;
}
private static int countDuplicates(String s)
{
int count = 0;
for (int i=1; i<s.length(); i++)
{
if (s.charAt(i) == s.charAt(i-1))
{
count++;
}
}
return count;
}
private static class CombinationIterable<T> implements Iterable<T[]>
{
private T input[];
private int sampleSize;
private int numElements;
public CombinationIterable(int sampleSize, T... input)
{
this.sampleSize = sampleSize;
this.input = input.clone();
numElements = (int) Math.pow(input.length, sampleSize);
}
public Iterator<T[]> iterator()
{
return new Iterator<T[]>()
{
private int current = 0;
private int chosen[] = new int[sampleSize];
public boolean hasNext()
{
return current < numElements;
}
public T[] next()
{
@SuppressWarnings("unchecked")
T result[] = (T[]) java.lang.reflect.Array.newInstance(
input.getClass().getComponentType(), sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result** = input[chosen**];
}
increase();
current++;
return result;
}
private void increase()
{
int index = chosen.length - 1;
while (index >= 0)
{
if (chosen[index] < input.length - 1)
{
chosen[index]++;
return;
}
else
{
chosen[index] = 0;
index--;
}
}
}
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a combination");
}
};
}
}
}
Dann hab ich wohl den teil mit dem löschen falsch aufgefasst.
Du löscht also alle Kombinationen, welche die gleiche anzahl an rightColorAndRightPosition und rightColorAndWrongPosition haben und nichts anderes?
bsp:
key: a b c d
try: a c d d
x1: a b d e
x2: a b c e
–> rightColorAndRightPosition 2 und rightColorAndWrongPosition 1
somit würde ein Ein Eintrag, wie x1 aus der Liste fliegen und x2 würde stehen bleiben da (3,1)?
Das war der Teil, der auf der Wikipedia-Seite nicht explizit beschrieben war, aber… ich gehe mal davon aus, dass das so laufen muss. Theoretisch könnte man da noch einiges deutlich trickreicher machen, und die computeResponse-Methode ist (wie auch im Kommentar steht) ziemlich krampfig, aber konzeptuell denke ich, dass man in irgendeiner (mehr oder weniger trickreichen) Form die “Liste der Möglichkeiten” immer weiter ausdünnen muss…
Ich versteh nicht ganz, was du mit den Charlisten willst. Ich habe jetzt probiert alle Kombinationen aus meiner Liste zu löschen, welche die gleiche Anzahl rightColorAndRightPosition und rightColorAndWrongPosition haben. Muss ich da noch etwas beachten oder wars das?
Wie gesagt: Die Berechnung der Respone ist ziemlich krampfig, wenn du es ohne Charlisten implementierst ist das ja OK (die werden ja nur da verwendet).
Das wichtigste an dem Six-Guess ist wohl, welche Guesses man zuerst macht.
Ich weiß bloß nicht, was du mit den Charlisten machst. Was bedeutet deine zweite for schleife in computeResponse? was überprüfst du da und was bezweckst du damit, wenn du den index und voralllem null einträgst?
Und nochmal : Die Berechnung der Respone ist ziemlich krampfig. War auch nicht Teil der ursprünglichen Frage. Du kannst dir gerne eine andere Methode basteln, die aus zwei Strings (oder wie auch immer du den Zustand repräsentierst) die Antwort berechnet. Sich nur in Foren Code zusammenzuschnorren bringt’s ja nicht…
In diesem Fall wird erst überprüft, welche Einträge die Richtige Farbe und Position haben, und diese Einträge werden dann gelöscht, denn in der zweiten Schleife wird überprüft, welche Einträge die richtige Farbe aber die falsche Position haben - und dort will man ja NICHT nochmal die mitzählen, die schon beim ersten Durchlauf erfasst wurden.