Python Bot Plays Connect Four (using Minimax and some heuristics)

[@seporokey]

I really like your content. It's exactly what I'm doing to practice game dev. I've been recreating pen and paper games with AI bots. I want to try something like Spades next since I want to try and make an AI that plays a game with incomplete information.

[@gskartwii]

I have also been thinking about card game AI a lot, spades would be amazing as well as hearts. I would also love to see a video about that!

[@ltsMeNoodle]

Thanks for the idea! I think I might try making a hearts bot.

[@GamesComputersPlay]

Thanks, looked it up. Yes, I think AI for a trick-taking game, like Spades should be a fun thing to program. I am learning about quite a few great games from the comments!

[@mnzznxplay9747]

I remember when I was living in England we had c4 contest in our class. Rules were that first who will win three times is winner of match. I climbed up to the finale, then lost 2 times, but came back winning twice. Last, decisive match was intence, it led to position where me and opponent needed the same spot filled to win in empty column. I analysed this and came to conclusion that my opponent should be first to place circle here for my win. Also, if we weren't going to win on rest of field, she will be first to put circle in that column, so I just should not let her win on rest of the field. We filled it in such way that would not give anyone victory. And finally we came to that column. As I predicted, she put her circle first, then me. My 4-circle row was finally filled. Victory

[@rauljvila]

Excellent explanation! Now with minimax and heuristics the game has moved to the next level. I look forward to the next projects. Thanks for the videos, and especially for all the links to other resources.

[@dhillaz]

18:35 Wow, only when you said that did I realize how new your channel is. Your videos are to the standard of a much more established creator. I will be sure to hit the like button more often, so you get where you need to be. 👍

[@GamesComputersPlay]

Thanks, I really appreciate it. It's a bit of a stress knowing your videos get thousands of views (as opposed to how chill it was before, when not even my wife watched my videos), but it is a good, exciting stress!

[@gorillaau]

@@GamesComputersPlay Does your wife watches you videos these days? :-)

[@DanielBerke]

That's really neat. I love the visual representation of the game state in the code output. Also the visual puns for the game names were pretty funny. :) (As a Python programmer interested in learning a faster language myself, I've been looking into the Rust language recently.)

[@GamesComputersPlay]

Thanks. I did hear about Rust several times already: like it is as fast as C++, but much more friendlier, almost like Python. Sounds very promising.

[@sofia.eris.bauhaus]

1988, when men still were small disks of plastic. nowadays we don't have REAL MEN like this anymore 😔.

[@linkhorshaw9575]

You should ask codebullet to do a face off

[@underrated1524]

YES (Just in general, I would love to see a collab between Games Computers Play and the big CB.)

[@GamesComputersPlay]

His avatar images are definitely better. I would argue I make better PPTs???.... ¯\_(ツ)_/¯

[@MrConverse]

Loser does a face reveal?

[@lizzzylavender]

“It was actually solved by two guys, just a couple of weeks apart” Guys I think we found the reincarnations of Leibniz and Newton

[@Chloe-ju7jp]

you should face it off against a perfect bot... See how often it manages to win as first player. Or as second player with the perfect bot being forced to start in columns 1,2,6, or 7

[@GamesComputersPlay]

Just did that (manually, entering each move in the code), increasing the depth to 8 plies (makes it think a few seconds per move). As you can guess, my bot lost, but the fight it put up was better than I expected. Lost on the ply 32, with only 10 empty cells to go. One of those situations where there are deep "wells" on the board, and you just forced to make your move there. If I understand correctly how it works, there are a very special moves in the beginning red has to follow to force the victory. And this special beginning only can be deducted with very deep minimax analysis - (almost the whole game, 41 plies, if I understand correectly). So my puny little 8 plies are no match. Heuristics helps a little, but it's like having a good form for your deadlift while competing with a forklift.

[@Chloe-ju7jp]

@@GamesComputersPlay very interesting, thank you!

[@ScorpioneOrzion]

@@GamesComputersPlay tho the game itself is solved, as in from any given position you can tell what the result would be if both players play the best moves

[@themightyripples6582]

I was actually just about to mention something similar. I wonder how accurate GCP's bot was in the end? How close in accuracy to the perfect bot was it?

[@EebstertheGreat]

"Man" is a classic name for a piece on a board game. The best-known example is chessmen. In chess, the word "piece" is often used with a technical meaning that excludes pawns (and sometimes the king). But all of them together, particularly in older writing, are "men," even the queen. It's a little silly and doesn't make much grammatical sense anymore, but it is still used from time to time.

[@GamesComputersPlay]

I honestly never heard it in this context before (given I have only been speaking English on any decent level only a third of my life, but still). I have looked it up just now in the Oxford Learner's Dictionary - and, indeed, meaning number 14: an object you play with in a game. I absolutely enjoy these little obscure meanings of well-known words, so this one is quite a gem.

[@sobertillnoon]

F in chat for Second Guy. FeelsBadMan

[@GamesComputersPlay]

I feel there was a story worth of a Hollywood movie. I will probably cry in the end.

[@UofU10]

Love it! Excellent content!

[@R8Spike]

3:16 cracked me up

[@AbylaiMaster]

You missed E in connect four (title)

[@GamesComputersPlay]

Woopsie. Thanks, fixed! (It's almost 2 am here)

[@easytiger6570]

@@GamesComputersPlay Yekaterinburg?

[@GamesComputersPlay]

@@easytiger6570 A bit more to the East. And to the South. Actually, not a bit, a lot. Even to another country. I'm in Shanghai :)

[@easytiger6570]

@@GamesComputersPlay But time zones doesn't match

[@GamesComputersPlay]

@@easytiger6570 how do you mean? +8 GMT, it's 7 minutes past midnight here right now.

[@choco_jack7016]

you remind me of code bullet, which I like because you code practically useless stuff in a really interesting way.

[@choco_jack7016]

wait damn didn't expect you to talk about him

[@GamesComputersPlay]

Yes, it was after his videos I got the idea for this channel. He has some fun videos, totally agree.

[@MoreInsane96]

In italy we call it "Power Four"

[@renerpho]

I hope Code Bullet is okay. He had taken breaks between videos before, but not without any activity on other social media for almost a year.

[@ArmaRGool]

Great video dude

[@Raf99]

Dont know if its easter egg or not but you are with laptop on video and there is the same laptop in background layout. Funny :)

[@Swagpion]

I want to see this A.I. go against code bullet's connect 4 A.I.

[@GamesComputersPlay]

That would be quite an interesting match indeed. From what I understand, CB’s AI copies a lot of moves from “The perfect” algorithm. But it couldn’t copy it all - so it probably will be somewhat clueless after X moves. So it boils down to: can my heuristics algorithm hold on against “perfect algorithm” for X moves. IDK, too many unknowns to make a meaningful prediction. But I’d cheer for my guy, of course.

[@ionutdobrin8541]

I really like your content! Love what you do. I don't know if you ever played Catan, but in case you did or you would have the time to search the game up, do you think it can be programmed and actually test some of the strategies in the game? Would really mean a lot your input and thoughts.

[@GamesComputersPlay]

Thanks a lot! I heard about Settlers of Catan multiple times, never had a chance to actually play. From what I know it is a bit to complex to write a bot, but I never looked into it closely, so I can easily be wrong.

[@ionutdobrin8541]

@@GamesComputersPlay yes it is a fun game and pretty complex to program imo. But i would much rather know the opinion of an expert, so if you ever have the time to study it better, i would greatly appreciate an opinion.

[@tandemmints8934]

Yeah, it likely would be very difficult to write a bot for. There is a great deal of randomness and social dynamics involved. One of the better ways I've found to play is not to focus on so much on 'winning', but rather on just making sure others are having a good time. Do that and they are more likely to cooperate with you, which greatly increases your chances of winning. Anyways, I love the game and if you need people to play with to get a feel for it I would be up for it!

[@Bleuthatup]

Comentando para bumpearte el engagement. Gran canal. Suscribed

[@GamesComputersPlay]

Muchas gracias! "Bumpeare" e una palabra muy divertido!

[@arkadye]

Watching this I see two things that could make your bot a lot more competitive. A transposition table is fairly easy to implement and should save you a lot of time, as I think you're analysing the same position multiple times. It's particularly powerful in a game like Connect 4 where the number of moves is quite limited. The other thing is an "opening book" or database for the first few ply so you can always play the best couple of moves at the start.

[@GamesComputersPlay]

Yes, transpositional table was one of the things in the "perfect bot". I actually found that "perfect bot" tutorial when I finished the program and most of the script, so didn't have a chance to implement all those technics. You can say it was an experiment how far I could go by myself without using anything, except wikipedia. I tried to implement "dynamic programming" (which is not exactly the same thing, but kind of solving the same problem), but it didn't help much, so I abandoned the idea. "Open book" is a good idea, practically, but I don't like it on some other level. It almost feels like cheating, like the program gets the moves off of a cheat sheet...

[@queuebit]

Thoughts on building an AI / simluator for card games (like Euchre, Hearts, etc)?

[@GamesComputersPlay]

Yes, some of these are in the to do list. I actually simulated a kids card game called "War" - it was quite easy as it reauires zero decisions from playes. You can see what rules make it less likely to get stuck in a cycle and so on. Probably not enough material to put it in a video, but it was an interesting mini-project.

[@opaknack7249]

Very cool Dude making very cool vids

[@tctrainconstruct2592]

11:18 what about noughts and crosses? btw you could also have employed move ordering, transposition table, a bitboard, forward pruning (like ProbCut), CNS/PNS, an opening book and zugzwang evaluation. In the heuristic, you could also add in evaluation for dead columns and upcoming zugzwangs.

[@GamesComputersPlay]

Absolutely. But this was more like "Can I beat the game with as amature solution as possible?"

[@hisho_isa]

Good vid I enjoy

[@brayanlondono_]

Can you do battleship??!?

[@GamesComputersPlay]

Yes, absolutely in the list of games to try to write a bot for!

[@ayior]

I made a comment on one of your videos predictng that you were picked up by the algorithm then. I failed you, I'm sorry, I hope the growth you deserve will come soon

[@GamesComputersPlay]

Hey, don't kick yourself too hard. To be fair, I do take some long pauses between videos, that algorythm frowns upon. And Actually I am quite happy with the crowd I already have :)

[@Taterzz]

so assuming google translate is accurate, that would make you кодовая метка

[@GamesComputersPlay]

Haha, pretty close. It's more like кодовая пуля (метка is more like a mark, maybe like a bullet-point, I would say).

[@a-lil-ghoti]

I'm surprised you didn't try estimating the strength of the bots by reducing the search depth of your algorithm. Like if you don't even use minimax but use your heuristic, can you beat the medium bot? If not, how deep would you have to search? And how much did the heuristic help? What about other heuristics, even silly things like "Checkers in the middle are worth more than at the edges". If you follow up I'd be interested!

[@Komeuppance]

"Perchild" lol... is that even good enough for 2021?

[@stopitnowlol6697]

Could you do a coding tutorial? like your next project show how you wrote the code and a normal vid like this. Something like this where you use image recognition and stuff like that would be cool to learn.

[@GamesComputersPlay]

I'm afraid it would be one rather boring video. :) Also, and more importantly, as not a professional programmer, I do have a bunch of "bad habits" in the way I code, so I wouldn't recommend myself as a coding teacher. Picking up fun projects, creative problem-solving, can-do attitude (and of course modesty) - I may have these things, but not the flawless coding style. What is actually a good thing for me to do is to provide more comments in the code, so anybody can follow along more easily. I often forget that this is something I may later publish and cut corners more often than a good programmer should.

[@GamesComputersPlay]

I have updated the source code with a bunch of comments - should be more or less easy to figure out what's what now.

[@stopitnowlol6697]

@@GamesComputersPlay thank you!

[@NovemberOrWhatever]

I downloaded the code, and I'll see if I can make it play better in less time. I don't know OO though, so I'm converting it to functional.

[@GamesComputersPlay]

Sounds great. Let me know what result you manage to achieve! As for the code, there is definitely room for improvement. Here's what I can think of right now: - Better way of storing the data. I use string for positions, which was simple and easy. I'm pretty sure if you somehow encode it it numbers it can get much easier. - A way to speed up the whole thing - numba, just sugegsted in one of the comments (thank you to who suggested it). - Another comment (thanks to the author) suggeted transporation table and "openings book" - which definitely should have positiove effect. - Any other tricks the Pascal Pons'es tutorial has. I only implemented basic ones, so there is more. - Personally, if I haven't read Perfect Bot's manual (and didn't know that the game was solved), my next step would have been exploring the option of combining minimax and heuristic scoring. Score all the nodes and work out the way to highest scores.

[@NovemberOrWhatever]

@@GamesComputersPlay Converting OO to functional (or at least mostly functional) is hard. I haven't spent too much time working on it so far, but I'm making some headway. I'm averaging .002 seconds per turn despite not using @jit, so I'm pretty sure it's not doing as much calculation as it should be.

[@helloiamenergyman]

Nice :)

[@arandomyoutubenerd276]

Pog! This is really interesting! Sorry to ask you again but are you able to help us with a Risk program me and some others are trying to make?

[@moonflocookie]

What is your problem?

[@arandomyoutubenerd276]

@@moonflocookie a lot lol, do you have Discord?

[@laytonjr6601]

The game is much more complex to modelise than monopoly, good luck!

[@arandomyoutubenerd276]

@@laytonjr6601 yah Thanks

[@GamesComputersPlay]

Risk is definitely in the backlog, although to be honest, right now I don'twouldn't even know where to begin. The very first part - where players have to place their pieces is already very confusing.

[@antcubingx]

Hi! can you make a video about uno! I love your videos!

[@GamesComputersPlay]

Thanks a lot. Yes, quite a few people suggested Uno. I actually still need to learn to how to play it myself, as I have never played it Anyway, it definitely goes in the "to-do" list of projects!

[@snellface]

****** you are welcome, great vidoes btw ****** :p

[@nathanb011]

I think you would find Numba rather useful.

[@GamesComputersPlay]

Thanks! Haven't heard of it, Googled just now. It does look really promising, especially the part where you don't really need to change your code much. Should give it a go in one of the futuree projects.

[@nathanb011]

@@GamesComputersPlay nothing beats native code, but it is extremely useful 👍

[@DIGGERfromAR]

Remove the unnecessary virtue signaling.

[@GamesComputersPlay]

And I didn't even get to the the whole "white move first" controversy.

[@yoshi6421]

Obviously didn't pause