Ich muss in Info einen Entwurf für ein Tic Tac Toe Spiel machen, dessen KI mit einen Spielbaum läuft. Ich habe mir bis jetzt folgendes gedacht:
[SPOILER]```
import java.util.Arrays;
public class Field {
private char[][] field;
public Field() {
Arrays.fill(field, ' ');
}
public char[][] getFieldArray() {
return field;
}
public void set(int x, int y, char c) {
field[x][y] = c;
}
public char get(int x, int y) {
return field[x][y];
}
public boolean isFilled() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (field**[j] != ' ') {
return false;
}
}
}
return true;
}
public boolean isSolved() {
return false;
}
}
[/SPOILER]
[SPOILER]```
public interface AI {
Field calculateNext(Field current);
}
```[/SPOILER]
[SPOILER]
private Object key;
private List<Tree> children;
public Tree(Object key) {
children = new ArrayList<Tree>();
setKey(key);
}
public Collection<Tree> getChildren() {
return children;
}
public void addChild(Tree child) {
children.add(child);
}
public void clear() {
children.clear();
}
public void removeChild(Tree child) {
children.remove(child);
}
public Object getKey() {
return key;
}
public <T> T getKey(Class<T> clazz) {
return clazz.cast(getKey());
}
public void setKey(Object key) {
this.key = key;
}
@Override
public String toString() {
return getKey().toString();
}
}
[/SPOILER]
Der Baum ist nicht generisch, da viele bei uns Generics nicht kennen.
Ich dachte nun, dass die KI einfach AI implementiert und dann für das aktuelle Feld immer das kalkulierte zurückgegeben wird. Nur weiß ich nicht, wie ich das machen soll. Wäre über Ansätze erfreut :D
Du musst eine Tiefen- oder Breitensuche implementieren die nacheinander alle Züge durchspielt. Dann markierst du die resultierenden Bäume danach ob du gewinnst, ein Unentschieden rauskommt oder ob du verlierst.
Wenn’s einen Baum gibt in dem du gewinnst, nimmst du den. Wenn’s einen solchen nicht gibt, nimmst du einen Unentschieden-Baum. Verlieren sollte gar nicht vorkommen da die Züge immer so gewählt werden können dass es höchstens ein Unentschieden gibt.
Hm. Nebulös: Erstelle eine Kopie des übergebenen Feldes, setze einen neuen Spielstein in dieser Kopie, und gib’ die Kopie dann zurück.
BTW: Ist irgendwo gesagt, dass dieser Spielbaum explizit konstruiert werden muss? Üblicherweise wird der nur “on the fly”, während der Rekursion, quasi “virtuell” aufgebaut.
BTW2: Ich würde die “getFieldArray”-Methode aus Field rausnehmen. Das ist ein Implementierungsdetail.
Ich habe mir was überlegt, hab dann aber ja get und set gemacht. Scheint verloren gegangen zu sein.
[quote=schlingel;89286]Du musst eine Tiefen- oder Breitensuche implementieren die nacheinander alle Züge durchspielt. Dann markierst du die resultierenden Bäume danach ob du gewinnst, ein Unentschieden rauskommt oder ob du verlierst.
Wenn’s einen Baum gibt in dem du gewinnst, nimmst du den. Wenn’s einen solchen nicht gibt, nimmst du einen Unentschieden-Baum. Verlieren sollte gar nicht vorkommen da die Züge immer so gewählt werden können dass es höchstens ein Unentschieden gibt.[/quote]
Könntest du mir das mal genauer erklären? Ich hätte jetzt gedacht, dass man z.B nicht als erstes setzt, somit wird der AI das Feld mit einem Stein übergeben. Zur Auswahl stehen 8 Felder. Beim nächsten Zug sind es ja nur noch 6 Felder die belegt werden können, dann 4 usw usf.
Ich hätte jetzt Probleme den Baum zu generieren und zu „bewerten“. Das mit dem on-the-fly hört sich an, als ob nach jedem Zug der Baum neu gestaltet wird. Wegen der Beewertung oder dem Suchen dachte ich an sowas wie ein Strategy interface, womit man vielleicht sogar Strategien implementieren kann (wie Zwickmühlen oder so), aber das scheeint ja schon quasi da drin zu sein.
Wäre nett wenn ihr mir vielleicht genauer helfen könntet. Denn Tic Tac Toe schaffe ich, eine KI auch, aber nicht als Spielbaum!
Zuerst hat man ein leeres Spielfeld.
Das ist ein Spielstand.
Darauf kann man exact 9 Züge vollführen.
Jeder dieser 9 Züge führt zu einem neuen hypothetischen Spielstand mit je einem gesetzten Feld.
Diese übergibt man nun der AI. Die aus ihrer Sicht das beste (Minimum aus unserer Sicht) aus den jeweiligen Situationen macht. Das macht der Gegner indem er für jede Spielsituation einen Baum aufspannt der die jeweils 8 verbliebenen Züge hat und gibt dies an unseren Hypothetisch optimalen Spieler zurück. Dies macht man solange bis man zu einem Terminalen Spielstand kommt.
Nun wählen wir aus den 9 Möglichen Zügen das beste Ergebnis und führen diesen Zug aus.
Du versuchst also des Gegners Ergebnis nach oben zu beschränken und er versucht deines nach oben zu beschränken.
…
Ich hatte mal ein Aufgabenblatt rumliegen bei dem dies recht ausführlich beschrieben war, dass ich leider nirgends finde.
Ja, MiniMax, ggf. mit Alpha-Beta-Pruning. Das ist praktisch für alle “vollinformierten” 2-Spieler-Brettspiele gleich, und dazu braucht man im allgemeinen nur drei Funktionen:
Damit klärt sich vielleicht auch, was mit “on the fly” gemeint ist: Man baut nicht wirklich eine Baum-Datenstruktur auf. Überleg’ mal wie viele Knoten dieser Baum schon für TicTacToe hätte. Bei jedem auch nur einen Hauch komplexeren Spiel würde einem da nach wenigen Zügen der Speicher platzen. Stattdessen läuft das ganze GROB vereinfacht im Pseudocode so ab wie
berechneBestesErreichbaresErgebnis(aktuellerSpieler)
{
für (jeden möglichen Zug z)
{
mache Zug z
berechneBestesErreichbaresErgebnis(andererSpieler);
mache Zug z rückgängig
}
}
Aber: In diesem Fall (d.h. bei TicTacToe) KANN man den Spielbaum auch komplett aufbauen, da spricht grundsätlich nichts dagegen. Es bringt nicht konkret irgendwas, aber … auch mit diesem Spielbaum kann man einen perfekt spielenden Spieler bauen.
Leute, das ist TicTacToe! Da reicht der naive Ansatz vollkommen aus. @groggy hat so schon Probleme mit der Angabe, warum blast ihr die Schwierigkeit weiter auf?
Gar nicht so viele. Warum also der Aufwand?
Richtig. Deswegen fängt man mal primitiv an bevor man sich so Sachen wie MiniMax anschaut. Und später landet man sowieso bei A* dessen Funktionen man entsprechend anpasst.
Ich würde so vorgehen, dass ich entweder den Spieler oder die KI den ersten Zug machen lasse. Bei der KI ist es trivialerweise das mittlere Feld. Immer.
Von dort aus kannst du dann den Baum aufbauen. Was passiert wenn der Spieler das obere linke Feld auswählt. Dann kann die KI das Feld rechts daneben auswählen, oder das ganz rechts, oder das links in der Mitte, etc. Von dort kann der Spieler eines der verbliebenen Felder auswählen. Da musst du wieder alle Möglichkeiten drüber iterieren lassen.
Wenn du so einen Entscheidungsbaum immer bis zum Ende (Unentschieden, Sieg oder Niederlage) durchführst bevor du den ersten Zug varierst hast du eine Tiefensuche implementiert. Die sprengt dir für dieses Beispiel keinesfalls den Speicher.
Wenn du an den ersten Baum kommst der mit Sieg für KI endet nimm den Zug. Findest du keinen Sieg-Baum nimm den ersten Unentschieden-Baum. Da die KI perfekt spielt gibt es für sie niemals eine Niederlage. (Du musst dir nur einen Unentschieden-Baum merken.)
Du erstellst also „on-the-fly“ jede Runde erneut alle Möglichkeiten. Ist, wie gesagt in diesem speziellen Fall, trivial und auch relativ flott.
hahahaha, wird unser groggy doch vom lehrer gefordert? xD
*** Edit ***
Nein das dürfte sogar ziemlich angehnehm „schnell“ sein.
Viele Möglichkeiten gibt es zwar, aber nach jedem Zug werde diese ja geringer,
bzw muss der computer auch gar nicht alle ausprobieren - eben nur bis zum „sieg baum“ oder
„unentschieden baum“
Ich denke, es gibt noch mindestens einen weiteren Grund, warum sowas wie MiniMax nicht am Beispiel „Schach“ erklärt wird :rolleyes: Inwieweit welcher Ansatz geeignet ist, kann man vielleicht nur beurteilen, wenn man weiß, ob das eine Aufgabe aus der Vorlesung „Informatik 1 - Bäume und andere Trivialitäten“ ist, oder aus „Intellektik - Künstliche Intelligenz und Spieltheorie“. Wahrscheinlich liegt die Wahrheit irgendwo dazwischen.
EDIT:
„Lehrer“…? Dann liegt die Wahrheit nicht dazwischen, sondern sogar noch „links“ vom erstgenannten. Kann ja keiner ahnen :o
Hier reicht ja fürs erste auch eine einfache Bewertung die 2 Züge im Vorraus plant. Jeder mögliche Zug erhält entweder 1 für sofortigen Sieg oder die Bewertung des darauf folgenden Zugs. Dabei wäre Gegner gewinnt -1 und kein Ergebnis oder Unentschieden 0.
ich bin einfach zu doof für diese Aufgabe. Sitze da seit einer Tagen dran und habe kein Ergebnis vor mir liegen. Irgendwie kriege ich das Konzept dahinter nicht in den Kopf, denn ich denke mal schwer kann das nicht sein.
was genau schaffst du denn jetzt nicht? ^^
Du hast das array von feldern. Jedes von denen hat nen State, besetzt - frei, wenn
besetzt welcher Spieler. So weit bist du denk ich mal? ^^
Nun musst du doch nur schauen welche züge möglich sind, geht ja auch ganz stupide wegen
der geringen menge durchs ganze spielfeld iterieren, wenn besetzt → alle umrandenden felder,
davon die nicht besetzten rauskramen in ne liste packen. Nun die Liste nacheinander abarbeiten und
Bis zum Ende schauen ob sieg (3.ter Stein eingelegt - oder einlegbar) , niederlage (spieler könnte 3.ten Stein eingelegt haben) oder nix.
Wenn du willst versuch ichs morgen mal
*** Edit ***
Sorry für den Jfo link,
aber da hat jemand doch was interessantes dazu gepostet…
public interface Field {
/**
* @return All possible Moves, an empty Game is are all numbers from 1 to 9.
*/
Set<Integer> possibleMoves();
/**
* @parameter move is a number from 1 to 9
* @return a new Field after applying the move
*/
Field applyMove(Integer move) throws IllegalMoveException;
/**
* @return the State of the Game.
*/
GameState getGameState();
}
enum GameState {
X_WIN, O_WIN, TIE, STILL_RUNNING
}
Ein nächster Schritt wäre dann mal die Implementierung des Interfaces.
Das Field, so wie es im Moment implementiert ist, incl. der API, die du damit zur Verfügung stellst macht es nicht unbedingt leichter.
