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 brute-force 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.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||