Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
An Approach To Game Compromise

By edAqa in Science
Fri Dec 06, 2002 at 08:50:04 AM EST
Tags: Software (all tags)
Software

Game compromise, a term that includes cheating and cracking, seems to mature at the same rate as game creation. For each device implemented follows a device to manipulate it. For each countermeasure comes an equally capable circumvention. A body of knowledge about the mitigation of compromise has grown, and continues to grow. It is unfortunate however that this knowledge appears disparate: inaccessible to those who need it and lacking a general framework of classification and extension.

A part of this document has been omitted since it cannot be displayed here (Math formulas), but it is not essential to the paper. The full paper (with original layout) can be found as a PDF here.


Bearing that specific problem in mind, this paper seeks to provide a starting point to the collection and analysis of compromises and countermeasures. First, it is necessary to define a means to identify a compromise. Second, a manner in which to determine the impact of a compromise is required in order for this to be of any predictive use. Third, the groundwork for the mitigation of compromise which will serve as the starting point for continuing works is sought.

This work is intended for presentation to the video game industry, particularly game developers, and as such the examples, and some terminology, are closest matched to this audience. Nonetheless, this is not solely applicable to such realms, and will strive to maintain generality where possible.

Type of Compromise

It is sufficient to provide a simplified view of the game architecture in order to define the two primary categories of compromise. We can split the game into the game world and the player world -- working definitions can be provided later. Information either travels from the game world to the player world, or from the player world to the game world. The former is normally classified as output, and the latter as input.

With two streams of information there naturally follows two types of compromise, one for each stream. The compromise of the output stream is termed the alteration of knowledge. This is so named because it impacts what an individual in the player world knows about the game world. The compromise of the input stream is termed the alteration of ability. This is so named because it impacts how an individual in the player world interacts with the game world.

Both situations present the opportunity for benefit or detriment. In the knowledge stream, a compromise may expose more details about the game world than normally allowed, or it may obscure that which is normally visible. In the ability stream, a compromise may augment abilities, or it may handicap them. It is vitally important to consider both benefit and detriment opportunities in game analysis.

Benefiting a stream would likely be done by a player to give himself, or his team, an increased chance of succeeding in the game. By increasing the amount of data visible by the players, a compromise improves the knowledge of those players, enabling them to make better informed strategic or tactical decisions. Altering the ability stream may improve player reactions and resources, or it may grant the player abilities they would not normally have.

Example: In Quake a player may have altered their local version of the enemy model skins such that they glow in the dark and/or with spikes that can be seen through walls(1). This is a benefit of knowledge compromise, as it affords that player to clearly see his enemies, which would otherwise be obscured by the dark.

A detriment to a stream would likely be done by a player who is attempting to weaken the position of his opponent. The compromise may hide essential information, limiting the ability to make informed decisions, or alter the actions taken by the players, thereby reducing their effectiveness.

Example: An FPS server maintainer sets the damage done by all non-clan members to be 90% of the actual damage. This is a detriment of ability compromise, as it weakens the ability of non-clan members by lessening the damage level they can inflict.

Note that compromises may target a specific set of playes, or it may simply impact the entire. In the case of the entire game it may still yield an advantage for specific players - that is, the applied compromise may produce a game world, that although it seems fair, offsets the balance in favour of a certain player's strategy.

Example: In an RPG a player may alter the mechanics of a realm such that all magical enchantments and magical effects have reduced effectiveness. This would reduce the damage done by enchanted weapons, but would also reduce the damage blocked by enchanted armor - the net effect might appear the same to many of the players. The exception being that the compromise was instituted by a player who does not rely on such magical effects: in absolute consideration, all others positions are lowered, and his remains equal,but looked at relatively that means his position has improved. Neverwinter Nights allows extreme opportunities as players can act as DMs creating their own relams stocked with custom items and thereby granting themselves extra powers.

As noted in the previous example such compromises may not be very overt. The more often a game is played, or the more often data in a particular game is used, the more susceptible it is to subtle changes. That is, a 1% change in a single instance would not likely be noticed, nor would it alter the outcome of the game. However, that 1% applied over hundreds of instances would slightly improve a player's ranking. In games that are very sensitively balanced, small changes in the game can make very large impacts over a period of time. The consideration of volume is further discussed under Detailed Analysis.

Classifying game compromise makes possible a common dialog that can be used to document, research, and discuss such compromises. As seen with software development in general, the establishment of patterns is a common method used to trade experience and to learn new techniques. The above does not profess to be the ultimate classification technique, rather it serves as the base from which a more complete repository of compromises could be based - such classification is vital to a particular project, as will be revealed further by this document.

Potency / Availability

The basic model of knowledge and ability is not sufficient for a predictive framework. Extension, by means of providing further classification, is needed to allow for analysis of impact.

Potency

Information in a game has, at any time, a particular state. Whereas the knowledge and ability stream indicates only the direction, the state of the information has two distinct properties: abstraction and accessibility.

Abstraction is the expression of the degree of purity, or conversely the degree of realism, represented by the data. What an individual in the player realm ultimately receives is the least abstract form of information. This information, received by the player, is said to have passed the reality fringe. What the game ultimately manipulates is information in its most fundamental form - a form in which no further reduction or separation can be performed. This fundamental information lies within the purity fringe.

Example: Morrowind, with patch, displays the hit points of the enemy only as a colored bar on the screen. It is likely that this data is stored in memory as two integers, current level and maximum. The display engine does not need knowledge of the absolute values, but instead only needs a percentage representation of the current level. This combination of the two variables pushes the data past the purity fringe. The display engine then draws this percentage as a colored bar on the screen. At the point of display the information has passed the reality fringe.

The Might And Magic series incorporated this revelation of potency directly into game by: acquiring additional skills and items will allow the player increased levels of knowledge about the game monsters or items.

A game compromise does not normally impact the data in a game directly, rather it alters the behavior of a game component in order to indirectly alter the data.(2) Each component tends to manipulate more than one piece of data. This leads to the defintion of Potency, which indicates how much control of a game a would be gained if the component were compromised. That is, the potency considers all of the data that exists in a component, where as the abstraction refers only to specific data items.

Availability

Accessibility is the expression of the degree of security for the information streams. On the one extreme the game defines a protocol of exchange that is rigidly enforced by external means. That is, the enforcement of this security is outside the scope of the rules of the game.(3) This protocol crosses what is termed the secure fringe. On the other end of this scale information leaves the game world -- the game has relinquished all control of the information into another domain, the player world. The point at which information crosses into this new domain is termed the free fringe.

Example: A game server resides behind a firewall that allows, an enforces, only a well defined protocol to propagate. This firewall is providing the secure fringe -- it is an external means used to rigidly enforce a game protocol. At the other end is a multicaster, which takes game information packets and broadcasts them unencrypted within a local network. This multicaster is on the free fringe, as once it broadcasts the data in this form, it has given up all control of the data.

At each point in the game, either within a component, or the exchange between components, each data item has some level of accessibility. It is important to consider how often this data will be used, or will appear, in this component. This is known as the volume of the data. The more often data is used, the more susceptible it may be to compromise(4) - or quite possibly, the more often it will likely be targeted for compromise due to its prolonged influence on the game. The consideration of volume and accessibility together yields the availability of the data.

Risk

Abstraction and Accessibility are properties that can assist in determining the risk of a compromise. As information moves away from the secure fringe to the free fringe, it becomes increasingly susceptible to manipulation -- that is, its availability increases. As information moves away from the purity fringe to the reality fringe, the potency of manipulation generally decreases. Used appropriately such analysis can provide the basis to reducing the occurrence of, or mitigating the effects of, game compromises.

The fringes have special meaning in relation to the availability and potency. Below the purity fringe the potency reaches a maximum - a compromise would be capable of altering the complete range of a variable. Above the reality fringe potency reaches a minimum(5), since the information has already undergone every translation applicable to it. Below the secure fringe availability becomes constant, typically a minimum, as access is limited by fixed external means. Above the free fringe availability reaches a maximum - in terms of game rules, any entity is now free to access the data.

Clearly most games will not follow this strict linear pattern, as that would require a very strict layered architecture. Normally various components of a game need to be defined and then placed appropriately with respect to the fringes. The analysis is then done for each component. The preceding provides this basic framework for identifying trouble spots, more information can be found in the Detailed Analysis section.

Note: Although it seems similar, the potency and availability should not be considered the same as impact and occurrence (or probability) in terms of traditional risk management. The reason is that it may well be a social consideration that determines which points are more susceptible to compromise.(6) In a game with a persistent world, a cheater may choose to exploit a very low potency compromise in order to prevent detection, but nonetheless gives them a long-term advantage. For a cracker, nothing short of the most potent compromise is of any use to them, and they will ignore all other available compromises in search of one which unlocks the game. The sociopolitical considerations are a topic for further research.

The intent of such analysis is to provide a clear starting point towards the improving of the game, in terms of reducing compromise occurrence and mitigating compromise impact. Establishing the fringes is a method to quickly eliminate, or provide, the manners in which this goal can be achieved. For example, the fringes can either quickly indicate that not such mitigation is possible, or that external security mechanisms are better than in-game mechanics. Additionally, the potency and availability score serve as a manner for communication within the development environment, assisting in project planning and quality assurance.

Mitigation

Mitigation is done by addressing the general reduction techniques and identifying some key trouble areas. The primary technique is domain adjustment, which will yield the most beneficial results(7). Following this are the range reductions, which are more specific.

Note: The Detailed Analysis section contains information pertaining to how the following strategies are devised.

Domain Adjustment

On the high side of the domain is the reality fringe and the free fringe. If the free fringe lies below the reality fringe then the game has provided for an easy compromise of abstract data (i.e. Abstract data is readily available for the would-be cheater). In order to minimize this area of compromise, it is necessary to push the free fringe up to the reality fringe.

The free fringe is not typically pushed beyond the reality fringe(8), as once the information has passed the reality fringe it is primarily outside of the domain of the game. Any attempt at pushing this fringe further can always be matched with mimicry, or intelligent interpretation. That is, since the intended players reside past the reality fringe, it is not possible for the game mechanics to distinguish between a genuine entity and an artificial one.

It should be noted that mimicry and intelligent interpretation are both techniques that can be used well before the reality fringe is passed. Mimicry is the act of tricking the system into believing that the input is coming from a genuine entity, that is, it is a compromise of the ability stream in the game. Such trickery could be devised to react to abstract data, or interpreted data, made available by another game compromise. Intelligent interpretation simply refers to a compromise of the knowledge stream that takes partially abstract values and calculates derived values of interest to a mimicy devise, or for presentation to the player.

The presence of both a mimicry compromise and an intelligent interpretation compromise yields an effective short-circuit of the complete game streams. In such a situation the player appears to react to game events even though neither the event, nor the action, required any actual intervention on behalf of the genuine player. Curiously, this exact scenario is intentionally implemented in any game that allows for the participation of artificial, or computer, opponents. Such games need to be careful, as the system being exploited by the artificial player is likely also going to be a target for compromise.(9)

On the low side of the domain is the purity fringe and the secure fringe. Since compromises on abstract data have the greatest potency, it is desirable to ensure that the secure fringe is greater than the purity fringe. In the interest of compromise reduction it is actually desirable to push the secure fringe as close as possible to the real fringe. In practice this latter attempt will be limited by available mechanics.

Example: In a typical computing environment, the pushing of secure fringe to the real fringe could be realized in this scenario: all game output comes as an A/V stream from a secure server, all game input devices send their raw data (keystrokes, mouse movements, etc...) directly to that secure server. This allows only for a mimicry compromise. That is, a compromise would need to mimic the behavior of a human player, as it has no knowledge of any abstract data, nor any manner to produce enhanced abilities. This compromise is not fairly preventable, and is also the most difficult. Fairly meaning that perhaps it could be prevented, but would also punish valid playing entities -- such as illegitimizing high shot accuracies as in games like Quake.

Range Reduction

Range reduction means either reducing the potency or reducing the availability. Within the gaps between the purity fringe and reality fringe, and the secure fringe and free fringe, reduction of range is the only option available for mitigation of compromise. This reduction can be complicated - indicating domain adjustment, minimizing of these gaps, is the primary goal. When reasonable domain adjustment has be exhausted it is however necessary to apply range reduction.

In both the potency and availability range there is an implicit reference to volume of data. Potency and availability are both proportional to the volume of information available. This makes the volume the first target for reduction, as its reduction will result in the reduction of both potency and availability.

When calculating the volume of information is important to consider three values: the size, the rate, and the instance count. The size is the strict size of the information packet, presumably expressible in bytes. The rate is how often the information passes the defined point. The instance count is the one that may often be forgotten. It is an estimation of the number of instances of the game that will exist during its lifetime.

Note: The instance count is important because often the number of compromises available for a game is most related to its popularity. Including this in the expression for volume explicitly includes this variable into compromise consideration.

Potency is an expression of the form of the information contained in the knowledge and ability streams. Reduction of the potency, other than a volume reduction, means a reduction in the abstraction, or generality of the information. This reduction can be achieved by either specifically limiting the range of allowed values for information, or by exposing function results instead of function variables.

Example: Storing a game variable as an integer allows any valid integer value to be placed in that variable. Specifying this integer as a strict set of values, limits the potency of modifying that variable. In some programming languages, such as ADA, this is offered as a natural syntax.

Availability is an expression of the security of the information contained in the knowledge and ability streams. It is typically a calculation of the complexity of the encoding, and the volume, of the information. Reduction therefore, aside from reducing volume, is achieved either by increasing the complexity of the data encoding.

Complexity is well expressed in terms of the computational complexity required to sensibly modify the target data. This is a combination of both the discovery complexity, and the execution complexity. The discovery complexity is an expression of how long it takes for the player world to understand the mechanics of the protection. The execution complexity is the standard complexity of how long it would take to break the encoding and modify the data.

Example: Discovery complexity is often treated as negligible in most secure environments -- security cannot be achieved by obscurity. However, in many environments the discovery time may be long enough to cover some critical time period. Spyro's Revenge existed for, what is seen as, a very long time before a crack emerged (a 2 month discovery complexity), but this was sufficiently long to prevent pirate copies from appearing during the primary sales period after release.(10)

Impact of Defects

Normally defects are the wild cards of game compromise: you do not know in advance where they will appear or what impact they will have on the game. Since it is unrealistic to assume that defects will not occur, and because their impact on game compromise is significant, it would be unreasonable to have a method to mitigating game compromise that did not consider the existance of defects.

It is possible to consider defects without the modification of the overall method: treat potential defects in the same fashion as potential compromises. This is sound since it is possible that every defect could alternately be introduced in the form of a designed compromise. That is, the set of all defects is a subset of possible compromises. This is also reasonable, since defects are often used as leverage to produce more significant compromises. It therefore follows that the general method for analysis of compromise includes the impact of defects.

One non-negligible trouble point when including defects in the analysis is the significance of the secure fringe. There arises a class of defects that occur on the priveleged side of that fringe, meaning they may not subject to external security considerations. A manner in which to reduce this problem is by segmenting the secure fringe, such that the intended secure portions of the game are subjected to secure communications with each other. Such a technique is usually discussed in relation to Byzantine failure(11) and will not be further discussed here.(12)

Detailed Analysis

This section defines more precisely the terms and concepts presented in the paper. It was completed in parallel with the discussion aspect of the paper. It is intended to provide, when possible, a less ambiguous set of definitions, for the purpose of critique and review of this paper. Additionally this allows for a more rigorous search of inconsistencies and ommisions from the general discussion, and the method in general. It is not a normative definition, nor is it meant to supplant the general discussion.

This section has been omitted from this form since it uses equations that can't be shown. Please see the PDF for this section.

Footnotes

1. http://planetquake.com/ Pak2's mods

2. Many games are susceptible to trainers, items that often directly alter the memory of the system. Such a compromise can be thought of as an alteration in the behavior of the memory of the system. Additionally, often compromises alter data is being actively transferred between components - Detailed Analysis shows how the transfer points can be treated the same as the component behaviours.

3. A secure socket layer through a firewall is an example: the defines a protocol that will be used to communicate with a server and it is understood that it will be the jobs of the system administrators to prevent unauthorized access to that server.

4. In specific cases, such as certain forms of interpretation and cryptography, the task of understanding or decrypting is eased by the presence of multiple samples of data. Especially in cases where the range of data limited, an abundance of samples allows a compromise to tune its operations to minimize the ambiguities in its calculations.

5. Reaching the minimum of potency doesn't necessarily mean a compromise would not be effective, for such a minimum may well yield a promising compromise.

6. This consideration is termed relevance, and is mentioned briefly in the Detailed Analysis of Potency. This analysis in this form does not provide a method to include relevance.

7. This is ascertaining by examining the detailed analysis, where it indicates that domain adjustment would remove entire components from certain consideration, whereas range reduction would only reduce the potency and availability of specific components.

8. To prevent certain types of cheating it may be desired to push the free fringe beyond the real fringe - this would be the case when the real data is still easily interpreted and or modified. Such an action however would be rarely effective without out-of-domain cooperation, which is the core of the subject about Digital Rights Management (DRM) Operating Systems, such as Microsoft's next OS version Palladium. It should be interesting to note, that any game which involves a human element, necessarily needs to have domain travel from the game world to the real world, which guarantees that that there are components where the data is both real, and fully available.

9. To an individual who wishes to cheat and/or develop a compromise, it should be clear that the presence of an artificial game player indicates that mechanisms exists which allow short-circuiting the full knowledge / ability stream loop. Extending this even further, any game that includes any sort of artificial agent necessarily has such ability to short-circuit the loop (this easily includes both the scripted behaviors of NPCs in an RPG and behaviours of intelligent monsters in an FPS). Since such intelligent systems are typically designed to be extendable, for the introduction of new agents, or for customer play programming, they are also likely to be a significant source of compromise.

10. "Keeping the Pirates at Bay: Implementing Crack Protection for Spyro: Year of the Dragon", Gavid Dodd, http://gamasutra.com/

11. "The Art of Systems Architecting", Mark W. Maier, Eberhardt Rechtin, includes a brief description of such failures and their use in systems architecture.

12. Refer to "Intrusion-Tolerant Enclaves", Bruno Dutertre, Valentin Crettaz, Victoria Stavridou. This paper describes a manner to prevent intrustion, but such techniques could also be applied to mitigating the effects of defects within the secure fringe.

13. In Age Of Empires a compromise appeared where the player was capable of seeing how much money the other player had (they had discovered the memory location where this data is held). The relevance of this discovery was not immediately obvious to the designer of the game, he initially thought it was not that significant. Upon further description it was understood how significant this really was: by continually monitoring this level of money it was possible to identify discrete transaction amounts, and then furhter correlate this to known events in the game, effectively revealing the strategy and current status of the other players.

References

"A layered Brain Architecture for Synthetic Creatures", Damian Isla et al, The Media Laboratory, Massachusetts Institute of Technology, 2001

"Cyberspace in the 21st Centry: Part Sevent, Security is Relative", Crosbie Fitch, Gamasutra, 2002

"How to Hurt the Hackers: The Scoop on Internet Cheating and How you can combat it", Matt Prichard, Gamasutra, 2000

"Internet Game Design", Tu-Shen Ng, Gamasutra, 1997

"Intrustion-Tolerant Enclaves", Bruno Dutertre et al, System Design Laboratory, SRI International, 2002

"On the (Im)possibility of Obfuscating Programs", Boaz Barak et al, 2001

"Security in Online Games", Andres Kirmse and Chris Kirmse, Gamasutra, 1997

"TCPA / Palladium Frequently Asked Questions", Ross Anderson, 2002, http://www.cl.cam.ac.uk/~rja14/tcpa-faq.html

"The Art Of Systems Architecting", Mark W. Maier and Eberhardt Rechtin, CRC Press, 2000

"The Case For Game Design Patterns", Bernd Kreimeir, Gamasutra, 2002

Games

Age Of Empires

Might And Magic

Morrowind

Neverwinter Nights

Quake

Spyro The Dragon

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o Scoop
o here
o 1
o 2
o 3
o 4
o 5
o 6
o 7
o 8
o 9
o 10
o 11
o 12
o PDF
o Age Of Empires
o Might And Magic
o Morrowind
o Neverwinte r Nights
o Quake
o Spyro The Dragon
o Also by edAqa


Display: Sort:
An Approach To Game Compromise | 83 comments (55 topical, 28 editorial, 0 hidden)
Old subject, old problem, old solutions... (4.40 / 5) (#12)
by dasunt on Thu Dec 05, 2002 at 08:06:12 PM EST

This problem of players cheating in a multi-player online game is a problem that has been around for over a decade. In MUDs, the solution is simple, never give the players knowledge they don't have and don't trust their input.

That means always check to make sure they can interact with objects, and always, always, assume that they will cheat.

Sadly enough, if the MMORPGs were the typical MUD, the code is so weak that a player could walk into a bank and "deposit" -1000000 coins, becoming an instant millionare.



That doesn't cut it (none / 0) (#52)
by p3d0 on Fri Dec 06, 2002 at 05:56:07 PM EST

There is always some valid input X that a very good player can make. With enough effort, a bad player can cheat in such a way as to provide input X. Therefore, simply making sure input is legal doesn't prevent cheating.

As an extreme example, let's suppose I'm playing chess against someone else online. How do you make sure I don't have Gary Kasparov sitting next to me giving me advice?
--
Patrick Doyle
My comments do not reflect the opinions of my employer.
[ Parent ]

Already happened... (4.50 / 2) (#54)
by dasunt on Fri Dec 06, 2002 at 07:34:53 PM EST

MUDs really have seen a lot that's under the sun of online multiplayer gaming. Bots are old news. Hell, any of the popular mud clients have the ability to trigger responses off incoming information, allowing an automatic or semi-automatic playing style.

In one of the muds I really enjoyed, triggers didn't go far. Sure, they were nice enough for XPing, but for player vs player fights, the mud would tend to go to the player with the most knowledge. Humans are a lot more effective then you'd think. Especially since in the muds I played in, there was about a half-second to second tick a lot of combat ran off of.

I once saw an excellent mudder sit down on an old 486 which was so slow under its OS that it had a second lag with the server (more depending on how much stuff was being spammed across the screen). After a bit of practice (say about 10 hours worth) the mudder finally adjusted himself to the point where he was a match for most people in player vs player combat.

Hypothetically, bots would provide a small advantage against two equally skilled players. In practice, it never works that way. The person who tends to sit back and figure out exactly how a mud works and what everything does doesn't tend to be the same person who writes the bots.

Now the FPS bots are getting pretty good. FPS's are a lot different from MUDs - you need the ability to run around, grab weapons, and aim quickly. But as long as you limit the FPS bot to the same input a human character has, my money will be on a good human character. Bots don't learn well. Humans do.

Just my $.02



[ Parent ]
Well (4.00 / 1) (#68)
by carbon on Sun Dec 08, 2002 at 03:30:47 PM EST

Now the FPS bots are getting pretty good. FPS's are a lot different from MUDs - you need the ability to run around, grab weapons, and aim quickly. But as long as you limit the FPS bot to the same input a human character has, my money will be on a good human character. Bots don't learn well. Humans do.

Well, FPSes have a tactical element as well, and even a strategic element under various teamplay modes and certain maps (Q2 DDay is a good example.) The problem is, in most FPSes, with good enough aim, you can discard the tactical part and just shoot yourself.


Wasn't Dr. Claus the bad guy on Inspector Gadget? - dirvish
[ Parent ]
More on muds (5.00 / 1) (#70)
by dentin on Sun Dec 08, 2002 at 07:30:34 PM EST

I run the mud Alter Aeon, and I definitely agree with you.  Bots are really old news, and there's enough strategy involved in a mud that using a bot really isn't worthwhile.  Using a bot on AA is even less worthwhile than most:

The mud provides server-side aliases.
The mud provides built in command stacking.
The mud provides built in variables.
The color system is designed to be effective and unobtrusive.

In addition, we have some very unobvious anti-bot code that makes 99% of botting scripts ineffective.  This only hits long term bots, such as exp bots or bots that attempt to improve spells and skills, which guarantees that it doesn't interfere with valid players.

About the only things you really need a special client for are highlight filters and triggers/actions.  The need for triggers is partially removed by setting short two-letter aliases that can be quickly invoked.

This all has tended to level the playing field between those using scriptable (hackable?) clients and those using regular telnet.  Having the latest and greatest mudding client with all the bells and whistles gives a player no discernable edge in the game.

I do disagree with your last comment though, about limiting bots to the same inputs that humans have.  A bot will always be able to respond faster than a human being given the same inputs, and more accurately/reliably.  The time delays in a mud are big enough that the bot response is mitigated; but in a FPS timing is everything.

-dentin

[ Parent ]

Maybe, maybe not (none / 0) (#74)
by X3nocide on Mon Dec 09, 2002 at 02:16:08 AM EST

Constraining a bot to a simple stereo sound source and a set of pixels for input will put a lot of strain on computing power. For most first person games coding and optimal strategy would be a fairly easy task of combining waypoint routes with pattern recognition to find opponents. But even for these simple games, pattern recognition can be an overwhelming task, especially to perform in real time. Modern PCs have massive amounts of hardware dedicated to simply rendering the 3d scene for players. In order to write a bot like that you'd have to remove transfer the screen from video ram into computer ram every frame, or just drop the video card altogether, just so it can have the picture to work with. Then it has to determine where objects are, and where to aim to shoot them (using some sort of differential analysis). This is pretty much outside the range of personal computer power.

This only becomes harder as the game is made more complex. Imagine moving from simple deathmatch to  teamplay. Now the bot must not only recognize moving objects but needs to classify them as friend or foe. Just this simple modification will greatly alter the time needed to identify targets. You're way outside the range of personal computing now, and this has all the strategic complexity of Nim or connect the dots.

If you disbelieve me on this, I'd love to see evidence to the contrary, especially since I might be doing some image recognition for my Senior Engineering project.

pwnguin.net
[ Parent ]

Don't let the bot look at pixels... (none / 0) (#77)
by dasunt on Mon Dec 09, 2002 at 01:41:07 PM EST

Let the server determine what the player can see.

Example:
I, Dasunt, am in 3DMud (a hypothetical graphical MUD). I can only see F feet. The server takes each object, calculates its distance to me, and throws out all objects who aren't less then or equal to F feet away. (Actually, in interests of server-side efficiency, we'd probably break 3DMud into zones [which allows unused areas to swap out to memory], and keep track of the objects which are greater then F distance away - That way we can do a simple delta-M for player movement, calculate that against F, figure out which objects could pass have passed into and out of range at that time, and then recalculate for only those objects, which means can limit updates of the whole zone database to once a minute or so per player).

With that being done, the server then takes the objects and runs checks to see if one object hides another. If so, the hidden object is not sent to the client. We also calculate the player FOV and remove objects that aren't in it ATM. (But we keep track of those objects since players tend to turn alot).

We also do a similiar test for sounds, which is simplified, since we don't have to check for FOV or objects concealing each other. (Although some objects might muffle another object, but that's easy enough to add.

Then we send all this data to the client, which renders it and translates the sound prompts to actual sounds. [Or a bot, which parses it and allows it to perculate through its triggers]

Now does it make sense?



[ Parent ]
Makse sense, but allready assumed in conjunction (none / 0) (#79)
by X3nocide on Mon Dec 09, 2002 at 05:42:21 PM EST

My hypothetical bot is supposed refute the statement that a computer given the same amount of input as a player. While I could contend the fact that a condensed representation stream is an alteration of the input, intead I'll simply say that your approach only works for systems engineered to allow such AI, and wouldn't be very practical in the real world.

I guess I should reveal that I don't really consider the bot I decribed above a very unfair cheat. It might be somewhat unethical to pose a player as a bot but overall its kinda neat, and it doesn't use any information or formation of information I don't.

pwnguin.net
[ Parent ]

Server-side crunching (none / 0) (#83)
by A Trickster Imp on Thu Jan 02, 2003 at 01:54:04 AM EST

It'll be a long time before this stuff happens.  Remember the exceedingly poor pathing in EverQuest, and monsters hitting through walls?  The latter happens because the wall collision on the server is disabled because it uses too much CPU.  (Well that, and the incredistupid AI that would have the monster hang at the door of an inn while you killed it with arrows from safely inside.)

[ Parent ]
My brain locked up at the third paragraph (2.50 / 6) (#25)
by donky on Fri Dec 06, 2002 at 09:28:56 AM EST

This article reads like it was translated from another language.  The first sentence doesn't make sense: "Game compromise, a term that includes cheating and cracking, seems to mature at the same rate as game creation." Then theres all manner of other constructions like "Benefiting a stream would.."

I've never heard of the term "game compromise".  Did you coin it yourself?

I'm surprised this got voted to the front page and wouldn't be surprised if those who voted it there were the faction that read the comments and judge based on that when they can't be arsed reading it themselves.

Its a pity this is so shoehornistic (I too have coined a phrase) as its and interesting topic and I am sure what you have to say would have been interesting to be able to read.

"Game compromise" makes sense to me (4.33 / 3) (#26)
by czth on Fri Dec 06, 2002 at 09:38:48 AM EST

This article reads like it was translated from another language. The first sentence doesn't make sense: "Game compromise, a term that includes cheating and cracking, seems to mature at the same rate as game creation." Then theres all manner of other constructions like "Benefiting a stream would.."

Makes good sense to me. "Game compromise" is the compromising (second item under verb) of a game, just like "system abuse" is the abuse of a system (genitive adjective?). I don't get the second construction either, though.

Might well be that this article is a victim (survivor?) of the oft-observed fact that any long article with technical content gets voted up :-). I skimmed the PDF, though, looked interesting enough.

czth

[ Parent ]

How bizarre (2.00 / 2) (#27)
by donky on Fri Dec 06, 2002 at 11:37:09 AM EST

Well, the compromise in "game compromise" reads in noun form to me.  To change it into verb form I would make it "game compromisation".  To me, "game compromise" would be a term describing compromises within games - players settling with each other.


[ Parent ]
My brain agrees, but I don't (3.00 / 1) (#33)
by czth on Fri Dec 06, 2002 at 01:07:31 PM EST

Well, you caught me, I was trying to pull a bit of a fast one :) because as you say, "compromise" as the definition required by the article doesn't show up in the list of noun alternates (at least not in the dictionary.com definition).

But compromise as a "nouned verb" (hey, at least it bucks the trend of verbing nouns ;) makes sense to me as used. Probably because I've seen it used many times before ("server compromise", although of course popularity doesn't imply correctness), or perhaps there's some fancy grammatical name that I don't know for "nouning" a verb in this case that makes it all valid and legal.

Anyway, meh :>.

czth

[ Parent ]

Derivation of the term "Game Compromise" (4.25 / 4) (#35)
by edAqa on Fri Dec 06, 2002 at 01:36:33 PM EST

The term is, as czth indicated, is related to the terms "server compromise" and "system compromise". I certainly did not intend to coin a new phrase, rather I took the phrase that has some meaning already, and expanded that meaning.

Also, note, from the Oxford English Dictionary:

compromise n. & a. II 5 A putting in peril; an exposure to risk

-- edA-qa
[ Parent ]
people define meanings (1.50 / 2) (#38)
by dipierro on Fri Dec 06, 2002 at 02:40:11 PM EST

popularity doesn't imply correctness


In the case of languages, actually, it does.



[ Parent ]
Interesting article, but what about consoles? (4.00 / 2) (#28)
by Silent Chris on Fri Dec 06, 2002 at 11:42:12 AM EST

How would this transcribe to consoles?  In that case, you have a consistent architecture that (for the most part) can't be modified .  Hardware consistencies also prevent people from fooling the servers.  On Xbox Live, for example, every network packet is encrypted from end-to-end and verified.  Do people need to change their strategies to hack consoles?  What hacks are feasible (microphone hacks, because most of the hardware is external?) and what is not?

Nothing changes (4.33 / 3) (#41)
by X3nocide on Fri Dec 06, 2002 at 03:01:14 PM EST

There's no difference between the two, essentially. There's a consistant architecture, but that doesn't get you any security on its own. Additionally witness Mod Chips. There are other more extreme examples of hacking hardware involving replacing parts (especially easy with commodity parts), but we can simply consider this example: an X-Box emulator. Certain academics are right now working on uncovering the hardware specifics needed to build such a device; combined with the unscroupulus release of a few key documents the X-Box would be completely hackable. With such an emulator (and a sufficiently fast computer), the only thing X-Box live sees is the packets. Encryption isn't a magic box, everything required to perform the encryption lies within the xbox itself, so its possible to replicate those packets within the emulator as well, and forward them through a standard ethernet card, or perhaps a custom job (hurray for open PC standards)

pwnguin.net
[ Parent ]
Two words: Turing Test (3.50 / 2) (#34)
by wumpus on Fri Dec 06, 2002 at 01:27:08 PM EST

The problem is that the client must be distributed, and given a sufficiently popular client, it will be hacked.

The server (assuming it is not distributed and trusted by whoever), then has to determine if the actions are determined by a player or by software. <Sarcasm>This has been considered a hard problem </Sarcasm>. An unhackable client would be one with an optimal human interface and a challenge that software gives no advantage to the player.

The real solutions come down to steadily booting off cheaters and hoping the game is sufficiently fun to overcome cheating and allowing the players to police the game.

Wumpus

Exactly the direction I'm heading (5.00 / 1) (#36)
by edAqa on Fri Dec 06, 2002 at 01:47:45 PM EST

An unhackable client would be one with an optimal human interface and a challenge that software gives no advantage to the player.

This one observation I made while doing the research for this article.  When you look at all aspects of cheating, there is a key observation that you should always make: all you can ever do is make cheating progressively more difficult (in a mathematical sense, in a social sense, or in a technical sense), you can never eliminate the possibility.

But, as you indicate in your comment, if the game is designed such that cheating provides no advantage, then you have effectively eliminated the value of cheating.

In the domain of video games, eliminating the benefit of cheating doesn't always seem clear, but in actuality the gameplay is a major factor in this area.  For example, in a turn based strategy game, there is no requirement for snap reflexes or hurried decisions, therefore, in such a game the benefit of reflex enhancers, such as aiming proxies, have no value.

-- edA-qa
[ Parent ]

Determinism (none / 0) (#53)
by pla on Fri Dec 06, 2002 at 06:33:36 PM EST

all you can ever do is make cheating progressively more difficult

Agree totally.
Consider the "optimal" client interface for reducing cheating - Basically the server streams "live" video to the client, and the client sends input to the server. The client has no knowledge of the actual game state, it just has an input and an output that all goes to the remote game server, over which the player has no control whatsoever.

However, a human player will make quite a few errors, even in a purely turn-based game. An automated "assistant" program can prevent those errors, and doesn't even need to run on the same system as the game client (think "video camera pointed at the screen, feeding another PC that decides what to do next"). In a time-dependant game (any action game, for example), the potential for "assistance" to the human player increases dramatically.


Or, for a real-world example of what I mean, consider why most casinos disallow card counting - It gives the player a real statistical advantage over the house. Most humans don't do this well, however, and very very few can do it perfectly. Even those who *do* count cards perfectly don't base their actions on all possible cards, but only the "big" ones, such as face cards.

A computer does not have such limitations. It can determine almost instantly the probability of any card coming up, in any number of decks, with any history of already-played cards.

As a result, casinos already came up with the "optimal" cheating detection system - They ask anyone who regularly wins more than they lose to leave. And, even *that* strategy can fail, as a group at MIT has demonstrated, as long as the player can make sure the one-off winnings sufficiently exceeds the long-term loss.


So, overall, I agree with other posters that this essentially comes down to a type of Turing test, not just to a matter of security... The game server needs the ability to identify humans against computers acting like humans. Unfortunately for gamers, this forms no less "hard" of an AI problem than the complement, of producing a computer that acts indistinguishably from a human. The only difference here involves the latter still having the ability to defeat the former, meaning that, in the long run, the cheaters WILL win.


[ Parent ]
Humans vs. Computers (none / 0) (#57)
by edAqa on Sat Dec 07, 2002 at 02:57:45 AM EST

The game server needs the ability to identify humans against computers acting like humans.

I very much agree with your response, yet I will expand upon this one point that you made above.

In your sentence you mention that the "game" must be able to identify humans and computers, but then you seem to reach the conclusion that the game needs to be able to conduct a turing test in order to do this.

This is the where the distinction between the "game" and the "computer" come in.  A game strictly involving computers is not as common as games that involve a computer and a human, or with the multiplayer games, several computers and several humans.

In these cases the human players are very much a part of the game, and they can participate in the enforcement of the rules.  The computer does not have to solely decide who is genuinely human or not.

Consider the clear example of a CPL tournament.  The human players can be reasonably assured that the other human players are not using bots or gaining assistance from a second human.  This is ensured because in these circumstances the rules of the game have added a Referee (people on the floor who monitor human activity) that can quickly spot and eliminate such cheaters.  This is done completely without any modification of the computer game engine.

The less clear examples start to appear in the case of MMORPGS, where it is very difficult for a computer to decide whether the person is really accumulating wealth fairly, or there is a bug they are exploiting, or they are cheating.  In these games there are again typically observers (working for the vendor normally) who observe the world and try to detect cheaters.

Now while the computer can't detect cheaters, and a regular game player may also not be able to, an observe who is granted special abilities probably can.  In this case we give the observer the ability to observe multiple portions of the game world simultaneously, and peer within the containers of the characters, and additionally present realtime statistics on the activities of individuals. (A clever game may guise this all as magical spells or advanced technology as to not upset the game theme)

So yes, it is correct that a computer would be required to solve hard problems in order to find a great number of types of cheating.  However, the game comprises both computers and humans, and there is no strict need for the computer to solely determine the status of its players -- rather, it should cooperate with the human players to help identify cheaters.

At this point we get into yet a new realm of compromise however, as cheaters will start developing techniques to deactive or mitigate the effectiveness of the combined computer/human cheat detection.  That is, perhaps we also have a realm of meta-compromise?
-- edA-qa
[ Parent ]

reverse turing test? (4.00 / 1) (#37)
by dipierro on Fri Dec 06, 2002 at 02:36:28 PM EST

The server (assuming it is not distributed and trusted by whoever), then has to determine if the actions are determined by a player or by software. <Sarcasm>This has been considered a hard problem </Sarcasm>.


It has?  I thought the hard problem was having the computer pretend to be a human, not for a computer to determine if something is a computer or human.  In fact, here are a few such tests right here.



[ Parent ]
Original turing test (4.00 / 1) (#44)
by wumpus on Fri Dec 06, 2002 at 03:59:43 PM EST

The original test was called the imitation game and required the testee to determine which of the subjects were male and female.

For the modern test, I imagine that determining the differnce between an AI and a human is as hard as imitating a human.

This of course raises the question of how you could raise you hacker test score by failing a turing test.

Wumpus

[ Parent ]

You don't seem to understand what a turing test is (none / 0) (#47)
by dipierro on Fri Dec 06, 2002 at 04:47:57 PM EST

The original test was called the imitation game and required the testee to determine which of the subjects were male and female.


Please provide a link.  I thought the testee (the computer) was supposed to play the part of the male or female.


For the modern test, I imagine that determining the differnce between an AI and a human is as hard as imitating a human.


No.  That's not what the modern test says at all.  Did you read the CAPTCHA link?  Determining if an opponent is a human or computer is really easy.  A computer can determine if an opponent is a computer.  A computer cannot however fool a human into thinking it is a human.  Two very different things.


This of course raises the question of how you could raise you hacker test score by failing a turing test.


Because that means that people mistaken you for a computer.  It makes sense if you understand what a turing test actually is.  Read about it.



[ Parent ]
This doesn't solve the problem. (none / 0) (#56)
by wumpus on Sat Dec 07, 2002 at 12:33:38 AM EST

The test listed may work in certain areas (especially Everquest bots who repeat certain actions), but would not help in clients that assist cheaters.

I've thought of similar things for tests (tricky encoding of text to say "shoot the one on the left", to beat an aimbot, "follow the blue dots" for a driving course.

The real problem is the tests you show aren't terribly fun and don't make good games (players with suspicous charecteristics could be tested as above).

Scott

[ Parent ]

turing test (none / 0) (#61)
by dipierro on Sat Dec 07, 2002 at 12:45:06 PM EST

The test listed may work in certain areas (especially Everquest bots who repeat certain actions), but would not help in clients that assist cheaters.


True, although that has nothing to do with a turing test.


The real problem is the tests you show aren't terribly fun and don't make good games (players with suspicous charecteristics could be tested as above).


Yeah, but that also has nothing to do with a turing test.



[ Parent ]
Its hard to imitate a human (none / 0) (#49)
by X3nocide on Fri Dec 06, 2002 at 05:08:16 PM EST

But damn near impossible for a computer to determine a computer imitating a computer from a human. You can call this the "Computers aren't psychic" theorem. Basically as the approximation increases in the mimic it becomes harder, until presumably the conversation matches what was given by a human (scary thought that thankfully won't happen any time soon). CAPTCHA can distinguish shitty computers just about as good as I can, maybe a little better. But what if the mimic computer is twice as good as the current ones? Or 50?

pwnguin.net
[ Parent ]
It's easy for a computer to recognise the computer (none / 0) (#62)
by dipierro on Sat Dec 07, 2002 at 03:03:56 PM EST

CAPTCHA can distinguish shitty computers just about as good as I can, maybe a little better.


Probably a little worse, but it's really not that hard to distinguish computers from humans.  It's much harder for a computer to imitate a human.  Other than perhaps the NSA, it's pretty much impossible at this stage.


But what if the mimic computer is twice as good as the current ones? Or 50?


Then you make harder tests, and you have a freely distributed AI program to boot.



[ Parent ]
If what you said were really true (none / 0) (#67)
by X3nocide on Sun Dec 08, 2002 at 02:30:05 PM EST

Then CAPTCHA could easily be adopted to an AI. If the goal here is to simply mimic a human without reguard to time constraints then one could simply generete random permutations of a dictionary until it found one that passed captcha's testing, and present that reply. It would be hairy and slow, but to my knowledge it would be faster and less complex than every other transparent AI out there.

pwnguin.net
[ Parent ]
You've got it backwards... (none / 0) (#69)
by dipierro on Sun Dec 08, 2002 at 03:57:04 PM EST

CAPTCHA couldn't be easily adopted to an AI, something that beat CAPTCHA could...

Your random permutations theory assumes that the tester is set up to allow unlimited trials from the same [IP address or whatever].  But that would be a stupid way to set it up.

Yes, a bunch of computers generating random words all day will eventually write shakespeare.  Is that AI?

[ Parent ]

Assumptions (none / 0) (#73)
by X3nocide on Mon Dec 09, 2002 at 01:54:01 AM EST

*Assume that captcha is infalliable.
*Assume you have a working copy of captchua locally.
* using this we just go through and test some output generated either randomly or perhaps using a somewhat more sophisticated technique using the ALICE approach. just go through and make sure what you're sending captchua is valid.

The basic idea of what I'm saying is that if captcha really was bullet proof then you could use it make sure your actions were "human."

No this really isn't AI. My goal here is to show that AI and ai detection boil down to the same task. But the question is far too biased towards human value to be really useful. We assume that people are all so very smart, but ALICE does quite well without much sophistication. ALICE can't learn but could probably pass a Touring Test.

Bottom line: captcha is only good at detecting ai not good enough to fool it. A little circular but I hope you understand what I mean.

pwnguin.net
[ Parent ]

I see what you're saying (none / 0) (#76)
by dipierro on Mon Dec 09, 2002 at 10:57:03 AM EST

Sorry about that.

You're making at least two more assumptions though.

1) Time is unlimited (your approach would take too long).

2) The domain of CAPTCHA is equivalent to the domain you want to use the AI.  Using CAPTCHA would be fine if all you wanted to do was recognize numbers.  But CAPTCHA doesn't do any more than that.

Now if you have all the time in the world you could at least use CAPTCHA to defeat CAPTCHA.  But the hidden assumption is that it's harder to solve the problems then it is to make up new ones.  It's kind of like public key cyrptography in that sense.  Sure, 5 years from now we'll be able to crack ever increasing key lengths, but 5 years from now we'll also be able to generate ever increasing key lengths.

Anyway sorry for implying that you didn't understand.  I was the one who didn't understand what you were saying.

[ Parent ]

Flagrant insecurity (4.00 / 1) (#48)
by X3nocide on Fri Dec 06, 2002 at 04:54:32 PM EST

Really, I don't mind real bots that work with the same information I do: sound and sight. What gets me is the bots that rely on the fact that the game is designed to transmit the entire gamestate and rely on the client to cull information that should be hidden, like silent people behind walls. If you've ever played a game or two against bots in a game like Halflife you know what I mean really quickly. They sit there and track opponents through walls once inside their "radius." Its a challenge to beat, and can help you train to beat cheaters some, its really not all that fun. You lose the element of surprise and anticipation. The answer to the turing problem (bots that work with the same information we do) is to simply segregate by skill. Of course, as is standard with any solution, a new problem arises: hacked servers. If you don't distribute then there really isn't a problem. If you do, you now have to worry about servers acting on behalf of cheaters to lower their ratings. The best thing I can come up with here is to use statistical analysis to flag accounts that vary wildly in skill ratings adjustments.

pwnguin.net
[ Parent ]
Over analysis? (4.20 / 5) (#39)
by X3nocide on Fri Dec 06, 2002 at 02:51:05 PM EST

I agree that this is an interesting problem that is repeatedly not addressed, but I think the graph analysis and "popularity" factor is the wrong way to approach this one. Also, I think the "stream" terminology is overkill for paper, since most of the paper deals with extra information within a given state. streams of data really only become important in latent situations.

The bottom line is security inside a contained system owned and operated a user is suspect to alterations no matter what algorithms you might use. Its required that you have a secure computer for such interactions. Halflife and Q3a both utilize this approach to verifying ownership.

Once you've established a secure client/server interaction, you'll need to ensure that only the information sent is what you expect the user to need, rather than sending a superset of that data. Its important to realize that a comprimised client will use as much data as available through comprimization. You might investigate security developed for open source multiplayer games.

I also have a qualm with measuring variable importantce as number of reads. Consider this simplistic game: A simple maze game with combatant monsters to battle. Add in a mysterious artifact on each level that must be returned to the start to exit. Compared to the number of times the life meter is reference, the artifact bit is miniscule, but absolutely vital to winning.

pwnguin.net

Reason for the graph analysis (5.00 / 2) (#43)
by edAqa on Fri Dec 06, 2002 at 03:28:32 PM EST

The purpose of the graph analysis was not to be a definitive approach to this topic.  I rather used this type of analysis to derive and verify the rest of the discussion -- that is, so I could at least prove to myself that the methods I outline are indeed correct and complete within the framework I used.

I'm not sure that your example invalidates my claims about the importance of the number of reads.  

We see that the artifact is vital to winning, but I am also assuming winning requires you have non-zero life.  In this case, every access to the life-meter has an immediate influence on the outcome of the game.

If the life meter is checked every X seconds to determine if the player is dead, then a compromise could, rather than altering the value of the life meter, choose to increase the value of X and give the player an extended "grace" period.

More relevant however is an example derived from an Age of Empires cheat.  If it is possible to see every minute change of the life meter, then a compromise could reconstruct the pattern in which it changes and determine how the game is altering life.

This technique is used in electronics a lot, in what is known as side-channel attacks (basically several chips with encryption keys have been broken by the frequency which which they access data and/or the timing with which they access the data).

Consider again your maze game, we assume the computers will be making use of a path finding algorithm to locate you, or the artifact.  Perhaps this is the A* algorithm.  And then we assume the life meter is accessed once per cycle.  Now you have a very unusual potential compromise.

As the monsters approach their target the A* algorithm takes less and less time to calculate, so if the game cycle is shortened, this means the life meter is accessed more frequently.  Now a compromise could then time the accesses to the life meter and as the frequency increases it could warn the player that the monsters are nearer (even though the player may not be able to determine this on the screen).

In this case then you may have improved your chance to escape the monsters and obtain the vital artifact.

Of course this is just one example, and the paper should not have indicated that strictly the number of reads increases importance. There are many factors that come into play, but they do all fall into some basic categories, and the paper was trying to isolate those basic categories.
-- edA-qa
[ Parent ]

A Non-Technical Example / Prisoner's Dilemma (4.50 / 6) (#40)
by edAqa on Fri Dec 06, 2002 at 02:54:00 PM EST

I would like to add a non-technical example to try and add more domains on which the discussion is covering.

One of the more popular games that is used to demonstrate or ideas is the "Prisoner's Dilemma".

In this game the best strategy (rational strategy) of the players is such that they will not realize the most beneficial outcome.  However, if the game activity were compromised, we can quickly see a strategy that develops which achieves better results than one would expect of the game.

That is, if the prisoner's can, unbeknownst to the guards, communicate (a compromise of the game), they will always get better results -- but to the guards they will be acting irrationally because from the guards view the prisoner's are not following the best strategy.

The presence of a compromise alters the dynamics of any game that could benefit from coordination.  In particular a compromise tends to upset the Nash equilibrium (allowing a single person to change their strategy and have a gain, without having any other person change their strategy -- even though the rules dictate this cannot be possible).

Example:

In the prisoner's dilemma we introduce a cheat by stating that prisoner A knows what prisoner B's choice is before making his own.  This then reduces the possible score B has in the game (but B will be unaware of this reduced possibility).  In this case, A's strategy is:
    1) if B defects then to defect, minimize A's loss
    2) if B cooperates, then what A does is determined by his intentions towards B (he can cooperate with no fear of being deceived)

Should B become aware of A's ability to cheat then B has only two options:
    1) choose to cooperate and be left to A's whims as to the outcome
    2) choose to defect and ensure that A also defects

If we introduce another cheat, that allows B to understand A's intentions, then B can simply make his choice by examining his own best outcome in the strategy of A:
     1) if A intends to deceive B, then B will choose to defect
     2) if A intends not to deceive B, then B will choose to cooperate

Do note now that with these two cheats, and the final strategy of B, and the strategy of A, we appear to have a Nash equilibrium again.

I only put this example together now, so please excuse me if there are obvious problems.

-- edA-qa

Nice link (none / 0) (#60)
by mlapanadras on Sat Dec 07, 2002 at 12:31:05 PM EST

Thanks for the link. Following the hypertext I eventually got to curious autopoiesis theory which gives a whole new look on programming design patterns.

[ Parent ]
Anger at the Players (3.00 / 1) (#42)
by failrate on Fri Dec 06, 2002 at 03:08:50 PM EST

Of course this all boils down to the fact that players shouldn't cheat in the first place. However, I've actually met people before who didn't care if they won through their own ability. They just wanted to win. I can't fathom how using some hack to win could be construed as fun, but maybe these people don't really have fun. They just conquer ruthlessly. Maybe they should get into corporate finance and leave the MMORPGs to the gamers.
Voodoo Girl is da bomb!
I find this article disturbing (1.00 / 4) (#45)
by StephenThompson on Fri Dec 06, 2002 at 04:22:25 PM EST

This article makes me queasy. Its hard to express my reaction, but just let me say this: Get out of your head. Then get off the computer and get out of the house.

this is business (5.00 / 1) (#50)
by YelM3 on Fri Dec 06, 2002 at 05:36:08 PM EST

I suppose you would have said the same thing if John Carmack told you he was spending all his time coding a nazi zombie game.

This is business, there is a lot of money to be made in online gaming, and cheating reduces the quality of the game.

[ Parent ]

Would cheaters play other cheaters? (3.66 / 3) (#46)
by AlephNull on Fri Dec 06, 2002 at 04:44:39 PM EST

An interesting experiment might be to have a separate server which allows most forms of cheating (maybe short of actually hacking the server). Would cheaters be willing to play other cheaters? Or do they get the thrill only by playing against those who play by the rules?

Could also turn into an interesting social experiment. Maybe a study of gamers should be carried out. Are those who cheat online also sociopathic in the 'real' world? Can online cheating be an indicator of possible criminal behaviour in later life? Maybe the "pre-crime division" doesn't need genetically altered 'sensitives', just the server logs.

Political correctness is doubleplusungood.

vs. game company (5.00 / 1) (#55)
by bigdavex on Fri Dec 06, 2002 at 09:21:51 PM EST

An interesting experiment might be to have a separate server which allows most forms of cheating (maybe short of actually hacking the server). Would cheaters be willing to play other cheaters? Or do they get the thrill only by playing against those who play by the rules?
The missing thrill there is someone trying to stop them.

[ Parent ]
Diablo 2 did this.... (4.00 / 1) (#59)
by oomcow on Sat Dec 07, 2002 at 04:41:25 AM EST

The Battle.net support for Blizzard's game "Diablo 2" did exactly this.

"Open Battle.net" had no server side verification of gameplay so players were free to hack their characters or the game and play with each other.  "Closed Battle.net" was verified on the server side so cheating was much more difficult (although countless cheats did arise).

The high number of people who continued to play "Open Battle.net" would seem to indicate that many cheaters did enjoy playing with other cheaters.  However, there were also a high number of cheaters who preferred the challenge of cheating on "Closed Battle.net".

As for the real world studies, I think it would be hard to find much correlation.  I'm would imagine that many people who cheat in games only do so because they feel they are free from the rules of normal society so they can explore their more repressed side.  =)

[ Parent ]

Limited cheating. (none / 0) (#71)
by mindstrm on Sun Dec 08, 2002 at 08:23:46 PM EST

The problem is... if the cheating is blatant and outright, there's no point in playing. All the rules of the game become moot. CHeating is only fun when it gives you an edge.

People didn't cheat outright in closed B.net...
but there were enough bugs in the game to lets tons of peopel duplicate weapons, get bizarre stats on their weapons, etctera. And you know what? It just made the game cooler.

I

[ Parent ]

Sad. (5.00 / 9) (#51)
by pla on Fri Dec 06, 2002 at 05:40:37 PM EST

Tough to decide which I consider more disheartening - That people actually let in-game problems such as cheating *seriosuly* bother them, or that people bother cheating in the first place.

Actually, I think I would have to consider the latter less sad. If they cheat for the purpose of getting ahead in the game, okay, just totally pathetic. But cheating to see if they can (assuming they find their *own* way to cheat, not just downloading the newest version of AoE-winner-9000 or the like), I can understand that. They have pitted their skills against those of a large body of opponents. Not in-game opponents, or in-game skills, but real life opponents, and real-life skills.

For an example, I find the circumvention of certain "cheat detection systems" a fascinating exercise in human response mechanisms. For example, let's say I write a local "assistant" to a game, that monitors various in-game parameters in a transparent manner and responds much faster and more reliably than I could.

My first try, the program might notice a bullet heading for me and can always dodge it, something that I could never possibly do consistantly by myself. But, the server realized I keep responding to threats in less than 50ms, a physical impossibility ("simple" human reaction times exceed 100-150ms, complex responses take over a third of a second). So it bans me.

Next, I tell it to wait a bit to respond. Okay, the server takes longer to realize I cheat, but still catches on that I *always* dodge 300ms after the start of the event. Another impossibility, to have so precise a reaction time. Banned again.

So I make the reaction time gaussian, between 275-325ms (perhaps very rarely getting hit by the bullet at the high end of the range). This works for about two weeks, until the server notices the long-term consistancy, yet another very unlikely occurrance.

Next, I make the mean of the gaussian reaction time dependant on an underlying slow Poisson process with parameters set by some non-cyclical external event, such as the 47th letter on the front page of www.cnn.com at the time I start my current playing session. I also throw in a low chance of "letting" me get hit by the bullet, just for show. Thus, I have come up with a model that behaves VERY much like a human, but about 6x better mean performance than I could get by myself on anything but a perfect day.

The process of coming up with that model represents not only an amazing level of knowledge about human response patterns, but also a nice game of chess with the author of the game server.

Unfortunately, it pisses off all the people who really just want to play the *overt* game.


There ARE people who need to think of this (5.00 / 2) (#63)
by gte910h on Sat Dec 07, 2002 at 03:07:57 PM EST

Software engineers (okay, programmers is a better term in most shops) write games. This is a real world problem that pisses people off, therefore they stop playing your game therefore you stop getting their subscription that allows them to play your game therefore you stop getting to write games for a living and therefore have to write a post to kuro5hin.org that overuses the word "therefore".

[ Parent ]
Huh? (none / 0) (#72)
by Danse on Mon Dec 09, 2002 at 01:06:50 AM EST

Of course people are bothered by cheating. They just paid 50 bucks or whatever, and sometimes a monthly fee to play a game and some asshole has to render their investment useless by cheating and taking the fun out of the game. Why wouldn't they be bothered?






An honest debate between Bush and Kerry
[ Parent ]
Because... (none / 0) (#75)
by pla on Mon Dec 09, 2002 at 10:54:12 AM EST

They just paid 50 bucks or whatever, and sometimes a monthly fee to play a game and some asshole has to render their investment useless by cheating and taking the fun out of the game.

I think you might have missed my point...

1) The cheaters paid their $50 + $9.99/mo just like everyone else.

2) Some "players" (most likely this only applies to hard-core programmers) may find it more fun to try to circumvent game security than to try to maximize certain meaningless fields in their account data (ie, "level", or "money", or "other imaginary occupants of this database rendered nonviable").

Note that, as I mentioned previously, #2 does *NOT* apply to morons who just download the latest hack to their favorite online game. I consider that just *SO* amazingly pathetic I cannot adequately express my level of contempt. Not that I care that they have "cheated", just that I consider such folks as truly sad, pathetic humans, who don't even realize that if they "honestly" have the intent of getting ahead in the game, breaking the rules of the game to do so automatically makes it impossible (well, at least "meaningless") to attain that goal.


But allow me to wander for a moment... I have a theory.

As a bored young geek, I used to played "real" role-playing games, with other humans. Fun, rowdy, full of surprises, included human interaction.

With online gaming, I personally find circumventing game security *LOTS* more fun than actually playing the game (don't worry, Hell will get a bit chilly before *I* pay a company to test their security for them - Companies pay *me* to do that). Current online games have such a *terribly* limited range of actions a player can take. Basically, no better than an offline game, except that you can chat with other players. A MUD, with good graphics. Slash, cast, rest, repeat. Happy happy joy joy.

However, I look at those who do play in the current generation of online games. Mostly younger than me, and their only real-world role-playing experience (if you can call it role-playing) comes from crap like Magic (or worse, Pokemon) cards. Games with an inherently limited set of possible player actions.

Thus, "modern" gamers (damn, listen to me, not even 30 yet and I sound like an ol' fogey <G>) have no basis for comparison by which to see the lack of flexibility in any on-line game available.


So I guess my advice to those who bitch about cheaters at on-line games would run thusly: Call five friends. Cancel your subscriptions to AoE and pool the money you save just from one month's bill. Buy a few dice and a copy of the AD&D DM's handbook and player's handbook (personally, I don't care for AD&D, but I doubt anyone would have trouble finding it). Or, if you feel cheap, check out Sidhe, an RPG system I created once upon a time, and spend the money you save on chips and Dew.

Now, play. Real human interaction. Totally dynamic plots. Essentially unlimited possible actions in response to any situation. Enough Mountain Dew to make everyone turn pale green. And best of all, no cheaters (and if you catch someone cheating, you get the joy of pummelling them mercilessly, in person).


[ Parent ]
Heh... (none / 0) (#78)
by Danse on Mon Dec 09, 2002 at 03:13:09 PM EST

Well, that might be fine for RPG players. I got tired of MUDs a while back. The social interaction was the most interesting part, but I have other ways of getting that. I play mostly twitch games now. They're fun, require a bit of skill, and don't really force you to play constantly to remain competitive. Since I can't really play Counter-Strike with a group of friends, it does annoy me quite a bit when someone is cheating and killing everyone with one shot... through a freaking wall. Sure, he paid for the game too, but he's not letting me play the game that I paid for. That's what I get pissed about.






An honest debate between Bush and Kerry
[ Parent ]
Scrabble, and the inclusion of cheating (5.00 / 3) (#58)
by edAqa on Sat Dec 07, 2002 at 03:19:56 AM EST

The game of scrabble obviously has many ways in which a player can gain an unfair advantage by means of a compromise.  There is however a rule in this game which incorporates the notion of untrustworthy players.

The basic rules of the game allow you to play any letter combination on the board that you please -- the board, the pieces, and the scoring will do nothing directly to stop you (although it does state which types of words you are allowed to play).

So along comes a player who decides to put words on the board that aren't real.  Another player dislikes this "supposed" word.  The rules of scrabble include a manner by which this tension between the two players can be resolved: the challenge.

If one player feels strongly enough that the word another player has created is not genuine, he can challenge that player, which becomes a miniature game in itself (and if you draw the game score matrix you will see it has a similar pattern to the prisoner's dilemma).

This challenge rule has essentially eliminated the game compromise* of playing an invalid word.  Rather it has made invalid words a viable and manageable aspect to a game strategy.

Scrabble therefore demonstrates one of the methods to mitigate game compromise: include the known manners of cheating in the rules of the game.

*Note: This actually allows computer opponents to cheat quite easily, as it would take more work to program an opponent that didn't have perfect recollection of the entire dictionary than one that did.  Thereby the cheapest computer opponent will always notice every invalid word and will always wage a successful challenge.

-- edA-qa

Cheat/challenge (none / 0) (#81)
by the on Tue Dec 17, 2002 at 12:22:09 PM EST

Given any game you can convert it into another by adding a rule that allows you to break a particular rule under threat of challenge. In fact, you could argue that Poker is just a game. Another nice example is the game Cheat. The underlying game is simple: you must discard all of your cards by throwing down matching sets. The twist is that you play with cards face down and you can be challenged. In fact, one time I took a normal trick taking card game (I think it was called "Le Truc" but I wouldn't stake my life on it, it had some slightly weird features like eights being high or something like that) and added the rules that all the plays are made face down and a trick is lost if you are challenged and can't demonstrate that you just played the cards you said you played. It made for some really interesting play with some quite extended stretches in which nobody saw any cards whatsoever.

--
The Definite Article
[ Parent ]
Poker is most certainly not just a game. (none / 0) (#82)
by vectro on Tue Dec 24, 2002 at 12:03:32 AM EST

It is a way of life.

“The problem with that definition is just that it's bullshit.” -- localroger
[ Parent ]
I think that this is a broad survey... (3.00 / 2) (#64)
by gte910h on Sat Dec 07, 2002 at 03:21:01 PM EST

...with an overblown, stilted writing style. This IS an important topic for people who make games. I think that this article's needs to read a good book on writing understandable english, but just having taken a class in which I made a networked game, I see where a LOT of these issues could be of interest for a game that people have an incentive to cheat at.

why the negative comments (4.33 / 3) (#65)
by padlock on Sat Dec 07, 2002 at 11:55:37 PM EST

I read this and couldn't believe the types of negative feedback this guy got. My only complaint would be that there weren't many hard technical tricks or methodology in his post either defense or attack.

But as to the idea that he's in his head, stilted or wasting his time, all I can say is get real, this type of information warfare kind of thinking goes back to the earliest real hackers and the bbs days.

Although his article is admittedly a high level theoretical overview, the people who are working on the techniques currently at play are probably years ahead of DOD programmers for example.

Just wait until the US faces a technologically equal opponent on the battlefield, and they start to attack the information pathways between our combatants' systems.

All you player haters who would rather have a coffee and chit chat about the latest film you saw should respect the people who disconnect from the real world and work in an abstract world instead.

It takes all kinds of people to make stuff go!

Counter espionage... (5.00 / 1) (#66)
by skyknight on Sun Dec 08, 2002 at 01:33:36 PM EST

is an interesting and highly effective way to help the "good guys" keep up with the bad guys in the cheats arms race. There are lots of little black hat cheating corps (how the hell does one pluralize 'corps'?) around that are comprised of people who dedicate substantial time to cracking software.

The counter espionage strategy involves having a white hat infiltrate one of these groups, posing as someone who wants to be a black hat. Over time they gain the trust of the group, and all the while the leak information out to the white hats who employ that knowledge in their latest cheat detection code.

Currently there are people who perform this service to various gaming communities out of a selfless love of the game in question. With the rise of the popularity of online gaming services, however, it may soon make sound economical sense for corporations to start paying salaries to people like this. There are already undoubtedly moles inside of corporations that put out games, so why shouldn't they realize the effectiveness of this tactic and put their own muscle behind it?

Of course, the way the United States' laws are headed, these computer cracking activities might constitute terrorism, so be careful what you do :-p



It's not much fun at the top. I envy the common people, their hearty meals and Bruce Springsteen and voting. --SIGNOR SPAGHETTI
An Approach To Game Compromise | 83 comments (55 topical, 28 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!