I made an approximate clone of Space Duel. Each player controls a little spaceship which orbits around the moon and can shoot bullets or lay mines. Trajectories follow the inverse square gravity from the moon and wrap around the sides of the screen. Collision with the moon or another player is instant death.

Anyway, I have had a lot of difficulty making a fun AI opponent. I want something that is very challenging, but which can be mastered with a little practice. I want an opponent that doesn't fall for cheap tricks but is beatable normally. The problem is that no matter what I try, I can't manage it.
I've figured out how to make a near unbeatable AI, but not how to make a fun one. Even when I try weakening it, it doesn't really work.

The main advantage of the AI is the ability to calculate exact trajectories into the future. I've intentionally simulated some uncertainty in the aiming calculations so the AI will sometimes shoot a close miss. However this isn't enough.


Anyway, here is a download link for the game so you can see the problem. (This is a precompiled Windows version. If you want to run it on other platforms, just pm me and I'll send you the source code)

Here's a video of the AI's dodging abilities at full strength. Obviously, the version in the actual game is weakened a bit.

Just a tip-of-the-brain suggestion: play the game a few times on your best AI. Every time you win or lose, write down three things:

• Whether or not the win/loss felt "fair"
• What the AI should have done that it didn't
• What the AI does do that feels annoying or overpowered
  
  Once you quantify what "feels too strong" about your AI, it's usually much more straightforward to come up with algorithmic ways to address those areas.

For the dodging, how about adding a lag in response to events, such as shooting? I admit to having no idea how AI works, but most of the time it is the reaction time that bothers human players.

Or maybe add a random integer value somewhere -- if the integer value is above X, the enemy dodges, if it's above Y, it will be a near dodge, above Z, it will be a hit that will feel like a lucky shot, and above N will be a total shell in the a$$. That is the way pen and paper RPG's settle for a "fair NPC battle".

There are dozens of places you can add randomness that can affect the feel of the AI. By adding fuzziness to reaction time (as stated above), aiming accuracy, decisions, etc. not only does the AI start to feel more "organic", but it can make it easier to defeat.

Looking at this from a design perspective, how is the AI implemented? You could look into Fuzzy Logic to provide an easier way to approximate actions, and make it easier to tweak. Mat Bucklands "Programming Game AI by Example" is basically my go-to book, and well worth a read. Mat actually goes over fuzzy logic in his book.

The easiest way you can make it fun though is to have the enemy hit and run. You could have him randomly decide to attack, then after attacking give the player an opportunity to strike back. The key to good AI is giving the playerr an opening that they can exploit.

Ever play Kingdom Hearts? Ever try beating their version of Sephiroth? He's what you'd call a big bruiser. He can do ludicrous amounts of damage, but his moves are fairly easy to predict, and after almost every single move he leaves a slight opening. Not a hugge opening, but just enough to where the skilled player can recognize it and then use that opportunity to attack. He is hand down my favorite boss in any game, but when you break down his actions, it is a relatively simple set of rules. Swipe at the player when they try to rush in, leap back to get some distance between the agent and the player before OMFG BIG EXPLODEY ATTACK, and charge->slash->leg it any other time.

Here's a brief summary of the current implementation

Dodging: For this part, the other player is completely ignored.
The ai projects the trajectories of everything into the future and essentially does a tree search of possible actions to minimize future damage. Obviously a full search has exponential complexity, so it uses the heuristic of using the same input for many consecutive frames, so that it only branches occasionally. It searches 123 frames into the future but it only branches 3 times. To make it easier, I also set it to completely ignore bullets and mines after 25 frames of depth. The rest of the search tree is only to avoid the moon.

Aiming: Calculate whether firing a bullet would cause it to hit if the other player does nothing. If so fire. A small error amount is added to the collision detection so that it sometimes has a close miss.


The main requirement of the dodging is that I want to make it so that the ai virtually never crashes into the moon. It looks really stupid and gives the player an instant unearned victory. This is why it searches far into the future for moon collisions even though it ignores bullets and mines after the first few frames.

A large portion of vehicular combat, be it on land, in the air, on the sea, wherever you don't have the full range of motion that you have on foot, is to avoid the damage in the first place and make sure that you don't put yourself in harms way. So maybe it might be more appropriate to write the AI so that it is not immediately reactionary to projectiles and it tries to predict the player more often than it does the projectile, and write moon avoidance as a steering behavior, negating the need for a tree for that aspect.

I'm not sure what you mean by a "steering behavior". The problem is that often times you'll be on a collision course with the moon and not be able to do anything about it. There's no immediate way to tell which trajectories are safe without actually calculating the trees.

I thought about making a precomputed lookup table for determining safe states, but the the problem is that the state space is 5 dimensional, so that's a ton of data, and it's not easy to calculate.

Steering behaviors are a pretty import part of AI my friend. You should look into them.

Add some noise to the AI's "observation" of the player's position/velocity and the position/velocity of his projectiles.

Perhaps reduce the magnitude of the noise for closer objects (since the AI can "see" them better/more accurately), or to increase difficulty.

Great video by the way!