¿Cuál es el estado del arte en la búsqueda de árbol de ajedrez por computadora?

Question

No me interesan las pequeñas optimizaciones que dan pocos porcentajes de la velocidad. Me interesan 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.

Answer 1

No estoy seguro de si ya lo sabe, pero revise Chess Programming Wiki; es un gran recurso que cubre casi todos los aspectos de la AI 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 es posible que pueda descubrir algunas técnicas interesantes utilizadas en algunos de los programas enumerados here. Si sus preguntas aún no son respondidas, definitivamente le recomendaría que pregunte en el Chess Programming Forums, donde es probable que haya muchos más especialistas 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).

Answer 2

Aunque hay muchas optimizaciones basadas en la heurística (me refiero a las formas de aumentar la profundidad del árbol sin buscarlas realmente) discutidas en la literatura de programación de ajedrez, creo que la mayoría de ellas rara vez se usan. 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 intentar agregar las otras heurísticas. El motivo 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 el árbol alfa-beta a la profundidad máxima siempre han superado los programas que dividen su tiempo entre ciertos niveles de alfa-beta y luego algunos heurísticos.

Aunque usar algunas heurísticas para extender la profundidad del árbol puede causar más daño que bien, 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 está previsto, debe tener un mecanismo de clasificación de movimientos (profundización iterativa). La profundización iterativa puede proporcionarle un 10% de aumento de rendimiento.

Agregando Variante principal searc h La técnica de alpha beta puede darle un 10% de impulso adicional.

Pruebe el algoritmo de MTD (f) también. También puede aumentar el rendimiento de su motor.

Answer 3

Los movimientos de asesino son un buen ejemplo de tamaño de código pequeño y una gran mejora en el orden de movimiento.

Answer 4

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 quiere 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 haya ningún algoritmo "enlatado" para ganar siempre ajedrez y hacerlo muy rápido. La forma en que tendrías que hacerlo es tener TODOS los posibles juegos jugados previamente indexados en una gran base de datos basada en diccionarios y haber guardado en antememoria 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.

Answer 5

MTD(f) o uno de los MTD variants es una gran mejora con respecto norma alpha-beta, siempre y cuando no tiene realmente el detalle fino en su función de evaluación y asumiendo que usted está utilizando el killer heuristic. El history heuristic 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.

Extended futility pruning, que incorpora tanto la poda de inutilidad normal y la profundidad de afeitar, es teóricamente poco sólida, pero notablemente efectiva en la práctica.

Iterative deepening es otra técnica útil. Y enumeré una gran cantidad de good chess programming links here.

Answer 6

Una heurística que no se ha mencionado es Null move pruning.

Además, Ed Schröder tiene una gran página que explica una serie de trucos que utilizó en su motor de Rebel, y cuánto mejora cada contribuyó a acelerar/rendimiento: Inside Rebel

Answer 7

que podría ser un poco fuera de tema, pero "estado de los programas de ajedrez de "arte" usan MPI como Deep Blue para un poder paralelo masivo.

Sólo considere que el procesamiento en paralelo juega un gran papel en el ajedrez moderno

Answer 8

Usando una tabla de transposición con una zobrist hash

Se necesita muy poco código para implementar [un XOR en cada movimiento o unmove, y un si declaración antes de recurrir en el árbol de juego], y los beneficios son bastante buenos, especialmente si ya está utilizando la profundización iterativa, y es bastante modificable (use una tabla más grande, una tabla más pequeña, estrategias de reemplazo, etc.)