Out for the next few days – I’ll be getting fat off the many flavors of mooncakes. Some random weekend reading links follow:

There’s something hypnotizing about the patterns that emerge when playing a long game of go. It is unfortunately much more difficult to program AI for go than it is to create simple “AI” for chess (due to board size, the number of moves available at each ply iteration, growing rather than decreasing complexity…) As such if you want to play a reasonable game you must search for live opponents (usually found at local parks; they are filled with old people with little to do). 

There have been numerous attempts at programming effective go-AI. This paper, “A Machine-Learning Approach to Computer Go”, describes how an evolutionary program can learn over time. In particular, the authors make use of a technique called ‘alpha-beta pruning’ to limit the amount of board space the program must evaluate on any given play:

… the best position that the player to move can force (based on the parts of the game tree that have already been expanded). These statistics are tracked for both players, not just the player currently deciding. As new positions are examined, they are compared to these known lower bounds. If it is determined that the player to move can force an outcome that is worse for his opponent than his opponent could have forced elsewhere (in the previously examined tree), it can be concluded that his opponent would never choose to move to the current position, and this position and all subordinate positions can be instantly discarded.

This is significant for two reasons: 1) it means I might get my AI go sometime in the next decade, 2) some AI-game programming techniques revolve around the assumption that the opponent makes an optimal move. What if the human opponent intentionally makes a sub-optimal move, to trick the algorithm? 

Will prove useful if this ever happens.