How to Program a Connect 4 AI (implementing the minimax algorithm)

00:00:00 how's it going everyone and welcome back
00:00:01 to another video this video is long
00:00:04 overdue but today we will be programming
00:00:06 an expert level Kinect for AI which is
00:00:09 going to be a lot of fun if you haven't
00:00:10 already I recommend you check out the
00:00:12 four videos I did before like a while
00:00:14 ago on I guess just programming the
00:00:17 Kinect for game and what we're gonna be
00:00:19 doing today is building off of that and
00:00:21 actually implementing the AI if you
00:00:23 don't want to like go through all the
00:00:25 effort of what like programming the game
00:00:27 from scratch
00:00:28 you also can just go to my github page
00:00:31 and I'll link to this in the description
00:00:33 but there's a spot a Kinect for py and
00:00:38 this is the game that we had finished
00:00:40 after the fourth video in that how to
00:00:42 program Kinect for in Python so if you
00:00:44 just click on the raw there and just
00:00:47 copy all of this ah this is going to be
00:00:54 the starting point from this video I'm
00:00:57 gonna be programming in connects or not
00:01:00 programming and Kinect for I'm
00:01:02 reprogramming in Python 3 and I'm using
00:01:04 sublime text as my editor so we should
00:01:08 call this connect four original dot py
00:01:11 also if you haven't seen it already I
00:01:14 really recommend you watch my video that
00:01:16 I did called like how does a board game
00:01:19 AI work because basically what we're
00:01:21 gonna be doing in this video is
00:01:22 following a long kind of the steps that
00:01:24 I go through in that video on the theory
00:01:27 behind a Kinect for AI so it really will
00:01:30 help you with the background information
00:01:32 on like how everything works because it
00:01:34 can be a little bit complicated at times
00:01:36 once you have the file locally just make
00:01:39 sure real quick that it runs properly so
00:01:41 when you run this original file you
00:01:43 should always it not running you should
00:01:46 get a screen that pops up what it looks
00:01:48 like Kinect for board and you just take
00:01:50 turns being the yellow and red player
00:01:52 dropping pieces I'll finish this up real
00:01:55 quick and it should do something like
00:01:58 that when you you win you don't have any
00:02:01 errors to start off so just make sure
00:02:02 that everything is working properly
00:02:04 before we actually get into the AI and
00:02:06 with this AI we're gonna start off just
00:02:09 like I did anyhow
00:02:10 does a boardgame AI video work with the
00:02:13 simplest approach we can think of for
00:02:16 the AI so we're just kind of have it the
00:02:18 player to just drop a piece randomly
00:02:21 somewhere on the screen so that's what
00:02:23 we're going to start out with before we
00:02:25 begin take a second to review the code
00:02:27 and make sure you kind of understand how
00:02:28 all the pieces fit together because as
00:02:30 we go through the steps of the AI if you
00:02:32 don't really understand how the game is
00:02:33 working it's gonna be kind of confusing
00:02:35 the steps that were implementing and to
00:02:39 start off where you are implementing the
00:02:41 random dropped
00:02:42 AI so we're going to go down to our game
00:02:45 loop which is here and in the initial
00:02:49 game we were checking for the mouse
00:02:51 button down event and then based on
00:02:54 whose turn it was so turn equals zero
00:02:56 was the red piece I think and then the
00:02:58 else statement was player two and that
00:03:00 was the yellow piece we are making the
00:03:03 jobs based off of that in this random AI
00:03:06 situation we are now not going to have
00:03:09 player to drop when a mouse click
00:03:12 happens is going to just will have
00:03:14 player to drop whenever right after
00:03:18 player one has made the move so once
00:03:21 player one makes the move that should
00:03:23 trigger player two to make the move and
00:03:24 to kind of make some of this clear I
00:03:27 don't like having like turn equals
00:03:29 equals zero popping up in the code all
00:03:31 over the place these are called magic
00:03:32 numbers so what I'm going to do real
00:03:34 quick is just to make things a little
00:03:35 bit more clear is I'm going to go up
00:03:37 here and define a static variable player
00:03:41 which equals zero and I'm going to have
00:03:43 a static variable or kind of just say
00:03:45 yeah a variable called AI equal to one
00:03:50 and that will just when I'm making these
00:03:53 variables will make it a little bit
00:03:55 easier for me to read the code and also

00:03:58 as we implement some of these functions
00:04:00 with the AI it'll make it a little bit
00:04:02 easier for us to understand how to
00:04:05 implement it so now attorney equals
00:04:07 equals zero is turn equals equals player
00:04:10 and then for this we don't want to end
00:04:14 the let me make this a little bit
00:04:17 smaller just for a sec oh that's makes
00:04:18 you small make it bigger but we don't
00:04:21 want it to be in the if statement if
00:04:22 mouse button down
00:04:23 we want it to be outside of this four
00:04:25 loop because shouldn't depend on event
00:04:27 should just depend on when this I guess
00:04:30 happens which we can store separately so
00:04:34 we're gonna move this back a few okay so
00:04:42 that now should be in line with the four
00:04:46 event and instead of an else we can't
00:04:49 have an else without an if above it so
00:04:51 what we're going to do now is we're
00:04:53 gonna do if turn equals equals AI and I
00:04:58 guess we'll also do and not game over
00:05:01 because we don't want this a piece to
00:05:04 drop after the game has sort of been
00:05:05 finished
00:05:06 so if journey equals equals AI and not
00:05:09 game over then we have the random AI
00:05:15 making a decision and let's see there
00:05:18 might be some other changes you have to
00:05:19 make now that we did that one thing we
00:05:22 might want to do is throw the print
00:05:24 board somewhere differently actually
00:05:26 it's good right here and let's see where
00:05:29 else was I didn't actually move it okay
00:05:33 so I'm gonna move this stuff outside of
00:05:35 the loop to let's see okay I'm thinking
00:05:39 about this okay if game over that should
00:05:41 be in the loop the turn what we're gonna
00:05:44 do with the turns now is only have them
00:05:46 change when a valley location was chosen
00:05:49 so here the turn is changing and same
00:05:55 thing for the player turn so if valid
00:06:02 location then we'll change the turn okay
00:06:08 no not that one less so inside the is
00:06:13 valid location okay so now what we what
00:06:16 we have just done we haven't really done
00:06:18 don't worry too much about the I guess
00:06:23 logistics of what we're doing but
00:06:25 basically we're setting it up so that we
00:06:26 can pick a random spot to drop a piece
00:06:30 we're just kind of having to do some I
00:06:32 guess extra work to clean up the code
00:06:35 and set it up for what we're trying to
00:06:37 do so if turn equals AI and not game
00:06:40 over cool and so now what we want to do
00:06:43 is that initially right here we this was
00:06:49 looking at where our mouse was and
00:06:51 picking the column based off of that
00:06:53 what we want to do instead is now to
00:06:56 just pick a random column so I'm going
00:06:58 to do column equals random brand int 0
00:07:03 which is the farthest to the left column
00:07:06 and we have column count columns right
00:07:11 but indexing is gonna put that off by 1
00:07:16 so we're gonna do a column count minus 1
00:07:17 and I'll pick a random number between 0
00:07:21 and I guess 6 inclusive to drop our
00:07:27 piece in and I have to I did not import
00:07:31 random so I have to do that real quick
00:07:32 all right I feel like I screwed
00:07:35 something up and maybe we'll get some
00:07:37 simple AI right here okay it seems to be
00:07:42 working but it's immediate and that's
00:07:44 kind of annoying but that's a good we're
00:07:47 doing well so far
00:07:48 oh and it's screwed up I just dropped a
00:07:52 piece in a winning location and it
00:07:55 screwed up there too so we have some
00:07:57 things we need to do so the first thing
00:07:59 I noticed that was really annoying was
00:08:01 right when we dropped our piece the AI
00:08:03 dropped their piece and that just
00:08:05 doesn't seem very like it's not a good
00:08:08 user experience so the first thing I'm
00:08:11 going we're gonna add is some time delay
00:08:15 for the AI piece so down here we have
00:08:19 the AI move and so basically what we're
00:08:22 gonna do is once this column has been
00:08:26 selected and is a valid location so if
00:08:30 it selects a column it's like not valid
00:08:33 I've already filled up or something it
00:08:35 will run the loop again like nothing
00:08:37 will have changed the turn won't have
00:08:38 changed or anything and it will find a
00:08:41 column that's valid and so in the is
00:08:45 valid location we're gonna add
00:08:46 a delay so I really hope I game got time
00:08:50 to wait 500 and this is similar to what
00:08:53 we did before when we ended the game
00:08:58 just to like hold the player 1 wins on

00:09:01 the screen so just like we did there so
00:09:03 we're gonna add that and so let's see
00:09:05 how it looks now quickly what the heck
00:09:11 okay so I noticed another issue so I
00:09:14 think it's working
00:09:15 but what's not happening is the board is
00:09:19 not getting re printed after the we
00:09:23 select our piece so the delay was there
00:09:27 but it was being weird because it wasn't
00:09:29 actually drawing the board again so what
00:09:32 we're gonna do here is once we select
00:09:37 like a is valid location we should
00:09:40 update the board because it will have
00:09:42 dropped a piece so I'm gonna add this
00:09:45 here see what looks like now yeah that
00:09:52 looks pretty good and it's moving around
00:09:55 okay it seems random but obviously as I
00:09:58 mentioned or as yeah as I mentioned in
00:10:01 the how does a board game AI work it's
00:10:05 when you just select a random column it
00:10:07 is such a stupid AI and it will not
00:10:10 block my obvious three in a row so I can
00:10:13 easily win right now also real quick
00:10:14 while I'm thinking about it I don't know
00:10:17 if you notice this but right now I
00:10:21 always get to go first
00:10:23 so we probably would want it to be
00:10:26 random who gets to go first it just
00:10:29 makes it a little bit more realistic and
00:10:31 we dwell it we want the code to work if
00:10:34 the AI goes first so we can really
00:10:37 easily add some logic that will allow us
00:10:41 to initially initialize who goes first
00:10:44 and all I'm gonna do is turn equals
00:10:48 random Rand int 0 1 or I guess we could
00:10:52 even do player AI which is going to be 0
00:10:56 to 1 as well so
00:10:59 what will happen now is instead of turn
00:11:02 where was turn initialized somewhere in
00:11:05 here turn equals zero now turn is going
00:11:10 to be either one or zero and the reason
00:11:12 we can do this just fine is because the
00:11:15 only place turn can change is after a
00:11:19 valid pieces have been dropped so
00:11:21 basically what's going to happen now is
00:11:22 we're gonna enter we're going to skip
00:11:24 over this event this code right here on
00:11:27 the first iteration if we get one in
00:11:29 that initialization step and then the AI
00:11:33 will drop a piece it will switch to the
00:11:37 player's turn and then we'll start back
00:11:39 up at the top of the loop and we'll wait
00:11:41 until the user clicks and then run the
00:11:45 code so let's just see if that worked oh
00:11:50 shoot yeah it looks like it worked all
00:11:54 right one more time just to make sure
00:11:57 it's kind of weird that it's starting
00:11:59 yellow it's a little bit laggy or
00:12:00 something but it is working and I want
00:12:03 to just make sure that I can get a I
00:12:08 should be able to go first at some point
00:12:10 – okay yeah so after three tries we
00:12:15 initialized the zero and I get to go
00:12:17 first as before one more thing before we
00:12:20 move on to the slightly more advanced AI
00:12:23 is that when I was running this one
00:12:26 thing that I found that was annoying is
00:12:28 come on run
00:12:30 Judith click first is when the yellow
00:12:35 piece is first so you see how when the
00:12:39 yellow piece is first the yellow block
00:12:41 popped up top here it draws the yellow
00:12:44 block up here I really want that to
00:12:45 happen now that only we're always red so
00:12:50 I'm going to change this to turn equals
00:12:52 player and then I want you to actually
00:12:53 get rid of this drawing the yellow
00:12:56 circle on the mass motion okay so let's
00:12:59 see what happens now yeah so now it just
00:13:04 pops up immediately and I could add
00:13:07 another delay but I'm fine with this
00:13:09 cool yay all right let's move on to
00:13:16 something smarter and actually start
00:13:17 implementing the scoring heuristic for
00:13:19 our board so what we're gonna be doing
00:13:21 is evaluating whether or not a board
00:13:23 state is good or bad based on you know
00:13:25 how many two in rows there are how many
00:13:28 three in a rose there are whether or not
00:13:30 you're playing in a center column and
00:13:33 you know vice versa for the opponent
00:13:35 having three in Rose tuna Rose etc and
00:13:38 so this is exactly what we did and how
00:13:40 does a board game AI work video except
00:13:44 the one difference is that a lot of the
00:13:46 scores I think I was going through in
00:13:49 that video we're relative to the piece
00:13:51 you dropped so like you'd only look at
00:13:55 the three in a rose created or the tuna
00:13:57 Rose created from the specific piece you

00:13:59 dropped that turn what we're gonna have
00:14:01 to do when we're implementing that so
00:14:04 that we can use that minimax algorithm
00:14:05 is do that relative you weigh the score
00:14:10 will be not it will be independent from
00:14:14 which piece was just most recently
00:14:17 dropped so you'll kind of look at all of
00:14:19 the board and count how many three in a
00:14:21 row is how many tuned rows etc let's
00:14:24 define a function called score position
00:14:26 which will give the will assign the
00:14:28 score to our board so I'm going to
00:14:32 define this right under the winning move
00:14:33 function so score position and if we're
00:14:37 scoring position we're gonna need to
00:14:38 take in two things in my opinion we're
00:14:41 gonna have to taking the board obviously
00:14:43 we'll also want to take in a piece so we
00:14:45 have to know whether it's red or yellow
00:14:47 going whether it's the player or the AI
00:14:50 okay cool and this is gonna be pretty
00:14:54 similar to how we did winning move or in
00:14:58 a way basically what we're going to
00:15:00 check is look at the whole entire board
00:15:02 and basically be counting the number of
00:15:04 twos in rows three rows etc I think to
00:15:07 start off and make things easier let's
00:15:09 just count whether you win or whether
00:15:12 you win or lose so we'll just be looking
00:15:16 at for in the rows and we'll start off
00:15:18 with just horizontal so whores
00:15:21 toll or score horizontal I'll say and
00:15:27 let's see one thing I want to do real
00:15:30 quick just it's on my mind is peace is
00:15:33 defined as one or two so one is the
00:15:35 player this peace value and two is the
00:15:38 ai's peace value and that's another like
00:15:41 magic number so I'm going to just try to
00:15:43 like I'm going to define two more
00:15:46 variables player piece and a eye piece
00:15:51 player piece equals one and this will
00:15:54 just apply to make our code a little bit
00:15:56 easier to read again and a eye piece
00:15:58 equals two so let me just go through and
00:16:01 try to switch things out so this would
00:16:05 be player piece here this is a eye piece
00:16:13 defined in several locations go down
00:16:16 player piece right here drop piece this
00:16:19 would be player piece winning move this
00:16:23 would be player piece I think this one
00:16:28 is something different here let's see
00:16:31 what else we have down here would be a
00:16:33 eye piece I can't I think down here
00:16:37 would also be a eye piece I think that
00:16:39 might have been at not positive but just
00:16:41 cleans up the code a little bit okay so
00:16:44 we want to score the horizontal
00:16:45 locations the way that I think we should
00:16:48 do this is basically what we're going to
00:16:52 do is we could do it the exact same way
00:16:55 we did winning move but it gets kind of
00:17:00 tough with these if statements to count
00:17:02 whether or not like you have two in a
00:17:04 row exactly or three in a row exactly
00:17:07 because then you'd have to let you have
00:17:09 the factor in all the different ways you
00:17:11 can have three in a row so what we're
00:17:13 gonna do is I'll run the game real quick
00:17:16 no no what did I do
00:17:18 sorry just need a pass this function
00:17:21 real quick what we are gonna do instead
00:17:24 of that is basically imagine so look at
00:17:29 my mouse down here in the corner we're
00:17:31 gonna look at with horizontal starting
00:17:33 we're gonna look at
00:17:34 window sizes of four and just basically
00:17:37 in those window sizes of four count how
00:17:40 many empty squares and how many filled
00:17:42 in squares there are and will basically
00:17:45 be able to count then the lines of two
00:17:47 lines of three lines of four from that
00:17:49 so this is how it's going to work so we
00:17:55 have our board and that's you know the
00:17:56 matrix the row of rows and columns so
00:17:59 what we're gonna say is for our in range
00:18:02 row count so for each row we're gonna
00:18:06 want to do this and then what we're
00:18:08 gonna do is we are going to define this
00:18:13 row array and yes row or a the best way
00:18:19 yeah row array so this is going to be
00:18:21 all of the pieces so if we're looking at
00:18:23 a single row this is just going to be
00:18:24 the seven tiles but just in a single
00:18:27 list so it's easier and we're gonna
00:18:30 define that as row array equals
00:18:33 int I for I and list board and then so
00:18:41 we want the specific row over on so it's
00:18:43 going to be board index of row but then
00:18:45 we want all the all the column positions
00:18:51 for that row so that's why we use this

00:18:53 colon right here you think that's what
00:18:56 we want let me just see and the entire
00:18:58 is just to make sure that we're always
00:19:00 getting something that's can be indexed
00:19:02 into the okay so what am I saying sorry
00:19:07 anti I think I just added this just to
00:19:10 be cautious that we didn't try to index
00:19:12 something with a float value or
00:19:14 something so that's our row array and so
00:19:18 then what we're gonna want to do is get
00:19:23 if this is like let's see we looked at
00:19:26 the board down here the row array would
00:19:28 be like this single list in here what
00:19:30 we're gonna do is look at all the pairs
00:19:34 of all the window sizes of four so to do
00:19:40 that we will do four see
00:19:44 in range column count minus three and
00:19:49 the reason we do minus three is because
00:19:51 the last one we're going to look at is
00:19:53 this so we don't look it
00:19:55 look we don't start with these last
00:19:57 three as the farthest to the left if
00:20:00 that makes sense
00:20:00 I'm highlighting grade in this area if
00:20:02 you missed that okay so we're getting
00:20:07 the horizontal windows and so the window
00:20:11 then will be a four will be the row
00:20:15 array and we're gonna index that from
00:20:19 our starting position so that's going to
00:20:20 be from C to C plus I guess four would
00:20:28 it be four or three after I think let's
00:20:32 do before yeah C plus four and we can
00:20:35 actually make this a variable too just
00:20:38 so you know where that 4 is coming from
00:20:39 I'm trying to call this window length so
00:20:43 window length equals four so window
00:20:49 length so we're getting four at a time
00:20:53 and then what we're gonna want to do
00:20:54 with that is count the number of ones
00:20:58 and two so a eyepieces
00:21:00 and you know player pieces whatnot so
00:21:03 what we're gonna do with this window is
00:21:05 there's a built in function of lists in
00:21:07 Python dot count so what I'm going to do
00:21:10 is count the piece that we're passing it
00:21:14 to the score position function and if
00:21:17 that equals equals four so that would be
00:21:19 we win so I guess if window dot count
00:21:24 piece equals equals four let's say we
00:21:27 have a score that we're defining so
00:21:30 score is zero initially will say score
00:21:34 plus equals like a hundred right so if
00:21:39 we ever find four in a row on the board
00:21:41 that's a really good board obviously and
00:21:44 so we should try to get that move okay
00:21:48 so we have score plus equals 100 and
00:21:51 then once we're done we're just gonna do
00:21:53 horizontal for now and I'll fill in will
00:21:55 fill in the diag
00:21:57 and vertical later turn score okay so
00:22:01 now we have this score position function
00:22:03 that looks at a single board state and
00:22:06 gives the score of a hundred if it is a
00:22:09 connect four and gives zero otherwise
00:22:15 and I guess for the sake of this that's
00:22:18 also preference three in our Ibis why
00:22:22 not
00:22:22 or maybe yeah three in a row so if I'll
00:22:28 define this above I'll define it below
00:22:34 LF window dot count piece equals equals
00:22:40 three and window dot count of zero so we
00:22:45 should define this as a piece to so
00:22:47 empty equals zero this is just how we
00:22:50 are storing the values behind the scenes
00:22:53 we know that account of empty equals
00:22:57 equals one then let's add I don't know
00:23:01 ten to our score so this is three and
00:23:06 Rose this is four and Rose right and
00:23:09 then we needed to find one more function
00:23:10 and that is just like pick best move and
00:23:17 that will give taking a board and what
00:23:20 else does this need to take in I'll
00:23:25 start with just the board potentially I
00:23:28 guess the piece too yeah why not pick
00:23:32 the best move so what we're gonna do
00:23:33 with this is we need to look at all the
00:23:37 different columns we can make the move
00:23:38 and then basically run the score
00:23:40 position on all those columns and then
00:23:42 pick the highest score that is returned
00:23:45 so we will write that as follows so we
00:23:54 have a function called I think Valley
00:23:55 locations if I'm not mistaken okay no we
00:23:58 don't but we can define a function
00:24:03 called valid locations real quick so I'm
00:24:06 going to do that
00:24:07 deaf valid Luke this call it get valid
00:24:12 locations so this will show us which
00:24:15 columns we can actually drop it in and
00:24:17 then evaluate from there that is the

00:24:19 board
00:24:19 we don't need actually have a piece to
00:24:21 figure out if it's a valid location or
00:24:23 not and so Valley locations is an empty
00:24:26 list to begin and for column in range
00:24:30 column count we don't have to do the
00:24:34 minus one here because this is exclusive
00:24:37 that that last value if is valid the
00:24:42 location of board and column then we
00:24:47 want to append that specific column
00:24:50 because that is a found location this is
00:24:51 just getting us a list of where we can
00:24:52 draw this because we'll be doing a lot
00:24:55 this a lot so it's good extract it into
00:24:57 a function valid locations dot append
00:25:00 column and then finally when we're done
00:25:05 we'll want to return the valid locations
00:25:08 okay so now we have valid occasions so
00:25:11 in our pick best move we'll need to use
00:25:13 this so valid locations equals get valid
00:25:19 locations of the board and let's think
00:25:23 what else we need to do so what we're
00:25:26 gonna want to do is for column in valid
00:25:29 locations we want to figure out what the
00:25:33 row is basically what we're gonna do is
00:25:35 to make our life easier is we're going
00:25:38 to pretty much simulate dropping a piece
00:25:41 and then have this new board that
00:25:43 actually gets passed into the score
00:25:45 position because we actually just take
00:25:46 in a board object there so we have to
00:25:48 kind of simulate each move to actually
00:25:50 evaluate using that function so we're
00:25:53 going to do is use our function get next
00:25:57 open row and that takes in the board and
00:25:59 the column and then this is something
00:26:05 that's tricky and not intuitive is we
00:26:08 can't just drop the piece into our
00:26:10 current board and array we can't even do
00:26:13 something like this we can't say like
00:26:14 temp board equals board and then say
00:26:19 okay let's
00:26:21 drop drop piece in the temp Ford and
00:26:29 row-column and I guess piece we can't
00:26:35 use this temp barred to simulate the
00:26:40 drop piece because what actually happens
00:26:41 with the numpy objects that we're using
00:26:43 to store all the values is that this
00:26:46 temp board ends up pointing to the same
00:26:48 exact memory location as the original
00:26:51 board so what we actually need to do is
00:26:54 make a copy of this board so this is
00:26:56 creating a new memory location where our
00:26:59 board is sitting and what we're doing is
00:27:01 pressing that new memory location into
00:27:06 our drop piece function so any
00:27:07 modifications don't modify our original
00:27:10 board hopefully that made sense just
00:27:14 draw a piece and then we want to
00:27:17 basically find the score of the new
00:27:20 board so guess what happens is this drop
00:27:25 piece automatically modifies temp board
00:27:27 so we can just go ahead and do score
00:27:32 equals score position of the temp board
00:27:41 and whatever piece that we dropped and
00:27:45 then what we'll want to do is basically
00:27:47 keep track of a best score so we'll say
00:27:55 best score and we'll set that to zero
00:27:59 initially and we'll have best column and
00:28:01 that'll just be like we'll just put it
00:28:07 as a random choice of the valid
00:28:12 locations and I defined about
00:28:15 applications below this so I'm gonna
00:28:17 just move these remove that down here
00:28:21 okay so we have our best score and our
00:28:24 best calm best score is initially zero
00:28:27 best calm is just random but what we can
00:28:29 do is if this score that we scored with
00:28:32 this new board
00:28:34 is greater than if score is greater than
00:28:37 best score then we can set our new best
00:28:42 score to score and we can set the new
00:28:47 best column to whatever column we were
00:28:50 checking when we got this new score okay
00:28:56 does that make sense and then finally
00:28:58 once we do this we'll do return that's
00:29:03 call think that it looks right all right
00:29:10 let's try that out real quick so all we
00:29:16 should see here is we didn't add that
00:29:17 anything too complex we just made it
00:29:20 preference winning horizontally and
00:29:23 getting three in rows horizontally so we
00:29:25 shouldn't be looking at any sort of
00:29:26 vertical maneuver okay so instead of the
00:29:31 random location here I'm going to
00:29:33 comment this out and do column equals
00:29:38 pick best move of the board and I guess
00:29:44 we're the AI here so I need to pass in
00:29:47 the AI piece come on moment of truth
00:29:57 I'm going to stack on top of okay so now

00:30:01 we should see it connect three in a row
00:30:03 that's what we're hoping for and it did
00:30:06 it cool so I'm going to just stack up
00:30:08 top again the way we scored it too it
00:30:10 should now preference feeling this in
00:30:13 after I drop which it did whoo we got
00:30:16 something a little bit smarter okay now
00:30:18 that we have the score working for the
00:30:19 horizontal moves we can kind of expand
00:30:22 upon this and make it work for diagonal
00:30:25 and vertical as well I also do a little
00:30:27 play a little bit of cleaning so it yeah
00:30:30 we're here's the code okay
00:30:35 pick us move struggling it okay yeah so
00:30:41 this is horizontal so we need to also do
00:30:45 vertical vertical is also easy so score
00:30:48 or vertical do next so that before
00:30:52 column and range column count the ones
00:30:58 that are tricky are the diagonals so
00:31:00 we're doing the exact same thing we did
00:31:01 with horizontal but we're gonna do it
00:31:04 with vertical and then once we have it
00:31:07 for each one will actually probably
00:31:09 improve how we're actually scoring this
00:31:11 make it more like I did in the we did in
00:31:13 the other video right for C and range
00:31:17 column count let's see what else we
00:31:19 should do we should then get the column
00:31:21 array gray which is going to be similar
00:31:26 to the last time it's gonna be int I for
00:31:31 I in list so this time we have the we
00:31:38 want to get every row position for a
00:31:42 specific column so we can do it like
00:31:44 this I believe I think that's what we
00:31:47 want and then we'll want to iterate
00:31:49 through the windows just like we did
00:31:51 last time but now we have to iterate
00:31:53 through the row window so for our and
00:31:56 range row count minus three window
00:32:02 equals row array C or R to R plus window
00:32:10 lengths and we can copy this one sweet
00:32:15 now that we have the window this code is
00:32:18 oh she didn't want to delete it this
00:32:20 could is the exact same so I can just
00:32:21 add this code and what we're gonna altum
00:32:23 Utley do is abstract away this window
00:32:26 counting stuff to its own function so
00:32:30 okay so now it should if we run this
00:32:33 again it should preference vertical as
00:32:38 well so I'm gonna block the horizontal
00:32:41 and it's still stupid and it's oh it
00:32:45 actually did block me that's interesting
00:32:47 but I'm gonna let it get okay so now
00:32:49 that it has two verticals in a row it
00:32:51 should preference making the move right
00:32:53 on top of it next it
00:32:55 that's right and it didn't so I'm
00:32:57 guessing we did something screwy it's
00:32:59 weird
00:33:01 hmmm this is weird
00:33:04 maybe it's just getting lucky ok it
00:33:08 should hopefully win vertically let's
00:33:10 see I don't know we did something wrong
00:33:13 window count piece score plus equals 100
00:33:22 what did I do wrong here oh shoot I
00:33:26 grabbed row array this needs to now be
00:33:29 column array okay sorry about that and
00:33:33 also for our Ranger okay yeah okay that
00:33:37 should be good hopefully let's see if it
00:33:39 preferences vertical moves now – so I'm
00:33:42 blocking the horizontal and now
00:33:45 basically once it stacks
00:33:47 chute we're gonna block the horizontal
00:33:49 again but come on okay let me play it
00:33:56 again so you can see exactly what I was
00:33:57 trying to show you right so it goes I'm
00:34:00 gonna block the horizontal hopefully it
00:34:03 stacks on top okay now that it's stacked
00:34:04 on top we should because it doesn't have
00:34:06 any sort of horizontal options it should
00:34:09 stack again and it does and so it now
00:34:13 should win vertically okay cool it's
00:34:15 over that we kind of mainly validated
00:34:17 that it was getting these windows
00:34:19 correctly for the vertical okay so this
00:34:23 was getting if we think about this same
00:34:25 graph it was looking at like the sliver
00:34:30 if we just cut off this one column it it
00:34:34 was making a list out of these sorry
00:34:38 these numbers zero zero two two two two
00:34:44 okay now let's do diagonals diagonals
00:34:51 are a little bit weird so we'll start
00:34:54 with the positively sloped diagonals so
00:34:57 the ones that are low on the left side
00:34:59 and rise up to the right side so score
00:35:03 positive sloped diagonal
00:35:08 all right so let's just run the game
00:35:10 real quick just to see that how we're
00:35:12 gonna do this so basically if you look
00:35:15 at my mouse we're gonna look at all the

00:35:18 possible ways we can do this diagonal
00:35:22 slope so we can do like this we can move
00:35:25 over do this move or do this go over do
00:35:29 this and then rise up one row and do the
00:35:33 same thing so basically now we have to
00:35:37 go from like row count minus three as
00:35:40 well as column count minus three and do
00:35:42 a little bit of minute bidding like that
00:35:44 and it's a little bit weird to get our
00:35:45 windows but it shouldn't be too too bad
00:35:47 so let's start with this so we're gonna
00:35:50 iterate starting with the rows so for a
00:35:53 row are in range row count minus three
00:35:58 because we're gonna be cut off at the
00:36:03 top because we're going up each time
00:36:04 once and then for C and range column
00:36:08 count count minus three
00:36:14 because we can't just have a okay so and
00:36:18 that's because we're going to the right
00:36:21 each time for so we have to cut off
00:36:22 early for that as well and then what we
00:36:26 need to do is our window is going to now
00:36:28 be we're going to do a little list
00:36:31 comprehension to do this it's going to
00:36:33 be the board at the row position and
00:36:36 then at the column position and what
00:36:41 we're gonna have to do is we're gonna
00:36:43 have to add a little bit of value each
00:36:45 time so it should start with zero so
00:36:47 we're after that we're gonna just add
00:36:48 some I plus I and that's gonna be for I
00:36:53 in range window length so basically
00:36:57 what's happening is if you think about
00:36:58 what I takes on if window length is four
00:37:01 I is going to start out at zero so
00:37:03 that's going to be just the earth the
00:37:07 position at R comma C then we're going
00:37:11 to this is going to become one so we're
00:37:13 going to increase positively one and one
00:37:16 so we're gonna go up in
00:37:18 across and that will continue and we'll
00:37:21 actually get our window in the proper
00:37:26 will get it will get us window size of
00:37:28 four that is a diagonal and this will
00:37:31 repeat this window right here will
00:37:34 repeat for all of these values so we'll
00:37:37 end up getting all of the positively
00:37:39 sloped diagonals and so we're gonna just
00:37:42 be and just copy this code here and we
00:37:50 can do the same for negatively sloped to
00:37:52 diagnose so for R and range will do the
00:37:55 exact same thing oh my gosh stop texting
00:37:58 me
00:37:58 ah sorry for C and range column cap
00:38:04 minus three and this is a little bit
00:38:07 trickier because now we need to stop
00:38:08 start at the top and go downwards so to
00:38:12 do that bear with me
00:38:14 we're gonna want our window to be equal
00:38:17 to do list comprehension again board R
00:38:20 so this is going to be the same exact as
00:38:23 before but now oh my gosh this is
00:38:28 annoying
00:38:30 Wow
00:38:32 I'm never what is this crap sorry I'm
00:38:39 gonna turn off the volume there we go
00:38:43 okay so what I was saying was now the
00:38:46 first thing we check is up here so
00:38:52 that's going to be the row plus one plus
00:38:55 two plus three to get that position so
00:39:01 that's gonna be Rho plus three and then
00:39:10 the C I think will stay the same I know
00:39:12 we're going to be going downward so
00:39:13 that's going to be C plus three as well
00:39:17 to get the position we're looking for
00:39:22 because we're going downwards to C plus
00:39:24 three
00:39:25 do we want C plus three yeah that should
00:39:31 work
00:39:34 sorry I'm just confusing myself now I
00:39:39 guess the C stays the same
00:39:42 so C is normal and Rho plus three and
00:39:47 then we'll – I and we will in this case
00:39:51 we will plus I for I in range window
00:39:59 length think that should work
00:40:04 let's think so if we think about all the
00:40:08 different combinations start with this
00:40:14 position that's the seer the 0th column
00:40:17 that's good then we go down one the road
00:40:20 decrease but the column increased down
00:40:23 again row increase with the column
00:40:25 decreased down again row increase or Rho
00:40:28 decreases but column increases so I
00:40:31 think what we did here is good and we
00:40:34 can score that just like we scored the
00:40:35 other ones so a little bit tougher to
00:40:38 test so what we'll do to test these is
00:40:42 will temporarily comment out the
00:40:46 horizontal and vertical and just see if
00:40:48 it when it has the option and sees the

00:40:51 day I know that it preferences it so
00:40:54 I'll make it easier for it
00:40:57 so if it puts it here here we should see
00:41:00 on the next time it putting a three in
00:41:02 the row okay yep it did I made them
00:41:06 moves a little bit quick but as we can
00:41:08 continue basically oh shoot
00:41:11 don't make that if I put it right here
00:41:14 it should if we implemented these
00:41:16 diagonals properly connect it
00:41:18 yay we can go ahead and uncomment all of
00:41:22 this now that we've checked that
00:41:24 diagonal I guess we should ideally check
00:41:25 positively sloped too but I'm pretty
00:41:28 sure we're good there okay and now what
00:41:31 I recommend we do is we're gonna add a
00:41:33 couple more different ways we can score
00:41:35 this and just so we don't copy all this
00:41:37 into each one of these individually
00:41:40 let's abstract out a new function called
00:41:42 like I don't know in fact called window
00:41:47 evaluate window about evaluate window
00:41:51 and we'll take in the board and piece
00:41:55 that earlier I guess not the board we
00:41:58 just need the window and I guess the
00:41:59 piece for that so this is going to be
00:42:02 the exact same thing as we did before so
00:42:04 if window dot count piece equals equals
00:42:10 four score plus equals 100 LF window dot
00:42:18 count piece equals equals three and
00:42:23 window dot count is empty equals equals
00:42:29 one score plus C equals ten let's think
00:42:33 what else we should have should also
00:42:35 have an LF for window dot count piece
00:42:39 equals equals two I guess we it doesn't
00:42:44 really matter if we use it for hell if I
00:42:45 don't think here and window dot camped
00:42:48 empty
00:42:49 actually it does I know it doesn't I
00:42:52 don't think it those empty equals equals
00:42:55 to the do score plus equals five and
00:42:59 these values these are kind of arbitrary
00:43:02 and I'm fine leaving them as kind of
00:43:04 arbitrary eyes I really need to extract
00:43:05 these out into their own variables I
00:43:07 guess I could
00:43:08 wanted to but basically these are the
00:43:10 type of values you play around with as
00:43:12 you kind of tune and try to make your AI
00:43:13 better let's see what else we could do
00:43:16 we could also have like I guess in verse
00:43:21 piece so this would be the opponent
00:43:23 piece so I can just call it opponent
00:43:26 piece equals we'll just say player piece
00:43:37 point apiece equals player piece and if
00:43:40 piece equals equals player piece then we
00:43:45 just need to switch it so that would be
00:43:47 and then opponent piece would be equal
00:43:51 to AI piece if that made sense what I
00:43:55 did I just was saying that okay let's
00:43:56 assume where the AI and set the opponent
00:43:58 piece to be player piece but if we're
00:44:01 not the AI and where the player and
00:44:02 where I've added in the window then the
00:44:04 opponent piece should be AI piece so we
00:44:07 could also do is something like if
00:44:09 window dot count opponent piece equals
00:44:16 equals three and window count dot
00:44:19 opponent or see window count empty
00:44:23 equals goes one then that means the
00:44:26 opponent has a three in a row and we
00:44:27 could do like score minus equals eight
00:44:30 let's say so it's like we weigh us
00:44:34 getting a three in a row more than we
00:44:36 weigh the opponent getting a three in a
00:44:38 row okay just to finish up this function
00:44:41 we should initialize score equals zero
00:44:44 and it will return score at the end and
00:44:47 this is just going to be so then when we
00:44:48 actually go into the score position you
00:44:51 can delete these lines and what we'll
00:44:52 actually do is do score plus equals
00:44:55 evaluate window of window piece and we
00:45:04 just copy this line here for each of the
00:45:06 other locations that we added these
00:45:08 logic cool cool
00:45:15 cool all right let's see what happens
00:45:21 Auto plus equals none type oh yeah she
00:45:29 better tan the score okay so we should
00:45:35 be seeing some preference so it should
00:45:39 probably want to get this three in a row
00:45:41 yep
00:45:43 okay will it block me so it doesn't seem
00:45:54 to be blocking me let's see if it
00:45:55 preferences diagonal downwards
00:45:58 I guess it's diagonals that way let's
00:46:02 see if it preferences diagonal downwards
00:46:03 now cool it's looking pretty good
00:46:06 however it's not blocking me so that is
00:46:09 an issue so it's not blocking me and the

00:46:18 reason it's not blocking me I just
00:46:20 realized is if we look at this if we
00:46:23 think about how this evaluate window is
00:46:25 working we're only calling it for the AI
00:46:27 so if the AI ever sees the opponent has
00:46:30 three and the window count is one empty
00:46:34 is one then the opponent already has
00:46:36 three so would be able to win in the
00:46:39 next case so in this case it would be
00:46:40 preferencing putting three in a row over
00:46:43 blocking the opponent so watch what
00:46:45 happens if I make this like negative
00:46:47 eighty now it's going to preference and
00:46:50 I also will have to will have to change
00:46:53 the best score to be some sort of low
00:46:55 negative number to start just so it
00:46:57 doesn't screw up if we get a negative
00:47:00 here now it should block always block if
00:47:04 I ever get three in a row yeah see that
00:47:09 cool I don't know if we'll keep this in
00:47:11 when we go to minimax and we're gonna go
00:47:13 to mid max rate around right really soon
00:47:16 the last thing I want to add before we
00:47:18 go to implementing the min max algorithm
00:47:21 is just scoring the center columns and
00:47:25 and you know adding preference for
00:47:26 center pieces because
00:47:28 that's what's going to create more
00:47:30 opportunities with the diagonals and
00:47:32 horizontals is if you have the center
00:47:34 center pieces okay so we can get our
00:47:39 Center array so score Center and I guess
00:47:42 this should be I'm going to move this
00:47:47 comment right below the score equals
00:47:51 zero move this up a bit and now I'm
00:47:56 going to add the score center column so
00:48:00 we're gonna create a center array just
00:48:02 like we were kind of making the row or
00:48:04 the column arrays within the score
00:48:07 vertical so we're going to do equals int
00:48:12 I for I and lists we want the board and
00:48:18 we want every row position but we only
00:48:21 want the center column so we can do
00:48:23 column count and then we could just you
00:48:26 know may and I think about it 0 1 2 3
00:48:29 would be the middle but just to kind of
00:48:32 not have magic numbers I'm going to do
00:48:34 floor division by 2 so that will get the
00:48:37 the middle column and then what we want
00:48:41 to do is just do Center count I guess
00:48:45 equals Center array dot count piece and
00:48:51 then we'll just add to our score I don't
00:48:54 know three points or so let's see I'm
00:48:59 kind of did some weird numbers here I
00:49:01 would had like six for each piece in the
00:49:06 center so Center her score plus equals
00:49:11 six let's say and these numbers are all
00:49:13 going to change so don't worry too much
00:49:15 about all the score increases this is
00:49:18 something you play around with okay
00:49:20 let's see if it's preferencing Center
00:49:21 now should not have gone there for this
00:49:27 preferencing Center score plus y equals
00:49:30 six
00:49:32 let's really crank up this score real
00:49:34 quick
00:49:35 and see if it works it's weird yes
00:49:43 something is goofing oh okay sorry I was
00:49:50 doing plus equals six but it was it
00:49:52 should be plus equals Center count times
00:49:58 six right so if you had two it'd be 12
00:50:01 plus 12 it would be if you had three
00:50:05 would be plus 18 etc okay now it looks
00:50:11 like it's preferencing Center we'll see
00:50:16 should block okay cool no I think it
00:50:20 should go Center if I'm not mistaken yep
00:50:24 cool and probably should go Center again
00:50:26 if I'm not mistaken okay I guess that
00:50:33 created more diagonals but okay Center
00:50:36 cool should block and go Center cool
00:50:39 I think that's accounting for the center
00:50:41 alright with that I think we're ready to
00:50:43 move on to the min/max algorithm and
00:50:45 what I think is helpful at least when I
00:50:48 was implementing this is I went ahead
00:50:50 and just was reviewing the Wikipedia
00:50:53 page on minimax so you know if you
00:50:57 didn't watch through the video I posted
00:50:58 minimax is basically a way so that we
00:51:01 can look down the branches of any sort
00:51:04 of rule based game like chess checkers
00:51:06 and in our case connect four so we can
00:51:11 basically look down at branches and
00:51:12 evaluate using our score function the
00:51:14 best branch that we can guarantee
00:51:16 getting so what I recommend we do is go
00:51:20 ahead and go to the pseudocode and this
00:51:23 is all we really have to implement so
00:51:26 function minimax node depth maximizing
00:51:29 player so the node in our case is going

00:51:32 to be the board depth is how far we want
00:51:35 to search down in our game and
00:51:36 maximizing player is going to be true
00:51:39 for the AI and false when we're looking
00:51:41 at the players move so let's go ahead
00:51:44 and
00:51:45 and this and I'll be kind of popping
00:51:48 this window back in and out okay so if
00:51:50 score position is good let's define mini
00:51:53 max okay
00:52:03 def mini max so we're going to pass in
00:52:07 the board we're going to pass in the
00:52:10 depth and we pass in the maximizing
00:52:14 player and I'm gonna just do pass for
00:52:19 now okay what do we need to do next in
00:52:20 this if the EPS depth equals zero or
00:52:25 node is a terminal node so what does the
00:52:27 terminal node in our case well that's
00:52:28 whenever a game is won or I guess we get
00:52:32 to the end of the game those would be
00:52:33 terminal node conditions so then we want
00:52:36 to return the heuristic value of that
00:52:38 node and else we want to kind of
00:52:41 recursively check our tree like you see
00:52:44 in this diagram down the bottom right
00:52:46 and find the best score so that's what's
00:52:49 happening down here let's start off
00:52:51 though with the I guess if depths equals
00:52:54 zero condition that's when we're going
00:52:55 to be returning the score position
00:52:58 function score okay so what are okay so
00:53:04 let's do this
00:53:06 if depth equals equals zero or terminal
00:53:14 node so this turn on node we haven't
00:53:17 defined yet so let's just define it so
00:53:19 what we just said was turtle nodes would
00:53:22 be us winning the opponent winning or
00:53:25 you know you've used all the pieces in
00:53:27 the game so let's do those so I'm going
00:53:33 to find another function sorry is
00:53:36 terminal node and now we'll just be true
00:53:39 if it is a terminal node and false if it
00:53:41 is not no path taken aboard so what are
00:53:44 the terminal node conditions well we
00:53:48 have this winning move function right
00:53:52 here so basically we can use this to our
00:53:53 advantage so if it's a win if this
00:53:57 returns true
00:53:57 for either of the pieces then it would
00:53:59 be a terminal node so those will be to
00:54:01 our conditions so we want to return
00:54:04 winning move board player piece or
00:54:13 winning move board AI piece or the final
00:54:23 condition is that there's no more valid
00:54:25 moves in the game so the board is
00:54:26 completely filled up so we can do in
00:54:28 this is we can say lengths get valid
00:54:31 locations of the board and that length
00:54:37 should be 0 if it's the terminal node so
00:54:40 this statement has is will return true
00:54:42 if it is a terminal node and false
00:54:44 otherwise
00:54:45 it's nice one-liner so what we're now
00:54:48 gonna do is I guess valid locations
00:54:52 equals get valid locations of the board
00:54:57 and then we're going to do is terminal
00:55:01 will be equal to is terminal node of the
00:55:08 board so now we can do if depth equals 0
00:55:11 or terminal node or I guess or is
00:55:16 terminal okay what do we want to do in
00:55:21 this case well there's three conditions
00:55:24 so if we are the AI then the first thing
00:55:28 we want to do is we want to if it is a
00:55:33 winning move for us the AI we want to do
00:55:35 if winning move so this is basically
00:55:39 just figuring out which case of these
00:55:41 three we're in if winning move board AI
00:55:50 piece then we want to return a high
00:56:00 score so return like
00:56:02 you know a really big number LF winning
00:56:06 move board player we want to return a
00:56:12 really or player piece sorry we want to
00:56:18 return a very low score and we're going
00:56:21 to augment this so it also has a
00:56:23 position but you'll see that in a sec
00:56:26 okay turn a really low score if it's
00:56:28 losing condition and then else this is
00:56:32 going to be when we evaluate our score
00:56:35 position this is a board that is not a
00:56:37 winning condition so and it's not a
00:56:40 terminal condition so we actually want
00:56:41 to get the score for it so we're gonna
00:56:43 do and I'm really just following if
00:56:49 you're getting confused with what I'm
00:56:50 doing I'm doing this step of the minimax
00:56:57 algorithm and I'm just finding the
00:56:59 heuristic value of the node and these
00:57:02 are kind of two edge cases the winning
00:57:03 move cases and I'm just handling them
00:57:06 separately I guess they could be kind of

00:57:08 factored into my minimax but just
00:57:13 because you know we're only really
00:57:17 looking at the opponents it might work
00:57:20 if I didn't handle these separately I
00:57:22 just in my head it makes it easier if I
00:57:25 handle these separately then finally the
00:57:27 else condition is when we want to I
00:57:33 guess the else condition here would be
00:57:36 the game is over so that's just kind of
00:57:38 like a weird case where we had returned
00:57:42 zero I suppose because you can't really
00:57:44 do anything from there alright cool so
00:57:49 we have the that's part of it and now
00:57:53 the final thing is if it is not no I'm
00:57:59 sorry if is terminal that's the is
00:58:03 terminal cases either we win the
00:58:06 opponent wins or the game is over
00:58:09 those are the three cases so I can just
00:58:12 even mark this game
00:58:13 is over comma no more valid moves the
00:58:19 other cases the depth is zero so you can
00:58:21 just do else here and that's going to be
00:58:23 depth is zero and in that case we want
00:58:27 to find the heuristic value of the board
00:58:29 so what we're going to do is just do
00:58:31 return score positions score position of
00:58:38 the board and I guess whatever piece we
00:58:42 dropped so in our case it would be the
00:58:45 AIS piece I guess maybe it would be good
00:58:48 to specify this but I'm just going to
00:58:54 keep it as the AI piece right now you
00:58:56 can fix it if you need to all right so
00:59:00 that's the first part of the minimax and
00:59:04 sorry if this I hopefully this is not
00:59:06 too confusing it'll all kind of fit
00:59:08 together once we you know get through
00:59:11 the rest of it all right let's finish
00:59:13 implementing the minimax so let's do the
00:59:16 bottom half of that when I was just
00:59:17 highlighting on the Wikipedia page also
00:59:19 this should be a piece the AI and the
00:59:25 player without the piece is just only
00:59:27 was used for the turn okay alright so
00:59:32 else yeah let's see what does that say
00:59:38 if maximizing player then and we
00:59:44 returned out of this so this week if you
00:59:47 get into this if statement you'll not
00:59:50 get into the other ones that were about
00:59:51 to define so if maximizing player and
00:59:56 I'm gonna just actually I think it'll be
00:59:57 easiest as if I just keep this on the
00:59:59 screen
01:00:06 where is the pseudocode pseudocode okay
01:00:11 cool so we have the pseudocode on the
01:00:15 screen and we have the code over here so
01:00:19 gosh not to make this the other half
01:00:22 okay not too bad alright so if
01:00:26 maximizing player I'm following right
01:00:29 here so my using player then we want to
01:00:35 initialize the score to some really low
01:00:38 value so we could do here is I think we
01:00:45 actually use if we actually want to
01:00:48 specify a negative infinity and positive
01:00:50 infinity I think what you can do instead
01:00:51 is we can do value equals math dot
01:01:00 infinity that works and I can actually
01:01:02 just do negative math dot infinity okay
01:01:05 so that covers that and then for each
01:01:08 child of notes that's for each position
01:01:10 we can drop in our connect for game so
01:01:13 what we're gonna do here is we're gonna
01:01:15 do for column invalid locations which I
01:01:21 already have to find up here fortunately
01:01:23 for us
01:01:24 calling invalid locations comma row
01:01:29 equals get next open row of the board
01:01:34 and that specific column that we're
01:01:36 looking at and then as before when
01:01:39 you're just doing this the score
01:01:41 position function we need to copy the
01:01:43 board so board copy just because
01:01:47 otherwise we'll use the exact same
01:01:48 memory location that the board is on so
01:01:50 it will really screw up when we're you
01:01:52 know our cursive Lea doing this okay and
01:01:55 we can go ahead and drop a piece in that
01:01:57 position you copy row column and we are
01:02:02 the if we're maximizing player then
01:02:05 where the AI piece alright and so what's
01:02:09 going to happen here is we're going to
01:02:11 have a new score
01:02:15 score which is going to be equal to the
01:02:19 minimax
01:02:21 which is going to be the max so if you
01:02:23 look at this it's going to be the max of
01:02:25 the current value which is negative math
01:02:27 infinity and minimax of depth minus 1 so
01:02:34 new score I guess would just be the max
01:02:38 of current square which was value and
01:02:42 minimax of this is our recursive call

01:02:47 here of the board copy depth minus 1 and
01:02:53 I guess we do false now because we're no
01:02:56 longer the maximizing player right now
01:02:59 the minimizing Peyer cool and then
01:03:02 finally what we'll want to do is return
01:03:05 the new score so that's the back to the
01:03:09 value and the minimax and we want to do
01:03:12 the same thing for the minimizing player
01:03:17 so else we know we are the minimizing
01:03:21 player and that is the code right here
01:03:26 we want to initialize the value to
01:03:29 positive infinity and now copy the same
01:03:36 thing for column invalid locations same
01:03:40 as for row equals getint next open row
01:03:44 of board and column we only need to copy
01:03:49 the board again because we don't want to
01:03:52 use that same memory location otherwise
01:03:54 might have issues when we try to recurse
01:03:56 back up the tree drop piece equals o
01:04:02 board copy row column and now we are
01:04:07 going to be the minimizing player so
01:04:11 what we need to do is actually make this
01:04:14 piece the player piece and same for the
01:04:22 new score though is going to be because
01:04:24 when we are if we remember
01:04:26 this the minimizing players trying to
01:04:28 take the lowest value so if you see this
01:04:30 node right here this 10 10 and plus
01:04:33 infinity 10 is the lower node so it
01:04:35 always take that so in the minimizing
01:04:41 player case we want to take be the new
01:04:43 score would be the min of the value and
01:04:49 minimax of word copy depth minus 1 and
01:04:56 then we want to do true for now
01:05:00 switching to the maximizing player so
01:05:02 this this false and this true is what's
01:05:05 allowing us to switch back and forth
01:05:07 between this maximizing player in the
01:05:10 minimizing player in the context of the
01:05:13 minimax algorithm and make sure you
01:05:16 understand the minimax algorithm watch
01:05:19 the video that I've posted previously on
01:05:20 it or just kind of review this Wikipedia
01:05:23 page to kind of get a feel for how it
01:05:25 works because that is crucially
01:05:26 important for understanding how this new
01:05:28 AI is working ok and we want to return
01:05:35 value or the new score cool I think this
01:05:40 is about it right think so however the
01:05:47 one issue I have right now as I look at
01:05:49 this is we're returning the score which
01:05:52 is good to know like how good of a move
01:05:55 can we make at a certain location but we
01:05:59 also need to augment the score with the
01:06:02 column that produces that score so in
01:06:05 addition to just producing or just
01:06:08 figuring out what the best score is we
01:06:10 need to figure out which column produces
01:06:12 that score so to do that we're gonna
01:06:15 just actually get rid of this Max and
01:06:17 min we're going to just break it out a
01:06:19 bit just it's easier to keep track of
01:06:21 what we need so we're gonna say that the
01:06:25 new score is equal to the minimax with
01:06:28 that same thing for this and instead of
01:06:35 doing it in just one line we're going to
01:06:37 just bring it to the new line so if
01:06:39 new score is greater than the value
01:06:45 value equals new score so this is the
01:06:49 same thing right now if we kept it like
01:06:51 this this is the same thing as the max
01:06:54 the one line our we just had but we also
01:06:56 want to do something like column so this
01:07:00 this column right here is like the best
01:07:02 column you can get so we could
01:07:04 initialize this to just a random choice
01:07:09 of the valid locations random dot choice
01:07:13 valid locations and same thing for down
01:07:18 here column equals random dot choice of
01:07:23 the valid applications right so now what
01:07:29 we have is column equals whatever column
01:07:32 we are currently iterating on that gave
01:07:34 us this new score when we recursively
01:07:36 did the minimax algorithm so that would
01:07:41 be call and okay that looks I think this
01:07:46 is good here we also no need to now
01:07:51 implement it down here same thing so
01:07:54 this time it would be if new score is
01:07:59 less than the value we want to do value
01:08:09 equals new score and column equals call
01:08:16 and we want to okay and then finally
01:08:22 what we have to do is instead of just
01:08:23 returning the score we want to return
01:08:26 both the score and the column that
01:08:29 produces that score so we'll return it
01:08:31 to false so do column and new score I
01:08:36 guess if value is our final thing that
01:08:38 we returned same thing here turn column
01:08:44 and value and then up here these are the
01:08:49 terminal conditions so if we get a

01:08:51 terminal
01:08:53 we don't actually know which column
01:08:57 produces the terminal location because
01:08:58 it's just looking at the board
01:08:59 particular but we can get that very
01:09:01 easily because we would get through this
01:09:05 so basically what we can do yeah so
01:09:10 basically when we returned this new
01:09:13 score right yeah so we're gonna augment
01:09:17 these none just has to basically all be
01:09:22 the same format even though these
01:09:24 wouldn't actually produce a column value
01:09:32 none zero okay so we don't know which
01:09:37 column produces those and basically what
01:09:40 we need to do now is if we want to just
01:09:42 the score we need to get the first index
01:09:44 you need to get the first index here is
01:09:47 that it I think that might be it
01:09:51 and then I guess right here – this would
01:09:54 just give us a score so in this case –
01:09:58 we need to do none to common score
01:10:01 positions so basically we're always
01:10:04 because this is a recursive function we
01:10:06 always needed to return the same format
01:10:08 so we're now just saying return us the
01:10:11 best score in the column that produces
01:10:14 the best score cool I think this is it
01:10:18 we can delete this pass so let's go
01:10:21 ahead and real quick test out our you
01:10:25 know our first attempt at the minimax
01:10:27 and to do that we can just go down to
01:10:30 here and – the best pick best move what
01:10:33 we're gonna do is do column equals
01:10:36 minimax of zero order I think it's board
01:10:44 then it is depth so let's just for sake
01:10:48 of simplicity we'll start with depth
01:10:50 equals two and then we are the
01:10:54 maximizing player so that isn't true
01:10:56 let's see if this works
01:11:02 nope damn is the location where do we
01:11:08 get the air where do we get this air too
01:11:17 many indices for array 267 if is valid
01:11:29 location shoot let's see oh alright yeah
01:11:40 sorry I was just trying to get the
01:11:41 column out of here but we actually get
01:11:43 the column and the minimax score so I
01:11:47 kind of have to unpack the tuple now
01:11:49 it's not just one thing it returns okay
01:11:58 all right so what we should see now
01:12:00 think at depth of two it should be smart
01:12:04 enough to block
01:12:05 I guess not yet I was hoping that it
01:12:09 would block me from getting this
01:12:12 situation where I could win on either
01:12:13 side I'm gonna try increasing the depth
01:12:16 to three and see if it does that right
01:12:22 so what I'm trying to see is if it's
01:12:23 looking ahead in the future and how we
01:12:25 can tell that is just looking ahead in
01:12:27 the future it should prevent us from
01:12:28 getting wins that can we can kind of
01:12:31 have two spots where we win so if I drop
01:12:36 it here it needs to block me so that I
01:12:37 can't get the horizontal three on the
01:12:39 bottom still is not doing it what the
01:12:42 heck
01:12:46 it might be some sort of error I
01:12:48 wouldn't just try one more time maybe
01:12:52 seeing if it's not looking far enough in
01:12:54 the future and do this depth for so this
01:12:57 is how far of a branch it's checking
01:13:00 yeah it's definitely having some issues
01:13:05 here it did win that time but it's
01:13:08 always picking zero
01:13:11 it's always picking the farthest to the
01:13:13 left and move why is that the reason it
01:13:17 is always picking the farthest to the
01:13:19 left even at depth of four is let's go
01:13:22 up and just check back why is my mouth
01:13:27 being so fidgety today won't scroll up
01:13:30 for me is okay I see it
01:13:39 if we look at where we are returning
01:13:42 this column and value it is inside of
01:13:44 the for loop so it's on the first column
01:13:48 basically and also we initialize the
01:13:50 value to negative infinity so it's
01:13:52 basically okay it's figuring out that
01:13:53 whatever score is on the farthest to the
01:13:55 left column it's gonna be bigger than
01:13:57 negative infinity so it's setting that
01:13:59 comb here and then returning it
01:14:01 immediately but we need to do is just
01:14:02 backspace this once and hopefully now it
01:14:06 should be pretty good and I probably
01:14:07 need to go depth of four I think about a
01:14:11 go to like depth of three and it will
01:14:12 still block just fine okay I kind of
01:14:19 want to go first just because I feel
01:14:21 like I'll see it easier okay so now it
01:14:28 needs to block one of my horizontals

01:14:30 which it does now which is good it needs
01:14:33 a block cool
01:14:34 that's looking good okay let's see if
01:14:37 it's looking into the future it should
01:14:40 put its piece right here next if I put
01:14:42 it up here cool it's looking good it's
01:14:45 like smart enough to know that like this
01:14:48 position right here where my mouse is
01:14:49 was the best spot to put it because that
01:14:51 gives us a win here and here so if it
01:14:53 looks in the future and knows it's going
01:14:55 to win it's not going to be easily
01:14:57 blocked by me looking good cool
01:15:04 all right real quick just because I'm
01:15:11 not positive how I feel about the values
01:15:13 that I currently set all these things up
01:15:15 here in the score positions function –
01:15:19 or I guess evaluate window I'm gonna
01:15:21 just change these to what I set when I
01:15:23 was playing around with this so the
01:15:25 window count equals four this actually
01:15:26 is pretty irrelevant at this point I
01:15:29 think the only reason this would play in
01:15:31 is if we set the depth equal to zero and
01:15:36 it had to use just this evaluate window
01:15:39 so I'm going to leave this in here but
01:15:41 this know that this is probably not too
01:15:43 important anymore
01:15:44 I'll still keep this value 100 okay
01:15:47 three and one so three in a row I'm
01:15:50 going to give this a weight of five two
01:15:55 in a row I'm going to give this a weight
01:15:56 of two and remember that it's in
01:15:58 multiple direction so you could have
01:15:59 multiple twos in a row and it adds up
01:16:03 opponent equalling three and one this is
01:16:07 not as important anymore because and
01:16:11 also I have to kind of make this a
01:16:13 smaller value because is this is
01:16:16 factored into the terminal condition
01:16:17 case so it will look ahead in the future
01:16:19 and make sure that it's not losing so
01:16:21 I'm gonna make that I minus four then
01:16:24 the other thing that I changed to is
01:16:25 instead of making this times six I'm
01:16:27 gonna make the center column worth plus
01:16:29 three and these are values you should
01:16:31 play around with so if you really want
01:16:32 an expert lowly I play around with these
01:16:34 values but honestly I feel like this air
01:16:37 right now like I'm gonna just play a
01:16:41 game like try to win I guess it's still
01:16:45 not amazing I guess its depth three
01:16:47 right now but yeah like look it like
01:16:51 it's making pretty good moves and it's
01:16:56 like gonna know to win if I put it there
01:16:58 I think this is a pretty good hey I at
01:16:59 this point to make it even better what
01:17:02 we can do is increase the depth of how
01:17:04 far it's looking where is that so if you
01:17:09 make it four that's looking if we think
01:17:12 about how the minimax
01:17:15 it's looking farther down in this tree
01:17:17 so this four would represent how far
01:17:20 it's looking down it's like right now
01:17:21 we're at depth force that's why it's
01:17:23 looking this far down and you can think
01:17:25 of this graph as being all the possible
01:17:27 ways they connect for board can work so
01:17:31 depth or let's see this would be even
01:17:34 better of an AI because it's looking
01:17:36 farther in the future we could even make
01:17:43 this better let's just go to depth five
01:17:45 and see what happens
01:17:53 okay I'm kind of having a problem I
01:17:55 don't know if you notice it but I did
01:17:57 depth five and it seems like it's just
01:18:01 oh it finally made a move it just takes
01:18:04 forever to make a move at this point try
01:18:08 to like think about why that is
01:18:12 you can even pause the video if you're
01:18:14 trying to like think about why that is
01:18:16 but yeah I mean if we're going if we're
01:18:22 doing depth 5 and we think about what
01:18:24 the minimax is doing it is branching out
01:18:27 at every step so the top of my hands is
01:18:30 the terminal node every time we do a
01:18:32 higher to oh my god I'm trying to be
01:18:34 even every time we do a higher depth we
01:18:37 expand exponentially more branches so
01:18:40 this is basically like 7 to the fifth
01:18:42 power or maybe even 6 power because we
01:18:45 also look at 0 so it is a lot of
01:18:47 branches to expand so it's going to run
01:18:50 slowly so 5 is probably the max you can
01:18:52 really do otherwise if you go to 6 your
01:18:55 computer's just going to explode
01:18:57 not really but basically it's probably
01:19:00 gonna freeze up and crash on you if you
01:19:01 go to 6 so this gets us to the final

01:19:05 thing I'm going to cover in the video
01:19:06 and that is the alpha beta pruning so
01:19:09 it's basically allowing us to go to
01:19:11 deeper depth by eliminating a lot of the
01:19:14 moves we have to
01:19:14 look at and I didn't actually cover this
01:19:16 in the video I posted about how does a
01:19:18 boardgame EIA work so check out a video
01:19:21 I posted in the description on kind of
01:19:23 the overview of it at a very high level
01:19:27 yet basically it is figuring out that
01:19:31 there are certain branches that a
01:19:34 computer is just or an AI is just not
01:19:36 likely to take if it realizes like in a
01:19:39 move if it goes a certain position that
01:19:41 it loses it's not going to go down that
01:19:42 branch so you can just not look further
01:19:44 down into the future there yeah so check
01:19:48 out that video real quick on alpha beta
01:19:50 pruning and then once you've watched the
01:19:51 video we will implement alpha beta
01:19:53 pruning to allow us to more quickly
01:19:56 search the depths we want okay
01:19:58 alpha beta pruning so just like when we
01:20:01 are doing the minimax what I recommend
01:20:04 is look going to the alpha beta pruning
01:20:08 Wikipedia page and there's also
01:20:13 pseudocode there so I think that's
01:20:14 helpful the pseudocode is helpful to
01:20:16 follow but it's just basically an
01:20:19 adaptation of what we've already seen
01:20:21 with the minimax
01:20:23 but now we have these two additional
01:20:25 parameters alpha and beta and you should
01:20:27 understand what these are now that
01:20:28 you've hopefully watch the video I
01:20:31 already had some knowledge about how it
01:20:33 worked so we're gonna go up to our sorry
01:20:41 I'm have this on another screen because
01:20:45 I don't want to screw this step up you
01:20:49 should yeah go to your minimax function
01:20:51 and we're gonna be adding our alpha and
01:20:54 our beta to that function and so we're
01:20:57 also going to have to pass this into all
01:21:00 of our other calls of it alpha beta and
01:21:06 right here alpha beta and we'll also
01:21:12 have to do it down here when we actually
01:21:15 call this and if we remember the alpha
01:21:19 and beta should be initialized to
01:21:22 negative math infinity and this is just
01:21:26 I'm looking at right
01:21:28 yeah the initial call right here
01:21:30 negative infinity negative bath infinity
01:21:34 math and infinity and true so that's the
01:21:38 initial call and then all right so let's
01:21:41 define this new minimax flushing with
01:21:43 alpha beta this should be a comment here
01:21:45 all right so let's see what it's doing
01:21:50 so basically all we're doing is that in
01:21:52 addition to getting our max value we
01:21:54 also are just evaluating the alpha so we
01:21:59 can do this below the new score stuff so
01:22:02 alpha equals max of the new score I
01:22:08 guess the value at this point we can do
01:22:10 value because it would have changed
01:22:12 value and alpha and then which we want
01:22:16 to do is or I'll just do it in the same
01:22:24 format that Wikipedia is doing so alpha
01:22:28 and the value okay and then what we want
01:22:34 to do is if alpha is greater than or
01:22:37 equal to beta then we want to break out
01:22:40 of our loop and that is good and then
01:22:45 same thing down here now we are the
01:22:51 minimizing player so we want to do beta
01:22:53 equals the min of the beta and the value
01:22:56 and if we find that alpha is greater
01:23:01 than or equal to beta then we have reset
01:23:03 condition where we're going to just
01:23:04 break off because we don't need to look
01:23:05 any more further in the tree and we'll
01:23:08 break so I think that's all we need to
01:23:13 do to implement alpha beta it's pretty
01:23:15 straightforward after you have the
01:23:16 minimax up and so let's run this real
01:23:19 quick
01:23:19 I'll probably it an error will say shoot
01:23:24 I needed not use my trackpad cuz
01:23:31 keep accidentally dropping pieces okay
01:23:35 it has peace there this should drop
01:23:36 quickly if before depth I was taking a
01:23:38 while now that we did this it should
01:23:40 drop quickly which was pretty good it's
01:23:43 pretty good reasonable more reasonable
01:23:47 than it was before for sure so I think
01:23:51 that is looking pretty good
01:23:53 and what we can honestly even do is now
01:23:56 that we're searching so far what we can
01:23:59 do is we have that initial time delay I
01:24:03 can actually just comment that out at
01:24:05 this point so this should be pretty

01:24:08 quick and we're going at depth five
01:24:10 which is pretty far down yeah that's not
01:24:13 bad I think even if we go to depth six
01:24:17 it's not too bad either but like before
01:24:19 if we went to def six it would take
01:24:22 forever
01:24:23 we'll see it also depends on what type
01:24:26 of processing power you have so I'm
01:24:29 going to try to have six here it's
01:24:33 taking a bit for sure did I do this
01:24:35 right it but not nearly as long as it
01:24:40 was taking before
01:24:41 yeah the alpha-beta pruning looks good
01:24:43 and one thing I just realized is that
01:24:46 you're gonna see more performance Keens
01:24:48 kind of as the game goes on further
01:24:49 because there's going to be at the start
01:24:51 of the game there's more possibilities
01:24:52 and less places that can break out of
01:24:54 that alpha-beta thing but as a game goes
01:24:56 kind of on you'll have more breaks
01:24:58 frequently so the performance gains will
01:25:00 be definitely seen as the game continues
01:25:02 on alright
01:25:06 that's where we're going to end what I
01:25:09 would say too is like we have a pretty
01:25:10 dang good AI as is but I didn't there
01:25:14 are additional things we could do to
01:25:16 make it even better so a couple ideas
01:25:19 that I'm thinking about is one thing is
01:25:22 that currently it doesn't wait lower
01:25:25 like so if you think of the game we're
01:25:27 gonna run it real quick if you think of
01:25:32 these rows down at the bottom like this
01:25:34 first row here the second row etcetera
01:25:37 it should we should wait we should wait
01:25:44 what am i translating we should wait the
01:25:46 lower wins select when you have three in
01:25:48 a row that's lower that's right be
01:25:50 weighted higher than if you have a three
01:25:53 in a row that's at the top here and
01:25:54 that's because you know as the game
01:25:57 fills up people have to put them on the
01:26:00 lower rows before the upper rows so like
01:26:02 if you are strategically playing as an
01:26:05 AI you would want to like put your
01:26:07 pieces down lower so you get more
01:26:09 chances to win also what I recommend is
01:26:12 you can make it even better than that by
01:26:14 watching the even-odd Connect for
01:26:17 strategy that I posted that's like a
01:26:18 really cool strategy that you could try
01:26:20 to implement with the AI you can also
01:26:23 they think and there's other things you
01:26:26 could play around with off thumb head
01:26:29 I'm kind of spacing right now but the
01:26:31 values all can be tuned of the scores
01:26:36 but yeah just have fun with it have fun
01:26:38 if you want to – if you like do
01:26:40 something really cool with your AI feel
01:26:42 free to email me I'll post a link to my
01:26:45 email your code and now maybe I'll like
01:26:47 stream myself playing some of your guys
01:26:48 is a eyes yeah that's all we got so if
01:26:53 you like this video and learn something
01:26:54 throwing a big thumbs up that would be
01:26:56 awesome and also make sure to subscribe
01:26:58 because I'll be posting more machine
01:27:02 learning a I type videos hopefully very
01:27:04 soon in the future but base make sure to
01:27:07 subscribe to not miss out yeah that's
01:27:11 all I have for this video thank you guys
01:27:15 for watching and peace out
01:27:18 [Music]

You may also like