A pseudo random or random AI is fine and nice, but it just depends on what extent of randomness. Let's say we are just thinking about movement. On the two extremes, we have movement along a fixed path and just random(pseudo-random) movement. Ironically, both of these are easy to beat.

For movement along a fixed path, it becomes predictable and things are easier to hit. For pure random motion, sometimes randomly shooting works just fine and there really is no aiming involved. Or in some cases, based on the situation, shooting in a straight line will kill a random moving opponent just because they really don't know any better.

However, there are situations where random (pseudo-random) motion becomes unbeatable, which in the case of a game, is really not something we want.

So, most of the time, the best approach is somewhere in the middle. A little randomness, along with deterministic behaviors. Then it becomes a challenge, and not impossible.