>>In this module we've been talking a lot about algorithms and extractions and how we
can express algorithms and how we can use algorithms to think more powerfully and elegantly.
So in this specific video, we're going to talk about something called pseudocode, and
pseudocode is a way of expressing ideas and expressing code without actually using a specific
language. And it's very language independent. It contains examples of the things that appear
in each language but there's no specific syntax to it. So for example we're going to use the
concept of if, which we've talked about in controls. If something happens then you do
this, but we can express it in a way that doesn't tie it specifically to a particular
language. So we're going to talk about that was some examples and you'll see what we mean.
In this video in order to understand pseudocode, we want to stick with an example. And so I'm
picking an example that I hope that you've heard of it, it's a game called Tic-Tac-Toe.
At least that's what it's called here in the United States, other parts of the world I've
heard it's called Noughts and Crosses. So in case that you have not heard of it let's
do a brief review. Tic-Tac-Toe is a game that's played with nine squares. They're generally
numbered 1 to 9 if you're doing them on the computer, which is the example that we'll
look at later, but you've got nine squares it's a 3x3 board and you can draw in alternating
turns. It's a two-person game. You draw either an X or an O. So let's imagine that you're
the X. Your goal is to get three X's in a row, either in a row or in a column or across
a diagonal and O's goal is to keep you from doing that while trying to get 3 O's in a
row, somehow. So in order to write out some pseudocode for Tic-Tac-Toe we need to consider
what exactly a Tic-Tac-Toe player should do. And I want to mention at this point that the
reason we're sticking with Tic-Tac-Toe in addition to it a being simple is actually
that your project is going to be on Tic-Tac-Toe. So you're going to be eventually writing a
Tic-Tac-Toe player up. So let's talk about what it means to play Tic-Tac-Toe and what
it means to play it well. Can we list out some rules? Let's start with rules before
we get to pseudocode. So what are the rules of a winning Tic-Tac-Toe player? Keep in mind
that we're not necessarily going to write the optimal Tic-Tac-Toe player. I just want
to make some quick rules sort of that you could write a player that would not be horrible.
So the first rule should be: if there is a win, do it. So if you can win, make that winning
move. If your opponent's about to win, clearly you should block your opponents move. How
about, it's always good to start in the center square. And if your opponent didn't start
in the center square, that is, say it's now your turn and the center square is free, then
play in that center square. So now if you've filled in the center and you clearly aren't
about to win what should you do next? Well how about if a corner is free and in particularly,
if a corner is free that's in line with another mark of yours an X or an O, whichever one
you are, or if you have the center then you should play in that corner. And finally, if
you can't make two in a row, which is what we were aiming for with that corner, then
just play in an empty square. I'm sure there's a more smart way to talk about which empty
square you should pick, but without talking about how to do the optimal strategy we are
just trying to make a player that's not horrible, than just play in the first empty square that
you find. This set of rules won't give you an optimal Tic-Tac-Toe player: that is, one
that would play optimally against another Tic-Tac-Toe player that's playing optimally,
but it will give you a player that's not horrible. You certainly don't want to play against a
random player. And so it's going to be the set of rules that we work from for this example.
So now let's talk about how to turn these into pseudocode. So in order to turn these
rules into pseudocode, let's consider that we're going to call each of these rules probably
a helper block, or just a block that can be called within another block. And we've already
talked about how to make a function or a block. So let's imagine that there is a block called
FindNextMove and within FindNextMove it's going to call each of these different helper
blocks. So to start with pseudocode let's start with the very first one, which was:
if you can win, do it! How do you know if you can win in a Tic-Tac-Toe board? Well the
way you can do that is: if there's three in a row, that is, any one of the rows, or a
three in a column, or a three diagonal. And we can hard code the winning positions just
to see if there is a winning position on the board and that's fine, but in order to check
to see if you can win-- that is, that you're one away from a winning position, we're going
to write a little bit more of a general function and we're going to talk about that now. So
let's focus on that function. Let's call it, that function or that block as it's called
in Snap!, let's call it FindWinningMove. And it's going to take an input and that input
is going to be a player, and so the way that we're going to express that in pseudocode
is to say the function name the FindWinningMove and we're to use parentheses and then put
in what the input is. And so we're going to call that player. So when you write pseudocode
typically you also write something about what the function does and what the function takes
as input, and the way that you do that is to use comments. The typical comments that
are used in pseudocode are // and they just mean that whatever's in there is just a comment,
it's a notation, it's not intended to be turned into code. So the first comment I would say
about this function is that it's going to return a move and the way that I'm going to
represent this is it's just going to return a number from 1 to 9 and if it can win, or
it will return -1 if there's no winning move. And the second comment that I would make is
to note that the player, that parameter that's coming in as player, is either going to be
an X or an O. That way you can just compare it directly to what's in the board. So the
first part of this pseudocode we're going to consider looking for X's or O's in a row
and by a row specifically here I mean the horizontal rows. So the way that we're going
to do that is we're going to look at something through a for loop and I'm going to loop through
a variable that I'm going to call row. And instead of just bringing it up in Snap!, the
way we're going to represent this is we're going to use the for that we used in Snap!
which is representing a for loop. I'm going to declare a variable called row just by saying
for row equals, and then I'm going to tell it what it's range is. And it's going to range
from 1 to 3, and when you see pseudocode you'll see various ways of expressing this. The way
I'm expressing it is just to use the word to, so it starts at one and it goes all the
way to three. So in order to determine how many X's or O's there are in this row I'm
going to declare a variable called num in row, and when I declare it I'm just going
to initialize it to zero. That is to say, there's nothing in a row at the moment. And
then I'm also going to be looking for blanks, because it's important what we're-- remember
the function that we're writing is FindWinningMove. We're not looking to see if there is a win.
We're looking to see if there is a move that we can make as a win, and that is, we want
to find two in a row with a blank so that we can fill it in. So I declare a variable
called num blank and I'll just say num blank equals zero, and then I'm going to make a
col variable called blank column and that just tells me which column it is that it is
blank, so that at the end you can say exactly where the move is. And now I'm going to loop
thorough the columns so for column equals 1 to 3. Let's look at the move at that entry
so at that entry row, column is it that player and I'm just going to say that by if move
at row, column is player then we increment the number that are in a row. And the way
we're expressing that is something that you haven't seen before in this course, we're
using the expression ++ and that means increment that variable by one. So another way you could
say it would be num in a row plus equals one, which is another way to say you just equal
the same thing + one, or you could say num in row = num in row +1, but ++ is a much shorter
way of saying that. So now that we've incremented num in a row we've said okay, we've had the
move there is the same as this player. Now we need to look and see if it's empty, because
if it wasn't player the next choice is it's empty. And if it's empty we're going to increment
the blank variable with num blank ++ and we're also going to note what column this is, so
we're going to say that blank column equals the column that we're in. And at the very
end, after for this row, after you've gone through the columns you're going to check
something. And the way that we're going to say that is if num in row is equal to two,
so that = = is a test rather than an assignment. A single equal is an assignment so if num
in row is = = to 2 and the num blank is one, then we're going to return that row and that
column because it tells you there were two in a row somewhere in that row for this player,
and there was a blank in between. So if the check for a winning move in rows didn't work
then the next logical thing to do is to look for a winning column, and it's exactly the
same logic except for we're going to swap the idea of the rows and the columns. So here
we're going to loop through the columns, so for column equals 1 to 3, and we're going
to initialize the same variables except for we're looking at columns instead of rows.
So number in the column is zero, number blank is zero and then the row that we're looking
at, the blank row is now zero. And we're going to say for row equals 1 to 3 so that is we're
going to look at each individual row. If the move is at that spot row, column is the player
then we increment the column num in col + + and if the move is empty, we increment blank
num blank + + and we need to say that row if it is empty. So we say blank row equals
row and then we do the exact same check that we did for the row with the columns. We now
look to see if there are two in a row that is num in colum is two and there's a blank
so num blank equals one and the way we express that in the pseudocode if num in col = = two
and num in col = = one then we're going to return that winning move, which is blank row,
column. So if you didn't find a winning move across the rows or across the columns you
need to check the diagonals. And the way that we're going to do that without a nested for
loop, because there's no reason to nest this on,e is to just look at the diagonal. And
we'll start with the left-hand diagonal the one that goes 1,1; 2,2; 3,3 and then we need
to check the other one which is 1,3; 2, 2; 3,1. So let's look at that first one, and
we're just going to say how many of them are that match this player and how many is there
another blank in there so it's pretty much the same as we've been doing except for instead
of saying num blank or num in row, I'm just going to keep a variable called num. Initialize
that to zero, the number blank is zero, and say which one it is that is the one that's
the empty and I'm just going to call that blank is zero. And I'm going to look through
the 1,1; 2,2; 3,3 and the way I'm going to do that is just to say there's a for loop
that is for row and column that both go together from one to three. And look and see if the
move at 1,1 for example is the player, and you increment the num and if it's empty you
increment the number that are blank and you save a pointer to that row. You say blank
is row. And then at the very end of that check you say, well, were there two of that player?
If num = = 2 and one blank if num blank = = 1 then return that. And we're going to make
this work for the other diagonal. You just need to switch your logic so that you check
the first row, the third column so 1,3; 2,2; and then 3,1 and you do the exact same logic.
At the beginning of this function we said that we were going to return a number from
1 to 9 or a -1. Now we've done something slightly different with this function so let's talk
about the -1 first. The way that we're going to do that is just to put it into the pseudocode
and say: okay, if we didn't find a winning move across the rows, the verticals, or the
diagonals, then let's just returning -1 at this point. But I'll note that actually what
we're returning instead of a number from 1 to 9 was actually the row and the column and
so what I would do at this point is actually just go back and fix the comment and just
say that we're going to return a row and a column if there's a winning move and otherwise
we're going to return a -1. That was a lot of pseudocode, but hopefully it's giving you
an idea of what pseudocode is and how you can use pseudocode to powerfully express your
ideas in a language- independent manner. So now let's take that pseudocode for FindWinningMove
and move back the pseudocode for the idea of FindNextMove. And that is, take our entire
set of rules that we talked about at the beginning and talk about how to turn those into pseudocode.
So let's call this block or function FindNextMove, and it's going to take a parameter player
and again the player is either an X or an O, because it needs to know who it's finding
the next winning move for or the next move for. And if you recall our first rule was
to find a winning move, so the thing we're going to do for FindNextMove is say call FindWinningMove
and see what it returns. So we're going to express that with if FindWinningMove of that
player is not equal to -1 and the way that I'm expressing not equal in this particular
version of the pseudocode is bang equal. You could do it with an = with a, with a line
through it as well. If it's not equal to -1, then return that move. And if you recall what
we're having it do is we're either return a winning new or return a -1, and so we're
checking. If it's equal -1 then we want to move to the next rule and if it's not equal
to -1 then we went to return that winning move and make that move. The next rule was
can your opponent when? Well, we better check that too. So the way we do that is just to
check if FindWinningMove on your opponent, that is the player that is not you, is not
equal to -1 then you return that move and block your opponent. Our next rule was: if
the center square is empty. So we're going to imagine that that's another block that
we've written and it's a pretty simple block, you just look at the center square and say
is it empty. If it's empty, return the center square and if it's not empty then you're going
to return -1 or something and not do it. And now we're going to look at the corners. Well
there's only four corners so we could just have a little for loop that loops through
the corners 1,1; 1,3; 3,1; and 3,3 and say: if that corner is free, then return it. And
finally, since we weren't making the optimal player we're just going to say okay. We didn't
find a move up to this point, let's just for each number from 1 to 9 look for the first
one that's empty. So is 1 empty? Return it. 2 empty? Return it. So basically the way we're
going to write that in pseudocode is, for each square in the board, return the first
one you find that is free. So pseudocode is really important for being able to express
your ideas logically and powerfully and another thing it's really helpful for is helping you
to think through your ideas and your algorithms before you actually implement them and create
bugs potentially. So you write them down, you look at it and you say wait a minute,
that doesn't look right. And so as you're writing down the pseudocode you can work your
way through the logic and hopefully find those bugs before you write them into your code.
It's possible that the way that we wrote FindWinningMove isn't the simplest way to do it, and I challenge
you to go ahead and write a much simpler one. Go ahead and think about it, write out the
pseudocode for it that will be great. The next lab is going to be the final lab for
the course and it is going to focus on Tic-Tac-Toe, because it ties together everything that you've
learned. And so go ahead and use this pseudocode and use the idea of expressing pseudocode
to make that lab work really well.