¿Existe un algoritmo óptimo para jugar Bejeweled?

Answer 1

Bejeweled se puede considerar como un juego en 2 pasos: en el primer paso haces algún movimiento, y en el segundo paso las piezas que fueron eliminadas por tu movimiento son reemplazadas. Este segundo paso puede considerarse como un turno de oponentes. Una vez que piensas en el juego de esta manera, se convierte en un ejemplo de un juego de suma cero. Otros ejemplos de juegos de suma cero incluyen ajedrez, damas y tic-tac-toe.

Las versiones de computadora de los juegos de suma cero a menudo usan “minimax” http://en.wikipedia.org/wiki/Min… para implementar jugadores de IA. Como dice Wikipedia, el objetivo es “minimizar la posible pérdida mientras se maximiza la ganancia potencial”. Esto se hace mirando todos los movimientos disponibles para obtener la mejor ganancia, luego mirando los movimientos de los oponentes para ver qué podría perderse en respuesta. Este proceso puede repetirse en turnos futuros mientras haya tiempo y memoria.

Ejemplo de ajedrez: la IA tiene la capacidad de tomar un peón o una torre. Con solo esta información, la IA gana más al tomar la torre, pero cuando la IA examina los turnos de los jugadores ve que si toma la torre, perderá a su reina, mientras que si solo toma el peón, nada sucederá. Ahora el mejor movimiento (ganancia potencial más pérdida potencial) es tomar el peón. Mirando un turno más allá, la IA puede ver si pierde a su reina por la torre que la IA ganará con un jaque mate. No es un mal movimiento después de todo.

De vuelta a Bejeweled. Durante el paso del jugador, el jugador puede ver todos los movimientos disponibles y elegir los que les darán más puntos para ese movimiento. Luego está el truco de calcular la respuesta de los oponentes, luego, para cada respuesta posible, el jugador puede calcular el mejor movimiento posible.

La parte difícil sobre la respuesta del “oponente” al rellenar el tablero es la desviación principal de juegos como el ajedrez, donde puedes asumir que tu oponente es inteligente. El tablero Bejeweled se llena (hasta donde yo sé) al azar, lo que significa que cualquier movimiento tiene la posibilidad de comenzar una cadena masiva que le otorgue al jugador una cantidad ridícula de puntos. Esta posibilidad es, sin embargo, muy pequeña. Existe una posibilidad mucho mayor de que si tiene dos piezas en una línea al lado del lugar donde caerán nuevas piezas, pueda obtener una cadena agrupada para obtener más puntos. Contra un jugador inteligente, la IA debe asumir que el jugador elegirá el mejor movimiento posible y usarlo para determinar cuál será su pérdida. Contra un oponente aleatorio, una suma de las probabilidades es mejor.

La otra pregunta que se me ocurrió cuando leí por primera vez esta pregunta es si Bejeweled, como Tetris http://arxiv.org/abs/cs.CC/0210020, es un problema en NP.

Answer 2

Según entiendo Bejeweled, hay un número finito de movimientos posibles en cada posición del tablero que determinan la siguiente posición del tablero. Sin embargo, hay una secuencia infinita de elementos de tablero desconocidos que se pueden agregar después de cada movimiento a medida que los cuadrados del tablero se vuelven claros.

Sostengo que no puedes jugar Bejeweled de manera óptima (sin conexión, es decir, sin un conocimiento avanzado de las entradas) por la siguiente razón:
Supongamos que usted afirma que conoce el movimiento óptimo en la posición p del tablero, que construí. Creo que puedo construir una secuencia de gemas próximas que haría más ventajoso hacer un movimiento diferente en la posición p de manera que el puntaje más alto posible en algún momento en el futuro, t, sea más alto con mi movimiento propuesto que con el tuyo . Una forma de hacer esto es crear una secuencia de las siguientes gemas que causarían una reacción en cadena de puntuación infinita solo si se elige mi movimiento original. Para probar esto matemáticamente, todo lo que tendría que hacer es encontrar uno de esos diseños de tablero donde pudiera causar una ganancia de punto infinito sin importar el movimiento que elija, para un movimiento diferente.

Una pregunta difícil de considerar es la siguiente: ¿se puede vincular la relación competitiva entre un algoritmo OPT, que se comportará de manera óptima en todo momento con conocimiento fuera de línea y un algoritmo en línea BVA (mejor algoritmo visible). Dejo esto a las personas con más tiempo que yo.

Answer 3

Esta podría ser la respuesta que estás buscando: ¡Candy Crush es (NP-) difícil!