Detectar bucles en un reproductor de computadora en un juego de cartas

Question

Hace un tiempo, creé una pequeña aplicación web de juego de cartas para divertirme. El jugador juega contra la computadora y sobre todo funciona bien. A veces, aunque el jugador de la computadora entra en un bucle, el objetivo del juego es perder todas sus cartas y si no tiene una carta para jugar, tome la pila. A veces la computadora juega x, y, z, toma la pila, juega x, yz, toma la pila, etc.

Llevo un registro de los movimientos que he hecho, por lo que en cualquier punto tengo una matriz que se ve algo como: [C2, D5, H2, S4, C5, H2, S4, C5, H2, S4, C5]

En este caso puedo ver que me he metido en un bucle de jugar H2, S4 , C5, luego toma la pila y luego repite.

Entonces, el problema generalizado es, ¿cuál es la mejor manera de detectar patrones repetitivos en una lista? Probablemente podría encender algo usando un simple bucle for, tratando de encontrar la tarjeta que estoy a punto de jugar y si encuentro eso en la posición x entonces podría verificar si el patrón de x a n se repite en la posición x- (nx) a x, pero esto parece ser el tipo de problema que podría tener un buen algoritmo para ello. Cómo codificaría esto con la siguiente firma de función:

function findLoops(previousMoves, nextMove, maxPatternLength) { 
    //Return [loopLength, loopCount] or null if there are no loops 
} 

p.s. esto no es una tarea, existe el juego y está en http://www.idiot-cardgame.com si alguien está interesado :)

Answer 1

En primer lugar la cuestión general: Su método sugerido

tratando de encontrar la tarjeta que estoy a punto de jugar y si encuentro eso en la posición x, entonces podría verificar si el patrón de x a n se repite en la posición x- (nx) a x,

se ve muy bien. Yo sugeriría básicamente lo mismo. Es O (n) y necesita una cantidad fija de almacenamiento, y es simple: ¿qué más desearías?

Segundo: Puede verificar la repetición en los juegos en general si mantiene una tabla hash de todos los estados del juego anterior (estado completo, nada que quede fuera). Cada vez que alcanzas un estado nuevo, busca si está en la tabla hash, si está en ella: tu estado de juego está en bucle.

en JavaScript que haya orden interna hastables por lo que este es muy fácil de hacer con algo similar como esto:

new_state = next_move(old_state); 
new_encoded_state = encode(new_state); // make it into a string 
if (allstates[new_encoded_state]) { 
     // we are looping! 
} else { 
     allstates[new_encoded_state] = 1; 
     // no looping 
} 

La variable allstates no es una matriz, pero de tipo Object. Puede tener acceso tipo array con cadenas y esto usa el objeto como hastable.