Hace poco conocí Quarto, un juego inventado por el matemático suizo Blaise Muller (que incluso tiene su propio Página de Wikipedia ). La conjetura de interés es que no hay empates posibles en Quarto, es decir, si cada juego posible debe producir una combinación ganadora [en particular, si es cierto, esto influye mucho en las estrategias de juego]. ¡A primera vista, hay 16! (algo más de 20 trillones) de posiciones de juego completas posibles, aunque hay que reconocer que hay muchas simetrías en juego.
En un intento de probar/desmentir la conjetura, construí una simulación de Quarto en MATLAB que era algo inteligente (cortaba muchas ramas del árbol antes de tiempo). Después de una semana de tiempo de ejecución, lo dejé; en ese momento había mirado alrededor de 2,5 mil millones de combinaciones de juego, y no encontró ningún empate.
Así que creo que estoy buscando una de estas cuatro cosas:
- Un solo contraejemplo de un tablero completo de Quarto que es un empate.
- Una prueba analítica de que no hay empates posibles.
- Una indicación de algún otro lugar donde se haya tratado esta cuestión anteriormente.
- Una estrategia para analizar el espacio de búsqueda necesario que es (como mínimo) unos cuatro órdenes de magnitud más eficiente que la fuerza bruta.
¿Algún comentario o idea?
1 votos
web.archive.org/web/20041012023358/http://ssel.vub.ac.be/ dice ...En consecuencia, si ambos jugadores juegan a la perfección siempre podrán forzar las tablas.
0 votos
Bingo, ahora que estoy seguro de que existe un sorteo. La siguiente pregunta obvia es ¿cómo de raros son? Estoy trabajando en ello.
0 votos
@Henry - PD - ¡Buen enlace!