[알고리듬] #83 라이프 게임

[key word]  생명체 게임, game of life, 콘웨이, 유전 법칙

파이썬 실습창을 열 수 있습니다.실습창 열기

 

라이프 게임

1. 라이프 게임의 이해

라이프 게임(Conway's Game of life)은 생물의 생존 주기(life cycle)를 시뮬레이트(simulate)한 것으로 케임브리지 대학의 J. Conway에 의하여 고안되었습니다. 인간(또는 생물)의 사회에서 인구 과밀이나 과소 때문에 인구의 감소가 일어나거나 다른 장소에 새로운 사회가 생기거나 합니다. 이러한 인구 분포의 변화를 초기의 적당한 인구 분포에서 어떤 규칙에 따라 시뮬레이트한 것이 이 게임입니다.

 

 

 

생명체의 주변에는 8개의 칸이 있습니다. 가장자리의 경우 3칸 또는 5칸이 있는 경우도 있습니다. 어떠한 경우이든 Conway는 genetic law(유전 법칙)라고 하여 다음 3가지를 고려하였습니다.

• 탄생: 주변에 꼭 3개의 생명체가 존재하는 경우,
• 사망: 주변에 1개 이하 또는 4개 이상 생명체가 존재하는 경우.
• 생존: 주변에 2개 또는 3개의 생명체가 존재하는 경우.

 

위의 원래의 유전 법칙을 다시 정리하면 다음과 같습니다.

• 생명체가 없는 경우: 주변에 꼭 3개의 생명체가 있으면 다음 세대에는 그곳에 생명체가 살게 된다.
• 생명체가 있는 경우: 주변에 2개 또는 3개의 생명체가 있으면 다음 세대에도 생명체가 살아 있다.
• 그 외의 경우에는 다음 세대에 그곳에 생명체가 없다.

 

위의 그림으로 유전 법칙의 예를 들겠습니다.

위의 그림에서 왼쪽은 현재 세대이며 오른쪽은 다음 세대입니다. 노란 점은 생명체가 있는 상태이고(alive), 회색은 없는 상태입니다(dead). 왼쪽 가장 위의 노란 점을 봅시다. 이 생명체의 주변 8곳에는 1개의 생명체만 있습니다. 그러므로 다음 세대(오른쪽 그림의 화살표 지점)에는 소멸했습니다. 그러나 왼쪽 가장 위의 노란 점 오른쪽은 생명체가 없는 곳이었지만 주변에 3개의 생명체가 있으므로 다음 세대에서 그곳에 생명체가 살게 됩니다(화살 표 오른쪽).

유전 법칙에 따른 위의 세대 변화를 완전히 이해하세요.

 

2. 자료 조사

인터넷 등에서 Game of life에 대하여 조사 하여 보세요.

바로 가기

생명체의 초기 분포는 변화가 없는 고정된 패턴(정물, still life), 일정한 행동을 주기적으로 반복하는 패턴(진동자, oscillator), 한쪽방향으로 계속 전진하는 패턴(우주선, spaceship) 등 여러 패턴이 존재합니다.

우리는 'game of life' 프로그램을 작성하여 이러한 패턴의 변화를 확인하려고 합니다.

 

3. 코딩의 예

import copy
grid=[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],         # 지금 세대 field.
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
      [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
      [0, 0, 0, 1, 1, 1, 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, 0, 0, 0, 0, 0, 0, 0, 0]]
next=copy.deepcopy(grid)                       # 다음 세대 field 
di=[0,1,1,1,0,-1,-1,-1]                        # 8방향 direction check data
dj=[1,1,0,-1,-1,-1,0,1]
n=10                                           # field size
for loop in range(10):                         # 임읭의 세대 cycle 개수
    for i in range(n):                         # field 출력
        for j in range(n):
            s+=grid[i][j]
            print('□■'[grid[i][j]],end=' ')
        print()    
    print()    
    for i in range(n):                          # 다음 세대 생성. 순서대로 모두 조사 
        for j in range(n):
            s=0                                 # 지금 세대의 주변 생명체 개수 조사
            for k in range(8):                  # 8방향 조사 
                ti=i+di[k]
                tj=j+dj[k]
                if 0<=ti<n and 0<=tj<n:         # sentinel(보초)를 둘 수 있다.
                    s+=grid[ti][tj]
            next[i][j]=int((grid[i][j] and s in [2,3]) or (s in [3]))
    grid=copy.deepcopy(next)                    # 다음 세대를 현 세댸로 deep copy

 

출력의 예입니다.

 

 

방향 데이터의 표준적인 사용 예입니다.

충분히 연구하세요.

안녕!