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.
- ¿Cómo es la regresión logística un caso especial de Markov Logic Networks?
- ¿Es AI la nueva fiebre del oro?
- ¿Es difícil construir un simulador de planta de energía usando una enorme red neuronal artificial para fines de simulación y educación?
- ¿Qué porcentaje de estudiantes MOOC de aprendizaje automático (ML) realmente termina trabajando con ML?
- ¿Cuál es la diferencia entre las clases de inteligencia artificial?
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.
