Tag Archives: AI

TTM: Time To MegaHAL

2 Replies

It seems that my Time To MegaHAL, or TTM, is about six weeks.

I’ll explain. What generally happens is this:

  1. I start a new job, and meet a whole new bunch of people.
  2. After about six weeks, someone suddenly mentions “hey, you’re that MegaHAL guy”!

It happened just today. My new boss, at a job I started six weeks ago, suddenly made the connection when a good friend of his published an interesting post about cobe, an optimised and much improved reverse-engineered rewrite of MegaHAL, written in Python and using SQLite as a storage back-end. A nice piece of work, although I’m a bit ashamed that someone had to wade through my 16-year-old vanilla C code to try to figure our what the bloody hell is going on :)

Of course, this will probably help to knock me out of my summertime hiatus. Things have been quite on the blogging front lately, what with moving into our new house just prior to Christmas and starting a new job first thing in the New Year. Now that our new place is looking more like a home and less like a cardboard box wholesaler, it’s time to sit back, take stock and figure out what’s next.

For me, that’s as follows:

Although, really, the first item on the list should really be “get more sleep, and exercise”.

Exciting times!

MegaHAL

5 Replies

One of my sabbatical projects is MegaHAL.10, an entirely new version of the mildly popular chatterbot that I wrote and put online fifteen years ago. I’ve been writing it in Google’s Go programming language, and I recently started getting some exciting results.

MegaHAL.10 generates sentences using a second-order Markov model. That means they tend to be random walks; you start out with a blank slate, and you never know where you’ll end up. The only guarantee is that any sequence of three symbols will have previously been observed by the model.

These kinds of random generations may be quite amusing, but they’re not too useful when you’re trying to simulate a conversation, which requires that each generation adheres to the current context. What would be much better is if you could force the model to generate a sentence that has the desired Markovian properties, but which contains pre-determined keywords.

With the original MegaHAL I did this by starting at the keyword and using two Markov models to generate the sentence, one proceeding from the keywords forwards to the end of the sentence, and the other going in the opposite direction. That was a bit of a hack, and could only guarantee that the sentence contains a single keyword.

For MegaHAL.10 I’ve been experimenting with other strategies, including a Fractal slot-filling model and a family of Markov models, each of which generates towards a specified target symbol. Both of these took a template sentence as input, which specified the keywords and their order, and both suffered from several problems, such as the fact that it may be impossible to complete the template, and that the local grammaticalness condition may need to be violated to make the keywords join up.

Recently I had a brainwave: what if we generated with the standard Markov model, but weighted the generations based on another model that specified the distance to the desired keyword. We could then generate a directed random walk, similar to an A* pathfinding algorithm. We may not be able to guarantee that the resulting sentence contains the keywords we want, but chances are it will contain at least a few.

Some bugs still need to be ironed out (and some wrinkles squished), but my tests so far indicate that this method may be the missing link. I trained MegaHAL.10 on the entire collection of Sherlock Holmes stories, and then I asked it to generate a random sentence, specifying these ten keywords in advance:

adventure foot wild scandal street twenty death finger villain rock

This is the sentence I got (I’ve highlighted the keywords):

“Twenty had changed their position, and the street by the death of the adventure of the ROCK OF GIBRALTAR. From the dead scientist.  His wild flight to escape from her finger into the garden.  Perhaps the villain was able to take counsel how far we can hardly put my foot over the case of this question. I saw that a very remarkable man, that was this William doing there is to avoid scandal.”

To me that’s completely amazing. “Give me a sentence containing these ten words”, I said, “making sure that each sequence of three words in your sentence appears somewhere in the collected Sherlock Holmes stories.” And MegaHAL.10 delivered.

Just to prove it wasn’t a fluke, here are a few more, using the same keywords:

“Twenty or thirty, I have seen death in the street by a strong family resemblance about misdeeds, and if you know now and so I dipped my finger on the ledge above the other hand had dropped his mask of his foot than might at any time before he was wild, wayward, and to our young companion looked at the young diplomatist’s window. There was this dark business which had been in the young lady.”

“Villain! Scoundrel!” cried the old quarters. At the foot of the death of the street. Holmes looked eagerly round for it was twenty before her in the dead scientist.  His wild eyes, stained cheeks and He put a triumphant conclusion.

“Death from some little distance down the street by a very simple chain: 1. You had a wild thrill as this was at the foot of the rock on each side of the adventure as a great scandal threatened to raise a scandal may well be cleared along those lines. Mr.  Douglas has spent a large coil from under the three strips. No finger impressions–no! Well, he is not here as I was at the other night.”

I’m planning to spend next week improving this algorithm, fixing various bugs, and optimising for memory and speed. I’ll then set to work creating a web version of MegaHAL.10, which will hopefully be going live before the end of the month.

XYZZY

4 Replies

I really love text adventure games. I’ve always had a fascination with natural language processing (my postgrad research was about computational grammatical inference after all), so part of the fun was figuring out how the parser works, and applying that knowledge to write my own text adventures in BASIC on the C64.

Zork

A classic text adventure. Image by Peter Scheyen.

These days there are great tools for writing text adventure games. The best would have to be Inform 7, which lets you write text adventures that are compatible with the Infocom Z-Machine (and thereby playable on a whole bunch of platforms, including the iPhone). Code written in Inform looks like this:

Insane, right? You should try it out. It’s pretty amazingly great.

If you’re not interested in writing your own text adventures, but you do enjoy playing them, then you’ll be pleased to know that there’s a vibrant community that continues to produce wonderful games (and who would prefer it if they were referred to as “interactive fiction”, thank-you very much). If you want to play the very best of these modern text adventures (sorry), then you could do worse than check out the winning entries of the Interactive Fiction Competition, which has been running for the past fifteen years. Heck, you can even play them in your browser, with Parchment (a z-machine interpreter written in JavaScript).

Speaking of text adventures, I’ve recently received my copy of Get Lamp, the text adventure documentary. Perhaps a screening is in order?

Pseudo Intelligence as Entertainment

4 Replies

Research can be speculative or applied. Artificial Intelligence research is often both, trying to solve real-world problems while at the same time testing theories about how the human brain works.

Man Playing Game

Game Face. Photo By: Phillip Toledano

A branch of the AI research crowd are interested in games both as a testbed for theoretical work and as a market for applied AI. Unfortunately, these are conflicting goals.

People play games to be entertained, and any AI present in the game must contribute to this. I personally think that AI enhances player enjoyment when it is both surprising and relevant. That is, it should result in an experience which feels new, yet which is consistent in the current context.

This regrettably suggests that AI is synonymous with NPCs, which is a mistake that both game players and researchers make. There are plenty of opportunities for non-NPC AI in games, and yet there is scant research being done in these areas. I’m referring to things such as

  • a cinematic camera that responds realistically to game world events and player movement;
  • dynamic set pieces, including chase sequences and fights;
  • story events that fit the overarching narrative but which adapt to a sandbox environment;
  • an audio score that foreshadows unscripted events and announces the presence of hero characters;
  • large-scale crowd and vehicle simulation;
  • adaptive character animation and movement;
  • accurate matchmaking algorithms for multiplayer online games;
  • elegantly handling dropouts with automatic AI takeover;
  • automatic navmesh generation from a polygon soup;
  • predicting player behaviour to counteract controller and network lag; and
  • automatic exploit detection and prevention.

The problem is that the role of the (usually lone) AI programmer on a game development team often involves many tasks that get in the way of performing research, including asset acquisition, audio and animation integration, data production, tool implementation and support, multithreading support, optimisation, debugging and so on, leaving a perfect opportunity for academia to supply the research chops. What’s needed are robust, efficient, designer-tweakable techniques that are easy to debug, and which scale with available CPU and memory. Sadly these requirements are not a priority for researchers, and yet researchers remain perplexed that game developers don’t use some of the inefficient, unpredictable techniques that they develop.

You see, the problem is that your neat little algorithm might perform well 95% of the time, which may be a great improvement over the state-of-the-art, and which may justify publication, but 95% is not good enough when you have an audience of 5 million game players (as hundreds of thousands of them will see broken behaviour).

But the biggest point of contention between game developers and researchers is that we gamedevs think that cheating is acceptable. After all, a game is just a Turing Test, with the player deciding whether intelligence exists based on the behaviour they perceive, so why not use all available information to deliver on that promise, instead of placing artificial restrictions on what data can be used based on whether or not it would be available to a human player? It just doesn’t matter how the behaviour is achieved – we’re not looking for insights into how the human brain works – it’s all down to player experience. This behavioural approach is out of favour with researchers (and has been ever since Chomsky defeated Skinner), but is the core of pragmatic game design. Perhaps never the twain shall meet.