Минимакс с обрезкой альфа-бета, получая результат - PullRequest
Новая
       39

Минимакс с обрезкой альфа-бета, получая результат

3 голосов
/ 26 октября 2011

Я следовал псевдокоду в статье в Википедии, и я думаю, что он заработал. Тем не менее, он возвращает счет, и это не совсем помогает, когда я хочу знать, какой шаг я хочу сделать.

Я попробовал то, что, по моему мнению, было бы способом получить лучший ход, но я не думаю, что это работает, поскольку, когда я на самом деле пытаюсь играть против него (шахматы), ИИ делает несколько замедленных ходов с уровнем глубины. 3.

Вот моя функция: 

public static function alphaBeta(node, depth, alph, beta, team, tellTheMove:Boolean = false):* {
        var pointer:ChessMove;
        if (depth == 0) {
            return scoreOf(node);
        }
        var childrenOf:Vector.<ChessMove >  = returnPossibleMoves(node,team);
        if (childrenOf.length == 0) {
            return scoreOf(node);
        }
        if (team == 0) {
            for (var i in childrenOf) {
                var that:Number = alphaBeta(childrenOf[i],depth - 1,alph,beta,1);
                if(tellTheMove){
                }
                if (that > alph) {
                    alph = that;
                    if(tellTheMove){
                        pointer = childrenOf[i];
                    }
                }
                if (beta <= alph) {
                    break;
                }
            }
            if(tellTheMove){
                return pointer; //Returns the move that's score last exceeded alpha.
            }
            return alph;
        } else {
            for (var j in childrenOf) {
                var that2:Number = alphaBeta(childrenOf[j],depth - 1,alph,beta,0);
                if (that2 < beta) {
                    beta = that2;
                }
                if (beta <= alph) {
                    break;
                }
            }
            return beta;
        }
    }

1 Ответ

4 голосов
/ 26 октября 2011

Глубина 3 очень мала для такой проблемы, как шахматы.На этой глубине большая часть мощности зависит от вашей окончательной оценочной функции.Эту функцию оценки очень сложно сделать так, чтобы она могла эффективно прогнозировать значение платы.

Попробуйте что-то попроще, что можно эффективно решить на более низкой глубине.Крестики-нолики - очень хорошая игра для первой попытки Min-Max.Это потому, что окончательный результат хорошо известен.Если вы правильно понимаете свой алгоритм, вы не сможете его превзойти.Если вы выполняете Tic-Tac-Toe, а алгоритм проигрывает, вы знаете, что у вас есть ошибка.

Также обратите внимание, что в некоторых случаях Min-Max играет оптимально, но все равно будет выглядеть отсталым для оппонента-человека.Например, если нет шансов на победу, Min-Max начнет играть в случайном порядке и делает очень глупые ходы.Дело обстоит так, потому что Мин-Макс ожидает, что противник также будет играть идеально, что обычно не происходит с людьми.Есть несколько простых изменений, которые могут быть внесены в алгоритм, чтобы изменить это поведение и заставить min-max играть «менее запаздывающий» в таких случаях.

...