As I mentioned in my last post, I’ve been thinking of building a game playing program. This idea is similar to an AI project I worked on while finishing my degree at Cal Poly Pomona, but I never got the chance to finish it due to some health issues. It seems like it would be a fun challenge and could be eventually applied to a new discovery I’ve stumbled upon called Battlesnake. This looks like a lot of fun, so lets get ourselves some practice with game playing programs by starting on something a little less complicated.
1. Preparation
So, how do we want to go about designing this program? To start, there’s a couple things I know I am going to want with the design.
- We’re going to want to follow good OOP principles. If we do our initial design right then we can go back and constantly improve the performance of our components without worrying about having to rewrite the entire thing. I’m not a fan of rewriting except in the most dire of circumstances, so lets try and save us a ton of work later.
- We know we want to use multi-threading, so we’re going to want to pick a programming language that supports parallel processing. As is my usual I will be attempting this in Java, but for ultimate speed we might think about using C++ or even C with some Assembly involved.
- We want to place a limit on how long the program can “think” about a move. To start we will pick an arbitrary time of 4 seconds. This I’m willing to be a little more fluid on, and I’ve already decided that if 4 seconds is too much time or seems to be working too well then I’m ok with eventually making the time limit shorter.
As for the initial game choice to solve, in tribute to that AI project I never got to finish we will be writing a program that plays Four-In-A-Row (more commonly known by the trademarked name Connect Four). In the original assignment our programs were meant to play against another students attempt at the program, so we will have to find some Four-In-A-Row programs to test ourselves against. I will be using the Gnome version of this game for initial testing, then when I feel comfortable that my program is performing properly I can test it against any number of Four-In-A-Row solvers found online.
2. Where To Begin
Now that we have an idea of what we want to implement, lets figure out how we want to start. I’m a big believer in doing good research, so I put in a lot of time reading and studying before getting started designing the outline of our program. Just about every source I found on making a game solver pointed to this particular problem being within the realm of Combinatorial Game Theory, which means that we’ll need to build and analyze a game tree. This gives us the choice of using either a deterministic or randomized algorithmic approach. I will be proceeding with a deterministic approach to solving this game tree, although attempting a randomized approach could be interesting to do just to see which approach wins more games against the other.
Knowing we want to go with a deterministic algorithm, its a pretty easy decision to go with the Minimax algorithm. More specifically, we’re going to be looking into the Negamax variation of Minimax. This algorithm seems like it will save us a lot of time having to calculate separate board state values for the Max and Min players, since any point for Max is a point away from Min and vice versa. There’s an absolute ton of improvements and refinements we can eventually do to make our algorithm faster and more efficient, but for now we’re going to concentrate on getting a working Negamax algorithm going. I find it much easier to design a program piece by piece, and it seems like every time I try to get a little too ahead of myself I just end up with a more complicated problem to figure out.
This also means we need a heuristic so that our algorithm can determine what constitutes a favorable board state. For our initial approach I’m thinking that we assign some point value to one or more disks that have the potential of forming four disks in a row (for example, a single disk with three empty spaces to its left could be worth 1 point, while two disks in line with two empty spaces to its left could be worth 5 points). The points themselves don’t matter as long as it makes clear what board positions are more favorable for a win, so this will almost certainly be revisited and revised as we continue to work on and improve this program.
3. Let’s Go!
Alright, now we have a good idea on how we’re going to start this project. Now’s the time to get fingers on keyboards and get to work. Come back for part two where we get on our IDE of choice and start writing!
