In college I took an AI class. For the most part I was pretty disappointed in it. I wanted to learn about techniques to make computers learn (Neural Networks and Evolutionary Computation and so forth) but intro to AI is mostly just A* and Alpha Beta search. Given, those are clever algorithms, but at their core they're just brute force, so I didn't find it all that interesting.
However, our final project in the class was to develop a program to play Connect 4. The class broke into teams of 4-6 people. Then we had a big tournament between all the teams to see who's connect 4 program would win. Our professor gave us a heuristic to start us off which she told us wasn't very good. We were supposed to develop our own heuristic and then any kind of UI (or not) that we wanted.
Heuristics are pretty boring. Basically you just spend a lot of time trying to figure out how to decide, given a certain board state, if the board is good or bad. So you do all the work of figuring out the game, code it into a heuristic, and the computer just brute forces its way through all possible game moves trusting that your heuristic is smart enough to tell what is good and bad.
My team didn't really want to work on the Heuristic. Instead the majority of them went off and created a pretty sweet OpenGL UI where the Connect 4 board would spin around and the pieces would fly off the stack and into the board...
We just used the Heuristic our professor had given us, but a friend and I optimized the crap (memory usage) out of our Alpha Beta search, board state representation, and heuristic evaluation. Because our alpha beta routine was so much faster than the other teams' we were able to search about 2 levels deeper into the game tree.
We tied for first place.
Even though our Heuristic wasn't supposed to be very good, the fact that our search algorithm was so much more efficient meant we looked further ahead than everyone else and that was all it took.
At the time, we also had access to a room full of computers. We considered creating a client/server program to use all those computers to evaluate the game tree in parallel but after we did the math we realized that adding 12 more computers would only get us one level further down the tree because the number of nodes in each level of the tree doubles. We didn't think one more level was worth the effort, so we didn't bother.
yeah we did! :-)
ReplyDeletestill ... it would have been pretty sweet had we linked the whole computer lab together to evaluate the boards (not that we could have gotten anything but A's in that class, but I figure that would have been enough :) )