Quarkiness

Featured

GOFAI for Game Dev

Neural Networks, Machine Learning (ML), Deep Learning, … – that’s modern AI. These methods have produced spectacular advances in vision, natural language, pattern recognition, and many other areas. Entire academic, corporate, and national efforts have sprung up to join the race to avoid any ‘ML Gap’. In fact, the terms ML and AI have now commonly become synonymous.

A related hardware trend has taken the computing industry by storm: Massively Parallel Processing (MPP). ML, specifically the training of neural networks, greatly benefits from such hardware acceleration. This wave began with the ubiquitous Graphics Processing Unit (GPU), then expanding into devices such as the Associative Processing Unit (APU), Tensor Processing Unit (TPU), Vision Processing Unit (VPU), and even Field Programmable Gate Array (FPGA). Even tiny chips that perform dedicated monitoring and automation tasks (edge computing) are now integrating such MPP technology.

Of course, game designers have been scrambling to enhance and augment their offerings by incorporating such methods. Mainly in the realm of AI players, to better reflect human strategic thinking. Chess, Go, general knowledge, and many other specific machine players have now achieved supremacy over human players. Playing some modern games against one or more AI players is almost a ‘social’ experience.

It wasn’t always thus.

Back in the single-threaded days, those halcyon days of early PC gaming, AI had a much wider horizon. Symbolic themes such as logic, optimization, semantics, rules, expert systems, goals, and graphical knowledge representation dominated. Steps and decisions were the basis of design, and often some sort of ‘theory of mind’ existed, even if very simplistic. Logic and knowledge representation tools sprouted, such as Lisp, Prolog, and several Production Systems. Navigating decision trees, usually via some form of context awareness and backtracking capability was a process that was reassessed at each step. This was great for automating simple, explicit thought processes and playing simple games (tic-tac-toe, checkers, adventure, cards, etc). However, it fell short when confronted with the much harder areas of vision and common sense. Good Old Fashioned AI (GOFAI) went the way of the buggy whip. The lull that persisted from the late 1980s through the early 1990s is an example of an ‘AI Winter’.

But perhaps that total abandonment was a mistake. It’s easy to rush right past available treasures when blinded by shiny new objects.

Modern games are certainly beautiful to look at, with amazing realism and depth, but are they more meaningful? more playable? more fun?? Gameplay is about much more than realistic perception and rendering. This is especially true for Game Based Learning (GBL). In GBL, the firing of neurons in the player’s brain is the goal, much more than the passive presentation of eye candy.

The Human Computer Interface (HCI) has actually progressed little over the decades. Instead of the game living mostly in the player’s mind, as it did in the primitive arcade days, it is now presented almost as a movie, with entire scenes played out for them. Much of the overall experience can be obtained just by watching game demos. The most compelling feature of modern games is their community… of human players!

What if gameplay itself was the focus? Exploiting and augmenting the innate power of human intelligence. HCI enhancements could once again move the game into the player’s mind, where it belongs. Instead of pre-fab, frustrating, stultifying scenarios, the player engages with a snappy, assistive, powerful, and ‘syntonic’ game. Simple rules could be explicitly available or even player-created. The great fun of Minecraft is largely due to the process of learning and mastering such rules, which are presented in a progressive, bootstrapping way. Instead of hiding the underlying mechanisms in order to present slick, canned movies, the player could be aware of how and why things actually work. The best combat games are those that enable the player to construct their own custom devices. Sadly, this is always achieved with a rigid menu system instead of a pencil-and-paper approach. Again, the player’s own creativity is stifled or ignored. Fairly complex worlds, even player-modifiable ones, can be created in Prolog. Explicit rules and facts are both computer and human readable. Transparency and openness are the keys to truly immersive games – pulling back the Oz curtain is a good thing.

Automation is another way to greatly enhance the playing experience. Sometimes the player is forced to repeat a series of steps even though they only wish to make one or two minor changes from their last go through. Wasting time is not fun. Giving the player access to such a series to make minor tweaks would be a great time saver, which would allow the player to focus on strategy, not mundane tactics or plain drudgery. And a tiny sprinkling of assistive AI to avoid stupid mistakes could enhance gameplay. Players don’t mind AIs ‘cheating’ so much as they mind pointless glitches and ‘gotchas’. Most decent chess AIs have had this feature for decades. It’s surprising that many modern games don’t even have a simple ‘undo stack’, instead relying on frequent game saves. The best games also have an ‘advisor’ system that helps the player with decision-making in the current context, with the option to squelch advice and tips as the player gains experience. The focus should be not only on rich content, but also rich context.

There is another area where automation is valuable: testing. By providing for massive machine-play error checking and discovery of gameplay glitches and bottlenecks, Automated Testing can greatly speed and enhance development. This can include an array of techniques, from short scripts to sets of rules and goals to full-blown simulations of human players.

But here’s the biggest nugget for GOFAI in games: Expert Systems. Capturing well-structure semantic knowledge is a perfect fit for strategy games. Many simple ‘How-To’ experts that encapsulate human knowledge can be easily created, rapidly consulted, and efficiently stored without any massive frameworks or ML tools. The skill of AIs can be enhanced merely by ‘learning’ from human players. Note that this is far, far simpler than actual Machine Learning. Most rule knowledge bases take up kilobytes of RAM, not gigabytes of code and storage. A packaging system would allow players to share (or even purchase) expert systems from others. Both gameplay and AI skill could be upgraded and personalized. This brings in a robust educational component, again, like Minecraft does. Human readability is key. We all have a basic comprehension of facts, rules, and inference. There’s no daunting learning curve required. Why not incorporate this innate comprehension into games?

In summary, gameplay has become too enamored of shiny bobbles and photo-realism. The current wave of Machine Learning is leading to evermore complex and power-hungry requirements, a burden on both developers and players. GOFAI could mitigate things rapidly and easily, and shift the game experience from the eyes to the mind’s eye. Game dev expands beyond the studio, into the laboratory. Let the fun begin.

Slide Rule

A slide rule is a simple, mechanical, analog computer. It has a single moving part – the central slider (and usually a movable cursor to read results). It has etched or printed scales on one or both sides for logarithms, exponents, roots, trigonometry, and sometimes more. A slide rule uses these scales to readily perform calculations. The basic principle is using logarithms to replace multiplication with addition. They advance calculation from simply counting to exploiting the relationships between numbers.

Most slide rules are linear ‘sticks’ that resemble everyday rulers. There are also circular and even cylindrical slide rules that extend the linear scales, fitting equivalent calculating power into a more compact device. There are also scales on the movable bar in the middle (slider). Scales are slid into position to set up a particular calculation, and the result is obtained using a precise cursor. The resolution of the scales (and the user’s eyesight) determine the precision of calculations. It is reasonable to get several significant digits at least.

Abacus

Counting is one of the most powerful human capabilities. In ancient times, common objects such as pebbles were used as abstract symbols to represent possessions to be tallied and traded. Simple arithmetic soon followed, greatly augmenting the ability of merchants and planners to manipulate large inventories and operations. Manipulating pebbles on lined or grooved ‘counting tables’ was improved upon by a more robust and easy to use device – the abacus. The name ‘abacus’ comes from Latin which in turn used the Greek word for ‘table’ or ‘tablet’. The abacus also had the advantage of being portable and usable cradled in one arm, a harbinger of the pocket calculator.

Variants included Roman, Chinese, Japanese, Russian, etc. Most commonly, they worked in base 10 with upper beads representing fives and lower beads representing ones. Vertical rods represented powers of 10, increasing right to left. Manual operation proceeded from left to right, with knowing the complement of a number being the only tricky part (eg. the complement of 7 is 10-7=3). The basic four operations + – x ÷ were fairly easy to learn, mechanical procedures. One did not have to be formally educated to learn to use an abacus, as opposed to pencil and paper systems. This was computation for the masses.

The abacus was one of the most successful inventions in history. In fact, it’s still in use today, mostly in small Asian shops. It is a universal and aesthetic symbol of our ancient love of counting.

Concatenative Biology

There are several ways to categorize programming languages. One is to distinguish between applicative and concatenative evaluation. Most languages are applicative – functions are applied to data. In contrast, a concatenative language moves a single store of data or knowledge along a ‘pipeline’ with a sequence of functions each operating on the store in turn. The output of one function is the input of the next function, in a ‘threaded’ fashion. This sequence of functions is the program. Forth is an example of a concatenative language, with the stack serving as the data store that is passed along the thread of functions (‘words’). “Forth is a simple, natural computer language” – Charles Moore, inventor of Forth.

One of the great advantages of concatenative languages is the opportunity for extreme simplicity. Since each function really only needs to know about its own input, machinery, and output, there is a greatly reduced need for overall architecture. The big picture, or state, of the entire program is neither guiding nor informing each step. As long as a function can read, compute, and write, it can be an entity unto itself, with little compliance or doctrine to worry about. In fact, in Forth, beyond the stack and the threaded execution model, there’s precious little doctrine anyway! Program structure is a simple sequence, with new words appended to the list (concatenated). The task of the programmer is just to get each word right, then move on to the next.

In nature, the concatenative approach is the only game in town. Small genetic changes occur due to several causes, random mutation being one of them. Each change is then put through the survivability sieve of natural selection, with large changes accumulating over large time scales (evolution). (Evolution is active across the entire spectrum of abstraction levels. Hierarchies emerge naturally, not through doctrine or design.) Concatenation is the way by which these small changes are accumulated. Much of the epic and winding road of human evolution is recorded in our DNA, which is billions of letters long.

This process can be seen happening right now in molecular biology. Consider the ribosome. This is the little machine inside a cell that reads a piece of RNA (a chain of nucleotides) and translates it into a protein (a chain of amino acids). There is no Master Control Program assigning names, delegating work, and applying functions. There is only a concatenative program, built up over the ages by evolution. So, basic life uses a fairly powerful and successful form of computation: DNA for storage, RNA for code, ribosome for computing, protein for application.
(and natural selection for testing) 🙂

We flatter ourselves when we talk of our ‘invention’ of levers, gears, factories, and computers. Nature had all that stuff and much more long before we ever came down from the trees. Math, engineering, and science are great not because of their products, but rather because they enable 3-pound hominid brains to explore nature and ponder the possibilities.

_{Originally posted Aug 12, 2014 in www.scidata.ca}