and a long-suffering manuscript I have been trying to get into publication with some collaborators [1]. With reference to the former:
Let's begin by highlighting a 2-bit game. Two examples of a 2-bit game (in terms of control) are
Pong and
Breakout. In both games, the player uses a single controller to move a virtual paddle back and forth across the screen [2].
A screenshot of Pong (left) and Breakout (right) and the degrees of freedom per player. Each degree of freedom (movement along the right-left axis) represents 2 bits of information.
Now let's discuss the mention of
Joust as an example of 3-bit control and
Pac-Man as an example of 4-bit control. For uninitiated readers, here are screen shots from the game (click to enlarge)
And here is a picture
of the Joust arcade console and its 3 bit control mechanism.
The
Joust joystick provides 2 bits of control (left on/off and right on/off), and the button is 1-bit of control (press or no press). This is sufficient complexity to control the action, but not enough complexity to account for all observed action in the game.
Pac-Man utilizes a maze rather than linear action, but has only one additional degree of control complexity. Here are some screenshots from the game (click to enlarge)
In terms of control complexity, Pac-Man is a 4-bit game (2 degrees of freedom), while the Atari 2600 controller can provide up to 5 bits of information (2 degrees of freedom and a button). These are arbitrary assessments of information content, and do not correspond with every possible degree of freedom in the game environment.
Examples of 4- and 5-bit control via joystick for a version of
Pac-Man (left) and the
Atari 2600 (right).
There are two additional sources of complexity we should be concerned with: the
combinatorial complexity of objects within the game, and
perceptual complexity of human information processing during gameplay. The former can be characterized by computational complexity classes, while the latter can be characterized in conjunction with control complexity in the form of information bandwidth (measured in
bits or
bits per second).
A taxonomy of computational classes for Pac-Man and other games is described by [3-5]. While Pac-Man is considered an NP-hard game, not all video games are. Furthermore, games that are in the same computational class do not have the same types of objectives or in-game properties. The games Tetris [6] and Minesweeper [7] have been found to be NP-complete. This is likely based on the combinatorial properties of each game.
According to Aloupis et.al [8,9], Super Mario Brothers can be classified as NP-hard. Other Nintendo games, such as Donkey Kong Country, are PSPACE complete. The Nintendo examples are interesting from an approximation perspective, as several Nintendo games have been reclassified by this research group between 2012 and 2016 [8,10].
The criterion are based on things like how the avatar moves within the game's activities. A game like Pac-Man involves so-called "location traversal" [4], which in computational terms is similar to the travelling salesman problem (NP-hard) [3]. By contrast, a game like Breakout involves a balancing maneuver [see 2] that is solvable in LSPACE.
Video game screenshots and computational complexity for several example games. Clockwise from top: Super Mario Brothers (NP), Donkey Kong Country (PSPACE), Breakout (LSPACE), Minesweeper (NP), Tetris (NP), Pac-Man (NP).
Human information processing (or performance) can be characterized in the form of informational complexity. One classic way to assess complexity in performance is the use of psychometric laws [11]. Invariants relevant to video game performance are
Fitts Law (hand-eye coordination), the
Weber-Fechner Law (
just noticable differences in stimulus intensity), and
Stevens Law (the perception of physical stimuli relative to intensity). In the case of Fitts Law, the
index of difficulty is often expressed as a function of bandwidth (bits/second). This provides a real-time expression of complexity that can be compared across games. Similarly, the presence of signal relative to noise can be expressed in terms of information content (
Shannon-Hartley theorem). The stimulus information available to the game player may or may not be congruent with control complexity and in-game combinatorial complexity [12]. Accounting for all three dimensions of this complexity is an avenue for further study.
NOTES:
[6] Demaine, E.D., Hohenberger, S., and Liben-Nowell, D. (2003).
Tetris is hard, even to approximate.
Proceedings of the International Computing and Combinatorics Conference, 351–363.
[10] Aloupis, G., Demaine, E.D., Guo, A., Viglietta, G. (2012).
Classic Nintendo Games are (Computationally) Hard.
arXiv, 1203.1895.
[11] One challenge in linking psychophysical complexity to video game perception is in capturing the entirely of what is cognitively extracted from the game environment.
For an example of a purely psychophysical aproach to game design, please see: Hussain, Z., Astle, A.T., Webb, B.S., and McGraw, P.V. (2014).
The challenges of developing a contrast-based video game for treatment of amblyopia. Frontiers in Psychology, 5, 1210. doi:10.3389/fpsyg.2014.01210
