About countably infinite state space: with about 10^56 states, Pacman still remains a very challenging domain ! Just to put things into perspective, my colleague recently ran some experiment where he would exhaust 8Gb of RAM, but could reduce this number down to 4Gb using random projections for dimensionality reduction.

http://www.cs.mcgill.ca/~jpineau/files/whamilton-icml13.pdf

http://www.cs.mcgill.ca/~whamil3/files/cpsr-talk.pdf

Also, don't forget that this is a partially observable domain (with only local sensory information) with no apriori knowledge of the overall goal to achieve. It learns completely from scratch ! If we find this task easy as human beings, it's because we have a lot of prior knowledge that we can transfer into this task