GECCO16: General Video Game Level Generation

Hello everyone,
This is my talk in GECCO16 for our paper “General Video Game Level Generation“.

GVG-LG Framework GECCO.001

Hello everyone, I am Ahmed Khalifa a PhD student at NYU Tandon’s school of engineering and today I am gonna present my paper General Video Game Level Generation

GVG-LG Framework GECCO.002

We want to design a framework that allows people to develop general level generator for any game described in video game description language.

GVG-LG Framework GECCO.003

So what is level generation? It using computer algorithm to design levels for games. People in industry have been using it since very long time. At the beginning the reason due to technical difficulties but now to provide more content to user and it enables a new type of games. The problem with level generation is all the well known generators are designed for a specific game. So it depends on domain knowledge to make sure levels are as perfect as possible. Doing that for every new game seems a little exhaustive so we wanted to have on single algorithm that can be used on multiple games. In order to do that we need a way to describe the game for the generators.

GVG-LG Framework GECCO.004

That’s why we are using Video Game Description Language. It’s a scripting language that enables creating different games super easily. So the script written is for that game which is kinda like dungeon system from legend of Zelda. VGDL is simple u need to define 4 sections, SpriteSet, LevelMapping, InteractiveSet, and TerminationSet. SpriteSet to define game objects such as goal, interactionset to define the interactions between different objects, termination set define how the game should end.

GVG-LG Framework GECCO.005

Here some extra examples that shows that vgdl is able to design different games such as freeway where the user try to reach the exit by crossing the street.

GVG-LG Framework GECCO.006

Snowman which is a puzzle game where the player try to build a snowman at the end position by placing the peices correctly. It’s inspired by a snowman is hard to build a famous Indiegame about creating snowmen and giving them names and hugging them.

GVG-LG Framework GECCO.007

Let’s get back to the framework, we want to create it as simple as possible so each user write a level generator where he gets a vgdl description of the game and he has to return a generated level

GVG-LG Framework GECCO.008

The game description object give the user all the information in vgdl and also give tags to the sprites according to their interaction. For example if object block the player movement and don’t react with anything else, is considered solid, if is the player then tagged as avatar, if it could kill the player then it’s a harmful object, collectible object is stuff that get destroyed

GVG-LG Framework GECCO.009

We designed 3 different level generations and shipped them with the framework, the first one is the random generator where it place all game objects in different location on the map

GVG-LG Framework GECCO.010

The second one is the constructive generator where it tries to use information available and design a good level. So it starts by calculate percentages for each object type then it draws a level layout, then place the avatar at random location then place harmful object in a position proportional to the distance to the avatar, then add goal objects. After that it goes through a post processing where it add more goal objects if needed to satisfy goal constraints.

GVG-LG Framework GECCO.011

The third one is a search based generator where it uses feasible infeasible 2 population genetic algorithm to generate the level. We populated with levels generated from the constructive algorithm to ensure that GA will find better levels. We use one point crossover where two levels are swapped around certain point. While mutations used is create where it creates random object at random tile, delete: deletes all objects from a random position,

GVG-LG Framework GECCO.012

We used several constraints to ensure playability of the levels. First one is cover percentage so we never generate an over populated levels or very sparse levels

GVG-LG Framework GECCO.013

Make sure there is one avatar becz if it’s not there it’s impossible to play the game

GVG-LG Framework GECCO.014

Sprite number constraint where it makes sure there is at least one sprite from each type, to make sure the levels are playable. For example if there is no key u can’t win the level

GVG-LG Framework GECCO.015

Goal Constraint to make sure that all goal conditions are not satisfied becz if they are satisfied then u win when the game starts

GVG-LG Framework GECCO.016

Death constraint is to make sure for the 40 game steps if the player did nothing he won’t die becz if the player dies at the beginning it’s unplayable game becz humans are not as fast as expected

GVG-LG Framework GECCO.017

Last one is win constraint and solution length is make sure the levels are winnable and not straight forward win, the best agent takes amount of steps before finishing.

GVG-LG Framework GECCO.018

These are all the constraints, about the fitness, it consists of two parts. The first part is score difference fitness inspired from Nielsen work. He found that the difference in score between the best agent (Explorer) and his worst agent (DoNothing) is big in good designed levels compared to random generated ones. We used the difference between our best agent and worst agent for that.

GVG-LG Framework GECCO.019

The second fitness is unique rule fitness, we noticed by analyzing all games that agents playing good designed levels encounter more unique intersection rules than random designed levels.

GVG-LG Framework GECCO.020

In order to verify that we did a user study, where the user plays two levels from a certain game and choose which is better. We used 3 different games without including puzzle games as there is no agent excels in playing puzzle games so far.

GVG-LG Framework GECCO.021

The results shows that users prefered search based levels over constructive which was expected while they prefered random over constructive without huge significance.

GVG-LG Framework GECCO.022

One of the main reason we think is people can’t differentiate between constructive and random but random always ensure all sprites there which make its levels playable while constructive although it looks better sometimes it misses a key or something.

GVG-LG Framework GECCO.023

We ran a level generation competition one week ago, we had 4 competitors (1 based on cellular automata, 3 based on search based approaches)

GVG-LG Framework GECCO24.001

It was simple because the cellular automata didn’t put tons of objects in the level which made it somehow playable while all the others overloaded the levels with tons of object so players die insatiately

GVG-LG Framework GECCO.025

Our future work, is enhancing search based generator to get better designed levels, enhance the framework based on competitors feedback, rerunning the competition again and encouraging more people to participate.

GVG-LG Framework GECCO.026

That’s it, Thanks.

That’s it for now.
Bye, Bye


IJCAI16 Talk: Modifying MCTS for Humanlike Video Game Playing

Hello everyone,
Ages since last post πŸ˜€ on Thursday July 14th I gave a talk about my paper “Modifying MCTS for Humanlike Video Game Playing” with Aaron Isaksen, Andy Nealen, and Julian Togelius at IJCAI16. Thanks to Aaron, he captured a video of my talk. Here is it:

Also we did a poster for the conference which looked amazing. Here is the poster:

Humanlike MCTS Poster.001

If the video is not clear, I am posting the slides here with my comments:

Humanlike MCTS New.001

Hello everyone, I am Ahmed Khalifa, PhD student at NYU Tandon’s School of Engineering. Today I am gonna talk about my paper “Modifying MCTS for Humanlike Video Game Playing”.

Humanlike MCTS New.002

We are trying to modifying Monte Carlo Tree Search algorithm to play different games like human player. We are using General Video Game Playing Framework to test our algorithm.

Humanlike MCTS New.003

Why do we need that? One important reason is create humanlike NPCs. One of the reason people play Multiplayer games is the lack of realistic NPCs to play with or against. Also evaluating levels and games for AI-assisted tools. For example if you gave these two levels to a human, he will pick the one on the left as its playable by human while the one of the right is super difficult, it might even be impossible to be played.

Humanlike MCTS New.004

Before we start, whats general video game playing which we are using its framework. Its a competition for general intelligence where competitors create different agents that plays different unseen games. These games are written in a scripting language called Video Game Description Language. Every 40msec the agent should select one of the available actions. Like up, down, left, right, use button, nil which is do nothing. A game play trace is a sequence of actions.

Humanlike MCTS New.005

Here are two videos that shows the difference between human player and MCTS agent. On the left you can see humans tends to go towards their goal and only do actions when necessary (for example only attack when monster is near). While MCTS agent on the right is stuck in the upper left corner moving in walls, attacking the air and walls.

Humanlike MCTS New.006

By analyzing the play traces for both human players and MCTS agent on different games. We found that humans tends to repeat the same action multiple times before changing. In the first graph it shows human have tendency to repeat the same action twice by 50%. Also humans tends to use more NILs and tends to repeat it more during the play trace. While in the third graph it shows the MCTS have a higher tendency to change actions more often than humans. Humans 70% of the time don’t change their action.

Humanlike MCTS New.007

In order to achieve similar play traces, we need to modify MCTS. These are the main 4 steps for MCTS.

Humanlike MCTS New.008

We tried to modify each step on its own but none of them have a big change in the distribution except for the selection step.

Humanlike MCTS New.009

Selection step depends on UCB equation to select the next node.

Humanlike MCTS New.010

UCB equation consists of two terms, exploitation term and exploration term. The exploitation term bias the selection to select the best node while the exploration term push MCTS to explore less visited nodes.

Humanlike MCTS New.011

We modified the equation by adding a new bonus term which consists of 3 parts:
Human Modeling
Trivial Branch Pruning
Map Exploration Bonus
Also we modified the Exploitation term with a MixMax term.
We are going to explain all these terms in details in the upcoming slides.

Humanlike MCTS New.012

We added a bonus value that shift the MCTS distribution to be similar to human distribution. As you see from the video the agent tends to repeat the same action and do more NILs with lower action to new action frequency. But as we see, it is still stupid, stuck in the corner, attacking air, moving into walls.

Humanlike MCTS New.013

Thats why we added the second term which avoids selecting stupid nodes (like attacking walls and moving into walls) As we see the agent stopped attacking the air and whenever it get stuck in a wall, it changes the action or apply nil. But its still stuck in the corner.

Humanlike MCTS New.014

So we added a bonus term that reward nodes that have less visited positions on the map. As we can see the agent now go every where and explore. But as we see the agent is coward, it avoids attacking the spiders.

Humanlike MCTS New.015

So we used MixMax term instead of the exploitation term which use the mixture between the best value and the average value of the node instead of the average value only. As we can see the agent become courageous and moves towards the enemies and kill them.

Humanlike MCTS New.016

Analyzing the play traces after all these modifications. our BoT (Bag of Tricks) algorithm tends to be more similar to human compared to MCTS in action repetition, nil repetition. Also having less action to new action changes.

Humanlike MCTS New.017

In order to verify these results we conducted a user study. In the study, each user watch two videos and he was to specify which is more likely to be human and why?

Humanlike MCTS New.018

From the study our BoT algorithm was more human than MCTS but still not as good as humans, except for PacMan where deceived the humans by 60%.

Humanlike MCTS New.019

When we analyzed the human comments we found that the main reason for recognizing agent are the same as we stuff we tries to solve. Jitterness (changing directions very quickly), Useless moves (attacking walls, moving into them), No long term planning (stuck in one of the corners), too fast reaction time, over confidence (killing all enemies and become over achiever)

Humanlike MCTS New.020

Thanks for listening.

That’s everything for now.


100th Post (Huge Post)

Hey All
This gonna be the largest post of all time, which will make you remember old days when I was writing about lots of stuffs and concepts and lots of amazing things.

This post is so long so if you are busy now you can check it later as it will took alot of time to check everything in it and this post will be starting for series of posts which gonna talk about my career and my coming games and my thoughts.

Let’s Start the post with some music and tracks from games that you must buy them without hesitation, these tracks are so beautiful that you must at least check them

Second thing I just wanna say that my dream movie (Indie Game: The Movie) will be released on 12 June on Steam Store by the way I am very happy with their success and their marketing strategy is amazing also what makes this movie good that as a movie that the music is a master piece and every scene in the movie in my view can be and talks are so inspiring for anyone who is out of the indie scene or outside gaming, I adore it a lot and here is the link for details and here is the launch trailer πŸ™‚

Third thing will just tell you about amazing games that are worth your money and you should at least check it some of them are not so new by the way πŸ™‚

These are not all amazing games I know but just couple of them and you should at least check them out Humble Indie Bundle V is so amazing and if features these games in it which is a very amazing deal where you get 5 amazing games and also helps charity

These are just some indie news and music non about my games and progress or anything so the next part of the post will be totally revolving around my games and progress.

First thing Ludum Dare results were out long time ago but I didn’t wrote anything about the game (Don’t Push the Button) or about the results.
Let’s see the results first:

#135 Humor 3.00
#220 Innovation 3.38
#273 Overall 3.24
#325 Fun 3.00
#379 Theme 3.14
#410 Mood 2.71
#419 Audio 2.50
#456 Graphics 2.83
#851 Coolness 33%

As it is obvious from the results I didn’t win nor got advanced position as usual but this time I have to analyze this.

  • It was my first Platformer since long time ago besides I am not good at playing Platformers
  • I made the game and I was the one who tested it so I wanted to make my Platformer difficult and fast so I adjust the gravity and speed to be a bit high and since I always test it so I get used to it and never noticed that it’s too fast to the player
  • I don’t have good exposure in indie scene beside I don’t have lots of friends their although I am trying hard so my game is played and rated only about 40 times which is not indicative at all

But I am pretty happy with the game, It was made as intended ,regardless of the speed issue, and people loved the zoom effect but I don’t think anybody notice the idea behind that, I hope someone figure it out (link).
The Next couple of new if you where following me on twitter(@amidos2006) I think you know most of them.

First thing do you remember my Collaboration game with Alexitron πŸ™‚
Yes you are right The Power

Is now out by GamePirate you should go and try it as I consider it one of my best games so far (link).

As you notice this game took so long to finish it and so long to get a sponsor deal at the end the deal was low but we decided (me and Alexitron) that it should be published so may be some are asking why this long.

I will explain, the core mechanic of the game was finished in about 2 or 3 months after starting the game and the only stuff remaining was the boss fights and the conversation system and menus. I started working on them and I finished the first boss in less than a week with most of the menus, but at that period I was recruited by the army (its a must and there is no way from getting away) so I spend 1 hell year trying to work on The Power but I couldn’t and I find myself starting to forget about game programming so I decided to start a new project (Project Cupid) and it was intended for a competition but since my vacations in army period was not good so I couldn’t submit it in the competition and continue to work on it till I finished it and put it for sponsoring.

I didn’t get a single bid on the game so I got somehow depressed so I decided to try to finish The Power and started to work on it again at October 2011 and by December I finished the game with everything and we were happy (me and Alexitron) and the only thing that was missing was the boss fight track since Alexitron have lots of nice friends and amazing people on Poppenkast so he asked Brother Android to continue on the project and finish the last track and he agreed.

Alexitron start a beta testing for the game on Poppenkast and we got nice comments about the game and we fix lots of bugs.
Here are some of the nice comments we got:

  • Andy: hey yeah, i’ve heard of Amidos. He’s cool and he’s really active in the indie world and just overall has a good presence. good luck on the project, guys!
  • Andrew: this is exciting. good luck buddy, keep us posted!
  • Stampede: Super! The Power was really good game. You gonna get lots of players with this!
  • Pgil: Sounds like things are going nice. I loved the Power…
  • DeadHeat: The power was great fun, hopefully this one goes just as well
  • Br.Android: The Power is awesome by the way.
  • Br.Android: Also also, this project is turning into basically an orgy of talent, and that’s superexciting.
  • Alexitron: Awesome ! Amidos is so cool to work with
  • ChevyRay: Lookin great babe.
  • Andrew: this is shaping up great.

By end of 2011 we uploaded The Power to FGL and I was so excited and I was imagining that lots of sponsors will be bidding, but that doesn’t happen the game was online on FGL although it good high editor rank and high developer rank but none of these helped to get a bid.

I decided to send emails to sponsors and I collected lots of sponsor emails and start sending about the game, and start waiting and after a month I got the first bid I was so excited and was imagining it will be at least 1000$ but what happens is that it was just 500$ so I got shocked and depressed and waited for more weeks but no reply from emails and also the views of the game started to decrease so I decided to leave it and start with new projects till it get a better deal.

After 5 months of waiting and I asked Alexitron to publish the game without sponsoring but he said “its better to start Last Call and see what we can get” (its a system in FGL to indicate sponsors that I am going to close bidding and start to choose a sponsor for my game)

I started Last Call and during the 3 days of last call I didn’t get any sponsoring deal except one from GamePirate (btw they are very nice and working with them is fun) although it was still low (
As you see the game took around 5 months to finish as work and in the end we (me, Alexitron, Brother Android, Pgil) got a very low amount of money that doesn’t compensate our expenses πŸ™ but I see its a great game and working with these amazing guys was great experience as it was my first time collaborating with someone and it was so fun πŸ™‚ also I noticed that long adventure games aren’t what sponsors are searching about.

By the way one of the most amazing thing I love about the game is its music as it is a result from collaboration of two talented musicians Brother Android and Pgil and the tracks were amazing and you can check the album on Bandcamp its free.

Another thing I think someone will ask about it “why don’t you try to make Indiegames Weblog or any other review site talk about your game so you get better exposure so may be more deals came?”. I tried that and sent emails to lots of website but as usual because I am not known and its only me whom is sending emails, I didn’t get a preview on any website, also I don’t think with exposure I can get a good deal as for example Celestial Mechanica by Roger Hicks is much more amazing and beautiful than The Power and it got exposure on IndieGames Weblog telling people that it is looking for sponsorship and after about 2 or 3 months I found Roger Hicks decided to sell the game on his own rather than trying to find sponsorship which means that(I think) he didn’t find good sponsor deal and decided to go on his own.

Some people might say “why don’t I do the same like Roger?” the answer is obvious The Power is just a flash port to Alexitron game which he made long time ago using game maker which runs on PC so the only way is to get a sponsor for it (link).

After this I knew that sponsors are rarely interested in long adventure games and I think they thinks its doesn’t worth and that’s because most of flash players are casual players who needs fast and easy game to play not long adventure game.

After finishing The Power in last December and put for sponsor I wanted to make another Collaboration game so I wrote on twitter if anyone is interested to make a game with and I got a reply from @Vartagh which is an italian game developer and best know for Steampack and Steampack C64.

We started talking with each other on skype the game we want to do, So I thought choosing a theme will narrow down our search. LudumDare 22 was just finished and its theme was Alone, so I told Vartagh about what about Alone theme as it looks nice, and he like it too. We talked about games we love and we found we love top down shooting games so we decided to do a top down shooter game and this decision came from our love to The Binding of Isaac and Hyper Princess Pitch and how these games are funny and at same time very addictive.

Varatagh told me lets make it looks cute and funny and that’s by using mushrooms as enemies (evil ones) and you are alone in a park where evil mushrooms started attacking you so the game name was inspired from that and told me let’s name it Alone in the Park as a Parody about Alone in the Dark and I told him that’s nice.

Then we started to work on the game he worked on graphics and design and I started coding the engine and helping in design and we are still working on it. I didn’t post screenshots about it here but I posted about it on my twitter account so I will repost them here again.

The game now 95% finished just some story lines and some editing level design and it will be available for beta testing before looking for sponsorship on FGL (as usual) hope to get a better sponsoring deal than The Power.

About Clean’Em Up, I told you that it is participating in two competitions (ImagineCup, IndieCade). ImagineCup round 3 results were released a week ago and the game didn’t proceed to round 4 which made me sad some how but not much at same time as I know the reason for that πŸ™‚ but before talking about reason I will show you 10 games that proceeded to round 4 and I think it will give you a good indication why our game didn’t proceed.

Do anyone realized why it was not one of the 10 πŸ™‚ the most obvious solution that our game contain lots of action and shooting that make the game doesn’t deliver the theme (How technology can solve World toughest problem?) quite well. We got this in feedback email from round 2 and we tried to make the game more involved with the theme but I think it didn’t do well in that.

I am hearing someone saying “Where is the relation between Clean’Em Up and theme in anyway?” its simple the problem we chosen was Cyber technology Threats and the solution is using Antivirus systems and we converted this into an cyber world where you play with the antivirus and trying to eliminate the viruses and worms and other forms of threats.

About the reviewing the game didn’t got feature at any site or got a review πŸ™ which sucks and non reply on my emails and the only site that replied on me was TruePcGaming and they were busy so they just made a preview for the game on their site but Adams is a nice guy πŸ™‚ btw and there other two reviews done by two Arabic review sites (first, second) and thanks to Abdulla Hamed (CEO of GameTako) for helping me to reach these sites as he is a well known person.

I wondered why all review sites didn’t reply on me so I sent to PixelProspector as he is sweet nice website but he was busy so he send to me some tips and hints to how to make a good email for press release so I updated my email and sent them again to reviewers according to his tips but I didn’t get any reply so I asked him on twitter why no one reply on me although I made everything better than past time.

As I told he is a sweet person so he asked me to send him the email with all data I sent, so he modified on the email and gave me some advice to be better and told me to send a follow up email when the game is released.

So I am waiting to finish the latest stuff in the game and I am asking again if anyone want to beta test the game or review the game contact me (amidos2002 (at) hotmail.com) or on twitter (@amidos2006).

Last thing about Clean’Em Up that it is expected to be released later that month (I hope so) as just some final fixes and adding more music tracks. I hope it do better in IndieCade.

I think the post is long enough by now although there are lots of stuffs I wanna share with all people πŸ™‚ but I will end this post and prepare for lots of incoming posts about my game making history where I am going to share the source code of lots of old games and abandoned games.

Also I started with new project for mobile devices called Crappy Dreams its an experimental game about dreams (my dreams), This project I am gonna share most of details with you and how I designed it and formulate it from my dreams and you can help me by giving me some comments and feedback about everything to try to improve the game.

Last thing thanks to Andy Moore and his DevVlog (especially these 1, 2, 3) as I was totally depressed with everything as whenever I ask someone for help rarely some one reply to me and its rarely I find a comment here in my blog about anything, beside none of my games got a mention or played with many people example Project Cupid is only played 127 times which is so low and didn’t get a feedback on it. May be I got depressed because my games always fail but who said that this is failure?

I said they fail because I was measuring success by how many plays and will it get feature but that is wrong measurement and I shall not treat games like that and I should change success goals and failure goals as they never been my dream in any day they evolved due to stress and pressure of work and low response. So I changed my perspective and I now make games like old days because I like making games and I love that and I wanna share my thoughts and experiences with people not for fame nor money (but I don’t say No for moeny πŸ˜€ as I need it for living)

I am inspired by Andy Moore and will post a lot and talk a lot and try to be more social with the indie scene and try to improve my games and my game design skills and I hope everything will be better in future and my main goal now is to enjoy what I am doing and let the stress away πŸ™‚ and I hope one day some people may say that I contributed a lot to the society and the gaming scene.

Sorry for long post hope you enjoyed it πŸ™‚

Bye Bye for now