If ya can't find the fossils, rig a computer program to "prove" your theory.You will eventually have to explain how a rigged program can design new and useful things that have not been foreseen by humans. It has already happened. A computer program using the technique described in this article has already designed a new, useful and patented electronic circuit.
This ain't a game anymore. And this is just the first few baby steps.
Carl Sims' Virtual Creatures Paper, Siggraph '94 is an earlier computer validation of the theory of evolution.
Programming a robot (or simulation of a robot) to walk in a real physical environment is hard problem. It's difficult enough to compute the set of parameters used to program the joints of a flexible creature with the right pressures and angles to get a creature to stand up and balance itself, let alone figure out the complex interactions required to define it's gait used run, jump, fly, swim, climb, etc.
Using genetic algorithms, however, Carl Sims was able to completely avoid all that complicated design work, and achieve results far better and faster than if he had set out to directly design the motor characteristics of the creatures himself.
Evolution is not simply random changes as creationists tend to think. It also requires a mechanism for selecting good random mutations over bad ones (the environment), and a memory to store a history of good changes (DNA).
Watch the videos on this website. All of the creatures in the paper not only "evolved" from a "single celled" organism, but they also "learned" to walk on their own, using a computer program that puts models of physical creatures' motor characteristics based on a simplified DNA in a real world physical environment.
http://www.genarts.com/karl/evolved-virtual-creatures.html His famous video is at:
http://alife.ccp14.ac.uk/ftp-mirror/alife/zooland/pub/research/ci/Alife/karl-sims/creatures-demo.mpg