From what Ive found out in my years of interest in AI - an awful lot of 'harder' AI is seaching through solution space (not just nice regular terrain style data, but irregularities of object analysis/manipulations and simulated behaviors).
Several difficulties :
With a complex environment to operate in, the number of interactions and possible interactions (and thus solutions) increases geometrically. Alot of data has to be sifted thru/evaluated to find that one thing you want to do. Along the same lines, the LOGIC (code) needed to handle the irrgularities of the environment grows geometrically also.
With a dynamic environment in a near realtime game (including the actions of other 'intelligent' objects) that changing environment must be RE-analyzed constantly (meaning you have to rerun much of the same analysis over and over frequently to be able to 'opportunisticly' interact.
One I found possibly of the highest difficulty is trying to come up with a unified measurement metric for the intelligent object to be able to decide between doing different possibilities (what is the priiority in that objects risk versus reward evaluations).
As usual having uncertainty (and being able to handle it) in the environment increases the difficulties at least a magnitude.