número medio de movimientos necesarios para completar una partida de FreeCell

Question

A veces, terminar una partida de FreeCell me lleva 10 minutos, otras veces sólo un minuto.

Sé que todas las ofertas de FreeCell en windows, excepto una, se pueden ganar, pero no estoy seguro de si son aleatorias o no [todavía eso es irreverente].

Supongamos: TODOS LOS JUEGOS POSIBLES. Reparto aleatorio. NO hay automatización.

IE. El número mínimo de clics es 52, no 0.

¿Cuál es el número medio mínimo de movimientos necesarios para completar una partida de Freecell?

Answer 1

Sorprendentemente, esto ya se ha estudiado. Y casi me avergüenza decir que estoy familiarizado con el resultado. Yo solía freecell mucho. Y para que sepas, 11982 es el juego imposible de Frecell. Pero recomiendo entrar en los juegos -1, -2, -3, etc también.

Así que aquí están algunas estadísticas de algunos estudios de freecell. En primer lugar, la profundidad de los ases, es decir, cuántas cartas cubren los ases, no es una buena medida de la dificultad. De media, 11,077 cartas cubren los ases (contando los ases). Analizando las docenas de miles de tratos, se necesita una media de entre 42,12 (de un solucionador que ejecutó 1,5 millones de tratos) y 46,33 (de un solucionador en 32000 tratos, los 32000 originales) movimientos para resolver. Esta es una medida difícil, ya que se basa en la calidad del solucionador, y no se sabe si estos solucionadores eran óptimos.

Un interesante estudio basado en jugadores demostró que alrededor del 79% de los tratos son resueltos por una persona en su primer intento. También resulta que algunas personas examinan cuántas freecells (las cuatro de la parte superior izquierda) son realmente necesarias para resolver un juego. El imposible 11982 se puede resolver con 5 freecells. Casi todos los juegos se pueden resolver con 3. Más de la mitad se pueden resolver con 2. Y casi 100 se pueden resolver sin ninguna célula libre . ¡Toma eso, freecell!

Uno de los grandes problemas es que los juegos de las celdas libres no están en absoluto surtidos al azar, por lo que no existen soluciones de lápiz y papel. Pero mucha gente se ha preocupado (sorprendentemente) por estas cuestiones, por lo que estos resultados son todos límites superiores. En resumen, unos 45 movimientos es el mínimo medio.

Referencias:

[1] http://solitairelaboratory.com/fcfaq.html

[2] http://scscompa.com/MainWebPage/freeceln.htm (que se hizo a mano, asombrosamente)

Answer 2

Es interesante ver esta discusión aquí, que descubrí después de que la longitud de las soluciones haya sido discutida en hilos recientes (a partir del 6 de diciembre de 2012) en el Lista de correo fc-solve-discuss (que yo administro), así como algunas configuraciones que mejoraron el rendimiento de la longitud de la solución de Solucionador de Freecell , un solucionador para Freecell y otros solitarios (que yo mantengo).

Como otras personas señalan aquí, el Freecell Generalizado (donde el número de rangos aumenta más allá del 13º rango (Rey)) es NP-completo, pero el Freecell regular basado en As a Rey no lo es (aunque 13 sigue siendo un valor significativo para la complejidad NP a manejar) .

Una cuestión que nos ha resultado difícil de resolver es cómo medir el número de movimientos porque hay algunas variaciones para la poda "automatic-moves-of-cards-to-foundations" (ver también Mensaje de Danny A. Jones al respecto con algo de pseudocódigo ). Esto me llevó a redactar una especie de especificación para representación comúnmente acordada de una solución .

Bueno, volviendo al tema que nos ocupa, aquí tenemos algunos resultados de los solucionadores:

• Danny A. Jones resuelve (una de ellas rápida y algo subóptima, y otra lenta que se ejecuta en las primeras 1.500 operaciones).

• Resultados de mi solucionador subóptimo (pero de código abierto)

• Soluciones casi óptimas para los primeros 1.000.000 de ofertas en freecellgamesolutions.com - pero con una interfaz muy poco amigable que requiere habilitar JavaScript, rellenar Captchas y otros tipos de cosas desagradables.

Si quieres un análisis matemático de la longitud media de la solución sobre todo el conjunto de acuerdos posibles, entonces no conozco ninguno, y no estoy seguro de tener las habilidades matemáticas para hacerlo.

Saludos cordiales,

- Pez Shlomi