This is the reason it's difficult to come up with fun AI for head-to-head fighting games: once you get past the thin veneer of mastering the moves, they're entirely about mindgames. A FSM-based CPU opponent does not have a thought process a human player can predict and exploit, nor the ability to avoid repeated mistakes.

I believe this applies to many other types of games as well, but games with many split-second paper-scissors-rock decisions suffer the most. A computer can be programmed to scout out and react to a carrier buildup in Starcraft, but cannot easily be programmed to outguess a jab/throw mixup in Street Fighter.