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");
    }
}

Это хотя углы должны стоить больше, а центр является наименее ценным. Кто-нибудь случайно знает обходной путь для этого?

РЕДАКТИРОВАТЬ: Я установил новый минимаксный алгоритм и разместил его в другом посте. Вы можете найти сообщение в разделе «Связанные» справа илиВот, Теперь все, что я делаю, - это внедряю его в код микроконтроллера и создаю функцию, которая может выбирать лучший / второй лучший ход из всех набранных ходов, а также рандомизировать его, если есть несколько ходов с одинаковым счетом. Таким образом, этот пост может бытьзакрыто.

 Lithimlin21 июл. 2016 г., 09:56
~ Редактировал мой оригинальный пост снова ~
 Lithimlin20 июл. 2016 г., 15:43
~ Отредактировал мой оригинальный пост ~
 lorro20 июл. 2016 г., 13:38
Для такого очень маленького пространства состояний, как крестики-нолики, вы можете просто держать идеальный ИИ и «бросать кубики» каждый раз, чтобы решить, выберете ли вы оптимальный шаг или другой, случайный шаг. Кроме того, средний может иметь проверку, чтобы предотвратить выигрышные ходы других игроков, когда это возможно.
 Lithimlin20 июл. 2016 г., 13:43
Это на самом деле не такая уж плохая идея, и я думаю, я просто сделаю это, если эта штука окажется тупиковой, но я все еще хотел бы знать, где я совершаю ошибку. Это, наверное, что-то очевидное, что я просто постоянно скучаю
 Codor20 июл. 2016 г., 14:02
Я также предпочел бы второе, я бы просто предположил, что вычислительная мощность достаточна для выполнения minmax или, по крайней мере, minmax с альфа-бета-отсечкой. Что это за микроконтроллер? Я хотел бы получить приблизительное представление о его вычислительной мощности.
 Lithimlin20 июл. 2016 г., 14:05
На нем есть чип MB91F464AB

Ответы на вопрос(1)

что попытка получить второй лучший ход с глубоким анализом - это перебор. Не исследуйте все дерево, ограничивая глубину вашего минимума (2 продвижения вперед позволяют выиграть, но ИИ все еще силен), или просто используйте случайный ход для действительно несовершенного ИИ.

 Lithimlin20 июл. 2016 г., 14:01
Итак, какие критерии я должен использовать, чтобы оценить каждый ход?
 Slava20 июл. 2016 г., 16:16
Этот ответ - чат с OP, а не реальный, поэтому он не имеет значения для других людей.
 Lithimlin20 июл. 2016 г., 15:43
~ Отредактировал мой оригинальный пост ~
 Lithimlin21 июл. 2016 г., 09:56
~ Редактировал мой оригинальный пост снова ~
 Lithimlin20 июл. 2016 г., 13:54
Что вы подразумеваете под точным ограничением глубины?
 Jarod4220 июл. 2016 г., 15:04
@Lithimlin: Вы могли бы просто сделатьLose < (notFinished / Draw) < Win.
 Pierre.Sassoulas20 июл. 2016 г., 13:59
Вы не исследуете все дерево игры, а только 2 хода вперед. (int глубина = getDepth (доска); стать Int глубина = 2;)
 Pierre.Sassoulas21 июл. 2016 г., 10:00
Если у вас есть несколько одинаковых очков, вы можете сделать первый или последний ход в зависимости от того, как ваш minmaxing (> или> =), ничего не делая, или выбрать случайным образом лучший результат, если вы не хотите, чтобы компьютер всегда играл так же.
 Pierre.Sassoulas21 июл. 2016 г., 10:28
Я думаю, что вы хотите сделать функцию оценки слишком совершенной. Предполагается, что он будет играть в случайном порядке первый ход, потому что в противном случае он сыграет лучший ход и будет непобедим. Позже ваш ИИ сыграет лучший ход, потому что для этого достаточно глубины 2, но он, возможно, уже проиграл.

Ваш ответ на вопрос