Coding

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]