For my AI class I had to write a “Dots and Boxes” AI. The assignment only required handling input and being able to play the game. However I wanted to do something extra and incorporate graphics. Therefore I had written a GDI based UI which helped me learn more about the low level windows API and windows message handling. The board representation was originally rendered with OpenGL as I had some ambitious ideas of doing 3d graphics, but was not able to do much more than drawing 2d boxes in the 3 days that I had allotted time for the entire project. I later ported the project to hand-held PDAs (Windows Mobile) where I removed the OpenGL dependency and fully rendered the UI and board through WinGDI.
QuatroAI makes use of the alpha-beta algorithm to find the least-worst move, the algorithm tries to optimize and order branches by priority. The priority is assigned based on the length of the chain a move forms and the amount of new captured boxes. At the time of writing an interesting challenge was being able to represent the state of the game where state could be stored and rolled back while the decision tree was being traversed. The implemented alpha-beta algorithm uses a depth first search approach and heavily relies on good prioritization of the tree branches.
Source is also included in the download.