Re: Algorithm for Optimising the Sequence of Quotas for the Switch Tasking
- 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
> 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
> (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
> 2. Calculate the results of assigning quotas for a variable @Quotas with
> @Quotas as calculated from Step #1, and the guessed @Quotas[2 .. $Inf] .
> Record it as the temporary optimal result.
> 3. Calculate a variables @Quotas 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
> 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.
> 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/ )