next up previous
Next: Analysis of the Results: Up: Experiments: 60 Successive Tasks Previous: C-Code

Experimental Results for Both Task Sets

Within roughly 0.3 days, OOPS found and froze code solving all thirty $1^n2^n$-tasks. Thereafter, within 2-3 additional days, it also found a universal Hanoi solver. The latter does not call the $1^n2^n$ 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 $1^n2^n$ 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).

  1. For the $1^n2^n$-problem, within 480,000 time steps (less than a second), OOPS found nongeneral but working code for $n=1$: (defnp 2toD).

  2. At time $10^7$ (roughly 10 s) it had solved the 2nd instance by simply prolonging the previous code, using the old, unchanged start address $a_{last}$: (defnp 2toD grt c2 c2 endnp). So this code solves the first two instances.

  3. At time $10^8$ (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.

  4. At time $2.85*10^9$ (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).

  5. At time $3*10^9$ (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.

  6. Finally, at time $30,665,044,953$ (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 $a_{last}$, 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.

  7. The program above turns out to be a near-optimal universal $1^n2^n$-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 $1^n2^n$-tasks can profit from the solver of instance 6. Reusing this current program $q_{a_{last}:a_{frozen}}$ again and again, within very few additional time steps (roughly 20 milliseconds), by time $30,665,064,543$, OOPS had also solved the remaining 24 $1^n2^n$-tasks up to $n=30$.

  8. Then OOPS switched to the Hanoi problem. Almost immediately (less than 1 ms later), at time $30,665,064,995$, it had found the trivial code for $n=1$: (mvdsk).

  9. Much later, by time $260 *10^9$ (more than 1 day), it had found fresh yet somewhat bizarre code (new start address $a_{last}$) for $n=1,2$: (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.

  10. Finally, by time $541 *10^9$ (roughly 3 days), it had found fresh code (new $a_{last}$) for $n=1,2,3$:

    (c3 dec boostq defnp c4 calltp c3 c5 calltp endnp).

  11. The latter turns out to be a near-optimal universal Hanoi solver, and greatly profits from the code bias embodied by the earlier found $1^n2^n$-solver (see analysis in Section 6.6 below). Therefore, by time $679*10^9$, OOPS had solved the remaining 27 tasks for $n$ up to 30, reusing the same program $q_{a_{last}:a_{frozen}}$ 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 up previous
Next: Analysis of the Results: Up: Experiments: 60 Successive Tasks Previous: C-Code
Juergen Schmidhuber 2004-04-15

Back to OOPS main page