Python Programming

Lecture 7 Complex Systems, Game of Life

7.1 Complex Systems

  • The game in Lecture 2 is boring. Why?

  • Each challenge is a unique puzzle, and each puzzle has a unique action that solves it.

  • In Tetris, the challenge is created by a combination of a random sequence of tetrominoes and the player's previous actions in dealing with them.

Games of Emergence

  • Games of emergence have a high replay value because the challenges and possible actions that occur while playing are different every time.

  • It is very hard to predict whether interesting gameplay will emerge from a particular game simply by looking at the rules.

  • It should be clear that creating emergence is not simply a matter of having many rules. You cannot create a more interesting game simply by adding more rules. In fact, sometimes it is more effective to reduce the number of rules to create a system that displays truly interesting and emergent gameplay.

Complex Systems

  • The system consists of many parts.

  • These parts are often quite simple to understand and to model individually. (The Butterfly Effect)

  • When these parts are put together, most complex systems display surprising and unpredictable behavior that can be difficult to explain just by looking at the parts separately.

  • Can emergence be Designed?

  • Cellular Automaton (元胞自动机)

    • At the boundary of mathematics, computer science, and games lies a peculiar field that studies cellular automaton.

    • Cellular automaton is a simple set of rules governing the appearance of spaces, or cells, in a line or on a grid.

    • Each cell may be either black or white. The rules determine what causes a cell to change from black to white (or vice versa) and how the color of a cell influences the cells around it.

    • Mathematicians think of such a collection of rules as a hypothetical machine that operates by itself without human intervention. This is why they are called automata.

  • A cellular automaton starts with its cells in a given configuration (some white, some black) and then applies the rules to each cell to determine whether its color should change.

  • It does not change a cell immediately; it checks every cell in the grid first, marks the ones to be changed, and then changes them all before the next iteration. Then it repeats the process. Each iteration is called a generation.

  • British scientist Stephen Wolfram has created a simple cellular automaton that exhibits emergent behavior.

  • He was named an inaugural fellow of the American Mathematical Society. he is the founder and CEO of the software company Wolfram Research where he worked as chief designer of Mathematica and the Wolfram Alpha answer engine.

The simple cellular automaton

  • It displays one set of possible rules and the resulting, surprisingly complex pattern that is created by printing each new generation of the system under the previous one. It begins with one black cell and all the rest white.

  • Notice that even though there is nothing random in the rules, this cellular automaton produces a pattern with distinctive and apparently random features.

  • Wolfram described his work in detail in his book A New Kind of Science (2002).

    • They must consist of simple cells whose rules are defined locally.

    • The system must allow for long-range communication.

    • The level of activity of the cells is a good indicator for the complexity of the behavior of the system.

    • Cellular automata show us that the threshold for complexity is surprisingly low.

    • Application

    • Let's build this simple model with Python.


import os

width = 100
height = 1
screen = []

Step 1: Initialization


def Init():
    for i in range(height):
        line = []
        for j in range(width):
            line.append(' ')
        screen.append(line)
    screen[0][50]='#'

Step 2: Show the screen


def PrintScreen():
    for i in range(len(screen)):
        for j in range(width):
            print(screen[i][j] + ' ', end='')
        print('|')

Step 3: Add a new generation


def Update():
    s = len(screen); line = []
    for j in range(width):
        line.append(' ')
    screen.append(line)
    for j in range(width-1):
        if screen[s-1][j-1]=='#' and screen[s-1][j]=='#' and screen[s-1][j+1]=='#':
            screen[s][j] = ' '
        elif screen[s-1][j-1]=='#' and screen[s-1][j]=='#' and screen[s-1][j+1]==' ':
            screen[s][j] = ' '
        elif screen[s-1][j-1]=='#' and screen[s-1][j]==' ' and screen[s-1][j+1]=='#':
            screen[s][j] = ' '
        elif screen[s-1][j-1]=='#' and screen[s-1][j]==' ' and screen[s-1][j+1]==' ':
            screen[s][j] = '#'
        elif screen[s-1][j-1]==' ' and screen[s-1][j]=='#' and screen[s-1][j+1]=='#':
            screen[s][j] = '#'
        elif screen[s-1][j-1]==' ' and screen[s-1][j]=='#' and screen[s-1][j+1]==' ':
            screen[s][j] = '#'
        elif screen[s-1][j-1]==' ' and screen[s-1][j]==' ' and screen[s-1][j+1]=='#':
            screen[s][j] = '#'
        elif screen[s-1][j-1]==' ' and screen[s-1][j]==' ' and screen[s-1][j+1]==' ':
            screen[s][j] = ' '

Step 4: Console


def Start():
    os.system("cls")
    print('== Game of Life ==')
    print('Press any key...')
    input()
    os.system("cls")
    Init()
    PrintScreen()
    c = input()
    while c!= 'q':
        os.system("cls")
        Update()
        PrintScreen()   
        c = input()
    print('End')

Start()

Command line

7.2 Game of Life

Game of Life

  • Probably the most famous cellular automaton was invented by John Conway and is called the Game of Life.

  • Conway was a Professor Emeritus of Mathematics at Princeton University in New Jersey.

  • Conway's automaton consists of cells that are laid out on a two-dimensional grid.

  • this grid goes on indefinitely in all directions. Each cell on the grid has eight neighbors: the cells that surround it orthogonally and diagonally. Each cell can be in two different states: It is either dead or alive.

  • In most examples, dead cells are rendered white, while live cells are colored black.

Rules

  • A live cell that has fewer than two live neighbors dies from loneliness.

  • A live cell that has more than three live neighbors dies from overcrowding.

  • A live cell that has two or three live neighbors stays alive.

  • A dead cell that has exactly three live neighbors becomes alive.

Example

  • When set into motion, the Game of Life usually has quite chaotic results, with a lot of activity exploding from its original live cells.

  • Demo: Game of Life (Random)

  • Frequently after a number of iterations the Game of Life settles in a more or less stable configuration, sometimes with a few groups of cells that oscillate between two states.


import os
import random

width = 60
height = 60
screen = []

Step 1: Initialization


def Init():
    for i in range(height):
        line = []
        for j in range(width):
            if random.random() > 0.8:
                line.append('#')
            else:
                line.append(' ')
        screen.append(line)

Step 2: Show the screen


def PrintScreen():
    for i in range(height):
        for j in range(width):
            print(screen[i][j] + ' ', end='')
        print()

Step 3: Get cells


def TryGetCell(i, j):
    i = i % height
    j = j % width
    return screen[i][j]

Step 4: Count cells nearby


def GetNearbyCellsCount(i, j):
    nearby = []
    nearby.append(TryGetCell(i - 1, j - 1))
    nearby.append(TryGetCell(i - 1, j))
    nearby.append(TryGetCell(i - 1, j + 1))
    nearby.append(TryGetCell(i, j - 1))
    nearby.append(TryGetCell(i, j + 1))
    nearby.append(TryGetCell(i + 1, j - 1))
    nearby.append(TryGetCell(i + 1, j))
    nearby.append(TryGetCell(i + 1, j + 1))
    num = 0
    for x in nearby:
        if x == '#':
            num = num + 1
    return num

Step 5: Update


def Update():
    global screen
    newScreen = []
    for i in range(height):
        line = []
        for j in range(width):
            line.append(' ')
        newScreen.append(line)
    for i in range(height):
        for j in range(width):
            count = GetNearbyCellsCount(i, j)
            if count == 3:
                newScreen[i][j] = '#'
            elif count < 2 or count > 3:
                newScreen[i][j] = ' '
            else:
                newScreen[i][j] = screen[i][j]    
    screen = newScreen

Step 6: Console


def Start():
    os.system("cls")
    print('== Game of Life ==')
    print('Press any key...')
    input()
    os.system("cls")
    Init()
    PrintScreen()
    c = input()
    while c!= 'q':
        os.system("cls")
        Update()
        PrintScreen()   
        c = input()
    print('End')

Start()
  • One of the earliest questions that the researchers studying the Game of Life asked themselves was this: "Is there an initial configuration of live cells that expands forever?"

  • glider

  • Demo: glider

  • Glider gun

Summary

  • Functions
    • Reading: Python for Everybody, Chapter 10.1-10.5, 10.7-10.8
    • Reading: Python Crash Course, Chapter 8