Now having followed the story most players would, I think, have opted to off him.

If you offer a choice here and don't offer the same choice at non-important events, the fact that you offered a choice would make it look suspicious and the player would think twice about whether or not to kill the character. In other words the player's choice will partially be based on the fact that the designer offered a choice in the first place, thus the choice option would break the immersion and the player won't be emotionally attached to the choice. If you want to elicit emotional response from the player, allow him to make the choice based on how he interacts with the game world, rather than simply making him choose A or B in a dialogue. Let's take the example with Ezio. You hunt the traitor down and once you have, you're offered to choose whether to spare his life or kill him. If you decide to not kill the traitor, why would you be hunting him down in the first place? It's not something you would be doing, if you had doubts about this traitor being a traitor. So, as a designer, what you should really do is make it so that successfully pursuing the traitor or not was the actual choice you as a player make. If the player has doubts - he might abandon pursuit, if he doesn't he can kill the NPC. However, this gameplay addition implies that failing a mission might be Ok, and thus leads us to a mission-less system of an open world - I'm not sure if it's possible to implement this kind of gameplay.

The other possible option would be making it so that completing a certain optional side mission would reveal the truth about the traitor and change the player's pursuit and eliminate mission into something else, like pursuit and interrogate.

Interactive stories like the famous gamebooks of the past. I loved those books but I never played them more than 2 times, anyway, and just to see a couple of differences in the story.

I think it's a waste of time, it's better to focus to a main important and good story, maybe a couple of branches, many side quests and nothing else.

A game's "story" is a "series of interesting choices." Where most games fail is the follow-up to the player's choices and how those affect the world around them. There should be consequences of equal gravity to either option in any player choice, and neither should be obviously preferable.

Civilization is an excellent example of this. The player can choose to conduct their foreign policy peacefully or more aggressively. Neither choice is a certain path to victory, and both offer significant challenges. In this way, the game reveals the player's character, or at the very least the character of the role the player takes. A great game would allow the player to experience the kind of character arc or change over time that a literary or film hero would.

Sadly, most game companies would rather spend another couple million $$$ on triangles. Things like characters and emotional connections with an audience are much too difficult it seems.

Interactive fiction or as I remember it from my youth "Choose your own Adventure" books often has a crossroad decision virtually at the start. One decision leads you deeper into an adventure and the other is an immediate end to that story. In a few of these books, that immediate ending usually read something like this: Your next six weeks were spent quietly and then you died to the alien invasion. In seeking to have a game that is interactive you open yourself up to the reality that the path you take is still at the mercy of the writers.

You cannot truly have a successful interactive adventure if the final outcome is immediately one event or another eg. Stopped the aliens or died to aliens. It needs to be a multiplicity of endings some of which are defeats, some are wins and importantly, some are compromises. Moreover the premise will never truly succeed if you imbue absolute opposites i.e. good and evil. Absolutes don't work well for the most part as it very difficult to produce reasonable "compromise" endings which is what I think you are looking for in a game. Either way you still exist at the mercy of the writers.

In writers terms I think this is called plot development.

The number of times that a game can let a player-created story branch off has to be limited. Which means that there will be some junctures in the story where the player can't branch the story. Like the Assassin's traitor, for example.

Nature exhibits the same approach. I remember watching a documentary on the ecosystem of the North West Coast of North America. In it they said that there were key species in the ecological chain that were critical to the proper functioning of the system. Other species could come and go, but the loss of particular species would destroy the whole environmental life chain itself. Plots and sub-plots could be built and resolved in similar fashion. The Witcher seems to be taking a pretty decent stab at the non-linear user-defined plot thing.

Well, personally I think interactive story games have a lot of untapped potential. I would really like to play a game that was like an interactive science fiction or fantasy romance novel. But I've also intensely enjoyed many completely linear movie-like games. Actually the thing I disagree most with is having only a few choices near the end. If the game doesn't branch relatively near the beginning I'm probably never going to play it again to see the other possibilities because it would be boring and frustrating to replay the first part.

Was thinking about the same today. Seems to me the focus could shift to the script & plot, I just finished trawling the free 3D game listing on MMOHut, and got to thinking that the plot lines for most were pretty stale. Might be different graphics, but the same old classes, same old grind. But then how many options are there ever going to be, eh? Still would be nice if there was more stories/plot lines like Fringe or Dark City or something. I know there's a ton of really good sci-fi that isn't just campagin and conquest.

Good comment on the balance of plot vs game play.