Next: Analysis of the Results:
Up: Experiments: 60 Successive Tasks
Previous: C-Code
Within roughly 0.3 days, OOPS found and
froze code solving all thirty -tasks.
Thereafter, within 2-3 additional days, it also found a
universal Hanoi solver. The latter does not call the
solver as a subprogram (which would not make sense at all), but it
does profit from experience: it
begins with a rather short prefix that reshapes the distribution
on the possible suffixes, an thus reshapes the most likely directions
in the search space,
by temporally increasing the probabilities of
certain instructions of the earlier found solver.
This in turn happens to increase the probability of finding a Hanoi-solving suffix.
It is instructive to study the sequence of intermediate solutions.
In what follows we will transform integer sequences discovered
by OOPS back into readable programs
(compare instruction details in Section A).
- For the -problem,
within 480,000 time steps (less than a second), OOPS found
nongeneral but working code for : (defnp 2toD).
- At time (roughly 10 s) it had solved the 2nd instance
by simply prolonging the previous code, using the old, unchanged
start address : (defnp 2toD grt c2 c2 endnp).
So this code solves the first two instances.
- At time (roughly 1 min) it had solved the 3rd instance, again
through prolongation:
(defnp 2toD grt c2 c2 endnp boostq delD delD bsf 2toD).
Here instruction boostq greatly boosted
the probabilities of the subsequent instructions.
- At time
(less than 1 hour)
it had solved the 4th instance through prolongation:
(defnp 2toD grt c2 c2 endnp boostq delD delD bsf 2toD fromD delD delD delD fromD
bsf by2 bsf).
- At time (a few minutes later)
it had solved the 5th instance through prolongation:
(defnp 2toD grt c2 c2 endnp boostq delD delD bsf 2toD fromD delD delD delD fromD
bsf by2 bsf by2 fromD delD delD fromD cpnb bsf).
The code found so far was lengthy and unelegant. But it does solve the first
5 instances.
- Finally, at time
(roughly 0.3 days), OOPS had
created and tested a new, elegant, recursive
program (no prolongation of the previous one)
with a new increased start address
, solving all instances up to 6:
(defnp c1 calltp c2 endnp).
That is, it was cheaper to solve all instances up to 6 by discovering
and applying this new program to all instances so far, than just prolonging
the old code on instance 6 only.
- The program above turns out to be a near-optimal universal -problem solver.
On the stack, it
constructs a 1-argument procedure that returns nothing
if its input argument is 0,
otherwise calls the instruction 1toD whose code is 1, then calls
itself with a decremented input argument, then calls 2toD whose code is 2,
then returns.
That is, all remaining -tasks can profit from the solver of instance 6.
Reusing this current program
again and again,
within very few additional time steps (roughly 20 milliseconds),
by time
,
OOPS had also solved the remaining 24 -tasks up to .
- Then OOPS switched to the Hanoi problem.
Almost immediately (less than 1 ms later), at time
,
it had found the trivial code for :
(mvdsk).
- Much later, by time (more than 1 day),
it had found fresh yet somewhat bizarre
code (new start address ) for :
(c4 c3 cpn c4 by2 c3 by2 exec).
The long search time so far indicates that the
Hanoi-specific bias still is not very high.
- Finally, by time (roughly 3 days),
it had found fresh code (new ) for :
(c3 dec boostq defnp c4 calltp c3 c5 calltp endnp).
- The latter turns out to be a near-optimal
universal Hanoi solver, and greatly profits from the code bias embodied
by the earlier found -solver (see analysis in Section 6.6 below).
Therefore, by time ,
OOPS had solved the remaining 27 tasks for up to 30, reusing
the same program
again and again.
The entire 4-day search for solutions to all 60 tasks tested
93,994,568,009
prefixes corresponding to
345,450,362,522
instructions
costing
678,634,413,962
time steps.
Recall once more that
search time of an optimal searcher is a natural measure
of initial bias.
Clearly, most tested prefixes are short -- they either
halt or get interrupted soon.
Still, some programs do run for a long time; for example,
the run of the self-discovered universal Hanoi solver working
on instance 30 consumed 33 billion steps,
which is already 5 % of the total time.
The stack used by the iterative equivalent of
procedure Try for storage management (Section 4.1)
never held more than 20,000 elements though.
Note that the method is really quick in a quite pragmatic sense--it
finds an initially unknown program that solves all Hanoi
tasks up to 30 disks, such that the total search time plus
the total execution time is just 20 times the execution time
of the found near-optimal program on the 30 disk problem only.
Next: Analysis of the Results:
Up: Experiments: 60 Successive Tasks
Previous: C-Code
Juergen Schmidhuber
2004-04-15
Back to OOPS main page