라이프 게임

Hasbro의 보드 게임인 인생 게임도 가끔 ‘라이프 게임’으로 불린다.

‘글라이더’ 패턴의 진행.

라이프 게임(Game of Life) 또는 생명 게임은 영국의 수학자 존 호턴 콘웨이가 고안해낸 세포 자동자의 일종으로, 가장 널리 알려진 세포 자동자 가운데 하나이다.

미국의 과학 잡지 사이언티픽 어메리칸 1970년 10월호 중 마틴 가드너의 칼럼 〈Mathematical Games(수학 게임)〉란을 통해 처음으로 대중들에게 소개되어 단순한 규칙 몇가지로 복잡한 패턴을 만들어낼 수 있다는 점 때문에 많은 관심과 반응을 불러일으켰다. 라이프 게임은 컴퓨터 과학에서도 의미가 있는데, 왜냐하면 라이프 게임이 범용 튜링 기계와 동등한 계산능력을 가진 세포 자동자이기 때문이다. 즉, 어떤 알고리즘에 의해 계산될 수 있는 것이라면 모두 이를 이용하여 계산할 수 있다.

설명[편집]

이 ‘게임’은 사실 게임을 하는 사람이 자신의 의지로 게임의 진행을 결정하는 일반적인 게임과는 약간 많이 다르다. 라이프 게임의 진행은 처음 입력된 초기값만으로 완전히 결정된다.

라이프 게임은 무한히 많은 사각형(혹은 ‘세포’)로 이루어진 격자 위에서 돌아간다. 각각의 세포 주위에는 인접해 있는 여덟 개의 ‘이웃 세포’가 있으며, 또 각 세포는 ‘죽어’ 있거나 ‘살아’ 있는 두가지 상태 중 한가지 상태를 갖는다(‘켜져’ 있거나 ‘꺼져’ 있다는 표현을 쓰기도 한다). 격자를 이루는 세포의 상태는 연속적이 아니라 이산적으로 변화한다. 즉, 현재 세대의 세포들 전체의 상태가 다음 세대의 세포 전체의 상태를 결정한다.

각각의 세포가 다음 세대에서 갖는 상태는 현재 자신의 상태와 이웃하는 여덟 개의 세포들 중 몇 개가 살아있는 상태인지만을 따져서 결정된다.

죽은 세포의 이웃 중 정확히 세 개가 살아 있으면 그 세포는 살아난다(‘태어난다’).
살아 있는 세포의 이웃 중에 두 개나 세 개가 살아 있으면, 그 세포는 계속 살아 있는 상태를 유지하고, 이외에는 ‘외로워서’, 또는 ‘숨이 막혀서’ 죽어버린다.

패턴의 예[편집]

라이프 게임에는 전혀 변화가 없는 고정된 패턴(정물 靜物, still life), 일정한 행동을 주기적으로 반복하는 패턴(진동자, oscillator — 정물은 주기가 한 세대인 진동자임), 한쪽 방향으로 계속 전진하는 패턴(우주선, spaceship) 등 여러 패턴이 존재한다. 아래에 간단한 예가 있다. 살아 있는 셀은 검은 색으로, 죽어 있는 셀은 흰색으로 표현했다.


block	배(boat)	깜빡이(blinker)	두꺼비(toad)	글라이더(glider)	LWSS

‘block’과 ‘boat’는 정물이고, ‘blinker’와 ‘toad’는 진동자, 그리고 ‘글라이더(glider)’와 ‘경량급 우주선(lightweight spaceship — LWSS)’은 우주선에 속한다.

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com

진동자로 수렴하기까지 많은 세대가 필요한 패턴도 있는데, ‘methuselah(므두셀라)’라고 불린다. ‘다이하드(diehard)’는 130세대가 지나서야 사라진다. ‘도토리(acorn)’는 5206세대가 지나서야 13개의 글라이더(glider)와 수많은 진동자를 남기고 안정화된다.지금까지 발견된 패턴 중 진동자로 수렴하기까지 가장 많은 세대를 거친 패턴은 리드카(Lidka)로, 무려 29,055 세대가 지나야 안정화된다.


diehard	acorn

라이프 게임이 처음 소개된 〈Mathematical Games〉에서, 콘웨이는 세포 수가 무한히 많아지는 패턴을 찾은 사람에게 상금을 걸었다.

해커 빌 가스퍼(Bill Gosper)가 1970년 11월에 처음 그러한 패턴들을 찾아 상금을 탔다. 패턴들 가운데에는 ‘글라이더’나 ‘우주선’을 발사하는 ‘총’과 안정화한 패턴들을 꼬리에 남기며 전진하는 ‘기관차’, 그리고 양쪽을 다 행하는 ‘갈퀴’ 패턴이 있었다. 그는 또한 제곱 비례로 성장하는 패턴인 ‘사육사’ 패턴도 찾아냈는데, 이것은 ‘총’ 패턴을 꼬리에 남기며 앞으로 전진한다. 이 후로 글라이더를 이용한 논리 게이트, 가산기, 소수 발생기와 라이프 게임을 더 큰 스케일과 느린 속도로 모방하는 단위 세포 등 다양한 패턴들이 만들어졌다.

맨 처음 발견된 ‘총’이 여전히 알려진 가장 작은 총이다:

가스퍼의 글라이더 건

무한히 성장하는 더 단순한 패턴들이 그 후에도 발견되었다. 아래의 세 패턴은 모두 무한히 성장한다. 처음 것은 10개의 살아있는 세포만을 가지며 이보다 적은 세포를 가진 무한 성장 패턴은 존재하지 않음이 증명되었다. 두 번째 것은 5x5의 정사각형 안에 포함되는 패턴이고, 세 번째는 두께가 1인 패턴이다.

여러 개의 글라이더가 합성되어 재미있는 결과를 형성하는 경우도 있다. 만약 두 개의 글라이더를 적당한 방법으로 블록에 충돌시키면, 블록은 글라이더가 발사된 곳을 향해 한 칸 다가간다. 세 개의 글라이더를 다른 방법으로 충돌시키면 블록은 발사된 곳의 반대 방향으로 한 칸 다가간다. 이것은 ‘움직이는 블록 메모리’라고 불리며 카운터를 모방하는 데 사용할 수 있다. 글라이더를 이용해 AND, OR, NOT 게이트를 만드는 것도 가능하다. 두 개의 카운터와 연결된 유한 상태 오토마타를 만들 수도 있는데, 이것은 만능 튜링 기계와 똑같은 계산능력을 가지며, 이는 라이프 게임이 무한한 메모리를 가진 어떤 컴퓨터와도 동등한 계산능력을 가짐을 의미한다. 글라이더 건의 패턴을 이용하여 새로운 개체를 조합하는 것도 가능하며, 원본의 복제물을 만드는 것도 가능하다. 또한 ‘만능 건축사’ 패턴은 튜링 머신과 동등한 컴퓨터를 만들 수 있으며, 이것은 더 복잡한 여러 가지 개체를 만들어내는 데 사용될 수 있다.