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

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

Когда алгоритм обнаруживает, что позиция потеряна, он возвращает -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 ходов), лучшая переменная выше равна пустому недопустимому ходу, переданному в качестве аргумента... почему??

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


person Fernando    schedule 01.03.2012    source источник
comment
Пожалуйста, прочтите часто задаваемые вопросы и как спросить и задать более конкретный вопрос. Кроме того, ваш вопрос неполный; вы не показали определение класса AI, что очень важно для проблемы   -  person Jim Garrison    schedule 01.03.2012
comment
Проблема концептуальная, а не проблема с кодом. Кода, который я предоставляю, достаточно, чтобы решить проблему, которую я думаю. Но все равно спасибо, я прочитаю это, чтобы узнать больше.   -  person Fernando    schedule 01.03.2012


Ответы (3)


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

person Kyle Jones    schedule 01.03.2012
comment
Вы только что решили проблему, спасибо! Теперь я возвращаю INFINITY/10 или -INFINITY/10, когда достигается потерянная позиция. Если я правильно понимаю, я должен вернуть значение между -INF и +INF, верно? - person Fernando; 01.03.2012
comment
Правильно, если только выигранные или проигранные позиции могут возвращать эти значения. - person Kyle Jones; 01.03.2012
comment
Вы также должны попытаться заставить функцию возвращать значение, основанное на том, сколько вы выиграли или проиграли, так что, если вы выиграете на 64 части, она должна вернуть большее значение, чем если вы выиграете на 50 частей. Таким образом, ваш алгоритм будет искать не только выигрыш, но и лучший выигрыш. Значения всех условий выигрыша должны быть больше, чем любое значение невыигрышного условия. - person user829876; 02.03.2012

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

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

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

person user829876    schedule 01.03.2012

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

person DNA    schedule 01.03.2012