¿Cómo se hace exactamente minimax la recursividad de trabajo?

Question

Así que yo estaba mirando hasta Mini-max para un Tic-Tac-Toe Juego, pero no podía entender cómo la recursividad trabajado?Bien, así que básicamente he aquí mis preguntas:

1. ¿Cómo minimax saber que a su vez es?Cuál es la mejor manera para indicar que el jugador cuyo turno se está generando?
2. ¿Cómo se generan los movimientos posibles?
3. ¿Cómo sabes cuando estás en una terminal de nodo, y ¿cómo se generan los nodos terminales?

Por ejemplo, en este Pseudo-código

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 α

Un node es un consejo correcto?Y es la profundidad cómo muchas capas, el código tiene que ir hacia abajo en la recursividad?También lo es la max función y donde se encuentran los nodos que se están generados a partir de?

Hasta ahora tengo este código para la creación de un consejo:

class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};

Pero, ¿cómo iba yo a saber que a su vez es?Y ¿cómo puedo generar los nodos secundarios para la junta?

Answer 1

Vamos a utilizar su tic-tac-dedo del pie como un ejemplo de la primera.

• Un algoritmo minimax funciona mejor para juegos donde los jugadores alternan turnos, pero se puede adaptar a juegos donde los jugadores pueden hacer varios movimientos por turno.Vamos a suponer que el primero, por la simplicidad.En ese caso, no necesita de la tienda 'X para mover' o 'O mover' con cada nodo, ya que sólo puede ser determinado por la paridad de la profundidad de nodo (si soy un número par de pasos, o un número impar de pasos, desde la parte superior).
• La generación de los movimientos posibles de cada posición requiere que usted sabe de quién se mueve es lo que se determina como antes), y las normas legales se mueve de una posición en particular.Para un simple juego como el tic-tac-toe, dada una posición, basta enumerar todos los estados que constan de una copia de la posición actual, además de una nueva pieza, perteneciente a la actual jugador, coloca en cada casilla vacía en turno.Para juegos como Othello, también debe comprobar cada ubicación para asegurarse de que sigue las reglas, y de actualización de la posición final de acuerdo a las consecuencias de la regla (por Otelo, cambiando los colores de un montón de piezas).En general, desde cada posición válida, se está realizando el seguimiento, enumerar todos los posibles resultados de una nueva pieza y comprobar para ver cuáles son permitidos por el conjunto de reglas.
• En general, usted NUNCA generar el árbol entero, desde el juego árbol de tamaños pueden superar fácilmente la capacidad de almacenamiento de la Tierra.Siempre establezca una profundidad máxima de la iteración.Un terminal de nodo, entonces, es simplemente un nodo en la profundidad máxima, o un nodo desde el que no hay movimientos legales que existen (por el tic-tac-dedo del pie, una junta con todos los cuadrados llenos).No generar los nodos terminales de antemano;que obtener generado de forma natural durante el juego árbol de la construcción.Tic-tac-dedo del pie es bastante sencilla que te puede generar el juego de todo árbol, pero entonces no intente utilizar su tic-tac-toe código para, por ejemplo,Otelo.

Mirando a su pseudocódigo:

• max(a, b) es cualquier función que devuelve el mayor de a o b.Este generalmente es proporcionada por una biblioteca matemática o similar.
• El depth es la profundidad máxima a la que va a buscar.
• El valor heurístico informático es algún valor numérico que describe el valor de la pensión.Para un juego como el tic-tac-dedo del pie, que es lo suficientemente simple que usted PUEDE enumerar el juego de todo árbol, puede designar 1 para un puesto en un consejo de que se gana para el jugador que está realizando el análisis, -1 para un puesto en un consejo de que se gana por el otro jugador, y 0 para cualquier concluyentes posición.En general, usted tendrá que cocinar una heurística de sí mismo, o uso de un bien aceptado.
• Generar los nodos sobre la marcha durante el análisis basado en sus nodos principales.Su nodo raíz es siempre la posición desde la que estás haciendo el análisis.

Si usted no ha trabajado con los gráficos y de los árboles, sin embargo, le sugiero que lo primero;el árbol primitivo, en particular, es esencial a este problema.

---

Como una respuesta a un comentario en este hilo pidiendo un ejemplo de la determinación de quién tiene el turno es para un nodo dado, ofrezco este pseudo-Python:

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

Cada nodo es capaz de mantener un seguimiento de su absoluta de la profundidad de la 'raíz' nodo.Cuando tratamos de determinar cómo debemos generar los puestos de la junta para el próximo movimiento, verificamos para ver de quien se mueve es basado en la paridad de nuestra profundidad (el resultado de self.depth % 2) y nuestro registro de quién mueve primero.

Answer 2

1) ¿Cómo se conoce Minimax a quién es el turno?¿Cuál es la mejor manera de indicar al jugador cuyo turno se está generando?

Tienes ese argumento de depth.Si la profundidad es incluso, entonces es un giro de un jugador, si es extraño, entonces es el turno del otro jugador.

2) ¿Cómo generas movimientos posibles?

Usando las reglas del juego.En Tic Tac Toe, un posible movimiento significa colocar la marca de uno en una celda libre.

3) ¿Cómo sabe cuándo está en un nodo terminal y cómo genera los nodos terminales?

Un nodo terminal es un nodo donde alguien ha ganado.Los generas por recursión.Cada llamada recursiva debe recibir el estado actual de la Junta.Supongo que ese es el código node y los parámetros child en su Pseudocódigo.Entonces, si en esa situación, alguien ha ganado, entonces es terminal, de lo contrario, intentas todos los movimientos legales y recurtores.

Answer 3

Puedo proporcionar un poco de idea de lo que está buscando, ya que escribí un algoritmo de Minimax para TIC-TAC-TOE.

Para responder a sus preguntas directamente:

1. Mi algoritmo Minimax no determinó eso. Aceptó un argumento que determinó qué jugador estaba usando el algoritmo.

2. Sabiendo que el jugador se mueva, bucle a través de todos los cuadrados en blanco en el tablero, y para cada uno, genere un nodo con el token del jugador actual en ese cuadrado. Recursivamente a proceder desde allí.

3. He usado una función que devolvió un valor que indicaba si el juego había terminado, y si era un sorteo o una victoria.

Mi algoritmo básico hizo esto:

• entrada: el jugador para moverse, y el estado de la junta.
• Encuentra todos los espacios en blanco que quedan en el tablero.
  • generar una nueva tabla con el movimiento del jugador en ese espacio.
  • Si el juego ha terminado, genere un nodo con el resultado del juego.
  • de lo contrario, ejecute el algoritmo, pasando en el otro jugador y la nueva tabla, y genere un nodo con el resultado del movimiento ideal del oponente.
• Determine qué nodo (movimiento) conduce al mejor peor de los casos posible.
• Salida: El mejor movimiento, e información sobre el resultado del juego.