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:
From there I proceeded to create a little animation that would show your piece falling into place:
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:
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).
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
- 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)
- 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
- 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.
- 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!
- If you’d like the source code, email me via the address on my ‘About Me’ page