Минимаксный алгоритм не возвращает лучший ход - PullRequest
Новая
       14

Минимаксный алгоритм не возвращает лучший ход

2 голосов
/ 01 марта 2012

Я пишу движок Отелло, использующий минимакс с альфа-бета-отсечкой.Работает нормально, но я обнаружил следующую проблему:

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

Вот код: 

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{             
    OthelloMove garbage = new OthelloMove();             
    int currentPlayer = board.getCurrentPlayer();

    if (board.checkEnd())
    {                        
        int bd = board.countDiscs(OthelloBoard.BLACK);
        int wd = board.countDiscs(OthelloBoard.WHITE);

        if ((bd > wd) && currentPlayer == OthelloBoard.BLACK)                
            return INFINITY;
        else if ((bd < wd) && currentPlayer == OthelloBoard.BLACK)                           
            return -INFINITY;            
        else if ((bd > wd) && currentPlayer == OthelloBoard.WHITE)                            
            return -INFINITY;            
        else if ((bd < wd) && currentPlayer == OthelloBoard.WHITE)                            
            return INFINITY;            
        else                             
            return 0.0f;            
    }
    //search until the end? (true during end game phase)
    if (!solveTillEnd )
    {
        if (depth == maxDepth)
            return OthelloHeuristics.eval(currentPlayer, board);
    }

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

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

        if(score > alpha)
        {  
            //Set Best move here
            alpha = score;                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());                              
        }

        if (alpha >= beta)
            break;                

    }                
    return alpha;
}

Я называю это используя: 

AI ai = new AI(board, maxDepth, solveTillEnd);

//create empty (invalid) move to hold best move
OthelloMove bestMove = new OthelloMove();
ai.bestFound = bestMove;
ai.minimax(board, bestMove, -INFINITY, INFINITY, 0);

//dipatch a Thread
 new Thread(ai).start();
//wait for thread to finish

OthelloMove best = ai.bestFound();

Когда ищется потерянная позиция (например, она была потеряна на 10 ходов позже), лучшая переменная выше равна пустому неверному ходу, переданному в качестве аргумента ...почему ??

Спасибо за любую помощь!

Ответы [ 3 ]

3 голосов
/ 01 марта 2012

Ваша проблема в том, что вы используете -INFINITY и + INFINITY в качестве выигрыша / проигрыша.У вас должны быть баллы за выигрыш / проигрыш, которые выше / ниже, чем у любого другого позиционного балла оценки, но не равны вашим значениям бесконечности.Это гарантирует, что ход будет выбран даже в безнадежно потерянных позициях.

2 голосов
/ 01 марта 2012

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

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

Мне кажется (не испытывая его), чтоесли вы обновите свою функцию eval таким образом и вообще пропустите проверку if (board.checkEnd ()), ваш алгоритм должен работать нормально (если с ним нет других проблем).Удачи!

0 голосов
/ 01 марта 2012

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

...