14 votos

¿Existe una estrategia ganadora para No rompas el hielo?

No rompa el hielo es un juego de niños en el que los jugadores se turnan utilizando mazos para golpear trozos de hielo fuera del campo de juego. El campo de juego se compone de una cuadrícula (6 x 6) de bloques cuadrados simples, excepto el bloque de 2x2 en el que se encuentra el oso patinador.

playfield

El objetivo del juego es no romper el hielo y que el oso se caiga.

¿Hay una estrategia ganadora? Si es así, ¿para qué jugador? Supuestos:

  • Cada jugador sólo elimina un bloque de su elección.
  • Los bloques son "pegajosos" y se adhieren entre sí a lo largo de cualquier borde, y así:
  • El juego termina cuando el cuadrado central de 2x2 ha sido desconectado del exterior del cuadrado de 6x6; es decir, cuando no hay un camino ortogonal (conectado a lo largo de los bordes) desde cualquier celda fuera del cuadrado de 6x6 a una celda en el interior del 2x2 central.

7voto

Si entiendo bien el juego, debería haber una estrategia ganadora para el jugador que va último. Si primero no tenemos en cuenta las esquinas, entonces el oso caerá cuando se elimine el penúltimo bloque:

--X---
--X---
--BB--
--BB--
------
------

(o similar) Como el número de bloques es par, este bloque será eliminado por el jugador que vaya primero. Ahora, hay dos complicaciones. Primero, el último bloque eliminado puede incluir la esquina:

-X----
-X----
-XBB--
--BB--
------
------

o

-X----
-XX---
--BB--
--BB--
------
------

Como el número de bloques restantes es ahora impar, el jugador que vaya en último lugar perderá. En segundo lugar, un bloque puede caer por estar desconectado. Como señala Steven, sólo pueden caer cuatro bloques de esta manera. Si cae un número impar de bloques, entonces el jugador que va último será el que haga el último movimiento en la primera configuración.

Sin embargo, ambos pueden evitarse fácilmente atacando primero los bloques de las esquinas. Como se necesitan dos movimientos para eliminar un bloque de esquina, el segundo jugador siempre puede eliminar el bloque de esquina antes de que el primero pueda hacerlo caer, y por supuesto antes de que se eliminen todos los bloques laterales. Esto asegura que la posición final será del primer tipo, y por tanto que el jugador que va primero pierde.

3voto

M. Dave Auayan Puntos 324

Algunas notas:

  • No tiene mucho sentido molestarse en eliminar bloques en las condiciones especificadas para la versión simplificada; las únicas celdas que pueden eliminarse al quedar aisladas son las cuatro celdas adyacentes en diagonal (pero no en horizontal) al bloque central. Todas las celdas del anillo exterior de 6x6 están, por supuesto, siempre conectadas, y todas las demás, excepto esas cuatro celdas, están conectadas al bloque interior de 2x2.
  • Las cuatro casillas de las esquinas exteriores del tablero pueden ignorarse a efectos de conectividad; no hay ningún camino a través de ellas que no toque también otro borde del tablero. Por lo tanto, sirven efectivamente como movimientos de "paso", un movimiento que puede ser tomado sin afectar al tablero de manera significativa. Además, como el juego es simétrico, si un jugador tiene la ventaja estratégica de pasar, también la tiene el otro; por lo tanto, un pase siempre debe ir seguido de otro pase. Como los pases vienen en pares (4 en total), tampoco tienen un efecto significativo en el juego y pueden ser ignorados al calcular el resultado del juego; es mejor dejar esas casillas vacías desde el principio.
  • Estas simplificaciones (junto con un montón de tablas de transposición) ponen el juego en un rango eminentemente analizable. Como las 4 casillas centrales no pueden ser eliminadas y las 4 casillas de las esquinas exteriores no importan, hay efectivamente 28 casillas cuyo estado puede cambiar significativamente; esto significa que el juego tiene 2 28 posiciones en total. Son sólo 256 millones de posiciones, y como se puede almacenar el valor de una posición en un solo bit, se podría guardar la "tabla de verdad" completa (esta posición es ganadora o perdedora) en sólo 32 megabytes. Si quieres ser extravagante, puedes incluso añadir un bit adicional que indique si la posición está "ya perdida" (es decir, si está conectada o desconectada), duplicando tu almacenamiento pero facilitando un poco las cosas.
  • Además, la construcción de esa tabla de verdad es sencilla; la posición con 0 bits encendidos es imposible, por lo que su valor no importa. Todas las posiciones con un bit encendido se pierden para quien acaba de llegar a ellas. A partir de ellas, se puede calcular el valor de todas las posiciones con dos bits activados (o, más sencillamente, rellenar las que no se pierden: las ocho posiciones con una celda "interior" y una celda "exterior" adyacente). A partir de ellas, se puede calcular el valor de todas las posiciones de tres bits, etc. Esto no llevaría más de un día de escritura y probablemente menos de 5 o 10 minutos de ejecución en cualquier máquina moderna decentemente potente, suponiendo que los algoritmos estén bien hechos.

Si hay suficiente interés, puedo intentar reunir algo para encontrar el valor final, pero me llevará uno o dos días; también es eminentemente posible que se pueda resolver con un rápido análisis de casos, ya que el 90% de la conectividad parece una "pista falsa" y (aparte de las celdas de la "esquina interior") el problema es casi totalmente una cuestión de eliminar una celda interior o tanto las celdas adyacentes exteriores como las adyacentes de la esquina interior. Debería poder analizarse como la suma de cuatro "minijuegos", uno por cada una de las cuatro esquinas del tablero (pero cuidado, en el lenguaje estándar el juego es misere y no normal, por lo que no se le pueden aplicar las sumas normales de nim).

2voto

Sevki Puntos 116

En teoría, una estrategia óptima, en el sentido de una Equilibrio de Nash Sin duda, debe existir. Sin embargo, basándonos en la descripción del juego en Wikipedia Pero veo algunas dificultades para encontrar una estrategia de este tipo en la práctica.

En primer lugar, parece que el juego no es determinista, por lo que la estrategia óptima sólo puede serlo en un sentido estadístico: no puede garantizar la victoria de ningún jugador. En segundo lugar, los resultados de las distintas jugadas parecen depender de las propiedades físicas de los bloques, lo que significa que para calcular la estrategia óptima habría que desarrollar primero un modelo preciso de la física del juego y luego ajustar el modelo a las mediciones reales.

(Esto no es completamente imposible: por ejemplo, se ha hecho para Pasar los cerdos pero ese es un ejemplo más sencillo, ya que los cerdos de Pass the Pigs no interactúan mucho entre sí. En ese sentido, Don't Break the Ice parece más cercano a, por ejemplo, Jenga .)

Por último, no estoy seguro de la consistencia de las propiedades físicas de las piezas de juego, ni de la probabilidad de que cambien con el tiempo debido a la edad o al desgaste. Si el comportamiento de las piezas varía demasiado, una estrategia calculada para un juego concreto puede no ser óptima para otro.

Dicho esto, sin embargo, todavía podría ser posible llegar a una aproximación determinista (o al menos consistentemente no determinista) del juego, y luego analizar esa aproximación. Sin embargo, no estoy lo suficientemente familiarizado con el juego en cuestión como para sugerir cómo podría ser esa aproximación, excepto por algunas características muy crudas (por ejemplo, que desconectar completamente el centro de los bordes del campo de juego debería ser seguramente una jugada perdedora).

-1voto

Franck Dernoncourt Puntos 1280

Dada la física, parecería que los bloques no serían pegajosos, pero aún así se puede predecir cuándo caerán. Los bloques se quedarán si están entre (con una línea de bloques sin romper) dos bloques que ya están confirmados para quedarse arriba (contando el borde)

Por ejemplo, tomemos este tablero.

----
--x-
---x
----

Los otros dos bloques de "esquina" junto a las X también caerían, ya que no están apoyados.

----
--xx
--xx
----

Sin embargo, el resto de los bloques se mantendrían. El resto del tablero se mantendría debido a la compresión con los bordes del tablero.

----
--xx
--xx
x---

Este bloque se ha roto, ahora. Sin embargo, nada más caerá. Voy a marcar los bloques estables con una "s". Estos bloques son estables porque se mantienen unidos por los bordes:

ssss
-sxx
-sxx
xs--

El resto de los bloques también se van a quedar porque se mantienen entre los bordes y otros bloques estables.

Sin embargo, sigue habiendo una estrategia ganadora bastante sencilla. Romper siempre el bloque de hielo a 180 grados de lo que jugó el primer jugador. El tablero siempre permanecerá simétrico, y eventualmente llegarás a un escenario como este.

xx-xxx
xx-xxx
xxBBxx
xxBBxx
xxx-xx
xxx-xx

Su oponente se verá obligado a romper una de estas cadenas, haciendo así que el centro caiga.

Nunca se puede perder al hacer esto debido a la simetría. La baldosa central sólo caerá si no está apoyada ni vertical ni horizontalmente. Si rompes una de las baldosas que sostienen el centro (aquí mostradas como baldosas S)

--SS--
--SS--
SSBBSS
SSBBSS
--SS--
--SS--

siempre romperías un lado en el mismo eje que tu oponente. No romperás la estabilidad en ningún eje porque tu oponente lo hará primero.

xxxSxx
xxxSxx
--BB--
--BB--
xxSxxx
xxSxxx

Si tu oponente rompe alguna de las fichas S, no habrá ninguna fuerza útil en sentido vertical.

xxxxxx
xxxxxx
--BB--
--BB--
xx-xxx
xx-xxx

Las dos baldosas inferiores no están proporcionando ninguna estabilidad al centro porque esta estabilidad sólo proviene de la compresión, y el otro lado de esa compresión está roto. Esto significa que cuando se eliminan las dos inferiores, no se está haciendo que el centro sea menos estable.

Sin embargo, conocer esta estrategia no significa que siempre vayas a ganar. Tienes que ser siempre capaz de derribar sólo el/los bloqueos que quieras (lo cual es habilidad, no estrategia). Tampoco he descubierto qué hacer si vas primero y tu oponente comete un error.

JugonesTop.com

Jugonestop es una comunidad para amantes del gaming. Puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X