The first battle is easy. Any kombatant will work as long as you avoid the computer's punches and avoid using a crouching low kick. Your offense should consist of waiting for the computer to approach you and uppercutting him or her when they are close enough. Alternatively, you can keep sweeping him or her, or utilize flipping kicks and projectiles.
Johnny Cage works well against male kombatants since you can use his Nut Cracker followed by an uppercut. Kung Lao, however, bends down too low after receiving the Nut Cracker, so quickly follow it up with another attack of your choice like a sweep. Using the Nut Cracker proceeded with his Split Kick, which is done by executing a low kick in close, and a late Shadow Kick also works well. The Nut Cracker-Split Kick-Shadow Kick combo takes good timing to be executed, however. If used correctly, Cage can amass several victories.
Second and Further Battles
At the second battle and onward, the computer gains the ability to cheat, and will cheat more often if you begin winning rounds. While cheating the computer will become invincible when executing certain attacks (mostly throws and uppercuts), and will execute special moves on command instead of needing to execute a motion input (such as pressing Down + Back while walking forward).
In general, computer opponents will usually walk straight for you, and throw you once he or she gets near you. Also, avoid getting trapped in the corner! If you've chosen Cage, you can easily goad the computer into the Nut Cracker or a Shadow Uppercut once he or she is close enough. Cage's Shadow Uppercut is your best weapon if you're facing Kitana.
If you're Kitana, you can use her Fan Lift on nearby opponents. Like the Baraka strategy, you're going to back away, but let your opponent get a little closer instead yet not too close. If your foe is too close, you'll get thrown; if he or she is too far, he or she could throw a projectile at you or sweep you.
With anyone else, your best bet is to try to goad the computer into flipping towards you. You can do this by backing away and doing a back flip. Once the computer is airborne, you can counter him or her with an uppercut, roundhouse or high kick. Sometimes, the computer likes to perform a special move at the start of battle, so be wary and prepare a countermove; A flip kick is good for countering projectiles.
Kitana will catch you with her Fan Lift if you flip towards her. Remember Cage's Shadow Uppercut, Baraka's Chop Chop Blades, or Kitana's Fan Lift if you're one of the said kombatants!
Mileena, on the other hand, will do mid-air Sai Blasts. Any kombatant will work if you can get mid distance, flip, and do a late kick before you land. If executed correctly, you'll end up flipping over her Sai Blasts, and kicking her out of the air.
Fighting Kung Lao
Avoid Kintaro's Teleport Stomp at all costs! The best way to defeat him is by keeping mid-screen and doing flip kicks. Kintaro should try to attack too soon and miss and end up being the recipient of your flip kick instead. Being Scorpion is an advantage since you can counter his missed Teleport Stomp or his taunting with the Spear followed by an uppercut.
The cheapest way to defeat Shao Kahn is by spamming the Teleport Drop if you're Mileena. Also, you can use the Chop Chop Blades if you're Baraka. Additionally, Kung Lao's Whirlwind Spin can easily override Kahn's Shadow Charge. Just spam Lao's Whirlwind Spin and hope Kahn doesn't throw his Light Spear.
Kahn can also be beaten with anyone else, but you may take heavy damage by his Shadow Charge. As the battle commences, flip towards Kahn, and quickly crouch. He might attack and miss, and it'll open him up for an uppercut. Flip towards him and duck again hoping he misses or taunts, and uppercut him. Additionally, you can add the Slide if you're either Reptile or Sub-Zero after an uppercut. Once Kahn is close to the corner, you can add a sweep after the uppercut for a bit more damage then repeat the said flip-and-uppercut method. If you have him totally cornered, then you can keep countering his missed attacks with uppercuts. Keep this up and Shao Kahn will be defeated.