Java tictactoe problems with minmax algorithm

i want to implement the MinMax algorithm for tictactoe. I have two methods min() and max() and a evaluation method, but it doesn't works. For example when i call

max(9);
Field[bestCol][bestRow]='O';
min(8);
Field[bestCol][bestRow]='X';     

in the main function the result is

OX-                                  
---
---

But the best Move for Player 'X' is to put the 'X' in the middle.

Here is my Code without the evaluation Method:

static char[][] Field = { { '-', '-', '-' },
                          { '-', '-', '-' },
                          { '-', '-', '-' } };

static char Player = 'O';
static char Computer = 'X';

static int Depth =9; // searchdepth
static int bestRow=0, bestCol=0; // best Move

public static int max(int depth) {
    if (depth == 0) {
        return evaluateMove();
    }

    int maxValue = Integer.MIN_VALUE;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (Field[i][j] == '-') {
                Field[i][j] = Computer;

                int value = min(depth - 1);
                Field[i][j] ='-';

                if (value > maxValue) {
                    maxValue = value;
                    if (depth == Depth) {
                        bestCol=i;
                        bestRow=j;
                    }
                }
            }
        }
    }
    return maxValue;
}

public static int min(int depth) {
    int minValue = Integer.MAX_VALUE;

    if (depth == 0) {
        return evaluateMove();
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (Field[i][j] == '-') {
                Field[i][j] = Player;
                int value = max(depth - 1);
                Field[i][j] = '-';

                if (value < minValue) {
                    minValue = value;
                    bestCol=i;
                    bestRow=j;
                }
            }
        }
    }
    return minValue;
}

Best Regards

EDIT:

Thanks for your answer. To the first point i have forgotten to change the '*' to '-' Here is my Evaluation Method:

public static int evaluateMove() {
    for(int i=0; i<3; i++) {
        int countX=0; int countY=0;
        for(int j=0; j<3; j++) {
            if(Feld[i][j]==Computer) countX++;
            if(Feld[i][j]==Player) countY++;
        }
        if(countX==3) return 10;
        if(countY==3) return -10;
    }

    for(int j=0; j<3; j++) { // Spalten
        int countX=0; int countY=0;
        for(int i=0; i<3; i++) {
            if(Feld[i][j]==Computer) countX++;
            if(Feld[i][j]==Player) countY++;
            if(countX==3) return 10;
            if(countY==3) return -10;
        }
    }
    return 0; // Unentschieden
}

---

Some things that struck me:

you are initializing the empty squares of the playing field with '-', but in the min/max-functions you assume that '*' is an empty square

in the min-function, as opposed to the max-function you set the best move at every level instead of the top level, so the deeper levels will overwrite the best result from the top level (so I think you should also check for depth==Depth)

I don't know what you do in main, but should also decrement "Depth" after each move, because this defines the top level (and thus the level where the best move should be assigned), and according to your question you decrement the "depth" argument during each call

I guess you know that you will only get the optimal result if you recurse until the end of the game (which is another argument for decrementing depth and Depth after every move)

You are not checking the diagonals in your evaluateMove function

In your second double loop in evaluateMove you check the condition for countX, countY inside the innermost loop (works, but it is irritating that it's different to first double loop => not so good for finding errors)

Edit: and finally (drum roll...):

In the first move you maximize the gain (for a Computer move ('X')) but you actually perform a Player move ('O'). For the second move vice versa. However, you have to minimize the gain in the first move (which means player wins) and maximize in the second move.

That is, what you actually do:

    public static void ComputeAndExecuteBestMove()
    {
        // since Player begins, we minimize the gain value for the first move
        if ((MaxDepth-Depth) % 2 == 0) 
        {
            max(Depth);
            Field[bestCol,bestRow] = Player;
        }
        else 
        {
            min(Depth);
            Field[bestCol,bestRow] = Computer;
        }

        // next move
        Depth--;
    }

but what you should do:

    public static void ComputeAndExecuteBestMove()
    {
        // since Player begins, we minimize the gain value for the first move
        if ((MaxDepth-Depth) % 2 == 0) 
        {
            min(Depth);
            Field[bestCol,bestRow] = Player;
        }
        else 
        {
            max(Depth);
            Field[bestCol,bestRow] = Computer;
        }

        // next move
        Depth--;
    }

链接地址: http://www.djcxy.com/p/56390.html

上一篇: Java minmax算法返回空移动，并且无法正确地撤消移动

下一篇: 用minmax算法的Java tictactoe问题