Perl: the Markov chain saw  
PerlMonks 
Re: CPU Boundries, Buffering, & Speed Discussionby Laurent_R (Prior) 
on Sep 13, 2013 at 21:54 UTC ( #1054022=note: print w/ replies, xml )  Need Help?? 
I think that you have to think about strategies to prune the combinations early, in order to cut down drastically the work to be done. Sometimes it can be done, sometimes it can't. In February of this year, I was asked to analyze a game where an individual plays against a computer (or a smart phone). This game had 2^16 (65,536) possible starting positions, 46 possible moves each time and usually 5 moves, leading in theory to 1.35 x 10^13 possible games, each consisting of 1 to 5 moves. Not a quadrillion, but not that far either. A test on a small subset of the problem showed that a bruteforce approach would probably last about 5,400 hours on my computer (225 days). Besides I would run out of memory and possibly even disk space long before I could store all these possible games. But that would be mostly duplicate work. I made a backward analysis of the game: there is only one winning position, and only 46 moves can lead to this winning position, so that there are 46 positions one move away from winning the game. Each of these positions can in term be reached by 46 moves, and so on. That approach reduces the number of actual games to be potentially considered to 206 million, a much more manageable number. But it also turned out that many of the positions found at win minus two moves had already been found at win minus one move, so that if I was playing the game and found such a position, I would obviously choose the win in 1 move rather than win in 2 moves, so that all these non optimal strategies could be eliminated early, further reducing considerably the number of moves and positions to be examined. In the end my Perl program actually studied only 2,335,926 moves and lasted about 2 seconds. The program also proved that all possible initial positions can be solved in 5 moves or less. This problem was relatively easy to simplify, it is often much harder. But if you are talking about a quadrillion iterations, forget about throwing better hardware at it, try to find a powerful pruning strategy.
In Section
Seekers of Perl Wisdom

