1

私は、両方のプレーヤーが人間であり、コンピューターがミニマックスアルゴリズムを使用して最適な動きを提案するたびに、三目並べゲームにミニマックスアルゴリズムを実装しようとしています。しかし、それは毎回正しい提案をしているわけではありません。例：次のシナリオに対して正しい提案はありません：プレーヤーX：1プレーヤーO：2プレーヤーX：5。これが私のコードです。

#include <stdio.h>
#include <algorithm>  
#include <string>
using namespace std;

#define inf 1<<20
int posmax, posmin;
char board[15];

void print_board()
{
    int i;
    for (i = 1; i <= 9; i++)
    {   
        printf("%c ",board[i]);
        if (i % 3 == 0)
            printf("\n");
    }
    printf("\n");
}

int check_win(char board[])
{
    if ((board[1] == 'X' && board[2] == 'X' && board[3] == 'X') ||
        (board[4] == 'X' && board[5] == 'X' && board[6] == 'X') ||
        (board[7] == 'X' && board[8] == 'X' && board[9] == 'X') ||
        (board[1] == 'X' && board[4] == 'X' && board[7] == 'X') ||
        (board[2] == 'X' && board[5] == 'X' && board[8] == 'X') ||
        (board[3] == 'X' && board[6] == 'X' && board[9] == 'X') ||
        (board[1] == 'X' && board[5] == 'X' && board[9] == 'X') ||
        (board[3] == 'X' && board[5] == 'X' && board[7] == 'X'))
    {
        return 1;
    }
    else if((board[1] == 'O' && board[2] == 'O' && board[3] == 'O') ||
            (board[4] == 'O' && board[5] == 'O' && board[6] == 'O') ||
            (board[7] == 'O' && board[8] == 'O' && board[9] == 'O') ||
            (board[1] == 'O' && board[4] == 'O' && board[7] == 'O') ||
            (board[2] == 'O' && board[5] == 'O' && board[8] == 'O') ||
            (board[3] == 'O' && board[6] == 'O' && board[9] == 'O') ||
            (board[1] == 'O' && board[5] == 'O' && board[9] == 'O') ||
            (board[3] == 'O' && board[5] == 'O' && board[7] == 'O'))
    {
        return -1;
    }
    else return 0;
}

int check_draw(char board[])
{
    if ((check_win(board) == 0) && (board[1] != '_') && (board[2] != '_') &&
        (board[3] != '_') && (board[4] != '_') && (board[5] != '_') &&
        (board[6] != '_') && (board[7] != '_') && (board[8] != '_') &&
        (board[9] != '_'))
    {
        return 1;
    }
    else return 0;
}

int minimax(int player, char board[], int n)
{
    int i, res, j;

    int max = -inf;
    int min = inf;

    int chk = check_win(board);
    if (chk == 1)
        return 1;
    else if (chk == (-1))
        return -1;
    else if (chk = check_draw(board))
        return 0;

    for (i = 1; i <= 9; i++)
    {
        if(board[i] == '_')
        {
            if(player == 2)  
            {
                board[i] = 'O';
                res = minimax(1, board, n + 1);

                board[i] = '_';
                if(res < min)
                {
                    min = res;
                    if (n == 0)
                        posmin = i;
                }
            }
            else if (player == 1)
            {
                board[i] = 'X';
                res = minimax(2, board, n + 1);
                board[i] = '_';
                if (res > max)
                {
                    max = res;
                    if (n == 0)
                        posmax = i;
                }
            }
        }
    }

    if (player == 1)
        return max;
    else return min;    
}


// 1 is X, 2 is O
int main()
{
    int i, j, input, opt;

    for(i = 1; i <= 9; i++)
        board[i] = '_';

    printf("Board:\n");
    print_board();

    for(i = 1; i <= 9; i++)
    {
        if (i % 2 == 0)
            printf("Player O give input:\n");
        else 
            printf("Player X give input:\n");

        scanf("%d", &input);
        if (i % 2 != 0)
            board[input] = 'X';
        else
            board[input] = 'O';

        printf("Board:\n");
        print_board();

        int chk = check_win(board);
        if (chk == 1)
        {
            printf("Player X wins!\n");
            break;
        }
        else if (chk == -1)
        {
            printf("Player O wins!\n");
            break;
        }
        else if ((chk == 0) && (i != 9))
        {
            posmax = -1;
            posmin = -1;
            if(i % 2 == 0)
            {
                opt = minimax(1, board, 0);
                printf("Optimal move for player X is %d\n", posmax);
            }
            else 
            {
            opt = minimax(2, board, 0);
            printf("Optimal move for player O is %d\n", posmin);
            }
        }
        else 
            printf("The game is tied!\n");
    }
    return 0;
}
4

4 に答える 4

2

私の意見では、あなたのプログラムは間違った提案をしません。Minimax は、両方のプレーヤーが最適なプレイをしている場合に、ムーブのスコアを計算します。あなたの場合のスコアは +1、-1、0 のいずれかです。したがって、たとえばゲームが必然的に負けた場合、どの深さで負けたかに違いはありません。次のゲーム状態が与えられた場合

X O _
X _ _
_ _ _

プレーヤー X の最適なプレイでは、プレーヤー O がどこに移動しても問題ありません (どちらの場合も負けます)。

  • O が 7 をプレイした後、X が 5 をプレイし、O が 6 をプレイし、X が 8 をプレイした後 --> X が勝つ
  • O が 3 をプレイした後、X が 7 をプレイ --> X が勝つ

プレイヤー X が勝ちます。Move 7 は、Move 3 および他のすべてのプレイ可能な Move と同じスコアを与えます。この例で、アルゴリズムに手の提案 7 を与えるようにしたい場合は、評価関数にゲームの深さを含める必要があります。これを行うには、関数の戻り値を次のように変更します。

int chk = check_win(board);
if (chk == 1)
    return (10 - n);
else if (chk == (-1))
    return -(10 - n);
else if (chk = check_draw(board))
    return 0;
于 2012-07-30T21:49:37.990 に答える
0

これは（非効率的にコーディングされていますが）正しいと思います。そうでない場合は、プログラムが間違っていると思われる場所に移動シーケンスを指定してください。

それはあなたが求めているものかもしれない最短の移動シーケンスを与えていません。次に、それをリファクタリングして、最短の移動シーケンス（勝った場合）または最長の移動シーケンス（負けた場合）を与える移動を返す必要があります。

于 2012-07-30T21:09:47.793 に答える
0

私が main() を間違って読んでいない限り、引き分けを宣言する前に 8 つのマスしか埋めていません。あなたが探しているバグではないかもしれませんが、それは始まりです。

于 2012-07-30T17:05:27.963 に答える
0

printf("Optimal move for player X is %d %d\n", posmax); と 置き換えます printf("Optimal move for player X is %d\n", posmax);

と

printf("Optimal move for player O is %d %d\n", posmin); と printf("Optimal move for player O is %d\n", posmin);

他のすべては正しいように見えますが、常に最速の勝利を出力するとは限りません (勝利が存在する場合)。

于 2012-07-30T21:22:50.227 に答える