Reminds me of the AI competition on infinite mario, recently:
Here is a video of the winning bot (A* based approach), cool to watch, as they display its trajectory calculations.
http://www.youtube.com/watch?v=DlkMs4ZHHr8
GA is cool and everything, but I am sometimes sceptical about its merits. Yes, it gives you a natural problem representation, but would it really have done a better job in this particular domain than using a technique like simulated annealing to move through the Mario AI parameter space?
We just don't know without seeing benchmark comparisons. Maybe its much worse. So, its a cool application, but we should be cautious about how quickly we decide GA was a particularly suitable search algorithm.
I have always thought that GA have won lot of acceptance for its name. Don't get me wrong, they are great to solve some problems, and even though they don't assure us to converge into a global minimum on our space, they are more robust than other methods to search in the whole space.
We can see a relation with the humans, I am pretty sure that we are not a global minimum in evolutionary terms, but... certainly we are at least close to be a local minimum.
I think simulated annealing would fall short if the levels have a lot of dead ends. A good reason to use GA is precisely to avoid the problem of getting stuck in local minima/maxima.
Simulated annealing is also intended to avoid getting stuck in local maxima.
It sounds like you are mixing it up with some sort of greedy search.
Also, it sounds as if you think they are optimising Mario's position in the level (when you talk about the level having dead ends). I haven't checked, but I several doubt thats the case. I would bet they are optimising a control scheme for mario, and that local maxima in the search space are locally good sets of control parameters, rather than anything to do with the topology of the level.
Normally evolutionary computation papers which describe experimental/applied stuff like this will describe what they actually did more precisely, give actual benchmarks, and if possible try alternative approaches (as you suggested).
GA is cool and everything, but I am sometimes sceptical about its merits. Yes, it gives you a natural problem representation, but would it really have done a better job in this particular domain than using a technique like simulated annealing to move through the Mario AI parameter space?
We just don't know without seeing benchmark comparisons. Maybe its much worse. So, its a cool application, but we should be cautious about how quickly we decide GA was a particularly suitable search algorithm.