Hi guys, this lecture is a bit different, today we are mostly glossing over Python itself and instead we are going to be talk about software development.
At this moment in time you are writing tiny programs. This is all good experience but you will quickly learn that as programs that larger the harder it is to get working. For example, writing two-hundred one page letters to your grandma over the course of a year is much easier than trying to write a two-hundred page novel. The main reason being is that the bunch of letters are mostly independent bits of writing, whereas a novel requires hundreds of pages to 'flow' together.
I’d argue software development is a bit like that too; writing small programs is very different from writing code for large complex systems. For small problems if things go wrong you can just start 'from scratch' whereas for large systems starting from scratch is often not possible (and/or would take years), and so any mistakes made in the design of the system are likely 'warts' you are going to have to live with. As codebases grow concepts like readability become increasingly important.
Today’s lecture is intended as an introduction to some of skills you will likely need once you try to develop a substantial programs. The TLDR version; figuring out a good design ‘off the bat’ can potentially save you hours upon hours of work later on down the line.
Today I will be showing you an example of how we might code up a game of chess. But crucially I’m going to skip over a lot of the ‘low-level’ stuff and instead try to provide a ‘high-level’ sketch for what such a program may look like. If you have the time it may be worthwhile to quickly skim back over the intuition for OOP lecture.
There is a saying in England:
“[you] can’t see the forest for the trees”*.
It means that if you examine something closely (i.e. each tree) you might miss the bigger picture (i.e. that all the trees come together to make a forest). Most of this lecture series has been talking about trees, but today we are talking about the forest.
So before we start looking at a chess game lets say a few words about design; in particular, what counts as good program design?
Simple is better than complex.
Complex is better than complicated.
[...]
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
As always, Tim Peter's ‘Zen of Python’ has a thing or two to say about design, the lines highlighted here place an emphasis on simplicity and clarity of expression, these concepts are core to the entire language and we would do well to remember that; if things start to get complicated maybe it would be prudent to take a step back and reconsider our approach.
At first glance we might think performance is a 'low-level' consideration. You write something and then find ways to save a byte of memory here or there. But considering performance merely as ‘fine-tuning’ would be a crucial mistake.
Those of you that read my 'joy of fast cars' lecture would have seen a few examples of such low-level 'fine tuning', in one example I showed how we could optimize a call to range such that we could search for prime numbers faster. And for what its worth this tinkering did in fact pay off, significantly so, in fact.
However, that lecture also contained a ‘high-level’ idea as well; our tinkering with the range function was, although faster, still blindly searching for a needle in a haystack. We then stepped back and wondered if there was a better way to do it and indeed there was; generating primes is better than blindly searching for them.
The lesson here is that good design choices, even if executed poorly, can easily out-perform bad ideas implemented well. If you want to know more about this, please check do some reading on ‘algorithmic complexity’ and Big(O) notation (we wont cover this stuff in this course).
In short, good design/algorithm choices tend to be very performant once we scale up the problem to huge data sets, and this is why it’s worth taking the time to come up with a good idea.
Throughout this lectures series I have highlighted readability numerous times so I'm going to keep this section super short:
Readability Counts!
Modularity is one way to deal with complexity. In short, this is where we try to chop everything up into neat little boxes, where each little box has just one job to do.
An alternative (and terrible) design would be to have one big box that does everything. The problem with such an approach is that you end up with a complex spider web, and you fear changing one small part because you don't know how that small change may affect the entire system.
Writing good code once and then reusing it is often better than starting from scratch each time. The way to make code reusable is to generalise it to solve variety of problems. This concept is probably best understood by example.
Suppose we were making a function that counted 1-to-100. What can we use this for other than its intended purpose?
Now suppose we write a function that counts from n-to-m. This code works for the current problem but because its design is generalised we may be able to reuse this code at a later date, in this project or the next.
If code is reusable, then that is often a good sign that it is modular as well.
In [1]:
# One use, "throw away" code:
def one_to_one_hundred():
for i in range(1, 101):
print (i)
# Multi use, 'generalised' code:
def n_to_x(n, m):
for i in range(n, m+1):
print(i)
Beautiful is better than ugly.
Tim Peters, ‘Zen of Python’
Beauty!? At first glance making beauty a consideration my sound like a strange or 'out-of-place' concept. But if you take a broad view of human achievement you’ll find that we mere mortals make things, and then make those things beautiful. Just think of something like a sword, it is an object made with the most brutal of applications in mind and yet we still decided that even this was an object worthy of being made beautiful.
Another discipline where discussions of aesthetics may initially seem out-of-place is mathematics, and yet, there are no shortage of mathematicians throughout the ages discussing the aesthetic qualities of field and moreover there is some experimental evidence to suggest mathematicians genuinely see beauty in formula's in the same way the rest of us see beauty in music or art. For some, beauty truly is the joy of mathematics.
"Why are numbers beautiful? It's like asking why is Beethoven's Ninth Symphony beautiful. If you don't see why, someone can't tell you." -Paul Erdos
I think it would be wrong to dismiss beauty as a trivial aspect of mathematics or programming for that matter. There truly is a joy in experiencing good code, you just need to learn to appreciate it, I guess.
Okay so the above discussion highlighted a few aspirations and considerations for our chess project. Let’s start by making a list of all the things we need to do:
Thats a lot of stuff to do right there, today's lecture will mostly deal with points one and two.
How should we represent a board in Python? This question mostly just boils down to what data-type we should use. Right now, I have two candidates in mind; strings and lists.
We could of course jump ‘straight-in’, pick one the data types at random and see what happens but, as alluded to in the above discussions such a method is both silly and wasteful. A better use of time would be to carefully consider our options BEFORE we write even a single line of code.
Okay, so let’s consider using a string for the board. What might that look like?
Well, the letters "QKPN" could represent the pieces (lower-case for white), and we could use the new-line character ("\n") to separate the rows. Something like this:
In [1]:
print("RNBQKBNR\nPPPPPPPP\n-x-x-x-x\nx-x-x-x-\n-x-x-x-x\npppppppp\nrnbkqbnr") # 'x' and '-' represent black and white squares.
Actually, we can do even better than this, Python strings support unicode and there are unicode characters for chessmen. So now our string implementation even comes with some basic graphics:
In [2]:
print("♖♘♗♔♕♗♘♖\n♙♙♙♙♙♙♙♙\n□ ■ □ ■ □ ■ □ ■\n■ □ ■ □ ■ □ ■ □\n□ ■ □ ■ □ ■ □ ■\n♟♟♟♟♟♟♟♟\n♜♞♝♛♚♝♞♜")
Okay so the board as a string seems possible, but are there any drawbacks of an implementation like this? Well, I can think of two. Firstly, notice that because these unicode characters are a bigger than normal letters we are going to need a new way to denote black and white squares. You can see from above I tried to use a combination of spaces and ‘□■’ characters but even then the formating is a bit off. In short, it looks like trying to get the board to look nice is going to be both tedious and fiddly.
You remember me mentioning that strings are an immutable data-type, which means that every time we want to change the board we have to make a new one. Not only would this be computationally inefficient it may also be a bit tricky to actually change the board.
For example, lets see what sort of work we would have to to make the move 1.Nf3:
In [4]:
def make_move(move):
"""Takes a string a returns a new string with the specified move"""
# Code here
pass
# Our new function would have to take the original string and return the new string (both below)...
original_string = "RNBQKBNR\nPPPPPPPP\n-x-x-x-x\nx-x-x-x-\n-x-x-x-x\npppppppp\nrnbkqbnr"
new_string = "RNBQKBNR\nPPPPPPPP\n-x-x-x-x\nx-x-x-x-\n-x-x-n-x\npppppppp\nrnbkqb-r"
print(new_string)
Now, to be clear, it is certainly possible to make the “make_move” function work, but it does seem to have several small moving parts and therefore probably lots of interesting ways to go wrong. And then lets think about the more complex functions; if movement seems a bit tricky, how easy do we think defining checkmate is going to be?
Basically, using strings seems doable but complicated. And as Tim Peters says, simple and complex are both better than complicated. Alright, on that note, let’s see if lists seem more straight-forward.
[[00, 01, 02],
[10, 11, 12],
[20, 21, 22]]
The above is a nested list but we have put each of the sublists on a new line to make it easier to visualise how such a structure can work like a game board. The numbers represent the (x, y) coordinate of that 'square'. And remember that lists can contain strings as well, so this option doesn't stop us from using those pretty graphics we saw earlier.
Compared to the string implementation, the 1.Nf3 move should be somewhat straightforward:
current_position_knight = (a, b) # where (a, b) are coordinates.
next_position_knight = (a2, b2)
Board[a][b] = {empty}
Board[a2][b2] = {Knight}
At first glance, this seems considerably easier than a messing arround mutating strings.
There is also another possible advantage to lists as well, and that is they can store a variety of data-types. I haven't spoken about classes in this lecture series and I'm not going to into detail (classes are not suitable for a beginner class, in my opinion) But, I’ll will very briefly introduce you to the concept and how we could use it here.*
In short, the brainwave is that if we use lists we could litterally build Knight objects, King Objects, etc and they can be placed inside a list. We can't do that with strings.
Basically Python makes it possible to create your own objects with their own methods. Using classes it is literally possible make a knight and put him onto a game board. Below I’ve provided a very rough sketch of what such a class could look like.
I would like to stress that this code is intended as a 'high-level' sketch and by that I mean lots of the small details are missing. Notice that the code for a Queen, King, Pawn, etc could all be written in the same way.
In [32]:
class Knight (object):
def __init__ (self, current_square, colour):
self.colour = colour
self.current_square = current_square
@staticmethod
def is_legal_move(square1, square2):
"""
Checks if moving from square1 to square2 is a legal move for the Knight.
Returns True/False
"""
# Code goes here... i.e we calculate all 'game legal' squares a Knight could reach from position X.
pass
def make_move(self, new_square):
# since we don't want to make illegal moves, we check the intended move is legal first.
if Knight.is_legal_move(self.current_square, new_square):
self.current_square = new_square # <= moves the knight!
else:
return "Invalid Move!"
# Other methods would go here.
# Lets make a White Knight. Let's call him 'Dave'.
Dave = Knight((0,0), "White")
# Once the knight is made, we can move it using the move_to method:
Dave.make_move((3,3))
Out[32]:
In [ ]:
# Note the following code doesn't work, it is for demonstration purposes only!
def all_bishop_moves(position, board):
""" When given a starting square, returns all squares the bishop can move to"""
pass
def all_rook_moves(position, board):
""" When given a starting square, returns all squares the rook can move to"""
pass
def all_queen_moves(position, board):
"""When given a starting square, returns all squares the queen can move to"""
pass
At first glance this code seems pretty good, but there are a few drawbacks. Firstly it looks like we are going to be repeating ourselves a lot; queen movement for example is just a copy & paste of the rook + bishop. The king function is likely a copy & paste of queen but where we change the distance to 1.
And by the way guys, repeating oneself is NOT quite the same as reusing code!
What we would really like to do here is generalise the problem as much as we can. And good technique for doing that is to think of the next project we might want to implement. For example, let’s suppose after building my chess game I want to support Capablanca Chess ?
Capablanca chess is played on a 10x8 board and it has two new pieces; the ‘archbishop’ moves like a bishop combined with a knight and a ‘chancellor’ moves like a rook and a knight.
So, what should we do here? Well, I think the first thing we should do is define movement of pieces WITHOUT referencing a board. If we don’t reference a board that means we should be able to handle boards of many different sizes. Secondly, if we define pieces in terms of combining general patterns (e.g Queen = diagonal + orthogonal movement) then defining new pieces will probably be less the five lines of code in many cases.
Let’s examine what that might look like:
In [ ]:
# Note the following code doesn't work, it is for demonstration purposes only!
def diagonal_movement(position, directions, distance =1):
"""
Returns all diagonal squares in all valid directions N distance from the origin
"""
# code here
pass
def othagonal_movement(position, directions, distance=1):
"""
# doctests showing example useage:
>>> othagonal_movement( (2, 2), directions=[left], distance= 2)
[(2,2), (2, 1), (2, 0)]
>>> othagonal_movement( (2, 2), directions=[right], distance= 4)
[(2, 2), (2, 3), (2, 4), (2, 5), (2, 6)]
>>> othagonal_movement( (2, 2), directions=[right, left], distance= 1)
[(2, 1), (2,2), (2, 3)]
"""
# code here
pass
Notice here that we have defined movement without reference to a board, our code here simply takes an (x,y) coordinate in space and will keep returning valid squares until it reaches the limit set by distance. The documentation in row movement explains the idea.
With this generalisation, we should be able to handle different boards AND we can define pieces with just a few lines of code like so:
In [ ]:
def queen_movement(position, limit):
o = othagonal_movement(position, direction="all", distance=limit)
d = diagonal_movement(position, direction="all", distance=limit)
return o + d
def bishop_movement(position, limit):
return diagonal_movement(position, direction="all", distance=limit)
In the case of an 8x8 board 'limit' would be set to 8. If a piece is only allowed to move 1 square forward (regardless of board shape/size) we can easily model that by setting the limit to 1.
notice that with this design some peices can be defined very simply. For example, we can define a king in the following way:
In [4]:
def king_movement(position, limit):
return queen_movement(position, limit=1)
But lets take a step back for a moment, what are actually doing here?
When naming variables, a good practice is to state what the code does rather than state what it is used for. The reason this can be a code idea is that renaming a function/variable to something general can make code more reusable and modular. The process of thinking about a name may help you spot ideas and patterns that you may have otherwise missed. So, let me ask the question again, what are we actually doing here?
Suppose I give you a table of data, and I want you so sum up all the columns. For example:
[0, 1, 2]
[5, 6, 7]
returns [5, 7, 9]
How can we solve this problem? Well, notice that our othagonal_movement function can be used to solve this problem:
In [6]:
def sum_column(table, column):
num_rows = len(table[0])
position = (0, column)
points = othagonal_movement(position, direction=["down"], limit=num_rows)
total = 0
for p in points:
x, y = p[0][1]
number = table[x][y]
total += number
return total
In short, the point is that although our main goal is to write code for a chess game it turns out some of the code we write could be useful in other contexts too. With good design, these sorts of 'coincidences' happen all the time.
Notice that it was only really possible to reuse othagonal_movement for a different purpose because that function doesn't actually care about chess. It doesn't need an 8x8 board to work, and so on.
So today we moved away from the nitty-gritty and focused on the ‘big picture’. We looked at a few ways to represent a chess program in Python and although my code today was very ‘loose’ hopefully you guys followed along and understood the main lesson I was trying to teach; good, thought-out design matters; it makes coding faster, less frustrating, and also more expressive.
As we move toward the final project you would do well to remember some of these principles. Alright that’s it for this lecture, no homework this week. See ya next time!
In [ ]: