C ++ MiniMax Функция

StackOverflow https://stackoverflow.com/questions/3630669

  •  26-09-2019
  •  | 
  •  

Вопрос

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

Я нашел запись Wikipedia имеет псевдокодную версию функции:

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 α

Несколько других функций MiniMax, которые я нашел с 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?*/
}

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

Спасибо! :)

Это было полезно?

Решение

Этот образец из Википедии делает негамакс с Alpha / Beta Creuning.

Вам может помочь, получая наименование прямой:

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

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

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

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

Другие советы

Ваша функция 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» и способ вернуть лучшее движение, найденное звонящему.

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

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

Хорошее место для начала игры в поисках дерева Шахматный программирование Wiki. Отказ За ваш вопрос о ходу: я думаю, что наиболее распространено два максимальных функция. Разница между двумя максимальными функциями заключается в том, что один возвращает только оценку, а другой возвращает счет и лучший ход. Рекурсивный заказ звонка будет похоже на следующее:

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

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

На ваш вопрос в комментарии: и math.max (альфа, счет) или math.min (альфа, счет) - альфа логический там?!

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

Одна заметка к переменной Playerturn: MiniMax или Alpha-Beta Algorithm не нуждается в этой информации. Поэтому я бы дал информацию - кто следующий - в состав доски. Функции FindPossiblemoves и Boardeval получают всю необходимую информацию от структуры доски.

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top