Detection of loops in a computer player in a card game

Question

Some time ago, I created a small web application for a card game for fun. The player plays against the computer, and basically it works great. Sometimes, although a computer player gets into a cycle, the point of the game is to lose all your cards, and if you do not have a card to play, you take a bunch. Sometimes the computer plays x, y, z, takes a bunch, plays x, yz, takes a bunch, etc.

I keep track of the steps I took, so anytime I have an array that looks something like this: [C2, D5, H2, S4, C5, H2, S4, C5, H2, S4, C5 ]

In this case, I see that I got into the cycle of the game H2, S4, C5, then took a bunch, and then repeated.

So, the generalized problem is, what is the best way to detect duplicate patterns in a list? Perhaps I could whip something using a simple loop, trying to find the card I'm going to play, and if I find this at position x, then I could check if the pattern from x to n is repeated in position x- ( nx) to x, but this seems like a problem that might have a good algorithm for it. How would you encode this with the following function signature:

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

ps this is not homework, the game exists and is located at http://www.idiot-cardgame.com , if anyone is interested :)

Answer 1

General question first: your suggested method

trying to find the card I'm going to play, and if I find it at position x, then I could check if the pattern from x to n is repeated at position x- (nx) to x,

looks really good. I would suggest basically the same thing. It is O (n) and requires a fixed amount of memory and is simple: what else would you like to do?

Second: you can check the repetition in games, as a rule, if you keep a hash table of all the previous states of the game (full state, nothing remains). Every time you reach a new state, see if it is in the hash table, if it is in it: your game state is looping.

In Javascript, you have built in hastables, so it is very easy to do with something similar like this:

  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 } 

The variable allstates is not an array, but an Object type. You can have an array as access with strings, and this uses the object as hastable.