It turns out that Battle for Wesnoth is just what I've been waiting for, a free strategy game with nice polish and an active developer community. It is modeled after Warsong, a Sega Genesis game Matt Yglesias likes. It is written in C++, but they've got a Python API for writing new AI's, which happens to be the part I'm interested in anyhow. This "Chesslike.py" AI is apparently better than the default and weighs in at under 300 lines of pretty simple Python. Seems like a good way to take some of the mystery out of game AI programming.