Sword of the stars has a stochastic tech tree. For each technology there is a list of predecessor technologies that may lead to that technology, and each race has different chance of each of these actually enabling the following tech.
PK: One big point that Eliezer is trying to make is that just "hacking away at code" without a much better understanding of intelligence is actually a terrible idea. You just aren't going to get very far. If, by some miracle, you do, the situation's even worse, as you most likely won't end up with a Friendly AI. And an UnFriendly AI could be very very bad news.
GenericThinker: A DSL might help, but you need to understand the domain extremely well to design a good DSL.
The state spaces of both chess and go have to be expanded to include "previous history". In the case of go, this is to avoid the ko problem -- moves that would produce the exact same board state as a previous state are forbidden. Chess, well, see a chess rule book, or wikipedia.