función minimax C ++

Question

He buscado en Google y Stackoverflow para esta pregunta, pero sigo sin entender cómo una función Minimax obras.

Me encontrado la entrada de Wikipedia tiene una versión pseudocódigo de la función:

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 α

Varias otras funciones minimax he encontrado con Google son básicamente la misma cosa; Estoy tratando de implementar esto en C ++, y esto es lo que tengo llegar a hasta el momento:

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?*/
}

Como se puede ver, estoy bastante confundido acerca de esta función Minimax. Por favor, por lo menos dame algunos consejos que me ayuda con esto.

Gracias! :)

Answer 1

Esa muestra de Wikipedia está haciendo negamax con alfa / beta poda .

puede ser ayudado por conseguir la denominación recta:

• La base es MiniMax, una implementación literal implicaría 2 métodos que toman vueltas (mutuamente recursivos), 1 para cada lado.

• Los programadores perezosos convertir esto en negamax, un método con un operador de - estratégicamente colocados.

• Alfa / Beta poda es hacer el seguimiento de una ventana de mejores movimientos (a través de múltiples profundidades) para detectar las ramas muertas.

Su playerTurn se utiliza para determinar quién es el turno. En negamax puede derivar esto desde la profundidad (iteraciones) es par o impar. Pero sería más fácil de usar 2 parámetros (Mycolor, otherColor) y les cambian en cada nivel.

Answer 2

función

Su miniMax () debe recordar el mejor movimiento que se encontró hasta el momento. Así que en lugar de este código:

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

Usted debe hacer algo como esto:

  /*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;
  }

Por supuesto, se necesita una variable "bestMove" y una manera de devolver el mejor movimiento encontrado a la persona que llama.

Answer 3

Añadir la variable playerTurn como argumento para miniMax y miniMax llamada que del jugador actual se desplazan en principio y de forma recursiva.

Además, las necesidades opponentSide a ser una función de playerTurn.

Answer 4

Un buen lugar para comenzar con la búsqueda de árbol de juego es el de ajedrez de programación wiki . Por su pregunta sobre el movimiento: Creo que es más común tener dos max-funciones. La diferencia entre las dos funciones max es que uno sólo devuelve la puntuación y el otro vuelve la partitura y el mejor movimiento. Una orden de llamada recursiva sería como siguiente:

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

Existen algunos artículos buenos con pseudocódigo para el algoritmo de Alfa Beta:

• TA Marsland - Computer Chess y Buscar
• J Schaeffer - los equipos de juegos (y personas) Jugar

A su pregunta en el comentario:?! y Math.max (alfa, puntuación) o Math.min (alfa, puntuación) es alfa existe un valor lógico

No alfa es una ventana de atado en un algoritmo de alfa beta. El valor alfa se actualiza con un nuevo valor. Debido a alfa y beta se intercambian con la llamada recursiva de la negamax-función de la variable alfa se refiere a la variable beta en la siguiente llamada recursiva.

Una nota a la variable playerTurn: El algoritmo minimax o alfa-beta no necesita esta información. Así que le daría la información - quién es el siguiente -, en la Junta-Estructura. Las funciones y findPossibleMoves boardEval obtener toda la información que necesitan de la Junta-Estructura.

Una nota a la condición de descanso recursiva: Si entiendo el código correcto, entonces es suficiente con el que tiene iterations == o. Creo que esto significa que el algoritmo ha alcanzado la profundidad deseada. Pero lo que si no hay movimientos posibles que quedan se acaben el algoritmo llega a esta profundidad. Tal vez debería escribir lo siguiente:

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

Answer 5

En el pseudocódigo, la variable de nodo tiene que contener toda la información sobre la posición actual del tablero (o lo que sea). Esta información incluiría al que le toca mover.