Connect-N game player
The challenge was implementing an alpha-beta pruning minmax algorithm for a connect 4 AI. Our evaluation heuristic looked at the rows, columns, and diagonals of a board and created features based on the pieces. Empty spaces were absorbed into surrounding features, and features were defined by any game pieces that occupied that space. So, a line (which could be a row, column or diagonal) of X _ _ O O _ X would have 3 features, [X _ _ ], [ _ _ O O _], and [ _ X ]. Each of these features were evaluated on the following basis: 1. consecutive pieces (X, O, _) are exponentially more valuable than disjoint pieces. 2. player pieces (X, 0) are linearly more valuable than empty spaces (_). Features owned by the AI (O for example) contributed to the value at any given state, while opponent pieces (X) detracted from the board state score. Additionally, the oldest move which was part of a feature was recorded, so if future states of the board both have winning conditions, the feature that was completed first will be the winner. With an iteratively deepening minmax algorithm, states were generated as permutations of current AI legal moves and the most valuable state was returned.This code was originally implemented using a number of different threads, which seemed to have failed when run on the linux box which was supposed to test our AI's against our classmates. I did some major redesigns late the night before it was due, and got a lot of it working, but it seems a little lobotomized to me. It certainly doesn't exhibit all of the intelligence it used to. I'm hoping to get back to it at some point and make a more generic alpha-beta minmax for future use.
(source code to come. esnips is down at the moment)
