This week I was working on a tic-tac-toe game using Python. An important part of the program was handling the 3×3 grid and updating the player’s marks. In this post I will describe how I tried implementing the grid using two dimensional lists and then changed my approach to use Numpy array views as a means of obtaining additional functionality.
If you would like to see an example of the utilization of another type of data structure, you can see how I used Python’s sets here.
A grid using Python lists
I initially implemented the 3×3 tic-tac-toe grid using a two-dimensional list as follows:
grid = [[0 for i in range(3)] for j in range(3)]
>>> grid [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
grid was initialized with zeros. We can see it as a list composed of three lists, and each one of these lists represents a row of the grid.
In order to modify or access one element of the grid, we need its row and column indexes (starting counting from 0). For instance, to modify the central case we would have:
grid[1][1] = 1
>>> grid [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
While this is simple enough, addressing each case using both a row and column index is prone to error. Let’s say I want to access the last element of the first row – grid[0][2] – but I type grid[2][0] instead. Besides that, it’s clearer to address the elements with the row or column that they belong to, as we will see.
Separating rows in the grid
Instead of using a row index, we can refer to each row directly:
grid = [[0 for i in range(3)] for j in range(3)] row0 = grid[0] row1 = grid[1] row2 = grid[2]
Then each case could be identified by its corresponding row list and onlye one index instead of two indexes:
>>> row2[2] = 1 >>> grid [[0, 0, 0], [0, 0, 0], [0, 0, 1]]
It can be seen that we the changes in row2 are reflected upon grid, very simply because row2 is an item of grid.
This worked well to achieve a clearer notation for each row of the grid, but I also wanted to address the elements by their column.
Difficulties of addressing elements by row and/or column
Just as it had been done with rows, I wanted to create some sort of alias to address each column separately. For instance:
grid = [[0 for i in range(3)] for j in range(3)] column0 = [grid[0][0], grid[1][0], grid[2][0]] column0[0] = 1
>>> grid [[0, 0, 0], [0, 0, 0], [0, 0, 0]] >>> column0 [1, 0, 0]
Here it can be seen that we created a list column0 with the corresponding grid’s elements, but that any change on column0 didn’t reflect back to the original grid. The reason behind this is that column0 doesn’t share the same memory address with the corresponding elements in grid.
At this point, I ran across a limitation using Python lists that I couldn’t overcome without adding complexity. This is when I switched to Numpy arrays instead.
A grid using Numpy array views
Numpy is a Python module that offers several array operations like those used in linear algebra. While I didn’t need any sort of special calculations with arrays, Numpy offered the functionality I was looking for to address the elements of my grid with different names using views. Let’s see how it worked out.
Creating a Numpy array
Luckily, the notation of Numpy arrays isn’t very different from the one used by Python’s lists. Besides importing the module and modifying the initialization of the grid, I didn’t need to change many things:
import numpy as np grid = np.zeros(shape=(3,3))
>>> grid [[0., 0., 0.], [0., 0., 0.], [0., 0., 0.]]
The print output is a little different but the functionality was the same as using a nested list… plus many other features.
Note: printing Numpy arrays actually returns array(...). I deleted that part from the output of 2D arrays to gain some space.
Creating views for rows and columns
Numpy views allow to share elements between different arrays. It’s like creating an alias of selected portions of an array. A change in either the alias or the original array will affect both of them.
A view is created by selecting a slice of the element. This is a special notation used to address only a portion of the elements, which is precisely what I was doing by selecting rows and columns:
# Using a grid filled with numbers 1 - 9 as example grid = np.arange(1, 10).reshape(3,3) row0 = grid[0] row1 = grid[1] row2 = grid[2] column0 = grid[:, 0] column1 = grid[:, 1] column2 = grid[:, 2]
>>> grid
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
>>> row0
array([1, 2, 3])
>>> column2
array([3,
6,
9])
While row slicing is similar to selecting elements of Python lists, column slicing is a bit different. We can understand the colons (:) as a place holder to denote ‘any index’. For instance, the expression grid[:, 0] means that we select all elements that have any value for the first index (:) and 0 for the second index. It’s equivalent to the expression I used with Python lists earlier:
column0 = [grid[0][0], grid[1][0], grid[2][0]]
As expected, any change on either the rows or the columns arrays also affects the original grid:
grid = np.zeros(shape=(3,3)) row0 = grid[0] row1 = grid[1] row2 = grid[2] column0 = grid[:, 0] column1 = grid[:, 1] column2 = grid[:, 2]
>>> row1[1] = 3 >>> column2[:] = 1 >>> grid [[3., 0., 1.], [0., 0., 1.], [0., 0., 1.]]
Here I switched to a 3×3 grid filled with zeros again so that the changes can be seen more clearly.
At this point, only the diagonals where missing…
Array view of diagonal elements
Diagonals were trickier because there is no way to create diagonal slices (that I know of). Luckily, the numpy.einsum function used to handle Einstein notation can create diagonal views:
import numpy as np
grid = np.arange(1,10).reshape(3,3)
diag0 = np.einsum('ii->i', grid)
diag1 = np.einsum('ii->i', np.fliplr(grid))
>>> diag0 array([1, 5, 9]) >>> diag1 array([3, 5, 7])
The ii->i argument passed to einsum is just a way of selecting the diagonal elements of the grid and returning them to a single array using the Einstein summation notation. See that to get the 2nd diagonal, I used the same expression but I flipped the grid from left to right using numpy.fliplr first.
Finally, we can change the diagonal elements of the grid by addressing the diagonal arrays created with numpy.einsum:
grid = np.zeros(shape=(3,3))
diag0 = np.einsum('ii->i', grid)
diag1 = np.einsum('ii->i', np.fliplr(grid))
diag0[:] = 1
diag1[2] = 9
>>> grid [[1., 0., 0.], [0., 1., 0.], [9., 0., 1.]]
In conclusion
Array views in Numpy allow addressing the same elements from different arrays. In this post, we saw how it was used to group different elements of the same grid in different ways in order to improve clarity and add functionality.