Tales of Souls

From Soul Calibur - Wiki on Neoseeker

Tales of Souls mode is the Story Mode for Soul Calibur III. You can take your character to different paths and in each path, you fight a different character. If you choose the right paths, you even get to fight the secret final boss, Night Terror! TOS mode allows you to use any playable character in the game with the exception of Abyss, Bonus Characters and Created Characters.

How to beat certain characters

Setsuka: I don't know why she's so hard for a "normal" character. She's pretty relentless. If you're using a fast character such as Talim or Taki, just block a lot and attack her after she fails to get her moves to hit you. For slower characters, such as Rock and Astaroth, just find an attack of their's that's not so slow and spam it on her whenever you get the chance.
Colossus: You can't stun this guy or anything. So find some quick combo to pull off on him. You can usually predict his attacks, since he shows you what he's going to do before he attacks you for most of his attacks. So just move out of the way, because most of his attacks are unblockable. When you beat him, move out of the way! You don't want him crushing you when he falls down.
Olcadan: This guy is a real pain! He blocks just about anything you throw at him. So, what do you do? Try to use is a guard impact whenever he tries a move on you. These can be hard to to do though and you have to time it right. When he's open for attack, pull of a powerful move or a long combo on him and aim for a ring out!
Abyss: Knowing that he's the final boss, he is going to be hard. All I can say is, use throw attacks on him as much as possible. They can be pretty effective on him. And of course, block when needed.
Night Terror: He's the secret final boss for the game. You can't ring him out. If you try it, he will simply fly back up, so that's not an option. Especially don't forget to block here. This guy has some pretty powerful moves in there and you don't want to get hit by them. When you get the chance, attack him with your character's fastest moves.