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/ )