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

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

Когда алгоритм обнаруживает, что позиция потеряна, он возвращает -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 ответа

Решение

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

Источник

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

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

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

Источник

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

Источник
Другие вопросы по тегам