Table of Contents
1. Working Research Notes (Work in Progress) 🔗
The following can be seen as addendum to Project Outline v1 and requires reading of it fist. It consists mostly of stitched together research notes with minimal annotation. It might be helpful to give a very rough overview on what we are currently working on.
This page acts as a snapshot and will not neccesairly be updated in the future. See Research Session Notepad and Research Session Log for a more extensive cronological record of research activity. Note that these documents are not optimized at all for being comprehensible to people outside the project. They may only serve as a costly signal of dedication.
Last update:
1.1. The Next Concrete Research Steps 🔗
In order to make progress on finding the algorithms of intelligence we need to create environments that allow efficient exploration of algorithmic ideas.
E.g. You are a roboticist developing an algorithm that controls a robot arm to grab something. It is useful to have a pysics simulation of an environment with a robot arm, that you can run your algorithm on, see how it fails and based on your observation change your code.
Such an environment can make the design process more efficient by enabiling a tight feedback-iteration loop.
1.2. Science Games 🔗
A science game is a benchmark evaluating an algorithms world modeling capability.
1.2.1. Explanation via Example 🔗
You sit infront of a computer. I will randomly choose a game, that you don't know, from steam for you to play. You now have 3 hours to get good at the game. I will now select a random goal. Your need to reach that goal as fast as possible. Then I randomly select another another game and we repeat.
Example games and world states:
- Counterstrike: Backstab two people in a row with a knive
- Replicube: Make a hollow sphere
- Supreme Commander: Beat a Medium AI using the fewest number of units possible.
- Intravenous 2: Beat a level without killing anyone.
- From the Depths: Make a ship that can beat the Megoladon unit at 75% the cost.
- AdVenture Capitalist: Make it such that you have the least ammount of money afer 1 hour with the constraint that you need to buy something at most 10 seconds after you are in the state where you can buy anything.
- Noita: Create a wand that damages yourself as much as possible.
- FTL: Beat the game using only boarding.
- Into the Breach: Win the game using a squad that has the same mech 3 times.
So the overal structure of the science game is:
- You are given an unknown game.
- You build a model of the game world.
- Achive a particular previously unknown goal as fast as possible.
- Goto step 1.
1.2.2. As an AI Benchmark 🔗
Building models of a world that allow you to efficiently steer the world into particluar states is a core bottleneck to understanding intelligence.
In order to play the science game well you need to be good at creating a model of an unknown world.
1.2.3. Procedurally Generated Games 🔗
For developing AI algorithms it seems useful to be able to quickly procedurally generate games. In particular the interface that allows the AI to interact with the game needs to be generated.
Writing interfaces for many steam games is impractical.
1.2.3.1. Generating cellurar automata 🔗
- The system generates a random cellular automata ruleset, including a cartesian interface for manipulating the cellular automata grid. Things that can be sampled:
- number of colors
- dimensionality
- neighborhood
- update rules
- What actions are available to manipulate the cell grid.
- E.g. "you can set the value of one cell at every timestep".
- Investigation
- The algorithm is given a simulator of the environment.
- The system also has additional powers not available in the final evaluation, such as setting arbitrary cells in the current cellular automata grid.
- The system randomly chooses an intial, and a target cell configurations.
- The algorithm get's as input the initial and target cell configurations, and needs to produce a sequence of actions that make the target state appear as quickly as possible.
- Goto step 1.
1.3. Cellular Automata as Environments 🔗
Cellular automata seem like a testing ground for world modeling algorithms. They hardcode the assumption of symetry (the laws of physics are the same throughout space), and locality (an object can only be influenced by it's immediate surroundings). Reality also has these properties. If we can make our environment simpler to solve by making more like reality, it seems like we should.
Cellular automata have many useful properties for investigation:
- It's easy to sample random rulesets.
- They are easy to implement.
We can easily create a science game from a randomly sampled cellular automata like described previously.
However, randomly sampled automata mostly exhibit very repetitive boring behavior. In the following the describe a type of automata that does not have this problem, while being closer to reality. It introduces something very roughly equivalent to conservation of energy.
1.4. Particle-Distributing Cellular Automata 🔗
The following is a cellular automata with a special ruleset (it's still randomly sampled).
Each color in the cellular automata has a value. Therefore each cell has a value (depending on it's color). In tern we can define the value of the world to be the sum of all the cells values. The local update rules of this cellular automaton are such that the value of the input world state, always must equal value of the output world state.1
This works by modeling each cell as containing 
particles, where 
is the value of the cell. (Note that when speak of cell color we are really talking about a particular cell value. We simply assign every possible cell value a color to be able to create more intuitive visualisations.) All an update rule can do is to move the particles of the "center cell" in a pattern that also matches the center cell's neighbors.
(In the actual implementation we don't model particles as objects. Each cell simply has a natural number associated with it. When we generate rules we constrain them though such that there can be no rule that creates or destroys particles.)
Just like with normal cellular automata only one rule matches for any contiguous segment of 3 cells in the current state. and can move the particles of a cell per tick, the total quantity of particles is neccesairly preserved.
Note that this conservation law implies that if there is nothing, then we will again get nothing, i.e. it implies that there are inert background cells, that just stay whatever color they where.
So cells with value 0 will always be background cells (though it is possible for other cell values to behave similarly to a background).
Note how in the above automata we can immediatly see a glider like analog in 1D. This construction moves much slower than the "speed of light". The speed of light as in the maximum speed that anything can travel is one cell here. Because we can
Beams of a single color that shoot of to the side seem common in random automata, but intuitively such glider like constructions are usually rare. However, based on randomly generating a few random rulesets they seem to be much more common in cell conserving cellular automata.
Generating the rules is actually very fast. It takes maybe 5 seconds for 15 colors (and the generating code is not optimized at all, it does a lot of redundant stuff). That is sort of crazy in that sampling normal cellular automata in the same way would be completely intractable. I can literally generate all rulesets for 15 colors. But I think even for 6 colors there are many more than "atoms in the universe" number of rulesets for normal cellular automata.
Every rule is of the form [[a b c] [x y z]]. All variables are natural numbers. The a b c match to the state (determine what rule to apply to a particular region). The x y z say how to distribute the particles of b for the next timestep. It must hold that:
(= (+ x y z) b)
for every rule. This enforces that the overall number of particles must stay the same.
1.4.0.1. Looking at some randomly Sampled Automata 🔗
:Claim: Randomly sampling normal cellular automata yields mostly very simple trajectories with no interesting structure.
:Question: Have particle-distributing cellular automata the same property?
In the following we analyse randomly sampled Particle-Distributing Cellular Automata cellular automata.
In the following images have the cell values be one of these:
(def color-map-1 {0 :red 1 :green 2 :blue 3 :orange 4 :violet 5 :cyan 6 :purple 7 :brown}) (def color-map-2 {0 : gray 1 :red 2 :green 3 :blue 4 :orange 5 :violet 6 :cyan 7 :purple 8 :brown})
:Question: Can we have an object A that is resistant, meaning even though another object B tries to "react" with it, e.g. by "trying to walk into it" it can't (object A is not changed)?
The following image answers YES:
Figure 1: A cell walks into a pattern but "bounces of" but then again walks at at it only to bounce off again.
:Question: Do larger cyclic structures exist (see Detecting Cyclic Structure in Particle-Distributing Cellular Automata) in which smaller cyclic patterns appear? The following image answers.
The following image answers YES:
Figure 2: In the center we see a glider type object. Note how this object it itself has a repeated cyclic pattern for part of the overall pattern. A red cell staying next to green cell. The same is true to a lesser extend for the glider type object on the right.
:Question: Do two objects A and B exist, such that these two objects "walking into each other" alters both objects, but the combined object still retains some properties of either object A or B?
The following image answers YES:
Figure 3: A glider type object has two red cells walk into it. A new glider type object forms, which walks to the left at seemingly the same rate.
Figure 4: An automata that just has all cells move to the left, but if cells are directly side by side they will over time move further appart such that there will be eventually a red cell between all green cells.
Figure 5: Here we can see that blue and green cells seem to always move left. We also see a glider like cyclic structure that moves left more slowly. Blue cells on their own just stay still.
Figure 6: Here cells of higher value seem like they want to split into either into lower value cells, or stay still. All cells seem like they want to have at least 1 red block between them and another cell.
Figure 7: When looking at all of spacetime the following automata seems like if you shoot some rays into it it will shoot them again out to the left. This means that there is the mostly blue structure, and if green cells walk into it and merge with the cells there, this structure will after some time "spit out" again green cells on the left.
Now images have all colors offset by 1. Gray is zero, red is one and so on.
Figure 8: A glider type object moves into an army of red blocks that stem from a violet block splitting. The glider is coerced to also become a bunch of red blocks. Now the army is larger! A very simple
1.4.1. Implementation 🔗
Here is a snapshot of the code used to generate these automata:
(require '[clojure.math.combinatorics :as combi]) (defn matchers [n-colors dimension] (map vec (apply combi/cartesian-product (repeat (+ (* 2 dimension) 1) (range n-colors))))) (defn redistributors [matcher] (let [n-particles (nth matcher 1)] (cond (zero? n-particles) [[0 0 0]] :else (map vec (remove (fn [distributor] (not= (reduce + distributor) n-particles)) (apply combi/cartesian-product (repeat 3 (range (inc n-particles))))))))) (defn sample-redistributor-rules [n-colors] (apply hash-map (mapcat (fn [matcher] (let [redistributors (redistributors matcher) rand-idx (rand-int (count redistributors)) rand-redistributor (nth redistributors rand-idx)] [matcher rand-redistributor])) (matchers n-colors 1)))) (defn merge-chunks [chunks] (reduce (fn [acc [i [a b c]]] (-> acc (assoc (+ i 0) (+ (peek (pop acc)) a)) (assoc (+ i 1) (+ (peek acc) b)) (conj c))) [0 0] (map-indexed vector chunks))) (defn map-redistribution-rules [state rules] (let [chunks (map rules (partition 3 1 state))] (merge-chunks chunks)))
We can then generate a ruleset and apply it to world state as follows:
(def rules (sample-redistributor-rules 15)) (def initial-state (repeatedly 60 #(rand-int 2))) (def trajectory (take 90 (iterate (partial map-redistribution-rules rules) initial-state)))
1.5. Extracting Structure 🔗
The next step is to extract some very basic structure.
1.6. Detecting Cyclic Structure in Particle-Distributing Cellular Automata 🔗
1.6.1. Question: Can we Extract Meaningful Structure via Cycle Detection? 🔗
- Can we efficiently detect cyclic patterns (patterns that contain themselfs in their induced trajectory)?
- How much of the worlds "structure" is captured by cyclic structures?
- How much more efficient can a Particle-Distributing Cellular Automata planning algorithm become, at finding action sequences that reach particular world states, when it knows all cyclic structures?
1.6.2. Process Documentation 🔗
The following describes a procedure to detect all cyclic structures that can appear in a particular Particle-Distributing Cellular Automata ruleset.
Roughly, the algorithms iterates through all possible starting states and checks if the starting state appears again in the trajectory that we get when applying the update rules to the starting state.
Note that this algorithm would work for standard cellular automata with only minor modifications.
1.6.3. Detected Cyclic Structure 🔗
The following is a cyclic patterns found by the detection algorithm, in increasing order of complexity. Here we only looked for cycles with a maximum length of 9:
Figure 9: A single cell that stays in place.
Figure 10: Two cells moving in tandem to the left.
Figure 11: A non-moving pattern cycling between two states.
Figure 12: A pattern of cycle 4 moving slowly to the right.
Figure 13: A pattern of cycle 9 moving slowly to the left.
1.6.4. Open Threads 🔗
1.6.4.1. Planning 🔗
- How can we use a hierachical model of cyclic patterns to significantly improve the perfromance of planning?
- What is a good baseline algorithm to compare against (potentially one that can be easily augmented by giving it good patterns).
1.6.4.2. Hierachical Pattern Model 🔗
- Detect when a cyclic pattern contains within it smaller cyclic patterns. The model of the larger pattern should be expressed as much as possible in terms of the smaller patterns that it contains.
1.6.4.3. Pattern Interaction 🔗
- What are the patterns that interact in predictable ways?
- E.g. what are the patterns such that if they run into each other, they form a new cyclic pattern that is the same, no matter what index in the cycle the two patterns are currently in.
- So far we assume we are on an inert red backgound. What are "attacks" that a pattern can fend of, i.e. what kinds of single cells, or larger patterns can run into this pattern
- without changing it permanently (temporary changes are allowed).
- such that the pattern grows, i.e. the pattern get's larger, or is composed of different cells, but the overall behavior stays
- exactly the same
- It still cycles at the same interval.
- It moves at the same velocity.
- When are patterns destroyed, and what does destruction mean? Maybe that only few or no properties of the pattern are preserved?
- Infer all possible ways that a particular pattern can arise. (Is this actually useful?)
Footnotes:
Technically we decrease the value because some cells move off screen but if we where to make the world large enough such that nothing would move offscreen, or would make the world wrap around then we would never loose anything.