Multi-agent game suggestions
Hello Mithrandir, I suggest an evolutionary game as a good premise for your goal.
My idea goes like this: It would be a highly competitive multiplayer game about evolution. Think of something like the spore cell phase, but like this:
There are 8 or 16 players on a map relative to their creature sizes (let's imagine the creatures are tiny 2D, top-down, swimming creatures).
Everybody starts off with the same creature and is allowed to add one increment, so one new mutation. This could be an extra fin to swim faster, or some sort of spike to increase attack, or a shell to increase stamina, an extra eye for better (further) vision, a sensor for a better map of the surrounding etc. etc. Then, all players are placed on the above mentioned map where the food they need to survive is limited, so they fight to the death for survival (or be smart and avoid fights as long as possible, or be fast and eat everything first so everyone else starves etc.)
As soon as only two players remain, every other player is randomly (50-50) given a copy of one of the creatures of these two players and is then allowed to add another mutation to it. Then the next round starts on a new map and the game goes on like this for several rounds.
You could also have some power ups on the map, increasing one of the skills temporarily.
Eating stuff should fill and, when full, even increase a life bar. The life bar should slowly and constantly be depleted, so the creature has a limited life span even when there is no fighting going on - enabling death through starvation. The size of the life bar is persistent over multiple rounds and is given to the players assigned the creature at the start of next round. Eating should temporarily cause the creature to slow down a bit.
The map could increase, the creatures could become land creatures at one stage, etc (remember that old game Evolution?). They don't even need to look realistic, you could have some abstract, geometrical creatures, although I really appreciated the style in Spore.
Another upgrade would be different teeth, that allow eating different kinds of foods. For this, occasionally add new types of food to the map and make them persistent over multiple rounds, so players can adapt. (red moving food, green stationary food, white food hidden in specific places on the map, etc ). Also, permanently remove a type of food from future rounds if every single piece of it has been eaten in a previous round.
Now you're wondering where your agents come into play - this is fairly easy - at least on paper. If you have the mechanics for evolution in place, you can have a player fight enemies that adapt to his play through evolution, by trying different things out. This could be a "survival" mode, where the single player is fighting one AI enemy after the other, the enemies changing and adapting as the rounds continue, getting better and better, until the player is defeated.
I can't quite remember the article right now, but there was one that I read about approaches to interactive narrative. They suggested that to allow the player to have a real effect but avoid black and white situations you'd have x parties that have conflicting goals and the player has to resolve it as best they can. Each agent would have multiple pathways to success (or failure) with various preconditions. The actions available may be different for each agent, for example a lawless agent may have the options of kill, steal, kidnap, etc while a lawful agent may have fight, pay ransom, etc. The agents could run some sort of planner, and the player's actions would affect which options were available to the agents and the weights on those options.
@Jeffery
That may have actually been my article 
I'm currently actively doing research on artifically limited decision spaces and constant time planning for interactive narrative in multiagent simulations. (I have been for about the past 10 months). Note that when I say artificially limited decision space, I mean during runtime. During runtime I only present the agents with decisions that are crucial to their survival, directly assist in reaching their own plot points, or are only highly prevalent to their subdemographic (Eg: Miners vs Knights).
Story telling in games:
Architecture:
During the prebake phase, I do a fair bit of HTNs in order to break down plot points. After that, I do discrete time series feature prediction via DRNNs. I take the outputted markov random field and attempt to construct a behavior tree from it.
During runtime when the agent wants to go to the next stage of its plot, it only uses the behavior tree rather than having to do planning. The catch is that this behavior tree isn't a "if A then B." It looks at the agent's time series up to that point (At every previous major state transition it has encountered. Eg: Going from a Peasent to a Miner), and it helps the agent determine its next state transition over a markov random field. Its extremely easy to acount for the player's actions as its just another transition state. Originally, when agents conflicted I left the fate of the system to the player. But I moved that to being managed by a PD-WoLF implementation. The player can still have large effects on the conflict resolution, but not as large as they did originally. Also PD-WoLF is a lot more entropy resistant than leaving things up to the player, so it assists in keeping the system deterministic.
In practice this works extremely well, and I can generate near 12 hours of story in only 20 seconds on a GTX 760 2GB. Actual story planning is near 100% independent from the number of agents that are present within the game; however, it is dependent on the number of clusters. Thats usually about 200 or so in a larger game (400K NPCs). Agent collaboration is a HUGE overhead though. Even though i've done months and months of work to reduce thread interdependence, it still is the biggest bottle neck on the system.
@LouisCastricato
I don't think so... unless your example had a wizard, elves, villagers and bandits. But your project looks cool. :) We're working on a survival horror roguelike ourselves, although a totally different theme and gameplay style to yours. How's yours going?
Backing up to what you were actually talking about, can I assume that all your extra steps are to support a large number of agents by pre-baking/streamlining the decision making process?
Yup. The majority of my prebake process is taking a procedurally generated decision pool of about 7.3mil or so decisions, and doing reduction after reduction to bring it down to sub 100K. Without prebaking, it takes my computer a solid 5 minutes to iterate over a few million agents. With the prebake, since most of the agents are clustered (semi-supervised), it usually only takes 10 seconds or so for a group of that size. This is mostly because we're only leaving the clusters with higher level decisions available to them, and rather than using T2 FLCs during runtime, we're baking all of that into a nice markov random field. The quality difference isnt noticable what so ever from the perspective of a player. (At least the people who we've tested it on).
It isn't perfect, there is still a ton of more work to do. The environment needs to remain markovian throughout the entire simulation (Of course this is a requirement by most multiagent reinforcement learners though 
), the primary decision pool cannot change in any way (Although how they're infered can change easily), and due to the limitations of CUDA, fuzzy decision trees can only branch so many times before we hit DR. All of this will be fixed eventually though.
Onto the Unpersons for a second. Thats primarily a demonstration of the software. It was a studio we purchased last December due to a fairly nice track record of cool rogue like games (Unpersons is the first English game they've made, otherwise I'd link the others. I can't find them since my Spanish isn't as good as I hoped.). A major component of the software is the ability to read through annotated text and extract starting states for time series functions. So we have the player write biographies for all of the main characters, and then do our prebake phase during runtime. Since the game doesn't actually have many agents (50 or so), we can do the prebake phase in only a few seconds. So its more of you can play through a rogue like that you've written the story for than anything else. Really cool in concept, and in practice (While it is a bit limited as we didn't want the player to annotated everything) is quite awesome. We use some auto annotation methods after asking the player a few methods. It isn't just a set of combo and check boxes. Its an actual text editor which I absolutely love The main characters also generate their own journals during runtime through some pretty cool NLG algorithms we have a linguist working with.
It sounds very interesting, however I suspect you're coming from a perspective of having been immersed in it for some time. ;) For someone with a basic AI background (bits of behaviour trees, planners, neural nets, etc), what's the general goal and approach of your technology?
I'm going to tell you what my professor told me when I started becoming interested in multiagent AI (About 2 years ago or so), since I still think its the best advice I've ever been given on a subject: Try to make the sims. Or atleast your version of it. It doesn't need to be amazing, it doesn't need to well written, hell it probably doesn't even need to be optimized. But try to implement a small sims like game based off of the knowledge of AI you have now. Just tinker until you're satisfied with it (Eg: Until you think that they're good enough to survive on their own for a while). Don't use code from any external sources. Only write it from your own knowledge.
Then, once you're done with that, rewrite all of it in a type of state machine or controller you've never worked with. Only read the papers that are crucial to optimizing and improving your sims game. You wrote your sims game as a FSM? Rewrite everything as a continuous fuzzy logic controller. Didn't use planning? Be sure to include HTNs.
After that, start looking into optimizing it and THEN look at how other people have implemented their version of the sims. Compare your results with theirs. See what you could have done better.
When I was first learning this stuff, that took me about 4 months in total. But I learned a TON about AI. It was awful at times. The subjects were overwhelming, and I never really knew if I had implemented things correctly. But the ability to tinker with AI subjects from the ground up rather than just learning them from a tutorial series or book felt amazing. I strongly recommend not buying any introduction to AI books, or watching any tutorial series unless you absolutely need it (Eg: For a class, or if you're entirely lost). I always felt like they hurt more than helped.
If you meant specifically about interactive media, I strongly recommend getting a good foundation in statistics, reinforcement learning, altnerative planners, and computational narratology (http://narrative.csail.mit.edu/cmn12/proceedings.pdf)
Edit: I misunderstood entirely. I thought you said you wanted to know how to learn it haha. The overall goal of my research (It doesn't matter how long it takes. I have multiple universities lined up to help if need be) is to be able to read through a book, extract all of its raw story, simulate said book, and then be able to generalize it. So I want to take half of book A, and seemlessly combine it with half of book B. I have a university in Austria that is willing to help (Provide researchers & equipment) next Spring on generalizing simulated plot lines, so this is something that is actively pushing torwards reality. For reference, if their research is successful, it will be made open source. (Just that section. Not the entirity of the software)
