3 ms·
I keep wondering about the dynamics of Langton's ant within an infinite adversarial environment. The game I have in mind retains the standard behavior and movem
by mitchellpkt 3y ago
I keep wondering about the dynamics of Langton's ant within an infinite adversarial environment. The game I have in mind retains the standard behavior and movement patterns of Langton's ant. However, it introduces an adversarial component: upon the ant's first encounter with any given tile, an adversary determines the initial color of the tile, either black or white. The adversary's influence is constrained to this initial tile color determination, without any additional intervention capabilities.
The adversarial objective is twofold: primary is the prevention of 'highway' construction by the ant, and secondary, if the primary objective cannot be fully achieved, is to disrupt the 'highways' as swiftly as possible post-formation.
I do not have a good intuition for who has the upper hand here. The adversary can be deliberate, but its influence is strictly limited to controlling initial conditions of the board.
Maybe this falls under the Cohen-Kong Theorem, or a potential extension of it. I'm not sure whether that applies here since the adversary may provide a board with finite support or may choose to instead provide a board (or board-generating procedure) with infinite support.
- mcphage 3y agoBasically, does the ant have a finite loop? I would be surprised if there wasn't one.
- mitchellpkt 3y agoNo idea. Hmm, off the cuff maybe I’d conjecture that there cannot exist any initial configurations such that the ant gets stuck in a loop of finite length for infinite iterations. On any Nth iteration, the ant has only touched <= N tiles. Suppose we do a thought experiment where we create a second board that is empty except for the initial states of the touched tiles up to the Nth step. This second board has finite support, and so the usual theorems kick in, and consequently the ant will eventually start building a highway that would carry it away from the initial loop. I’m just making up guesses though, I have no clue if that is right.
- NackerHughes 3y agoSince the movement of Langton's Ant is entirely deterministic, it would be possible in this scenario to make the Ant go wherever the adversary pleases. The initial settings of the pixels can be carefully engineered to facilitate any arbitrary pattern of motion. The ant's movement can be easily calculated ahead of time to help with getting the initial pixel colours right.
- mitchellpkt 3y agoYep, it's a deterministic perfect information game. To "win" one needs only produce an initial board (or board generating procedure) that achieves certain characteristics, such as bounded highway length even with infinite iterations by the ant. What I am curious about is whether these boards/procedures exist, and how to find them.
- mitchellpkt 3y agoUpdate: I wrote a toy python library for evaluating Langton's ant in procedurally-generated infinite adversarial environments. https://github.com/Mitchellpkt/infinite_adversarial_langtons_ant https://github.com/Mitchellpkt/infinite_adversarial_langtons...