Tutorial 8: Game of Life

Exercise 1: A Class for Points

We will play Game of Life on grids of a given finite size n x m. There are several natural ways to store the live points in every round: one could create an (nxm)-matrix in which the entries encode if a point is alive or not. However, since in most situations the number of live points is far lower than the number of dead points, this encoding is not very efficient when the grid is large.

We choose an alternative encoding in which we only remember the live points and store them in a set. To do so, we introduce a class Point that lets us encode points in the grid. For convenience we give you the beginning of the class with the __init__() method already included.

Create a class Point by copying the following:

class Point:
    """Encodes a live point in the Game of Life.
    Data attributes:
    x -- x-coordinate
    y -- y-coordinate
    """

    def __init__(self, x, y):
        self.x = x
        self.y = y

To simplify debugging your code later on, add a method __repr__(). Recall that __repr__ is supposed to give a canonical representation of the Point that will allow it to be reconstructed; this will make it very useful for debugging.

For example, given a Point with coordinates 1 and 2, this method should return the string 'Point(1, 2)'. Your method should begin with

    def __repr__(self):

Once your __repr__() method is defined, you should be able to run the following test:

In [1]: p = Point(2, 3)

In [2]: p.x
Out[2]: 2

In [3]: p.y
Out[3]: 3

In [4]: repr(p)
Out[4]: 'Point(2, 3)'

In [5]: p
Our[5]: Point(2, 3)

Afterwards, upload your file life.py:

Exercise 2: Making Points Hashable

Before you work on this exercise, make sure that you remember how sets and hashing work. If you don’t remember (or, worse, don’t even know what either of these things are), then have a look at the lecture slides and the explanations at the bottom of this page.

We want to store the live points in our implementation the Game of Life in sets. In particular, every point should only be contained once in a set and we want to be able to check if a point is in a set. We can already put Points into sets, but unfortunately the behavior is not what we would like.

In [6]: a = Point(1, 2)

In [7]: b = Point(1, 2)

In [8]: s = {a, b}

In [9]: s
Out[9]: {Point(1, 2), Point(1, 2)}

In [10]: Point(1, 2) in s
Out[10]: False

In [11]: a == b
Out[11]: False

Try to understand the above behavior!

To get the behavior that we want, we have to adapt the way that Points are treated in sets. To do so, we have to change the way that they are compared and hashed.

First, write a method __eq__() to compare Points for equality. It should return True if and only if the two points have identical x- and y-coordinates. Your method should begin as follows:

    def __eq__(self, other):

Sets in python implicitly use hashing to store the elements. To make this work correctly with our points, add a method __hash__() that should begin as follows:

    def __hash__(self):

Remember that the value computed by __hash__() is an integer. Moreover, this value has to be identical for two Points whenever the points are equal with respect to __eq__().

When you are done with both __eq__() and __hash__(), you should be able to run the following test:

In [12]: a = Point(1, 2)

In [13]: b = Point(1, 2)

In [14]: a == b
Out[14]: True

In [15]: hash(a) == hash(b)
Out[15]: True

In [16]: s = {a, b}

In [17]: s  # should only contain one element, since a == b
Out[17]: {Point(1, 2)}

In [18]: Point(1, 2) in s
Out[18]: True

To avoid too many hash collisions for reasonable grid of Points make sure that when you execute

len({hash(Point(i, j)) for i in range(100) for j in range(100)})

on the ipython console, you get as an answer at least 5000.

Afterwards, upload your file life.py:

Introducing and showing the Board

Having a data structure for individual Points, we now define a class to store the whole grid which we will call Board. The class begins as follows:

class Board:
    """A board to play the Game of Life on.
    Data attributes:
    alive_points -- a set of Points
    x_size  -- size in x-direction
    y_size  -- size in y-direction
    """

    def __init__(self, x_size, y_size, points):
        self.alive_points = points
        self.x_size = x_size
        self.y_size = y_size

In contrast to the original Game of Life which is played on infinite grids, we will assume that our boards have a size that is chosen upon creation of the board. We store the size in two attributes x_size and y_size that are initialized by __init__() and represent the size in x- and y-direction, respectively. By convention, the possible values for the x-coordinate are 0, ..., x_size-1 (from left to right). Similarly, the possible values for the y-coordinate are 0, ..., y_size-1 (from top to bottom). Moreover, Board has an attribute alive_points that is filled by a third argument and stores the live points. We assume that those are always stored in a set.

Copy the beginning of the class Board above to your file life.py.

We now give you a graphical representation of Game of Life. Download the file tkview.py and run it. Afterwards you can run the program with a board that you provide as follows:

In [26]: b = Board(5, 5, {Point(1, 2), Point(2, 2), Point(3, 2)})

In [27]: g = GraphicalLife(b, 20)

In [28]: g.mainloop()

Try it out! Also, try to create different board configurations!

Exercise 3: Dealing with the Neighbors

To compute the state of the Board in the next round, it will be useful to compute the neighbors of a Point. To this end, add a method get_neighbors to the class Point (not the Board class!) that returns a set containing all neighbors of a Point.

    def get_neighbors(self):
        """Return the neighbors of the Point as a set."""

Since a Point has no way of knowing the size of the Board it is placed on, we do not check if the neighbor is actually legal, i.e., a point on the board.

Test your method get_neighbors(). For example, on the console you should get (possible with a different order on the results)

In [29]: p = Point(2, 2)

In [30]: p.get_neighbors()
Out[30]:
{Point(1, 1),
 Point(1, 2),
 Point(1, 3),
 Point(2, 1),
 Point(2, 3),
 Point(3, 1),
 Point(3, 2),
 Point(3, 3)}

In [31]: p = Point(0, 0)

In [32]: p.get_neighbors()
Out[32]:
{Point(-1, -1),
 Point(-1, 0),
 Point(-1, 1),
 Point(0, -1),
 Point(0, 1),
 Point(1, -1),
 Point(1, 0),
 Point(1, 1)}

Note that in the second example several points are illegal because they have negative coordinates. We will take care of this now. Add a method is_legal() to the class Board that returns True if a given Point lies on the Board and False otherwise. Remember that on the board we have positions exactly for those Points whose x-coordinate is between 0 and x_size-1 and whose y-coordinate is between 0 and y_size-1.Your method should begin with

    def is_legal(self, point):
        """Check if a given Point is on the board."""

Test your method is_legal as follows:

In [33]: b = Board(5, 5, set())

In [34]: b.is_legal(Point(2, 2))
Out[34]: True

In [35]: b.is_legal(Point(0, 0))
Out[35]: True

In [36]: b.is_legal(Point(0, 5))
Out[36]: False

In [37]: b.is_legal(Point(-1, 0))
Out[38]: False

Afterwards, upload your file life.py:

Exercise 4: Computing the number of neighbors

The state of a point in the next round depends on that of this round and that of its neighbors. In particular, we will have to count the number of live neighbors for cells. This is what we will do in this exercise.

Write a method number_live_neighbors() in Board that computes the number of neighbors of a given point that are alive. Your method should start as follows:

    def number_live_neighbors(self, p):
        """Compute the number of live neighbors of p on the Board."""

Hint: if s and t are sets, then s.intersection(t) returns their intersection.

Test your method number_live_neighbors(). In the console, you should get:

In [39]: b = Board(5, 5, {Point(1, 2), Point(2, 2), Point(3, 2)})

In [40]: b.number_live_neighbors(Point(2, 2))
Out[40]: 2

In [41]: b.number_live_neighbors(Point(1, 2))
Out[41]: 1

In [42]: b.number_live_neighbors(Point(0, 0))
Out[42]: 0

Afterwards, upload your file life.py:

Exercise 5: Computing the next round

Now we have everything together to go from the state of the Board in one round to that in the next round.

Write a method next_step() in Board that computes the points that are alive in the next round and updates the points attribute accordingly. Your method should start as follows:

    def next_step(self):
        """Compute the points alive in the next round and update the
        points of the Board.
        """

Reminder of the rules

• an alive point remains alive if it has 2 or 3 alive neighbors, otherwise it becomes dead.
• a dead point becomes alive if it has exactly 3 neighbors, otherwise it remains dead..

Hints:

• Do not modify Board.alive_points in-place; create a new set.
  
• If s and t are sets, then s.union(t) returns their union.
• Use is_legal() to check if points are on the board.

Test your method next_step(). In the console, you should get:

In [43]: b = Board(5, 5, {Point(1, 2), Point(2, 2), Point(3, 2)})

In [44]: b.next_step()

In [45]: b.alive_points
Out[45]: {Point(2, 1), Point(2, 2), Point(2, 3)}

To test next_step() in the graphical representation and actually play the game, all you need to do is

1. Delete the # from the line self.create_next_button() in create_widgets() in the class GraphicalLife (in tkview.py), and run tkview.py again to make sure this modified class is being used.
2. Create a Board object, b, as above.
3. Create a GraphicalLife object: g = GraphicalLife(b, 20)
4. Do g.mainloop() to get things started. Your graphical window should now have a working “Next” button.

Try it out, and play around with some different starting configurations for the board, to see how they develop.

Afterwards, upload your file life.py:

Exercise 6: Loading boards

As you might have seen in the last exercise, creating initial conditions for the board is somewhat cumbersome. To simplify this, add a function load_from_file() (outside the Board class). The behavior of load_from_file() should be as described below:

def load_from_file(filename):
    """Load and return a board configuration from file in the following format:
    - The first two lines contain a number representing the size in
        x- and y-coordinates, respectively.
    - Each of the following lines gives the coordinates of a single
        point, with the two coordinate values separated by a comma.
        Those are the points that are alive on the board.
    """

Test your functions. You can load some of the boards provided in boards.zip and see what they do. You will need to download the file (right-clicking on the link and selecting “Save link as…”), saving it in your Tutorial_8 project directory. You should see boards.zip appear in the file browser on the left-hand-side of Spyder. Now double-click on board.zip, and click “Extract” in the pop-up. You should now have a series of files in your Tutorial_8 project that contain board descriptions.

For example, you should get the following in the ipython console (though the order of the points in the set may of course be different):

In [46]: b = load_from_file('blinker.lf')

In [47]: b.alive_points
Out[47]: {Point(1, 2), Point(2, 2), Point(3, 2)}

Play around with the game and see how different input boards develop over time.

Afterwards, upload your file life.py:

Exercise 7: Changing boards

Creating your own boards is still somewhat inconvenient, because you have to edit files by hand. In this exercise, we will create a graphical way of creating configurations. To this end, create a method toggle_point() that given coordinates x and y adds Point(x, y) to the set in the alive_points attribute if it is not there and deletes it from the set if it is there. Add this method to Board! It should begin as follows:

    def toggle_point(self, x, y):
        """Add Point(x, y) if it is not in alive_points, otherwise delete it
        from points.
        """

Test your method toggle_point(). You should have the following behavior:

In [48]: b = Board(5, 5, {Point(1, 2), Point(2, 2), Point(3, 2)})

In [49]: b.toggle_point(1, 2)

In [50]: b.toggle_point(2, 1)

In [51]: b.alive_points
Out[51]: {Point(2, 1), Point(2, 2), Point(3, 2)}

When the method seems to work, you can integrate it into the graphical representation of the game by deleting the # from the line #self.canvas.bind("<Button-1>", self.toggle_point) in create_widgets() in the class GraphicalLife (in tkview.py; don’t forget to run tkview.py again afterwards). Clicking directly on the playing field of the graphical representation should now allow you to add and delete live points.

Upload your file life.py:

Exercise 8: Periodicity

We say that a Board b is periodic if there is a number k such that after applying b.next_step() k times, the set b.alive_points is the same as in b. Essentially this means that after some rounds the game comes back to its initial state. Note that, since our Boards are finite, there are only finitely many possibilities for the set of alive points, so after a finite number of iterations they must cycle. However, it is not the case that they must come back to their initial state.

Write a function is_periodic() that, given a Board, decides if it is periodic (returning to state 0), and returns the index of the state to which it loops (as this always exists on a finite board). You function should start as follows:

def is_periodic(board):
    """
    Return (True, 0) if the input board is periodic, otherwise (False, i),
    where i is the smallest index of the state to which it loops
    """

Test your method is_periodic(). You should have the following behavior:

In [52]: b = Board(5, 5, {Point(1, 2), Point(2, 2), Point(3, 2)})

In [53]: is_periodic(b)
Out[53]: (True, 0)

In [54]: b = Board(5, 5, {Point(1, 2), Point(3, 2)})

In [55]: is_periodic(b)
Out[55]: (False, 1)

To avoid infinite loops, you can set a maximum number of iterations (say 1000) for your loop.

Afterwards, upload your file life.py: