Of Ants and Turmites - Full Instructions
12 March 2021
In this post, I’m going to describe how I’ve defined the instruction sets for turmites, the definitions I used, and ways to expand beyond them. Here are some things to look for, in no particular order:
- the methodical means I used to ensure I got to observe all possible behaviors
- how did I make it repeatable, deterministic
- how can the total states be changed
- how can the action space be changed
- how can the action space be defined
Methodical search
From seeing the expandability of ants, I knew there’d be a lot of different arrangements with a turmite’s instruction set. However, if I organized the instructions, I could use some sort of counting method to enumerate all of the possibilities. Additionally, I’d always been enamored with the concept of a “seed” as I’d seen in game’s like Microsoft’s implementation of Solitaire. The ‘counting’ method was something I’d used before, but this may have been the first time I had an opportunity to create and use a seed.
There would be some number of actions dependent upon the number of internal and external state combinations and some limited, defined structure of an action. So (size of action) x (number of actions) = (size of seed), though note that this may not be in base-10 numbers. Whether there were 2 possible actions or 71, a turmite’s definition could be represented as a multi-dimensional array of those possible actions with a size based on the number of internal and external states. This could be flattened and assumed to be a base-N (N being total possible action count) number, which I could then convert to base-10 for convenience. So as a base-N number, I can now systematically search the entire space simply by counting. I can also calculate the total number of turmites this space could define as above.
Turmite definition
A specific turmite could be defined by its permutation of actions. The order of its actions define it, and the number of actions it’ll have is based on the product of internal and external states. 2 internal and 2 external are common, but this doesn’t need to be the case. If we consider defining a turmite with only one internal option and we simplify its action so it always changes, we end up with an ant. So ants are special cases of turmites. In example, our basic ant is:
| Color | Direction |
|---|---|
| White | Left |
| Black | Right |
which, as I’ve defined turmites, could be represented as:
| External State: White Square | External State: Black Square | |
|---|---|---|
Internal State -> N/A |
Change External State Keep Internal State Turn Left |
Change External State Keep Internal State Turn Right |
We have the freedom to choose any number of internal states and external states, so (total turmite actions) = (internal state definitions) x (external state definitions). Changing the number of defined internal and/or external states is one of the ways we can extend turmites. Let’s look more at an individual action definition.
Action definitions
Turmites are separated from ants by inclusion of an internal state which they can decide to change (or not) as part of their ‘action’. To my turmites, I made external changes also an option. Basic turmites, like ants, always change their external state (the value of the square they enter) during interaction. As a result, my turmites have the following in their full action:
- Change external -> true/false
- Change direction -> left/right/forward/backward
- Change internal -> true/false
As these are powers of 2, they conveniently convert to bits giving us 1 + 2 + 1 bits or 2 * 4 * 2 options. Since this aligns to bits so well, it’s hard for me to unsee. I’d stored these as _short_s too because they happened to fit and it was cute. The important part here is that there are 16 possibilities. Using 2 internal and 2 external states at 4 bits each gives us 16 total bits and 65536 turmites to define them all. Whatever you choose for options in your action, find the product of all the options and that’s your base-N. Mine was base-16 based on 2 * 4 * 2. Any number in there is potentially an action you’d assign to an internal/external state combination in your turmite. This will cover the whole space, but (as we’ll revisit later) the total action space may be too broad. Depending on what you have for actions, some “actions” could actually be devoid of action, meaningless, undesirable, or have contradictory components.
The above way of creating an action could be seen as ad hoc. Another way to define actions and assign them to states is with a table (or at least a conceptual table). You pre-define all actions statically/separately, number them sequentially from zero, and refer to the number. Starting with zero allows you to easily use base-N conversions.
Expanding Actions
The actions I’ve defined are independent from the actual values of the states. Direction change is statically defined in the action (and relative to facing direction in my implementation) and the internal and external state change amounts to adding either a 0 or 1 to the current value. States are used to select the turmite’s action and acted upon very simply, however you could choose to use the real value in the action formula. The results would still be deterministic, but the values produced and interpreted as an image would be more complex. Maybe you perform a step on the state value from the Collatz Conjecture, maybe you replace the value with the next highest value from the Fibonacci Sequence.
State definition
I used a simple even/odd determination to allow numbers to grow higher than 1 while still maintaining just 2 external states. I then used this as a faux step-count to find areas where the turmite stepped frequently. It’s not a true step count because the actions include ones that don’t modify external state. These states can be expanded nearly limitlessly as well. Perhaps state determination isn’t “even vs odd” (divisibility by 2) but a determination about divisibility by another number or set of numbers, or whether the number is a perfect square. Your seed could even provide a value to be used as a divisor or as part of your calculation.
We can get into trouble here, however. If you have conditions that can be satisfied by multiple states, how do you resolve conflict? I feel like if you’re heading this direction, you’re exiting turmites and creating something else. Implementation details start to matter more. The easiest way to proceed is to avoid rules that will conflict, determining state in such a way that exactly and only 1 evaluation of external and internal state resolve to true.
Boundless possibilities
Expanding the number of external states that a turmite responds to, the number and way it uses its internal state, and the selection of actions it takes gives you effectively limitless possibilities. At this point we’ve also been starting on an empty grid. What if the internal state was actually a stack and the actions provided manipulation of it? What if the outside world were given values prior to running the turmite? Could you make a programming language by careful planning of what was placed in the turmite’s path and use the turmite as an interpreter? Yeah, I think so. I mean *shrug* I just kind of want to draw some pictures, but this is why we can use the turmite both as a microcosm of computer science issues and an expandable basis to drive other projects.
Potholes on the road to adventure
Trying to bypass decisions with randomness
As you consider more options for movements or state change replacements, I would warn against any randomness at all. Ants and Turmites are supposed to be deterministic. If you decide that the direction change also includes a knight’s move, giving you 32 options I can think of, the action must be fully defined from the state the turmite is coming from or from some more limited set (table-wise?) of movement options. Don’t say “I want a knight’s move, but I don’t care if it’s left or right. . . guess I’ll just make that a coin toss”. Yes, even if you seed your pseudo-random generator, you’re still outside the realm of deterministic turmites.
Many ‘countable’ turmites should be skipped
There are a few styles of loops that don’t produce changes or that merely alternate between on and off forever. Any turmite with an initial action which leads to the initial state forever is no good. In my example, this would be any that don’t change internal state and don’t cross its own path (straight line for example). Another is if it doesn’t ever change its external state. Some boring turmites can be predicted early.
Hard to determine “interesting” patterns
This is the problem I’ll be exploring. Spent a lot of time on it already. If an ant or turmite starts building a highway, it doesn’t stop unless it hits something. Detecting a repeating pattern which is a highway would seem desirable. Building a triangle or square is also of only limited interest if you’ve already got a good triangle pattern in your collection. While they aren’t perfect loops, they change in a regular manner. Unfortunately for this line of thinking, lots of interesting patterns emerge from regular repeated near-loops. Nautilus shells and golden ratio rectangles, for instance. Local area modification coverage isn’t a perfect predictor of ‘interesting-ness’ either. And then there are rotations or flips of previously identified, established patterns. . . as you expand out controls, where do you stop? How do you at least limit repetition with limited risk of suppressing/losing an interesting pattern? My answer is: very carefully.
The search for interesting designs
That’s where we’re going. I’ll use some machine learning techniques, utilize cloud resources, set up and learn more about recommender systems and semi-supervised machine learning, and make a whole bunch of mistakes and premature assumptions as I try to develop a system which will learn my aesthetic tastes and shorten the search for new and interesting turmite-generated images.
If you have interesting state determination criteria or action definitions, feel free to share. I’m going to rewrite my turmite code in Python (originally in C#) and expand it to be flexible enough to expand in all the ways described above.