【PostgreSQL】SQLでライフゲームの実装

PostgreSQL Advent Calendar 2012 12/14 です。

ライフゲームとは「生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲーム」のことです。
碁盤目状に配置されたセルが、隣接するセルとの関係により、誕生・生存・死滅していく様子をシミュレーションします。

ルールは下記参考
ライフゲーム - Wikipedia

このライフゲームをSQLを使って実装してみます。

データ構造

セルの集合を下記のように表現します。
・１つのセルにつき、１行のレコード
・セルは３つの属性（列）を持つ
　integer x：碁盤の左端から右に何個目か
　integer y：碁盤の上端から下に何個目か
　integer alive：生存状態（生きているセルなら1、死んでいるセルなら0）

データはこれだけです。


初期化

碁盤のサイズ、生存しているセルの割合、を決めてランダムに生成

CREATE TABLE cells AS
SELECT
 x::integer, y::integer
 ,CASE WHEN random() < 0.3 THEN 1 -- 3割のセルが生存
 ELSE 0
 END::integer AS alive
FROM
 generate_series(1,5) t1(x) -- 横のサイズが5
 ,generate_series(1,5) t2(y) -- 縦のサイズが5
;
/*
SELECT * FROM cells;
 x | y | alive 
---+---+-------
 1 | 1 |     1
 1 | 2 |     0
 1 | 3 |     0
 1 | 4 |     0
 1 | 5 |     0
 2 | 1 |     0
 2 | 2 |     0
 2 | 3 |     1
 2 | 4 |     1
 2 | 5 |     0
 3 | 1 |     1
 3 | 2 |     1
 3 | 3 |     1
 3 | 4 |     1
 3 | 5 |     0
 4 | 1 |     0
 4 | 2 |     0
 4 | 3 |     0
 4 | 4 |     0
 4 | 5 |     0
 5 | 1 |     0
 5 | 2 |     0
 5 | 3 |     0
 5 | 4 |     1
 5 | 5 |     0
(25 rows)
*/

描画

初期化したセルから碁盤を描画してみます。
aliveの値をテキストに集約して0,1の文字列で表現しています。

SELECT string_agg(alive_y, E'¥n' ORDER BY y) AS board
FROM(
 SELECT
  y
  ,string_agg(alive::text, '' ORDER BY x) AS alive_y
 FROM cells
 GROUP BY y
)t
;
/*
               board               
-----------------------------------
 10100¥n00100¥n01100¥n01101¥n00000
(1 row)

10100
00100
01100
01101
00000
*/

次世代の生成

まずはSQLを

SELECT
 x, y
 ,(
  SELECT
   CASE WHEN c1.alive = 0 AND c2.alives = 3 THEN 1 -- 誕生
   WHEN c1.alive = 1 AND (c2.alives = 2 OR c2.alives = 3) THEN 1 -- 生存
   ELSE 0 -- 死滅
   END
  FROM(
   SELECT sum(c2.alive) as alives
   FROM cells c2
   WHERE
    NOT(c1.x = c2.x AND c1.y = c2.y) -- 自分自身を除く
    AND
    c1.x BETWEEN c2.x - 1 AND c2.x + 1 -- 横の範囲 
    AND
    c1.y BETWEEN c2.y - 1 AND c2.y + 1 -- 縦の範囲
  )c2
 )::integer AS alive
FROM cells c1
;
/*
 x | y | alive 
---+---+-------
 1 | 1 |     0
 1 | 2 |     0
 1 | 3 |     0
 1 | 4 |     0
 1 | 5 |     0
 2 | 1 |     1
 2 | 2 |     0
 2 | 3 |     0
 2 | 4 |     1
 2 | 5 |     0
 3 | 1 |     0
 3 | 2 |     1
 3 | 3 |     0
 3 | 4 |     1
 3 | 5 |     0
 4 | 1 |     0
 4 | 2 |     1
 4 | 3 |     0
 4 | 4 |     1
 4 | 5 |     0
 5 | 1 |     0
 5 | 2 |     0
 5 | 3 |     0
 5 | 4 |     0
 5 | 5 |     0
(25 rows)


01000
00110
00000
01110
00000
*/

ちょっと解説

次世代のaliveを生成しているサブクエリを具体的なケースに置き換えてみます。
x=2, y=3のセルは次世代で生存しているでしょうか？
サブクエリをc1.x=2, c1.y=3, c1.alive=1で置換したものが下記になります。

  SELECT
   CASE WHEN 1 = 0 AND c2.alives = 3 THEN 1 -- 誕生
   WHEN 1 = 1 AND (c2.alives = 2 OR c2.alives = 3) THEN 1 -- 生存
   ELSE 0 -- 死滅
   END
  FROM(
   -- ここのサブクエリで周囲の生存セル数を計算
   SELECT sum(c2.alive) as alives
   FROM cells c2
   WHERE
    NOT(2 = c2.x AND 3 = c2.y) -- 自分自身を除く
    AND
    2 BETWEEN c2.x - 1 AND c2.x + 1 -- 横の範囲 
    AND
    3 BETWEEN c2.y - 1 AND c2.y + 1 -- 縦の範囲
  )c2

具体的なケースができたら、後は全てのセルに対して同様に処理してやればOKです。

状態を保存する場合はUPDATEするなり、CREATE TABLEするなりしてやりましょう。


まとめ

ライフゲーム？それ、SQLでもできるよ。


Advent Calendar

明日はsakamotomsさんです。



おまけ1

任意の碁盤の状態からcellsを初期化したい場合

CREATE OR REPLACE FUNCTION board_to_cells(board text)
 RETURNS TABLE(x integer, y integer, alive integer)
 AS $$
  SELECT
   row_number() OVER(PARTITION BY y)::integer as x
   ,y::integer
   ,alive::integer
  FROM(
   SELECT
    row_number() OVER() AS y
    ,regexp_split_to_table(alive_y, '') AS alive
   FROM(
    SELECT
     regexp_split_to_table($1, '\n') AS alive_y
   )t
  )t
 $$
LANGUAGE SQL;

/*
SELECT * FROM board_to_cells(E'010\n100\n100');
*/

おまけ2

パフォーマンス実験
手元の環境にて、初期状態が100×100, 生存率3割で試したところ、次世代の計算にかかる時間が20秒強ほど。
もっと高速な実装を考えてみるのも面白いかも。