resnicks_termite.md

   1 # Resnick's Termite
   2
   3 WORK IN PROGRESS
   4
   5 { Found this in the book *The Computational Beauty of Nature*. --drummyfish }
   6
   7 Resnick's termite is a simple [cellular automaton](cellular_automaton.md) simulating behavior of ants, demonstrating how even a very dumb behavior of a single agent can lead to higher collective intelligence once we increase the number of the agents. The simulation was made by Mitchel Resnick, the theme is similar to that of [Langton's ant](langtons_ant.md) but Resnick's termites are [stochastic](stochasticism.md), [nondeterministic](determinism.md), they rather show how statistics/[randomness](randomness.md) in behavior help many ants build tunnels in sand. The game demonstrates how randomly scattered chips start getting chunked together and form tunnels once we let ants with extremely simple behavior work together on moving the chips. Besides this demonstration however there doesn't seem to be anything more interesting going on (at least until we start to modify and tweak the thing somehow).
   8
   9 The system is defined quite simply: we have a world made of cells, each cell can be either empty or have a wooden chip on it. In this world we have a number of ants, each of which behaves by the following [algorithm](algorithm.md):
  10
  11 1. Randomly walk around until you bump into a chip.
  12 2. If you are not carrying a chip, pick up the one you bumped into, otherwise drop the chip you are carrying. Go to step 1.
  13
  14 The original implementation had ants who had direction (up, right, down, left) and on each step could make a random turn to the right or left. If an ant bumped into a chip it turned 180 degrees. These things prevented some annoying patterns like an ant just picking up a chip and immediately dropping it etc. Some further modifications were suggested like giving the ants some simple sense of sight or teleporting them randomly after dropping the chip.
  15
  16 ```
  17 iteration 0:
  18  ----------------------------------------------------------------
  19 |   ,  ,     '   '    , '    , ; ;    ' ',,''    ',  '     '     |
  20 |  '  ,     ,    ' ' '  ',,   ;'      ,,,  ,,,    ;       '  ;,  |
  21 |,     ,   ',  ; '  ' ',   '  ,   ' ','   '          ,, ''  ,  ',|
  22 |    ' ,;''   ,  ,',    ,     ,  ' ,  '','    '',; '   , ,, ',   |
  23 |  , ',,  ,,', ,  , ;     ;', ,';'    ,',    '   ,  '   ;;   ',  |
  24 | ',   ' ' ;  ,,       ,     ,  , '       ,  , '    , ,   ,  '   |
  25 | ,  ,',    ,'      ' ''   ' ,' '  ; , ' ' ; , , '   ,,   ,   , '|
  26 |    ,  '' ''    ' ,   ;        ;   ,;' '' ; ;            '     '|
  27 | ,  ,,      ;''  ', ;       '  '   ' ,' ,,,, , , ',    ,',,';   |
  28 | '    '',,'    , '    '   ,  '',,  ,,  ,','  '  ; '    '  ,;    |
  29 |',,   '   , ,   ,    ' , , ' ;,,  '  '  ,, ,';,  , ;     ;, '  ;|
  30 |,   '   '  ' ' ;, ,,,; ',   ;   '   ,  '  ';  ,  '  ; , ';,   , |
  31 |  ' ,' ', ' , , '  ', ''    ' ,  ;     ;    ,, ,,, ;, ','  ', ' |
  32 |',,   '     ,  '''     '   ,, ','   ' ' ''  ,,   ,  ',  '   ',''|
  33 |     , ,    ,   ,,';,;,, ,    , ' ,'    ',  '   ;     '         |
  34 | ,  '  ,'  , ;       '  , , ,   , ' , ';  ,,    ,  ','',        |
  35 |         ,',   ,' ' ,,    '''  ,       '  ' ', ',     ,,,     ',|
  36 |      ,',, ,, '; ,' '  '  ',       '   ,  ' ,        '  ,;  ; ' |
  37 |''  ','  ' ,    ' ,, , '    , ;  '   ,''       ,  ,'  ;     ,', |
  38 |   ,     ' ; , '    ''';   ,      '','  , '   ,    '' '     ',  |
  39 |    '   ,   '    ' '    ,  ,    ' ,'      ''   ,',  ,  ;,',,', '|
  40 |   '   ', '''';   '''     , '  ,',    ,'' ;'   ,   , '    , ,  ;|
  41 |,,  , ', '  ,   ;''   '     '      ,',    '    ,  ,'  ,,  '  ,  |
  42 |  ',', '       , ','    ,;,   ,; ',,, '             ',    ' ;   |
  43 |' ,  '  ,    ' ,  '     '      ,  ;   ' '  , ;  ,;   '' '  ,''  |
  44 |   ;  ,  ,;,;   '     , ' ''    ,     ,   ,    ,   ,,,'  ' ,,' ,|
  45 | '     ,'  ''      ',,       '  ',      '   ; ;       , ,, ' ,  |
  46 |    ,  ; , ,;'  , '  , '' '   '',   ,    ;   , ,       ,'''  ' '|
  47 |, ;,     ,         ' ,, ; ',,;,;';        ; ; , ''   ,       ', |
  48 |,' ';  ,  ,       ,,  '   ,' ''     ' ,' ,  '' ' ,,   , ', ,    |
  49 |; '  '''    '   ,  ,  ,     '           '     , ,,         ,'   |
  50 |;  , '           '  '   '    ', ''',,    ',       , '  ,      ,'|
  51  ----------------------------------------------------------------
  52
  53 iteration 5963776:
  54  ----------------------------------------------------------------
  55 |   , ;;';   '    ;';   ';,,   ,       '   , ,         ;'   ,''; |
  56 |    ';, ;  ,,,  , ,,  ;,,'',          ,,,              ,;   ;   |
  57 |    ,          ' ,'       ,,       '';'   '      ' ,     ' ' '';|
  58 |, ,,          ,   ,,              ''; ,         ;        ,';;,; |
  59 |'  ,            ,,,''             '' '  ' ' '  ''       ;'  ,'''|
  60 |, '';             ,,             ,'; , ;, ,,    ; ;     ,, ;    |
  61 |  ' ,      '' ' ';,               '  ',;    ;   '';,   ,'       |
  62 | '',  '   ',     ,               ; '',  ''  '     , '',,,  '  ,'|
  63 |, ;       ,        ;'                 ' ;    ,       ; ;;  ,,  ;|
  64 |, ;        ';     ,            '     ,;' ;;'         ,'';       |
  65 |                   '           ,      ';  ;,            ' '''   |
  66 |;            ',' ,';,;' '             ,,      ,  ' ;   ',       |
  67 |;,   ,,    '      ',;, ,                         ;,,'           |
  68 |         ,';'   ;';  '                 ,,,         ';          '|
  69 |,, ,  '   ,  '  ;'''',    '                         ;  , '      |
  70 |'  ;,,;' '' ';,, '       ,, ;       ';'    '''      ,,   ,,,   ,|
  71 |,,    ;,     , ';;     , ;   ;,    ',  ,, ;'    ,,            ;;|
  72 |         ;, ,;,;',  '  ;;,  ''    ', ;                          |
  73 |  ; ,  ' ,'' ,,'    ,,      ;'  ;;,;;    ' ',,;''          ,    |
  74 |  ,;   ,  ,       ''           '  ,;,    ,,   '''        ' ;'   |
  75 | ; ,;,         , ''  '        ;; ;; ; '  ' ,,'    ''    ,,; ,' ,|
  76 | ,              ''   ';;     '''  ,,;' '''     ' ' ;     ;;'    |
  77 | ,; '     ;;;  ,,             ,,'';    ; ;',    ;,,;          , |
  78 |'  ,;      ,' '                          ,           ;     ' ' ,|
  79 |'' ,;,, '';                                       ' ''   '' ,,  |
  80 |''    ;,            ,,, ;'          '';,,        ;'  ,        , |
  81 | ,, '    ';;'                       ,'                      ';, |
  82 |  ,    ,  ,           ',,;             ;'                  ';   |
  83 | ,,  ;; ,              ,               '                    ;,  |
  84 |     ,  ',     ''                , ;     ,   ;,             ;,  |
  85 |     '',,''   '' ,'       '                     ;,    ''        |
  86 |   ,,'' ,,  '      ;  ''  '   ;  ';'      ' '     '   ,,  , ; ' |
  87  ----------------------------------------------------------------
  88 ```
  89
  90 Here is an extremely basic implementation in [C](c.md) (without the fancy behavior improvements mentioned above, to keep the code short):
  91
  92 ```
  93 #include <stdlib.h>
  94 #include <stdio.h>
  95
  96 #define WORLD_SIZE 64
  97 #define ANTS 200
  98 #define CHIP_DENSITY 5
  99
 100 unsigned char world[WORLD_SIZE * WORLD_SIZE]; // 0: empty, 1: chip
 101
 102 typedef struct
 103 {
 104   int pos;
 105   unsigned char chip;
 106 } Ant;
 107
 108 Ant ants[ANTS];
 109
 110 void printHBorder(void)
 111 {
 112   for (int i = 0; i < WORLD_SIZE + 2; ++i)
 113     putchar((i != 0 && i != WORLD_SIZE + 1) ? '-' : ' ');
 114
 115   putchar('\n');
 116 }
 117
 118 void printWorld(void)
 119 {
 120   printHBorder();
 121
 122   for (int y = 0; y < WORLD_SIZE; y += 2)
 123   {
 124     putchar('|');
 125     for (int x = 0; x < WORLD_SIZE; ++x)
 126     {
 127       int n = y * WORLD_SIZE + x;
 128
 129       switch ((world[n] << 1) | (world[n + WORLD_SIZE]))
 130       {
 131         case 1: putchar('\''); break;
 132         case 2: putchar(','); break;
 133         case 3: putchar(';'); break;
 134         default: putchar(' '); break;
 135       }
 136     }
 137
 138     putchar('|');
 139     putchar('\n');
 140   }
 141
 142   printHBorder();
 143 }
 144
 145 void updateAnts(void)
 146 {
 147   for (int i = 0; i < ANTS; ++i)
 148   {
 149     int newPos = // this just randomly moves in one direction
 150       (WORLD_SIZE * WORLD_SIZE +
 151       ants[i].pos +
 152       ((rand() % 2) ? ((rand() % 2) ? -1 : 1) :
 153       ((rand() % 2) ? -1 * WORLD_SIZE : WORLD_SIZE)))
 154       % (WORLD_SIZE * WORLD_SIZE);
 155
 156     if (world[newPos]) // stepped on a chip?
 157     {
 158       if (ants[i].chip)
 159       { // has chip; drop the chip
 160         if (!world[ants[i].pos])
 161         {
 162           ants[i].chip = 0;
 163           world[ants[i].pos] = 1;
 164         }
 165       }
 166       else
 167       { // no chip; pick up the chip
 168         world[newPos] = 0;
 169         ants[i].chip = 1;
 170       }
 171     }
 172
 173     ants[i].pos = newPos;
 174   }
 175 }
 176
 177 int main(void)
 178 {
 179   srand(123);
 180
 181   for (int i = 0; i < WORLD_SIZE * WORLD_SIZE; ++i)
 182     world[i] = (rand() % CHIP_DENSITY) == 0;
 183
 184   for (int i = 0; i < ANTS; ++i)
 185   {
 186     ants[i].pos = rand() % (WORLD_SIZE * WORLD_SIZE);
 187     ants[i].chip = 0;
 188   }
 189
 190   int i;
 191
 192   while (1)
 193   {
 194     if (i % 65536 == 0)
 195     {
 196       printf("iteration %d:\n",i);
 197       printWorld();
 198     }
 199
 200     updateAnts();
 201     i++;
 202   }
 203
 204   printWorld();
 205   return 0;
 206 }
 207 ```