Tic Tac Toe und Minimax - Erstellen einer unvollkommenen KI auf einem Mikrocontroller
Ich habe ein Tic-Tac-Toe-Spiel auf einem Mikrocontroller erstellt, das eine perfekte KI enthält (das bedeutet, dass es nicht verliert). Ich habe dafür keinen Minimax-Algorithmus verwendet, nur eine kleine Zustandsmaschine mit allen möglichen und optimalen Zügen. Mein Problem ist jetzt, dass ich verschiedene Schwierigkeiten umsetzen wollte (Easy, Medium und Hard). Die KI wäre bisher die Schwierigste. Also habe ich mir überlegt, wie ich das am besten mache und wollte schließlich dasminimax -Algorithmus, aber auf eine Weise, dass er alle Punkte für alle Spielpositionen berechnet, so dass ich manchmal auch den zweitbesten Punktestand anstelle des besten auswählen kann. Da ich nicht immer alle diese Berechnungen auf dem Mikrocontroller selbst durchführen kann, wollte ich ein kleines Programm erstellen, das ich auf meinem Computer ausführen kann und das mir Arrays aller möglichen Platinenzustände (in Bezug auf Symmetrie usw. zur Minimierung des Speichers) liefert verwendet) und ihre entsprechenden Bewertungen. Dazu habe ich zunächst versucht, den Minimax-Algorithmus selbst zu implementieredepth um das @ richtig zu berechnscores von jedem Staat. Es sollte mir dann (vorerst) alle optimalen Züge in einem Array zurückgeben. Es scheint jedoch nicht so gut zu funktionieren. Ich habe versucht, es mit einigen @ zu debuggprintf Linien. Hier ist der Code der beiden bisherminimax Funktion sowie meine Hauptfunktion:
static int minimax(int *board, int depth)
{
int score;
int move = -1;
int scores[9];
int nextDepth;
printf("\n----- Called Minimax, Depth: %i -----\n\n", depth);
if(depth%2 ==1){
player = -1;
} else {
player = 1;
}
printf("Player: %i\n---\n", player);
if(isWin(board) != 0){
score = (10-depth)*winningPlayer;
printf("Player %i won on depth %i\n", winningPlayer, depth);
printf("Resulting score: (10-%i)*%i = %i\nScore returned to depth %i\n---\n", depth, winningPlayer, score, depth-1);
return score;
}
score = -20;
nextDepth = depth+1;
printf("Next depth is %i\n---\n", nextDepth);
int i;
for(i=0; i<9; i++){
if(board[i] == 0) {
if(nextDepth%2 ==0) {
player = -1;
} else {
player = 1;
}
printf("Found vacant space at position %i\n", i);
printf("Set value of position %i to %i\n---\n", i, player);
board[i] = player;
int thisScore = minimax(board, nextDepth);
printf("Value of the move at position %i on next depth %i is %i\n---\n", i, nextDepth, thisScore);
scores[i] = thisScore;
if(thisScore > score){
printf("New score value is greater than the old one: %i < %i\n---\n", thisScore, score);
score = thisScore;
move = i;
g_moves[nextDepth-1] = move;
printf("Score was set to %i\n", thisScore);
printf("Remembered move %i\n---\n", move);
}
board[i] = 0;
printf("Value of position %i was reset to 0 on next depth %i\n---\n", i, nextDepth);
}
}
if(move == -1) {
printf("Game ended in a draw.\n Returned score: 0\n---\n");
return 0;
}
printf("Move at position %i was selected on next depth %i\n", move, nextDepth);
printf("Returning score of %i to depth %i\n---\n", score, depth);
return score;
}
Dasmain ist:
int main(int argc, char **argv)
{
memcpy(board, initBoard, sizeof(board));
int score = 0;
int depth = getDepth(board);
score = minimax(board, depth);
printf("\n--- finished ---\n\n");
printf("Moves with the highest score: ");
int i;
for(i=0; i<9; i++){
printf("%i | ", g_moves[i]);
}
printf("\n");
printf("The score is %i\n", score);
printf("The best next board is: \n|----|----|----|\n");
for(i=0; i<3; i++){
printf("| %-2i ", board[i]);
}
printf("|\n|----|----|----|\n");
for(i=3; i<6; i++){
printf("| %-2i ", board[i]);
}
printf("|\n|----|----|----|\n");
for(i=6; i<9; i++){
printf("| %-2i ", board[i]);
}
printf("|\n|----|----|----|\n");
return 0;
}
Außerdem habe ich einige Variablen:
//1 = Beginning Player
//-1 = second Player
static int player;
static int winningPlayer = 0;
static int g_moves[9];
/* 0 1 2
* 3 4 5
* 6 7 8
*/
int initBoard[9] = {
0, 0, 0,
0, 0, 0,
0, 0, 0,
};
int board[9];
Sowie meine gewinnende Funktion:
int isWin(int *board)
{
unsigned winningBoards[8][3] = {
{board[0], board[1], board[2],},
{board[3], board[4], board[5],},
{board[6], board[7], board[8],},
{board[0], board[3], board[6],},
{board[1], board[4], board[7],},
{board[2], board[5], board[8],},
{board[0], board[4], board[8],},
{board[2], board[4], board[6],},
};
int i;
for(i=0; i<8; i++){
if( (winningBoards[i][0] != 0) &&
(winningBoards[i][0] == winningBoards[i][1]) &&
(winningBoards[i][0] == winningBoards[i][2])){
winningPlayer = winningBoards[i][0];
return winningPlayer;
}
}
return 0;
}
Aus irgendeinem Grund kehrt der Minimax das letzte Mal von @ zurücdepth 7 Schritt für Schritt zudepth 1, mein Array wird überschriebeng_moves mit allen Nullen führt also zu den folgenden Zeilen in meiner Druckausgabe (nur die letzten 70 Zeilen):
...
----- Called Minimax, Depth: 7 -----
Player: -1
---
Player 1 won on depth 7
Resulting score: (10-7)*1 = 3
Score returned to depth 6
---
Value of the move at position 2 on next depth 7 is 3
---
Value of position 2 was reset to 0 on next depth 7
---
Move at position 0 was selected on next depth 7
Returning score of 3 to depth 6
---
Value of the move at position 3 on next depth 6 is 3
---
Value of position 3 was reset to 0 on next depth 6
---
Move at position 0 was selected on next depth 6
Returning score of 3 to depth 5
---
Value of the move at position 4 on next depth 5 is 3
---
Value of position 4 was reset to 0 on next depth 5 ,
---
Move at position 0 was selected on next depth 5
Returning score of 3 to depth 4
---
Value of the move at position 5 on next depth 4 is 3
---
Value of position 5 was reset to 0 on next depth 4
---
Move at position 0 was selected on next depth 4
Returning score of 3 to depth 3
---
Value of the move at position 6 on next depth 3 is 3
---
Value of position 6 was reset to 0 on next depth 3
---
Move at position 0 was selected on next depth 3
Returning score of 5 to depth 2
---
Value of the move at position 7 on next depth 2 is 5
---
Value of position 7 was reset to 0 on next depth 2
---
Move at position 0 was selected on next depth 2
Returning score of 5 to depth 1
---
Value of the move at position 8 on next depth 1 is 5
---
Value of position 8 was reset to 0 on next depth 1
---
Move at position 0 was selected on next depth 1
Returning score of 5 to depth 0
---
--- finished ---
Moves with the highest score: 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
The score is 5
The best next board is:
|----|----|----|
| 0 | 0 | 0 |
|----|----|----|
| 0 | 0 | 0 |
|----|----|----|
| 0 | 0 | 0 |
|----|----|----|
Wenn Sie weitere Informationen benötigen, um mir zu helfen, gebe ich diese gerne an Sie weiter, wenn ich sie selbst habe.
Danke im Voraus
BEARBEITEN Also habe ich mein @ umgeschriebminimax -Funktion, so dass jetzt alle möglichen Board-Status in einer TXT-Datei über die Konsole gedruckt werden (cmd: ./NAME_OF_FILE> DEST_NAME.txt im entsprechenden Ordner). Der Code lautet wie folgt:
int minimax(int *board, int depth)
{
g_node++;
int player;
int move = -1;
int score = -20;
int thisScore = -20;
int i;
if(isWin(board) != 0){
printf("\nNode: %i\n", g_node);
printf("Board state:");
for(i=0;i<9;i++) {
if((i%3) == 0)
printf("\n");
printf("%2i ", board[i]);
}
printf("\n");
printf("has a score of %i\n", (10-depth)*winningPlayer);
return (10-depth)*winningPlayer;
}
if(depth%2 ==1){
player = -1;
} else {
player = 1;
}
for(i=0; i<9; i++){
if(board[i] == 0){
board[i] = player;
thisScore = minimax(board, depth+1);
if(thisScore > score){
score = thisScore;
move = i;
}
board[i] = 0;
}
}
printf("\nNode: %i\n", g_node);
printf("Board state:");
for(i=0;i<9;i++) {
if((i%3) == 0)
printf("\n");
printf("%2i ", board[i]);
}
printf("\n");
if(move == -1){
printf("has a score of 0\n");
return 0;
}
printf("has a score of %i\n", score);
return score;
}
Mein nächster Schritt ist das Ausdrucken der Tafel mit dem maxscore jeder Bewegung an der entsprechenden Position.
Example:
10 8 10
8 7 8
10 8 10
for the empty board at the beginning.
EDIT 2: Ich habe jetzt eine weitere Funktion namens @ hinzugefüprintScoredBoards, das im Grunde das tun soll, was ich oben in meiner letzten Bearbeitung beschrieben habe, aber es gibt ein Problem. Da es immer möglich ist, nach dem 5. Zug zu gewinnen, wenn Ihr Gegner dumm genug spielt und da dasminimax probiert alle Möglichkeiten aus, auch die, mit dem folgenden Code bekomme ich eine gewertete Tafel aller 15er für die leere Tafel.
void printScoredBoards(int *board, int depth)
{
int player;
int scoredBoard[9] = {0,0,0,0,0,0,0,0,0,};
int i;
if(isWin(board) == 0){
if(depth%2 ==1){
player = -1;
} else {
player = 1;
}
for(i=0; i<9; i++){
if(board[i] == 0){
board[i] = player;
scoredBoard[i] = minimax(board, depth+1)+10;
printScoredBoards(board, depth+1);
board[i] = 0;
}
}
printf("Scored board:");
dumpTable(scoredBoard);
printf("\n");
}
}
Dies ist obwohl die Ecken mehr wert sein sollten und die Mitte am wenigsten wert ist. Kennt jemand zufällig einen Workaround dafür?
BEARBEITEN Ich habe einen neuen Minimax-Algorithmus eingerichtet und in einem anderen Beitrag veröffentlicht. Sie finden den Beitrag im Bereich "Verknüpft" auf der rechten Seite oder unterHie. Jetzt implementiere ich es nur noch in den Mikrocontroller-Code und erstelle eine Funktion, mit der aus allen erzielten Zügen der beste / zweitbeste Zug ausgewählt und zufällig ausgewählt werden kann, wenn es mehrere Züge mit derselben Punktzahl gibt. Dieser Beitrag kann dabei @ segeschlosse.