[Erledigt]Tic-Tac-Toe und der Minimax-Algorithmus
-
Hi Leute
Ich will mich etwas in das Thema "Künstliche Intelligenz" einarbeiten und nun versuchte ich ein kleines Tic-Tac-Toe Programm zu entwerfen. Das Programm soll zunächst so einfach wie möglich sein, also Konsolenbasierte Ausgabe. Mein Problem besteht darin, dass ich es einfach nicht schaffe meiner "KI" auch nur einen Hauch von "Intelligenz" zu geben. Mein Ansatz war der Minimax-Algorithmus, jedoch gelingt es mir nicht diesen zu realisieren, mein Code:class Computer { private: int** field; int freieFelder; public: Computer( int** field ); ~Computer() {} int makeMoveMax( int** field, std::vector<Coordinates> pmoves ); // Computer int makeMoveMin( int** field, std::vector<Coordinates> pmoves ); // Spieler int bestMove(); std::vector<Coordinates> possibleMoves( int ** ); }; Computer::Computer( int** field ) { this->field = field; freieFelder = countFreeFields(field); }Die Klasse "Computer" soll also alle Bestandteile des Algorithmus selbstständig durchführen, so, dass im Hauptprogramm lediglich ein Spielfeld erstellt und übergeben werden und eine Funktion geschrieben werden muss, die Computer und Spieler nacheinander ziehen lässt. Nun zum Hauptproblem, dem Algorithmus:
int Computer::bestMove() { std::vector<Coordinates> coords = possibleMoves( field ); // anzahl der möglichen züge ermitteln for( int i=0; i<coords.size(); i++ ) // computer zieht { int** arrcpy = copyArray( field, 3, 3 ); // derzeitiges Spielfeld kopieren arrcpy[coords.front().x][coords.front().y] = 0; std::vector<Coordinates> new_coords; for( int j=1; j<coords.size(); j++ ) // vector bis auf das erste element kopieren { new_coords.push_back( coords[j] ); } coords = new_coords; std::cout << "makeMoveMin = " << makeMoveMin( arrcpy, new_coords ) << std::endl; if( makeMoveMin( arrcpy, new_coords ) == 1 ) // wenn möglichkeit gefunden, koordinaten zurückgeben { field[coords[i].x][coords[i].y] = 0; std::cout << "MOVE: X = " << coords[i].x << ", Y = " << coords[i].y << std::endl; return 1; } //return coords[i]; } return 0; } int Computer::makeMoveMax( int** field, std::vector<Coordinates> pmoves ) { std::vector<Coordinates> coords = possibleMoves( field ); if( checkWin( field ) == 0 ) return 1; // wenn computer gewonnen hat int** arrcpy = copyArray( field, 3, 3 ); for( int i=0; i<pmoves.size(); i++ ) { arrcpy[pmoves.front().x][pmoves.front().y] = 0; // computer zieht std::vector<Coordinates> new_pmoves; for( int j=1; j<pmoves.size(); j++ ) // vector bis auf das erste element kopieren { new_pmoves.push_back( pmoves[j] ); } pmoves = new_pmoves; if( makeMoveMin( arrcpy, new_pmoves ) == 1 ) // wenn ein positives ergebnis erzielt wurde return makeMoveMin( arrcpy, new_pmoves ); } return -1; // wenn keine Lösung gefunden wurde } int Computer::makeMoveMin( int** field, std::vector<Coordinates> pmoves ) { std::vector<Coordinates> coords = possibleMoves( field ); if( checkWin( field ) == 1 ) { showField(field); return 0; } // wenn Spieler gewonnen hat int** arrcpy = copyArray( field, 3, 3 ); for( int i=0; i<pmoves.size(); i++ ) { arrcpy[pmoves.front().x][pmoves.front().y] = 1; // Spieler zieht std::vector<Coordinates> new_pmoves; for( int j=1; j<pmoves.size(); j++ ) // vector bis auf das erste element kopieren { new_pmoves.push_back( pmoves[j] ); } pmoves = new_pmoves; return makeMoveMax( arrcpy, new_pmoves ); } } std::vector<Coordinates> Computer::possibleMoves( int** field ) { std::vector<Coordinates> pmoves; for( int i=0; i<3; i++ ) for( int j=0; j<3; j++ ) { if( field[i][j] == -1 ) { Coordinates coords( i, j ); pmoves.push_back( coords ); } } return pmoves; }In einer weiteren Datei werden Funktionen definiert, die in der Klasse verwendet werden, die eventuell auch wichtig sind:
struct Coordinates { Coordinates( int x_, int y_ ) : x(x_), y(y_) { } int x; int y; }; int checkWin( int** field ) { if( field[0][0] == 1 && field[1][1] == 1 && field[2][2] == 1 || field[2][0] == 1 && field[1][1] == 1 && field[0][2] == 1 || field[0][0] == 1 && field[1][0] == 1 && field[2][0] == 1 || field[0][1] == 1 && field[1][1] == 1 && field[2][1] == 1 || field[0][2] == 1 && field[1][2] == 1 && field[2][2] == 1 || field[0][0] == 1 && field[0][1] == 1 && field[0][2] == 1 || field[1][0] == 1 && field[1][1] == 1 && field[1][2] == 1 || field[2][0] == 1 && field[2][1] == 1 && field[2][2] == 1 ) return 1; // wenn der Spieler gewonnen hat else if( field[0][0] == 0 && field[1][1] == 0 && field[2][2] == 0 || field[2][0] == 0 && field[1][1] == 0 && field[0][2] == 0 || field[0][0] == 0 && field[1][0] == 0 && field[2][0] == 0 || field[0][1] == 0 && field[1][1] == 0 && field[2][1] == 0 || field[0][2] == 0 && field[1][2] == 0 && field[2][2] == 0 || field[0][0] == 0 && field[0][1] == 0 && field[0][2] == 0 || field[1][0] == 0 && field[1][1] == 0 && field[1][2] == 0 || field[2][0] == 0 && field[2][1] == 0 && field[2][2] == 0 ) return 0; // wenn der Computer gewonnen hat else return -1; // wenn das Spiel noch nicht vorbei ist } int showField( int** field ) { std::cout << "-------------" << "\n| " << field[0][0] << " | " << field[1][0] << " | " << field[2][0] << " |" << "\n-------------" << "\n| " << field[0][1] << " | " << field[1][1] << " | " << field[2][1] << " |" << "\n-------------" << "\n| " << field[0][2] << " | " << field[1][2] << " | " << field[2][2] << " |" << "\n-------------" << std::endl; } int** copyArray( int** array, unsigned int size_a, unsigned int size_b ) { int** copyed_array = new int*[size_a]; for( int i=0; i<size_a; i++ ) copyed_array[i] = new int[size_b]; for( int a=0; a<size_a; a++ ) for( int b=0; b<size_b; b++ ) copyed_array[a][b] = array[a][b]; return copyed_array; } int countFreeFields( int** field ) { int res = 0; for( int a = 0; a<3; a++ ) for( int b=0; b<3; b++ ) { if( field[a][b] == -1 ) ++ res; } return res; }Leider gibt mir die Ausgabe nur mist aus:
------------- | -1 | -1 | -1 | ------------- | -1 | -1 | -1 | ------------- | -1 | -1 | -1 | ------------- makeMoveMin = 1 MOVE: X = 0, Y = 1 ------------- | -1 | -1 | -1 | ------------- | 0 | -1 | -1 | ------------- | -1 | -1 | -1 | ------------- Spieler am Zug Feld X: 2 Feld Y: 1 ------------- | -1 | 1 | -1 | ------------- | 0 | -1 | -1 | ------------- | -1 | -1 | -1 | ------------- makeMoveMin = 1 MOVE: X = 0, Y = 2 ------------- | -1 | 1 | -1 | ------------- | 0 | -1 | -1 | ------------- | 0 | -1 | -1 | ------------- Spieler am Zug Feld X: 2 Feld Y: 2 ------------- | -1 | 1 | -1 | ------------- | 0 | 1 | -1 | ------------- | 0 | -1 | -1 | ------------- ------------- | 0 | 1 | 0 | ------------- | 0 | 1 | -1 | ------------- | 0 | 1 | -1 | ------------- ------------- | 0 | 1 | 0 | ------------- | 0 | 1 | 0 | ------------- | 0 | 1 | -1 | ------------- makeMoveMin = -1 ------------- | 0 | 1 | 0 | ------------- | 0 | 1 | -1 | ------------- | 0 | 1 | -1 | ------------- ------------- | 0 | 1 | 0 | ------------- | 0 | 1 | 0 | ------------- | 0 | 1 | -1 | ------------- makeMoveMin = -1 makeMoveMin = -1 ------------- | -1 | 1 | -1 | ------------- | 0 | 1 | -1 | ------------- | 0 | -1 | -1 | ------------- Spieler am Zug Feld X: //...im letzten Abschnitt wird also kein möglicher Zug mehr gefunden. Nun meine Frage(n):
- Ist mein Programmcode üerhaupt als Lösungsansatz tauglich?
- Hat jemand ein Paar Tipps für mich wie ich meine KI dazu bringe "intelligente" Züge zu machen?Mfg Auma
-
Entschuldigt, Kann geschlossen werden habe es nun hinbekommen
Mfg
-
nun ja, ich kenn den minimax algorithmus nicht, aber ich würde so ran gehen:
das feld hat nur neun felder
der erste zug hat also 9 möglichkeiten, der zweite 8, der dritte 7...
das heist, es gibt 362880 mögliche wege zu einem vollen spielbrett zu kommen.
Dann gehen noch vorzeitige enden, aufgrund dder unfähigkeit des spielers
wegDas heißt man kann am anfang (initialisierungsphase) eine Datenbank aufbauen, mit allen möglichen Spielzügen (Baum).
Dann weist du jedem Knoten zu, bei wievielen Enden der Computer gewinnt/verliert, so hat man zu jedem Entscheidungsknoten die info über Gewinnchance für die möglichen züge.Wärend des spiel geht man je nach spielerentscheidung dann im baum immer mit und wählt dann den Ast, mit der höchsten wahrscheinlichkeit.