라이프 게임
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)’은 우주선에 속한다. 그리고 무한히 이을 수 있는 패턴들이 있는데, 예를 들어 배(boat)는 무한정 이을 수 있다.
진동자 또는 정물로 수렴하기까지 많은 세대가 필요한 패턴도 있는데, ‘methuselah(므두셀라)’라고 불린다. 고대 로마에서 유래된 펜토미노 퍼즐의 모양 중 R-펜토미노(R-Pentomino)는 세포는 5개이지만 1130세대가 지나서야 안정화된다. (이는 6개 미만 세포 패턴 중 가장 활동적인 패턴이다.) ‘다이하드(diehard)’는 130세대가 지나서야 사라진다. ‘도토리(acorn)’는 5206세대가 지나서야 13개의 글라이더(glider)와 수많은 진동자 또는 정물을 남기고 안정화된다. 지금까지 발견된 패턴 중 진동자 또는 정물로 수렴하기까지 가장 많은 세대를 거친 패턴은 리드카(Lidka)로, 무려 29,055 세대가 지나야 안정화된다.
|
|
| diehard | acorn |
라이프 게임이 처음 소개된 〈Mathematical Games〉에서, 콘웨이는 세포 수가 무한히 많아지는 패턴을 찾은 사람에게 상금을 걸었다.
해커 빌 가스퍼(Bill Gosper)가 1970년 11월에 처음 그러한 패턴들을 찾아 상금을 탔다. 패턴들 가운데에는 ‘글라이더’나 ‘우주선’을 발사하는 ‘총’과 안정화한 패턴들을 꼬리에 남기며 전진하는 ‘기관차’, 그리고 양쪽을 다 행하는 ‘갈퀴’ 패턴이 있었다. 그는 또한 제곱 비례로 성장하는 패턴인 ‘사육사’ 패턴도 찾아냈는데, 이것은 ‘총’ 패턴을 꼬리에 남기며 앞으로 전진한다. 이 후로 글라이더를 이용한 논리 게이트, 가산기, 소수 발생기와 라이프 게임을 더 큰 스케일과 느린 속도로 모방하는 단위 세포 등 다양한 패턴들이 만들어졌다.
맨 처음 발견된 ‘총’이 여전히 알려진 가장 작은 총이다:
무한히 성장하는 더 단순한 패턴들이 그 후에도 발견되었다. 아래의 세 패턴은 모두 무한히 성장한다. 처음 것은 10개의 살아있는 세포만을 가지며 이보다 적은 세포를 가진 무한 성장 패턴은 존재하지 않음이 증명되었다. 두 번째 것은 5x5의 정사각형 안에 포함되는 패턴이고, 세 번째는 두께가 1인 패턴이다.
 
|
|
여러 개의 글라이더가 합성되어 재미있는 결과를 형성하는 경우도 있다. 만약 두 개의 글라이더를 적당한 방법으로 블록에 충돌시키면, 블록은 글라이더가 발사된 곳을 향해 한 칸 다가간다. 세 개의 글라이더를 다른 방법으로 충돌시키면 블록은 발사된 곳의 반대 방향으로 한 칸 다가간다. 이것은 ‘움직이는 블록 메모리’라고 불리며 카운터를 모방하는 데 사용할 수 있다. 글라이더를 이용해 AND, OR, NOT 게이트를 만드는 것도 가능하다. 두 개의 카운터와 연결된 유한 상태 오토마타를 만들 수도 있는데, 이것은 만능 튜링 기계와 똑같은 계산능력을 가지며, 이는 라이프 게임이 무한한 메모리를 가진 어떤 컴퓨터와도 동등한 계산능력을 가짐을 의미한다. 글라이더 건의 패턴을 이용하여 새로운 개체를 조합하는 것도 가능하며, 원본의 복제물을 만드는 것도 가능하다. 또한 ‘만능 건축사’ 패턴은 튜링 머신과 동등한 컴퓨터를 만들 수 있으며, 이것은 더 복잡한 여러 가지 개체를 만들어내는 데 사용될 수 있다.
라이프 게임의 변종들[편집]
이 부분의 본문은 라이프형 세포 자동자입니다.라이프 게임을 시작으로, 몇 가지 새로운 규칙을 가진 변종들이 존재한다. 원래의 라이프 게임은 3개의 이웃 세포가 살아있을 때 태어나며, 2개 또는 3개의 이웃 세포가 살아있을 때 생존하고 나머지 경우에는 사망한다. 이 규칙은 ‘23/3’으로 표시할 수 있다. 앞쪽 숫자들은 세포가 생존하기 위한 숫자를 의미하며, 뒤쪽 숫자들은 세포가 새로 태어나기 위한 숫자를 의미한다. 그러므로 ‘16/6’은 6개의 이웃이 존재할 때 세포가 새로 태어나고, 1개나 6개의 이웃이 존재할 때 생존하며 나머지 경우 사망하는 규칙을 가짐을 의미한다. 하이라이프(HighLife) 규칙은 원래 규칙에 6개의 이웃이 존재할 때 새로 태어난다는 규칙이 추가되며, 이는 ‘23/36’으로 표시된다. HighLife는 ‘복제자’ 패턴들로 유명하지만, 이 규칙의 대부분의 패턴들이 너무 복잡하거나 황폐한 패턴들을 생성한다.
- Diamoeba 5678/35678 (혼돈스럽다) 다이아몬드 모양 패턴들. 종종 파국적으로 멸망함
- Seeds /2 (폭발적) 불사조(몇 개의 남은 세포들로부터 폭발적으로 부활함), 간결한 패턴들
- Serviettes/234 (폭발적) 불사조, 레이스 무늬 패턴들
- Maze 12345/3 (폭발적) 미로같은 패턴
- Mazectric 1234/3 (폭발적) Maze와 아주 비슷함. Maze보다 덜 막혀있음
- 2x2 125/36 (혼돈스럽다) 2x2 블록 패턴이 출몰함
- Replicator 1357/1357 (폭발적) 모든 패턴이 복제자 패턴이다. Replicator은 복제자 패턴이란 뜻이다
- Amoeba 1358/357 (혼돈스럽다) 아메바형 패턴
- Conway's game of life 23/3 (혼돈스럽다) ‘라이프 게임’
- Highlife 23/36 (혼돈스럽다) ‘하이라이프’ (복제자 패턴이 등장한다)
- Stains 235678/3678 (안정적) 잉크 방울이 마르는 것 같은 패턴을 보여준다
- Coagulations 235678/378 (폭발적) 혼돈스러운 패턴과 응고하는듯한 정착 패턴들
- Pseudo life 238/357 (혼돈스럽다)
- Move 245/368 (안정적) 기관차와 우주선 패턴들
- 34/34 (폭발적) ‘34 Life’
- 34678/3678 (폭발적) ‘낮과 밤(Day & Night)’
- Coral 45678/3 (폭발적) 산호초 모양으로 성장한다
- 5/346 (안정적) ‘Long life’
- Assimilation 4567/345 (혼돈스럽다)
- Life without death 012345678/3 (폭발적)
- Gnarl 1/1 (폭발적)
- Walled cities 2345/45678 (안정적)
- Pylamid /12345678 피라미드 형태
- Sponge cells 01234567/456 (안정적) 스폰지 모양
- wired life 23/3678 (혼돈스러움) 약간 오래 가는 life
- 1 life 13/3 작은 막대 패턴과 진동자들
- drill 245678/3 막대가 나오는 듯한 패턴
- h tree 012345678/1 결정 또는 나무 모양으로 성장함
- rats in maze 1234/37 미로 안쪽에서 움직이는 세포들
- repilcater2 02468/1357 (폭발적) 복제자 패턴과 비슷함
- wired life 37 23/37 () 일반 라이프보다 이상한 희귀 패턴이나 펄사가 매우 자주 나옴
Life32/game of life 프로그램에 따름.
