Think You’re Good At Connect 4?

I won’t question your adeptness at a favorite childhood game, but my bot Herbert will. Myself and a few other guys developed Herbert for our final project in AI class, and he is frustratingly unbeatable. After a game or two against him, you might consider an early retirement from the Connect 4 world. [Update 3/3/2012 I have uploaded Herbert for you to download and play against. See details at bottom of this post for more]

‘Herbert’ as I affectionately named him is a piece of software that implements a MiniMax with Alpha Beta Cutoffs search algorithm. Basically all this means is that Herbert will look at the current game state board, generate the possible moves one could make from that board, then the possible moves from those boards, and so on, creating a large tree of possible boards which it then ranks as optimal or suboptimal. It will make a move towards a board it deems the best one.

As the number of all possible boards for even something like a Connect 4 board is very, very large, Herbert can’t look at all of them, and therefore must make some decisions based on just what he can foresee, like a human player. To ensure Herbert wouldn’t spend too much time searching, we implemented an iterative deepening loop so that he could break out when he found a win or ran out of allotted time to search.

The result is a bot that is nearly unbeatable. Herbert performed very well in his AI debut-at a tournament against the other Connect 4 bots in the class. Due to a mixup, we played the majority of the games at the tournament with an older version of Herbert, and got the new, beefed up Herbert just before tournament end, and proceeded to whoop every bot we came up against. Too bad Herbert v2’s performance wasn’t good enough; we came in third place or so out of eight teams. Herbert 2.0, though, went undefeated.

The really cool thing about a MiniMax algorithm is that it will play optimally well against an optimal opponent (i.e. another Connect 4 bot), provided you ‘rank’ your generated boards properly to choose the right path. using Alpha Beta cutoffs effectively can also narrow the search and greatly cut down search time. What Alpha Beta cutoffs basically mean is that we can determine ahead of time whether evaluating boards down a certain branch of the tree will possibly affect our current ‘best path’ or not, and if it doesn’t, we don’t search it!

My personal responsibilities on the project were vast; I can not claim credit for the majority implementation of the MiniMax algorithm or most of the functions used to evaluate boards for optimality (although I spent A LOT of time helping the guys who did implement these improve them and debug them), I created the graphical user interface (GUI), or at least about 98% of it.

If you’ve read any of my older posts, you may have stumbled across my rendition of the Simpson’s living room in 3D. Building this scene took at least as long as that one. First of all, I do not claim to be anywhere near an expert in openGL, but I’m darn proud of how this thing turned out.

Again, the entire scene is rendered using openGL primitives (and a texture or two). The thing is… How do you create a connect 4 board? Each ‘slot’ is basically a cube with a spherical/cylindrical hole in it, and openGL doesn’t have a native shape like that to my knowledge. So I had two options: either define the vertices of the shape myself, or approximate it using openGL primitives. I chose the latter. Here’s how I did it:

openGL natively supports rendering toruses (donut shapes): so I started by rendering just the open slots, generating a board that looked something like this:

Now, from here, we can just generate cubes (stretched a bit, of course) to cover the gaps just perfectly enough, like so:

This solution works well enough, but is hardly perfect. If you look closely enough, you can see that little gap of white. The same is true of the actual board, although it’s so subtle you’d hardly ever notice it (except for me, who spent days looking at, to me it’s glaringly obvious).

The result is that you look like you have… a cube with a circular hole cut out. Perfect.

I’d like to say after getting the board to render perfectly all the pieces just fell into place from there, but that’s far from the truth. I had to implement a mouse tracker that would render a transparent piece to follow the top of the board, so that a user would know which column they’d be dropping their piece in:

I just couldn’t seem to get rid of that little dark patch you see in the transparent piece, so I just had to live with it.

From there I proceeded to create a little animation that would show your piece falling into place:

And look at the shadow underneath the board! That was me, too! The shadow is a perfect rendition of the board in real time. it updates with each falling piece!

So while the entire scene is rendered in 3D we decided to let the user look around a bit. After the click the right mouse button, they can rotate the scene at will to look at it from all angles. Other teams did a similar thing, but they thought that 3D rotation would ruin their 2D selection boxes and break the user-selection for their game, so they had a 3D scene that couldn’t be rotated…essentially making it a 2D scene (in that case, why bother?).

I had an easy solution for that (no, not 3D picking): After the user let up on the right mouse the scene would ‘snap back’ into place. Any functions relating to the actual game were disabled during rotation as an extra precaution.

Here’s the scene from a few different angles:

Yay Clipping!

Finally, I built a little ‘win screen’. I should just call it a ‘CPU win screen’ because I haven’t seen a human beat Herbert since when he only made random valid moves.

I must take a second now to thank my team for helping put this whole thing together. They were motivated, dedicated, and had a high standard for quality: Andres (MiniMax optimization, board evaluation) Zac (GUI textures, help with timer), Mike (board evaluation functions) and TJ (original MiniMax w/ alpha beta implementation).

Finally, I want to thank all those “Hallway” testers I grabbed to help test the game–GUI and Herbert alike– family, friends, and roomates. I suck at Connect 4 personally, so having a few good players to test Herbert for weaknesses really helped.

Our professor gave out two automatic A’s for the assignment: the team with the best overall record in the tournament, and the team with the best GUI (and one team couldn’t win both). We won the ‘Best GUI’ award. Awesome.

Some notable things about the project:

  • There’s no 2-person play; it’s always Human versus CPU
  • You have the option after each game to choose whether the human or CPU will play first.
  • To play against other bots, a human ‘data enterer’ was needed to translate their bot’s move to the other person’s game so they would stay synchronized (i.e. no networking code was involved here)
  • The team that ended up winning the tournament I personally feel also had a superior GUI rendered in C#, and I must tip my hat to their expertise.
  • If I could make some more optimizations for the CPU to play against a Human, I would make a few changes: like making semi-random moves sometimes, accounting for the human to make some mistakes, so maybe be a little more aggressive; a difficulty meter that one could set to be as hard or easy as they wanted; and a few other things.
  • I would implement a few threading techniques so that the user can interact with the scene while Herbert is thinking
  • Herbert is programmed to think for just under 1 minute, as that was the time allotted for each move. He moves sooner the longer the game goes on (smaller search space, and definite wins/losses spotted).
Win Screen

The House always wins

That’s all I have to say about Herbert and the MiniMax implementation! If you have further questions or want the full .exe, just email me (my details can be found on the ‘About Me’ page).

Downloading and Playing Instructions

  1. Download the files from here (Link no longer available due to lack of interest–Rapidshare takes down items that haven’t been downloaded in 30 days)
  2. After you unzip the folder there should be another folder inside named “RunMe!”. Inside this folder is a file named  “Connect 4 GUI.exe”, this is the main application. Double click it to run
  3. Herbert takes about 45 seconds to think per move (a long time against a human, but he was designed to play against other Connect 4 bots). He is also single-threaded, which means that while he is thinking, you’ll be unable to do anything else in the application (i.e. it will “freeze up”) until he makes his move.
  4. Herbert has been beaten a few times since I posted the article. Sometimes he makes some strange inexplicable moves that cause him to lose. As far as I understand, there’s some Connect 4 game out there where you can win tokens that he’s been used on. I’m guessing he’s pretty successful in general, but I’ve been told he’s been beaten. I also have personally beaten him, so please don’t assume he’s actually a perfect player because he’s not. That said, he’s REALLY, really good!
  5. If you’d like the source code, email me via the address on my ‘About Me’ page
Advertisements

Tags: , ,

58 Responses to “Think You’re Good At Connect 4?”

  1. Dave Says:

    Is this magical Herbet possible to download?

    Regards

  2. Michael Says:

    I wanna play him too!

  3. other random guy Says:

    I would also love to play herbert! Super cool.

  4. gieseanw Says:

    Hi Michael and other random guy,
    I’ve sent you both e-mails. Please respond so I can send you Herbert.

  5. Bryan Says:

    I want to play herbert too, see what he’s got!

  6. 3rd random guy who WANTS THIS Says:

    hey can I get it too I love this game- why dont you upload it to mediafire or something?

  7. Kyle Says:

    Hello,

    I’d love to test this and maybe even see your source code to get an example for my own implementation. Please get back with me 🙂

    • gieseanw Says:

      Hi Kyle,
      I’d love to give you the executable files, but before I hand out the source, I am going to attempt to get in touch with my other team members to see if they are okay with it (Since they co-wrote this, I figure they should have a say in the matter)

  8. Pascal Says:

    I’d like to play this bot as well.

  9. jimmer Says:

    I would be delighted to test my skills on your super cool bot!

  10. joshua Says:

    Hey, this is a fairly recent post, so i thought you might be interested to know that connect 4 was solved mathematically some time ago. By this, i mean that it was proved that the first player can force a win every time. (i don’t believe the solution used minimax, since that would be pretty simple. but i could be wrong)
    some reference here: http://en.wikipedia.org/wiki/Connect_Four#Mathematical_solution
    I’ve been messing around with TitOT bot.

    • gieseanw Says:

      Hey Joshua,
      You’re right, it has been solved mathematically. The gist of my bot is that it implements a MiniMax search with Alpha-Beta cutoffs, which was what the group project assignment was for our class. Realistically, one could’ve just downloaded the pre-generated file containing all possible boards, and used that like TitOT does (and it took ~2000 hours to generate that in ’05). Maybe one day I’ll replace the bot’s AI with a solved version that is impossible to beat if it goes first.

      Generally speaking though, the game is “solved” like chess is “solved”: There’s only a finite number of boards, and if you could generate all of them, you can guarantee wins after just the first move(s). Chess, however, has many orders of magnitude more boards than Connect 4, which is why it isn’t solved yet.

      Thanks for pointing that out!
      -Andy

  11. Robert Says:

    I would like to play against herbert 🙂

  12. Oliver Says:

    Can you please send it to me too.

  13. Morgan Requiem Says:

    Hello, I don’t know if you still check this anytime..
    But I’d like to have Herbert. I’m Determined to beat him!
    If you’re still handing him out.. I’d very much appreciate the opportunity to give him a go!

    • gieseanw Says:

      Hi Morgan,
      I’ve sent Herbert to you! Enjoy! I *do* still check this, and I really need to get a new post up… Graduate school presents so many interesting topics and programs!
      -Andy

  14. Akshay Hulasare Says:

    Hi could you please send Herbert to me? I’d love to improve against him. hulasare@gmail.com

    • gieseanw Says:

      Hi Ashkay,
      I’ve sent Herbert your way. With all the requests to play him, it may be time I made the application multi-threaded, assuming I can still compile it.

  15. Stephen Says:

    May I also have herbert sent to me?

  16. harry Says:

    Hi,

    Please can I have a copy of Herbert.

  17. I Win Says:

    Hi, just thought I would let you know I beat your bot on my first try… oh and the computer played first 🙂 . Cool little app though, it put up a good fight!

  18. HerbertIsWeak Says:

    Just letting you know that I too beat Herbert on the first go and he went first… The reason I think, is not due to the source code but rather his name. If you had named him something tough like ‘Arnold’ then I would’ve definitely lost! Good work though 🙂

  19. jades Says:

    Can you send yours to me? I created a minimax program as well and wonder how ours would do against each other.

  20. Nicholas Romjue Says:

    I would like the bot for mac if possible

    • gieseanw Says:

      Hi Nicholas. When I created the game, I was only developing with Windows in mind. I don’t know where to start for a Mac, really, but I don’t think it would be hard as the code is pretty pure OpenGL. I plan on hosting all my code on GitHub, so perhaps you could try?

  21. Nick Says:

    Hey could i get a copy and the source code? Thanks

  22. sykikal Says:

    I’d like to play against the bot. Could you send it to me or re-upload it please?

    • gieseanw Says:

      Hi sykikal,
      Thanks for your interest. Give me a day or two, and I’ll get you a runnable version 🙂

      Bear in mind the executable will be a Windows-only one. I can also provide you with the source code.

      -Andy

      • sykikal Says:

        I’m using Windows so it being a Windows exclusive isn’t a problem. That’d be great if you could send me the source code as well. Thank you for your help Andy.

      • sykikal Says:

        Andy? What happened? Are you still around? I’m still interested in the bot. Maybe you didn’t contact me because you didn’t know how to. My email is sr ( at ) vgi.me .

  23. happyraccoon Says:

    Hi is is possible for me to have the source code? I was trying to figure out a good way to do an evaluation of a given board state.

    • gieseanw Says:

      Hi happyraccoon, I’ve sent it to you. I wrote the code as an undergrad in 2010, so I don’t exactly remember the board evaluation function, and I don’t make any promises that the code will be very legible to you 🙂

  24. Pallav Agarwal Says:

    Can I have the game too? If possible, I would also like to get the source code. (Would save me the trouble of sitting playing on two AI’s if I can directly hook it up to mine :D). I want to see how well my AI can perform against someone else’s.

  25. Ahmed Essam Says:

    Hi … can you send me a link of the game please 😀
    I’m coding connect 4 in my spare time and I really hope that soon my project would beat yours 😛 xP

  26. Gamer Says:

    Hi, may i have the source code? Thanks

  27. Charles Says:

    COULD YOU SEND IT TO ME PLX

  28. Charles Says:

    CharlesDoremieux@hotmail.com^

  29. Edward Marno Says:

    Would love to play him! Please could you send me a copy? Thanks! 🙂

  30. Neal Says:

    I would love to try your program out if you still have it available. Thanks!

  31. Jordan Says:

    Hi, could you also send me the game? Thanks

  32. sella Says:

    hi, can i have the source code please? thank you x

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: