Names and values: making a game board

Tuesday 27 August 2013

In Facts and myths about Python names and values, I described how Python's names and values work. There I posed some other questions, one of which was:

Why do beginners find it hard to make a tic-tac-toe board in Python?

Writing a game often involves a grid-like board. Python doesn't have a native two-dimensional array, so you can use a list of lists. Making a checkerboard full of zeros can be done with a literal list:

board = [
    [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, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
]

But that's tedious, especially if you need a 100×100 board. Even if you don't, it seems like you could do it more compactly. Python lets you multiply lists by integers to replicate elements, so you can use this code to produce a list of eight zeros:

row = [0] * 8

Let's try using that technique twice, once to make a row, and then again to fill out the board:

from pprint import pprint
# Construct the empty board
board = [ [0]*8 ] * 8
pprint(board)
[[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, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

It works! Now let's change one of the cells:

# Put a 1 in the upper-left corner
board[0][0] = 1
pprint(board)
[[1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, 0, 0, 0, 0]]

Huh? Somehow setting one cell changed the first cell in every row!? What's going on?

Just as with assignment, list multiplication doesn't copy data (Fact: assignment never copies data.) When we replicate a list with multiplication, we get the same value referenced many times. When we made the single row, we made a list with eight references to the same zero:

row is a list with eight references to the same zerorow0row = [0] * 8

When we make the board, the same behavior of replicating a list applies, so the board is actually eight references to the same list:

board is a list of eight references to the rowboard0board = [ [0]*8 ] * 8

When we assign to board[0][0], we are changing one element, but that element is visible through all eight rows, because all eight rows are actually references to the same list:

changing only one elementboard01board[0][0] = 1

In Facts and Myths, I called this the Mutable Presto-Chango.

Perhaps this is clearer if you consider that these two ways to make the board are exactly the same:

# Make it all at once
board = [ [0] * 8 ] * 8

# Make a row, then make a board
row = [0] * 8
board = [ row ] * 8

Assigning the row to its own variable doesn't change the behavior, but when we see it assigned to a name, it's more obvious that you'll get eight references to the same row.

OK, but why didn't setting one element change all 64 zeros? The diagram shows that there's only one zero, referenced by all the elements of the board.

Two names can refer to the same value. In fact, in our case, eight names refer to the same value. The names are board[0][0], board[0][1], ..., board[0][7]. Changing one of those names to refer to 1 won't make all of them refer to it, any more than if the eight names had been "a", "b", ..., "h". (Fact: Names are reassigned independently of other names.)

The compact way to make a board that works correctly is to use a list comprehension to make each row:

board = [ [0] * 8 for i in range(8) ]

With this code, we use [0]*8 to make the row, which is fine because assignment will correctly update a single element in that row. The list comprehension makes a list with eight of those, but instead of each one being a reference to the same row, the row is recomputed each time, so a new list is made for each row.

It's important to keep straight two different syntaxes that look very similar:

# List multiplication, doesn't work right:
board1 = [ [0] * 8 ] * 8

# List comprehension, does work right:
board2 = [ [0] * 8 for i in range(8) ]

In the first case, [0]*8 is calculated once, placed into a one-element list, and then replicated 8 times, giving 8 references to the same row. In the second case, [0]*8 is the expression in the list comprehension, and so is evaluated anew eight times, producing eight distinct lists to serve as our rows.

If this is still confusing, Facts and myths about Python names and values has more details, or try the code on pythontutor.com.

tagged: » 9 reactions

Comments

[gravatar]
Marin 7:51 AM on 28 Aug 2013

Maybe dictionaries should be more popular and marketed? To me it feels that dict is great fit for such simple gameboards.

[gravatar]
Kontre 3:27 PM on 28 Aug 2013

I'd use a numpy ndarray for 2D tables. It's both easier and faster, but it adds some dependancies.

[gravatar]
gt3 5:59 PM on 28 Aug 2013

Nice article. I remember doing Tic-Tac-Toe as my first Python project years ago. Making the board data structure was actually easy using a single list (e.g., ['1','2','3','4','5','6','7','8','9']) but the problem more the brute-forced index scanning algorithm I felt was needed to work with it. But that's often the problem with using improper data structures and are beginner problems more than Python's fault.

[gravatar]
Russell Borogove 7:24 PM on 28 Aug 2013

I'm with Marin on this: the correct way to create a gameboard:

from collections import defaultdict
gameboard = defaultdict( lambda:0 )
gameboard[0,0] = 1

[gravatar]
Ned Batchelder 7:46 PM on 28 Aug 2013

@Russel: couldn't you at least have used defaultdict(int) ?

:-)

[gravatar]
Russell Borogove 8:12 PM on 28 Aug 2013

@Ned -- yeah, I was going back and forth between 0 and None for my example as I typed it and got a little non-optimal.

(Odd -- why does defaultdict(NoneType) not work?)

[gravatar]
G 10:53 PM on 2 Sep 2013

Probably because you can't call NoneType and get an instance:

>>> import types
>>> types.NoneType()
Traceback (most recent call last):
File "", line 1, in
TypeError: cannot create 'NoneType' instances

[gravatar]
Remigiusz 'lRem' Modrzejewski 12:01 PM on 27 Sep 2013

If you're unhappy with the amount of control graphviz gives you, but don't want to draw by hand, you may be interested in tikz. It's a LaTeX thing, but if you like it drop me a message and I can show you how to export it to svg.

[gravatar]
Veky 5:29 AM on 11 Mar 2014

> Probably because you can't call NoneType and get an instance

You can use defaultdict(print) (in Py3) though. :-DD

Add a comment:

name
email
Ignore this:
not displayed and no spam.
Leave this empty:
www
not searched.
 
Name and either email or www are required.
Don't put anything here:
Leave this empty:
URLs auto-link and some tags are allowed: <a><b><i><p><br><pre>.