人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

ライフゲーム

人工知能というより人工生命の分野ですが最初はライフゲームを作ってみます。ライフは人生という意味もありますがライフゲームは人生ゲームとはまったく関係ありません。まず、フィールド(黒い部分)をマウスクリックすると、黄色い■が出てきます。もう一度押すと■が消えます。キーボードの上下左右キーで青色のカーソルを動かしてスペースキーで描くこともできます。細かい図形を描くときはキーボードの方が便利です。キャンバスに適当に描いたら、Sキーを押してください。徐々に図形が変化していきます。もう一度Sキーを押すと止まります。またNキーを押すと1ステップずつ経過をみることができます。Cキーを押すとフィールドをきれいにします。Rキーを押すと適当に■をばらまきます。

pylife.py
f:id:aidiary:20100814095901p:plain

ライフゲームとは

ライフゲームは1970年ごろにイギリスの数学者コンウェイが考案したゲームです。ゲームといってもユーザにできることはライフの初期配置を決めることだけで、あとは画面上の変化を楽しむものです。万華鏡みたいなものですね。

ライフゲームはとても単純な規則から成り立っています。そのような単純な規則からさまざまな図形が生み出されます。その振舞いは非常に複雑でまるで生命のように感じられます。このように単純な規則から複雑な振舞いが生じることは人工生命分野では創発と呼ばれます。ライフゲームは人工生命分野の古典的プログラムと言えます。

ライフゲームで興味深い点は、ライフゲームの世界に生命を持った物体が存在する可能性があることです。えっ?コンピュータの中に生物がいるはずないって?世の中にはそう考えない人もいるんです。私たちが知っているタンパク質でできた生物がすべてではない。生命の本質は自己複製にあってタンパク質でできていようがソフトウェアでできていようが関係ないって・・・

ライフゲームの仮想世界で生物の自己再製を研究した人の中にはパソコンの原理を発明したフォン・ノイマンや人工生命の研究を始めたラングトンがいます。彼らは自己複製ループを実際に作り、生物と同じ現象を再現することに成功しています。

(注)フォン・ノイマンやラングトンが対象とした世界は見た目はライフゲームに似ていますが、ライフゲームよりはもっと複雑なセル・オートマトン(2012/1/13)という環境です。

詳細を知りたい方は参考文献を参照してください。

  • ライフゲームの世界 - ライフゲームの素晴らしい解説動画です。ライフゲームの深淵を垣間見ることができます(2013/1/5)

ライフゲームの規則

ライフゲームの1つのマスはセルと呼ばれます。セルとはドラゴンボールに出てくる・・・じゃなくて細胞のことですね。セルには「生」と「死」の2つの状態があります。「生」の状態は黄色の■です。「死」の状態は黒です。各セルは周囲8つのセルと接しています。セルの次の世代の状態は周囲の8つのセルの状態によって決まります。その規則はとても単純です。

  1. 生きているセルの周囲に2つまたは3つの生きているセルがあればそのセルは次の世代も生きている
  2. 死んでいるセルの周囲に3つの生きているセルがあればそのセルは次の世代で生き返る(子供が生まれる)
  3. それ以外の場合には次の世代で死ぬ

周囲に適度なセル(2つか3つ)があれば快適なので生き残れるがそれ以上いるとストレスで、少なすぎるとさびしくて死んでしまうってことですね。3ついると子供が生まれるって想像すると何か変ですがそういう決まりです(笑)。数にいくつか例を示します。
:plain
f:id:aidiary:20100814095902p:plain

面白いパターン

ライフゲームの研究を通して面白いパターンがたくさん見つかってます。下はその例です。入力する位置はどこでもいいんですが、パターンによって動く方向があるので説明を読んで適当に配置してみてください。

ブロック
永遠に変化がないパターンである固定物体の代表。

f:id:aidiary:20100814100726p:plain

タブ
これも固定物体。なんでタブ???

f:id:aidiary:20100814100727p:plain

蜂の巣
これも個体物体。見た目が蜂の巣に似てる。

f:id:aidiary:20100814100728p:plain

ボート
これも固定物体。見た目がボートに似てる。

f:id:aidiary:20100814100729p:plain

これも固定物体。ボートを少し豪華にしたので船かな。

f:id:aidiary:20100814100730p:plain

これも固定物体。池の形してる。よく出てくる。

f:id:aidiary:20100814100731p:plain

ブリンカー
ブリンカーはよく現れるパターンできらきらと点滅するような動きをする。

f:id:aidiary:20100814100732p:plain

蜂の巣箱
最終形が蜂の巣のような6角形になるためこう呼ばる。ブリンカーに1つ生きてるセルを付け加えるだけでまったく違う形に進化するのは不思議。

f:id:aidiary:20100814100733p:plain

Tテトロミノ
4個からできる面白いパターン。テトロミノとは4個の正方形を辺で接するように結合したいろいろな形を指す造語。TテトロミノはT字型のテトロミノという意味で交通信号と呼ばれる形に進化。

f:id:aidiary:20100814100734p:plain

交通信号
Tテトロミノの最終形。ブリンカーを4つ集めた形。

f:id:aidiary:20100814100735p:plain

グライダー
グライダーは構造を保ったまま動くパターンの代表例。4世代進むと元の形に戻り斜め方向に1セル分だけ移動する。

f:id:aidiary:20100814100736p:plain

Rペントミノ
セルの断片を空間にまき散らし、グライダーまで発射する。Rペントミノがいずれ安定するかは謎だったが1970年に1103世代で安定することがわかった(このスクリプトではフィールドが有限なので無理)。

f:id:aidiary:20100814100737p:plain

養蜂場
蜂の巣が4つの形に進化。蜂の巣と養蜂場の関係はブリンカーと交通信号の関係に似てる。

f:id:aidiary:20100814100738p:plain

ハーシェル
Rペントミノの48世代目に出てくる形。天文学者ハーシェルが発見した天王星の天文記号に似ていることが名前の由来。グライダーを2機飛ばして本体は爆発。爆発するロケットからの空中脱出みたいで楽しい。

f:id:aidiary:20100814100739p:plain

イーター1
イーターは近くにある物体を食い、自分自身はもとの形を保つ。イーターは好き嫌いが多く、食べられる物体は限られる。これはローフ(パン)を食べる例。

f:id:aidiary:20100814100740p:plain

イーター2
イーターがグライダーを食べる例。

f:id:aidiary:20100814100741p:plain

イーター3
イーター同士で共食いする例。

f:id:aidiary:20100814100742p:plain

ひきがえる
ひきがえるののどの部分に似た動き。膨らんだり縮んだりを永遠に繰り返す。このように何回も同じパターンを繰り返すものを振動子と呼ぶ。

f:id:aidiary:20100814100743p:plain

ビーコン
点滅装置。点滅・・・してる?ビーコンも振動子の一種。

f:id:aidiary:20100814100744p:plain

時計
時計が回転するように動く。これも振動子。

f:id:aidiary:20100814100745p:plain

パルサー
巨大な振動子。こんな簡単な初期配置から複雑な振動子ができるのは不思議。

f:id:aidiary:20100814100746p:plain

8の字
ビーコンを3倍でかくしたような形。大きく膨らんでまたもとの形に戻るという動きを繰り返す振動子。このようなパターンをパルセイターと呼ぶ。

f:id:aidiary:20100814100747p:plain

ペンタデカソロン
8の字と同様パルセイターの一種。大きく膨らんでもとの形に戻るという動きを繰り返す。

f:id:aidiary:20100814100748p:plain

床屋の看板
床屋にある看板のような動きをする振動子。斜めにいくらでも長く伸ばせる。

f:id:aidiary:20100814100749p:plain

フリップフロップ
回転しているように見える振動子。フリップフロップというのはコンピュータの記憶回路の名前だけどなぜ???

f:id:aidiary:20100814100750p:plain

銀河
渦を巻いている銀河のように見えるパルセイター。

f:id:aidiary:20100814100751p:plain

タンブラー
2匹の蛇が、目に見えない壁を登っては滑り落ちるようなかっこうらしい。

f:id:aidiary:20100814100752p:plain

時計II
まさに時計。真ん中の部分しか動かない。まわりに4つある■はブロック。この■は必要ないのでは?と思って取ってみると時計はとたんに壊れてしまう。

f:id:aidiary:20100814100753p:plain

グライダーシャトル
ペンタデカソロン2つの間にグライダーがあるという初期配置。このグライダーはペンタデカソロンに衝突すると180度反対の向きに移動し始める。ペンタデカソロンは無傷のままでグライダーは永遠に往復運動を繰り返す。

f:id:aidiary:20100814100754p:plain

宇宙船
グライダーと同じく移動するパターン。グライダーは斜め移動だが宇宙船は回転しながらまっすぐ飛ぶ。

f:id:aidiary:20100814100755p:plain

シャトル
往復運動をするパターンをシャトルと呼ぶ。ブロックの間をシャトルがいったりきたりする。反転するときの逆噴射がかっこいい。

f:id:aidiary:20100814100756p:plain

Bヘプトミノ
往復運動のパターン。いかにも壊れそうだけど壊れずに往復運動を続ける。逆噴射も出る。

f:id:aidiary:20100814100757p:plain

アクロン
Rペントミノと同じく爆発的に成長する形です。5206世代で安定することが示されている(このスクリプトではフィールドが有限なので無理)。

f:id:aidiary:20100814100758p:plain

グライダー銃
グライダー銃は永遠に成長を続ける形。ライフゲームの作者コンウェイは永遠に成長できる形を最初に見つけた者に50ドルの懸賞金をかけていた。この難問に挑戦したのがMITの学生グループでこのグライダー銃を発見して50ドルを受け取った。

f:id:aidiary:20100814100759p:plain

パイヘプトミノ
これも永遠に成長を続ける形。前進しながら後ろに煙を撒き散らして進む。

f:id:aidiary:20100814100800p:plain

空飛ぶ機械
シュシュポッポ列車のように前進しながら煙を撒き散らすが煙は時間が経つと消滅する。

f:id:aidiary:20100814100801p:plain

ソースコード

#!/usr/bin/env python
#coding:utf-8
import pygame
from pygame.locals import *
import random
import sys

SCR_RECT = Rect(0, 0, 800, 600)  # スクリーンサイズ
CS = 10  # セルのサイズ
NUM_ROW = SCR_RECT.height / CS   # フィールドの行数
NUM_COL = SCR_RECT.width / CS  # フィールドの列数
DEAD, ALIVE = 0, 1  # セルの生死定数
RAND_LIFE = 0.1

class LifeGame:
    def __init__(self):
        pygame.init()
        screen = pygame.display.set_mode(SCR_RECT.size)
        pygame.display.set_caption(u"Conway's Game of Life")
        self.font = pygame.font.SysFont(None, 16)
        # NUM_ROW x NUM_COLサイズのフィールド(2次元リスト)
        self.field = [[DEAD for x in range(NUM_COL)] for y in range(NUM_ROW)]
        self.generation = 0  # 世代数
        self.run = False  # シミュレーション実行中か?
        self.cursor = [NUM_COL/2, NUM_ROW/2]  # カーソルの位置
        # ライフゲームを初期化
        self.clear()
        # メインループ
        clock = pygame.time.Clock()
        while True:
            clock.tick(60)
            self.update()
            self.draw(screen)
            pygame.display.update()
            for event in pygame.event.get():
                if event.type == QUIT:
                    pygame.quit()
                    sys.exit()
                elif event.type == KEYDOWN:
                    if event.key == K_ESCAPE:
                        pygame.quit()
                        sys.exit()
                    # 矢印キーでカーソルを移動
                    elif event.key == K_LEFT:
                        self.cursor[0] -= 1
                        if self.cursor[0] < 0: self.cursor[0] = 0
                    elif event.key == K_RIGHT:
                        self.cursor[0] += 1
                        if self.cursor[0] > NUM_COL-1: self.cursor[0] = NUM_COL-1
                    elif event.key == K_UP:
                        self.cursor[1] -= 1
                        if self.cursor[1] < 0: self.cursor[1] = 0
                    elif event.key == K_DOWN:
                        self.cursor[1] += 1
                        if self.cursor[1] > NUM_ROW-1: self.cursor[1] = NUM_ROW-1
                    # スペースキーでカーソルのセルを反転
                    elif event.key == K_SPACE:
                        x, y = self.cursor
                        if self.field[y][x] == DEAD:
                            self.field[y][x] = ALIVE
                        elif self.field[y][x] == ALIVE:
                            self.field[y][x] = DEAD
                    # sキーでシミュレーション開始
                    elif event.key == K_s:
                            self.run = not self.run
                    # nキーで1世代だけ進める
                    elif event.key == K_n:
                        self.step()
                    # cキーでクリア
                    elif event.key == K_c:
                        self.clear()
                    # rキーでランダムに生きているセルを追加
                    elif event.key == K_r:
                        self.rand()
                elif event.type == MOUSEBUTTONDOWN and event.button == 1:
                    # 左ボタンクリックでセルを反転
                    px, py = event.pos
                    x, y = px/CS, py/CS
                    self.cursor = [x, y]
                    if self.field[y][x] == DEAD:
                        self.field[y][x] = ALIVE
                    elif self.field[y][x] == ALIVE:
                        self.field[y][x] = DEAD
    def clear(self):
        """ゲームを初期化"""
        self.generation = 0
        for y in range(NUM_ROW):
            for x in range(NUM_COL):
                self.field[y][x] = DEAD
    def rand(self):
        """ランダムに生きているセルを追加"""
        for y in range(NUM_ROW):
            for x in range(NUM_COL):
                if random.random() < RAND_LIFE:
                    self.field[y][x] = ALIVE
    def update(self):
        """フィールドを更新"""
        if self.run:
            self.step()  # 1世代進める
    def step(self):
        """1世代だけ進める"""
        # 次のフィールド
        next_field = [[False for x in range(NUM_COL)] for y in range(NUM_ROW)]
        # ライフゲームの規則にしたがって次のフィールドをセット
        for y in range(NUM_ROW):
            for x in range(NUM_COL):
                num_alive_cells = self.around(x, y)
                if num_alive_cells == 2:
                    # 周囲の2セルが生きていれば維持
                    next_field[y][x] = self.field[y][x]
                elif num_alive_cells == 3:
                    # 周囲の3セルが生きていれば誕生
                    next_field[y][x] = ALIVE
                else:
                    # それ以外では死亡
                    next_field[y][x] = DEAD
        self.field = next_field
        self.generation += 1
    def draw(self, screen):
        """フィールドを描画"""
        # セルを描画
        for y in range(NUM_ROW):
            for x in range(NUM_COL):
                if self.field[y][x] == ALIVE:
                    pygame.draw.rect(screen, (255,255,0), Rect(x*CS,y*CS,CS,CS))
                elif self.field[y][x] == DEAD:
                    pygame.draw.rect(screen, (0,0,0), Rect(x*CS,y*CS,CS,CS))
                pygame.draw.rect(screen, (50,50,50), Rect(x*CS,y*CS,CS,CS), 1)  # グリッド
        # 中心線を描く
        pygame.draw.line(screen, (255,0,0), (0,SCR_RECT.height/2), (SCR_RECT.width,SCR_RECT.height/2))
        pygame.draw.line(screen, (255,0,0), (SCR_RECT.width/2,0), (SCR_RECT.width/2,SCR_RECT.height))
        # カーソルを描画
        pygame.draw.rect(screen, (0,0,255), Rect(self.cursor[0]*CS,self.cursor[1]*CS,CS,CS), 1)
        # ゲーム情報を描画
        screen.blit(self.font.render("generation:%d" % self.generation, True, (0,255,0)), (0,0))
        screen.blit(self.font.render("space : birth/kill", True, (0,255,0)), (0,12))
        screen.blit(self.font.render("s : start/stop", True, (0,255,0)), (0,24))
        screen.blit(self.font.render("n : next", True, (0,255,0)), (0,36))
        screen.blit(self.font.render("r : random", True, (0,255,0)), (0,48))
    def around(self, x, y):
        """(x,y)の周囲8マスの生きているセルの数を返す"""
        if x == 0 or x == NUM_COL-1 or y == 0 or y == NUM_ROW-1:
            return 0
        sum = 0
        sum += self.field[y-1][x-1]  # 左上
        sum += self.field[y-1][x]    # 上
        sum += self.field[y-1][x+1]  # 右上
        sum += self.field[y][x-1]    # 左
        sum += self.field[y][x+1]    # 右
        sum += self.field[y+1][x-1]  # 左下
        sum += self.field[y+1][x]    # 下
        sum += self.field[y+1][x+1]  # 右下
        return sum

if __name__ == "__main__":
    LifeGame()

参考文献

  • ライフゲイムの宇宙 - おすすめの本です。ライフゲームの説明だけでなく、熱力学や現代物理学、天文学、生物学の話題も散りばめられています。少し難しいですがとても面白いです。初版は1990年ですが2003年に復刊されました。

ライフゲイムの宇宙

ライフゲイムの宇宙

  • 作者: ウィリアム・パウンドストーン,William Poundstone,有澤誠
  • 出版社/メーカー: 日本評論社
  • 発売日: 2003/06/12
  • メディア: 単行本
  • 購入: 5人 クリック: 280回
  • この商品を含むブログ (41件) を見る

  • Conway's Game of Life - ライフゲームの素晴らしいアプレットがあります。私のものより広い範囲を見られます。
  • ライフゲーム - Wikipedia - ライフゲームの詳しい解説や参考文献へのリンクがあります。