Minmax Algorithm for tic

I am writing a minmax algorithm as the artificial intelligence for a tic-tac-toe game, I followed the similar instruction here, but the algorithm seems not intelligent enough, even though I tried to search deeper in the tree, can anyone help to analyze where goes wrong? thank you very much in advance!

- (int) miniMax:(int)depth : (UIImage*) player {
    NSMutableArray *steps = [self generateMoves];

    if (depth == 0 || [steps count] == 0) {
        return [self evaluate];
    }

    int bestScore = player == myImg ? -1000000 : 1000000;
    int currentScore = 0;
    for (UIImageView *step in steps) {
        step.image = player;
        if (player == myImg) {
            UIImage *opp = player == xImg ? oImg : xImg;
            currentScore = [self miniMax:depth - 1 :opp];
            if (currentScore > bestScore) {
                bestScore = currentScore;
                nextStep = step;
            }
        } else {
            UIImage *opp = player == xImg ? oImg : xImg;
            currentScore = [self miniMax:depth - 1 :opp];
            if (currentScore < bestScore) {
                bestScore = currentScore;
                nextStep = step;
            }
        }
        step.image = NULL;
    }

    return bestScore;
}

- (int) evaluate {
    int score = 0;
    score += [self evaluateLine:img0 :img1 :img2];
    score += [self evaluateLine:img3 :img4 :img5];
    score += [self evaluateLine:img6 :img7 :img8];

    score += [self evaluateLine:img0 :img3 :img6];
    score += [self evaluateLine:img1 :img4 :img7];
    score += [self evaluateLine:img2 :img5 :img8];

    score += [self evaluateLine:img2 :img4 :img6];
    score += [self evaluateLine:img0 :img4 :img8];
    return score;
}

- (int) evaluateLine:(UIImageView*)img1 :(UIImageView*)img2 :(UIImageView*)img3 {
    int score = 0;
    // first cell
    if ([img1 image] == myImg) {
        score = 1;
    } else if ([img1 image] == oppImg){
        score = -1;
    }

    // second cell
    if ([img2 image] == myImg) {
        if (score == 1) {
            score = 10;
        } else if (score == -1) {
            return 0;
        } else {
            score = -1;
        }
    } else if ([img2 image] == oppImg){
        if (score == -1) {
            score = -10;
        } else if (score == 1) {
            return 0;
        } else {
            score = -1;
        }
    }

    // third cell
    if ([img3 image] == myImg) {
        if (score > 0) {
            score *= 10;
        } else if (score < 0) {
            return 0;
        } else {
            score = -1;
        }
    } else if ([img3 image] == oppImg){
        if (score < 0) {
            score *= 10;
        } else if (score > 1) {
            return 0;
        } else {
            score = -1;
        }
    }

    return score;
}

What I use here is: if there exits the same image as the human player holds, the score plus 1. If there are two or three player's image in a line or row or diagonal, the total score is 10 and 100 separately. If there exist both 'X' and 'O' in a same row, column or diagonal, the score is 0. Computer holds the negative score for these mentioned above.

---

Minimax assumes that the evaluation function is from the perspective of the first player. What you want is a function that always have a higher value if the first player is better.

It seems that your heuristic function adapts its value based on the current player (I am not an objective-C programmer). Change that function so that it does not know what myImg or oppImg is -- use xImg and oImg directly. Might just work.

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

上一篇: 带有Alpha的MinMax

下一篇: 用于抽象的Minmax算法