Ejemplos de estrategias óptimas encontradas por computadora en juegos

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.

fkenter
fuente
8
No existe tal cosa como "más óptimo".
Jeffε
1
No se puede decir que son estrategias "óptimas", pero las computadoras aparentemente han hecho una gran diferencia en las aperturas de ajedrez.
Peter Shor

Respuestas:

12

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".

Yuval Filmus
fuente
8

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).

Neal Young
fuente
1
No soy un experto en Go, pero mi impresión del trabajo de Mathematical Go es que es una matemática mucho más interesante que interesante, y que las estructuras que encuentran, en su mayor parte, no se correlacionan realmente con las estructuras que ocurren en juegos reales ¿Quizás alguien con más experiencia en Go pueda hablar de esto?
Steven Stadnicki
1
Sí, eso es más o menos lo que entiendo también.
Neal Young
1

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.

SamM
fuente
1

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" :

  #player          #moves
1 Tomoaki Okayama  20  Japan    Czech Open 2012     
2 Moritz Karl      21  Germany  BW Open 2013     
3 István Kocza     22  Hungary  Czech Open 2010     
  Jimmy Coll       22  Belgium  Barcelona Open 2009     
5 Adrian Lehmann   23  Germany  German Open 2013

(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)

Marzio De Biasi
fuente