¿Cómo funciona Deep Blue?

Ha habido muchos avances desde la última vez que vi este problema. Leí un libro sobre esto hace unos 20 años, pero lo más probable es que ese libro ya no esté a la vanguardia.

Deep Blue pudo aprovechar la moderna arquitectura de resolución de problemas de CPU múltiple en paralelo. Específicamente, tenían 64 CPU, una asignada a cada cuadrado en el tablero, aunque no sé cómo esta arquitectura asignó evaluaciones de movimientos múltiples, específicamente qué movimientos o árboles de ruta se asignaron a qué CPU y cómo se compartieron las tareas. Además, esto es parte de la CS moderna y después de mi tiempo, aunque estoy seguro de que ahora es estándar o al menos más estándar en los estudios de CS, dado que los chips modernos están diseñados de esta manera.

El otro problema es la evaluación de la posición. Los humanos y, en particular, los Grandes Maestros entrenados son increíblemente buenos para evaluar el potencial de una posición y un movimiento. Estoy seguro de que un algoritmo de computadora tiene que verificar muchos más árboles que un GM, ya que el GM podrá determinar con cierta idea qué árboles tienen más posibilidades de examinar. Es probable que otros GMs puedan ver más allá de algunos movimientos de sacrificio blandos o locos para ver si esa línea es prometedora, si los jugadores normales de ajedrez de menor rango ya hubieran rechazado el examen de esta combinación. De vuelta a las computadoras. Los algoritmos originales utilizaron el valor por pieza como una forma de evaluar la posición y comparar dos posiciones potenciales de dos ramas finales diferentes en el árbol de decisión. Teniendo en cuenta que la computadora también tiene que evaluar la mejor respuesta de los oponentes, ya que la computadora no solo está buscando la mejor posición de las computadoras, sino también la mejor posición de las computadoras dada la evaluación de todas las respuestas de los oponentes para la mejor respuesta de los oponentes. Sin embargo, el valor de la pieza no tiene relación con la posición o el potencial de una posición, otras dos posiciones pueden tener el mismo valor de la pieza pero resultados muy diferentes.

Hay dos formas de mejorar esto, hacer que el árbol que se examina sea más largo, lo que aumenta exponencialmente la potencia de cálculo necesaria (la ley de Moore es el factor limitante aquí) o mejorar el algoritmo de evaluación. El algoritmo adicional más fácil de entender para los humanos también tiene paralelos en las enseñanzas de los humanos. La noche en el borde es sombría. Toma el centro. Controla el centro. El obispo y la reina tienen más movimientos potenciales cuando están en el centro del tablero que controla el centro … (Cuando el obispo está hacia una esquina o borde, una o ambas diagonales se acortan, y por lo tanto hay menos movimientos potenciales). es la forma algorítmica más simple, solo cuenta el número de movimientos potenciales (la computadora es rápida en esto incluso si somos lentos), incluidos los movimientos que son ilegales (tomar tu propia pieza) o que no tienen sentido en este momento (regalar una pieza …), Pero en esencia son cuadrados controlados o influenciados por esa pieza. Esto se convierte así en una forma rápida para que la computadora valore algorítmicamente dos posiciones de valor de pieza potencialmente iguales o incluso valore potencialmente un sacrificio que crea oportunidades incluso si el árbol no puede ser examinado completamente hasta el final … Claramente ponderando diferentes cuadrados con diferentes valores y ponderando movimientos vs. control vs. control en un área en disputa podría agregar más matices a esto de una manera que podría especificarse algorítmicamente. Check o la amenaza de Checkmate o incluso la amenaza de check limitan aún más los movimientos potenciales de un oponente, ya que a pesar de que pueden controlar la mayoría del tablero en este momento en respuesta al check, sus movimientos potenciales reales provienen de un conjunto muy restringido. Persiguiendo al rey con cheques en todo el centavo del tablero tiene mucho potencial, incluso si hay sacrificios de piezas en el camino para mantener esta cadena de cheques en funcionamiento. Por lo tanto, no todos los tipos de movimientos “potenciales” deberían tener el mismo valor, aunque probablemente ninguno debería tener valor cero … Comprobación descubierta o incluso un ataque descubierto (moviendo otra pieza) para que la comprobación ahora expanda aún más los movimientos “potenciales” a la presencia una pieza de bloqueo, claramente, pero por la presencia de muchas piezas de bloqueo tendría menos valor …

De esta manera, se podría tratar de adaptar un banco de datos de GM conocidos o juegos de ajedrez de alta calidad a varios algoritmos y extraerlos de datos para determinar cuáles son las mejores variables indicadoras de quién será el ganador. De esta manera, se podría utilizar la minería de datos en un conjunto de “pruebas” algorítmicas comprobables y comprobables para tratar de determinar cuál es el peso apropiado de un control de centro frente a borde cuadrado … Y el valor de un forzado, versus legal, vs. movimiento de esfera de control, vs. pero para una pieza de bloqueo también podría ponderarse.

El otro truco puede ser no evaluar todas las rutas a los mismos n niveles de profundidad. Tal vez todos los caminos se evalúen a m de profundidad y luego el árbol se pode a los 64 mejores caminos y esos se evalúen más a n> m de profundidad o incluso puede ser que estos solo elijan los 8 mejores movimientos (puntaje de mayor potencial) en cada camino para avanzar a esa n profundidad, reduciendo / recortando parte del componente exponencial de llegar a la profundidad n.

Al final, tales pensamientos también son beneficiosos para que un jugador de ajedrez entienda mejor cómo podemos evaluar el tablero. Y aunque en este punto Deep Blue es el campeón, eso no significa que los humanos no puedan entrenar para aprovechar el tipo de movimientos que un algoritmo informático perderá o tendrá más dificultades para evaluar.

Aunque hay varios programas comerciales disponibles, y por lo tanto debe haber mucha experiencia y conocimiento desarrollado, creo que sería difícil comenzar desde cero y desarrollar un nuevo algoritmo competitivo independiente sin un préstamo serio del conocimiento existente y algoritmos Ha habido muchas mejoras en los últimos 30 años e incluso los programas baratos “simples” ahora son bastante fuertes, tal vez esto solo está aplicando viejos algoritmos defectuosos a computadoras más rápidas, pero esto requeriría aumentos exponenciales en el tiempo de computación (y sí) han sido incrementos exponenciales en el tiempo computacional en los últimos 30 años), pero creo que los algoritmos también han evolucionado para ser más inteligentes sobre qué caminos evaluar y cómo evaluar y diferenciar el potencial.

More Interesting

¿Los asistentes personales de IA se convertirán en algo común?

¿Será posible tener una máquina de IA que construya su propio lenguaje de programación y se desarrolle / mejore por sí mismo?

¿Qué tan buenos son los algoritmos generales de juego?

¿Cómo pueden los ingenieros industriales ser parte de la próxima revolución industrial, es decir, la inteligencia artificial?

Si el software fuera tan inteligente como nosotros, ¿en qué entorno funcionaría?

¿Cuáles son algunos métodos para etiquetar datos de entrenamiento para una red neuronal?

¿Existe una solución fintech que use IA?

Cuando la inteligencia artificial (IA) se negocia en los mercados de valores, ¿qué fuente de noticias siguen la mayoría de las IA?

¿Podría la inteligencia artificial desarrollar emociones?

¿Es la IA la próxima ola de evolución? ¿Es esto lo que es 'Kali Yuga'?

¿Qué tipo de IA es la computadora esposa de plancton en Bob Esponja?

Después del curso de ML de Andrew Ng, ¿debo hacer el curso de red neuronal de Geoffrey Hinton antes de hacer un aprendizaje profundo? ¿Cuánto conocimiento de redes neuronales es lo suficientemente bueno como para comenzar a hacer un aprendizaje profundo?

¿Por qué RR.HH. pone tanto énfasis en el EQ de un empleado, especialmente en un momento en que los robots y la IA están a punto de reemplazar a la fuerza laboral humana?

¿Qué son buenos robots que hablan en 2016?

¿El aprendizaje automático es parte de la inteligencia artificial?