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.

See Your Way Out - Using mathematics and image processing to quickly pathfind

As I outlined in my blog entry Earning Your Pathfinding Merit Badge: How Game Characters Navigate Their Game World, pathfinding (or path finding) is a critical component in PC games.

Pathfinding refers to the techniques used in games to allow Non-Player Characters (NPC) to navigate the game world.

Most games use some variant of Dijkstra's algorithm, a technique pioneered by Dutch computer scientist Edsger Dijkstra. Dijkstra's algorithm produces a shortest path tree for its result by solving the shortest path problem for a graph with non-negative edge length (the distance between the vertices of the graph are never negative).  It is one of a myriad of graph search (or graph traversal) algorithms.

Dijkstra's algorithm is often used in routing problems, such as network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First), and transportation map shortest path solutions.

Perhaps the most commonly used variant in games is the A* search algorithm. Instead of using the distance from the start node (vertex) of the graph, this variant chooses nodes based on an estimate of the distance from the start node to the destination node. This estimate is formed by adding the known distance to the start node to a guess of the distance to the destination node. This guess is called the heuristic of the algorithm.

By utilizing such a technique, the A* algorithm provides improved performance when compare to the behavior of Dijkstra's algorithm. If the guess is set to zero, the two algorithms are equivalent. When the guess is made positive but less than the true distance to the goal, A* continues to find optimal paths, but because fewer nodes are examined, performance is improved. When the guess exactly matches the actual distance, A* finds the optimal path and does so while examining the minimal possible number of nodes. If the guess is increased yet more, A* continues to find paths, examining fewer nodes still, but no longer guaranteeing an optimal path. In most games, since it is not practical to guarantee a correct heuristic at all times, this is acceptable due to the increase in algorithm performance.

With extremely complex environments (like the maze we'll be looking at), these algorithms can prove to be impractical, with other solutions preferred. A nice overview of such issues can be seen at Sean Barrett's Path Finding blog entry.

I'm going to go through a technique that is conceptually beautiful to me: Using image processing to solve a maze path finding problem.

I'm sure every reader is familiar with mazes. Perhaps some of you have found yourself lost in a particularly fiendish one, having to ring the nearby "rescue bell'!

I'll be using the superb Matlab system from Mathworks.

From their web site: "MATLAB® is a high-level language and interactive environment that enables you to perform computationally intensive tasks faster than with traditional programming languages such as C, C++, and Fortran." 

It most certainly is! Along with the equally superb Mathematica it is the staple of my tool set for doing complex mathematical programming, analysis, graphing, and data manipulation. These two products would be my desert island choices to take with me if I could only have two programming environments.

I'll be using the Matlab image processing package DIPimage, developed by Cris Luengo, Professor in multidimensional image analysis at the Swedish University of Agricultural Sciences and Uppsala University. I've borrowed copiously from his examples. Users of Matlab can obtain a license for DIPimage free of charge (normally a $3200.00 and up cost) for academic, non-commercial use. I highly recommend it!

Let's begin.

We will start with the following simple (no holes, loops, etc.) maze:

Note the entry and exit apertures in the lower right and upper right areas of the outer call of the maze. Try solving it manually if you'd like!

Next, we use our image processing functions to convert our maze to grey-valued, and threshold it to obtain the binary image. The maze walls are now shown in red, with the path areas in black:

maze = colorspace(inputmaze,'grey');
maze = ~threshold(maze)

We use image processing functions to "label" any found walls and show them with differing colors. In this case, we clearly see the maze comprises two walls:

maze = label(maze);
dipshow(maze*2,'labels')

From this we can easily see the path is the area between the two maze walls. By applying a little mathematical morphology, we can isolate one of the walls:

path = maze==1

We then can do a binary dilation on the wall and fill in any holes (effectively a smearing of the wall):

pathwidth = 5;
path = bdilation(path,pathwidth);
path = fillholes(path)

Next, let us erode this smeared version of the wall. This operation effectively "shrinks" the wall by subtracting components smaller than the erosion radius and in the case of a binary image such as ours by removing the perimeter pixels. We then take the difference of the eroded image and the original image:
 
path = path - berosion(path,pathwidth);

Finally, overlaying the result with our original maze shows our desired goal:

overlay(inputmaze,path)

I think you'll agree, a most fascinating use of tools to solve a problem from a domain you'd not likely think to be image processing.

The interested reader can find details of techniques such as these in these excellent references:
 
The Image Processing Handbook by John C. Russ
 
Digital Image Processing Using MATLAB by Rafael C. Gonzalez
 
Feature Extraction & Image Processing by Mark Nixon
 
Happy trails to you!

The Alpha and The Omega of "Search" Engines?: WolframAlpha

You might have noticed I've embedded WolframAlpha into the heading area of the blog. You might not know what it is.

Stephen Wolfram is one of the brightest people you could ever meet. Most certainly a genius. Educated at Eton, and later attending the University of Oxford he had by the age of eighteen already written cited papers in particle physics and quark production. He received his PhD in particle physics at the California Institute of Technology, where he became a faculty member. There he pursued research in computer science, cellular automata, physics, and cosmology, earning him one of the first awards of the MacArthur Fellows Program, commonly known as the "Genius Award".

While at Caltech, Wolfram worked on the implementation of the computer algebra system SMP, essentially version one of what later became the widely used standard for technical computing, Mathematica. Irascible, opinionated, brash and forceful, Wolfram is not one to shy away from imposing his world views on others. His recent years of research led to the publication of A New Kind Of Science, outlined in my blog entry Life Goes On: Further Ruminations on Conway's Game of Life.

WolframAlpha is Stephen's attempt to provide a generalized "computational knowledge engine". Based on the prodigious capabilities of Mathematica, WolframAlpha simultaneously provides a hyper-capable calculating environment and the ability to query for data, either for the sake of the returned data or for use in calculations. The data used is "curated" by Wolfram Research, providing for a much more reliable level of quality compared to existing search engines.

This is no Google. Asking some generic question is likely to be met with the WolframAlpha equivalent of "Huh?":

Ask the engine something more precise, such as "United States population growth", and the character of the system begins to emerge:

Combine this with calculation capabilities second only to actually purchasing a copy of Mathematica to run locally, and you have truly phenomenal capacity for data gathering, analysis, and calculation at your fingertips.

Here, WolframAlpha shows us the integral of a complex equation integral (sin(theta)/cos(theta)^2^pi):

Give it a try, and visit the site at WolframAlpha for more details.

To give it a whirl right now, try typing "ISS now" (without the quotes) into the WolframAlpha box at the top of the blog entry, and pressing enter  or clicking on the equals sign. Be prepared to be impressed!

Earning Your Pathfinding Merit Badge: How Game Characters Navigate Their Game World. A µ post.

As most gamers probably have, I've pondered what mechanism must games use to allow the NPCs in the game to find their way around the game world. Why did games like F.E.A.R. and Halo seem to exhibit more realistic NPC movements?

I was exposed more deeply to the problem when I embarked on building a simple FPS game from scratch including AI, rendering, and netcode. I'd originally planned on a game that mirrored my neighborhood so my friends and I could run around familiar territory and maim each other. It ended up being a shoot-the-aliens sci-fi game: I'm no artist, and it was easier for me to make characters that didn't look like pale imitations of humans.

I'd pulled out all my references in preparation for writing a blog entry outlining the basics of the techniques used for pathfinding in games, when I happened upon a most excellent overview written by a game developer.

They do a much better job than I think I could have, you can view the overview at Fixing Pathfinding Once and For All at the Game/AI blog. Nice graphical explanations, with videos demonstrating the differences in pathfinding strategies.

Other useful background information can be found at A* Pathfinding for Beginners and a short entry at Wikipedia.

My own personal references are the superb four volumes of AI Game Programming Wisdom, and the equally excellent Game Programming Gems, now up to eight volumes with the most recent 2010 release. I was heavily influenced by reading the more academic treatments found in both Artificial Intelligence for Games by Ian Millington by and Behavioral Mathematics for Game AI by Dave Mark.

If you have any interest in how realistic character movement is accomplished in games, I highly recommend taking a look at the links, and if you decide to program your own, I can't think of better reference works than the book series I've used.

I Know What You Did Last Summer: Omniscient Debugging.

I've been doing some coding using the recently released Visual Studio 2010 from Microsoft to experiment with some of the new features and capabilities added since the release of version 2008, my day to day coding platform.

One of the more interesting and very useful features added (only in the Ultimate edition, unfortunately) is IntelliTrace historical debugging. The ability to debug an application while in effect manipulating time (going backwards in the execution history, for example) is known as Omniscient Debugging. The term is properly used when referring to the eponymous open source debugger by Bill Lewis, a computer scientist at Lambda Computer Science and Tufts University, but has become part of the vernacular and a synecdoche for such debuggers.

For readers that are not programmers, the "debugging" of programs is part of the life of any developer. Any sufficiently complex application is likely to have a few "bugs", cases where the expected behavior of the application is not observed to happen. This can be caused by any number of things, from incorrect specification of the design, mistakes in translating the design into program code, use cases that were not considered, bugs in the very tools used to produce the application, etc.

By way of example, let us consider the following tiny application (written in a form of psuedocode):

(define add_two_numbers using Number1, Number2 as (return Number1 * Number2))

The developer hands this off to the users, who start using the new routine add_two_numbers:

add_two_numbers 0,0  →  0

add_two_numbers 2,2  →  4

add_two_numbers 4,4  →  16

Oops! The first two test cases return the proper expected results, but the third returns 16 instead of the expected 8. In our admittedly trival example, we can see from visual inspection the programmer mistakenly put the multiplication operator "*" where the addition operator "+" should have been.

In real applications, mistakes may be buried in hundreds of thousands of lines of program code, and visual inspection is seldom practical. This is where the traditional debugger comes into play for the developer.

A debugger allows the programmer to observe the execution of the application under consideration, by showing exactly where in the execution stream the application is, and allowing the viewing and changing of variables and storage for the application, setting "breakpoints" where the programmer wishes to temporarily halt the execution,  stepping through the execution one step at a time, stopping when certain conditions are met, and in some cases even allowing the changing of the program's state.

Workspace for a typical debugger, in this case  the WinPDB debugger debugging itself.

These capabilities greatly assist the developer in the determination and correction of problem cases. In our example, one could imagine the developer has determined the problem lies in the add_two_numbers routine (imagine of course that the routine is sufficiently large that simple inspection is not an option). By utilizing the debugger, the developer could execute the application, requesting that execution be paused when the add_two_numbers routine is entered.

At that point, the developer could step through the execution of the routine, observing the flow through the source code step-by-step. The source of the problem would of course become apparent, and could be quickly remedied.

In the case of severe bugs, an application may "crash". In some cases, a "crash dump" will be produced by the execution environment. This contains information about the state of the application at the time of the crash. This information can be used by the developer with the debugger to analyze the state of the application when it crashed, and observer the contents of variables, the place in the source code the execution was at the moment of the crash, and basic information about the path by which the application came to that place.

A core problem with this model of debugging, however, is that detailed information about the execution path and program states leading up to the bug or crash is generally not available, even in a detailed crash dump file. This forces the developer to deduce where the problem might be and then test that hypothesis with the debugger by setting conditions and breakpoints while analyzing the application flow. This will usually lead to a more refined hypothesis, leading to further debugging, leading to a more refined hypothesis, nearly ad infinitum (or at least it can feel that way) until the problem is found. In cases where the bug is sporadic, the programmer may have difficulty even reproducing the problem.

This can be a very time consuming and taxing practice for the programmer involved!

Ideally, the programmer would be able to observe the state of execution for the application at any point in time of the execution lifetime.

That is precisely the capability that omniscient debugging brings to the tool set of the programmer. The concept of such historical debugging has been around for decades, but implementations proved impractical for most of this time. The first truly practical and usable example is surely the Omniscient Debugger (ODB) of Bill Lewis. A very detailed paper by Bill can be seen in Debugging Backwards in Time, and a most interesting video lecture of the same name is hosted by Google.  You can view these to garner details on how this functionality is achieved, with examples of the kinds of bugs that are vastly simpler to find by taking advantage of this kind of technology.

With Visual Studio 2010, Microsoft has incorporated and extended this capability and technology, calling it IntelliTrace. Supporting the historical debugging of managed C# and Visual Basic, with experimental support for F#, the product promises to make the work of developers on the Microsoft platform vastly more productive. Details of the new capabilities can be found in the MSDN articles Debugging With IntelliTrace and Debugging Applications with IntelliTrace.

Open source developers can avail themselves of historical debugging with the aforementioned ODB, TOD and GDB debuggers.

I know what you're thinking. More importantly, I know what you were thinking...

Life Goes On: Further Ruminations on Conway's Game of Life.

Conway's Game of Life, as I noted in an earlier blog entry An Alien Message? is an utterly fascinating example of Cellular Automata, capable of mind boggling complexity from an incredibly simple set of base rules.

As a further example of how the game can "compute" in the same way that a traditional computer and programming language can be used to execute programs that compute, I loaded up the recently created seed pattern by Jason Summers for a new type of "Primer" pattern. These patterns in the game will in some fashion "output" the sequence of prime numbers. This particular pattern emits the type of prime number most familiar to us: 2, 3, 5, 7, 11,13... ad infinitum.

Start the video, and observe the area where the "gate" is in the lower left middle. Passing through it will be Life "Spaceships" spaced precisely as the sequence of primes.

As discussed in my earlier entry, patterns for the game exist that create a Universal Turing Machine, meaning the game can "compute" in the same way that any program can. If it can be done in any programming language, so it can be done in the Game of Life using such a pattern. Mind blowing!

Stephen Wolfram, polymath extraordinaire and creator of the widely used mathematical, programming, and graphing workbench Mathematica has written extensively on the subject of cellular automata in his book A New Kind of Science.

In all fairness, while well received overall the book was the target of some rather excoriating reviews by experts in the various related fields, and accusations of intellectual thievery have been raised. Perhaps the most scathing of these and an interesting read on its own can be found in Quantum Information & Computation with the review by Scott Aaronson, a theoretical computer scientist and member of the MIT Electrical Engineering and Computer Science department.

The book is good read nonetheless for a view into the wide applicability of cellular automata, and the five pound nearly 1300 page tome will make a fine doorstop if you find it not to your fancy.

Wolfram extensively discusses the relationship of these objects to nature, modeling complex behaviors and results with simple basic starting seeds. A good example is that of certain seashells, where the complex patterns of their shell is generated by natural cellular automata.

Wolfram's central point in the book is that complex behaviors and results do not require a complex system for their production.

This culminates in the core of his "new science", the "Principle of computational equivalence".

As eloquently described in the Wikipedia entry for the book, "The principle states that systems found in the natural world can perform computations up to a maximal ("universal") level of computational power. Most systems can attain this level. Systems, in principle, compute the same things as a computer. Computation is therefore simply a question of translating inputs and outputs from one system to another. Consequently, most systems are computationally equivalent. Proposed examples of such systems are the workings of the human brain and the evolution of weather systems."

To get your own hands-on feel for how simple systems can generate incredibly complex results, get yourself a copy of the most excellent Golly cellular automata application where you can explore Conway's Game of Life and other types of cellular systems.

You may find yourself as addicted and fascinated as I am!

A Bathroom Reader for Computer Science. A µ post.

Poking around for some pictures for my blog entry that talked about the programming language APL and showcasing an implementation of Conway's Game of Life in one line of the language, I came across an implementation of the Universal Turing Machine in The Game of Life.

As I outlined in that entry, the implications for this are deep. The game, a prime example of cellular automata, consists of a tiny rule set of just four rules yet it can 'compute' anything that can be done by any program you could write for a traditional computing environment using more familiar programming languages. I am honestly awestruck every time I think about this.

The author of this particular pattern for the game has a piece in the book Collision-Based Computing edited by Andrew Adamatzky. The description of the book, published by the top notch academic publisher Springer:

Collision-Based Computing presents a unique overview of computation with mobile self-localized patterns in non-linear media, including computation in optical media, mathematical models of massively parallel computers, and molecular systems.

It covers such diverse subjects as conservative computation in billiard ball models and its cellular-automaton analogues, implementation of computing devices in lattice gases, Conway's Game of Life and discrete excitable media, theory of particle machines, computation with solitons, logic of ballistic computing, phenomenology of computation, and self-replicating universal computers.

Collision-Based Computing will be of interest to researchers working on relevant topics in Computing Science, Mathematical Physics and Engineering. It will also be useful background reading for postgraduate courses such as Optical Computing, Nature-Inspired Computing, Artificial Intelligence, Smart Engineering Systems, Complex and Adaptive Systems, Parallel Computation, Applied Mathematics and Computational Physics.

Yummy! As with most Springer books, prepare to have your wallet 'Springered', in this case to the tune of $130.00. Ouch! I've spent enough already on their superb publications in computer science, physics, and mathematics to purchase a nice car, so I suppose I'll spring (ugh! I couldn't help myself!) for this one too.

I you're interested in computation by non-standard methods, some bordering on incredulousness, this sounds like a fun read.

I figure one chapter per visit.

Always Be Reading A Book That Will Make You Look Good If You Die In The Middle Of It.

When I was doing the start up thing in the Silicon Valley, there was an engineer the I'd always see reading some pretty esoteric books. I queried them one day when I noticed they were carrying a rather large book on quantum mechanics. Having an interest myself, I welcomed the chance to discuss the subject. Turned out he wasn't even really reading the book. It was, in his words, "bait for the smart ones over at the Stanford campus." He would spend his lunch time over there at the commons, hunting his prey. I never did find out if the bait actually worked...

 "Outside of a dog, a book is man's best friend. Inside of a dog it's too dark to read. " - Groucho Marx

A good bookshelf is a must for any serious devotee of hardware and software. Myself, I stopped counting when I crested the 1000 book mark for my computer science related texts. As learning tools, reference works, and sources of pleasure, a good computer book is hard to beat in my opinion. With that in mind, I thought I'd make an entry listing the top tenish books that I think every serious programmer should have in their shelves.

These are not listed in any particular order other than that which they came to mind, and are operating system and language agnostic for the most part.

The Art of Computer Programming; Donald Knuth
All three volumes of course, plus the five fascicles that presage volume 4. Never has so much CS knowledge been packed into such a small space. This truly is a CS degree in a box.

Elements of Programming; Alexander Stepanov
Programming is mathematics. Seldom is this fact given proper treatment. This book remedies that brilliantly.

Introduction to Algorithms; Cormen, Leiserson, Rivest, Stein
A standard reference for professionals, and a widely used university text. Half of a CS degree is in this book.

Modern Operating Systems; Andrew Tanenbaum
The classic all-around reference and learning resource for the details of the inner workings of operating systems. From the creator of Minix, a Unix like teaching OS that was the template for the first Linux.

Beautiful Code; Andy Oram, Greg Wilson
See how luminaries in the programming world have created elegant solutions to difficult problems in a variety of programming paradigms and languages.

Masterminds of Programming: Conversations with the Creators of Major Programming Languages; Federico Biancuzzi, Chromatic
A superb 'behind the scenes' look at how historic and influential languages came to be, told by their progenitors.

Code Complete: A Practical Handbook of Software Construction ; Steve McConnell
A classic, recently updated. Certainly one of my 'desert island' picks for instruction on the proper design and construction of software.

Programming Windows; Charles Petzold
It's dated. It's also still the classic reference for Windows programming. "Look it up in Petzold!"

Windows Internals; Mark Russinovich, David Solomon, Alex Ionescu
There is no better publicly available reference for what makes Windows tick than this tome from the 'ghostbusters' of the Windows world.

The Algorithm Design Manual; Steven Skiena
Implementations and explanations of all of the important algorithms, and humorous to boot.

Structure and Interpretation of Computer Programs; Harold Abelson, Gerald Jay Sussman
This classic, often called 'the wizard book', was the text for MIT's introduction to programming classes. A rigorous lesson in how to think about programming.

Compilers: Principles, Techniques, & Tools ; Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman
The best survey, in my opinion, of the inner workings of compilers, with a sharp view of how design decisions affect the user.

I think if I awoke to my house on fire, after getting my family out, these would be the books I'd want to save from the blaze. I could happily settle for them being the only books on my personal shelf.

What's on your own list that you'd bring to a desert island?

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.

So You Wanna Be A Programmer?

A recent comment gave me the impetus for this entry. Often, as I answer a question about computers and computing fielded by non-programmer friends, I'm asked 'How hard would it be to learn simple programming?'

It goes without saying that to become truly expert in programming takes much time and experience. Researchers in the field quote 10,000 Hours as the average tipping point, echoed by a personal hero of mine in the world of computing, Peter Norvig, currently Director of Research at Google and one of the truly great minds of computer science and artificial intelligence.

But one can easily do most useful things with far less time, and the hobbyist programmer can easily be writing simple programs in a short time, and then enjoy the unfolding learning process as they progress in their knowledge.

That said, allow me to list some resources for the budding programmer. These are meant to be accessible to those with zero background in the field. I've assumed the reader is on the ubiquitous Windows operating system on a PC, since that covers about 93% of the market at the time of writing! Nonetheless, interested readers can avail themselves of the recommended Scheme and Ruby language choices in other environments such as Linux.

Step right up! Pick a language, any language!

The first decision you'll need to make is which language to start with. I've picked three that I've seen success with by novice programmers. These are Visual Basic and C# ('See Sharp') from Microsoft, and Ruby.

All three of these languages offer the opportunity to learn cutting-edge programming techniques such as Object Orientation and Functional Programming. Purists may object that none of these is 'pure' in either sense, and that is of course correct. Nonetheless, as a framework for learning the concepts involved, all three choices are excellent.

All of these languages are available as free of charge downloads.

I've had great success recommending the following books for autodidacts for each of these languages:

• Microsoft Visual C# 2008 Express Edition: Build a Program Now!
• Microsoft Visual Basic 2008 Express Edition: Build a Program Now!
• Learn to Program, Second Edition (The Facets of Ruby Series)
• Programming for the Absolute Beginner (No Experience Required)  (Not VB, but Basic) 

In addition, there are a myriad of nice web based tutorials. A few I can recommend include:

• Visual C# .NET Programming
• Visual Basic .NET Programming for Beginners
• Learning Ruby (Various nice short tutorials at the home of the language.)

Once your interest is whetted or perhaps while starting down the road to programming bliss, you'll want to take a read of Beautiful Code, where experts in the field explain elegant solutions to difficult programming problems. You'll probably need some programming time to fully grok the whole book, but it is an absolutely superb read.

Another most enjoyable book that will give one insight into the 'cool' of programming is Hackers & painters: big ideas from the computer age, by one of the most brilliant thinkers in programming (in my opinion), Paul Graham. Paul delves into the world of Lisp, arguably the most 'beautiful' language extant.

The book is a wonderful read even for a non-programmer: most of any discussion relating to programming is done using well explained examples. The author writes with a sharp wit, and will certainly get your juices flowing over esoteric programming problems.

One might wonder why I haven't recommended Lisp for the beginner, being as I consider it so 'beautiful'.

Two luminaries of the world of Computer Science, the aforementioned Paul Graham and the brilliant Gregory Chaitin seem to agree with me on the beauty of this language, the latter saying "...the original LISP, the conceptual heart of LISP, a core which is a jewel of considerable mathematical beauty, austere intellectual beauty."

Another Lisp lore favorite of mine is Greenspun's Tenth Rule of Programming: "Any sufficiently complicated C or Fortran program contains an ad hoc informally-specified bug-ridden slow implementation of half of Common Lisp."

It's a fair question though. I actually have used Lisp to teach programming one-on-one, I think it makes one a much better thinker in the realm of programming, and even if Lisp is never used by the learner once on their way, it will have profoundly changed the way they think about programming.

But the edifice of Common Lisp is deep. And wide. And tall.

I think that learning Common Lisp on one's own, without any prior background, is like a fast-food diner deciding to learn how to cook. But learning to cook in this case includes learning how to manufacture a rifle, learning how to stalk your prey and properly dispense with it, then figuring out how to butcher the beast, next learning how to smelt iron to make the cooking utensils, followed by a lesson in the production of an oven, and finally instruction in proper Chef de Cuisine antics. You get the idea.

But if you're bent on really expanding you mind in your learning adventure, try something like PLT Scheme, a simplified dialect of Lisp. There are excellent learning resources at the PLT Scheme Learning page, I highly recommend the book How to Design Programs should you take this route, it is centered around PLT Scheme. An amusing overview and good tutorial is provided at Teach Yourself Scheme in Fixnum Days.

You might just find yourself repeating an observation of a student of mine at the end of a course in Scheme:: "Why on earth would I ever want or need to use any other language?"

You might also want to take a peek at my blog entry What programming languages should you learn?, where I describe what I think would be an ideal course of languages for someone seriously interested in programming.

Any of these learning routes should prove rewarding, and start you on the trail toward programming wisdom.

(begin
   (display "Hello, Budding Programmer!")
   (newline))

Persistent vegetative state: Has a Do Not Resuscitate order been put on PC game development?

PC gaming, as we have known it over the past many years, is dying. It may already be brain-dead and we just don't know it yet. Certainly many of the developers that produce games for the PC platform seem to have gone comatose. By PC gaming, I mean the games where the basic game from the developers could be configured and modified ('modded') into a game that fit the players' desires.

New custom maps? No problem! New characters? You got it! New scoring modes or kit restrictions for competitive play? For certain! Custom dedicated servers with admin controlled settings? Check! LAN based private servers? You bet! In-game console? Of course! Build a completely new game from scratch using the core that can become wildly popular? Been there, done that!

Some games provided the tools to do these kinds of things, others needed clever reverse-engineering, but it could be done. Those days, I think, are drawing rapidly to a close. The market realities (depending on who you talk to, consoles such as the Xbox, Playstation, and Wii enjoy a six or seven to one sales revenue advantage overall compared to PCs) dictate this.

Developers either decide not to even develop for the PC, or do so in a lowest common denominator fashion. More and more, the development environment is a 'write once, deploy many' environment. That means the developer builds the game using the meta-environment of the development tools, and these in turn produce the 'run time' executables and assets for the deployment platforms simultaneously. In some cases, this will result in games that are the same across platforms, except perhaps for input device support. In other cases, some 'customization' can be done for each specific platform to the core (bulk) of the generated game, such as server browser functionality for the PC version that may not exist for the console versions.

In any case, this 'customization' must be fairly limited, else it starts to intrude on the whole purpose of building games using a 'write once' model: rapid development, deployment and easy updating of the core game. We see more and more laments from PC gamers about some new game being a poor 'port' from the console version. The problem is not bad ports - a port can in fact be quite excellent, with platform specific functionality added during the porting process.

The problem is the emerging model of game development no longer revolves around porting of games, but around the deliberate dumbing down of the core game design and development to fit the commonalities of the chosen deployment platforms. There is no longer any real porting done, just the gluing on of some limited platform specific functionality to the core game code vomited out by the development tools. And even more unfortunately, it seems developers put amateurs on to the job of adding these PC specific features: see Pings? We Don't Need No Stinking Pings! for a recent example of this.

The net result of more and more game developers adopting this kind of development model means more and more games are going to be built to this 'lowest common denominator' of functionality for the platforms the developer decides to deploy to.

The reality is developers are moving to this model, or are using it already. Once the development tools and environments are deemed mature, the result for them is faster, easier, and less expensive development, with vastly simplified deployment and maintenance. The complexity of these tools and environments, combined with the deep abstraction they use to enable their functionality, means making these tools available to the end-user is most unlikely, and reverse-engineering of games has become more and more difficult.

So, the developers can make a game at a lower development cost, designed and built to a lower standard of functionality and capability, and sell it at a very profitable price to a willing (mostly console playing) public. We should certainly be able to understand the reasons and motivations for the game developers and publishers to move to this model. They're in the business to make money, after all. Sadly, as this model is adopted by more developers and publishers the importance of the PC player community diminishes with each passing day.

The situation reminds me of the near death of the classic mechanical wristwatch: Introduced in the early 70's, Quartz wristwatches seemed like the Ebola of the mechanical watch making world. Soon, manufacturers of the hand made mechanical works of art were dropping like peasants during the Great Plague. Most switched over their primary manufacturing to quartz movement based watches. Simpler to make, cheaper to build, and profitable to sell. And yet, a few of them recognized that there was a market for truly well executed 'old school' technology, and that buyers would pay a premium for the privilege. This has resulted in pieces like the one from my blog entry Things Unexpectedly Technical, which sold out instantly to seven fortunate buyers for seven figure prices.

The end seems near for 'old school' PC gaming. We can only hope some developers will realize there is a market of PC connoisseurs that are willing and able to take advantage of PC games built and deployed in a PC centric fashion. Even if it means a pricier game, I for one am willing to pay for excellence.

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!

I ♥ Windows 7 Event Logging!

I was recently debugging a couple of applications, and was trapping some events as part of the process. I forget how useful the Event Viewer is in general, and particularly with the greatly enhanced functionality in Windows 7/Vista.

Two of the really cool features are the ability to build sophisticated custom filters and views, allowing you to focus on exactly what you're looking for, and the ability to create events on events.

For example, the following XPath query for a filter/view allows me to trap a specific event for a specifc PID, excluding all other 'noise' in the event log:
  
<QueryList>
   <Query Id="0"
     Path="Microsoft-Windows-Winsock-AFD/Operational">
      <Select Path="Microsoft-Windows-Winsock-AFD/Operational">
         *[System[Execution[@ProcessID="3141"]]]
            and *[System[EventID="1000"]]
      </Select>
   </Query>
</QueryList>

Equally cool, I can assign tasks to any event/view/filtered view such that the system will notify me with a dialog, E-Mail me, or start any arbitrary program.

Hugely useful, allowing efficient, quick & dirty debugging without even needing to fire up a real debugger, and as an incredibly useful ancillary to formal debugging.

“Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.

Quine's Paradox. Named after the brilliant Willard Van Orman Quine, author of a favorite book of mine titled Quiddities: An Intermittently Philosophical Dictionary. The sentence is intended to show a paradox similar to The Liar Paradox can be had even without self-reference.

Named after him is the Quine Program, denoting a program that can reproduce itself as output, given no input (which makes the problem trivial, and is considered 'cheating'.)

It is effectively the Fixed Point of the execution environment. An example in Scheme looks like this:

((lambda (x)
   (list x (list (quote quote) x)))
   (quote
      (lambda (x)
         (list x (list (quote quote) x)))))

For a mind-opening exposition on all things recursive and self-referential, I highly recommend a read of the amazing work by Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid

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!

A Most Interesting Development in Graphics and Rendering

Check out the stuff at Unlimited Detail Technology.

Most fascinating, an amazing start for an autodidact. It is so good, I wonder if it is some elaborate April Fools' joke...

It will be quite interesting to follow the progress of this project, even more so the reactions of Nvidia and ATI. If they're smart, and this is the 'real deal', one should buy the technology outright, and utilize the GPGPU functionality available in their products to speed computation.

In the SCHEME of Things

One of the startups I was involved in (Ariba - one of the few survivors of the Internet bubble of 2000, and home to some of the most brilliant people I've had the pleasure of working with) utilized Scheme for the underlying configuration, display, data definition, and process control system. Scheme is one of the two languages widely used based on the lambda calculus, homoiconic with mind-altering features like first-class continuations. Think of it as a 'cleaned-up' Lisp-1.

A hugely powerful language, perhaps, along with Common Lisp, my favorite. It allowed us to be unbelievably agile in response to customer needs: While the competition would have to take engineers off of pressing projects to have them do quick-and-dirty coding to add some deal-breaking feature, more often than not the Ariba field tech giving a demo could add it on-the-fly. Blew the minds of prospective customers (not to mention keeping the competition wondering what kind of voodoo magic we had), and resulted in a hugely successful company.

I was reminded of the elegance and conciseness of the language from a blog post I recently read. The poster wanted to dump the logs of an IRC they frequented. Need to setup the underlying network, connections, open the log, display it. The code?

(require net/url)
(display-pure-port (get-pure-port (string-url "http://ccl.clozure.com/irc-logs/lisp/2009-12/lisp-2009.12.28.txt")))

From Lam Luu, a student and lover of the language, Quicksort for any data type, with a user supplied comparator:

(define (filter list get?)
(cond ((null? list) '())
((get? (car list)) (cons (car list) (filter (cdr list) get?)))
(else (filter (cdr list) get?))))

(define (qsort list compare)
(if (null? list)
'()
(let ((pivot (list-ref list (random (length list)))))
(append (qsort (filter list (lambda (x) (< (compare x pivot) 0))) compare) (filter list (lambda (x) (= (compare x pivot) 0))) (qsort (filter list (lambda (x) (> (compare x pivot) 0))) compare)))))

What a beautiful languge!

The Race for Real-Time Photorealism

Having built a simple client-server FPS game including a simple rendering infrastructure and even simpler netcode from scratch as a brain exercise, I'm always amazed at what the real experts in the field can do.

A most fascinating article in the March 2010 issue of American Scientist covers aspects of rendering for realistic scene generation. My feeling is we are less than a decade away from games that can render environments indistinguishable from a movie. The rendering of humans, or other familiar living things, may be a bit further down the road: We are so programmed to incredibly subtle visual triggers, while it is currently posssible to render a human that is indistinguishable from reality, the illusion collapses once movement, speech, or other interaction occurs.

A fascinating read, available at the time of this post at: http://sigmaxi.org/4Lane/QMag/AMS_Mar_2010.pdf

Yes, Virginia, 32-Bit Windows can use more than 4GB of physical RAM...

In one of the forums I frequent, a debate broke out in a thread over whether 32-bit editions of Microsoft Windows can in fact handle or otherwise use any physical RAM in a system over 4GB. There is still widespread misinformation posted about this, even after all the time taken by various MS engineers (such as the most amusing Raymond Chen) to clarify the facts.

Let's set the record straight.

YES! 32-bit versions of windows can take advantage of more than 4GB of physical RAM.

Example 1: The server editions.
I refer the reader to Memory Limits for Windows Releases for the canonical document.

On these systems, the application is of course limited to 2GB of userspace virtual address space. Using the (again, oft misunderstood) /3GB switch, applications that are compiled with the appropriate flag can avail themselves of a 3GB virtual address space. Utilizing processor and OS PAE capabilities, and Windows APIs such as AWE, or via Kernel mode drivers, such applications can map whatever physical RAM address space the machine exposes into their particular virtual address space. This is how things like SQL Server can have huge memory use (well over any 4GB limit) on such versions of the OS.

Far too many Internet 'experts' advise readers to use things like the /3GB switch to 'increase how much memory your program can use', completely missing that fact that the application must be compiled using the appropriate flag to do this. This can be done 'after the fact' with EDITBIN or a Hex editor, but unless you're sure the coders of the application were sane, or you've otherwise analysed the binary, you might be asking for trouble. In addition, programs compiled with '/GL' (Whole Optimization) cannot be modified using accepted post-compile methods. The end result is the reader ends up burning 1GB of address space that the OS could use for the Kernel, that ends up just sitting there wasted. I would direct the interested reader to the aforementioned Raymond's blog for an amusing, multi-year expose of this.

Example 2: The 'client' editions.
Things get a little more confusing for the 'client' versions of Windows (the consumer versions.) For these, Microsoft decided after rigorous testing that the problems exhibited by drivers and other low-level code would present too many problems when faced with RAM addresses beyond 4GB, and so disabled the 'awareness' of the OS for these versions of the OS for RAM beyond 4GB.

However, properly coded applications and drivers (e.g., Ram Disk software by SuperSpeed) can in fact utilize RAM beyond 4GB even in the 'client' 32-bit Windows versions. I used to do this every day, until the remaining reasons not to use a 64-bit OS were eliminated for me.

Here's a screenshot of this very application, running on a friend's PC with 6GB of physical RAM, providing a 5GB RAM Disk. Note that the 2GB of physical RAM above 4GB is being used perfectly well by this application running under 32-bit Windows (click to see large original):



There were valid reasons for using such 'work-arounds' for 32-bit systems to use more than 4GB of RAM in the past: driver vendors had not kept up with 64-bit systems, and often had either no drivers, or problematic ones. Those days seem long gone, and at this point, there's really no good reason not to use a fully 64-bit capable operating system, even on consumer PCs.

Nonetheless, the fact remains: Yes, Virginia, 32-bit windows can use more than 4GB of ram.

Update:

Finally! Someone at Microsoft read this, perhaps? As of early 2011, the Microsoft Developer Network's canonical document "Memory Limits for Windows Releases" has been properly updated with the correct facts:

X86 client versions with PAE enabled do have a usable 37-bit (128 GB) physical address space. The limit that these versions impose is the highest permitted physical RAM address, not the size of the IO space. That means PAE-aware drivers can actually use physical space above 4 GB if they want. For example, drivers could map the “lost” memory regions located above 4 GB and expose this memory as a RAM disk.

About time...

What programming languages should you learn?

I get asked periodically "What programming language should I learn to build my own games?".

Most games built today are done in C and/or C++. So I suppose, if you are looking to enter the game development field, learning one or both of those should be a priority. I like to think of the question in more general terms myself, more along the lines of "What programming language should I learn if I want to learn how to program?"

Having taught Lisp to engineers, I've seen the value of exposure to different paradigms in developing maturity in programmers. Were I to build the 'ideal' coursework to teach a 'How to Program, from Scratch' curriculum, I think I'd follow this course:

1) Assembler. Little practical use for building a new piece of software. Frankly, the speed of code produced by modern compilers of high-level languages is so good that in most cases only the most experienced human coders can better them. And yet, by learning this most basic lingua franca of the machine, the budding programmer will be exposed to thinking in the same way the machine 'thinks'. I for one believe this leads to more sane considerations as to the efficiency of their code. Of course, the ability to debug/disassemble/analyze applications where the source code is unavailable means knowledge of assembler is invaluable.

2) C. The mother tongue of many operating systems, still one of the most widely used application development languages. A good first step for the beginning programmer to get a foundational understanding of basic programming techniques and structure.

3) Java. Introduces, in a framework easily grasped by someone with C experience, the concepts of Object Oriented programming. One could argue there are other environments that do the job better (Ruby, Python, etc.), but the wealth of excellent teaching materials, and the availability of real jobs in the real world, makes this my choice to teach the OO concepts.

4) Erlang. Originally developed by Ericsson, this language introduces the learner to the world of distributed, fault-tolerant, concurrent programming. The conciseness of the language for its intended purpose allows for easy experimentation in these arenas.

5) Forth. Stack based, non-explicit grammar. I include this as an excellent environment for the learner to look at problems from a completely different angle.

6) Lisp. Functional programming at its best. Were I forced to pick one language for someone to learn if they are learning to program from ground zero, this would be it. Lisp has had features and functionality that are still unequalled overall by any other language. Even though every other language of import has evolved over time, adding features and capabilities (and becoming more lisp like), this still holds true. The mind expansion that results from really understanding and using the capabilities of the language will make one a better programmer in any language, even if they never use lisp again. The electric acid kool aid test for new (and experienced) programmers.

7) Mathematica. What? A mathematical computational software system? Yes! I use this product for various modeling and mathematical processing tasks. It utilizes an extremely sophisticated programming language that can be used in any of the traditional programming modes (imperative, OO, functional, rules-based, etc.), and can combine these methods in a single code chunk. The term rewriting reduction system that pervades Mathematica makes for one-liners that can require many lines of code, or even pages, in other languages. Memoization? In Mathematica, the one line:

Fib[0]=0; Fib[1]=1; Fib[n_] := Fib[n] = Fib[n-1] + Fib[n-2]

Gives us the Fibonacci function, fully memoized. Compare this to a Python (already a more concise language than most) implementation:

memo = {0:0, 1:1}
def fib(n):
      if not n in memo:
               memo[n] = fib(n-1) + fib(n-2)
       return memo[n]

Isn't the Mathematica solution so much more elegant and readable?

Not only does this allow for remarkably rapid 'proof of concept' experiments, but it also serves as an excellent environment to experiment with the many ways of solving the same problem. If I'm not using Lisp to prototype something, I'm probably using Mathematica. I used Mathematica to create the animated image of the Sun's analemma and the relation to the equation of time, by calculating the Earth's orbital elements and their effect on true and mean solar time. You can take a peek at it on the wikipedia entry Equation of Time, or the image itself at Analemma and EOT.

I'd probably throw in some SQL for good measure. This bag-oriented (that's right, not set-oriented, nor relational for that matter) language is the most widely used query language for large database systems. That the thought process needed to produce well-formed, optimal queries using this is different enough in concept from the paradigms of the previously mentioned languages, not to mention any large data based system is likely to have some form of DBMS under the covers that uses SQL, makes this a worthwhile addition.

Each of these I think forces the programmer to think differently enough in how to approach a problem they can't help but end up with an expanded 'thought portfolio' to use in attacking future problems.

Your thoughts?