¿Cómo "piensan" los motores de ajedrez?

Lo que quiero saber es cómo se programan los motores para encontrar movimientos. Estoy seguro de que primero calculan las líneas más forzadas, como capturas y controles. ¿Pero qué pasa con los movimientos posicionales sutiles y profundos? Parece que también los encuentran muy rápidamente (en términos generales. Por supuesto, se pierden tales movimientos de vez en cuando). Como en, ¿cómo están programados para buscar movimientos silenciosos / ideas posicionales? No pueden simplemente forzar la fuerza bruta en cada movimiento, ya que eso tomaría demasiado tiempo, por lo que debería haber una forma inteligente de llegar a los mejores movimientos realmente rápido. Estoy interesado en saber esto porque creo que también ayudaría a los jugadores a pensar en el tablero en el mundo real.

En general, los motores de ajedrez usan un árbol de decisión. La raíz del árbol es la posición actual y tiene un nodo secundario para cada posición que se puede hacer haciendo un movimiento legal. Cada uno de estos nodos a su vez tiene un nodo hijo para las posiciones a las que se puede llegar haciendo un movimiento legal desde ellos. El motor empuja el árbol a una profundidad definida por sus capacidades y el tiempo que se le permite "pensar". Las posiciones que se pueden alcanzar de más de una manera simplemente tienen referencias cruzadas para que no tengan que considerarse más de una vez. Una vez que se crea el árbol, la computadora usa un conjunto de reglas ponderadas para analizar las posiciones finales en el árbol y comienza a eliminar aquellas que no son deseables o que el oponente puede evitar que llegue. El árbol se corta de esta manera hasta que solo quede un movimiento y la computadora lo haga.

http://www.chess.com/blog/zaifrun tiene series o artículos sobre cómo crear un motor de ajedrez si desea conocer más en profundidad cómo funcionan.

Estás haciendo una pregunta bastante compleja, pero es bueno volver a lo básico. Hay un par de conceptos a considerar:

Evaluación

Si a un jugador (real) se le muestra una posición y se le pregunta "¿quién está ganando este juego?", ¿Cómo se decide? Lo más probable es que verifiquen algunas cosas básicas, como: diferencias de material, el grado en que las piezas se han desarrollado o están posicionadas "bien", peones duplicados / aislados / conectados / pasados, archivos abiertos (controlados), hasta qué punto el tablero son los peones.

Ahora, si tuviera que hacerlo, podría encontrar una forma sistemática de calcular un puntaje de posición basado en lo anterior. Podrías decidir, por ejemplo, que un peón vale 1 punto, y que un peón pasado vale 0,3 puntos más. Los peones aislados o duplicados pueden valer un poco menos, etc. Si sumas todo, obtienes un valor estimado para la posición inmediata en cuestión.

Esto se conoce como evaluación y, básicamente, todos los programas de ajedrez tienen una forma de evaluar las posiciones (ignorando los motores de ajedrez de IA que son típicamente muy débiles).

¿Pero qué pasa con los movimientos posicionales sutiles y profundos?

Bueno, apenas hemos arañado la superficie de la evaluación de posición. La implementación real de una función de evaluación podría ser simplista, para permitir que se evalúen más posiciones por segundo (aunque de manera aproximada), o más compleja, lo que lleva a menos posiciones evaluadas, pero con un mayor grado de confianza. No es inusual que la función de evaluación tenga en cuenta cientos o incluso miles de datos separados.

Buscar

He omitido específicamente algo de lo anterior, que la mayoría de los jugadores reales pensarán de inmediato: ¿hay alguna forma de ganar el juego de inmediato para cualquier lado? ¿Hay compañeros o piezas "colgantes" visibles? Aunque es fácil trivializar esto, es cualquier cosa menos trivial.

¿Qué significa para un jugador tener plena confianza en una combinación? Al final, se reduce a haber calculado todas las opciones. Los jugadores reales generalmente no harán esto (excepto para compañeros triviales o muy forzados), la mayoría de las veces solo consideraremos un puñado de opciones y descartaremos otras que parecen ser "no constructivas" o que obviamente conducen a una pérdida . A menudo cometemos errores durante este cálculo, por ejemplo, podemos darnos cuenta de que un cambio en las órdenes de movimiento hace que las amenazas se evapore, etc. El punto es que para estar completamente seguro de una combinación, en realidad necesita calcular todo el camino hasta su conclusión, suponiendo que cada el jugador solo hará el mejor movimiento posible disponible para ellos (esto se conoce como "min / max").

Ahora, dado que el ajedrez tiene un espacio de búsqueda mucho más grande (esto es a lo que se refiere "todos los movimientos posibles en el futuro") de lo que es factible para que una computadora calcule, deben hacerse compromisos. Al igual que los humanos, las computadoras pueden decidir ignorar líneas enteras de pensamiento basadas en ciertos criterios. Esto se conoce como heurística . Vale la pena señalar que si bien solo puede estar realmente seguro de una combinación si la fuerza bruta, una función de evaluación compleja a menudo puede detectar la presencia de amenazas (por ejemplo, podríamos contar tenedores, oportunidades de brochetas, etc., para guiar una búsqueda en esa dirección )

Al final, aunque las computadoras son extremadamente rápidas, son las heurísticas las que les permiten calcular tan profundamente. Dicho esto, es posible que se sorprenda de lo profundo que se calculan los motores modernos, por lo general es más allá de 3 movimientos, incluso en juegos rápidos.

Conclusión / combinándolo todo

Entonces, para resumir: las funciones de evaluación tienen mucha inteligencia incorporada (es decir, toman en consideración más cosas que un jugador humano promedio), las heurísticas permiten que la computadora analice líneas de pensamiento que decide que probablemente no terminarán bien, y las computadoras son extremadamente, extremadamente rápidas. Súmelos y son bastante difíciles de superar.

Estoy de acuerdo con las respuestas

Recuerdo al GM Roman Dzindzichashvili hablando de eso, en uno de los videos de Roman Labs , no recuerdo qué video era (si alguien conoce los detalles, edite mi respuesta).

Roman dijo que el desarrollador del motor Fritz es su amigo. Así que Roman probó a Fritz para ver qué tan bueno era, y el desarrollador le dijo a Roman que para que fritz tomara decisiones complejas (sacrificando materiales a cambio de una ventaja posicional, por ejemplo) tenían que cambiar el valor de las piezas, como decirle al programa que un obispo malo vale 1 punto, un obispo en diagonal abierta vale 7 puntos, los caballeros valen 5 puntos en posiciones cerradas ...

No sé los números exactos para cada pieza, pero así es como funciona, y ahora su motor no tendrá ningún problema en sacrificar a un alfil malo o lo que sea si puede decirle el valor de cada pieza en cada posición.

EDITAR

Ver también The Chess Programming Wiki .

Es simplemente imposible para las computadoras mirar lo suficientemente profundo (25 capas y más) y verificar cada movimiento posible.

Lo que hace posible es la técnica llamada poda alfa-beta que significa que las computadoras, similares a los humanos (pero mucho mejor) solo siguen las prometedoras continuaciones.

Evalúan las posiciones constantemente (según algunas reglas precodificadas, valorando el material, la seguridad del rey, la actividad, las estructuras de peones, etc.) y analizan las variaciones que parecen conducirlos hacia la mejor posición.

Todavía está cerca de la magia cómo logran hacerlo lo suficientemente eficiente como para evaluar millones de estas posiciones en un segundo.

En resumen, tienes razón, no pueden ver todos los movimientos si juegan ajedrez estratégico, pero pueden ver rápidamente movimientos decentes. El problema aún está en los planes a largo plazo y en el horizonte que pueden ver, pero esto se está trabajando (Rybka analiza mucho más lento, pero juega mucho más al ajedrez posicional, mientras que Houdini es romántico en su 'corazón mecánico' calculando más movimientos y jugando más agresivamente). ¡Incluso las computadoras tienen sus propios estilos!

La poda alfa-beta simplemente significa que si encuentra una línea que resulta mal para usted, deja de mirar ese movimiento candidato y, en su lugar, prueba con otros. Es un tipo de poda hacia atrás, lo que significa que nunca perderá un buen movimiento como resultado. La poda hacia adelante, por el contrario, se basa más en conjeturas. La poda inútil, la reducción de movimientos tardíos y la maquinilla de afeitar son tipos de poda hacia adelante, y todos se basan en la sensación del programador sobre qué tipo de movimientos deben considerarse. Un programa que realiza muchas podas hacia adelante puede perder sacrificios sorprendentes que conducen a aparearse, pero por otro lado, elimina muchos movimientos realmente malos, por lo que puede profundizar en la observación de los movimientos que favorece.

La mayoría de los motores buscan los primeros movimientos en profundidad y examinan todas las posibilidades. Si ningún movimiento falla alto (es decir, parece claramente peor que un movimiento que ya ha considerado), extiende la búsqueda un poco más. En general, continúa explorando cada línea hasta llegar a una posición inactiva (sin controles, capturas, amenazas de pareja, etc.), y luego realiza su evaluación. Los movimientos silenciosos pueden no considerarse cuando están en lo profundo del árbol de búsqueda, pero una vez que llegas a esa posición real en el juego, el motor observa todos los movimientos, silenciosos y agudos por igual. En realidad, puede ver esto en la salida del motor a veces, cuando un motor de repente favorece un movimiento que no había estado considerando algunos movimientos hacia atrás.

Los motores calculan tan rápido que no es tan importante para ellos considerar qué movimiento mirar primero, pero para los humanos esta es una pregunta clave. Jonathan Tisdall intenta responder esto en su libro, Mejore su ajedrez ahora. Cuando estás en el ataque, él sugiere que primero veas los movimientos más violentos. Cuando defiendes, primero miras las líneas más difíciles. También cita reglas generales de posición (por ejemplo, centralización, coordinación) al decidir qué movimientos mirar primero.

Otros libros que pueden ser relevantes son los Movimientos de ajedrez invisibles de Emmanuel Neimann y los Movimientos de ajedrez forzado de Charles Hertan, quienes argumentan sobre la importancia de considerar movimientos improbables o sorprendentes en posiciones agudas. Hertan incluso habla de desarrollar 'ojos de computadora' para tales tácticas.