Latest Entries »

Udacity – the future of education

Filed under: PhD, Stanford — Leave a comment
March 17, 2012

Traditional education has as much to fear from the potential of the internet as the worlds of publishing, record shops, book shops, and even now Game shops.  Performing an activity at scale (both volume and geography) reduces the shared cost of any overhead, and a new university called Udacity has sprung out of Stanford to take advantage of this new world.

Udacity presents students with short video lectures interspersed with HTML forms that take in answers to questions.  The focus of the university is programming, and the web application even includes a program interpreter so students need to write code which the servers interpret, test and return marks.  The content of the course is genuinely challenging and allows students to learn in their own time, even though the courses have a fast weekly pace.

The potential of this is quite astonishing – I was part of the beta course in AI (run directly by Stanford).  They had over 85,000 students enroll, and over 23,000 finished the course.  The course was of course globally available and free, so programmers from 57 countries took part, with translations crowd sourced by the students.

I have now recommended the university to at least 10 programmers (from complete beginners to experienced masters) and every single one is coming back with positive feedback.  They are offering courses from the first steps of programming to the details of how to create the brains of a self driving car (which is excellent).  The courses are taught by the absolute cream of the profession (e.g. Sebastian Thrum who pioneered the self driving car in the DARPA grand challenges and now is heading the Google Self Driving Car team).

They are of exceptional quality, and it is hard not to draw a line between the lack of proper ICT training in the UK that is appalling, and the supply provided by off shore web sites and entrepreneurs, and wonder about the state of UK universities in 20 or 30 years time.  My suspicion is they will be a place of networking and research rather than learning.  What is not clear is where the funding will come from for such activities, which in most cases starts with some form of tax or international investment.

This is probably not somewhere for the UK to be left behind – the internet can move the balance of power before most of us have even noticed there was a threat.

Comment

Neuro Evolving Robot Operatives

Filed under: Games, NEAT, PhD — Leave a comment
January 16, 2012

One of the interesting applications of the NEAT algorithm is to generate artificial brains via the use of Artificial Neural Networks.  These are approximations to the way that our brains are wired up, consisting of a bunch of neurons that have firing thresholds, and synapses that link the neurons together.  When you add in some sensor neurons that feed the network with location, sight, sound etc, the artificial brain can, by modification and distortion of the signals across the network, fire signals to effector neurons, which can control an agents behavior, movement, speech etc.

Of course if you randomly wired together a set of neurons and synapses, real or artificial, the ‘brain’ created would most likely do nothing or work itself into a crash state.  However if you start with a very small amount of neurons and links, then slowly add more under a training regime, you can get some startlingly intelligent behavior – in precisely the same way as nature develops embryos to thinking creatures.

Another correlation between real world and artificial embryo development is that the artificial neural networks are stored as a DNA string, which is unpacked to create the network.  The most interesting behavior is shown when individuals with successful brains reproduce with other fit individuals.  In this manner it is possible to create networks that have the best of both parents, and over enough generations it’s possible to create networks displaying highly complex behavior.

The video game N.E.R.O. (Neuro Evolving Robot Operatives) has been created to show how these neural networks can create individual and team behaviors in a virtual world.

The general idea is to take untrained robots (which will make generally random actions) and reward individuals which display promising behavior.  These then are more likely to reproduce in the next generation, and over time the promising behavior gives way to the operatives taking actions which could easily be mistaken for human play.

The NERO engine has been open sourced, so it’s possible for anyone to develop their own AI’s, or present new challenges for existing agents.

This technique has not, to my knowledge, been used in any commercial games to date, although given that it allows characters to develop over time could be used to create games that are able to endlessly adapt to the players style, presenting new challenges within every game.

Comment

ObjectiveNEAT Posted

Filed under: NEAT, PhD — Leave a comment
January 13, 2012

As a learning exercise I recently wrote an implementation of NEAT (Neuro Evolution of Augmenting Topologies) in Objective C, the language of choice for iOS devices.

The godfather of NEAT and many derived AI techniques, Ken Stanley, has picked this up and published the project to the NEAT AI groups here and here.

It’s always nice for something you’ve created to be passed on to a wider group, my hope is that other developers may build upon the code and create some iPhone or iPad games or apps that make use of the AI technique to develop around the user, presenting new challenges or being able to interpret a users intentions through learning over time (like SIRI).

The original source can be found here, with documentation here.

 

 

Comment

Procedural Textures

Filed under: PCG, PhD — 1 Comment
December 12, 2011

Generating textures for games and virtual worlds is a time consuming task, to give you an example any big budget film or game may have well over 50% of the development budget assigned to creating 3d models and the images which cover them to make them realistic.

I’ve talked about procedural content generation before, but to give you an idea of it’s capabilities is a picture generated by the Graphic Designer Toolbox.

Looks pretty creepy, but the interesting thing is that it is created by a few blocks of mathematical algorithms rather than designed by hand.  Simply swapping in different algorithms can create entirely different effects, from clouds, to cities, mountains, deserts, and many other instantly recognisable features.  The effort required to generate a tool box of features may be large, but once you have the toolbox and can begin chaining effects, a single skilled designer can outperform a team very quickly. Modern films such as Avatar used this along with other PCG techniques to generate a whole alien worlds fauna and flora – without such methods it simply would not have been possible.

Comment

Objective NEAT

Filed under: NEAT — Leave a comment
December 9, 2011

I’ve recently put together an implementation of NEAT in Objective C, the preferred language for Apple Mac and iOS devices.  The code is running quite smoothly now, although there are many small improvements and major extensions to be added.

The code can be downloaded from GitHub here, and I’ve put a full documentation up here.

The code is free to use, modify and include within any free or commercial applications, and I hope that it pushes a few more iPhone developers to create some cool applications and games with the technology.  There will be a few more posts on how the algorithms can be used for generating content or working with games in the future.

Comment

SketchaWorld

Filed under: PCG — Leave a comment
December 8, 2011

The current generation of games and virtual world applications require vast amounts of content to be considered believable, all of which takes designers, graphics artists and 3d modellers to put in place.

As the expectations of consumers rise, the cost of creating this content increases exponentially.  This is one reason that Procedurally Content Generation is of high value to the next generation of games and virtual world applications, whereby programmers design algorithms that create infinite worlds of all shapes and sizes.

One major issue with PCG is that sometimes the results can be ugly, boring, or unplayable.  Another is that it is can be difficult to direct the creation of a world without an underlying knowledge of how the abstract code works, which can be difficult for a designer to manipulate.

Ruben Smelik from the Delft University of Technology has just successfully defended his PhD in a Declarative Approach to Procedural Generation of Virtual Worlds, which makes very good reading for those interested in the subject.

Ruben has also built an application which immediately shows the simplicity and potential for successful PCG – SketchaWorld.

I am intending to apply the NEAT algorithm to this approach of building worlds, either a a direct (using HyperNEAT) or indirectly via softawre agents under the control of evolved neural networks.

Comment

NeuroEvolution of Augmenting Topologies

Filed under: NEAT, PCG, PhD — Leave a comment
December 1, 2011

In 2002 Ken Stanley and Risto Miikkulainen presented an evolutionary method for developing solutions using Neural Networks – NeuroEvolution of Augmenting Topologies, or NEAT. This technique, while relatively new, takes inspiration from natural evolution and has been used in a number of very interesting applications from agent control through to creation of new music and art forms.

It’s an area of research that is highly relevant to my work, and to better understand the topic I’m putting together an implementation in Objective C, the preferred language for Mac and iOS devices.  As an introduction to the topic and for other students I’ve put together a brief presentation on the subject.

Presentation on NEAT

Since then Ken has moved on to the Evolutionary Complexity Research Group (EPLEX) at the University of Central Florida and extended the research in a number of ways, the most interesting to me being in the search for novelty.  Ken has a website that shows some of the directions and algorithms, and to get an idea of where it is heading I’d recommend his Keynote speech from the 2010 SPLASH conference.

Comment

Subversion RIP

Filed under: Games, Opinion, PCG — 1 Comment
November 8, 2011

It’s a great shame to hear that Introversion Software, a London based indie game developer, have decided to put on hold Subversion, a game of great interest to anyone involved in PCG.  The company has decided to take some of the technology they built for the project and focus on another game called Prison Architect, which should be good news as they’ll undoubtedly be making sensible commercial decisions.

There is a full interview here, and has many topics worth considering for an indie developer, or anyone involved in PCG.

  1. Worlds and Levels created by PCG techniques are, more often than not, really boring to play.  This is a biggie – you can make a computer generate the most beautiful landscapes, plants and water features, but this stuff has a tendency to repeat itself to infinity, which is no fun at all.  Even the makers (well publishers) of Elite limited the number of galaxies from the possible 256 million to only 8, on the basis that the player would lose all interest in the ridiculous scale.  Successful PCG games like Minecraft ensure that the players can design their own unique architecture over the world of mathematics, this generates interest for other players.
  2. Making something more realistic does not make it more fun.  Everyone knows that the KISS (keep it simple stupid) mantra is the most important in UI, UX, product, game, or pretty much any other design, however it’s very difficult for an artist to follow this simple rule, even more so when there is an elegance to making the environment fully integrated to the point otherwise designed laws naturally emerge.  I’ve been following Introversion for a long time and I can see the quandary they would have been in: as proponents of PCG as a necessity to make up for lack of human level designers, it became more tempting to generate everything well past the position of utility.
  3. It’s a highly complex (possible unsolvable) problem to simulate architecture that would otherwsie been created by a human (or even animal) builder.  The most immediate uses of PCG may be as a tool to generate ideas that human (or crowd of) designers then curates by selecting and modifying into something useful.

The direction of my research is in creating software agents that can assist human designers (or crowds of them) generate more interesting levels, either by evaluating the raw creations of PCG, or perhaps by simulating human behavior in shaping their environment, or even learning how designers create content and replicating these fuzzy techniques.  Introversion software have been pioneering these techniques for many years, and so I wish them the best in commercial success with Prison Architect so they have more time to play with creating virtual worlds.

Comment

Plant Growth

Filed under: Demos, PCG, PhD — Leave a comment
November 1, 2011

Generating plants and fauna has been one of the primary successes of computer graphics over the last few decades, most people would be surprised at how often the plants in a film or advert are virtual copies of the real thing.

A simple way to create plants is using Lindenmayer Systems, which take a starting string and over a number of steps re-write the original string based upon simple rules.

So for example we could start with the character A and every time we iterate we replace the letter A with AB, and if we find a B we replace it with letter A. This gives us a series that looks like:

A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB

and so on.  Visually we could change the characters to directions for an image drawer (things like turn left, turn right, draw forwards) and instantly we’ve produced some nice little snowflakes.

We can generate all sorts of interesting shapes by making tiny additions to those initial rules, such as adding the ability to jump spaces without drawing, changing colour, all in all a very simple way to make some familiar looking patterns.

Where things get more dynamic is if we allow the algorithms to maintain a stack of visited matrices, which means to branch, a bit like trees.

Move into the realm of 3D and we begin to get some very lifelike trees.  Of course trees are not made up of identical sticks from root to branch, so we need to add in a little stochastic sampling (randomness in the growth) as well as the idea that the tree will grow seasonally, and a trunk will grow differently to a branch, a leaf or a flower, however all of this can be managed with some imagination.

To get an idea of how far this has come, check out the virtual arboretum managed by SpeedTree, a company which specializes in dreaming up virtual fauna.  To get some more details of how the magic happens, I’d recommend The Algorithmic Beauty of Plants by Przemyslaw Prusinkiewicz and Aristid Lindenmayer.

 

Comment

Genetic Algorithms

Filed under: PCG, PhD — Leave a comment
October 26, 2011

Genetic Algorithms provide computers with the solve all manner of problems by following the simple principles of natural evolution, largely by breeding virtual programs, allowing them to compete at solving a problem, then selecting the best to reproduce and create a new generation of possible solutions.

I first came across this concept while reading The Blind Watchmaker by Richard Dawkins, a book I cannot recommend highly enough – while it focuses on the evolution of life, it provides insight on all manner of subjects.  In the book Richard Dawkins introduces Biomorphs, a computer program he wrote that would take a simple genotype (a coded sequence similar to a DNA string) use it as a seed for a development algorithm which would result in a phenotype (in this case images which bore striking resemblances to insects or plants).  A few examples from his book:

Without going into the technical details, genetic algorithms such as have the potential to solve all sorts of problems faster than random searches or even human design.  Some applications include:

  • Acoustics, in the design of amongst other things opera houses and high fidelity speaker cone enclosures  for optimum sound reproduction
  • Engineering, for example car and wind turbine shapes for aerodynamics
  • Astronomy, in the identification of undiscovered star systems
  • Electrical Engineering, in all manner of chip design optimisations
  • Financial Markets, in many cases outperforming traders predicting market changes
  • Playing games such as Chequers, to the level that within a relatively small number of generations can beat any but the most expert players.
  • Military and other logistical planning, both areas where it is used to aid human decisions in summarizing a near infinity of variables.
  • Data mining or search, particularly in areas where the data sets are so vast that patterns simply cannot be put forward or tested by simpler techniques (including skilled humans) with any hope of success.
  • Recognition of patterns and objects in images.
  • Developing agent and team behavior, used in many computer games and real world competitions such as RoboCup.

My interest in the field is as an underpinning to the main subjects of my research, right now focusing on the use of agent intelligence and procedural content generation to create digital content such as environments, worlds, graphics, music and virtual characters and agents.

These require slightly different use of Genetic Algorithms than in the above examples – generally GA’s are able to find a solution to a given problem when this can be expressed formally (such as a mathematical sum) however in general are not optimised for finding a solution that is based upon taste, fashion or other qualities that are difficult to quantify. They do, however, provide a mechanism to help a human designer create and evaluate such content, an area which traditional procedural content generation techniques have been criticized for being unable to do.  An early example of this happening comes courtesy of Karl Sims from a contribution to the SIGGRAPH 5 years after the Blind Watchmaker was published.

This slideshow requires JavaScript.

To get an idea of the state of the art have another look at Avatar, pretty much 90% of what you see on screen was created using GA graphic techniques.

Comment