Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

Comment on

( #3333=superdoc: 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 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.

In reply to Re: CPU Boundries, Buffering, & Speed Discussion by Laurent_R
in thread CPU Boundries, Buffering, & Speed Discussion by jdlev

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • 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:
    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
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others surveying the Monastery: (6)
    As of 2018-06-23 20:56 GMT
    Find Nodes?
      Voting Booth?
      Should cpanminus be part of the standard Perl release?

      Results (125 votes). Check out past polls.