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

Re: Algorithm for Optimising the Sequence of Quotas for the Switch Tasking

Expand Messages
  • Shlomi Fish
    Hi all. This is a report on my progress. ... An Israeli joke tells that once a certain Israeli politician got a puzzle game with 6 pieces. He locked himself in
    Message 1 of 2 , Dec 27, 2009
      Hi all.

      This is a report on my progress.

      On Thursday 24 Dec 2009 20:24:14 Shlomi Fish wrote:
      > The original algorithm for generating a meta-scan (see http://xrl.us/beuigz
      > ) is:
      >
      > {{{{
      > # First we record the number of iterations (= states scanned) it took the
      > scans' to solve a given board for each of a large set of boards. (in our
      > case the Microsoft 32,000).
      > # Then, we allocate a certain number of iterations, and assign this quota
      > to the scan that solves the most boards within this quota.
      > # Repeat.
      > }}}}
      >
      > So if we have @Quotas = [350, 500, 600, 200...] we will assign 350
      > iterations to the first scan, and then 500 to the second one and then 600
      > to the third one, 200 to the fourh, etc.
      >
      > Question is: what is the optimal @Quotas-as-a-function-of-$quota_index
      > allocation?
      >
      > For a long time, I couldn't really think of a good way to do that, but
      > recently, after experimenting with a more specific problem, I came up with
      > this method:
      >
      > 1. Calculate the results of assigning quotas when picking up @Quotas[0]
      > (where the first scan is 0) from a range of iterations (say anywhere from
      > 100 to 1,000) where Quotas[1 .. $Inf] is being guessed (to say
      > [350,350,350...] till infinity). Record it as the temporary optimal
      > result.
      >
      > 2. Calculate the results of assigning quotas for a variable @Quotas[1] with
      > @Quotas[0] as calculated from Step #1, and the guessed @Quotas[2 .. $Inf] .
      > Record it as the temporary optimal result.
      >
      > 3. Calculate a variables @Quotas[2] based on @Quotas[0,1] and the guesses.
      >
      > And so forth.
      >

      An Israeli joke tells that once a certain Israeli politician got a puzzle game
      with 6 pieces. He locked himself in his office trying to solve it. Two years
      later, he comes out in complete disarray, and says "Ha! It says on the box
      '3-5 years [old]' and I solved it in two!". In a way, that's how it's been
      with me for some time since I wrote the previous message.

      What happened was that I implemented the algorithm in Perl 5 based on the code
      that I wrote previously, and it was too slow. As a result, I sought a faster
      language to implement it. After contemplating writing it in C which I knew
      very well, I finally decided to try implementing it in C#/.NET (using Mono -
      http://www.mono-project.com/ ), and spent quite a few hours on getting all the
      code to run there. At the end of the day, it worked and ran much faster than
      the Perl program, and the algorithm finished.

      The results were that it yielded a solution in 18,150,636 iterations (which
      has been verified using the existing Perl code) instead of in 18,382,968 ,
      which is what you get with constant quotas of 350. I noticed and verified that
      the algorithm yielded monotonically decreasing results.

      That was all nice and dandy, but when I fed the resultant meta-scan into the
      solver it ran slightly slower than "-l cool-jives". Moreover, as I noticed it
      resulted in a different number of iterations than what the meta-scan-
      generating algorithm yielded as an estimate.

      I tried using both --scans-synergy's and to increment the quotas by 1 in case
      there's an off-by-one error, but while some of them improved the final
      iterations count, they did not result in the same iterations numbers.
      Therefore, I now need to investigate why the result is different by simulating
      the scans and seeing where fc-solve deviates from that.

      So that's how far I got for now.

      Here's a blog post I wrote about C# in regards to the porting of the Perl
      code:

      http://community.livejournal.com/shlomif_tech/40163.html

      Regards,

      Shlomi Fish

      > This will yield @Temp_Optimal_Quotas[0 .. $Num_Quotas] that we can use as a
      > better starting point.
      >
      > After that I've been thinking that we can repeat this algorithm only this
      > time while using @Temp_Optimal_Quotas as the guessed iterations (and so
      > forth until we become saturated).
      >
      > It's not a very time-efficient method, and I'm not sure it guarantees good
      > results, but it should be easy to code, and so I'd like to see if it works,
      > and how well it improves upon the existing heuristics.
      >
      > Regards,
      >
      > Shlomi Fish
      >

      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      My Aphorisms - http://www.shlomifish.org/humour.html

      Bzr is slower than Subversion in combination with Sourceforge.
      ( By: http://dazjorz.com/ )
    Your message has been successfully submitted and would be delivered to recipients shortly.