Notebook

畳み込み演算によるlifegameの生死判定¶

Ruby Numo (NUmerical MOdule) のgnuplot-demo/misc/lifegame のLifeGameクラスを見たとき、とてもシンプルで不思議なコードに引き込まれました。

「これだけのコードでどうやって生死の判定をしているのだろう？」と、

とても興味を持ったところで少し調べてみると「畳み込み演算」らしいことが分かりました。盤面の生死の状態を画素として捉えて、畳み込みフィルタによる画像処理を行うイメージです。好奇心の冷めないうちに、観察の記録をこの iRuby Notebook に書き留めておきます。

次のコードは class LifeGame からクラスの部分を書き出したものです。盤面の初期化(initialize メソッド)と更新(update メソッド)のみのシンプルな構成です。

require 'numo/narray'

class LifeGame

  def initialize(nx,ny,m)
    @data = Numo::UInt8.zeros(ny,nx)
    @data[m..ny-1-m,m..nx-1-m] = Numo::UInt8.new(ny-2*m,nx-2*m).rand(2)
    @step = 0
  end

  def update
    b = Numo::UInt8.zeros(*@data.shape)
    b[1..-2,1..-2] =
      @data[0..-3,0..-3] + @data[0..-3,1..-2] + @data[0..-3,2..-1] +
      @data[1..-2,0..-3] + @data[1..-2,2..-1] +
      @data[2..-1,0..-3] + @data[2..-1,1..-2] + @data[2..-1,2..-1]
    @data.store((b.eq 3) | ((b.eq 2) & Numo::Bit.cast(@data)))
    @step += 1
  end

  attr_reader :data,:step
end

盤面の初期化¶

盤面の初期化はinitializeメソッドで行います。以降は小さな盤面を作成し、確認用のコードを直書きしながら確認していきます。

In [11]:

require 'numo/narray'
require 'numo/gnuplot'
require "base64"

data = Numo::UInt8.zeros(6,6)

Out[11]:

$\left(\begin{array}{cccccc} 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{array}\right)$

盤面の初期値を設定¶

0は死、1は生の状態を表します。実際のクラスでは盤面の初期状態を乱数によって生成していますが、ここでは1世代目の初期値として「ビーコン」と呼ばれる周期が2の振動子を設定します。

In [12]:

data[0..5,0..5] =  [[0,0,0,0,0,0], 
                    [0,1,1,0,0,0], 
                    [0,1,1,0,0,0], 
                    [0,0,0,1,1,0],
                    [0,0,0,1,1,0], 
                    [0,0,0,0,0,0]]

Out[12]:

[[0, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 0], [0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 0]]

盤面をupdate¶

updateメソッドでは、畳み込み演算用データ b を、 data と同じサイズで初期化。

In [13]:

b = Numo::UInt8.zeros(*data.shape)

Out[13]:

$\left(\begin{array}{cccccc} 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{array}\right)$

畳み込み演算¶

畳み込み演算によって 8 方向のデータを畳み込み、セルの生死判定用の数値を作成しています。ここでは配列のビューを指定して操作が行われています。

In [5]:

b[1..-2,1..-2] =
      data[0..-3,0..-3] + data[0..-3,1..-2] + data[0..-3,2..-1] +
      data[1..-2,0..-3] + data[1..-2,2..-1] +
      data[2..-1,0..-3] + data[2..-1,1..-2] + data[2..-1,2..-1]

Out[5]:

$\left(\begin{array}{cccc} 3&3&2&0\\ 3&4&4&2\\ 2&4&4&3\\ 0&2&3&3\\ \end{array}\right)$

生死判定用の数値を格納する場所は、実際の盤面サイズより、ひと回り小さな範囲に格納されます。

In [6]:

Out[6]:

$\left(\begin{array}{cccccc} 0&0&0&0&0&0\\ 0&3&3&2&0&0\\ 0&3&4&4&2&0\\ 0&2&4&4&3&0\\ 0&0&2&3&3&0\\ 0&0&0&0&0&0\\ \end{array}\right)$

2世代目の生死判定¶

ここで畳み込み演算の結果から2世代目のセルの生死判定を行い、生存データのみを盤面に書き込んでいます。

この1行だけで盤面全体の生死判定ができるとは、なんとシンプルで素敵なことでしょう。

In [7]:

data.store((b.eq 3) | ((b.eq 2) & Numo::Bit.cast(data)))

Out[7]:

$\left(\begin{array}{cccccc} 0&0&0&0&0&0\\ 0&1&1&0&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&1&0\\ 0&0&0&1&1&0\\ 0&0&0&0&0&0\\ \end{array}\right)$

3世代目の生死判定¶

再びupdateメソッドによって3世代目のセルの生死判定を行います。「ビーコン」は2周期の振動子なので、ここで元の状態に戻ります。

In [8]:

b = Numo::UInt8.zeros(*data.shape)
b[1..-2,1..-2] =
      data[0..-3,0..-3] + data[0..-3,1..-2] + data[0..-3,2..-1] +
      data[1..-2,0..-3] + data[1..-2,2..-1] +
      data[2..-1,0..-3] + data[2..-1,1..-2] + data[2..-1,2..-1]
data.store((b.eq 3) | ((b.eq 2) & Numo::Bit.cast(data)))

Out[8]:

$\left(\begin{array}{cccccc} 0&0&0&0&0&0\\ 0&1&1&0&0&0\\ 0&1&1&0&0&0\\ 0&0&0&1&1&0\\ 0&0&0&1&1&0\\ 0&0&0&0&0&0\\ \end{array}\right)$

次世代の生死判定¶

以後のupdateによって、2周期の振動子はこの状態を繰り返します。

In [9]:

b = Numo::UInt8.zeros(*data.shape)
b[1..-2,1..-2] =
      data[0..-3,0..-3] + data[0..-3,1..-2] + data[0..-3,2..-1] +
      data[1..-2,0..-3] + data[1..-2,2..-1] +
      data[2..-1,0..-3] + data[2..-1,1..-2] + data[2..-1,2..-1]
data.store((b.eq 3) | ((b.eq 2) & Numo::Bit.cast(data)))

Out[9]:

$\left(\begin{array}{cccccc} 0&0&0&0&0&0\\ 0&1&1&0&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&1&0\\ 0&0&0&1&1&0\\ 0&0&0&0&0&0\\ \end{array}\right)$

セルの生死判定について¶

次世代の存在条件¶

次の世代が存在する条件はつぎの2つです。

死んでいるセルに、隣接する生きたセルが3つ存在すれば次の世代が誕生する。

(b.eq 3)

生きているセルに、隣接する生きたセルが2つか3つ存在すれば、次の世代でも生存可能。

(Numo::Bit.cast(data) & ((b.eq 2) | (b.eq 3)))

それ以外は次世代では生存できない。（死の状態）

これらの条件から、storeする条件式はつぎのようになるはずです。

(b.eq 3) | (Numo::Bit.cast(data) & ((b.eq 2) | (b.eq 3)))

ところが実際のコードは少し違います。

@data.store((b.eq 3) | ((b.eq 2) & Numo::Bit.cast(@data)))

カルノ図で確認¶

確認のためカルノ図を描いてみます。

図を描きやすいように、予め各条件をa, b, cに置き換えます。

A = Numo::Bit.cast(data)
B = b.eq 2
C = b.eq 3

C | (A & (B | C))

真理値表は次のようになります。

$A$	$B$	$C$	$OUT$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

真理値表を元にカルノ図を描くと

$A \backslash BC$	$\overline{B}$	$\overline{B}$	$B$	$B$
0	0	1	1	0
1	0	1	1	1
	$\overline{C}$	$C$	$C$	$\overline{C}$

論理圧縮¶

上記のカルノ図を使って論理圧縮を行うと次のようになります。

圧縮前の C | (A & (B | C)) は

圧縮後に C | (A & B) となる。

ここで置き換えを元に戻すと (b.eq 3) | (Numo::Bit.cast(data) & (b.eq 2)) となり

この条件は、実際のコードの

@data.store((b.eq 3) | ((b.eq 2) & Numo::Bit.cast(@data)))

と同じ結果になることがわかります。

実際の「ビーコン」の動作を確認¶

In [14]:

require 'numo/narray'
require 'numo/gnuplot'
require "base64"

class LifeGameTest

  def initialize(nx,ny,m)
    @data = Numo::UInt8.zeros(ny,nx)
    @data[0..5,0..5] =  [[0,0,0,0,0,0], 
                         [0,1,1,0,0,0], 
                         [0,1,1,0,0,0], 
                         [0,0,0,1,1,0],
                         [0,0,0,1,1,0], 
                         [0,0,0,0,0,0]]
    #@data[m..ny-1-m,m..nx-1-m] = Numo::UInt8.new(ny-2*m,nx-2*m).rand(2)
    @step = 0
  end

  def update
    b = Numo::UInt8.zeros(*@data.shape)
    b[1..-2,1..-2] =
      @data[0..-3,0..-3] + @data[0..-3,1..-2] + @data[0..-3,2..-1] +
      @data[1..-2,0..-3] + @data[1..-2,2..-1] +
      @data[2..-1,0..-3] + @data[2..-1,1..-2] + @data[2..-1,2..-1]
    @data.store((b.eq 3) | ((b.eq 2) & Numo::Bit.cast(@data)))
    @step += 1
  end

  attr_reader :data,:step
end

nx,ny = 6, 6 # don't modify
life = LifeGameTest.new(nx,ny,1)
filename = "lifegameTest.gif" 

Numo.gnuplot do
  reset
  set output: filename
  set term: "gif", animate:true, delay:50, size:[500,500]
  set :nokey
  set size: {ratio:1.0*ny/nx}
  set xrange: -1..nx
  set yrange: -1..ny
  unset :colorbox
  set palette_defined:'(0 "white", 1 "green")'

  10.times do |i|
    life.update if i > 0
    set title:"lifegame step=#{i}"
    plot life.data, flipy:true, with:"image"
  end
  set :output
end

img = Base64.strict_encode64(File.binread(filename))
IRuby.html %Q(<img src="data:image/gif;base64,#{img}" />)

Out[14]:

まとめ¶

numo-gnuplotで出会ったlifegameから、新しい知見を得ることができました。

感謝！

参考¶

In [ ]: