John Conway's Game of Life

This document has been changed since it was first released.

To see the list of changes see section entitled Changes at the end of this specification.

Introduction

The Game

Life is played on a rectangular grid of arbitrary size which we shall henceforth refer to as the board. Each square of the board is known as a cell and these can be either live or dead. Each cell has eight adjacent cells, that is orthogonally as well as diagonally opposed cells included. Figure 1 illustrates this; the eight white squares in the diagram below are adjacent to the black one.

Example

The Rules

There are only two rules:

1. A live cell with exactly two or three adjacent cells stays alive. Otherwise the cell dies.
2. A dead cell with exactly three adjacent cells comes to life (i.e. becomes a live cell). Otherwise it remains dead.

Boundary cases

A cell at a corner of the board only has three adjacent cells, while one on the edge but not in a corner has only five. The cells which lie "outside the board" so to speak can be though of as being dead. That is, for the purposes of applying the rules you can think of the board has being surrounded by a border of dead cells that is one cell in thickness.

Playing the Game

Life is a zero player game. It's behaviour is completely determined by the initial state of the board. Each turn in the game is known as a generation and applying the rules is known as evolving the board. The generations are numbered from zero so that the initial state of the board is generation zero.

The rules are applied in no particular order to the individual cells. They may be thought of as being updated simultaneously.

Example

This figure shows the initial board and the subsequent two generations. Interestingly, Generation 2 is what is known as a stable configuration. Applying the rules to this arrangement of cells will lead to the same configuration. Try it and see.

Example

Representation in Haskell

Cells are represented by booleans. True and False represent live and dead cells respectively.

type Cell = Bool

The board is represented as a list of lists of cells. Each list represents a column of the board and all such lists are equal in length.

type Board = [[Cell]]

The Location type represents the coordinates of a cell in the world.

type Location = (Int,Int)

The world is represented by a pair. The first component is the location of the top right hand corner of the board. The locations of cells range from (0,0) to this value. The second component of the pair is the board itself.

As mentioned above, the board is as a list of lists of cells, each such list representing a column of the board. The first element of the first list corresponds to the location (0,0). The last element of the last list corresponds to the top right hand corner of the board.

type World = (Location, Board)

The figure below clarifies locations and representation of the world somewhat.

It would be represented as:

Implementation

In this assignment you will implement the logic that drives the Game of Life. We present the functions in a rough order of difficulty. We provide example invocations of each function. We shall use the following worlds in all examples, save initWorld. They represent the world in Figure 4 and Generation 0 of Figure 3 respectively.

world = ((1,2), [[True, True, False], [False, True, True]])
world2 = ((4,4), [[False, False, False, False, False], [False, False, True, False, False], [False, False, True, False, False], [False, False, True, False, False], [False, False, False, False, False]])

Functions

getCell

getCell :: World -> Location -> Cell

Given a game world and a location, yield the liveness at that location.

GameOfLife> getCell world (0,0)
True
GameOfLife> getCell world (1,0)
False
GameOfLife> getCell world (1,2)
True


If the location argument to getCell is out of bounds (i.e. refer to a cell which is not present in the world) the function should signal an error using Haskell's error function. An example invocation is:

GameOfLife> getCell world (50,21)
*** Exception: Cell (50,21) is out of bounds


The error message must be exactly of this form. i.e.

Cell (x,y) is out of bounds

where (x,y) is the location argument given to getCell. Note that error will automatically print "*** Exception: " in front of the string you pass to it. Make sure that you do not add this yourself.

setCell

setCell :: World -> Location -> Cell -> World

Update a location in the world with the given liveness.

GameOfLife> setCell world (1,1) False
((1,2), [[True, True, False], [False, False, True]])
GameOfLife> setCell world (1,0) False
((1,2), [[True, True, False], [False, True, True]])

Like getCell, setCell should also signal an error when it is given a location argument that is out of bounds. The format is the same as for getCell.

evolveCell

evolveCell :: World -> Location -> Cell

Compute the next-generation state for the cell at the given location. This is done according the rules presented earlier.

GameOfLife>evolveCell world (0,0)
True
GameOfLife>evolveCell world (0,2)
True


evolve

evolve :: World -> World

Given a world in the game, produce the next state of the world.

GameOfLife>evolve world
((1,2), [[True, True, True], [True, True, True]])
GameOfLife>evolve world2
((4,4), [[False, False, False, False, False], [False, False, False, False, False], [False, True, True, True, False], [False, False, False, False, False], [False, False, False, False, False]])


initWorld

initWorld :: String -> World

Initialises the world from a string representation.

• The '*' character represents live cells
• The '.' character represents a dead cell
• Each row of the board is terminated by a newline

An example of a valid world is:

.....
.***.
.***.
*****
.***.
..*..


which as a string looks like:

".....\n.***.\n.***.\n*****\n.***.\n..*..\n"

Hint: This is a good world to test your function on. If you look carefully it looks like a large arrow pointing downwards. Make sure your function parses the world so that it has correct orientation.

GameOfLife> initWorld ".....\n.***.\n.***.\n*****\n.***.\n..*..\n"
((4,5),[[False, False, True, False, False, False],[False, True, True, True, True, False],[True, True, True, True, True, False], [False, True, True, True, True, False],[False, False, True, False, False, False]])

While testing your other functions you may want to type in the value of a world directly into a ghci window. Be careful that you get the order of values correct. Remember, the first element of the first list represents the bottom left hand corner of the board.

Bonus

If you find this assignment easy and would like some additional challenge, this optional bonus part is for you. Otherwise, you can safely ignore this section of the specification. If you do solve the bonus part, you can get up to two extra marks. However, before starting on the bonus, you must first complete and submit the basic part of the assignment.

An evolve function that repeatedly uses evolveCell to yield the next generation is likely to be quite inefficient. It should be remembered that indexing into a list using the !! operator has a cost proportional to the length of the list. If this operation is used for each cell, the resulting solution will run in time proportional to the square of the number of cells. This is not as efficient as it could be.

For bonus marks, implement a two pass approach to evolution. The first pass should yield a representation of the board where each cell is annotated with the number of adjacent cells. The following pass should evolve each annotated cell in turn. Such a solution will run in a time proportional to the number of cells. For large boards this can make quite a difference.

It should be noted that bonus marks will only be awarded to well designed and well written solutions. It will not be enough for them to simply work.

Stub files

We are providing you with the skeleton of the solution (which also compiles). It contains:

• Type definitions of Cell,Board etc
• Type signatures for each function that you are required to implement
• Dummy definitions for those functions

To begin on the assignment download the file GameOfLife.hs.

IMPORTANT: You must not alter any of the function signatures in the stub file.

This is because your assignments will be automatically tested against a test harness. This harness expects that the functions will have exactly the types specified above and will fail if any of them do not. Naturally the function bodies may be changed at will.

Simulator

The Game of Life is made a lot more interesting when you can see your creations creep and crawl across the screen. To aid in this endeavour we have provided a simulator in which to test your final solution. It is bundled as a gzipped tarball and contains the files necessary to compile the simulator against your solution for testing. For further instructions see the README file contained in the tarball.

Note that you can develop the functions in GameOfLife.hs independent of this simulator, just with GHCi. However, once you have implemented all the functions, you will find the simulator useful to see how your worlds evolve.

Download

LifeClient.tar.gz - to unpack, use the command tar xzf LifeClient.tar.gz on Linux

If you plan to work on your assignment on your own machine (instead of CSE lab computers), you must install the library wxHaskell in addition to GHC; see our software downloads.

Important: It seems as if the LifeClient does not work properly on Windows. Hence, please use it on the CSE lab machines if you don't have Linux at home. The LifeClient is not essential to solve this assignment. So, you can still solve the assignment at home; however, if you want to see the animation, you need to do that at uni if you haven't got Linux at home.

In the absence of the LifeClient, you can use the following function to convert a World to a character representation.

import Data.List

showWorld :: World -> String
showWorld (_, board) =
  unlines (map (map toChar) board')
  where
    board' = reverse (transpose board)
    toChar True = '*'
    toChar False ='.'

Diary

Every time you work at your assignment solution document what you did and what the outcomes where in your assignment diary. The diary must be a plain text file called diary.txt. Create and edit it in Xemacs, or some other text editor, not with some word processing software. The file must be saved in ASCII format.

Although this part of the assignment is assessable it is actually designed to help you. Writing down how you plan to design something and problems you encountered along the way can be of enormous benefit in arriving at a working solution. As such, you should not write this document at the very end. Not only will it show, you will also have missed out on any benefit it might have provided.

Deadline

You must submit your assignment by 23:58 on Sunday 28 August, 2005 10:00AM on Monday 29 August, 2005.

If you wish to submit an assignment late, you may do so, but the maximum available mark for late assignments is reduced by 10% per day for up to five days. Assignments that are more than 5 days late will be awarded zero marks. So if your assignment is worth 85% and you submit it one day late you still get 85%, but if you submit it two days late you get 80%, and so on.

Assignment extensions are only awarded for serious and unforeseeable events. Having a cold for a few days, deleting your assignment by mistake, going on holiday, going abroad, work commitments, etc do not qualify. Therefore aim to complete your assignments before the due date in case of last minute illness, and make regular backups of your work. We cannot stress this last point enough. "Regular backups" does not mean every few days - it should be done after every significant change to your code. No extension will be granted without a fully documented submission for special consideration at the Student Centre.

Remember that we check for plagiarism (i.e., copied code and team work) and there are serious penalties. See the plagiarism information in the Course Outline.

Submission

Your solution should be submitted using the give command. Type the following at the unix command line:

give cs1011 ass1 GameOfLife.hs diary.txt

For those of you who wish to submit the solution outlined in the Bonus section also type the following:

give cs1011 ass1_bonus GameOfLife.hs diary.txt

Remember, this is a separate solution. The original must still be submitted

Early submission

There is a single mark for early submission of a draft. To receive this mark your solution must:

• compile,
• have getCell and setCell fully implemented, and
• be submitted by 23:58 28 August, 2005 11:00AM 22 August, 2005 using the command

  give cs1011 ass1_draft GameOfLife.hs diary.txt

  Note how the assignment specifier for the early submissions and final submission are different (i.e., they are ass1_draft and ass1, respectively).

Important hint: The give program allows you to submit your assignment multiple times and only your last submission will be marked. So, there is no harm in submitting partial solutions before the deadline. Do not leave your first submission until the last minute. Always submit some intermediate versions early.

Marking

It is a generally accepted software engineering principle that it is not simply enough for a program to be understood by the machine; it must also be human readable. For the subjective part of the marking we will be awarding marks for programs that have good comments, useful names, and good decomposition and overall design. Good decomposition practices are things such as placing repeatedly used computations in where clauses and breaking complex functions up into calls to small, less complex functions. Source files should also be no wider than 80 characters.

Questions or Problems?

Ask your tutor, or post to the message board.

Changes

References

1. A Game of Life simulator written in Java.
2. Wikipedia's definition of the Game of Life.