Помогите с моей реализацией MinMax - PullRequest
Новая
       14

Помогите с моей реализацией MinMax

0 голосов
/ 15 марта 2011

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

Небольшая помощь будет оценен:)

Вот соответствующие классы ... (удаленная реализация для ясности) 

class Board { //Stores board state, Immutable

    Board playMove(Move m); //generates new Board after playing "Move m"

    List<Move> nextMoves(Move m); // generates all possible moves, previous move is required to decide the validity of the next moves

    boolean isTerminal(); //board at terminal state?
}


class Move { //stores positions played and score gained from that move

}

А вот моя реализация Min-Max ... Может кто-нибудь указать, что я делаю неправильно? Спасибо. 

private Move bestMove = null; // field variable

private int maxMove(Board board, Move prevMove, int myScore, int oppnScore) {
    out("maxMove " + board );
    if(board.isTerminal()) {
        return myScore - oppnScore;
    }
    int mx = Integer.MIN_VALUE;
    for(Move nxtMove: board.nextMoves(prevMove)) {
        int k = minMove(board.playMove(nxtMove),
                        nxtMove,
                        myScore + nxtMove.score,
                        oppnScore);
        if(k > mx) {
            mx = k;
            bestMove = nxtMove;
        }
    }
    return mx;
}

private int minMove(Board board, Move prevMove, int myScore, int oppnScore) {
    if(board.isTerminal()) {
        return myScore - oppnScore;
    }
    out("minMove " + board );
    int mn = Integer.MAX_VALUE;
    for(Move nxtMove: board.nextMoves(prevMove)) {
        int k = maxMove(board.playMove(nxtMove),
                        nxtMove,
                        myScore,
                        oppnScore + nxtMove.score);
        if(k < mn) {
            mn = k;
            bestMove = nxtMove;
        }
    }
    return mn;
}

РЕДАКТИРОВАТЬ: краткое описание игры следующее: перед вами определенное количество монет разных номиналов. Вы и другой игрок по очереди убираете одну монету со стороны eithor (слева или справа). Номинал монеты обозначает очки, которые вы набрали за этот ход. Некоторые монеты имеют особое значение, например, «Выбор X» означает, что вы пропустите ход, или «Y» означает, что вы получите еще один ход. Ваша цель - набрать больше очков, чем ваш оппонент.

Ответы [ 2 ]

0 голосов
/ 15 марта 2011

Не думаю, что я четко понимаю правила игры, но похоже, что ваше состояние терминала не совсем правильное.

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

Я думаю, что вы хотите, чтобы выиграл игрок с наибольшим количеством очков. Таким образом, вы можете просто проверить, находится ли myScore> oppScore и вернуть 1,0 и -1 соответственно. Это означает, что первый игрок хочет максимизировать доход (то есть он пытается сделать его 1 - он выигрывает), в то время как противник пытается минимизировать доход (то есть он выигрывает, если он равен -1). в случае неудачи они скорее пойдут на 0 (ничья).

Кроме того, зачем вам нужно prevMove для генерации следующего хода? Разве board не имеет всей информации о текущем состоянии игры (то есть оставшихся монетах)?

0 голосов
/ 15 марта 2011

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

...