Estoy buscando ejemplos en juegos como Go, Chess y Backgammon, donde el movimiento óptimo creído resultó ser subóptimo cuando una computadora encontró mejores estrategias.
8
Estoy buscando ejemplos en juegos como Go, Chess y Backgammon, donde el movimiento óptimo creído resultó ser subóptimo cuando una computadora encontró mejores estrategias.
Respuestas:
El ejemplo más conocido es probablemente las damas (también conocidas como borradores ), que se resolvió recientemente en 2007 (el juego es un empate). Otros ejemplos se enumeran en la página de Wikipedia sobre juegos resueltos ; notables entre ellos son conectar cuatro y nueve hombres morris . Además, se han resuelto varios finales de ajedrez.
Quizás esto no parezca una respuesta a su pregunta, pero si un experto (como Marion Tinsley ) pierde ante un programa de computadora, entonces la computadora debe haber encontrado un movimiento "más óptimo".
fuente
Ver Wolfe y Berlekamp - Mathematical Go . Utilizando la teoría de los juegos de Conway, muestran cómo analizar ciertos tipos de finales de Go. Sus soluciones resultan ser mediblemente mejores que las soluciones dadas por los mejores jugadores de Go. (No es exactamente una respuesta a su problema, ya que esas últimas soluciones probablemente nunca se consideraron óptimas).
fuente
Las técnicas de final de juego de ajedrez se han mejorado enormemente con el advenimiento de las bases de tablas de finales Las bases de las mesas finales son tablas de búsqueda que resuelven el ajedrez cuando no hay más de (actualmente) siete piezas en el tablero. Aquí hay una tabla en línea que he usado en el pasado que funciona para hasta seis piezas.
Algorítmicamente, estas bases de tablas no son muy interesantes; Se generan principalmente por la fuerza bruta. Sin embargo, han contribuido a varios aspectos de la teoría de los finales. Wikipedia tiene un buen resumen de algunos puntos interesantes aquí.
Estos descubrimientos también tuvieron implicaciones para la "regla de cincuenta movimientos", que establece que después de cincuenta movimientos sin captura o avance de peón, cualquier jugador puede reclamar un empate. Incluso antes del análisis por computadora, se pensaba que varios juegos finales tomaban más de cincuenta movimientos, y la regla se extendió ligeramente en esas circunstancias (probablemente el más famoso es el juego final de torre y alfil contra torre ). A medida que el número de posiciones que requerían estos movimientos se hizo mayor, estas extensiones se eliminaron y la regla normal de 50 movimientos se restableció en todos los casos. El análisis moderno ha demostrado que algunos finales requieren varios cientos de movimientos .
Este es otro artículo interesante, que resume algunos efectos de las bases de tablas de siete piezas en la teoría de finales. Particularmente me gusta el mutuo zugzwang que se muestra en la última posición.
fuente
No es propiamente una "estrategia de juego", sin embargo, en 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson y John Dethridge descubrieron que todas las posiciones del cubo de Rubik se pueden resolver con un máximo de 20 vueltas con una prueba asistida por computadora [1] ... un buen resultado.
El código fuente anotado está disponible en http://cube20.org/src/ .
El número promedio de movimientos realizados por los métodos de resolución estándar es ~ 50-60, pero también hay un salón de la fama oficial de "pocos movimientos" :
(tenga en cuenta que el límite superior de 20 se alcanzó solo una vez en 2012 ... así que en los campeonatos de cubos de Rubik los humanos están lejos de jugar la "estrategia óptima" :)
[1] Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge: El diámetro del grupo de cubos de Rubik es veinte. SIAM J. Matemáticas discretas. 27 (2): 1082-1105 (2013)
fuente