Sep 22 2016
Board Games and Computer Science
I really enjoy playing board games. Not luck based games such as Monopoly or Risk, but games that require a well-executed strategy. My favorite board game is Maharaja. The idea is to move your architect along the cheapest routes to visit cities and to build palaces. The first player to build all seven palaces wins. Finding the cheapest route to a city depends on where you have already placed houses and on where you can build or move houses on your turn. This is a shortest path problem that must
consider all the different house configurations that can be created during the player’s turn, selecting and utilizing the cheapest one. Writing a competent AI for this game appeared a manageable task as it required a Graph data structure with Dijkstra’s shortest path algorithm. Maharaja became the first board game that I turned into a computer game, complete with networking for multiple human players. It was not uncommon for me to think that there was a bug in the game when I couldn’t figure out the path that the AI used and spent so little money on. After staring at the board awhile, I could always find the roundabout route that the AI found, which I might never have seen as a player. 
Continue Reading »