¿Cómo probar que cada subsección, la estrategia es más óptima en el algoritmo de Minimax?

Question

La pregunta es como lo sugiere el título.

Sé que el algoritmo de Minimax hace esto para el juego de 2 personas (asume que queremos maximizar la ganancia de A): cuando es su turno, tomamos el máximo de los valores de los niños porque estamos maximizando la ganancia de A, y cuando estáEl turno de B, tomamos los valores mínimas de los niños porque queremos minimizar la ganancia de B.

Sin embargo, no creo que la lógica anterior demuestre que cada sub-problema, la estrategia es la más óptima en el algoritmo de minimax.¿Algún sugerencia o soluciones a la pregunta que propuse?Si la lógica anterior lo hace, ¿podría elaborarlo?

Answer 1

La reclamación Minimax tiene: Minimax está dando una estrategia óptima si el otro jugador también está utilizando la misma estrategia.

base : para una hoja en el árbol del juego: solo hay una estrategia, que minimax obviamente elige, y es óptimo, ya que es el único.
hipótesis : Minimax elige la estrategia óptima para un juego de profundidad d.
prueba :

Veamos un juego de profundidad d+1. Obviamente hay 2 escenarios posibles:

1. está fuera, esta es una fase max. En este caso, de todos los movimientos posibles que podemos hacer, Minimax evalúa recursivamente el valor MIN-MAX para cada una estrategia, y nos da el resultado óptimo para un 'sub-juego', donde hemos elegido este movimiento. Cada uno de estos subgames es de profundidad d, y de la hipótesis de inducción, es óptimo.
   Ya que esta es la fase máxima: el algoritmo MIN-MAX elige al máximo, que es la solución óptima para nosotros.
2. es el turno del oponente: esta es la fase min. De manera similar a la lógica anterior, Minimax divide el caso a todos los movimientos posibles que el oponente puede hacer, y evalúa su resultado. De la hipótesis de inducción, las evaluaciones son óptimas, y elegimos lo mínimo de ellos, lo que será lo que habría elegido el oponente, y es una estrategia óptima para él (y asumir que el oponente elige de manera óptima por cada paso del camino). El oponente elige la evaluación mínima, que minimiza nuestro beneficio y, por lo tanto, maximiza su beneficio.

qed

Basado en ello, puede concluir otra reclamación de Minimax: el valor devuelto por la estrategia no es menos de lo que realmente obtendrá (independientemente de la estrategia de OppNent). Esto puede ser probado por inducción de manera muy similar a la anterior.

Directrices:

base : una estrategia solamente, y la está devolviendo, cuando el 'árbol' es en realidad una hoja.
reclamación : el valor devuelto por Minimax para el juego de profundidad d es un límite inferior a todos los juegos que se juegan a partir de este nivel, donde eligió de acuerdo con Minimax, y no hay restricciones al oponente.
prueba :

Veamos el juego de profundidad d+1.

1. Si es su turno, eligió el máximo de todas las hojas, ya que usted Tener la elección aquí. Cada una de las hojas le garantiza (induciton hipótesis) al menos algún valor, y al elegir el máximo de ellos - También garantiza el valor elegido.
2. Si es el turno del oponente, no tiene control sobre la elección. Solo puedes estar seguro de que él eligió un poco de movimiento, sin idea, que. Sin embargo, para todos los movimientos posibles, obtiene un nuevo 'Subcame' de profundidad d, donde la hipótesis de inducción se mantiene. El oponente puede elegir cualquiera de estos movimientos, por lo que puede garantizar que después de este movimiento, tendrá un valor de al menos min{game after opponent move}, que es exactamente lo que el retorno de la fase mínima.

qed .

Answer 2

No puede demostrar que Minimax maximiza el beneficio del jugador, porque Minimax no intenta maximizar la ganancia del jugador.

lo que hace Minimax es Minimizar Posible la pérdida del jugador ;Es decir, sus decisiones son conservadoras y asumen el peor escenario (juego óptimo del otro jugador).Intenta demostrar que uno;Lo encontrarás mucho más sencillo.