Tac脚趾和Minimax -在微控制器上创建一个不完美的人工智能

Question

我在一个微控制器上创建了一个Tic-Tac-Toe游戏，包括一个完美的AI (完美的意思是它不会输)。对此，我没有使用极小极大算法，只是一个带有所有可能和最优动作的小状态机。我现在的问题是，我想实现不同的困难(容易，中等和困难)。到目前为止，人工智能将是最难的。所以我想过如何用最好的方法来做这件事，最后我想要使用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;
}

由于某些原因，minimax上次从depth 7逐步返回到depth 1时，它用所有的0覆盖我的数组g_moves，从而在我的打印输出中产生了以下行(只有最后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函数，因此它现在使用控制台(cmd: /NAME_OF_ file > DEST_NAME.txt )在.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的函数，它基本上应该做我在上一次编辑中描述的事情，但是它有一个问题。因为如果你的对手玩得够傻的话，在第五步之后总是有可能赢的，而且既然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");
    }
}

这是，虽然角应该更值钱，而中心是最不值钱的。有没有人碰巧知道解决这个问题的办法？

编辑：，我设置了一个新的极大极小算法，并将其发布在另一篇文章中。您可以在右侧的“链接”部分或here中找到该帖子。现在，我所做的就是在微控制器代码中实现它，并创建一个函数，它可以从所有得分的移动中选择最佳/次最佳移动，如果有多个相同分数的移动，则将其随机化。因此，这个员额可以关闭。

Answer 1

我认为，试图得到第二最好的移动充分深入分析，这是过头了。不要通过限制你的最小值的深度来探索整棵树(2移动允许赢，但AI仍然很强)，或者只是对一个非常不完美的AI使用随机移动。