Algoritmo de solitario “boca arriba”

Question

Estoy diseñando un programa para resolver juegos de solitario con la mayor puntuación posible.El juego se puntúa según el siguiente sistema de puntos:

10 points for moving Aces to top
9 points for moving 2s to top
8 points for moving 3s to top
7 points for moving 4s to top
6 points for moving 5s to top
5 points for moving 6s to top
4 points for moving 7s to top
3 points for moving 8s to top
2 points for moving 9s to top
1 points for moving 10s or face-cards to top
2 points for freeing a "downcard" (face-down card on the table)
2 points for moving a card from the deck to the table
-2 points deducted for moving a card from the top to the table
-20 points deducted for flipping over the deck
Putting a card back to the top after moving it from the top to the table does not give double points.

Las cartas del mazo se voltean una a la vez y los jugadores pueden voltear el mazo un número ilimitado de veces (sin embargo, la deducción de -20 puntos aún se aplica).

He encontrado varias guías de estrategia, como Guía de estrategia de Klondike para el juego de solitario de Windows, pero estas guías son para real Juegos de solitario donde no se conocen las cartas de la mesa.

Estoy buscando crear un algoritmo para resolver lo que yo llamo juegos de solitario "boca arriba" en los que tengo conocimiento del mazo antes de repartirlo. Editar: A partir de los artículos que figuran en las respuestas a continuación, parece que este juego se ha llamado "solitario reflexivo".

Hasta ahora, mis ideas han sido:una especie de fuerza bruta, donde se prueban y puntúan todos los movimientos posibles;un algoritmo simple que analiza cada columna individualmente e intenta el "mejor" movimiento posible;y finalmente una especie de algoritmo similar a la búsqueda de caminos, donde se puntúa cada movimiento y se encuentra el mejor "camino".

El problema con la fuerza bruta es que llevaría una eternidad (literalmente) ya que puedes repetir movimientos infinitamente.Con un algoritmo simple, no podía hacer cosas complicadas como reorganizar dos columnas para colocar todos los corazones y tréboles (por ejemplo) para liberar un solo 8 de corazones.Por lo que puedo ver, la búsqueda de caminos funcionará, pero no sé cómo funcionaría ese tipo de implementación.

Answer 1

Es posible que los siguientes artículos le resulten útiles (parece que un equipo de investigación ya lo hizo).

Búsqueda de solitario en tiempo real:

• http://web.engr.oregonstate.edu/~afern/papers / solitaire.pdf

Solitario: hombre contra máquina

• https://web.stanford.edu/~bvr/pubs/solitaire.pdf

Answer 2

Lo primero que probaría es un ingenuo algoritmo de anticipación de pasos fijos, donde en cada paso analizaría todos los posibles n pasos adelante y elegiría el que conduzca a la puntuación general más alta.

Juega con diferentes valores de n en la misma serie de paquetes pseudoaleatorios y vea cómo (si es que lo hacen) las puntuaciones mejoran al aumentarlas.

Si esto produce un éxito razonable, el siguiente paso es asignar puntos a determinadas posiciones que pueda utilizar durante el proceso de evaluación.(Por ejemplo, se puede restar la distancia de los ases 'con cartas boca abajo' desde la parte superior de su pila).

El siguiente paso podría ser una búsqueda adaptativa, en la que primero se mira hacia adelante un número fijo de pasos y luego se expanden aún más solo las hojas prometedoras del árbol de movimientos.(Poda, básicamente).

Y así sucesivamente, hay muchas cosas que puedes probar y suenan muy divertidas, así que disfrútalas.

Pero si todo lo demás falla, organiza un concurso de codificación.:)