Loading ...
Sorry, an error occurred while loading the content.

Patsolve 3.0

Expand Messages
  • Tom Holroyd
    I ve just uploaded Patsolve version 3.0. You can find it here: http://members.tripod.com/professor_tom/archives/index.html
    Message 1 of 7 , Feb 26, 2002
    • 0 Attachment
      I've just uploaded Patsolve version 3.0. You can find it here:

      http://members.tripod.com/professor_tom/archives/index.html
      http://members.tripod.com/professor_tom/archives/patsolve-3.0.tgz

      (The archive contains a Windows command-line executable as well as the
      Unix source code.)

      Features of this release:

      * Completely redesigned memory system. Patsolve uses
      much less memory than before, and can be told how much
      memory to use through a command-line flag (-M).
      * New pile hashing and tree storage for positions. Positions
      are now stored in a forest of trees instead of a splay tree.
      The FNV hash is used for piles (not whole positions).
      * Speed mode. The -S flag causes Patsolve to find solutions
      as fast as possible, instead of looking for short solutions.
      About 35 games/second for Freecell on my workstation (over
      125,000/hr). Seahaven is even faster, about 150 games/sec.
      * Auto range solving. For example, "-N1 1001" will play the
      first 1000 games using the MS Freecell numbering.
      * Stubborn mode (-E) won't exit after finding the first
      solution; it will keep looking for even better solutions
      until you run out of memory.
      * Fully restartable (useful for inclusion in other programs).
      * All parameters were trained using a genetic algorithm, code
      for which is included (it's in Python). Performance has
      improved for both speed and quality over previous versions.

      Note that optimized parameters are included for only six variants:
      Freecell, Seahaven, Seahaven where only Kings can start a pile, and
      the speed mode versions of the above. Other modes (for example,
      variants with other than 4 free cells) will still work but the
      parameters may not be as optimal. Training new sets is possible but
      the GA takes a long (really long) time to run. The defaults should
      work pretty well but I haven't tested this much.

      Also, I'll be out of town for a week starting in a few minutes so I
      won't be able to respond to bug reports and other comments until next
      Wed. :-)

      Dr. Tom Holroyd
      "I am, as I said, inspired by the biological phenomena in which
      chemical forces are used in repetitious fashion to produce all
      kinds of weird effects (one of which is the author)."
      -- Richard Feynman, _There's Plenty of Room at the Bottom_
    • Shlomi Fish
      I had to fix the makefile to specify ./param.py instead of param.py. However, when I run make I get the following notice: # make ./param.py param.dat Traceback
      Message 2 of 7 , Feb 27, 2002
      • 0 Attachment
        I had to fix the makefile to specify ./param.py instead of param.py.
        However, when I run make I get the following notice:

        # make
        ./param.py param.dat
        Traceback (most recent call last):
        File "./param.py", line 4, in ?
        from util import *
        ImportError: No module named util
        make: *** [param.h] Error 1

        I am using Python 2.1.1-3mdk on a Mandrake Linux 8.1 system.

        Any help would be appreciated.

        Regards,

        Shlomi Fish


        --


        ----------------------------------------------------------------------
        Shlomi Fish shlomif@...
        Home Page: http://t2.technion.ac.il/~shlomif/
        Home E-mail: shlomif@...

        He who re-invents the wheel, understands much better how a wheel works.
      • Tom Holroyd
        ... Oh yeah, util is a module of mine that has some simple stuff for argument processing and so on. Perhaps I ll include it in future. But note that you don t
        Message 3 of 7 , Mar 5, 2002
        • 0 Attachment
          On Thu, 28 Feb 2002, Shlomi Fish wrote:

          > ImportError: No module named util

          Oh yeah, util is a module of mine that has some simple stuff for
          argument processing and so on. Perhaps I'll include it in future.
          But note that you don't need it unless you change param.dat. The
          distribution includes param.[ch] already. If the Makefile tries to
          recreate them, just do 'touch param.[ch]'.

          Tom
        • Shlomi Fish
          ... OK. But you may want to do the same, a priori to save the user some frustration. And you may wish to call it something like tomholroyd.util or anything
          Message 4 of 7 , Mar 6, 2002
          • 0 Attachment
            On Wed, 6 Mar 2002, Tom Holroyd wrote:

            > On Thu, 28 Feb 2002, Shlomi Fish wrote:
            >
            > > ImportError: No module named util
            >
            > Oh yeah, util is a module of mine that has some simple stuff for
            > argument processing and so on. Perhaps I'll include it in future.
            > But note that you don't need it unless you change param.dat. The
            > distribution includes param.[ch] already. If the Makefile tries to
            > recreate them, just do 'touch param.[ch]'.
            >

            OK. But you may want to do the same, a priori to save the user some
            frustration. And you may wish to call it something like "tomholroyd.util"
            or anything that will indicate it is your proprietary module.

            Regards,

            Shlomi Fish

            > Tom
            >
            >
            >
            > To unsubscribe from this group, send an email to:
            > fc-solve-discuss-unsubscribe@yahoogroups.com
            >
            >
            >
            > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
            >
            >

            --


            ----------------------------------------------------------------------
            Shlomi Fish shlomif@...
            Home Page: http://t2.technion.ac.il/~shlomif/
            Home E-mail: shlomif@...

            He who re-invents the wheel, understands much better how a wheel works.
          • WKRfresno@aol.com
            I doubt that I had much credibility when I wrote that my solver had done over one million games per hour last year. Now that yours runs near that magnitude
            Message 5 of 7 , Mar 6, 2002
            • 0 Attachment
              I doubt that I had much credibility when I wrote that my solver had done over one million games per hour last year. Now that yours runs near that magnitude people will start to believe it can be done. It'll be fun to see how much you can improve during the coming months. Mine runs on a single-processor Intel 733. What's yours?
              If you are using an Alpha (64 bits?), can the numbers be normalized to those run on other processors? Do you know how fast anyone else's solver is? Has anyone reported how fast your solver runs on their machine, and what their machine is?

              Damn. I don't know whether yours (of you) has an apostrophe.  Now I do, if the spell checker is reliable.

              Bill Raymond
            • Tom Holroyd
              ... Well, I m not really in that ballpark, but a factor of ten or so would get me there. That s not really so hard to imagine, in principle. I know for a
              Message 6 of 7 , Mar 6, 2002
              • 0 Attachment
                On Wed, 6 Mar 2002 WKRfresno@... wrote:

                > I doubt that I had much credibility when I wrote that my solver had done over
                > one million games per hour last year. Now that yours runs near that magnitude
                > people will start to believe it can be done.

                Well, I'm not really in that ballpark, but a factor of ten or so would
                get me there. That's not really so hard to imagine, in principle. I
                know for a fact that there are many places in my solver that could be
                sped up through relatively simple optimizations, but a factor of ten
                would be difficult without major architectural changes. The biggest
                thing is search order. My solver will always do single card moves and
                it'll always use a simple tree search with heuristics and no
                lookahead. You do multi-card moves and more in-depth analysis of the
                positions. Eliminating unlikely moves is a big win. Consider that
                when a human expert solves a game, he or she probably only considers
                roughly O(N) positions, where N is the number of moves in the game.
                That is, a good human player can go through a game without ever
                hitting undo, or only hitting it a few times. Even starting over
                doesn't increase the number of positions examined much. Right now I'm
                looking at maybe 2 or 3 _thousand_ positions. Getting down to 2 or 3
                _hundred_ would be in the ballpark of human ability, and at computer
                speeds, I don't doubt that 1e6 g/h is possible...

                > If you are using an Alpha (64 bits?), can the numbers be normalized to those
                > run on other processors?

                Well, I have a 666 MHz Alpha, but it's quad-issue, so it can execute 4
                instructions simultaneously, but not all possible combinations of
                instructions. So the real rate is variable, and these are also RISC
                instructions. That is, it's tough to compare with Intel. I don't
                have a lot of numbers for other processors. I welcome benchmarks
                using Patsolve's autoplay feature. time patsolve -fS -N0 1000. I get
                28 sec (user) = 35.7 g/s ~ 128,000 g/h. My 100 MHz Pentium laptop
                does it in 355 sec ~ 10,000 g/h. So the Alpha is 12.6 times as fast
                even though the clock rate is only 6.6 times as fast. This makes
                sense since it's an all-integer computation. You get higher rates
                with Alpha if you can mix floating point with integer -- this box has
                two FPUs and two integer ALUs.

                > Damn. I don't know whether yours (of you) has an apostrophe. Now I do, if
                > the spell checker is reliable.

                Your's is never correct. That'd be "your is".

                Dr. Tom Holroyd
                "I am, as I said, inspired by the biological phenomena in which
                chemical forces are used in repetitious fashion to produce all
                kinds of weird effects (one of which is the author)."
                -- Richard Feynman, _There's Plenty of Room at the Bottom_
              • Tom Holroyd
                ... Yeah. Or I should just include util.py, like I shoulda in the first place. The GA stuff is totally broken, too, but that s largely because I use a
                Message 7 of 7 , Mar 6, 2002
                • 0 Attachment
                  > > If the Makefile tries to recreate them, just do 'touch
                  > > param.[ch]'.
                  > >
                  >
                  > OK. But you may want to do the same, a priori to save the user some
                  > frustration.

                  Yeah. Or I should just include util.py, like I shoulda in the first
                  place. The GA stuff is totally broken, too, but that's largely
                  because I use a Numerical Recipes routine, and they don't like other
                  people to distribute that source (but you can get it if you buy their
                  book). I should just replace it with something else. Anyhow if you
                  want util.py just ask me, for now. I'll do an update in a while, and
                  fix both of these problems.

                  Tom
                Your message has been successfully submitted and would be delivered to recipients shortly.