Minimax explicado por un idiota

Question

He perdido mi día entero tratando de utilizar el algoritmo minimax para hacer una tictactoe inmejorable AI. Me he perdido algo en el camino (cerebro frito).

No estoy en busca de código de aquí, sólo una mejor explicación de que hice mal.

Aquí está mi código actual (el método Minimax siempre devuelve 0 por alguna razón):

from copy import deepcopy


class Square(object):
    def __init__(self, player=None):
        self.player = player

    @property
    def empty(self):
        return self.player is None


class Board(object):
    winning_combos = (
        [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6],
    )

    def __init__(self, squares={}):
        self.squares = squares
        for i in range(9):
            if self.squares.get(i) is None:
                self.squares[i] = Square()

    @property
    def available_moves(self):
        return [k for k, v in self.squares.iteritems() if v.empty]

    @property
    def complete(self):
        for combo in self.winning_combos:
            combo_available = True
            for pos in combo:
                if not pos in self.available_moves:
                    combo_available = False
            if combo_available:
                return self.winner is not None
        return True

    @property
    def player_won(self):
        return self.winner == 'X'

    @property
    def computer_won(self):
        return self.winner == 'O'

    @property
    def tied(self):
        return self.complete == True and self.winner is None

    @property
    def winner(self):
        for player in ('X', 'O'):
            positions = self.get_squares(player)
            for combo in self.winning_combos:
                win = True
                for pos in combo:
                    if pos not in positions:
                        win = False
                if win:
                    return player
        return None

    @property
    def heuristic(self):
        if self.player_won:
            return -1
        elif self.tied:
            return 0
        elif self.computer_won:
            return 1

    def get_squares(self, player):
        return [k for k,v in self.squares.iteritems() if v.player == player]

    def make_move(self, position, player):
        self.squares[position] = Square(player)

    def minimax(self, node, player):
        if node.complete:
            return node.heuristic
        a = -1e10000
        for move in node.available_moves:
            child = deepcopy(node)
            child.make_move(move, player)
            a = max([a, -self.minimax(child, get_enemy(player))])
        return a


def get_enemy(player):
    if player == 'X':
        return 'O'
    return 'X'

Answer 1

Su función completa no está funcionando como se esperaba, haciendo juegos para ser declarado atadas antes de cualquier cosa puede pasar. Por ejemplo, considere esta configuración:

>> oWinning = {
 1: Square('X'),
 3: Square('O'), 4: Square('X'),
 6: Square('O'), 8: Square('X'),
}
>> nb = Board(oWinning)
>> nb.complete
True
>> nb.tied
True

Esto debería ser una victoria para el equipo en el siguiente movimiento. En su lugar, se dice que el juego está ligado.

El problema es que su lógica en completa, en este momento, comprobaciones para ver si todos los cuadrados en un combo son libres. Si alguno de ellos no lo son, se presume que esa combinación no se puede ganar con. Lo que tiene que hacer es comprobar si están ocupadas las posiciones en ese combo, y siempre y cuando todas esas combinaciones son Ninguno o el mismo jugador, que combinado deben considerarse todavía disponibles.

por ejemplo.

def available_combos(self, player):
    return self.available_moves + self.get_squares(player)

@property
def complete(self):
    for player in ('X', 'O'):
        for combo in self.winning_combos:
            combo_available = True
            for pos in combo:
                if not pos in self.available_combos(player):
                   combo_available = False
            if combo_available:
                return self.winner is not None
    return True

Ahora que adecuadamente probado esto con el código actualizado estoy consiguiendo el resultado esperado en este caso de prueba:

>>> nb.minimax(nb, 'O')
-1
>>> nb.minimax(nb, 'X')
1

Answer 2

Paso 1: Construye tu árbol de juego

A partir de la actual junta generar todas las posibles movimientos de tu oponente puede hacer. A continuación, para cada uno de los generar todos los posibles movimientos que puede hacer. Para Tic-Tac-Toe simplemente continuará hasta que no se puede jugar. En otros juegos que por lo general va parada después de un tiempo o profundidad dada.

Esto se parece a un árbol, dibujar usted mismo en un pedazo de papel, cartón corriente en la parte superior, todos oponente se mueve por debajo de una capa, todos los movimientos posibles en respuesta de una capa debajo etc.

Paso 2: Puntuación todas las placas en la parte inferior del árbol

Para un juego simple como Tic-Tac-Toe para el 0 si pierde, 50 corbata, 100 victoria.

Paso 3: Propagar la puntuación arriba del árbol

Aquí es donde el min-max entran en juego. La puntuación de un tablero previamente sin puntaje depende de sus hijos y que llega a jugar. Suponga que usted y su oponente siempre elegir el mejor movimiento posible en el estado dado. El mejor movimiento para el oponente es el movimiento que da la peor puntuación. Del mismo modo, su mejor movimiento es el movimiento que le da la puntuación más alta. En caso de turno del oponente, que elija el niño con la puntuación mínima (que maximiza su beneficio). Si es su turno se asume que va a hacer el mejor movimiento posible, por lo que elegir el máximo.

Paso 4: Escoja su mejor movimiento

Ahora jugar el movimiento que da como resultado la mejor puntuación propagada entre todos sus posibles jugadas desde la posición actual.

Trate en un pedazo de papel, si se parte de un tablero en blanco es demasiado para que inicie desde una posición avanzada de Tic-Tac-Toe.

Uso de la repetición: Muy a menudo esto se puede simplificar mediante el uso de la recursividad. La función "puntuación" se llama de forma recursiva a cada profundidad y en función de si o no la profundidad es par o impar que seleccionar max o min, respectivamente, para todos los movimientos posibles. Cuando ésta no es posible, se evalúa la puntuación estática de la junta. soluciones recursivas (por ejemplo, el código de ejemplo) puede ser un poco más complicado de entender.

Answer 3

Como ya saben la idea de Minimax es a lo profundo de búsqueda para el mejor valor, suponiendo que el oponente siempre jugará el movimiento con el peor valor (peor para nosotros, así que es mejor para ellos).

La idea es, que tratará de dar un valor a cada posición. La posición en la que se pierde es negativo (no queremos eso) y la posición en la que gana es positivo. Usted asume que siempre se trate de la posición de más alto valor, pero también asume el oponente siempre apuntará a la posición de menor valor, que tiene el peor resultado para nosotros, y lo mejor para ellos (que ganan, nosotros pierde). Así que ponerse en sus zapatos, tratar de jugar tan bien como sea posible como ellos, y asumen que van a hacer eso.
Así que si usted encuentra que tiene posibles dos movimientos, uno les da la opción de ganar o perder, uno que resulta en empate de todos modos, se asume que irán para el movimiento que tendrá a ganar si se les deja hacer eso. Así que es mejor ir por el empate.

Ahora, para una visión más "algorítmico".

Imagine que su red está casi lleno a excepción de dos posiciones posibles.
Consideremos lo que sucede cuando se reproduce la primera:
El oponente jugará el otro. Es su único movimiento posible así que no tenemos que considerar otras se mueve de ellos. Vistazo al resultado, asociar un valor resultante (+ 8 si won, 0 si sorteo, -8 si se pierde: a tres en raya se puede representar como los +1 y -1 0)
. Consideremos ahora lo que sucede cuando se juega la segunda:
(Lo mismo aquí, el oponente tiene un solo movimiento, mirada a la posición resultante, el valor de la posición).

Usted tiene que elegir entre los dos movimientos. Es nuestro movimiento, por lo que queremos el mejor resultado (este es el "máximo" en Minimax). Elegir el que tenga el mayor resultado como nuestro "mejor" movimiento. Eso es todo por el ejemplo "2 se desplaza desde el extremo".

Ahora imagina que tienes no 2, sino 3 mueve a la izquierda.
El principio es el mismo, que desea asignar un valor a cada uno de los 3 movimientos posibles, para que pueda elegir el mejor.
Así se empieza por considerar uno de los tres movimientos.
Ahora se encuentra en la situación anterior, con sólo 2 movimientos posibles, pero es el turno del oponente. A continuación, empezar a considerar uno de los movimientos posibles para el oponente, como lo hicimos anteriormente. Del mismo modo, nos fijamos en cada uno de los movimientos posibles, y te encuentras con un valor de resultado para los dos. Es el movimiento oponente, por lo que suponemos que jugarán el "mejor" se mueven por ellos, el que tiene la peor participación para nosotros, así que es el que tiene el menor valor (este es el "mínimo" en Minimax). Ignorar la otra; asumen que jugarán lo que encontraron que era mejor para ellos de todos modos. Esto es lo que su movimiento va a ceder, por lo que es el valor que se asigna a la primera de sus tres movimientos.

Ahora se consideran cada uno de sus posibles otros 2 se mueve. Se les da un valor de la misma manera. Y a partir de sus tres movimientos, que elija el que tiene el valor máximo.

Ahora considere lo que sucede con 4 movimientos. Para cada uno de sus 4 movimientos, que mira lo que pasa por los 3 movimientos de su oponente, y para cada uno de ellos se asume que se elija el que le da el peor resultado posible de la mejor de las 2 restantes se mueve para usted.

A ver dónde se dirige esto. Para evaluar un movimiento n pasos desde el extremo, nos fijamos en lo que puede suceder para cada uno de los n posibles movimientos, tratando de darles un valor para que pueda escoger el mejor. En el proceso, usted tendrá que tratar de encontrar el mejor movimiento para el jugador que juega en n-1: el oponente, y elegir el paso con el menor valor. En el proceso de evaluación de la N-1 movimiento, usted tiene que elegir entre las posibles N-2 se mueve, lo que será nuestra, y asume vamos a jugar tan bien como podamos en este paso. Etc.

Esta es la razón por este algoritmo es inherentemente recursiva. Cualquiera que sea n, en el paso n a evaluar todas las medidas posibles a n-1. Aclarar y repetir.

Para hoy tic-tac-toe máquinas son lo suficientemente potente como para calcular el momento todos los resultados posibles derecha fuera desde el comienzo del XXe juego, porque hay sólo unos pocos cientos de ellos. Cuando miras a ponerlo en práctica para un juego más complejo, que tendrá que dejar de computar en algún momento, ya que tomará mucho tiempo. Así que para un juego complejo, que también tendrá que escribir el código que decide si se debe continuar buscando todos los posibles próximos movimientos o para tratar de dar un valor a la posición ahora y volver temprano. Esto significa que usted también tendrá que calcular un valor para la posición que no es definitiva - por ejemplo, para el ajedrez que tomaría en cuenta la cantidad de material de cada oponente ha en el tablero, las posibilidades inmediatas de cheque sin compañero, el número de fichas que controlar y todos, lo que hace que no sea trivial.