Improve infinite loop detection

[kevinabrandon]

Currently the program detects infinite loops by counting the number of turns a game lasts. If a game has more than 20,000 turns, it declares it an infinite loop.
There are two problems with this method.

1. It is possible (although very unlikely), that a game can go beyond 20K turns.
2. Having the simulation spin for 20K moves is a big waste of time. If it could detect that the hand is going to repeat forever as soon as it begins repeating it would significantly speed up the program.

[kevinabrandon]

We could keep a copy of all previous hands. Then on each current hand we check it against all the previous. If any previous hands are exactly the same as our current hand, then we're in an infinite loop. This seems like it would get tedious and take a while on any long game ( > 1000 moves).

In the event of an infinite loop, does the game repeat in exactly 52 turns? If so, then we only need to keep track of the previous 52 hands, and only need to check against the single hand 52 moves previous.

I'm not so sure all loops repeat in exactly 52 turns. This needs to be investigated more.

[kevinabrandon]

So I've done some work on this problem in the improve-infinite-loop-detection branch.

The first thing that I noticed is that checking all the hands against a hand 52 turns previous will catch about 80% of the infinite loops. I played 100K games, and there were ~41K infinite loops. Of those 41K games, I was able to detect about 34K by checking hands against their 52-turn previous hand. The games that had infinite loops that weren't caught by this method, defaulted to the original method, which was to break after 20K turns.

I added a timer to see if this improves things and found that it does, but not by as much as I was hoping. Here are the results of the timers (all runs have 10K games).

Test	Time (seconds)
First a case with no infinite loops (the cards are shuffled between turns).	0.88 s
Case with infinite loops, simply breaking over 20K turns.	20.4 s
Case with infinite loops, checking the 52nd previous hand each turn.	45.4 s
Case with infinite loops, only start checking the 52nd previous hand each turn after a game has over 2K turns already.	32.1 s
Case with infinite loops, check the 52nd previous hand once every 1000 turns	15.5 s
Case with infinite loops, check the 52nd and 53rd previous hand once every 1000 turns	8.2 s

If I check each turn against the 52nd previous hand, I catch ~80% of all the infinite loops. If I only make that check every 1000 turns, then I only catch ~50% of all the infinite loops. If I check only every 1000 turns, I can get the 80% rate back by checking both the 52nd and the 53rd hand. This seems to be the best I can do for now.

Unfortunately the 20% of the infinite loops I miss are still severely slowing down the processing. However, I was able to cut the time in half.