Cálculo correcto de la probabilidad en el Buscaminas

Question

Cuando juego al Buscaminas, de vez en cuando llego a un punto en el que tengo que adivinar. Entonces intento calcular la probabilidad de que cada opción sea una mina para elegir el movimiento más seguro. Pero a veces me encuentro con que diferentes cálculos dan como resultado diferentes probabilidades, lo que significa que lo estoy haciendo mal en algún sentido, y esto es lo que quiero aclarar.

A continuación se presenta un ejemplo de este dilema. Fíjate en la marca verde de la zona superior izquierda. Tengo dos opciones junto a la marca 4, cada una con una probabilidad de $\frac{1}{2}$ .

Por otro lado, desde el punto de vista de los 5 puntos, tenemos que seleccionar 2 casillas de 3, lo que sugiere una $\frac{2}{3}$ probabilidad para cada casilla.

También podemos seguir un tercer cálculo, partiendo de la casilla 2 de la derecha de esta "isla" restante: si la casilla superior es una mina, se puede ver fácilmente que la casilla superior de la casilla 4 debe ser también una mina; si no, se puede demostrar que ambas casillas de la casilla 4 tienen la misma probabilidad de ser minas. Esto implica que el cuadrado superior de 4 marcas tiene una probabilidad de $\frac{3}{4}$ para ser una mina - de nuevo una contradicción.

Un intento más "desesperado" sería decir que las tres "trayectorias de cálculo" son igualmente probables, por lo que tenemos que sumar las probabilidades calculadas y sumarlas con un factor de $\frac{1}{3}$ . Pero eso es bastante incómodo, y estoy seguro de que hay un razonamiento más sólido aquí, pero no fui capaz de probarlo yo mismo.

Entonces... ¿cuál es la forma correcta de calcular la probabilidad?

Como última observación: asumo aquí que la isla restante es lo suficientemente grande como para que no se pueda extraer ninguna otra información significativa de los cuadrados restantes, como el número de minas restantes, o una enumeración directa de todas las posibles distribuciones de minas.

Gracias, y espero que lo encuentres tan intrigante como yo. :)

Answer 1

Obtienes diferentes probabilidades porque en cada caso sólo consideras una parte concreta del tablero, y por tanto en cada caso sólo consideras una parte estricta de toda la información que hay. Así que, realmente no hay ninguna contradicción aquí.

Si quiere saber cuál es la probabilidad dada la todo tablero, entonces sus cálculos serán más complicados. De hecho, tendrías que tener en cuenta incluso más que esas tres "trayectorias" que has mencionado... y si añades la información de que hay exactamente 10 minas más para colocar, se complica aún más.

Aun así, yo diría que tu tercera línea de razonamiento (que comienza con el 2 en la parte superior derecha de la región abierta) probablemente se acerca más a la probabilidad real, por las siguientes razones:

1. Tiene en cuenta la mayor cantidad de información (de hecho incluye la información relativa al cuadrado de 5).

2. Queda un buen espacio en la parte superior izquierda, por lo que se pueden empaquetar fácilmente diferentes números de minas allí, por lo que incluso saber que quedan 10 minas debería impactar/restringir mínimamente lo que podría pasar al lado de esas 2.

3. Las 3 banderas apiladas una encima de la otra junto al 5 tallan naturalmente el espacio en una "izquierda" y una "derecha", y no hay una línea directa de razonamiento en cuanto a cómo la satisfacción de los números de la izquierda repercutirá en lo que ocurre en la derecha.

Por lo tanto, el número de maneras de tener una mina directamente a la izquierda del 2 superior derecho debería estar muy cerca del número de maneras de tener una mina por debajo de eso ... lo que significa que estaría de acuerdo en que, incluso si se tiene en cuenta todo el tablero, la probabilidad de una mina en cada uno de esos cuadrados es de hecho alrededor de $1/2$ y con eso, la probabilidad de que el cuadrado superior junto al 4 sea una mina es efectivamente muy cercana a 3/4

En general, sin embargo, sí, tratar de tener en cuenta todo lo que es "humanamente posible" ... que en la mayoría de los casos es no considerando cuántas minas más hay. Pero el ejemplo que has puesto aquí sí que muestra cómo ciertas líneas de razonamiento tienen en cuenta más información que otras, y cuanta más información tienes en cuenta, más te acercas a la probabilidad si de alguna manera podría tomar en todo.

Answer 2

No hay una forma significativa de calcular estas probabilidades sin conocer el algoritmo que utiliza el buscaminas para generar el tablero. Entonces se calcularía la probabilidad de que, por ejemplo, la casilla superior contenga una mina como:

$$P(\text{Top square is mined})=\frac{P(\text{Algorithm would generate a compatible board with a mined top square})}{P(\text{Algorithm would generate a compatible board})}$$

Donde un tablero "compatible" significa una colocación de minas consistente con las pistas que ya tienes y las minas que ya has revelado.

Realmente no hay una forma más sencilla, ya que el algoritmo podría ser muy complicado para evitar generar tableros que sean aburridos de resolver. Podrías intentar resolver versiones de juguete del problema en las que el tablero se selecciona uniformemente, o en las que cada casilla se mina independientemente con probabilidad $p$ Lo que me imagino que llevaría a cálculos combinatorios bastante tediosos que implicarían calcular exactamente cuántas configuraciones de minas son consistentes con las pistas que ya tienes.

Answer 3

En primer lugar, yo etiquetaría los cuadrados. Imaginando que la zona verde es como una matriz, $M$ utilizan las mismas convenciones de indexación. Por lo tanto, $M_{4,2}, M_{3,2}, M_{1,2}$ y $M_{1,3}$ están en blanco. Ahora haz una lista de todas las posibilidades.

A continuación se enumeran las posibles formas en que podría haber minas en cada posición, teniendo en cuenta sólo la caja verde.

$M_{4,2}, M_{1,2}, M_{1,3}$

$M_{3,2}, M_{1,2}$

$M_{3,2}, M_{1,3}$

Por lo tanto, dada la caja hay una probabilidad de 1/3 de que haya una mina en $M_{4,2}$ y una probabilidad de 2/3 de que haya una mina en $M_{3,2}$ . Recogiendo $M_{4,2}$ sería mejor.

Answer 4

Para calcular la probabilidad hay que determinar primero todos los posiciones que las minas pueden colocarse para satisfacer correctamente toda la información conocida en todo el tablero.

Entonces, para cada posición es necesario calcular el valor de ' peso para la posición, es decir, de cuántas maneras se puede formar esta posición. Esto se hace, utilizando la combinatoria, calculando de cuántas maneras podrían colocarse las minas restantes (no utilizadas para satisfacer la información conocida) en el espacio restante (no junto a las fichas de información).

Entonces el número total de soluciones es la suma de los ' pesos '.

El probabilidad de una baldosa que contiene una mina es la suma de los pesos a través de la posiciones que tienen una mina en esa baldosa dividida por el número total de soluciones .

Se han realizado algunos trabajos en esta área y hay hilos que lo discuten en la página de reddit del buscaminas. Los mejores solucionadores automáticos utilizan variaciones optimizadas de este enfoque para ayudarles a tomar sus decisiones.