Wolfram|Alpha: Systematic knowledge, immediately computable.

Showing posts with label Games. Show all posts
Showing posts with label Games. Show all posts

Wednesday, October 27, 2010

Schannel Event 36888 ( 10 / 10 ) When Playing BFBC2 / MOH / Etc. - WTF?

Since the beta of EA/DICE's Battlefield Bad Company 2, forums have had a myriad of posts with game problems, with this symptom included in the posts. Since retail release of the game, and the subsequent release of Medal of Honor by the same publisher/developer teams, the same has been seen for the latter game.

Specifically, the event log entry in the windows system log is:

Event 36888, Schannel
The following fatal alert was generated: 10. The internal error state is 10.

When I first saw the error myself, I recognized it from my network programming days as an informational error, indicating some kind of barf-o-rama on the server side of  a secure connection handshake. Unlike most of the other Schannel event IDs, this particular one seems to remain undocumented. Nonetheless, the Info opcode and 10 / 10 Alert Description and Error State hint strongly at it being server side.

Since it seemed to have no material effect on the playability of the game(s), my interest in investigating it stopped there. A recent poster, however, indicated that disabling their AV (Trend) caused the apparently related game issues to be remedied. While it appears that the game itself runs correcly despite encountering the Schannel error, it may be that some A/V that muck with everything on the wire might take drastic action in the face of it. Strange if some do, but plausible.

In any case, barring some other application / utility causing problems (e.g., said A/V), the error itself can be safely ignored. If it really bothers you, you can change the logging level via a registry change by modifying (or adding if needed) the key:

HKEY_LOCAL_MACHINE\System\CurrentControlSet\Control\SecurityProviders\SCHANNEL

DWORD value EventLogging with a value of 0 will eliminate such event log messages. Note that current versions of windows seem to be more voluble for these errors - on older (e.g. XP), the error may occur without a log entry being generated.

I became interested again in this event / error recently while tracing the traffic activity of the game debugging a separate issue. Both games are built on the same engine / network infrastructure, so it is not surprising they share the same frailties.

From an outsider's view (since I have no access to the game source code, nor the EA master or game servers, my view must be the result of probing and testing theories, using debuggers and traffic sniffers), the network infrastructure for these games is a bit of a wreck. In the same way one might surmise their neighbor is a slob from observations of the trash bags thrown on their front lawn, the mishmash of connections and traffic these games generate is appalling. The possibilities of problems due to one piece failing or being unavailable are surely a source of grief for many attempting to play these games online.

If this system was designed this way from scratch, someone should be publicly whipped with a length Ethernet cable. If it is the result of 'evolution' of features and functionality by adding servers to the 'master' pool, the time has come perhaps for EA to rethink the infrastructure and rebuild it from scratch.

In any case, the Schannel error in these games appears to be generated by an improperly configured EA server that provides them with hardware information à la Steam's hardware survey.

Another way to eliminate the error (and stop spying by EA, if that's your stance), is to add the following to the file \windows\system32\drivers\etc\hosts:

127.0.0.1        bf1943hwtelemetry.ea.com

This prevents the game(s) from even starting the handshake process, short-circuiting the error path.

In summary: The error is harmless, it is not the cause of crashes / etc. in the game itself per se though it appears it might throw programs such as A/V into a tizzy (when I feel like it, I may investigate this further.) You can just ignore it, or if it bothers you having it in your event log, take one or both of the steps outlined above.



Wednesday, May 19, 2010

Nim Chimpsky Plays A Game: A Simple Game Played With Simple Recursion

Nim Chimpsky, named as a pun of Noam Chomsky the brilliant linguist, cognitive scientist and philosopher, was a chimpanzee that researcher Herbert S. Terrace of Columbia University claimed had learned a form of sign language and was able to communicate intelligently. Whether or not this was in fact true is still hotly debated in the research community.

If one believes that Nim had the intelligence to learn and use language, one might think the chimp could play one of the simplest of children's games, also called Nim. The game of Nim is a game of extensive form and perfect information that comes in many flavors. We will be using perhaps the simplest form, often called the subtraction game. This version consists of  two players starting with a number (usually represented as a pile of objects like coins or pebbles), where each player in turn removes one, two, or three objects. The player to take the last object is the loser.

It can be trivially shown that such a game reduces to a player avoiding being left with n 1 (mod 4) objects, in other words, a player should try to remove enough objects to leave the opponent with 1 (mod 4) objects. In the usual game, where the moves are limited to {1,2,3...m), this becomes 1 (mod m+1), i.e., if a player can take one to six objects in a turn, they want to leave the opponent with 1 (mod 7) objects. If a player finds themselves in such a position already, they cannot move to a winning position, and the usual strategy is to remove only one object in the hope that the more objects that remain, the more likely the opponent will make a mistake.

When she was a toddler, the game amused my daughter. It didn't take long for her to figure out the strategy however, and then it became boring. I came up with a variation that I called "Nim with holes". In this variation, instead of the moves being the positive integers with some upper limit, the moves can be any member of some set X of positive integers agreed upon by the players. So a game might start off with a pile of objects of size fifty, with "legal" moves being the removal of say n{2,4,7,9} objects. Or perhaps "Prime Nim" where the moves are limited to n∈{2,3,5,7,11}. The "holes" version of the game can be analyzed in a similar fashion to the original, the closed form strategy is left as an exercise for the reader.

Instead, let's look at solving the problem using a simple recursive program. Common in the functional programming style (and usually preferred over imperative/iterative methods for this style of programming), a recursive program (or routine or function) is one that references itself in its body.

For example, a simple function to calculate the factorial of a number n, usually denoted as n! and equal to the product of all positive integers less than or equal to n could be written in the iterative and functional styles (using c for this example) as:


Factorial function in C language, written in iterative style (left) and functional style (right).

As can be seen, the iterative version of the function "iterates", or steps incrementally, toward the goal, starting with a value of one for the variable fact and stepping through each integer and multiplying the value of fact by that integer, until the integer of n, the input value has been reached. The functional style, on the other hand, does away with the need for any intermediate variable. Instead, it "winds up" to the return value by taking the input value n and multiplying it by the value of the factorial function of n-1. In a recursive style of programing, the "stop" or "base case" must be defined to allow the "unwinding" of the recursion. In our example, we see that when the factorial function is passed a value less than or equal to one, it simply returns 1. This returned value is used in the multiplication by the caller, and so on back up the recursion chain until the final, initial caller returns the ultimate result.
 
The same factorial function, written using Scheme, would have the following form:
 
(define factorial (lambda (n) (if (= n 1) 1 (* n (factorial (- n 1))))))
 
Recursion can be a difficult concept to get one's head around initially, especially for non-programmers (and even some programmers!) An excellent introduction to the thought process can be found in Thinking Recursively by Eric Roberts. A deeper examination can be had in the landmark book by Douglas Hofstadter titled Godel, Escher, Bach: An Eternal Golden Braid. Anyone interested in recursion should have these books on their shelves. They are certainly must-haves for any self-respecting programmer.
 
We can see how solving our game of "Nim with holes" lends itself to a recursive solution by thinking about the possible plays going backwards, that is, starting with a losing position. Let's consider a game of "Nim with holes" where the players have agreed the legal moves must belong to the set {2,3,5}. We immediately see that a player finding themselves with one or two objects is in a losing position, and a player finding themselves with 3,4,5,6, or 7 objects can leave their opponent in that losing position. As we move away from the goal, reversing the possible game play steps, we would find that having eight or nine objects, or fifteen or sixteen are "losing positions", that is, the player faced with these cannot remove a number of objects that allows them to leave their opponent with a losing position, nor leave a position where the opponent cannot leave them the next losing position closer to the end game.
 
With a simple set of legal moves, this is easy to do in one's head. As the set of legal moves becomes more complex, the difficulty in determining winning and losing positions in the game becomes more difficult. Algorithmically it is trivial, and using a recursive and functional style of programming, elegant.
 
We want to build a simple function that can take the game state (the number of objects) and the set of legal moves as its arguments, and return "True" if we've won already, "False" if we're in a losing position (meaning we'll just move the minimum allowed), and the position we need to move to (if we can) that will put our opponent in a losing position (that we can then maintain for the rest of the game: once there, perfect play means the opponent is ultimately doomed.)
 
A trivial realization of this using Scheme is shown below.
 
"Nim with holes" move analysis function written in Scheme with example results (click to enlarge).
 
The winning position (winpos) function takes the game's current state (number of objects left) and a list of the legal moves. If we've already won (no objects left) #t (true) is returned. Otherwise, for each move in the legal move list (using the map function in Scheme), the function tests if any of the reachable positions are a losing move by testing each of them for the ability to reach a losing position, by testing each of them...until it winds recursively down to the base case: we have won. If the recursion is able to reach this state, when it is "unwound", the final result is the first position presently reachable that can lead us to the ultimate winning position. If the recursion results in not being able to reach the ultimate winning position, it returns #f (false) indicating we a presently in a losing position, and should take the minimum allowed move.

The operation of this recursion can perhaps be most simply imagined by first thinking about the game in what surely must be the simplest case: the only legal move is to take one object. Clearly, the winning positions alternate, with all odd numbers of objects being a losing position, and all even numbers being the winning positions. Pick some position, say five objects. The function tests for zero, which fails, resulting in the function calling itself for a value of four objects, which goes through the same sequence to call itself for three objects...until we arrive at the call to itself for zero objects.

This is our "base case", where the function returns #t (true). As this return is "unwound" or "percolated" back to the original first caller, note that it will have the logical not applied for each return for each nested call. This is where in our function the move positions are alternated between player and opponent: what is a winning position for a player is a losing position for their opponent and vice versa. In our example case, we  are in effect seeing the result of not(not(not(not(not(#t))))), resulting in #f (false), meaning our position of 5 objects is unfortunately a losing position in the case of the only legal move being removal of one object.
 
We can see in the lower part of the IDE the results from asking the function to evaluate a game state of 17 objects with legal moves of 2,3 or 5. The result indicates taking 2 objects and leaving 15 will put us in the winning position. The second example uses a simple map to map the winpos function onto a list of possible game states from 0 to 19 using 2,3 and 5 as the legal moves. The result is the list of results from the winpos function.
 
Readers can download the excellent (and free) Dr. Scheme environment from PLT Scheme should they want to experiment with Scheme, functional programming and recursion. The site has excellent tutorial materials and references for those interested in learning the details of this superb Lisp dialect.The trivial game solving function example (which can of course be extended to any similarly solvable game) can be found at NimWithHoles.scm.

Thursday, May 13, 2010

I've Got A Stalker: S.T.A.L.K.E.R. Shadow of Chernobyl, that is.


S.T.A.L.K.E.R.: Scavenger, Trespasser, Adventurer, Loner, Killer, Explorer, Robber.

Sounds like my neighbor. I remember sometime in 2004, after an all night gaming session on the classic Far Cry in my LAN room, one of my gaming buddies turned to me and asked if I'd seen the web site for an upcoming game, S.T.A.L.K.E.R.: Shadow of Chernobyl. I hadn't, so we took a look.

I was blown away by the description and the screen shots shown, the graphics looked amazing compared to any shooter we'd played up to that time. The rumored release of the game was soon, so the juices started flowing for what looked to be a most excellent addition to the game collection.

Unfortunately, the game faced delay after delay, eventually resulting in a ninth place finish in Wired's Vaporware '06 contest. In January 2007, a contest for players to experience the game beta in a marathon session collapsed when the THQ staff (publishers of the game) that had organized the event were themselves unable to obtain copies of the game.

The game finally made its public debut at the end of March, 2007.

The game is played in an area known as the Zone, based on the Exclusion Zone around the area of the Chernobyl Disaster, with story components borrowed from the novel Roadside Picnic. In the game, a second disaster occurs twenty years later, leading to mutations, anomalies, and the associated valuable artifacts, prime scavenging material for the game characters.

This was the first game I'd ever played that had any kind of real "scavenger" aspect, that is, the "gatherer" part of "hunter-gatherer". This aspect of the game is in fact central to game play. The character you play (I'll not reveal details, as that would be a plot spoiler) starts the game basically buck naked as far as weaponry and protective clothing.

By fulfilling mission requests provided by all sorts of NPC in the game and by obtaining or otherwise finding valuables in the game, the player builds a stock of goods that can be sold or traded for items such as food, weaponry, clothing, ammunition, artifacts, etc.

The artifacts in the game play a key role in trading and player protection:

"As a result of the second Chernobyl disaster, The Zone is littered with small areas of altered physics, known as anomalies. There are several different variations, each one having a unique impact upon those who cross its path. They can be potentially deadly to the player and other NPCs, delivering electric shocks, or pulling them into the air and crushing them.

Most anomalies produce visible air or light distortions and their extent can be determined by throwing bolts (of which the player carries an infinite supply) to trigger them. Some stalkers also possess an anomaly detector, which emits warning beeps of a varying frequency depending on their proximity to an anomaly. The guide in the film Stalker, and his predecessors in the Strugatsky brothers' book Roadside Picnic, test various routes before proceeding. In the film, metal nuts tied with strips of cloth are used.

Anomalies produce Artifacts, the valuable scientific curiosities that make the Zone worth exploring monetarily. As well as being traded for money, a number of Artifacts can be worn so that they provide certain benefits and detriments (for example, increasing a stalker's resistance to gunfire while also contaminating him with small amounts of radiation). Artifacts are found scattered throughout the Zone, often near clusters of anomalies."

At first, I found this aspect of the game boring and time consuming. Little did I know I would soon become addicted to the hunt, particularly for the more rare items. I soon came to appreciate this type of game play, common in the MMORPG games such as World of Warcraft that I'd poked fun at.

Game play covers a huge area of many square miles. Originally, the game was to be completely open, but by release, the map had been subdivided into eighteen areas, each reachable through specific passages. Nonetheless, the game play always feels expansive, with superb draw distances.

The ultimate goal of the player is to reach the Chernobyl reactor itself, to reach the most curious of all of the strange items in the game. The actual end game depends on how the player has progressed through the game.

This, combined with the wide range of choices in interactions and missions (Who do I want to befriend? Who do I decide to trade with? What items do I want for my character?) leads to excellent replay value in the game.

The game is based in the in-house developed X-Ray graphics rendering engine. From the Wikipedia entry:

"The X-ray Engine is a DirectX 8.1/9 Shader Model 3.0 graphics engine. Up to a million polygons can be on-screen at any one time. The engine features HDR rendering, parallax and normal mapping, soft shadows, motion blur, widescreen support, weather effects and day/night cycles. As with other engines that use deferred shading, the X-ray Engine does not support anti-aliasing with dynamic lighting enabled. However, a "fake" form of anti-aliasing can be enabled with the static lighting option; this format utilizes a technique to blur the image to give the false impression of anti-aliasing."

Even in 2010, the graphics hold up well, especially on high-end machines.

The A.I. system was also built in-house. The "ALife" system originally was to have NPC constantly active in the game world, regardless of player interaction. By release, this had been reduced in functionality. Nonetheless, the capabilities are quite robust, as described in the Wikipedia entry:

"GSC Game World's proprietary ALife artificial intelligence engine. ALife supports more than one thousand characters inhabiting the Zone. These characters are non-scripted, meaning that AI life can be developed even when not in contact with the player.

The NPCs have a full life cycle (task accomplishment, combat, rest, feeding and sleep) and the same applies to the many monsters living in the Zone (hunting, attacking stalkers and other monsters, resting, eating, sleeping). These monsters migrate in large groups. The non-scripted nature of the characters means that there are an unlimited number of random quests. For instance, rescuing stalkers from danger, destroying stalker renegades, protecting or attacking stalker camps or searching for treasure. The AI characters travel around the entire zone as they see fit.

Numerous tactics can be employed to complete the game, such as rushing or using stealth and sniping. The NPCs will react in a different way to each of them. S.T.A.L.K.E.R.'s NPCs plan ahead by "Goal-Oriented Action Planning" to achieve this."
 
S.T.A.L.K.E.R. uses a modified version of the ODE physics engine to provide rag doll physics and accurate bullet ballistics: Bullets are affected by gravity and ricochet off of surfaces.
 
Adding to the realism is a completely dynamic day / night progression of time, including weather effects such as rain, lightning, showers and sunlight.
 
An eerie soundtrack completes the palette of game play. This was the first and only game I've played that had parts that really got the creep-o-meeter rising for me. There were many moments exploring the bowels of some haunted deserted underground laboratory where the anticipation of terror had my pulse rising.
 
Even at an age nearing four years, still a most worthwhile game, both for FPS fans and RPG players. That it is now available on Valve's excellent Steam system for under $20.00 makes this a no-brainer if you have not already played it. Since the version is the latest patch, most of the niggling bugs that were in the initial release have been remedied.

The follow-up games from the same developer, S.T.A.L.K.E.R.: Clear Sky released in September 2008 for North America, and S.T.A.L.K.E.R.: Call of Pripyat released in February 2010 fail to capture the magic of the original in my opinion. The former was an unmitigated disaster, bug ridden and having none of the flavor that made the original so engaging. The latter returned to more of the game play mechanics of its progenitor, and is arguably the least bug plagued of the three. Recommended for players that loved the original, but for others only if it can be had at a bargain price.

All three games in the series have an active "modding" community, providing new maps, characters, game and character abilities, and modifications of difficulty levels. This adds considerably to the game play value and longevity of the game.

Like many things in life, this is a case where the original is the best.
 
Highly recommended, grade A material.

Monday, May 10, 2010

An Alien Message?


This just may be the ultimate 'tweetable program' that does something interesting. I first saw this kind of conciseness in a pamphlet sized book back in the seventies that highlighted the efficiency of the language used, APL (A Programming Language). The author had taken the winning code from a programming contest, where conciseness and correctness were highly scored, and adapted it to APL. One line to do the classic brain teaser puzzle Instant Insanity.

If I recall correctly, the original code was either in C (fairly new at the time) or BASIC (some pretty powerful versions existed even then), and the winning code was something like eighty lines of actual code (not counting the required comments for the contest.)

The particular piece of code heading this entry produces the generations of the board for Conway's Game of Life.

The game is 'played' algorithmically, by applying simple rules to an initial matrix of 'creatures' set up to the player's desired configuration:
  •  Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
  • Any live cell with more than three live neighbours dies, as if by overcrowding.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any dead cell with exactly three live neighbours becomes a live cell.
The complexity of the patterns that result, and the 'behaviors' that appear can be mind boggling. One pattern might result in every cell quickly dying. Another could result in fantastic evolutions of patterns and shapes. Some patterns produce 'gliders' that crawl their way across the matrix. Some even birth copies of themselves (none have been seen yet, but the proof of such patterns in the game is available in Winning Ways for your Mathematical Plays by Berlekamp, Conway and Guy).

The list of possible patterns is endless, as are the results they generate, and aficionados of the game actually host contests where players supply initial patterns that 'fight' each other until a winner is decided.

An example of a pattern known as a 'gun', that produces 'gliders' is seen in the animation below:



You can view other more complex patterns, including some that do useful work, at the video link at the end of this article.

The game is perhaps the first widely known example of a cellular automaton, and exhibits Turing completeness, that is, the game is sufficient to simulate the Universal Turing machine. This means a sufficiently complex initial game board, given a sufficient time span, can perform the same 'program' as a computer with infinite memory and no time constraints. If that doesn't startle you, it's time to fill up your coffee mug!

All of this complexity captured in one line of APL code.

Take a moment to absorb these two morsels you've been handed. In one line of APL, we have the Game of Life. In the Game of Life, we have a Universal Turing Machine. That one line of APL could conceptually (given no constraints on memory or time) run any program you could possibly write, or even imagine. Any program that could ever be written. What an amazingly concise language!

I quickly fell in love with APL, particularly because of my mathematical bent, which the language is ideally suited for. I suffered many a time from the denseness of the language though. A running joke of the time was that the language was 'write once, read never', capturing the difficulties that the author of particularly terse APL might have deciphering their own code when returning to it after some time.

The language uses a family of special characters to represent various monadic (taking the result of everything to the right of the symbol as the argument) and dyadic (accepting an additional argument, the first data to the left of the symbol) functions. It is in fact based on a mathematical notation developed by Kenneth Iverson for array manipulation that he used with his students at Harvard University.

In some cases, functions are represented by overstrikes, that is, literally typing a symbol and then typing another symbol over the original. The use of this depended on the system involved, and in general the same functionality could be accomplished without needing overstrikes. There are also versions of APL that provide special character input using combinations of standard characters via input method editors to represent the symbols.

The concise use of functions applied using the language's simple recursive precedence rules (the right argument of a function is the result of the entire expression set to the function's right) and the incredibly high level of abstraction possible makes for ridiculously rapid, interactive and iterative solutions to even the most fiendishly complex problems.

Functional programming before functional programming was cool.

Soon after I learned the language, this beauty came along:


Oh Man! This was a computer lover's dream machine. Arguably the first 'portable' computer (at over 53 pounds wet), the IBM 5100 represented a giant leap in movable computing power.

Fully equipped with a whopping 64KB of memory and tape drive, with BASIC and APL programming languages (selected by flipping a toggle switch on the front panel), and a giant 5" CRT  display of 16 lines of 64 characters each, it cost about $20,000.00 in the mid seventies. That's roughly $80,000.00 in today's dollars.

A sophisticated digital wristwatch likely has more processing power today, and certainly most smart phones would leave the 5100 in their dust. I still lust after one!

I found one some time ago that had been uncovered in a garage. Perfect condition. With all the trimmings, including the rare external tape unit and printer. The last example I'd seen sold for somewhere north of $15,000.00, and it was in only fair shape, with only BASIC on no peripherals. I called the seller, and he indeed still had the unit. The price? Under $2,000.00. He'd had no calls (no surprise to me: the ad he placed was in a place no one would possibly look for one of these.)

I didn't have the heart. Or the lack of one, I suppose. I pondered it for a day, then called the seller and filled them in on the rising collectible value of these units. My feeling was his unit, as perfect as it was, belonged in a museum. I'm sure he thought I was nuts for spilling the beans. I felt good about it. After weeping...

Enough already with the trip down memory lane! Back to the subject at hand: APL. Functional programming in the seventies. Preceded only by Lisp.

The more things change, the more they stay the same!

You can watch an expert APL user building the game of life from scratch in the video below. Fascinating and frankly still jaw dropping to me after all this time.




In addition, an interesting five minute video that shows many different initial starting patterns and their results including one where prime numbers are part of the resulting behavior can be seen at Amazing Game of Life Demo on YouTube.

If you want to experiment with the game and try your own patterns, the open source, cross platform implementation of the game in Golly is superb. Golly also provides a large library of already built patterns ranging from simple to complex, amusing to beautiful, and useless to startlingly capable.

Saturday, May 8, 2010

Spies Like Us.

I'll be participating in another Bash webcast tomorrow. The subject is the increasingly cryptic goings on at GKNOVA6, the viral marketing website that appears to be related to the upcoming release of Treyarch's Call of Duty series, Black Ops. You can see the progress evolve by taking a look at GKNOVA6 at the Call of Duty Wiki.

Clever sleuthing by interested gamers around the world has led to the analysis and decipherment of a host of messages, including some craftily hidden steganographic text (see my blog entry Steganography, GKNOVA6 Style for the first example and details on how this can be done).

I've been invited to participate with Jock the host and his guests Josh Peckler from planetcallofduty.com and Carbonfibah, one of the seven recipients of the mystery packages with the USB keys that started the whole ball rolling and a major contributor to the code breaking efforts. Having a background in cryptography and secure systems, I hope to add some value talking about the various methods seen as this has unfolded, and the techniques applied to extract the results. We'll also be discussing the evidence pointing to this being a campaign from the minds of Treyarch.

This is the second recent instance of some very clever marketing by game developers: a few months ago, the popular game Portal from Valve Software had an update. The only material change seemed to be more of the cute portable radios were to be found throughout the game. What soon unfolded, however, is that each new radio had some kind of message. Some were normal sounding transmissions, a few were Morse code, some sounded peculiar, almost like an old FAX machine (turned out to be Slow Scan TV signals, a technique used by HAM radio operators), yet other radios only gave up their secrets when brought to just the right place in the game.

Careful ratiocination by followers of the game led to the decipherment of the various messages, which led them to a web site, done in an old-school bulletin board style, that when logged into led the user to Aperture Science Laboratories. Portal 2, anyone?

Stay tuned for updates on the webcast, I'll update this entry when it goes live! I can't tell you anything more about the details at this time.

"We could tell you, but then we'd have to kill you." - Dr. No

Update 05/09/2010: Had a blast, again, with Jockyitch and his cohorts on the BASH cast. Learned much from Josh and Carbonfibah about the evolution of the messages from GKNOVA6, and how the swarms of gamers worldwide went about deciphering them. Look for the cast at BashandSlash soon!

Update 05/10/2010: Webcast / Podcast is live, here!

647 Grains of Diplomacy: When you care enough to send the very best.

Sniping. Snipers. Often the most despised activities and roles in online FPS games. Myself, I seldom play the role: I find it rather boring. In games like Battlefield: Bad Company 2 it is so easy to get frags as a sniper while remaining basically untouchable, a trained monkey could do it. Not my style.

That said, a few years back, having played all of the FPS games that interested me until my fingerprints had worn off and facing a dearth of new FPS games, I came across an unopened copy of a game I'd not heard of at a local discount bookstore. The game was called Sniper Elite. For nine bucks I figured what the heck, even if it's a dog of a game it would be something new to play. Much to my surprise, I quickly became a fan of the game. The well modeled bullet ballistics and challenging single player missions kept me amused for some time, highlighted with the slow motion bullet's-eye view of a 1000+ meter head shot.

The online play was equally rewarding, and made me appreciate the tactics and strategy involved in the hide-and-seek game of sniping. For those that appreciate this kind of play, it is the best of the genre. The game still has a small but fiercely loyal following. At times, copies of the game were selling for over $100.00 on eBay. Recently, the game has become available on the most excellent Steam system of Valve Software. It's ten bucks. If you even have the slightest inkling you might enjoy a sniping game, it's well worth this meager price. You too might become addicted! For certain, you will either love it or hate it - I've not seen a reaction between these extremes yet. Be forewarned: the graphics are a bit dated (they were when the game was released), and the controls can take some getting used to, but it really is a great game.

Sadly, once I was hooked on a proper sniper centric game, I found that the few other games that shared this bent were but shadows of Sniper Elite. It looks the five year drought for quality sniper centric games may be over soon. City Interactive, the largest producer of video games in Poland (home to some of the greatest mathematical minds of history) is set to release Sniper: Ghost Warrior. From the information available and the videos and screen shots at the game site, it looks like a game that could be a worthy successor to Sniper Elite: Properly modeled ballistics and environmental effects for shots, free exploration and non-linear game play, with a variety of mission types. The environments shown remind me of the original Far Cry's lush jungle scenes.

The game is scheduled for release in Q2 for PC and Xbox 360.

I for one can't wait!

Thursday, May 6, 2010

Steganography, GKNOVA6 Style.

The recent viral marketing campaign of GKNOVA6, believed by many to be related to the upcoming Call of Duty game has used cleverly disguised messages to hint at something. What, no one is sure of at this point. One of the messages, itself some kind of hint, has a message hidden within it, revealed by temporal frequency analysis. Details of this can be seen at the entry at BashandSlash. Hiding information in plain sight (plain 'hearing' in this case) like this using techniques such as changing bits of sound or image files or otherwise embedding the information is known as Steganography

Frankly, it's pretty obvious listening at GKNOVA6 that there's something under the covers. I decided to try my hand at this in a less obvious way. Here's a clip of Amazon Rain Forest Sounds. Click to listen, or right click and 'save as' to download if you want to analyze it. There is a repeating message hidden in it: the name of the site that first made me aware of GKNOVA6. The message is hidden as sounds that when appropriately analyzed reveal the actual text of my message. I think the low-level synthesized audio I used for these 'messages' would pretty easily pass the natural sound test and be undetected for most listeners. The louder one stands out a bit on purpose, so you can hear what the 'message' sounds like embedded with the real rain forest sounds.

My message signal was produced in short order using Matlab and Mathematica and was then injected into the real jungle sounds. Basically, imagine scanning a 2-D array that represents the characters you want to inject, where one dimension maps into signal time (the left to right of the message) and the other maps to frequencies (the points occupied by the message in the vertical for a given point in time). As you scan the array in time, you generate some combination of one or more frequencies for that point in time that you inject into your 'cover' signal. Playing a bit loose with the terminology, you are in essence doing an inverse short-time Fourier transform.

The spectrogram you can use to recover the message is doing the reverse: mapping the frequencies and amplitudes for a narrow (in the time dimension) window scanning the signal in time overall. The resultant is nothing more than short-time Fourier transform of the signal: snapshots of the Fourier transform of the windowed signal stacked in time. The video below is a screen recording of the WavePad sound editor with the clip loaded and analyzed. All three message repeats of BASHANDSLASH stand out plain as day in the spectrogram. 

Pretty cool, I think! If you have something that can do temporal frequency analysis (many sound editors have this functionality), or have a package like Mathematica, Matlab, or Maple and know your way around the Fourier transform, have a look at the clip yourself. For a readily accessible, well written book on the basics, see Mathematics of the discrete Fourier transform (DFT) with audio applications by Stanford researcher Julius O. Smith III.

[Update: While making the effort to learn the low-level mathematics and techniques to do this sort of thing is great exercise for the brain, you may not have the time or interest to do so. If you just want to play around with the concepts, I've located a program that you can use to experiment with synthesis of signals from shapes. While the intent of this program is research into analysis and synthesis via partials, it provides a simple means of experimenting with the concepts involved. See S P E A R - Sinusoidal Partial Editing Analysis and Resynthesis for details. ]

Simple shape drawn in S P E A R then converted to audio, with temporal frequency analysis of that audio done in WavePad. (Click to enlarge)

If you'd rather view some results instead of making your own, click on the video below to see the amplitude envelope, temporal frequency analysis, and frequency distribution of the Rain Forest clip.


Rain forest sounds recording with secret message embedded analyzed, showing amplitude over time, STFT (Spectrogram) and frequency distribution. Click on the video while playing to see a larger version in a new window on YouTube.


[Update: Reading the first comment, it occurred to me that an analogy might help some visualize what's happening here.]

If you've ever seen a player piano (I mean a real player piano, with the perforated paper rolls, not a modern digitally based one), you've basically seen a sort of 'mechanical' transform at work (I'm really going to be playing loose with terms and analogies here to simplify this). The roll has positions across the paper that correspond to each note of the piano. As the roll is drawn over the sensor, any place there's a hole, the corresponding piano key is actuated.

So if you look at a point along the length of the roll, going at right angles to the length you would see what note(s) were actuated at that time. The length of the roll is the time dimension, the width is the frequency dimension. You could almost map the holes in the roll as it is wound on to the take up spool as the piano plays into the points of a spectrogram recording the piano (not literally, but surprisingly close).

Let's imagine you had a special 'punch player piano' that would take a blank roll of paper and punch the holes corresponding to the keys you played over time. That roll would be like the transforms over time of the notes you played. Just like the spectrogram, but having far less detail and not accounting for anything other than key press and duration. Now, if we took the roll the 'punch player piano' made and put it on a regular player piano, it would play your 'song' perfectly, mimicking the keys you pressed as time flows. Keys to holes, holes to keys.

Now imagine we take a blank roll, and we manually punch holes in it to make letters and shapes. We could still put that roll into our player piano, and it would play the notes corresponding to your manually made 'song'. It might sound like trash, but who cares. That 'song' would correspond to the 'sound' of my letters and shapes. We do this and record it. This is like my 'hidden' message sound. We could mix in some other real notes or melodies on the paper if we wanted, we could still see our shapes and letters.

Next, say we had someone that could hear any combination of notes and press all the right keys on a piano to mimic them. We play them this 'song' we recorded from our player piano that played the roll we manually punched to form shapes and letters.  As they manually 'replay' our song, their piano punches the holes corresponding to the keys they press into a fresh paper roll. They are effectively acting like a 'human spectrogram recorder', producing a spectrogram (the punched holes on their roll). The end result? Their roll of paper will have the same shapes and letters as the one we manually made. We went from holes (time) to keys (frequency) then from keys (frequency) back to holes (time). Shapes and letters to sounds, sounds to shapes and letters.

So in the main part of this blog entry, we knew what 'shape' we wanted the spectrogram of our hidden message to be (what holes in the roll we needed to make our shapes), and from that made the 'sounds' of it. We mixed that in with real sounds to mask it, and passed it along. Given the right tools, we can take the sounds and see the shapes. Our hidden message sounds produce the shapes we wanted in the spectrogram (the holes in the roll make our shapes). The real sounds that mask our hidden message matter not, but our shapes (the message) are revealed.

Tuesday, May 4, 2010

Splinter Cell Conviction µ-review. A µ post.

My game biases: FPS shooters are my preferred game.I despise most FPH (Flashing Pink Hooves, e.g. WOW, Guild Wars, etc.)

Played on: Mid and high-end PC.

Other nano-review info: Based on single player campaign only, I'll update with MP/Co-op.

Likes:
  • Improved graphics for characters.
  • Interesting game play.
  • Improved enemy NPC AI.
  • Grim is built like a chain smoking bowling alley regular that would polish your balls with her tongue. Bowling balls. Get your mind out of the gutter.
  • Ties up most of the story from the prior games.
  • Well laid out movement system, cover-based.
  • Animations adapt to player positions in environment.
Dislikes:
  • I kind of miss the old movement system where I decided exactly what cover was.
  • Graphics for everything other than characters is starting to look primitive. Modified Unreal engine just not up to snuff anymore.
  • No ability to 'switch shoulders' for aiming.
  • Less Splinter Cell stealth and more Rainbow Six shoot at the hoards.
  • Seems the game cannot even be played completely 'stealth'.
  • Far too much mouse 'inertia'. Weapon aiming, particularly if zoomed seems like you're connected to the sight via slinkies. Inertia adds realism, but this much is silly.
  • Can only use one stickycam at a time.
  • Far too short SP campaign. If you take eight hours, Sam's in a wheelchair in your game.
Grade: B

Buy it if you're a fan of the series, or MP and co-op is your thing (I'll flesh out the nano-review with these later - I tend to prefer SP what with the droves of cheats in most MP shooter games). If the SP campaign is your primary interest, there are much better bang for the buck (i.e., longer campaign) games out there, like Modern Warfare 2.

Saturday, May 1, 2010

Boo! I have you now, child of Satan!

I haven't laughed so hard in a while. This guy might have a heart attack if he played the original S.T.A.L.K.E.R. in the dark...

Caution: Not safe for work / kids content!

Getting Teased by Treyarch: COD7 = Call of Duty: Black Ops

I listened in to the the live webcast by BashandSlash covering the roll-out of the teaser video by Treyarch for the upcoming continuation of the Call of Duty game series. It was a gas to listen in on the commentary from a bunch of the BASH regulars and patricipating in the live IRC chats.

The guest list included:

Guests:
PST*Joker (mycallofduty.com), Rudedog (fpsadmin.com), Josh Peckler (planetcallofduty.com), iBleedv20 (omnilinkit.com), John (EFragTV.com)

Special guest
JD_2020 from Treyarch

You can watch the trailer in HD, and listen to the archive of the webcast at BashandSlash

Thursday, April 29, 2010

I Scream, You Scream, We All Scream for DICE Scream!

Doing some mathematical work with Maple 13 tonight and needed a break. Thinking of the recent fiasco with DICE and their new game Battlefield Bad Company 2 (see Pings? We Don't Need No Stinkin' Pings!), I decided to see how hard it would be to connect to EA's central server (where the information for the game server browser comes from - the one that doesn't work properly in the game) using Maple. I'd already done some work reverse engineering the traffic for this and the patcher, looking to ease the pain of users with the  game browser and the patch process (yay for Steam - patches there just work, no worries of overloaded, flaky EA servers!)

Maple, for those not familiar with it, is an extremely sophisticated application for doing all things mathematical. The product has an amazing list of capabilities for mathematical analysis, graphing, and programming. It is however primarily a mathematical tool, competing with the likes of Mathematica and Matlab. I use all three, Mathematica being my personal favorite. For quick and dirty, however, I find the 'Document Mode' in Maple to be ideal for rapid exploration. I often do proof of concepts there, and when the ideas are fleshed out, move them to Matlab or Mathematica.

So how hard would it be to get to the Electronic Arts centralized server, using a tool completely out of its domain (kind of like using a champagne bottle for a baseball bat), without any of the raw socket nonsense that the game developers used? See for yourself - seven lines of Maple gets you the initial connection and response. A handful more lines would get you a complete server browser. Without the hassles the game introduces by using raw sockets. Pretty powerful tool, doing things out of its real domain. It makes me wonder even more: what were the game developers thinking when they chose to use raw sockets?

Maple Code:

with(Sockets);
sid := Open("159.153.235.12", 18395);
reply := Array(1 .. 65, datatype = integer[1]);

WriteBinary(sid, Array([67, 79, 78, 78, 64, 0, 0, 0, 0, 0, 0, 91, 80, 82, 79, 84, 61, 50, 10, 80, 82, 79, 68, 61, 98, 102, 98, 99, 50, 45, 112, 99, 10, 86, 69, 82, 83, 61, 49, 46, 48, 10, 80, 76, 65, 84, 61, 80, 67, 10, 76, 79, 67, 65, 76, 69, 61, 101, 110, 95, 85, 83, 10, 83, 68, 75, 86, 69, 82, 83, 73, 79, 78, 61, 53, 46, 49, 46, 50, 46, 48, 46, 48, 10, 84, 73, 68, 61, 49, 10, 0], datatype = integer[1]));

ReadBinary(reply, sid);
Close(sid);
convert(subs(0 = 32, 10 = 32, convert(reply, list)), bytes);

EA Server Response:

"CONN ATIME=1272627041 TID=1 activityTimeoutSecs=240 PROT=2"

Hello, EA! All your base are belong to us!

Monday, April 26, 2010

Pings? We Don't Need No Stinking Pings!

The popular new online FPS Battlefield Bad Company 2 has had its share of teething pains. Among those most bothersome to players is the inability to see 'pings' for servers in the online server browser. The developers, EA/DICE, have stated the solution to this issue is to run the game with elevated privileges, either by running in a full administrator account, or by using RunAs or compatibility mode changes to accomplish this.

Poppycock! The fix is to get rid of the poor coding choices that get this kind of result from my debugging traces of over a month ago:

socket: 0: Process 0xfffffa8005375060 (0x768 ), Endpoint 0xfffffa8005c49420, Family 2, Type SOCK_RAW, Protocol 1, Seq 1006, Status 0x0
(FAM: AF_Inet/IPv4) (SOCK: Raw) (PROTO: Stream)

The game is opening (or attempting to open) a Windows socket of  type (3) sock_raw. The use of raw sockets has become increasingly restricted with each new version of Windows, and for good reason.

This is the reason the BFBC2 game executable must be run as an administrator, or have its privileges elevated, for the player to see pings properly in the server browser.

Readers having this issue, either run the game from a 'real' administrative account, or right-click on the game executable and mark it for compatibility mode "Run this program as an administrator". Do note, there can be other issues such as firewall, ISP, or PC configuration that may still prevent pings showing properly.

There is no reasonable reason I can think of that an application like this game needs to use raw sockets, forcing the user to compromise the security and functionality of their system to make the application work the way it should. There are several proper solutions to accomplish the goal of getting the needed data that do not require unneeded privilege use or elevation by the user.

That this information was handed to the devs, and nothing has been done to remedy it, despite a patch in the intervening time being released, is puzzling to say the least. A lunch hour's worth of coding changes should fix this amateur mistake that should never have been made. (How hard is it to get to the server without raw sockets? See "I Scream, You Scream, We All Scream for DICE Scream!" for an answer).

Fix this, DICE!