Минимаксная функция C ++

Question

Я искал этот вопрос в Google и Stackoverflow, но до сих пор не понимаю, как работает минимаксная функция.

Я обнаружил, что запись в Википедии имеет псевдокодовую версию функции:

function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    α = -∞
    for child in node:                       # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

Несколько других минимаксных функций, которые я нашел в Google, по сути, одно и то же; Я пытаюсь реализовать это в C ++, и это то, что я до сих пор придумал:

double miniMax(Board eval, int iterations)
{
    //I evaluate the board from both players' point of view and subtract the difference
    if(iterations == 0)
        return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is;
    I mean, how do you generate a list of possible moves if you don't even know
    whose turn it's supposed to be? But the problem is, I don't see where I can
    get playerTurn from, as there are only 2 parameters in all the examples of
    minimax I've seen*/
    vector<int> moves = eval.findPossibleMoves(playerTurn);

    //I'm assuming -∞ in the wikipedia article means a very low number?
    int result = -999999999;

    //Now I run this loop to evaluate each possible move
    /*Also, the Lua example in the wiki article has
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      Is alpha a boolean there?!*/
    for(int i = 0; i * 2 < moves.size(); i++)
    {
        //I make a copy of the board...
        Board temp = eval;

        /*and make the next possible move... once again playerTurn crops up, and I
        don't know where I can get that variable from*/
        temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);

        /*So do I create a function max that returns the bigger of two doubles?*/
        result = max(result, -miniMax(temp, iterations - 1));
    }

    return result;
    /*So now I've returned the maximum score from all possible moves within a certain
    # of moves; so how do I know which move to make? I have the score; how do I know
    which sequence of moves that score belongs to?*/
}

Как вы можете видеть, я немного запутался в этой минимаксной функции. Пожалуйста, по крайней мере, дайте мне несколько советов, чтобы помочь мне с этим.

Спасибо! :)

Answer 1

Этот образец из Википедии выполняет NegaMax с альфа / бета-обрезкой .

. Вам может помочь получение прямого имени:

• Основой является MiniMax, буквальная реализация будет включать 2 метода, которые по очереди (взаимно рекурсивные), по 1 для каждой стороны.

• Ленивые программисты превращают это в NegaMax, один метод со стратегически размещенным оператором -.

• Альфа / бета-обрезка отслеживает окно лучших ходов (на нескольких глубинах) для обнаружения мертвых ветвей.

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

Answer 2

Хорошим местом для начала поиска по дереву игр является wiki для шахматного программирования.На ваш вопрос о переезде: я думаю, что наиболее распространено иметь две max-функции.Разница между двумя функциями max заключается в том, что одна возвращает только оценку, а другая возвращает оценку и лучший ход.Порядок рекурсивного вызова будет выглядеть следующим образом:

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)

Есть несколько хороших статей с псевдокодом для алгоритма альфа-бета:

• TA Marsland - Компьютерные шахматы и поиск
• J Schaeffer - Игры, в которые играют компьютеры (и люди)

К вашему вопросу в комментарии: и math.max (альфа, счет) или math.min (альфа, счет) Является ли альфа логическим значением здесь!!

Никакая альфа не является границей окна в алгоритме альфа-бета.Альфа-значение обновляется новым значением.Поскольку альфа и бета поменялись местами с помощью рекурсивного вызова функции negamax, переменная альфа ссылается на переменную бета в следующем рекурсивном вызове.

Одно примечание к переменной playerTurn: алгоритм минимакса или альфа-бета немне не нужна эта информацияТак что я бы дал информацию - кто следующий - в структуру Правления.Функции findPossibleMoves и boardEval получают всю необходимую им информацию от Board-Structure.

Одно примечание к условию рекурсивного прерывания: Если я правильно понимаю ваш код, то у вас есть только тот, который имеет iterations == o.Я думаю, что это означает, что алгоритм достиг желаемой глубины.Но что, если не осталось никаких возможных ходов, пока алгоритм не достигнет этой глубины.Может быть, вы должны написать следующее:

vector<int> moves = findPossibleMoves(...);
if (!moves.size())
    return boardEval(...);

Answer 3

Добавьте переменную playerTurn в качестве аргумента к miniMax и вызовите miniMax, что текущий и рекурсивный ход текущего игрока.

Кроме того, opponentSide должна быть функцией playerTurn.

Answer 4

Ваша функция miniMax () должна помнить лучший ход, который она когда-либо нашла. Так что вместо этого кода:

  /*So do I create a function max that returns the bigger of two doubles?*/
  result = max(result, -miniMax(temp, iterations - 1));

Вы должны сделать что-то вроде этого:

  /*So do I create a function max that returns the bigger of two doubles?*/
  double score = -miniMax(temp, iterations - 1);
  if (score > result)
  {
     result = score;
     bestMove = i;
  }

Конечно, вам нужна переменная "bestMove" и способ вернуть лучший ход, найденный вызывающей стороне.

Answer 5

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