algorithm - redes - inteligencia artificial pdf libro
¿Cuál es el estado del arte en la búsqueda de árbol de ajedrez por computadora? (8)
No estoy interesado en pequeñas optimizaciones que dan pocos porcentajes de la velocidad. Estoy interesado en las heurísticas más importantes para la búsqueda alfa-beta. Y los componentes más importantes para la función de evaluación.
Estoy particularmente interesado en los algoritmos que tienen la mayor relación (mejora / código_tamaño). (NO (mejora / complejidad)).
Gracias.
PS Killer move heuristic es un ejemplo perfecto, fácil de implementar y potente. La base de datos de heurística es demasiado complicada.
A pesar de que muchas optimizaciones basadas en la heurística (me refiero a maneras de aumentar la profundidad del árbol sin buscar) se discuten en la literatura de programación de ajedrez, creo que la mayoría de ellas se usan muy poco. La razón es que son buenos impulsores de rendimiento en teoría, pero no en la práctica.
A veces, estas heurísticas pueden devolver un movimiento malo (es decir, no el mejor) también.
Las personas con las que he hablado siempre recomiendan optimizar la búsqueda alfa-beta e implementar la profundización iterativa en el código en lugar de tratar de agregar las otras heurísticas.
La razón principal es que las computadoras están aumentando en potencia de procesamiento, y la investigación [necesito citas, supongo] ha demostrado que los programas que usan su tiempo total de CPU para forzar brutales al árbol alfa-beta hasta la profundidad máxima siempre han superado a los programas que se dividen su tiempo entre ciertos niveles de alfa-beta y luego algunos heurísticos.
Aunque el uso de algunas heurísticas para extender la profundidad del árbol puede causar más daños que beneficios, hay muchos impulsores de rendimiento que puede agregar al algoritmo de búsqueda alfa-beta.
Estoy seguro de que sabe que para que alfa-beta funcione exactamente como se pretende, debe tener un mecanismo de clasificación de movimientos ( profundización iterativa ). La profundización iterativa puede proporcionarle un 10% de aumento de rendimiento.
Agregar la técnica Principal search h de variación a alpha beta puede darle un 10% de impulso adicional.
Pruebe el algoritmo MTD (f ) también. También puede aumentar el rendimiento de su motor.
La mayoría de los algoritmos de AI de juegos de mesa se basan en http://en.wikipedia.org/wiki/Minmax MinMax. El objetivo es minimizar sus opciones mientras maximiza sus opciones. Aunque con el ajedrez, este es un problema de tiempo de ejecución muy grande y costoso. Para ayudar a reducir eso, puedes combinar minmax con una base de datos de juegos jugados previamente. Cualquier juego que tenga una posición similar en la mesa y tenga un patrón establecido sobre cómo se ganó ese diseño para su color se puede usar hasta "analizar" dónde moverse luego.
Estoy un poco confundido con lo que quieres decir con la mejora / code_size. ¿Realmente se refiere al análisis de mejora / tiempo de ejecución (gran O (n) vs. o (n))? Si ese es el caso, hable con IBM y Big Blue, o con el equipo de Parallels de Microsoft. En PDC hablé con un tipo (cuyo nombre ahora se me escapa) que estaba demostrando Mahjong usando 8 núcleos por oponente y ganaron el primer lugar en la competencia de diseño de algoritmos del juego (cuyo nombre también se me escapa).
No creo que existan algoritmos "enlatados" para ganar siempre ajedrez y hacerlo muy rápido. La forma en que tendrías que hacerlo es tener TODOS los posibles juegos jugados anteriormente indexados en una gran base de datos basada en diccionarios y haber guardado previamente el análisis de cada juego. Sería un algoritmo MUY compex y sería un problema de mejora / complejidad muy pobre en mi opinión.
Los movimientos de asesino son un buen ejemplo de tamaño de código pequeño y una gran mejora en la ordenación de movimientos.
No estoy seguro de si ya lo sabe, pero consulte la Wiki de programación de ajedrez : es un gran recurso que cubre casi todos los aspectos de la IA moderna de ajedrez. En particular, en relación con su pregunta, consulte las secciones de Búsqueda y evaluación (en Principios temáticos) en la página principal. También podría descubrir algunas técnicas interesantes utilizadas en algunos de los programas enumerados aquí . Si sus preguntas aún no son respondidas, definitivamente recomendaría que pregunte en los foros de programación de ajedrez , donde es probable que haya muchos especialistas más para responder. (No es que no necesariamente obtendrá buenas respuestas aquí, solo que es más probable en foros de expertos específicos del tema).
Una heurística que no se ha mencionado es la poda de movimiento nulo .
Además, Ed Schröder tiene una gran página explicando una serie de trucos que utilizó en su motor Rebel, y la cantidad de mejora que cada uno contribuyó a la velocidad / rendimiento: Inside Rebel
Podría estar un poco fuera del tema, pero los programas de ajedrez "de última generación" usan MPI como Deep Blue para un poder paralelo masivo.
Solo tenga en cuenta que el procesamiento paralelo juega un gran papel en el ajedrez moderno
Usando una tabla de transposición con un hash zobrist
Se necesita muy poco código para implementar [un XOR en cada movimiento o unmove, y una instrucción if antes de volver a generar en el árbol del juego], y los beneficios son bastante buenos, especialmente si ya está utilizando la profundización iterativa, y es bastante modificable (uso una mesa más grande, una mesa más pequeña, estrategias de reemplazo, etc.)
MTD (f) o una de las variantes de MTD es una gran mejora con respecto a la alfa-beta estándar, siempre que no tenga detalles realmente finos en su función de evaluación y suponiendo que está utilizando la heurística asesina . La historia heurística también es útil.
El programa de ajedrez mejor calificado Rybka aparentemente ha abandonado MDT (f) a favor de PVS con una ventana de aspiración cero en los nodos PV.
La poda extendida de inutilidad , que incorpora tanto la poda inútil normal como la depuración profunda, es teóricamente poco sólida, pero notablemente efectiva en la práctica.
La profundización iterativa es otra técnica útil. Y enumeré muchos buenos enlaces de programación de ajedrez aquí .