Tuesday, July 26, 2011

Knowledge Representation in Games

Motivated by an assignment (~in1122 class) I started to create a system that could take several game session logs and analyze them to find non-trivial relevant information.

What is non-trivial, relevant information in a game session? In a previous post of my blog, fat client architecture, I tell a little story that motivates this kind of analysis.

Knowledge representation and reasoning has always been a field marked by the dispute among practitioners if representation and reasoning should be put together or not. I won’t get into much detail about this, but for my work they are treated as distinct parts.

First, in this post we will explore the knowledge representation part or, in other worlds: How I use the Game Ontology Project to describe game sessions.

Second part, the automated reasoning part, is creating a production system, using Drools Expert, to analyze a game session output and recognize common game hacks. And that is the subject of another post in the near future.

GOP, or Game Ontology Project, is “a framework for describing, analyzing and studying games”. The framework consists of a “… a game ontology that identifies the important structural elements of games and the relationships between them, organizing them hierarchically”.
Initially the top level of the ontology consisted of five elements: interface, rules, goals, entities and entity manipulation. However, according to the Wiki “… [They] considered another top-level called “Entities”… However, we haven’t had the time or the need to actually explore it and see what sorts of entries we’d need to define.”
I am not very sure about this need in my work. For the reasoning a definitely needs the definition in code but in a conceptual level I am still not sure. But, since we are mostly concerned in representing a game session most of our work is developed using the Entity Manipulation branch of the ontology.

Entity manipulation consists of altering the attributes or abilities of an entity in the game world
Some of the classes that inherit from Entity Manipulation are:
·        To Collide
·        To Create
·        To Move
·        To Customize
The GOP Wiki is full of examples (strong and weak) that represent each concept. To Collide has a strong example in the game Pac-Man.
“In Pac-man, Pac-man can collide with ghosts. In his normal state, this will remove Pac-man. If he has recently eaten a super pellet, this will remove the ghost.”
A typical Pac-man game session would be described with a log that resembles the following:
·        ToMove(Pacman, left)
·        ToRemove(Point00), where Point00 represents one of the points that the Pac-man can eat.
·        ToMove(Pacman, up)
·        ToColide(Pacman, Pinky)
·        ToRemove(Pacman)
So, we move Pac-man to the left, eat a point (the others were probably eaten already), then we move the Pac-man up and the Pinky ghost gets us. Game Over!
The figure below shows screenshots of the game session that generated the mentioned output.

Figure 1: Game starts, player moves left then eats a point, moves up and finally hits a ghost.
Obviously some of these concepts need attributes to improve their expressiveness and consequently our analysis. For instance, suppose we want to check if the ToCollide is valid. How can we be sure that Pinky and the Player are in the same place?
ToCollide could also be inferred from previous actions such as ToMove from the Player and Pinky. Such rule would be modeled, in FOL, as something like:

For more sophisticated thing we feel the need to include a third element in ToCollide that represents time. So we can write rules like:
For an online game this should be mandatory. Since we handle a part of the computation to the client that is running in the player machine, it is possible to determine if the ToCollide is a valid statement or a possible cheat. The server holds all information it needs (game rules, setup of a level, etc…) to simulate server-side.
There are three important notes to be said about these rules. The first is that we are already mixing knowledge representation with reasoning here. However the rules presented are actually reasoning or a just a form of representation of our knowledge about the game rules? That is a complicated debate that is, again, out of the scope of my work.
The second is that, in a massive system with a few hundred thousand users doing an extensive analyzes of every game log is impractical. However, carefully choosing which logs, the ones with best performance for instance, is of great value not just for security but also for design.
Supose we have a game like Pacman in which the score formula makes it possible to, knowing the initial setup of the level, infer the biggest score possible and the shortest time in which the game can be completed. That would be a good filter to choose which Player should be audited.
The next post will translate some of this knowledge into the Drools Expert framework. The framework will enable us to integrate the reasoning process in a java server. We will also try to answer the question that’s in your head right now: Why would I use that instead of a ordinary procedural approach?