[HN Gopher] Langton's ant
___________________________________________________________________
Langton's ant
Author : scapecast
Score : 89 points
Date : 2023-05-17 13:39 UTC (9 hours ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| elevaet wrote:
| I prefer Langton's Phage
| mitchellpkt wrote:
| 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 wrote:
| Basically, does the ant have a finite loop? I would be
| surprised if there wasn't one.
| mitchellpkt wrote:
| No 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 wrote:
| Since 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 wrote:
| Yep, 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.
| dang wrote:
| Related:
|
| _Langton 's Ant_ - https://news.ycombinator.com/item?id=20123626
| - June 2019 (25 comments)
|
| _Hexagonal Langton 's Ant 2 - Colors, Gliders and Highways_ -
| https://news.ycombinator.com/item?id=10324517 - Oct 2015 (13
| comments)
|
| _Langton 's ant_ - https://news.ycombinator.com/item?id=8265482
| - Sept 2014 (42 comments)
|
| _Langton 's ant_ - https://news.ycombinator.com/item?id=2230459
| - Feb 2011 (20 comments)
| javier_e06 wrote:
| There must be a minecraft version of this critter somewhere.
| StrictDabbler wrote:
| I used to play around with Langton's Ant a lot.
|
| The longer patterns remind me of the climbable game assets in
| "Below the Root" and "The Jungle Book", early games by Dale
| Disharoon/DeSharone that I played on an Apple II compatible,
| though they were available on DOS and C64 as well.
|
| I'd always assumed that Dale based his vines on Langton's Ant but
| the timeline doesn't add up. Dale's games came out several years
| earlier.
|
| It is an interesting aesthetic subset of digital noise.
|
| Worth noting that Dale also worked on the strange Legend of Zelda
| CDi games. He had an unusual arc.
|
| https://www.uvlist.net/game-173637-Below+the+Root
|
| http://blog.hardcoregaming101.net/2012/09/dale-desharone-uns...
| chkas wrote:
| https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...
| tromp wrote:
| I like the result after just the first 52 steps:
|
| https://easylang.dev/ide/#run=len%20f%5B%5D%20100%20*%20100%...
| qubex wrote:
| There's a good discussion of this in one of my favourite books:
| William Gary Flake's _The Computational Beauty of Nature_ (1998).
| rhdunn wrote:
| There are some interesting patterns/behaviours with Langton's
| ants.
|
| In a wrap around world (e.g. moving off the left/right will enter
| the other side), the ant will collide with its "hive" (starting
| blob) or "highway" (diagonal pattern) and repeat a hive-highway
| construction cycle.
|
| With two ants, depending on their starting position, they will
| end up in one of 3 patterns:
|
| 1. A hive-highway pattern like one ant;
|
| 2. As 1, but will collide with each other, then undo their
| construction until they go back to the beginning and then repeat
| this pattern;
|
| 3. Race around each other in an expanding diamond pattern. If the
| world is a wrap around world, when they reach one edge, they will
| start to undo/shrink the diamond, generating an expanding-
| collapsing diamond pattern.
|
| It's also interesting playing around with more colours/states,
| and different rules (180deg turn, no turn).
|
| With these generalized turmites, I've seen them create/use "super
| highway" constructs. -- A "super highway" is a straight line of a
| single colour where a turmite's behviour for that colour is to
| not turn. -- It will then race forward along that highway.
| tectec wrote:
| Wow, that brings me back. My older brother wrote a Langton's ant
| program in QBasic, and one of my earliest computer memories was
| watching that thing go.
| mg wrote:
| I always considered Rule 110 the simplest system (code complexity
| wise) that is turing complete:
|
| https://en.wikipedia.org/wiki/Rule_110
|
| I wonder if the Langton's ant algorithm (say in Javascript) is
| shorter.
|
| My gut feeling is that it's about the same size. But maybe
| Langton's ant is shorter because it only needs a single loop.
|
| In pseudo-code it is super simple: 10
| INVERT(X,Y) 20 IF GETCOL(X,Y): TURNLEFT() 30 ELSE
| : TURNRIGHT() 40 STEPFORWARD() 50 GOTO 10
|
| But an actual implementation would be quite a few more lines.
| chriswarbo wrote:
| > I always considered Rule 110 the simplest system (code
| complexity wise) that is turing complete
|
| It can get a bit subjective, when trying to compare _really_
| simple systems.
|
| > an actual implementation would be quite a few more lines
|
| The simplest Turing-complete system to _implement_ that I 've
| come across is FlipJump ( https://esolangs.org/wiki/FlipJump ).
|
| The easiest Turing-complete system I've implemented is
| BitBitJump, which is older than FlipJump and _slightly_ more
| complex ( https://esolangs.org/wiki/BitBitJump ). I used it as
| a simple way to enumerate the output of all programs:
| implementation at
| http://www.chriswarbo.net/js/optimisation/levin_bbj.js and
| visualisation/explanation here
| http://www.chriswarbo.net/projects/optimisation/levin.html
|
| (Technically these aren't Turing-complete, in the same way that
| C isn't Turing complete: the amount of memory they can
| reference is bounded by their word size. This can be fixed by
| allowing I/O to external storage. My program enumeration loops
| through all word sizes ;) )
| ChintanGhate wrote:
| Here's my implementation from 2014 that let's you spawn more ants
| on the grid. http://code-art.chintanghate.me/LangtonsAnt.html
| SeanAnderson wrote:
| This is so cool! Does the term "ant" here have any real-world
| implications to the behavior of ants, or is it simply a creative
| term? Obviously ants are known to build highways, but that's
| through use of pheromone trails rather than a very simple process
| of turning, right? But I guess the black/white configuration is a
| binary representation of a pheromone trail? So, maybe?
| gkbrk wrote:
| Langton's ant is really cool, especially considering the
| extremely simple rules.
|
| - At a white square, turn 90 degrees clockwise, flip the color of
| the square, move forward one unit.
|
| - At a black square, turn 90 degrees counter-clockwise, flip the
| color of the square, move forward one unit.
|
| If you look at the images and animations, you might think that it
| becomes repetitive quickly, and nothing interesting happens. But
| that is only if you have an infinite grid.
|
| If you have a grid that wraps to the opposite side on the edges,
| it interacts with its own path a lot more. This produces very
| chaotic and "random" results. In fact, I've made a toy PRNG based
| on Langton's ant, and it does quite well on PractRand. It's not a
| performance king, far from it, but still really cool that two
| simple rules can do that.
|
| It would be a fun project to make a (probably very slow) cipher
| based on Langton's ant.
___________________________________________________________________
(page generated 2023-05-17 23:02 UTC)