Las probabilidades de ganar en el dragaminas con un juego perfecto

Question

¿Cómo podría alguien hacer esto? Supongamos que el primer "clic" nunca será una bomba, y que el número de minas y el área son ambos conocidos. Espero que haya una forma inteligente de hacer esto, pero no me sorprendería tanto si no la hay.

EDITAR: Asumiría (aunque sin ninguna prueba real) que se podría escribir un programa que pudiera resolver el dragaminas en tiempo lineal (a medida que el tablero se agranda linealmente, si la proporción minas/área se mantiene igual).

Me parece que en general no hay que considerar más de 9 bloques (el extremo superior de lo que he visto jugando al dragaminas en el experto) para determinar si

1. es una mina
2. es un cuadrado seguro
3. las probabilidades de que sea una mina

Eso apoyaría mi afirmación anterior.

EDITORIAL 2: Esto también parece contradecir el hecho de que el dragaminas es NP completo, y con probablemente no tanto trabajo uno (tal vez incluso yo, pero probablemente no) podría escribir un algoritmo que puede jugar un juego perfecto de dragaminas que tendría un tiempo de ejecución linealmente creciente que contradiría (verano de) el papel aquí . Así que supongo que esto plantea la siguiente pregunta que es: ¿dónde está el fallo en mi lógica?

EDITORIAL 3: Realmente estoy más interesado en las probabilidades que en el algoritmo para resolver el dragaminas. Y me ayudaría si alguien pudiera explicar por qué el número de comprobaciones/pruebas/cálculos que uno tiene que hacer no aumenta linealmente con respecto al área.

Answer 1

El documento " La precipitación de proteínas inducida por el ácido tricloroacético implica la asociación reversible de un intermediario estable parcialmente estructurado "(Rajalingam et al. 2009 Ciencia de las proteínas  18(5), 980-993.) puede ser relevante.

En la introducción, mencionan que la explicación convencional es que "el TCA obliga a la proteína a precipitarse secuestrando el agua ligada a la proteína" - es decir, puede forzar la precipitación de la proteína de una manera relacionada con los agentes caotrópicos o anticaotrópicos como el sulfato de amonio.

Sus experimentos indican una explicación más compleja. Su hipótesis es que el TCA cargado negativamente interrumpe las interacciones electrostáticas en la proteína, lo que da lugar a un estado parcialmente plegado que es propenso a la agregación. El hecho de que la precipitación del TCA sea menos eficaz en las proteínas intrínsecamente desordenadas apoya esta hipótesis (ya que no tienen un estado parcialmente desplegado propenso a la agregación).

La naturaleza ácida del TCA (el efecto del pH) ayuda a la velocidad de precipitación, pero no parece ser necesaria, ya que la sal de sodio del TCA es capaz de precipitar las proteínas en soluciones neutras, aunque más lentamente que el TCA ácido.

Answer 2

A veces hay que tener en cuenta algo más que los 8 bloques circundantes. Como ejercicio de IA computacional, se nos pidió que implementáramos un agente buscaminas.

En el límite entre las casillas resueltas y las no resueltas, se podría tener que considerar todas las combinaciones posibles de resuelto/no resuelto. Considere el siguiente ejemplo:

El límite consta de 15 casillas. Por lo tanto, hay $2^{15}$ posibles formas de distribuir las minas aquí. Sin embargo, los números de las casillas conocidas adyacentes al límite impondrán condiciones severas, por lo que tal vez sólo 10 de ellas sean compatibles con los números. Si el cuadrado x es una mina en sólo 1 de estos 10 casos, deberíamos suponer que es seguro, si la densidad de minas dada es mayor que una entre 10. O, mejor aún, el cuadrado x no es nunca una mina en ninguno de los casos posibles, y tenemos una apuesta segura. Sin embargo, hay ciertamente ejemplos en los que realmente SE NECESITA hacer este tipo de cálculos, (considerando el límite de los cuadrados resueltos) para hacer este tipo de cosas, y esto es exactamente lo que uno hace para demostrar que el buscaminas es NP-completo.

Ejemplo: Consideremos la serie #1#1#1# de cuadrados, donde # es desconocido. Cada dos incógnitas debe ser una mina, por lo que la probabilidad de que el primer y el último cuadrado desconocido no es independiente. El primero es una mina si el último es una mina. A partir de aquí, se pueden construir problemas que emulen a 3-SAT o similares.

Answer 3

Dejaría esto como comentario, pero no tengo la reputación. Esta es mi opinión, que es un poco diferente, pero no tanto, de los otros carteles.

Parte del problema es que elegir simplemente la casilla con la menor probabilidad de que haya una mina no siempre es una jugada perfecta. Después de cada clic, se suele tener nueva información sobre la posición de las minas, lo que ayuda al algoritmo. Una casilla con una baja probabilidad de que haya una mina, pero también una baja probabilidad de proporcionar nueva información, podría no ser tan buena elección como una casilla ligeramente más arriesgada que obtenga una gran cantidad de información. El algoritmo que diseñes tiene que tener en cuenta también el valor esperado de esa información (que a su vez depende del potencial de información en el nuevo estado, así como de su riesgo), y comparar de alguna manera las opciones basándose tanto en el contenido de información como en el riesgo. No hay, por lo que veo, una forma fácil de hacerlo.

Una forma de evitarlo, para un tamaño de tablero concreto, es crear una tabla con todas las posiciones posibles y hacer un preprocesamiento sobre ella. En la práctica, esto sólo te ahorra tiempo si quieres jugar MUCHAS partidas, e incluso entonces los requisitos de memoria son probablemente imposibles incluso para un tablero relativamente pequeño.

Answer 4

Me considero un jugador experto. He analizado muchas veces las posiciones finales ambiguas del tablero y, aunque un número deprimente de ellas tiene unas probabilidades terribles (50/50 o peor), hay algunas en las que una o dos de las casillas cubiertas tienen muy buenas probabilidades (más del 90% de posibilidades de no tener mina). Está claro que lo óptimo es hacer clic primero en estas casillas (a pesar de la afirmación de que una casilla "más arriesgada" podría dar más información). Por suerte para nosotros, la versión de Windows 7 del Buscaminas lleva un registro de las estadísticas de victorias. Asumiendo que sólo fallo partidas ganables un pequeño porcentaje de las veces (quizás un 2-3%), puedes considerar mi porcentaje de victorias a largo plazo como una estimación de la capacidad de ganar del Buscaminas Experto. Mi porcentaje de victorias a largo plazo ronda el 32%, o algo menos de un tercio de todas las partidas. Me sorprendería que el porcentaje real fuera superior al 35%. Aunque mi récord actual sólo se basa en 190 partidas, he jugado muchas veces este número en múltiples ordenadores desde Windows 3, cuando conocí el juego (sí, son más de 2 décadas de Buscaminas).

Aunque uno de los carteles afirma que sólo obtiene un 20% en experto utilizando un programa, yo deduciría que el algoritmo utilizado es inferior y no emplea la lógica suficiente para deducir las casillas seguras en ciertas condiciones complejas. Me he encontrado con estados del tablero en los que hay que considerar una cadena o ciclo de docenas de cuadrados juntos para descubrir que sólo hay una solución lógicamente consistente. Estos tienden a ser bastante raros, pero resolverlos correctamente es esencial para determinar la verdadera tasa de ganabilidad.

Si excluimos las partidas que terminan en ambigüedad y quedan menos de, digamos, 5 bombas, entonces diría que la tasa de ganabilidad sube significativamente... a tal vez 2/3 o así. Realmente preferiría que el juego detectara la ambigüedad y te diera una oportunidad gratis cada vez, o simplemente te diera un número fijo de intentos malos en cada partida (la versión de Windows 8 tiene un modo que hace esto). Con, digamos, 4 aciertos gratuitos, diría que más del 99% de las partidas serían ganables.

Para ello, otra pregunta interesante es: ¿cuántos aciertos gratuitos serían necesarios para que el 100% de las partidas fueran ganables?

Answer 5

Después de haber jugado al Buscaminas de forma intermitente desde que Win 95 era joven, estoy convencido de que el juego hace trampas hoy en día. Antes de Win Vista podías ocasionalmente (tal vez una de cada 20 intentos) conseguir un comienzo muy prometedor simplemente haciendo clic tres o cuatro veces antes de empezar a resolver el tablero en serio, despejando así áreas muy grandes casi al instante. Pero hoy en día las minas están más bien repartidas por todo el tablero. He observado tres cambios que afectan al juego actualmente:

1 Nunca encontrarás una tabla fácil. 2 Sin embargo, rara vez se encontrará con un tablero realmente imposible. 3 Ya no puedes esperar despejar el tablero en ningún sitio tan rápido como podías hacerlo antes de Vista. (Mi mejor puntuación real (es decir, sin mirar/reiniciar) con Win 7 es de 172 s, mi mejor puntuación con Win XP era de 84 s. Y no, no tengo pruebas para respaldar esa afirmación. Mi gato "apagó" ese ordenador para siempre).

Sí, (casi) siempre habrá al menos uno o dos aciertos 50/50, normalmente cuando se tienen uno o más conjuntos de dos minas en un cuadrado 2x2. Pero rara vez encontrarás más de media docena de situaciones de este tipo a la vez. Realmente pensaba que esto era siempre así, pero después de jugar unos 2500 tableros, me encontré con uno que no requería ninguna conjetura en absoluto. Por supuesto, es muy probable que haya pasado por alto otras antes de eso, al activar una mina por error. Al fin y al cabo, siempre voy a jugar rápido.

De todas formas, resultados aparte, lo que quiero proponer es que la lógica detrás de la configuración de las minas, desde Win Vista ya no es aleatoria. Además, puede ser deliberadamente sesgada para crear aquellas situaciones que no se pueden resolver sin adivinar. Usted probablemente puede averiguar cómo y si esto afecta a sus discusiones.