Tic Tac Toe и Minimax - Создание несовершенного ИИ на микроконтроллере
Я создал игру Tic-Tac-Toe на микроконтроллере, включая идеальный ИИ (идеальный смысл, который он не теряет). Я не использовал минимаксный алгоритм для этого, просто маленький конечный автомат со всеми возможными и оптимальными ходами. Моя проблема сейчас в том, что я хотел реализовать различные трудности (Easy, Medium и Hard). ИИ пока будет сложным. Поэтому я подумал о том, как сделать это наилучшим образом, и в итоге захотел использоватьminimax алгоритм, но таким образом, что он рассчитывает все оценки для всех игровых позиций, так что я иногда могу выбрать второй лучший результат вместо лучшего. Поскольку я не всегда могу выполнять все эти вычисления на самом микроконтроллере, я хотел создать небольшую программу, которую я мог бы запускать на своем компьютере, которая дает мне массивы всех возможных состояний платы (в отношении симметрии, например, чтобы минимизировать объем памяти). используется) и их соответствующие оценки. Для этого я сначала попытался реализовать сам минимаксный алгоритм, касающийсяdepth для того, чтобы правильно рассчитатьscores каждого государства. Затем он должен был вернуть мне все оптимальные ходы (на данный момент) в массиве. Тем не менее, это, кажется, не работает так хорошо. Я пытался отладить его с некоторымиprintf линий. Вот код обоихminimax функция, а также моя основная функция:
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;
}
main является:
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;
}
Кроме того, у меня есть некоторые переменные:
//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];
Как и моя выигрышная функция:
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;
}
По какой-то причине в последний раз минимакс возвращается изdepth 7 шаг за шагом кdepth 1, это переписывает мой массивg_moves со всеми 0, что приводит к следующим строкам в моем выводе (только последние 70 строк):
...
----- 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 |
|----|----|----|
Если вам понадобится какая-либо другая информация, чтобы помочь мне, я буду рад предоставить ее вам, если она у меня будет.
Заранее спасибо.
РЕДАКТИРОВАТЬ: Поэтому я переписал свойminimax Функция теперь печатает все возможные состояния платы в файле .txt с помощью консоли (cmd: ./NAME_OF_FILE> DEST_NAME.txt в соответствующей папке). Код следующий:
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;
}
Мой следующий шаг - распечатать доску с максимальнымscore каждого движения в соответствующей позиции.
Example:
10 8 10
8 7 8
10 8 10
for the empty board at the beginning.
РЕДАКТИРОВАТЬ 2: Теперь я добавил еще одну функциюprintScoredBoards который в основном должен делать то, что я описал выше в моем последнем редактировании, однако есть проблема с этим. Поскольку после 5-го хода всегда можно выиграть, если ваш оппонент играет достаточно глупо иminimax Опробует все возможности, в том числе и те, с помощью следующего кода я получаю выигрышную доску всех 15-ти для пустой доски.
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");
}
}
Это хотя углы должны стоить больше, а центр является наименее ценным. Кто-нибудь случайно знает обходной путь для этого?
РЕДАКТИРОВАТЬ: Я установил новый минимаксный алгоритм и разместил его в другом посте. Вы можете найти сообщение в разделе «Связанные» справа илиВот, Теперь все, что я делаю, - это внедряю его в код микроконтроллера и создаю функцию, которая может выбирать лучший / второй лучший ход из всех набранных ходов, а также рандомизировать его, если есть несколько ходов с одинаковым счетом. Таким образом, этот пост может бытьзакрыто.