A Brute Force Approach
May 22nd, 2012
I’ve been struggling with problems with Actor AI, and came up with an interesting idea. I started with the observation that Actors must be able to pursue some sort of goals, and to do so they needed explicit desires. This wasn’t too difficult to handle: some combination of power, wealth, group affection, and a happy personal relationship. It might be possible to add other group factors, such as admiration or respect, but these really just boil down to power. Specifying these values for each Actor specifies the Actor’s basic goals.
But how does the Actor actually pursue those goals? I considered a great many possibilities before coming to the realization that computers are fast enough nowadays to permit a brute force approach. For each verb, I need only specify Roles, Role Activation Scripts, and Options. No inclination equations are necessary. Instead, the Actor considers every possible sequence of different Verbs. Yes, it’s a monstrously large tree search. So what? CPUs these days have cycles to burn. If one of the frontiers of computing is mining humongous amounts of data, why not pursue the analogous frontier of utilizing humongous numbers of cycles?
One interesting aspect of this idea is that each branch could be pursued independently by a separate processor. If the top of the tree has four branches, we assign one CPU to each branch, and then have that CPU search down its branch. We might be able to terminate the search on a simple time limit: after so many milliseconds, the CPU terminates its search and returns its best result.
The crucial data structure to make this work is what I’ll call the Change Accountant. The execution of each Verb-Role will entail changes to the overall storyworld database: its Historybook as well as characteristic values for Actors, Stages, and Props, and also relationship values among Actors. The trick here is to have an object that specifies two things: 1) the variable that was affected; 2) its previous value. The final value is stored into the overall Engine data set. When it comes time to decurse back up the tree, we simply run through all the objects in the Change Accountant for that step, restoring each altered variable to its previous value. The only problem I can see with this is how to point to the variable itself. In C, I’d just use a pointer or handle, but Java doesn’t permit such shenanigans; I know that this can be done, but my programming skills are too weak to provide me with an answer – which means that I’ll have to study Java some more. Humph.
I have no idea if this idea is practicable; the only way to find out how fast it will all be is just to build and run the damn thing. But there are a variety of things I could do to speed things up if necessary. In any event, this might be a crucial part of the overall solution.
Postscript May 25th
This idea won’t work as described. Suppose that Joe Actor is diving down through the branches of the tree. One of his long-term goals is to get rich. Joe runs into the “let’s make a deal” verb. He tries out every possible expression of that verb. One of those variations is “Joe offers to trade his chewing gum wrapper for Mary’s golden crown”. He will examine every possible result of that Event. One possible result is “Mary accepts the deal”. That nets Joe the golden crown. This is a great outcome, so Joe decides to pursue it. Except, when he comes to the deal verb, Mary will reject his offer. The tree-search yielded an incorrect answer.
The obvious solution is to provide inclination equations for every option, as per standard Storytron design. But if I’m going to write all those inclination equations, that makes the tree-search less valuable. Why bother with the tree search?
One possibility is to combine the two approaches, so that there are both inclination equations and tree searches; the inclination equations provide the short-term behavioral directions, and the tree search establishes the long-term strategy. This would be an extremely process-intensive approach, gobbling up cycles by the billion. On the one hand, I quail at the thought of the engine going away for ten seconds before returning with an answer. On the other hand, the notion of such intense process is rather appealing; it’s the most extreme version of my admonition to be process-intensive rather than data-intensive. If it worked, that would certainly produce something shattering.
Besides, I can always speed up the processing. I could skip the interpreter and hard-wire the processing directly in Java, although that would be a nightmare of coding. I’d need some help for this, but each of the top-level branches could become an object that is assigned to its own CPU; at some point in the future I might be able to break it down even further and have separate CPUs for the second-level branches.
Of course, the subject-actor would have to use his own perceived values of everybody else’s personality traits, but that can be done by transferring the perceived values into the actual values at the outset of the branching.
I must say, I am rather enamored of the idea of bringing a modern CPU to its knees.