Monthly Archive: February 2016

I was in graduate school (for the second time) when Alan Sokal pulled off his controversial hoax.  The fame it generated and the shame it heap upon the postmodern academic movement flared up for a brief time.  Unfortunately, based on a recent article by Peter Dreier, it seems that any lessons learned from it were lost of many academics. Fortunately it made a lasting impression on me.

For those who aren’t familiar, Sokal, a physicist at NYU specializing in quantum field theory and quantization of gravity, wrote an article for the social studies magazine Social Text, an academic journal that prided itself on being a champion of postmodern thinking.  In his article, entitled Transgressing the Boundaries: Towards a Transformative Hermeneutics of Quantum Gravity, Sokal attacks the very basis of the Western scientific method. His opening paragraphs read

and

For those who don’t have the stomach to wade through that gibberish (let alone what followed), what Sokal is trying to say is that scientific principles and results depend upon the culture and class from which one comes. He backs up this assertion by blurring the meaning of the Copenhagen interpretation of quantum mechanics into saying that the essential role of observer brings a social or cultural aspect to all science.

After the publication of this ridiculous nonsense, Sokal publicly announced that his article was a hoax. His aim in perpetrating this hoax was to demonstrate both the lack of rigor in certain academic circles and the clear introduction of bias if the writing appealed to the editorial slant of the journal. In his own words, Sokal said that he undertook this bit of hokum in order to see if a leading journal of cultural studies would

An example of these very preconceptions is on display in the discussion where Sokal cites Madsen and Maden who, according to the article, have two criteria for distinguishing between modernist and postmodernist science. Their criteria for postmodern science are:

1. it be free from any dependence on the concept of objective truth
2. it be constructed from those theoretical elements which are essential for the consistency and utility of the theory.

Earlier this week, Peter Dreier came clean about a similar hoax he had pulled-off in 2010. In his article entitled Confessing my sins and exposing my academic hoax, Dreier describes writing a sham abstract for a social studies panel on the “Absence of Absences”. In his narrative, he talks about how he wanted to see if he could write pure gibberish and still get it accepted to an academic conference. About the abstract that got him an invitation to the conference being held in Tokyo, Dreier says

After describing his flirtation with obfuscation, Dreier goes on to show that the desire by certain academics to indulge in abuses against the language is, by no means, limited to his little jaunt. He cites several cases of overly complicated postmodern phrasing which desperately tries to mask silly ideas with “academic pomposity”. In one particularly biting paragraph, he says

I applaud both Sokal and Dreier for making a vivid point about what sometimes passes for academic thinking in institutions of higher education but I can’t help but feel that they miss a bigger point. In both of their critiques, the notion of postmodern thinking is held up as an object of ridicule. But pointing out the ‘silliness’ of the postmodern logic isn’t enough. Sokal actually comes fairly close (whether accidentally or intentionally I don’t know) to what I am advocating in his treatment of Madsen and Madsen’s criteria for a science to be regarded as postmodern. Sokals passage shows, without explicitly stating so, the inherent contradictions of postmodern thought.

Briefly summarized, postmodern points-of-view use objective truths and logical tools built upon them, to try to prove the lack of objective truths. Each of the arguments rests firmly upon the unspoken and unrecognized assumptions that words mean something, that conclusions have a decidable truth value, that arguments supporting these conclusions can be logically derived, and that the argument put forth is objective – that is to say anyone of any culture will agree with the conclusions.

So how can postmodernism logically argue against logic? It can’t. It just isn’t consistent – and that is the real lesson of these hoaxes.

Several months ago, I wrote about the proof, due to Richard Kaye of Birmingham University in 2000, that the seemingly innocent-looking game Minesweeper is an example of an NP-Complete problem.  The essence being that no algorithm for solving the problem is known that scales as a polynomial function of the board size.

I suppose that it was inevitable that analysis of this sort would be extended to a host of other games.  After all, most computer scientists no doubt enjoy gaming as much as they enjoy computers.  In addition, unless there is some odd aspect of computer-scientist biology, each of them was once a child and, undoubtedly, was captivated by play.  But it was with a particular satisfaction that, after aimlessly wandering across the internet, I discovered the charming paper entitled Classic Nintendo Games are (Computationally) Hard.

This paper, written by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta, is an exploration of five of the classic 8-bit Nintendo franchises:  Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon.  Using an approach much like what Kaye used in his analysis, Aloupis et al examine the generalized form of each of these games.  A generalized form means that the size and structure of an individual board is open to manipulation but that the basic rules of the game are not altered.  Rooms take on arbitrary sizes and configurations and the number of non-playing characters (NPCs) can be unlimited.  Other than these liberties, the underlying mechanics of the game is maintained.

Now, I will confess that I never sunk much time into Donkey Kong, Legend of Zelda, or Metroid (much to my regret) and that I had only a passing flirtation with the Mario franchise, but Pokémon is a different story.  I’ve spent countless hours with that franchise and don’t regret a minute of it.  So, I thought I would discuss a little of how Pokémon can be thought of as NP-hard.

The first and most primitive notion is what Aloupis et al call the ‘decision problem of reachability’.  This is a rather big and forbidding name for a basic problem that almost every gamer has asked himself during gameplay:  ‘Given where I am and my current status can I reach that spot there?’  This is a particularly familiar problem in such large and open worlds like Elder Scrolls V: Skyrim.

The image below is an actual screenshot from Skyrim, where a player encounters a dragon on a mountaintop.  Because this meeting is essential to the storyline, the game limits access to the summit until the player has completed certain changes in status (i.e., solved a number of puzzles or quests, etc.).  Of course, the player doesn’t know this when the game commences and often the question as to whether the player can find a way up to the summit is left undecided until the plot advances to the point where the way becomes clear.  The mountains that appear in the distance remain undecided for many players throughout their interaction in the game.  They don’t figure in the plot and their accessibility is unknown unless the player manages to reach the peak.  In absence of such a feat, the player has to conclude the answer as ‘maybe’ – thus showing how art imitates real life.  I am sure that even the developers are not sure what answer to give.

Fortunately, the Pokémon games, being 2-dimensional worlds, are much simpler.  But not so simple that the paper by Aloupis et al is a trivial read.  In fact, I found it to be quite difficult in the sense that the framework being used is familiar only to the specialist and I have neither the time nor the inclination to get completely up to speed.

Instead, I would like to convey the flavor of it in terms of a Pokémon player.  The general idea about ‘decision problem of reachability’ is captured in the game mechanic familiar to anyone who has ever played Pokémon, the NPC enemy trainers.

For those of you who are unfamiliar or who simply want me to define my terms carefully, here is a quick summary.  In Pokémon, the player takes on the role of a young trainer who has in his possession between 1 and 6 pocket monsters.  His goal is to level up his Pokémon primarily through engaging in battles with other Pokémon either wild or in the possession of other trainers.  As the player roams the world, he encounters other trainers who, if the conditions are right, challenge the player to a battle.

Each enemy trainer possesses a set location, a direction in which he faces, and a line-of-sight. There are two ways to trigger a battle with an enemy trainer.  First, the player can ‘sneak up’ on the enemy trainer by moving next to him without entering his line-of-sight.  Talking to the enemy trainer initiates the battle but leaves the NPC in its set location.  Second, the player can walk through the enemy trainer’s line-of-sight.  The moment the player enters a space within the line-of-sight his motion is stopped and the enemy trainer moves from his set location to challenge the player.  Alternatively, a player may choose to avoid the enemy trainer by either avoiding talking to the NPC or not entering his line-of-sight.  This latter option is not always available.

Depending on which choice the player makes, certain areas in the game become accessible or inaccessible as the NPCs move to open or block certain spaces.  This behavior, when generalized, is at the heart of the proof by Aloupis et al.

The basic structure of their analysis is the creation of certain playable scenarios, called gadgets.  There are 6 gadgets that they use to prove NP-hardness: Start, Finish, Variable, Clause, Check, and Crossover.  The precise nature of these gadgets is involved, so I’ll only touch the Variable gadget as it is easy to understand.

The Variable gadget’s purpose is to provide the player with a single choice that flips a switch between two positions.  The construction Aloupis et al provide is

The red rectangle indicates the line-of-sight of the enemy trainer and the set location of the trainer is (2,4) (2^nd row, 4^th column from the upper left – denoted by the caricature of a man with glasses in a lab coat).  A player entering at a has two choices.  First, the player may choose to sneak up on the enemy by taking the top fork and beating him in battle, thus leaving the exit at c open.  Second, the player may choose to take the bottom fork, forcing the enemy to come down to (3,4) to battle.  Winning the battle then leaves the exit at b open.

The other 5 gadgets are constructed with similar elements and mechanics but often they are larger and more complicated to understand.  And the details are not all that important unless one wants to understand the technical details.  Rather, the basic message is that even cloaked behind the guise of a game, even ones as fun as the five famous Nintendo franchises analyzed, logic and decidability are all around us.