Archive for the ‘video games’ Category

Von Neumann Machines and CRPGs (Computer Role Playing Games)

September 8, 2006

I’ll start with the mundane fact that inspired this post: WoW was down today, preventing me from gaming online. Being a huge geek and somewhat addicted to the game, I started browsing for interesting WoW-related material online… finding, soon enough The Daedalus Project, a collection of essays, surveys and reports by Nick Yee, a grad Student at Stanford University. It’s a pretty awesome site, which attempts to explore the socio-psychological issues relating to MMOGs in a serious way. I highly recommend it:)

At some point, while browsing the site, I downloaded a video of Nick’s presentation to PARC, in which he talks about several issues in MMOGs. At the beginning of the presentation, Nick introduces the notions of the leveling grind/loop (this is a loose paraphrase). If you’ve never played an MMO before, you’ll appreciate exactly how *boring* this part of the presentation sounds. It goes something like this:

“So you talk to this guy and he tells you to kill ten rats. So you walk outside, and you see something that looks like a rat, and you smack it. It turns out to be what you’re looking for, so you kill ten of its kind, and come back to the guy. He tells you to kill twenty more rats. So you go outside again, but then you see another player, just like you. You figure you’d kill the rats twice as fast, so you join up with him, and form a group…”

I do not fault Nick’s presentation skills: this *is* boring. Now let’s skip ahead to the World of Warcraft “endgame:” quests accomplished at the highest level attainable, 60. A description of the player activity at this level can be found in the Leroy video, which, aside from being hilarious, is very good at showing two things:

– high-level quests are complex challenges, overcome only by coordinated effort and planning.

– following the ‘see and smack’ principle that worked at level 1 results in utter failure at level 60.

When I formulated the above ideas in my head, they sounded strangely familiar… but I couldn’t place where from, until I looked back at my Cog Sci reading for this week, specifically chapter two of E. Baum’s The Mind Is a Computer Program, which discusses Turing and Von Neumann machines. That’s when it hit me: character leveling in MMOs (and indeed in most computer roleplaying games) heavily resembles evolution through interaction with self-replicating automata, i.e. Von Neumann machines.

First, a quick note on background: the wiki article is quite general, and at first glance doesn’t seem to include Von Neumann’s famous proof of self-replicating machines. I’ll reproduce it here partially; viewers familiar with Turing machines and logical constructions should be able to follow:

“There is no great difficulty in giving a complete axiomatic account of how to describe any conceivable automaton in binary code. Any such description can then be represented by a chain of rigid elements like that. Given any automaton X, let f(X) designate the chain which represents X. Once you have done this, you can design a universal machine tool A which, when furnished with such a chain f(X) will take it and gradually consume it, at the same time building up the automaton X from parts floating around freely in the surrounding milieu. All this design is laborious, but it is not difficult in principle, for it’s a succession of steps in formal logics. It is not qualitatively different from the type of argumentation with which Turing constructed his universal automaton.” (Von Neumann 1966, p. 84)

He goes on to say:

“Now, we can do the following thing. We can add a certain amount of control equipment C to the automaton A + B. The automaton C dominates both A and B, actuating them alternately according to the following pattern. The control C will first cause B to make two copies of f(X). The control will next cause A to construct X at the price of destroying one copy of f(X). Finally, the control C will tie X and the remaining copy of f(X) together and cut them loose from the complex (A + B + C). At the end the entity X + f(X) has been produced. Now choose the aggregate (A + B + C) for X. The automaton (A + B + C) + f(A + B + C) will produce (A + B + C) + f(A + B + C). Hence auto-reproduction has taken place.” (Ibid, 85)

Finally, and most crucially:

“You can do one more thing. Let X be A + B + C + D, where D is any automaton. Then (A + B + C) + f(A + B + C + D) produces (A + B + C + D) + f(A + B + C + D). In other words, our constructing automaton is now of such a nature that in its normal operation it produces another object D as well as making a copy of itself.” (Ibid, 86)


So how does this relate to gaming?
Very simply. All that has to be introduced is the notion of ‘leveling,’ which most of the viewers should be familiar with. When a character in an MMO or any CRPG levels, he/she usually acquires new abilities, or enhances existing abilities. Then let (A + B + C) be the original character, while f(A + B + C + D) be the “character sheet” of the same character at one level higher. Then, by analogy, the character can append its new character sheet to itself to produce the one-level-higher version, plus a copy of the same “character sheet” (allowing other players following the same leveling path to use the latter!).

Why is this cool, anyways?

So the technical comparison I’ve just made is somewhat trivial; but the framework it suggests is, IMHO, not.

First of all, one of the implications of Von Neumann’s work was that his machines can reach arbitrary levels of complexity, bounded only by the kinds of automata one could write down (and thus, only by the rules of first-order logic). Now think back to the Leroy video – overcoming difficult challenges, planning, coordination – very complex constructs from a logical point of view! It seems that the structural similarities I have traced out between MMO characters and Von Neumann machines correspond to functional similarities between the same.

Second of all, if we extend the analogy on the MMO side, we can try to represent character sheets as schematics, composed of the same basic elements as the characters themselves. Writing down these character sheets in terms of first order logic would be a notational nightmare; but we can probably try to create a second-order language of basic abilities, such as:

  • attack bonus
  • damage bonus
  • armor class
  • hit points

etc. Each of these abilities can easily be represented as a variable / subroutine within a computer program, which in turn is reducible to a logical construct. Now, given this second-order language, we can also likely represent every ability, spell, item, etc. in any MMO world as a sentence. I of course do not have an explicit proof, but one needs only to take a look at the way players write down MMO items/abilities in shorthand (for instance: “axe35-46dmg/spd1.6” to indicate the relevant properties of a weapon) to get an intuitive sense that this is the case.

Third, and finally, Von Neumann’s work includes a further passage (which I won’t quote here) on mutation and evolution. The gist of it is: if we take the process of self-replication to be akin to biological reproduction, and introduce a random mutation to the machine in the course of the reproduction, one of two things might happen. Either the mutation will occur in one of the elements A, B, or C, rendering the resulting machine unable to self-replicate further, or “sterile;” or the mutation will occur in element D, resulting in machine (A + B + C + D’), able to reproduce further. If we add the concepts of evolution and of survival of the fittest into the resulting model, we approach a “machinistic life” framework wherein biological-type competition leads to emerging complexity from basic building blocks. The implications for carrying this framework over to an MMO are particularly intriguing: the players, potentially, are evolving “fit” characters who are able to make the best use of a set range of parameters (character stats) to survive and reproduce (in the replicating/leveling sense) in a hostile environment.

So who cares?
No, this isn’t all a revelation of The Next Big MMO (though it could be, if somebody wanted to). Rather, if this series of ideas holds up to further scrutiny, it might be a key towards emerging complex behavior in interacting agents! One twisted, probably unworkable scenario would be to create a test server of some MMO and secretly populate it with automata – computer programs that level and adventure along with the players. Preposterous, I know… but what would happen? Given the MMO environment, it might not be too difficult to make these automata pass a local version of the Turing Test (player interaction can be extremely limited, and it’s in principle possible to communicate via a small vocab of chat phrases). Many there would be a lot of failures; maybe, even in the best case scenario, one would only develop a group of level 60 automata that are really good at raiding, aggroing, and pulling; but maybe, just maybe, they might learn to cooperate and multitask in a general competitive setting). And that would be one step closer to AI.

Whew. This was long. Most of you guys have probably gotten stuck on the Von Neumann. But if anyone made it this far, thank you for reading, and please comment!

Vlad