Hawaiian War Games

Artificial intelligence. Sounds cool doesn’t it? I certainly thought so when I was trying to decide on classes to take last fall. I saw the AI class listed in the course catalog and said to myself: “Greg, you have to take that class! Girls love a guy that doesn’t have to make friends because he can program them”. And so I decided to take it. I was somewhat disappointed at first because upon first inspection of the syllabus, the class didn’t seem to have anything to do with programming new friends. I guess I will be alone forever :'(. That was a joke by the way… I don’t want anyone getting the wrong idea that I am some kind of sad sack. Anyways, back to AI. So I was looking at the syllabus and realized that most of the class was spent analyzing different algorithms that can win games like chess, checkers, go, etc. If you have ever looked into AI, then you probably know I am talking about algorithms like minimax, alpha beta pruning, and even machine learning stuff like neural networks.

It is all very fascinating to read about. Computers have consistently beaten world champions in checkers, chess, go, and a wealth of other simple card and board games. What is even more interesting is that almost all of the algorithms that have beaten human world champions are based on the same concept. We programmers usually avoid this concept and therefore have a pretty disgusting word for it. I’m talking about brute forcing. That’s right, the world champions in some of the most famous and widely played games in the world have all been conquered by what is essentially lazy programming. For you non-programmers out there, brute forcing is when you write an algorithm that tries every single combination in order to determine the best next move. This is pretty easy to visualize in tic tac toe because it is a relatively simple game. In tic tac toe, the first player has 9 different move options. The second player then has 8 different move options for each of the 9 moves that the first player could have made. That means there are 9*8 = 72 different board configurations that the first player can encounter when making his third move. The player making the third move can then make 7 different moves off of that bringing our board configurations up to 7 * 72 = 504. There can be up to 9 moves in a game of tic tac toe though so you can see the number of board configurations spiral out of control until the number is in the hundred thousands. The branching of these moves off of one another is kinda shaped like an upside down tree where the top of the tree is an empty board and the leaves of the tree are the winning board configurations.

Simplified game state tree for tic tac toe

Now, brute forcing would not be super difficult in the case of tic tac toe because hundreds of thousands is still a pretty small number of options for a computer to evaluate. It does, however, get difficult for a game like chess. The number of possible game states in chess is not even known. The most common estimate is called the Shannon Number. The Shannon number is about 10^120 and is not even an estimate as much as a lower bound. This means that the number of possible board configurations in chess is AT LEAST 10^120. For reference, this is more than the number of atoms in the universe. Therefore, it is impossible for a computer to compute every possible board state and evaluate which path is the best in order to choose the best move. One way to get around the limitations of computers is to write an algorithm that checks all moves up to a certain depth in the game tree, evaluates each of the game states at that certain depth for the utility (or how good each state is for the player whose turn it is), and then makes the move that has the most utility. The function that evaluates the game states is called the heuristic function. The accuracy of the heuristic function is pretty much what determines how good the algorithm is at playing the game. The best heuristic functions (you know, the ones that beat the grandmasters) take years to develop.

So why did I just spend the last minute rambling on about upside down trees, utility, and heuristics? Well as I was looking at the syllabus that first day of class, I noticed that in lieu of a final exam, we would be writing our own AI to compete in a class wide double elimination tournament. The name of the game was Konane, an ancient board game originating in Hawaii. Konane is played with two players and two different types of game pieces filling a board in a checkerboard pattern. In the first couple of moves, the two players remove pieces. The rest of the game is spent using your pieces to jump over the enemy pieces and ‘capture’ them. The first player who can’t make a move loses. Konane was an interesting choice because it can be played on any size board. The number of pieces and possible moves is proportional to the size of the board, my professor had us use an 18×18 game board to make sure we couldn’t brute force the entire game.

My team and I wrote our AI using the tree search and heuristic functions I described above. We also included alpha beta pruning (which I won’t describe because it is way too complex for this) to double our possible depth. We spread the processing out on all the cores of our system (something that is really easy to do in a recursive algorithm) to maximize our processing power. The final algorithm made our CPU fan scream, but it was totally worth it because in the end we clinched the victory. Looking back on it, I think we only won because I spent way too much time trying to figure out the best heuristic functions further proving how important these are. We really couldn’t agree on a heuristic function to use. I mean, there are so many that seem like they would be good. Number of possible moves is a good indicator of health because the less moves you can make, the closer you are to losing. Piece count is also a good one–the more pieces you have is roughly similar to the number of moves you can make. In the end, we found some good linear combinations of these heuristics and their inverses through seemingly endless trial and error. We ended up using one of those and it got us the victory.

So that’s the story of how my group became the kings of our AI class. We didn’t have to invent anything new or discover some sort of algorithm to win. We just used concepts that were discovered by some of the most brilliant minds of the computing era and have been tried and tested since their discovery. And that’s really the lesson I want you to take away from this. Oftentimes, when encountered with a problem. Someone has already had that problem, solved it, and put it on the internet for all to see (the Internet really is beautiful, isn’t it). Modern programmers absolutely do not have to be genius mathematicians, they just have to be good at interpreting other people’s work so they can implement it themselves. It may seem daunting at first to read a fancy published paper written by some genius PHD somewhere, but don’t let that keep you from reading it and trying it yourself if it interests you. Practice makes perfect! The reason papers are written is so other people can duplicate the work that was done in it and possibly expand on the findings. Who knows, maybe the next time you try to implement someone else’s research yourself, you will discover an expansion that is just as revolutionary.

Because I talked about some of my own work in this post, I have included the code below (It’s in python). There are several different modes you can set it to run in. Currently, it is set to pull up a GUI so you can play against the AI. It is very rough though as it was for a class so take it with a grain of salt.

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 )

Connecting to %s

%d bloggers like this: