Monday, January 25, 2016

Some rules for the modern scientist

If you don't make your papers publicly available on your webpage, you don't want people to read them. Making them available means providing a link to a downloadable version in pdf format, preferably hosted on your own web site. You cannot blame anyone for not reading and citing your work if it cannot very easily be found online without a paywall. All respectable academic publishers allow self-archiving of publications these days; if they don't allow it, they are not respectable.

If you don't have a Google Scholar profile, you don't want to be hired. Like it or not, citation counts and h-index are among the least bad metrics for evaluating researchers. And like it or not, metrics are necessary because people on hiring committees do not really have the time to read your papers on detail, nor do they typically have the necessary context to understand their significance.

If you never try to describe your research in more popular terms than an academic paper, you don't want anyone outside your field to know about what you are doing. All academic fields are full of jargon which acts as an effective deterrent to non-specialists understanding your work. Every so often, try to give a public lecture, write a blog post or record a video that explains your work so that ordinary people would understand it. Skip the jargon. Your target audience could be your high school friends who became hair dressers or car mechanics, or why not your parents. Don't forget to ask someone from your target audience if they understood what you wrote or talked about. You will learn a lot.

If you don't network with your research colleagues on Facebook and/or Twitter, you don't really care about keeping up to date with what happens in your research community. Conferences happen only a few times per year, and research happens faster than that. Mailing lists are mainly used for calls for papers. Your peers will talk about events, papers, ideas, results online. To stay relevant, you need to keep up to date on what's happening. If you desperately want to keep your private life online separate from your professional life, create alternate social network accounts for professional networking. But really, if you are passionate about your research, why would you want to keep it separate from your private life?

Monday, January 11, 2016

Why video games are essential for inventing artificial intelligence

The most important thing for humanity to do right now is to invent true artificial intelligence (AI): machines or software that can think and act independently in a wide variety of situations. Once we have artificial intelligence, it can help us solve all manner of other problems.

Luckily, thousands of researchers around work on inventing artificial intelligence. While most of them work on ways of using known AI algorithms to solve new problems, some work on the overarching problem of artificial general intelligence. I do both. As I see it, addressing applied problems spur the invention of new algorithms, and the availability of new algorithms make it possible to address new problems. Having concrete problems to try to solve with AI is necessary in order to make progress; if you try to invent AI without having something to use it for, you will not know where to start. My chosen domain is games, and I will explain why this is the most relevant domain to work on if you are serious about AI.

I talk about this a lot. All the time, some would say.

But first, let us acknowledge that AI has gotten a lot of attention recently, in particular work on "deep learning" is being discussed in mainstream press as well as turned into startups that get bought by giant companies for bizarre amounts of money. There have been some very impressive advances during the past few years in identifying objects in images, understanding speech, matching names to faces, translating text and other such tasks. By some measures, the winner of the recent ImageNet contest is better than humans at correctly naming things in images; sometimes I think Facebook's algorithms are better than me at recognizing the faces of my acquaintances.
Example image from the ImageNet competition. "Deep" neural networks have been made to learn to label images extremely well lately. Image courtesy of image-net.org.

With few exceptions, the tasks that deep neural networks have excelled at are what are called pattern recognition problems. Basically, take some large amount of data (an image, a song, a text) and output some other (typically smaller) data, such as a name, a category, another image or a text in another language. To learn to do this, they look at tons of data to find patterns. In other words, the neural networks are learning to do the same work as our brain's sensory systems: sight, hearing, touch and so on. To a lesser extent they can also do some of the job of our brain's language centra.

However, this is not all that intelligence is. We humans don't just sit around and watch things all day. We do things: solve problems by taking decisions and carrying them out. We move about and we manipulate our surroundings. (Sure, some days we stay in bed almost all day, but most of the rest of the time we are active in one way or another.) Our intelligence evolved to help us survive in a hostile environment, and doing that meant both reacting to the world and planning complicated sequences of actions, as well as adapting to changing circumstances. Pattern recognition - identifying objects and faces, understanding speech and so on - is an important component of intelligence, but should really be thought of as one part of a complete system which is constantly working on figuring out what to do next. Trying to invent artificial intelligence while only focusing on pattern recognition is like trying to invent the car while only focusing on the wheels.

In order to build a complete artificial intelligence we therefore need to build a system that takes actions in some kind of environment. How can we do this? Perhaps the most obvious idea is to embody artificial intelligence in robots. And indeed, robotics has shown us how even the most mundane tasks, such as walking in terrain or grabbing strangely shaped objects, are really rather hard to accomplish for robots. In the eighties, robotics research largely refocused on these kind of "simple" problems, which led to progress in applications as well as a better understanding of what intelligence is all about. The last few decades of progress in robotics has fed into the development of self-driving cars, which is likely to become one of the areas where AI technology will revolutionize society in the near future.

Once upon a time, when I thought I was a roboticist of sorts. The carlike robot in the foreground was supposed to learn to independently drive around the University of Essex campus (in the background). I think it's fair to say we underestimated the problem. (From left to right: me (now at NYU), Renzo de Nardi (Google), Simon Lucas (Essex), Richard Newcombe (Facebook/Oculus), Hugo Marques (ETH Zurich).)

Now, working with robots clearly has its downsides. Robots are expensive, complex and slow. When I started my PhD, my plan was to build robot software that would learn evolutionarily from its mistakes in order to develop increasingly complex and general intelligence. But I soon realized that in order for my robots to learn from their experiences, they would have to attempt each task thousands of times, with each attempt maybe taking a few minutes. This meant that even a simple experiment would take several days - even if the robot would not break down (it usually would) or start behaving differently as the batteries depleted or motors warmed up. In order to learn any more complex intelligence I would have to build an excessively complex (and expensive) robot with advanced sensors and actuators, further increasing the risk of breakdown. I also would have to develop some very complex environments where complex skills could be learned. This all adds up, and quickly becomes unmanageable. Problems such as these is why the field of evolutionary robotics has not scaled up to evolve more complex intelligence.
The basic idea of evolutionary robotics: use Darwinian evolution implemented as a computer algorithm to teach robot AIs (for example neural networks) to solve tasks. Image taken from a recent survey paper.

I was too ambitious and impatient for that. I wanted to create complex intelligence that could learn from experience. So I turned to video games.

Games and artificial intelligence have a long history together. Even since before artificial intelligence was recognized as a field, early pioneers of computer science wrote game-playing programs because they wanted to test whether computers could solve tasks that seemed to require "intelligence". Alan Turing, arguably the principal inventor of computer science, (re)invented the Minimax algorithm and used it to play Chess. (As no computer had been built yet, he performed the calculations himself using pen and paper.) Arthur Samuel was the first to invent the form of machine learning that is now called reinforcement learning; he used it in a program that learned to play Checkers by playing against itself. Much later, IBM's Deep Blue computer famously won against the reigning grandmaster of Chess, Gary Kasparov, in a much-publicized 1997 event. Currently, many researchers around the world work on developing better software for playing the board game Go, where the best software is still no match for the best humans.

Arthur Samuel in 1957, playing checkers against a mainframe computer the size of a room and thousands of times less computer power than your phone. The computer won. 

Classic board game such as Chess, Checkers and Go are nice and easy to work with as they are very simple to model in code and can be simulated extremely fast - you could easily make millions of moves per second on a modern computer - which is indispensable for many AI techniques. Also, they seem to require thinking to play well, and have the property that they take "a minute to learn, but a lifetime to master". It is indeed the case that games have a lot to do with learning, and good games are able to constantly teach us more about how to play them. Indeed, to some extent the fun in playing a game consists in learning it and when there is nothing more to learn we largely stop enjoying them. This suggests that better-designed games are also better benchmarks for artificial intelligence. However, judging from the fact that now have (relatively simple) computer programs that can play Chess better than any human, it is clear that you don't need to be truly, generally intelligent to play such games well. When you think about it, they exercise only a very narrow range of human thinking skills; it's all about turn-based movements on a discrete grid of a few pieces with very well-defined, deterministic behavior.

Deep Blue beats Kasparov in Chess.


But, despite what your grandfather might want you to believe, there's more to games than classical board games. In addition to all kinds of modern boundary-pushing board games, card games and role-playing games, there's also video games. Video games owe their massive popularity at least partly to that they engage multiple senses and multiple cognitive skills. Take a game such as Super Mario Bros. It requires you not only to have quick reactions, visual understanding and motoric coordination, but also to plan a path through the level, decide about tradeoffs between various path options (which include different risks and rewards), predict the future position and state of enemies and other characters of the level, predict the physics of your own running and jumping, and balance the demands of limited time to finish the level with multiple goals. Other games introduce demands of handling incomplete information (e.g. StarCraft), understanding narrative (e.g. Skyrim), or very long-term planning (e.g. Civilization).

A very simple car racing game I hacked up for a bunch of experiments that went into my PhD thesis. We also used it for a competition.

On top of this, video games are run inside controllable environments in a computer and many (though not all) video games can be sped up to many times the original speed. It is simple and cheap to get started, and experiments can be run many thousand times in quick succession, allowing the use of learning algorithms.

After the first year, the Simulated Car Racing Competition switched to the TORCS racing game, which is more advanced. It also undeniably looks better.

So it is not surprising that AI researchers have increasingly turned to video games as benchmarks recently. Researchers such as myself have adapted a number of video games to function as AI benchmarks. In many cases we have organized competitions where researchers can submit their best game-playing AIs and test them against the best that other researchers can produce; having recurring competitions based on the same game allows competitors to refine their approaches and methods, hoping to win next year. Games for which we have run such competitions include Super Mario Bros (paper), StarCraft (paper), the TORCS racing game (paper), Ms Pac-Man (paper), a generic Street Fighter-style figthing game (paper), Angry Birds (paper), Unreal Tournament (paper) and several others. In most of these competitions, we have seen performance of the winning AI player improve every time the competition is run. These competitions play an important role in catalyzing research in the community, and every year many papers are published where the competition software is used for benchmarking some new AI method. Thus, we advance AI through game-based competitions.

There's a problem with the picture I just painted. Can you spot it?

That's right. Game specificity. The problem is that improving how well an artificial intelligence plays a particular game is not necessarily helping us improve artificial intelligence in general. It's true that in most of the game-based competitions mentioned above we have seen the submitted AIs get better every time the competition ran. But in most cases, the improvements were not because of better AI algorithms, but because of even more ingenious ways of using these algorithms for the particular problems. Sometimes this meant relegating the AI to a more peripheral role. For example, in the car racing competition the first years were dominated by AIs that used evolutionary algorithms to train a neural network to keep the car on the track. In later years, most of the best submissions used hand-crafted "dumb" methods to keep the car on the track, but used learning algorithms to learn the shape of the track to adapt the driving. This is a clever solution to a very specific engineering problem but says very little about intelligence in general.
The game Ms. Pac-Man was used in a successful recent AI competition, which saw academic researchers, students and enthusiasts from around the world submit their AI Pac-Man players. The challenge of playing Pac-Man spurred researchers to invent new versions of state-of-the-art algorithms to try to get ahead. Unfortunately, the best computer players so far are no better than an intermediate human.
In order to make sure that what such a competition measures is anything approaching actual intelligence, we need to recast the problem. To do this, it's a great idea to define what it is we want to measure: general intelligence. Shane Legg and Marcus Hutter have proposed a very useful definition of intelligence, which is roughly the average performance of an agent on all possible problems. (In their original formulation, each problem's contribution to the average is weighed by its simplicity, but let's disregard that for now.) Obviously, testing an AI on all possible problems is not an option, as there are infinitely many problems. But maybe we could test our AI on just a sizable number of diverse problems? For example on a number of different video games?

The first thing that comes to mind here is to just to take a bunch of existing games for some game console, preferably one that could be easily emulated and sped up to many times real time speed, and build an AI benchmark on them. This is what the Arcade Learning Environment (ALE) does. ALE lets you test your AI on more than a hundred games released for 70s vintage Atari 2600 console. The AI agents get feeds of the screen at pixel level, and have to respond with a joystick command. ALE has been used in a number of experiments, including those by the original developers of the framework. Perhaps most famously, Google Deep Mind published a paper in Nature showing how they could learn to play several of the games with superhuman skill using deep learning (Q-learning on a deep convolutional network).

The Atari 2600 video game console. Note the 1977-vintage graphics of the Combat game on the TV in the background. Note, also, the 1977-vintage wooden panel. Your current game console probably suffers from a lack of wooden panels. Not in picture: 128 bytes of memory. That's a few million times less than your cell phone.

ALE is an excellent AI benchmark, but has a key limitation. The problem with using Atari 2600 games is that there is only a finite number of them, and developing new games is a trick process. The Atari 2600 is notoriously hard to program, and the hardware limitations of the console tightly constrain what sort of games can be implemented. More importantly, all of the existing games are known and available to everyone. This makes it possible to tune your AI to each particular game. Not only to train your AI for each game (DeepMind's results depend on playing each game many thousands of times to train on it) but to tune your whole system to work better on the games you know you will train on.

Can we do better than this? Yes we can! If we want to approximate testing our AI on all possible problems, the best we can do is to test it on a number of unseen problems. That is, the designer of the AI should not know which problems it is being tested on before the test. At least, this was our reasoning when we designed the General Video Game Playing Competition.

"Frogger" for the Atari 2600.

The General Video Game Playing Competition (GVGAI) allows anyone to submit their best AI players to a special server, which will then use them to play ten games that no-one (except the competition organizers) have seen before. These games are of the type that you could find on home computers or in arcades in the early eighties; some of them are based on existing games such as Boulder Dash, Pac-Man, Space Invaders, Sokoban and Missile Command. The winner of the competition is the AI that plays these unseen games best. Therefore, it is impossible for the creator of the AI to tune their software to any particular game. Around 50 games are available for training your AI on, and every iteration of the competition increases this number as the testing games from the previous iteration become available to train on.

"Frogger" implemented in VGDL in the General Video Game Playing framework.

Now, 50 games is not such a large number; where do we get new games from? To start with, all the games are programmed in something called the Video Game Description Language (VGDL). This is a simple language we designed to to be able to write games in a compact and human-readable way, a bit like how HTML is used to write web pages. The language is designed explicitly to be able to encode classical arcade games; this means that the games are all based on the movement of and interaction sprites in two dimensions. But that goes for essentially all video games before Wolfenstein 3D. In any case, the simplicity of this language makes it very easy to write new games, either from scratch or as variations on existing games. (Incidentally, as an offshoot of this project we are exploring the use of VGDL as a prototyping tool for game developers.)

A simple version of the classic puzzle game Sokoban implemented in VGDL.

Even if it's simple to write new games, that doesn't solve the fundamental problem that someone has to write them, and design them first. For the GVG-AI competition to reach its full potential as a test of general AI, we need an endless supply of new games. For this, we need to generate them. We need software that can produce new games at the press of a button, and these need to be good games that are not only playable but also require genuine skill to win. (As a side effect, such games are likely to be enjoyable for humans.)

Boulder Dash implemented in VGDL in the General Video Game Playing framework.

I know, designing software that can design complete new games (that are also good in some sense) sounds quite hard. And it is. However, I and a couple of others have been working on this problem on and off for a couple of years, and I'm firmly convinced it is doable. Cameron Browne has already managed to build a complete generator for playable (and enjoyable) board games, and some of our recent work has focused on generating simple VGDL games, though there is much left to do. Also, it is clearly possible to generate parts of games, such as game levels; there has been plenty of research within the last five years on procedural content generation - the automatic generation of game content. Researchers have demonstrated that methods such as evolutionary algorithms, planning and answer set programming can automatically create levels, maps, stories, items and geometry, and basically any other content type for games. Now, the research challenges are to make these methods general (so that they work for all games, not just for a particular game) and more comprehensive, so that they can generate all aspects of a game including the rules. Most of the generative methods include some form of simulation of the games that are being generated, suggesting that the problems of game playing and game generation are intricately connected and should be considered together whenever possible.
Yavalath, a board game designed by computer program designed by Cameron Browne. Proof that computers can design complete games.
Once we have extended the General Video Game Playing Competition with automated game generation, we have a much better way of testing generic game-playing ability than we have ever had before. The software can of course also be used outside of the competition, providing a way to easily test the general intelligence of game-playing AI.

So far we have only talked about how to best test or evaluate the general intelligence of a computer program, not how to best create one. Well, this post is about why video games are essential for inventing AI, and I think that I have explained that pretty well: they can be used to fairly and accurately benchmark AIs. But for completeness, let us consider which are the most promising methods for creating AIs of this kind. As mentioned above, (deep) neural networks have recently attracted lots of attention because of some spectacular results in pattern recognition. I believe neural networks and similar pattern recognition methods will have an important role to play for evaluating game states and suggesting actions in various game states. In many cases, evolutionary algorithms are more suitable than gradient-based methods when training neural networks for games.

But intelligence can not only be pattern recognition. (This is for the same reason that behaviorism is not a complete account of human behavior: people don't just map stimuli to responses§, sometimes they also think.) Intelligence must also incorporate some aspect of planning, where future sequences of actions can be played out in simulation before deciding what to do. Recently an algorithm called Monte Carlo Tree Search, which simulates the consequences of long sequences of actions by doing statistics of random actions, has worked wonders on the board game Go. It has also done very well on GVGAI. Another family of algorithms that has recently shown great promise on game planning tasks is rolling horizon evolution. Here, evolutionary algorithms are used not for long-term learning, but for short-term action planning.

I think the next wave of advances in general video game-playing AIs will come from ingenious combinations of neural networks, evolution and tree search. And from algorithms inspired by these methods. The important thing is that both pattern recognition and planning will be necessary in various different capacities. As usual in research, we cannot predict what will work well in the future (otherwise it wouldn't be called research), but I bet that exploring various combinations of these method will inspire the invention of the next generation of AI algorithms.

A video game such as The Elder Scrolls V: Skyrim requires a wide variety of cognitive skills to play well.

Now, you might object that this is a very limited view of intelligence and AI. What about text recognition, listening comprehension, storytelling, bodily coordination, irony and romance? Our game-playing AIs can't do any of this, no matter if it can play all the arcade games in the world perfectly. To this I say: patience! None of these things are required for playing early arcade games, that is true. But as we master these games and move on to include other genres of games in our benchmark, such as role-playing games, adventure games, simulation games and social network games, many of these skills will be required to play well. As we gradually increase the diversity of games we include in our benchmark, we will also gradually increase the breadth of cognitive skills necessary to play well. Of course, our game-playing AIs will have to get more advanced to cope. Understanding language, images, stories, facial expression and humor will be necessary. And don't forget that closely coupled with the challenge of general video game playing is the challenge of general video game generation, where plenty of other types of intelligence will be necessary. I am convinced that video games (in general) challenges all forms of intelligence except perhaps those closely related to bodily movement, and therefore that video game (in general) is the best testbed for artificial intelligence. An AI that can play almost any video game and create a wide variety of video games is, by any reasonable standard, intelligent.

"But why, then, are not most AI researchers working on general video game playing and generation?"
To this I say: patience!

A game such as Civilization V requires a different, but just as wide, skillset to play well.

This blog post became pretty long - I had really intended it to be just a fraction of what it is. But there was so much to explain. In case you've read this far, you might very well have forgotten what I said in the beginning by now. So let me recapitulate:

It is crucial for artificial intelligence research to have good testbeds. Games are excellent AI testbeds because they pose a wide variety of challenges, similarly to robotics, and are highly engaging. But they are also simpler, cheaper and faster, permitting a lot of research that is not practically possible with robotics. Board games have been used in AI research since the field started, but in the last decade more and more researchers have moved to video games because they offer more diverse and relevant challenges. (They are also more fun.) Competitions play a big role in this. But putting too much effort into AI for a single game has limited value for AI in general. Therefore we created the General Video Game Playing Competition and its associated software framework. This is meant to be the most complete game-based benchmark for general intelligence. AIs are evaluated on playing not a single video game, but on multiple games which the AI designer has not seen before. It is likely that the next breakthroughs in general video game playing will come from a combination of neural networks, evolutionary algorithms and Monte Carlo tree search. Coupled with the challenge of playing these games, is the challenge of generating new games and new content for these games. The plan is to have an infinite supply of games to test AIs on. While playing and generating simple arcade games tests a large variety of cognitive capacities - more diverse than any other AI benchmark - we are not yet at the stage where we test all of intelligence. But there is no reason to think we would not get there, given the wide variety of intelligence that is needed to play and design modern video games.

If you want to know more about these topics, I've linked various blog posts, articles and books from the text above. Most of the research I'm doing (and that we do in the NYU Game Innovation Lab) is in some way connected to the overall project I've been describing here. I recently put together a little overview of research I've done in the past few years, with links to most of my recent papers. Many more papers can be found on my web page. It is also important to realize that most of this work has a dual purpose: to advance artificial intelligence and to make games more fun. Many of the technologies that we are developing are to a lesser or greater extent focused on improving games. It's important to note that there is still important work to be done in advancing AI for particular games. In another recent blog post, I tried to envision what video games would be like if we had actual artificial intelligence. A somewhat recent paper I co-wrote tries to outline the whole field of AI in games, but it's rather long and complex so I would advise you to read the blog post first. You can also peruse the proceedings of the Computational Intelligence and Games and Artificial Intelligence and Interactive Digital Entertainment conference series.

Finally, it's important to note that there is plenty of room to get involved in this line of research (I think of it all as an overarching meta-project) as there are many, many open research questions. So if you are not already doing research on this I think you should start working in this field. It's exciting, because it's the future. So what are you waiting for?

Tuesday, November 17, 2015

Neuroevolution in games

Neuroevolution - the evolution of weights and/or topology for neural networks - is a common and powerful method in evolutionary robotics and machine learning. In the last decade or so, we have seen a large number of applications of neuroevolution in games. Evolved neural networks have been used to play games, model players, generate content and even enable completely new game genres. To some extent, games seem to be replacing the small mobile robots ubiquitous in evolutionary robotics and simple benchmarks used in reinforcement learning research.

Sebastian Risi and I have written a survey on neuroevolution in games, including a discussion of future research challenges. The main reason is that there was no survey of neuroevolution in games in existence; the other reason was that we wanted a tutorial overview to hand out to the students in our Modern AI for Games course.

A while back we asked the community to send us comments and suggestions for important work we might have overlooked. We received a lot of useful input and incorporated most of the suggested work. Thank you for very much for the help!

Now we are happy to announce that the paper will finally be published in the IEEE Transactions on Computational Intelligence and AI in Games (TCIAIG). We hope you like it!

TCIAIG early access:
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7307180

A preprint of the manuscript is available here:
http://arxiv.org/pdf/1410.7326v3.pdf

Wednesday, October 07, 2015

What if videogames had actual AI?

Is there any artificial intelligence in a typical videogame? Depends on what you mean. The kind of AI that goes into games typically deal with pathfinding and expressing behaviors that were designed by human designers. The sort of AI that we work on in university research labs is often trying to achieve more ambitious goals, and therefore often not yet mature enough to use in an actual game. This article has an excellent discussion of the difference, including a suggestion (from Alex Champandard) that the "next giant leap of game AI is actually artificial intelligence". And there's indeed lots of things we could do in games if we only had the AI techniques to do it.

So let's step into the future, and assume that many of the various AI techniques we are working on at the moment have reached perfection, and we could make games that use them. In other words, let's imagine what games would be like if we had good enough AI for anything we wanted to do with AI in games. Imagine that you are playing a game of the future.

You are playing an "open world" game, something like Grand Theft Auto or Skyrim. Instead of going straight to the next mission objective in the city you are in, you decide to drive (or ride) five hours in some randomly chosen direction. The game makes up the landscape as you go along, and you end up in a new city that no human player has visited before. In this city, you can enter any house (though you might have to pick a few locks), talk to everyone you meet, and involve yourself in a completely new set of intrigues and carry out new missions. If you would have gone in a different direction, you would have reached a different city with different architecture, different people and different missions. Or a huge forest with realistic animals and eremites, or a secret research lab, or whatever the game engine comes up with.

Talking to these people you find in the new city is as easy as just talking to the screen. The characters respond to you in natural language that takes into account what you just said. These lines are not read by an actor but generated in real-time by the game. You could also communicate with the game though waving your hands around, dancing, exhibiting emotions or other exotic modalities. Of course, in many (most?) cases you are still pushing buttons on a keyboard or controller, as that is often the most efficient way of telling the game what you want to do.

Perhaps needless to say, but all the non-player characters (NPCs) navigate and generally behave in a thoroughly believable way. For example, they will not get stuck running into walls or repeat the same sentence over and over (well, not more than an ordinary human would). This also means that you have interesting adversaries and collaborators to play any game with, without having to resort to waiting for your friends to come online or have to resort to being matched with annoying thirteen year olds.

Within the open world game, there are other games to play, for example by accessing virtual game consoles within the game or proposing to play a game with some NPC. These NPCs are capable of playing the various sub-games at whatever level of proficiency that fits with the game fiction, and they play with human-like playing styles. It is also possible to play the core game at different resolutions, for example as a management game or as a game involving the control of individual body parts, by zooming in or out. Whatever rules, mechanics and content are necessary to play these sub-games or derived games are invented by the game engine on the spot. Any of these games can be lifted out of the main game and played on its own.

The game senses how you feel while playing the game, and figures out which aspects of it you are good at as well as which parts you like (and conversely, which parts you suck at and despise). Based on this, the game constantly adapts itself to be more to your liking, for example by giving you more story, challenges and experiences that you will like in that new city which you reached by driving five hours in a randomly chosen direction. Or perhaps by changing its own rules. It's not just that the game is giving you more of what you already liked and mastered. Rather more sophisticatedly, the game models what you preferred in the past, and creates new content that answers to your evolving skills and preferences as you keep playing.

Although the game you are playing is endless, of infinite resolution and continuously adapts to your changing tastes and capabilities, you might still want to play something else at some point. So why not design and make your own game? Maybe because it's hard and requires lots of work? Sure, it's true that back in 2015 it required hundreds of people working for years to make a high profile game, and a handful of highly skilled professionals to make any notable game at all. But now that it's the future and we have advanced AI, this can be used not only inside of the game but also in the game design and development and process. So you simply switch the game engine to edit mode and start sketching a game idea. A bit of a storyline here, a character there, some mechanics over here and a set piece on top of it. The game engine immediately fills in the missing parts and provides you with a complete, playable game. Some of it is suggestions: if you have sketched an in-game economy but have no money sink, the game engine will suggest one for you, and if you have designed gaps that the player character can not jump over, the game engine will suggest changes to the gaps or to the jump mechanic. You can continue sketching, and the game engine will convert your sketches into details, or jump right in and start modifying the details of the game; whatever you do, the game engine will work with you to flesh out your ideas into a complete game with art, levels and characters. At any time you can jump in and play the game yourself, and you can also watch a number of artificial players play various parts of the game, including players that play like you would have played the game or like your friends (with different tastes and skills) would have played it.

If you ask me, I'd say that this is a rather enticing vision of the future. I'll certainly play a lot of games if this is what games will look like in a decade or so. But will they? Will we have the AI techniques to make all this possible? Well, me and a bunch of other people in the CI/AI in Games research community are certainly working on it. (Whether that means that progress is more or less likely to happen is another question...) My team and I are in some form working on all of the things discussed above, except the natural interaction parts (talking to the game etc).

If you are interested in knowing more about these topics, I recently wrote a blog post summarizing what I've been working on in the last few years. Last year, I also co-wrote a survey paper trying to give a panoramic overview of AI in games research and another survey paper about computational game creativity. Also, our in-progress book about procedural content generation covers many of these topics. You might also want to look at the general video game playing competition (and its results) and the sentient sketchbook and ropossum AI-assisted level design systems. For work on believable NPC behavior, check out the Mario AI Turing Test competition and procedural personas.

Finally, I've always been in favor of better collaboration between AI researchers and game developers. I wrote a post last year about why this collaboration doesn't always work so well, and what could be done about that.

Thursday, July 30, 2015

Revolutionary algorithms

Edit: Apparently it is not clear to everyone that the following post is satire. Well, it is.

You have surely heard about evolutionary algorithms and how they, inspired by Darwinian evolution in the natural world, are excellent general-purpose search and optimization algorithms. You might also know about neural networks, which are learning algorithms inspired by biological brains, and cellular automata, inspired by biological developmental processes. The success of these types of natural computation has spurred other attempts to base algorithms on natural phenomena, such as particle swarm optimization, ant colony routing, honey bees algorithm, and cat swarm optimization. These algorithms are popular not only for their biological inspiration but also for their proven performance on many hard computational problems.

However, in an era where unfettered market forces force bankruptcy upon liberal-democratic countries as a result of bank bailouts dictated by the global financial elite, the neoliberal ideological basis of such algorithms can be called into question. After all, they are based on a model of individual betterment at the expense of the weaker members of population, an all-consuming "creative" destruction process where disenfranchised individuals are ruthlessly discarded. "Survival of the fittest" describes the elimination process by which the invisible hand strangles the weak; "self-organization" is the capitalist excuse for exploiting non-unionized labor. Common evolutionary algorithm operators like survivor selection represent the violence inherent in the system.

But there is an alternative: algorithms for socially just optimization based on models of the workers' struggle and the liberation of the oppressed. While rarely discussed in major  (corporate-sponsored) conferences, revolutionary algorithms have certain similarities with  the better-known evolutionary algorithms. The basic structure of a revolutionary algorithm is as follows (Marks and Leanin 2005):


  1. Initialize the population with n individuals drawn at random.
  2. Evaluate all individuals to assign a fitness value to them; sort the population according to fitness.
  3. Remove the most fit part of the population (the "elite").
  4. Calculate the average fitness in the population; assign this fitness to all individuals.
  5. Increase fitness of the whole population linearly according to a five-generation plan.
  6. Repeat step 5 until maximum fitness has been reached.


As you surely understand, this simple scheme does away with the need for elimination of lower-performing individuals while assuring orderly fitness growth according to plan. Just like in evolutionary computation, a number of modifications to the basic scheme have been proposed, and proponents of the various "schools" that have grown up around specific types of algorithms do not always see eye to eye. Here are some of the most important new operators:


  • Forced population migration (Sztaln 2006): While in evolutionary computation much effort is is spent on diversity maintenance, in revolutionary computation it is important to counteract the damaging effects of diversity. Forced population migration moves whole parts of the population around in memory space, so as to counteract any dangerous clustering of similar individuals.
  • Continuous anti-elitism (Polpotte 2008): While standard revolutionary algorithms only cull the elite in the initialization phase, the radical scheme suggested by Polpotte eliminates the most-fit part of the population every generation. When no fitness differences can be discerned, which individuals to remove can be determined based on arbitrary factors.
  • Great leap mutation (Maocedong 2007): This modification of the basic scheme is particularly useful when the initial population has a very low average fitness. Here, the population is sorted into small "villages" and each village is told to accomplish its development goals on its own, including creating its own search operators.

More recently a newer generation of researchers have questioned some of the basic assumptions underlying revolutionary computation, such as the stable identity of individuals and the boundaries of the population array. The replacement of some parts of the population with others has been decried as a form colonialism. Revolutionary algorithms of the poststructuralist variety therefore eschew strict divisions between individuals and practice adding random variables to instruction pointers and array indexes. This naturally meets resistance from antiquated, orthonormative models of computation and operating systems. In this context, it is important to remember that "segmentation fault" is just a form of norm transgression.

In the end, those algorithms that are most efficient will win; society cannot afford substandard optimization. And in the same way as the success of evolutionary algorithms is predicated on the success of Darwinian evolution in nature, the success of revolutionary algorithms is predicated on the success of the ideologies and movements that they are modeled on.

(This post was inspired by discussions with Daan Wierstra, Mark Nelson, Spyros Samothrakis and probably others.)

Saturday, July 25, 2015

How not to review a paper

On occasion of several paper reviews I've received recently, and a few I've written, I'd like to give some useful tips for how to review a paper. That is, how to review a paper if you want to do a really, really bad job of it. Note that I work in the AI and Games field, so somewhat different advice might apply to screwing up a paper review in another field.

First of all, be vague. Say what you think about the paper in very abstract terms, and at all costs avoid pointing out specific flaws with the paper so that they could be easily fixed.

This applies most of all to any comments about the literature review. It's fine to point out that the literature review is missing important related work, but by no means include any references to said work. Ideally, say that the paper cannot be accepted because of glaring omissions in the references, and fail to provide a single paper they should have referenced.

If by any chance you think the paper you are reviewing should have referenced one of your own papers, then you should definitely not say so. Your papers are obviously of such brilliance that everybody already know about them by virtue of them being published somewhere. Instead, treat this omission of citation as a personal insult, and add a passive-agressive slant to your review.

If you find it hard to be abstract enough in your review, then you may consider doing the opposite: only talk about details. Talk at length about verb forms and the possible inclusion of semicolons, and if you have substantial comments about the methodology or results bury them as deep as you can in a wall of text. For maximum effect, use a stream-of-consciousness style where you jot things down as you read the paper, often digressing into reflections on various topics that reading the paper reminded you of. It's great if some of your later comments contradict your earlier comments. At the end of it all, issue an arbitrary accept/reject recommendation without explaining which of the numerous comments made you come to this conclusion.

It's imperative that you don't write any summary of your review, or the effect is lost.

If the language and tone of the paper is not exactly how you would have written it, urge the author(s) to enlist the help of a native English speaker to correct their English. This comment works best if you can tell that the authors are native English speakers, and if you carefully add some grammar and spelling mistakes to your review.

Speaking of how you would have written the paper, it's a good idea to evaluate the paper from the perspective of what you would have done if you wrote the paper. Say for example that the authors present an algorithm and are mostly interested in the algorithm's correctness, whereas you would personally be more interested in its runtime. Then it's perfectly fine to reject the paper because they studied the correctness and not the runtime of the algorithm, and they clearly should have studied the runtime instead. After all, you are the one reviewing the paper, so you should decide what it should be about.

In the same vein, don't just accept any definitions of terms or scoping of the investigation that the paper might contain. Read the paper using whatever meaning of the words in it that you find convenient. And if the authors state that they are not concerned with topic X, that is no reason for you to not go on at length about how important topic X is and why they should have included it.  It's your freedom to read the paper any way you want and assign any kind of meaning to it you like.

This brings to our final and perhaps most important piece of advice. It's likely that there is some part of the paper you don't understand, because like everybody else you are occasionally frequently out of your depth and these authors write like morons anyway. If this happens - don't admit it! Don't lose face by explaining that you don't understand the paper! Your reputation as an anonymous reviewer is at stake. Instead, simply pick at random some interpretation of the part of the paper you don't understand, preferably some interpretation that makes very little sense. Then write your review as if that interpretation was true. Hilarity ensues, at least on your side.

If you heed all this advice, you will surely be able to produce the kind of reviews that one frequently receives after submitting to some famous conferences and well-respected journals.

Friday, June 19, 2015

What I've been working on lately

It has been remarked upon that I publish a lot of papers on a number of topics. It might not be clear how they all fit together. What is it that I work on, really? Of course, I have no problems seeing how the various strands of my research inform each other and contribute towards a small set of common goals. But that might not be so easy for you to see.

So here's an incomplete selection of themes from my recent research, together with links to some relevant papers. For simplicity and for the sake of the length of this text vs your attention span, I will limit myself to work that I've published in the last two years. Note that though I've written code for some of the research systems myself, contributed with conceptual development to all of these papers, and written parts of almost all of them, most of the work below was done by my various students and other collaborators. That's why I'll use the academic "we" in the examples below, referring to my various groups of collaborators. I'm of course very happy that so many talented and hard-working people feel like attaching my name to the author lists of their papers, for one reason or another.

Generally, my research has the dual aim of using AI to enable better (or more interesting) games, and on using games to enable better AI. This means coming up with better game-playing algorithms, with algorithms that can perhaps also play games in a human-like manner, methods for generating complete games or part of games, studying games and players, and for using games to test AI algorithms. This all comes together, for example you cannot design a game without being able to play it and knowing how humans play it, and you can't advance your game-playing AI without having suitable games and levels to try it out on. Ultimately, we're aiming towards general AI that can not only play any game but also design any game, including the game that you seem to want to play right now. That's very general, so let's be more specific.

Procedural content generation

PCG, creating game content with algorithms, is sort of hot right now. For several reasons: if the computers create levels, items, quests etc we don't have to do it ourselves, so games could be endless, adapt to the player, be cheaper to produce etc. Also, creating a content generators is about defining and understanding a particular aesthetic. My various collaborators and me have been working on PCG for quite some time now (actually, since before it was hot) in particular exploring how to best use evolutionary algorithms for generating various forms of game content. We call this search-based PCG. Some examples of recent work includes basing Super Mario level generation on design patterns, evolving maps to advantage particular game-playing algorithms, and multiobjective and multimodal methods for strategy game map generation.  We've also introduced new algorithms like constrained novelty search and repurposed older methods such as n-grams for level generation. Understanding the output of these generative methods is very important, and for that reason we have developed ways of characterizing level generators, and generic metrics for level design. A major effort was to edit and write the first textbook on procedural content generation in games; earlier we wrote about goals and challenges for PCG research.

Mixed-initiative and AI-assisted game design

While having the computer create levels, items, quests etc all by itself is great, there's also room for collaboration with humans. Computers are good at some things and humans at others, and human designers might want to interfere at various points in the content creation process. Mixed-initiative PCG systems implement a dialogue between a designer and computer, where PCG processes assist the human designer while retaining the designer's freedom. Sentient Sketchbook is one such system, where humans design strategy game maps while algorithms critique the designs and offer suggestions; it also learns the designer's style. Another of our systems is Ropossum, which can generate complete levels for the physics puzzler Cut the Rope and also assist designers. It uses a combination of grammatical evolution, reasoning and tree search, but we have recently experimented with using object path projections for playability testing and with creating levels based on evolved (fictive) playtraces.

Data games

There's more digital available than ever before, including large amounts of open data that anyone can access. This includes geographical, economical and demographical data amongst other forms. Data games are games that are built on such data, in the sense that the game's content is generated from open data. We're trying to create ways to improve the generation of meaningful game content by seeding PCG with real-world data, but also make data exploration more playful. Our work involves data-based content generation for existing games such as Open Data Monopoly and Open Data Civilization, using game mechanics for data exploration and visualization such as in Open Trumps and Bar Chart Ball, and data-based procedural generation of complete games as in Data Adventures.

Generating complete games

The logical endpoint of PCG is generating the whole game, not just the levels and textures but all the rules and mechanics and everything else that's not the game engine. Even what the game is about and what the goal is. If we are to understand game design properly, we need to build systems that can generate good games; and if we want to test general AI properly we need an infinite supply of new games. We have argued that those game types that would be most realistic to try yo generate are classical board games and simple 2D arcade games; this is also what we have been attempting to generate earlier. Recently, we have invented ways of representing and generating card games, by searching through a space of card games that includes well-known games such as Texas Hold'em. We have also designed a Video Game Description Language which can be used to define simple card games, and invented ways of automatically evaluating the quality of such games and generating new games. It is also interesting to see how different games can be generated by simply varying the parameters of a simple existing game – in our work on generating unique Flappy Bird variants we found that plenty of playable yet different games can emerge.

MCTS for video games

In order to be able to generate games you need to test them, and to test them automatically you need AI that can play the games. Being able to play games is of course also important for other reasons, such as providing good opponents and collaborators to the player. Monte Carlo Tree Search is a statistical tree search algorithm that has been very successful in playing board games such as Go. We are trying to figure out how to adapt this algorithm to video games, that have very different requirements from board games - for example continuous space and time, as well as lack of guarantee that random actions will lead to a terminal state. In the course of this, we have developed a number of MCTS modifications and MCTS-inspired algorithms for e.g. Super Mario Bros, car racing and general video game playing; the further success of MCTS variants can be seen in the first General Video Game Playing Competition, where the objective is to not just play one game but a whole set of different games.

Behavior imitation and procedural personas

Playing a game well is not all there is to playing a game – there's also the issue of playing style to consider. We've seen numerous cases where the best-playing AI plays the game in a decidedly non-humanlike manner. If we want to test a game or a level, or provide interesting NPCs in a game, we need to create AI that can play that game in the style of a particular human, or maybe humans in general. One approach is to train neural networks on gameplay traces as we've tested with Super Mario Bros. A more involved approach is to model the player as a ``procedural persona'', assuming bounded rationality and a set of objectives. This conceptual framework has been combined with q-learning and neuroevolution to play a roguelike dungeon crawler game in various styles. These procedural personas have also been used to evaluate levels in level generation algorithms. We also organized a Turing Test competition for Super Mario Bros-playing agents, where the objective was to fool judges into believing your bot was a human.

Game data mining and player modeling

The vast amount of data generated by modern games can be used to understand both games and their players. We call attempts to make sense of this data game data mining. Our efforts include crowd-sourcing platform game level preferences, and using this to study which micro-structures in the game levels best predict certain player responses. We have also found out that we can predict people's life motives from how they play Minecraft, and detect sexual predators from game chat logs. Another question that we have investigated with data mining is how game mechanics create meaning. Of course, much of the behavior imitation work above could be seen as game data mining as well. You could perhaps take this further if you allow the game to select what the player plays so as to learn more about the player.

Music and games

There's many similarities between music and games. For example, games are often experienced as quasi-linear structures with variations in intensity and "mood"; music is often also used to accompany and heighten the emotional expression of a game. We worked on affect-expressing music generation for games and on bidirectional communication between games and music so that playing becomes composing and composing becomes level designing. Given all the work that has been done in music generation, it seems reasonable that some of the methods and representations used there can be used for game content generation; here, we have investigated using functional scaffolding for level generation.

Surveying and organizing the research field

As I've been involved in the field of artificial and computational intelligence in games since it was just a baby (or at least just a symposium), I've had a chance to get some perspective on what we are doing, why and perhaps where we should be going. Our Panorama of CI/AI in games is an attempt to give a high-level overview of all the different research directions within the field and how they can inform and benefit each other. In some ways, it is a much longer (oh no!) version of this blog post with more pretentious language (really?) and also talks about other people's work. You should read it. We have also written surveys about computational creativity and games and neuroevolution in games. On top of that we recently organized a Dagstuhl seminar on the future of the field.

"Stuff"

There are are so many interesting things to do – ars longa, vita brevis. So when a nice idea comes by it's always a good idea to try to implement it, run some experiments and turn it into a paper, even though it might not fit perfectly into the current research direction that you've told yourself you're pursuing. Some of my "other" recent papers which I still consider very interesting deals with community structure detection in complex networks and geometric differential evolution. On particular note is our DeLeNoX system for computational creativity, which I think is really cool and should be used for... something.

Finally, just a note that we are not done yet. We don't have AI that can play any game or that can design a large variety of good, novel and meaningful games, so the job is not done. And when the job is done this very likely means that we'll have solved general AI and there is no more job to do at all for anyone. But until then: more work to do, come join.

Wednesday, March 11, 2015

EvoStar paper previews

Why not use the blog to post links to new papers from me and my group? At EvoGames (part of the EvoStar conference), in April in Copenhagen, my collaborators will be presenting the following papers:

Thorbjørn S. Nielsen, Gabriella Barros​, Julian Togelius and Mark Nelson​: General video game evaluation using relative algorithm performance profiles.
This is groundwork towards generating complete games in VGDL, the language used to describe games in the general video game playing competition. We show that random games can be separated from human designed games by testing a portfolio of algorithms on playing them.

Marco Scirea​, Mark J. Nelson and Julian Togelius: Moody music Generator: Characterising control parameters using crowdsourcing.
Marco has been working on his music generator for games for a while, and here we perform the first evaluation of its ability to express emotions. One of the main novelties of the paper is the evaluation method, which analyzes free-text descriptions.

Antonis Liapis​, Christoffer Holmgård Pedersen​, Georgios Yannakakis​ and Julian Togelius: Procedural Personas as Critics for Dungeon Generation.
For a while, Christoffer has been working on modeling player behavior in a bounded rationality framework. Here, we use those models in an evaluation function for search-based level generator.

Mohammad Shaker​, Noor Shaker​, Julian Togelius and Mohamed Abou-Zliekha: A Progressive Approach to Content Generation.
This work follows up on Mohammad's work on the AI-assisted design tool "Ropossum" for the physics-based puzzler Cut the Rope. In this paper, the generation problem is turned on its head, as play-sequences are first evolved and then content is found that could allow those sequences to be played.

Mohammad Shaker, Noor Shaker, Mohamed Abou-Zliekha and Julian Togelius: A Projection-Based Approach for Real-time Assessment and Playability Check for Physics-Based Games.
Another addition to the Ropossum toolbox, this paper presents a way of testing and visualizing playability through a form of occlusion modeling, where level components cast shadows of unplayability.

Monday, February 23, 2015

How to write me an email (and get a response)

My inbox has as many mails as the night sky has stars. That's why I did not respond to your mail. Not because I didn't want to and not because I didn't like you. I'd love to be able to hit that reply button right after I read your mail. Could you please help me with this? Below are some tips.
  1. Write short. Response time is approximately proportional to mail length. This includes any attachments to your mail.
  2. State your request clearly. What do you want an answer to? Make it easy to answer your request. Best case: a yes/no question.
  3. Skip the formality. Skip the boilerplate. "Hi Julian" is a good start, your name is a good way to finish the mail. Everything in between should be unique.
  4. Do tell me how your day was if you feel like it. If I know you, I care about you and appreciate you telling me. Don't ask me how my day was. I will feel I need to reply and it will take me longer. It's also perfectly fine to not tell me how your day was.
  5. If the purpose of your mail is general chitchat, maybe we should talk on the phone instead.
  6. Don't be rude. Your email deserves an answer, unless you tell me explicitly that it deserves an answer.
  7. If I don't answer within a few days, do send me a reminder in the same mail thread. See if you can state your request more succinctly in your reminder.
  8. Don't contact me on Facebook, SMS, Skype or similar with the same request as your mail. These services don't provide an overview of outstanding messages and I therefore don't treat them as a task list. Your message will be lost in cyberspace.
I'm aware that this post may make me sound like a self-important and condescending person. I really hope I am not. I'm just someone who want to spend less time reading and writing emails, and avoid making people angry because I don't respond to their emails. I guess you want the same.

Thursday, February 12, 2015

Six things that cannot be listed - #4 is totally non-trivial!

There are many lists of things out there right now. But not everything can be listed. Here is a list of some things that can not be listed. In a particular order:


The real numbers

You might think it's easy to list the real numbers. Start at 0, and then you have 0.1, 0.2, 0.3... But wait, between 0 and 0.1 you have 0.01, 0.02 and so on. And between 0 and 0.01 you have 0.001, 0.002... In fact, it is impossible to get anywhere at all, because there is always a finer-grained way of listing the numbers. Unlike the natural numbers (positive integers), which you can simply list as 1, 2, 3... Georg Cantor proved that this was the case. And that's why the real numbers are in a sense more infinite than the natural numbers.

Cantpr later tried to prove that nothing could at the same time be more infinite than the natural numbers and less infinite than the real numbers. He couldn't, so he went crazy and ended up in a mental asylum.


The list of all lists that do not contain themselves

Sure, there are many lists that do not contain themselves. Your laundry list is presumably one of those, even if you write the list on a piece of paper you forget in your jeans (you'd only be washing the paper, not the list). An example of a list that does contain itself is the list of all lists of lists. And of course the list of all lists also contains itself. But the question is whether the list of all lists that do not contain themselves should list itself or not. Because if it does, it shouldn't, and if it doesn't, it should. Bertrand Russell spent a number of years puzzling over this so you don't have to.

This was important, because lists of lists are necessary in order to show that mathematics are true. Having thus destroyed attempts at founding mathematics on logic, Russell went on to be imprisoned for pacifism.
Thinking about infinity might make you want to hide.


All the animals

Jorge Luis Borges provided the following list of animals, in a fictional text about a text:
  • Those that belong to the emperor
  • Embalmed ones
  • Those that are trained
  • Suckling pigs
  • Mermaids (or Sirens)
  • Fabulous ones
  • Stray dogs
  • Those that are included in this classification
  • Those that tremble as if they were mad
  • Innumerable ones
  • Those drawn with a very fine camel hair brush
  • Et cetera
  • Those that have just broken the flower vase
  • Those that, at a distance, resemble flies
It's clear that this is not getting us anywhere and we should stop now.

Borges later lost his eyesight, but apparently never his virginity.

There are some pretty weird animals out there.


All statements that are true in a formal system of sufficient power

Kurt Gödel thought a lot about truth. In particular, about which statements were true and which were not. To find out which statements were true, he invented a way to list all the statements in a system. Even more impressively, using this list he could figure out whether the statement was true just by looking at the number of it. Because the statements could be about anything within the system, there must be a statement in the list which talks about whether this statement itself is true - a statement that contains the proof of itself. As with all other statements, the number of this statement says whether it is true or false. Gödel showed that this statement is false. This means that is is impossible to list all true statements in a formal system, or all false statements for that matter. Rather disheartening really if you want to believe that the truth is in there.

Gödel, always a somewhat troubled fellow, later starved himself to death.


All steps you take as you follow a coastline


Following the coastline of Britain in larger and smaller steps. Sorry, no animals. Image from Wikipedia.
Benoit Mandelbrot wrote a paper with the amazing title "How Long Is the Coast of Britain?". You might think that this should have been a very short paper. I mean, it's something like 12000 kilometers or so. But actually the question is complicated. There's another figure you can find online which is something like 19000 kilometers. How can they be so different? You see, you can only measure length in straight lines, and a coast is never completely straight (neither are most things in the natural world). In order a measure a coastline, you need to approximate it with a series of straight lines. Think of when you want to measure the length of a path by a walking it: you simply count the steps you take. Perhaps surprisingly, the length you measure depends on how long steps you take. You see, with smaller steps you can follow the path more closely and take more turns, and you will arrive at a higher number. The same goes for coastlines. If you want to measure the coast of Britain, you can do this in different ways. For example, you can choose to measure it by fitting straight lines of 10 kilometers to it and get one number. Or by fitting straight lines of 1 kilometer and get a much higher number. If you fit lines of a hundred meters you get an even higher number... and so on. At some point you will be measuring around individual grains of sand, and Brighton beach itself will probably be hundreds of kilometers long. In fact, you can't list the number of steps you would need to take, for the same reason you can't list the real numbers: there's always a smaller step possible.

Mandelbrot escaped the nazis and went on to live a long (how long?) and apparently happy life.

(Note to self: should illustrate this text with pictures of puppies, kittens and/or smiling people. That way, people might actually read it. Or at least click on it.)