はじめてな Elixir(25) ライフゲームを作ってみる

今日はライフゲームを作ってみました。綺麗にかけた感じが全くしません。どう綺麗にかけるのか先輩錬金術師さんたちに教えを請いたいところです。

ライフゲームとは

広い空間上に同一の状態機械が並んでいてそれらが一斉に動作するような機構をセルオートマトンと言います。各々のセルは隣接セルの状態を見て、自分の次の状態を決めます。ライフゲームはセルオートマトンでも最も有名と言って良いかと思います。正確には Conway's Game of Life と言います。

ライフゲームの規則

話せば長くなるので詳細は以下で。動画だけ見てもらっても楽しめるかと。
Wikipedia, Conway's Game of Life
Wikipedia, ライフゲーム

ここでは簡単に説明します。ライフゲームは以下のルールによるセルオートマトンです。

• 2次元空間にセルが並んでいて、各セルは上下左右に整列しています
• セルは2状態（生きてる、死んでる）を持ちます
  • このプログラムでは生きてる/死んでるをそれぞれ 1/0 で表しています
• 各セルの時刻は同期しており、n世代の隣接セルの状態によってn+1世代の状態が決まります
  • 初期値としての第0世代があります
• 自分のセルの周り8つ（左上、真上、右上、真左、真右、左下、真下、右下）のセルを見て、生きているセルの数が…
  • 3あるとき：次の世代で自分は生きます（今死んでるなら産まれます）
  • 2あるとき：今の自分の状態を維持します（死んでるママか生きてるママ）
  • それ以外の場合：次の世代で自分のセルは死んでしまいます

#ライフゲームを作る
最終ゴールはライフゲーム自体を作ることではないのですが、まずは腕試しで作ってみます。設計方針は以下。

• シングルプロセスで動くように記述する
  • あとでマルチプロセスで動かしてみようと画策してます
• データ構造
  • 盤面全体はタプルで表現する
  • 途中の操作ではリストを使って良い
• 表示は凝らない。コンソールに2次元の空間を埋める文字が見えればよい
• ExUnit を使ってテストをちゃんとやる

で、作ったプログラムが以下です。

dlife.ex

defmodule Dlife do
  @moduledoc """
  This module plays Conway's Game of Life in single process.
  """

  @doc"""
  The function nth_gen generates new generations
  from the initial field `world` for `n` times
  where nth_gen(n, i, world).
  Please feed 0 to `i` for displaying the generation cycle.

  For exapmle,
    Dlife.nth_gen(10, 0,
      {{0, 0, 0, 0, 0},
       {0, 0, 1, 0, 0},
       {0, 0, 0, 1, 0},
       {0, 1, 1, 1, 0},
       {0, 0, 0, 0, 0}})
  shows a flying glider with 10 generations.
  """

  @interval 200 # mili seconds
  
  def nth_gen(n, i, world) do
    pp(world, i)               # 現世代を綺麗に表示して
    if n == i do               # i が n に到達したらおしまい
      :ok
    else
      new = next_gen(world)    # 次世代を計算する
      Process.sleep(@interval) # ちょっぴり待つ
      nth_gen(n, i+1, new)     # i で再帰かけて n 世代分回す
    end
  end

  # pp は prity print の略
  # 1行単位で IO.inspect で表示して、全行数分を for で回す
  def pp(world, gen) do
    IO.puts("#{gen}th")
    for j <- 0..tuple_size(world)-1 do
      IO.inspect(elem(world, j))
    end
  end

  # 盤面全部のセルに対して以下を行う
  # あるセルの周辺のセルのリストを作り |> 生きてる数を数えて次の生死を決める
  # for の返り値がリストなので |> タプルに変換して返り値とする
  def next_gen(current) do
    (for j <- 0..tuple_size(current)-1 do
       (for i <- 0..tuple_size(elem(current, 0))-1 do
         get_neighbor(i, j, current) |> dead_or_alive()
       end) |> List.to_tuple
    end) |> List.to_tuple
  end

  # あるセルの周辺のセルの状態をリストで返す
  # .....
  # ..*..
  # ...*.
  # .***.
  # .....
  # のど真ん中の座標で呼ぶと以下が返る
  # [0,1,0,0,0,1,1,1,1]
  # やたらとゴチャゴチャしてるのは、盤の端面で反対側に折り返すため
  # rx, ry はそれぞれ水平・垂直方向の広さ (range of x, y) を意味する
  def get_neighbor(x, y, world) do
    rx = tuple_size(elem(world, 0))
    ry = tuple_size(world)

    [elem(elem(world, rem(y+ry-1, ry)), rem(x+rx-1, rx)),
     elem(elem(world, rem(y+ry-1, ry)),     x),
     elem(elem(world, rem(y+ry-1, ry)), rem(x+   1, rx)),
     elem(elem(world,     y),           rem(x+rx-1, rx)),
     elem(elem(world,     y),               x),
     elem(elem(world,     y),           rem(x+   1, rx)),
     elem(elem(world, rem(y+   1, ry)), rem(x+rx-1, rx)),
     elem(elem(world, rem(y+   1, ry)),     x),
     elem(elem(world, rem(y+   1, ry)), rem(x+   1, rx))]
  end

  # セルの近傍リストを受け取って、次の世代で生きるなら1、死ぬなら0を返す
  def dead_or_alive(neighbor) do
    me_now = Enum.at(neighbor, 4)
    case (Enum.sum(neighbor) - me_now) do
      2 -> me_now
      3 -> 1
      _ -> 0
    end
  end
end

ライフゲームを動かす

おされなUIを作らなかったので力技で入出力します。以下のように呼び出すと動きます。

dlife.ex

  def test5() do
    Dlife.nth_gen(20, 0,
      {{0, 0, 0, 0, 0},
       {0, 0, 1, 0, 0},
       {0, 0, 0, 1, 0},
       {0, 1, 1, 1, 0},
       {0, 0, 0, 0, 0}})
  end
end

これらはどちらもグライダーという移動する構造で、2周期で鏡像に反転しながらx方向かy方向に1マス進みます。これを2回、すなわち4周期で元の形に戻り斜め方向に1マス分進むパターンです。動かすと0thから4thで右下45度方向に1つ移動しているのが分かります。
Wikipedia, グライダー_(ライフゲーム)

iex(1)> Dlife.test5()
0th
{0, 0, 0, 0, 0}
{0, 0, 1, 0, 0}
{0, 0, 0, 1, 0}
{0, 1, 1, 1, 0}
{0, 0, 0, 0, 0}
1th
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 1, 0, 1, 0}
{0, 0, 1, 1, 0}
{0, 0, 1, 0, 0}
2th
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 0, 0, 1, 0}
{0, 1, 0, 1, 0}
{0, 0, 1, 1, 0}
3th
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 0, 1, 0, 0}
{0, 0, 0, 1, 1}
{0, 0, 1, 1, 0}
4th
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 0, 0, 1, 0}
{0, 0, 0, 0, 1}
{0, 0, 1, 1, 1}

このプログラムでは盤の左右と上下がつながってるトーラス構造にしていますので、端っこまで行くと反対側から出てきます。

5th
{0, 0, 0, 1, 0}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 0, 1, 0, 1}
{0, 0, 0, 1, 1}
6th
{0, 0, 0, 1, 1}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 1}
{0, 0, 1, 0, 1}
7th
{0, 0, 0, 1, 1}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 0, 0, 1, 0}
{1, 0, 0, 0, 1}
8th
{1, 0, 0, 1, 1}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 1}
{1, 0, 0, 0, 0}
9th
{1, 0, 0, 0, 1}
{0, 0, 0, 0, 1}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{1, 0, 0, 1, 0}
10th
{1, 0, 0, 1, 0}
{1, 0, 0, 0, 1}
{0, 0, 0, 0, 0}
{0, 0, 0, 0, 0}
{1, 0, 0, 0, 0}

盤の大きさが5x5なので20世代まで来ると元の場所に戻ります。

20th
{0, 0, 0, 0, 0}
{0, 0, 1, 0, 0}
{0, 0, 0, 1, 0}
{0, 1, 1, 1, 0}
{0, 0, 0, 0, 0}
:ok
iex(2)>

これは、例えば盤面を10x10で100世代までやるなら以下のように呼び出します。

dlife.ex

  def test10() do
    Dlife.nth_gen(100, 0,
      {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
      })
  end

プログラムの試験

いつもサボってるので試験もやってみました。

dlife_test.exs

defmodule DlifeTest do
  use ExUnit.Case
  doctest Dlife

  @world_nul {{0, 0, 0, 0, 0},
              {0, 0, 0, 0, 0},
              {0, 0, 0, 0, 0},
              {0, 0, 0, 0, 0},
              {0, 0, 0, 0, 0}}

  @glider_0th {{0, 0, 0, 0, 0},
               {0, 0, 1, 0, 0},
               {0, 0, 0, 1, 0},
               {0, 1, 1, 1, 0},
               {0, 0, 0, 0, 0}}

  @glider_1st {{0, 0, 0, 0, 0},
               {0, 0, 0, 0, 0},
               {0, 1, 0, 1, 0},
               {0, 0, 1, 1, 0},
               {0, 0, 1, 0, 0}}

  @world_0th @glider_0th

  test "@world_0th" do
    assert elem(@glider_0th, 0) == {0, 0, 0, 0, 0}
    assert elem(@glider_0th, 1) |> elem(2) == 1
  end

  test "next_gen" do
    assert @world_nul == Dlife.next_gen(@world_nul)
    assert @glider_1st == Dlife.next_gen(@glider_0th)
  end

  test "new_single_life" do
    assert Dlife.get_neighbor(0, 0, @world_0th) |> Dlife.dead_or_alive() == 0
    assert Dlife.get_neighbor(1, 1, @world_0th) |> Dlife.dead_or_alive() == 0
    assert Dlife.get_neighbor(2, 2, @world_0th) |> Dlife.dead_or_alive() == 0
    assert Dlife.get_neighbor(2, 4, @world_0th) |> Dlife.dead_or_alive() == 1
    assert Dlife.get_neighbor(3, 3, @world_0th) |> Dlife.dead_or_alive() == 1
    assert Dlife.get_neighbor(4, 4, @world_0th) |> Dlife.dead_or_alive() == 0
  end

  test "get_neightbor" do
    assert Dlife.get_neighbor(1, 1, @world_0th) == [0,0,0,0,0,1,0,0,0]
    assert Dlife.get_neighbor(0, 0, @world_0th) == [0,0,0,0,0,0,0,0,0]
    assert Dlife.get_neighbor(2, 2, @world_0th) == [0,1,0,0,0,1,1,1,1]
    assert Dlife.get_neighbor(2, 4, @world_0th) == [1,1,1,0,0,0,0,0,0]
    assert Dlife.get_neighbor(3, 3, @world_0th) == [0,1,0,1,1,0,0,0,0]
    assert Dlife.get_neighbor(4, 4, @world_0th) == [1,0,0,0,0,0,0,0,0]
  end

  test "dead_or_alive" do
    assert Dlife.dead_or_alive([0,0,0,0,0,0,0,0,0]) == 0
    assert Dlife.dead_or_alive([0,0,0,0,1,0,0,0,0]) == 0
    assert Dlife.dead_or_alive([1,0,0,0,0,0,0,0,0]) == 0
    assert Dlife.dead_or_alive([1,0,0,0,1,0,0,0,0]) == 0
    assert Dlife.dead_or_alive([0,1,0,0,0,0,0,1,0]) == 0
    assert Dlife.dead_or_alive([0,1,0,0,1,0,0,1,0]) == 1
    assert Dlife.dead_or_alive([0,1,0,0,0,0,1,0,1]) == 1
    assert Dlife.dead_or_alive([0,1,0,0,1,0,1,0,1]) == 1
    assert Dlife.dead_or_alive([1,0,1,0,0,0,1,0,1]) == 0
    assert Dlife.dead_or_alive([1,0,1,0,1,0,1,0,1]) == 0
  end
end

これで試験をやると以下のようになります。

$ mix test
Compiling 1 file (.ex)
.....

Finished in 0.06 seconds
5 tests, 0 failures

Randomized with seed 411500

こういう入力に対して出力がはっきり決まってる関数は試験しやすいですし、試験することで細かいミスも弾けて便利でした。

経験したこと

出来上がってみると行数も想定してたより少なくて「これぐらいで書けるのかぁ」という感想を持ちました。ただここに至るのにちょいと時間を喰ったので備忘録がてら残しておきます。

データ構造

盤全体は一様な空間で、それも場合によっては結構でかくする可能性もあるので、タプルにしました。奥に行くと線形にアクセス時間が増えるリストを避けたのです。ただしこれが正解だったかよくわかりません。

• タプルの関数が貧弱
• リストのほうがEnum関数群と相性が良くて使える関数も断然多い
• for の返り値の型がリストになる

ということがあるので、プログラムがタプルとリストを行ったり来たりします。工夫して全体をリストにして Enum 関数にパイプで流し込むようにするほうが綺麗になったかもしれません。そして、その方が結果的に動作も速くなる可能性もあるかなと思いました。

それは関数か変数か

途中で意味のわからないエラーメッセージに出くわしてずいぶんと自分の時間を溶かしました。以下はポイントがわかりやすいようにとことん単純に贅肉を削ぎ落としてます。

iex.ex

iex(1)> x=1   # x に 1 をマッチさせる
1
iex(2)> x-1   # x から 1 を引いてみる
0
iex(3)> x - 1 # x から 1 を引いてみる… ここまでは良い
0
iex(4)> x -1
** (CompileError) iex:4: "x -1" looks like a function call but there is a variable named "x", please use explicit parentheses or even spaces

iex(4)> 

これ「x(-1) って関数に見えるよ〜ん」って言ってます。

しかし、スペースの入れ方で解釈が変わり得るってどうよ。字句解析でトークンに分けるときにトークン間のスペースとタブはその個数によって意味が変わっては混乱を招くのではないのですかね。

この↑メッセージは「曖昧だからカッコつけるかスペース入れるかはっきりせい」と言ってきてるのでまだ意味がわかります。次に出てくるのはホントわかりませんでした。

iex(4)> rem(x-1, 5)   # rem/2 の第1引数は x から 1 を引いた値
0
iex(5)> rem(x - 1, 5) # rem/2 の第1引数は x から 1 を引いた値
0
iex(6)> rem(x -1, 5)  # rem/2 の…
** (CompileError) iex:6: undefined function rem/1

iex(6)> 

ここでは「関数 rem/1 が定義されてない」って言ってます。いやいや使ってるの rem/2 だから。だれがどこで rem/1 を使ってるというのか。（ちなみに、関数 rem/2 は整数演算で剰余を計算します。ここでは rem/2 でなくても、すでに定義されてる /2 の関数なら何でも同じ状況を再現できるかと思います。）

これは私が書いた式の x が変数ではなく x/2 なる関数と iex が解釈して rem(x(-1, 5)) と構文解析してるのです。これもっと複雑な式の中に出てくると「関数 x/2 が未定義だ」とか言うこともあって、より混乱します。

こんなことを避けるために、関数が引数取るときはすべからく括弧をつけるような文法の方が良いのではないですかね。ここの括弧、そんなに省略したいですか？ ちなみに1歩譲って関数の arity が 0 のときは括弧省略もありでも良いです。引数なしの関数と変数とを同一に取り扱う意味論で行けそうと思うので。

Qiitaのキーワードリスト

とまあ、これで時間喰ってイラっとしてるところに、最後の最後でまた時間を喰ってしまって、今日はついてないなぁというところ。

Qiita のキーワードは Conways_Game_of_life としています。本来なら Conway's_Game_of_life と書くべきで、そのように書いてました。そうも書き込めるのです。

するとね、保存ができないのですよ、右下の「下書き保存」ボタンを押しても。焦りますわ。全文コピって自分の emacs のバッファに入れました。エラーメッセージも出ないし、ボタンは押せるのですが、そのまま何も起こりません。なんか言ってよね、もう。

#参考文献

• Elixir v1.8.1, Tuple
• Elixir v1.8.1, List
• 日経サイエンス別冊176 マーチン・ガードナーの数学ゲームⅠ 新装版 ISBN978-4-532-51176-0 第6話
• ライフゲイムの宇宙 ウィリアム・パウンドストーン ISBN978-4-535-78383-6