Алгоритм Minmax для игры в крестики-нолики в Objective-C

Я пишу алгоритм minmax в качестве искусственного интеллекта для игры в крестики-нолики, я следовал аналогичной инструкции здесь, но алгоритм кажется недостаточно умным, хотя я пытался искать глубже в дереве, может ли кто-нибудь помочь проанализировать, где идет не так? заранее большое спасибо!

- (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;
}

Я использую здесь следующее: если выходит то же изображение, что и игрок-человек, оценка плюс 1. Если есть два или три изображения игрока в строке, ряду или диагонали, общая оценка составляет 10 и 100 по отдельности. Если в одной и той же строке, столбце или диагонали существуют как «X», так и «O», оценка равна 0. Компьютер удерживает отрицательную оценку для упомянутых выше.


person photosynthesis    schedule 12.02.2014    source источник
comment
Что вы имеете в виду под тем, что не так? В чем проблема?   -  person insys    schedule 12.02.2014
comment
@user2311023 user2311023 проблема в том, что он все еще не такой умный, например. если я поставлю два крестика в строке, компьютер не будет пытаться ее заблокировать. Поэтому я думаю, что что-то не так с моей реализацией алгоритма.   -  person photosynthesis    schedule 12.02.2014
comment
Я не думаю, что уместно просить людей просмотреть ваш код, не указав при этом на конкретную проблему.   -  person insys    schedule 13.02.2014


Ответы (1)


Минимакс предполагает, что функция оценки выполняется с точки зрения первого игрока. Что вам нужно, так это функция, которая всегда имеет более высокое значение, если первый игрок лучше.

Похоже, ваша эвристическая функция адаптирует свое значение в зависимости от текущего игрока (я не программист на Objective-C). Измените эту функцию, чтобы она не знала, что такое myImg или oppImg — используйте напрямую xImg и oImg. Может просто работать.

person Willem    schedule 16.02.2014