Questions about a Meta-Scan Construction Algorithm (for Single-Player Games)
Shlomi Fish
my name is Shlomi Fish and I'm the originator and lead developer of
Freecell Solver ( http://fc-solve.berlios.de/ ), an automated solver
for
several variants of cards solitaire.
Now, fc-solve is very configurable, and one can construct many
individual scans that will operate on the same state collection.
For any given board, one can usually find an individual scan that
will solve it quickly, but normally most scans will perform poorly
on some boards.
Furthermore, Freecell Solver has support for running several scans on
the same state collection by giving each scan a quota of iterations to
try and then interrupting it, and switching to a different scan. As a
result, I was able to construct meta-scans that comprise of several
individual scans which generally perform better than any individual
scan.
It was done by declaring a sequence of mapping of {$Scan_ID, $Quota}
($ indicates a variable a-la shell or Perl) which are ran for every
board that the solver attempts to solve. It tries $Scan_ID[$idx] for
$Quota[$idx] iterations, and then (in case it could not solve the
board
already) interrupts it, and switches to a different $Scan_ID[$idx+1]
for $Quota[$idx+1]. If the Scan_ID was already started, it will be
resumed from the position it reached, without restarting.
To construct such a sequence, which will have reasonable performance,
we
measured the performance of several individual scans across a range of
initial layouts (the first 32,000 Microsoft Freecell deals, in our
case) and
then used the following algorithm, which is greedy, but not optimal:
* http://www.shlomifish.org/lecture/Perl/Lightning/Opt-Multi-Task-in-PDL/
I'll describe it here:
{{{{{{{{{{{{{
1. Allocate a quota of iterations.
2. Chose the scan that solves the largest number of boards.
3. If no boards could be solved with any of the scans, increase the
quota by another quota.
4. Repeat steps 1-3 as long as there are unsolved boards.
}}}}}}}}}}}}}
Note that once a quota of iterations was allocated to an individual
scan, it will make progress with them in solving the board, and once
interrupted will take less time to solve the boards, after it is
resumed.
I've recently created a variation of this algorithm:
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/980
In this variation, instead of assigning the quota to the scan that
solves the most boards, it is assigned to the scan which generates the
minimal average solution length for the boards that it solves within
the
quota.
My questions are:
1. What is the name of this meta-scan generating algorithm? I'm asking
because I want to package the code I used to construct the meta-scan
and
distribute it as open-source software, and would like to use the right
terminology.
2. Are there documented algorithms for constructing such meta-scans
that
generally generate better results?
3. Assuming we want to use this algorithm, is are there any documented
ways to optimise the choice of the sequence of quotas' sizes so it
will
yield better results. For example, I can assign the algorithm the
sequence {300,300,300...} or {500,500,500,500...} or
{300,301,302,303,304...} or {300,500,300,500} etc. and it will yield
different results at any time.
------------------
I'll be grateful for anyone who can answer any of these questions.
Regards,
Shlomi Fish ( http://www.shlomifish.org/ )