There are a couple of most plausibly hard steps: the origin of life up to just before bacteria split from archaea, and the origin of eukaryotes, which happened just once after something like 2 billion years. But I had in mind something cheaper more like scaling up the idea of http://www.karlsims.com/evolved-virtual-creatures.html. Intelligence has evolved in animals as unrelated as octopi and us.