Zenn
Open26

人工生命Tierra

todeskingtodesking

Ray, T. S. 1991. An approach to the synthesis of life. In : Langton, C., C. Taylor, J. D. Farmer, & S. Rasmussen [eds], Artificial Life II, Santa Fe Institute Studies in the Sciences of Complexity, vol. XI, 371–408. Redwood City, CA: Addison-Wesley.

概要についてはこれを読めばよさそう。
公開されてるPDFはかなり品質が悪いが、ソースが公開されてるのでCloud LaTeXとかでコンパイルすればよい(ただし図が出ない)
http://life.ou.edu/pubs/alife2/tierra.tex

todeskingtodesking

理想的な生物学は、生命のすべての形態を対象とすべきである。しかし、実際には、生命のたった一つの形態——地球上の生命——しか研究対象にできていない。地球の生命は多様だが、すべては一つの系統に属している。生物学がN=1に基づいている以上、なにが地球生命固有で、なにが生命一般の特性なのかを知ることはできない。真に比較可能な自然生物学には、光年単位での惑星間航行を必要とするだろう。理想的な実験進化生物学のためには、複数の同じ惑星系を作成し、特定のパラメータだけ変えて何十億年か観察する必要があるだろう。

todeskingtodesking

壮大なイメージから始まるこの論文では、惑星系を何十個か作るかわりに、コンピュータを使って生命をシミュレートする手法を提案している。地球の生命とはまったく違う原理に基づく生命の進化を観察することで、生命に対する洞察が深まるだろう。

todeskingtodesking

非公式gitミラー。195c2eb84d91a1938faabad38e24b9b47d0e262c https://github.com/acisternino/tierra

todeskingtodesking

STATS area:

> InstExec  =  8,177185  Cells =  342  Genotypes =  131  Sizes =  23
命令実行回数, 生命数, 遺伝子の種類数, サイズの数

> Extracted = 0080acw @ 10 v
最後に閾値( SavThrMem or SavThrPop)を超えた生命, その時点での個体数, 既に保存済みだったらv

PLAN area:

> InstExeC      =      8  Generations  =     19  Thu Jan 18 12:43:17 1996
>     NumCells  =    344  NumGenotypes =    136  NumSizes  =     22
>     AvgSize   =     84  NumGenDG     =      1  
>     AvgPop    =    340  Births       =    840  Deaths    =    852
>     RateMut   =  17998  RateMovMut   =   1344  RateFlaw  =  75648
>     MaxGenPop =    105  (0080aaa)    MaxGenMem =     105 (0080aaa)
>     Speed     =  16129  NumNodes     =     32

Info menu:

  • Size histogram: Size * Living + Genotypes
  • Genotype histogram: Genotype * Living
  • Memory histogram: Size * Living(by memory footprint)
  • Size query: List most common genotypes by size.

Size queryで表示される情報:

#     = actual count, populations of adult cells of this genotype
Mem   = is the percent of Soup, occupied by adult cells of this genotype
Err   = is the number of error flags generated by that genotype,
Move  = number of instructions moved to daughter cell by that genotype,
Bits  = Watch bits.  If the soup_in variables WatchExe, WatchMov, or WatchTem
        are set to a non-zero value, Tierra will keep a record of a variety
        of activities and interactions within and between genotypes which
        are permanent.  This data is stored in the bit field in the GList
        structure (bit definitions are defined in the tierra.h module).
        Some details of these observations are described below.

Bitsによって特定の実行情報を追跡できる

WatchExe bits:

    bit  2  EXs = executes own instructions (self)
    bit  3  EXd = executes daughter's instructions
    bit  4  EXo = executes other cell's instructions
    bit  5  EXf = executes instructions in free memory
    bit  6  EXh = own instructions are executed by other creature (host)

WatchMov bits:
どこからどこに命令がコピーされたかの統計っぽい。

    bit 17  MFs = moves instruction from self
    bit 18  MFd = moves instruction from daughter
    bit 19  MFo = moves instruction from other cell
    bit 20  MFf = moves instruction from free memory
    bit 21  MFh = own instructions are moved by other creature (host)
    bit 22  MTs = moves instruction to self
    bit 23  MTd = moves instruction to daughter
    bit 24  MTo = moves instruction to other cell
    bit 25  MTf = moves instruction to free memory
    bit 26  MTh = is written on by another creature (host)
    bit 27  MBs = executing other creature's code, moves inst from self
    bit 28  MBd = executing other creature's code, moves inst from daughter
    bit 29  MBo = executing other creature's code, moves inst from other cell
    bit 30  MBf = executing other creature's code, moves inst from free memory
    bit 31  MBh = other creature uses another cpu to move your instructions

WatchTem bits:
ジャンプ命令等でどのテンプレートが参照されたかの統計

    bit  7  TCs = matches template complement of self
    bit  8  TCd = matches template complement of daughter
    bit  9  TCo = matches template complement of other
    bit 10  TCf = matches template complement of free memory
    bit 11  TCh = own template complement is matched by other creature (host)
    bit 12  TPs = uses template pattern of self
    bit 13  TPd = uses template pattern of daughter
    bit 14  TPo = uses template pattern of other
    bit 15  TPf = uses template pattern of free memory
    bit 16  TPh = own template pattern is used by other creature (host)
todeskingtodesking

コードリーディング:

  • tierra.c の life() がメインループ
    • (*slicer)() がエネルギー分配関数
    • その後の ReapCheck() がdisturbanceを発動させる処理(適当なタイミングでリーパーによる大量絶滅を実施)
todeskingtodesking

slicer

グローバルな関数ポインタで、エネルギー分配処理を選択できるようにしてある(tsetup.cにて設定)

実装は slicer.c で定義された三種類:

  • SlicerPhoton
  • SlicerQueue
  • RanSlicerQueue

SlicerPhoton()

フォトン - クロロフィルのメタファーに基づくエネルギー分配。
光子が特定のセルに当たったとき、その周辺の命令列パターンと命令列"chlorophill"の距離に応じてエネルギーを得る。

SlicerQueue()

Slicer queueに基づくエネルギー分配。これが一番基本的なやつ。

  1. 現在のセル(グローバル変数ce)に、サイズに応じたエネルギーを与える
  2. IncrSliceQueue() でceを次に進める
  3. ce の実行時間(生殖でリセット) が RepInst * LazyTol を超えていたらReapCell(ce, LEAP_LAZY)

RanSlicerQueue()

semirandom constant/"size dependent" time slice algorithm

キュー操作は SlicerQueue と同様で、得られるエネルギーの計算式が違う

todeskingtodesking

TimeSlice(size_slice) in tierra.c

現在の生命 ce に size_slice のエネルギーを与えて実行する。

        for (c = ce->c.n - 1; c >= 0; c--)
        {   CpuHalt=0;
            ce->c.c = &(ce->c.ar[c]);
            ce->c.ac = c;

現在実行中の個体(ce)の現在アクティブなCPU(ce->c.c)はce->c.ar[c]で、個体が持つce->c.n個のうちc番目ですよ、という設定をしている場所。実装が難解だし仕様も複雑！

                if (ce->c.c->slicexit ||
                    (ce->c.sy.sy && (ce->c.c->sy.G > -1) &&
                    (ce->c.sy.sy[ce->c.c->sy.G].sync && ce->c.c->sy.sync)))
                    continue;

難読コード選手権か???

今回のスコープ(一番単純なCPU一個バージョン)に関係なさそうなコードはなるべく無視してゆく。
CPUを複数持てる、命令セットの変更に柔軟に対応できる、スレッドがある、等の仕様のせいで複雑。

本質的な処理は以下:

        // for each cpu:
                di = FetchDecode();
                (*id[di].execute)();
                IncrementIp();
                SystemWork();
todeskingtodesking

FetchDecode() in tierra.c

本質的には以下か:

    di = (*(is.eins)) % InstNum; // eins: pointer to instruction being executed
    (*id[di].decode) ();
    return di;
todeskingtodesking

IncrementIp() in tierra.c 

    ce->c.c->ip += is.iip; // iip: amount of increment instruction pointer, 命令のdecodeで設定される。
todeskingtodesking

SystemWork() in tierra.c 

    // 命令エラー時のリーパーキュー移動処理
    if (ce->c.c->fl.E)
    {   ce->d.flags++;
        if (!(ce->d.dm))
            // d.flags(エラー数)が多かったらキュー移動
            // UpRprIf(ce);
            if (cp->d.flags >= cells[cp->q.p_reap.a][cp->q.p_reap.i].d.flags)
                UpReaper(cp);
    }

    // 命令数が一定を超えたらスープ内のランダム位置を変異
    if (RateMut && ++CountMutRate >= RateMut)
    {   mutate();
        TotMut++;
        CountMutRate = tlrand() % RateMut;
    }
todeskingtodesking

mutate() in operator.c

スープ内のランダム位置に対して mut_site() を呼ぶ

mut_site() in operator.c

確率 MutBitProp で指定位置をbit flip。それ以外の場合は指定位置をランダムな命令に置換。

todeskingtodesking

命令定義

idt in soup_in.h に一覧、instruct.cにexecute関数、decode.cにdecode関数

todeskingtodesking

Tierraの命令セット

tierra/gb*/opcode.map に命令セット定義あり