« Jason Jacobs: Substitution Systems Design Process | Main | Alastair Hewitt: An Alternative Approach to Anticipative Reinforcement Learning »

Saturday, July 14, 2007


Adrian German

I was asked by one member of the audience during the presentation if the set of rules that I have chosen would work better than a random search. While I asked for a definition of "random search" another member of the audience said "randomly searching reveals eggs with a probability that is proportional with the area looked at". Both comments are quite meaningful but I would like to point out that there is danger in making assumptions without explicitly stating them, since we might end up speaking about different, distinct problems.

As an example, it should be clear that you're not allowed to sample the space without replacement: sampling the floor, the ground, is not like randomly drawing balls from a urn. If you remove part of the ground you won't have what to walk on. My solution does not suffer of this predicament: what the head of my Turing tape has visited can be safely eliminated, since the border is simply connected and allows you to reach any of the points not visited yet.

You also don't want to revisit places that you've searched before (in my case I can throw away the pieces of inside, once they no longer belong to the border). A random walk where steps in all directions are equally likely would not get very far very quickly and would be very redundant. My model extends like water on the table, in all directions, except I didn't get to show that.

Otherwise I just want to point out that my model paints (or marks) the space to avoid going back into territory that has been already searched. The only redundant movement is on the border, in search of replacement patterns. The space that is marked, or painted, can be removed since it is not needed after it becomes part of the inside. Only the border needs to be kept, that is. I think I may have said this already.

During my presentation I only showed the basic animation loop in the rewritten program; I have enumerated the rules and the basic topological restrictions. I have also, I hope, communicated clearly the basic idea, also the steps one would take if one were to apply NKS to this problem from here on, and that that was exactly what I did do back in 1993 when I produced these rules. Except then I searched through a space of rules "by hand" whereas much more could be done with an NKS approach. I am going to finish the implementation that I mentioned tonight and I will upload it tomorrow to the forum, and then I will post the link to it here. Thanks for your patience and interest.

Many thanks for allowing me to add this comment here after the talk and thanks for the summary as well.

Adrian German

With considerable delay (about 15 days, I guess) I have posted a notebook on the NKS forum (click on the link to be taken to my post which includes a link to the Mathematica notebook) with details of the implementation discussed during my presentation.

The direct link to the notebook:


Obviously, I'd be more than eager to answer any questions with respect to the approach I presented. Also I would be quite interested in any joint development of subsequent rule spaces and/or experiments with anyone interested.

Adrian German

A plain HTML version of my notebook:


This, for those who might not have Mathematica 6 just yet.

The comments to this entry are closed.