El algoritmo MTD (f) para resolver problemas de optimización de minimax es bastante inteligente. No hay un criterio objetivo más inteligente, pero hay un criterio objetivo “más recientemente impresionado por” que este algoritmo satisface para mí, y tal vez para usted también en un momento.
MTD (f) utiliza la búsqueda alfa beta como una subrutina, por lo que mencionaré rápidamente qué es eso primero. Alpha Beta search es una búsqueda minimax que mantiene la mejor solución hasta ahora para el jugador máximo, [math] \ alpha [/ math], y la mejor solución hasta ahora para el jugador min, [math] \ beta [ / math], para que el jugador max pueda evitar evaluar subárboles donde se pueda verificar más rápidamente que el jugador min puede producir un valor [math] v <\ alpha. [/ math] Y viceversa con el jugador min usando [math ] \ beta [/ math] para evitar expandir subárboles. Cuando la búsqueda Alfa Beta se usa sola, [matemática] \ alpha [/ matemática] y [matemática] \ beta [/ matemática] se inicializan a [matemática] – \ infty [/ matemática] y [matemática] + \ infty [/ matemática] respectivamente, de modo que las soluciones fuera del rango especificado nunca puedan ocurrir. Esta inicialización conservadora garantiza la corrección, pero las ventanas anchas ofrecen menos oportunidades para podar subárboles (inicialmente no poda y más poda ya que los límites dan más información).
MTD (f) está motivado por este hecho sobre la relación de las tasas de poda y el ancho de la ventana para comenzar con una suposición inicial de la solución minimax, f, y luego realizar búsquedas Alfa Beta con ventanas pequeñas como [matemáticas] \ alpha = f-1 [/ math] y [math] \ beta = f [/ math]. Esto hace que el resultado de una búsqueda alfa beta de ventana pequeña no sea la solución definitiva, sino información sobre si la solución es mayor o menor o igual que el valor actual de f. MTD (f) continuará haciendo búsquedas rápidas (debido a la alta tasa de poda) hasta que los límites superior e inferior conocidos colisionen. Hablando intuitivamente, este uso de límites para ampliar la respuesta es rápido por razones similares a que la búsqueda binaria en una lista ordenada es rápida.
- ¿Qué sabes sobre el algoritmo de búsqueda de Fiverr?
- ¿Cómo son los problemas de programación competitiva? ¿Son problemas que afectan a la sociedad que pueden resolverse mediante algoritmos informáticos? ¿Puede dar un ejemplo?
- ¿Las estructuras de datos son más importantes o es el lenguaje?
- ¿Debería usar la función de clasificación () incorporada de C ++ para problemas en la programación competitiva, o debería implementar el algoritmo por mi cuenta?
- ¿Cuál es la explicación de este código?
Algoritmos alfa beta de ventana pequeña como este son utilizados por motores de ajedrez de última generación, como Stockfish, que se encuentra entre los mejores del mundo en este momento. Por supuesto, los motores de ajedrez no obtienen toda su fuerza de la elección del algoritmo de búsqueda minimax, también usan tablas de transposición y heurísticas de orden de movimiento, etc.
