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.

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.

Back to OOPS main page