Отелло Альфа-Бета Обрезка плохо играет на питоне - PullRequest
Новая
       55

Отелло Альфа-Бета Обрезка плохо играет на питоне

3 голосов
/ 12 января 2012

Я сейчас пытаюсь сделать хороший ИИ для Отелло, и сделал это с помощью алгоритма Minimax.Однако, когда я попытался сделать более глубокий поиск с использованием альфа-бета-обрезки, казалось, что алгоритм работает ужасно.Я проверил это с другими источниками, такими как Wiki и Berkely.edu, и я думаю, что реализовал это правильно, но я все еще не могу найти проблему. 

def alphabeta(board, player, a, b, lev):
        h = heur(board, player)
        if lev == 0:
                return h, None
        poss = get_legal_moves(board, player)
        if len(poss) == 0:
                return h, None
        move = 0
        for x in poss:
                cpboard = board[:]
                cpboard[x] = player
                bracket(cpboard, player, x)
                a1, q = alphabeta(cpboard, opponent_color(player), a, b, lev-1)
                if player is me:
                        if a1 > a:
                                a, move = a1, x
                else:
                        if a1 < b:
                                b, move = a1, x
                if b <= a:
                        break
        if player is me:
                return a, move
        else:
                return b, move

Ответы [ 2 ]

2 голосов
/ 29 февраля 2012

Возможно, ваш альфа-бета-код неверен. Помните о том, что происходит, когда игрок «проходит ход» (т. Е. Не имеет доступных ходов), из-за этого в моем коде была хитрая ошибка.

Вы вызывали рекурсию с переключенными значениями альфа и бета? Мой работает так (код Java): 

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{
    float bestResult = -Float.MAX_VALUE;
    OthelloMove garbage = new OthelloMove();

    int state = board.getState();
    int currentPlayer = board.getCurrentPlayer();

    if (state == OthelloBoard.STATE_DRAW)
        return 0.0f;
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.BLACK))                    
        return INFINITY;        
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return INFINITY;
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return -INFINITY;
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.BLACK))
        return -INFINITY;

    if (depth == maxDepth)
        return OthelloHeuristics.eval(currentPlayer, board);

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer);

    for (OthelloMove mv : moves)
    {            
        board.makeMove(mv);
        alpha = - minimax(board, garbage, -beta, -alpha, depth + 1);
        board.undoMove(mv);

        if (beta <= alpha)
            return alpha;
        if (alpha > bestResult)
        {                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());
            bestResult = alpha;
        }
    }

     return bestResult;
}

Звонок, как: 

 OthelloMove bestFound = new OthelloMove();
 int maxDepth = 8;
 minimax(board, bestFound, -Float.MAX_VALUE, Float.MAX_VALUE, maxDepth);
//Wait for Thread to finish
 board.makeMove(bestFound);

Редактировать: Если у игрока нет доступных ходов, getAllMoves () возвращает «фиктивный ход», который не меняет доску, просто пройдите ход.

Надеюсь, это поможет!

1 голос
/ 16 января 2012

Ваша реализация в алфавитном порядке выглядит для меня неплохо. Поскольку minimax и alphabeta дают одинаковые результаты при правильной реализации, вы должны иметь возможность использовать свой старый минимаксный код для проверки алфавита, по крайней мере, для скромной глубины поиска. Если их результаты различаются при поиске в одном и том же дереве игр, то вы знаете, что сделали что-то не так.

Но, скорее всего, плохая игра является результатом чего-то в вашей функции оценки "heur".

...