IJCAI16 Talk: Modifying MCTS for Humanlike Video Game Playing

Hello everyone,
Ages since last post :D 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.
ByeBye

Super-W-Hack! Incubator Pitch

Hello everyone,
Today me and Gabriella gave a talk about Super-W-Hack for the incubator program. I felt it would be nice to share the talk with you people.

SuperWHack-Pitch.001
Hello everyone, I am Ahmed and this is Gabriella. We are PhD students at the game innovation lab here at NYU. We are going to talk today about our game Super-W-Hack!

SuperWHack-Pitch.002
Super-W-Hack! is a roguelike game with retro aesthetics as a tribute to the roguelike genre. Our game takes the procedural content generation (PCG) up to the next level. We use it to generate everything in the game.

SuperWHack-Pitch.003
Levels are procedurally generated, names, layouts, enemy distributions.

SuperWHack-Pitch.004
Player weapons: weapon pattern, names, sounds.

SuperWHack-Pitch.005
Even bosses are procedurally generated.

SuperWHack-Pitch.006
All game main features are done. But since our research is in PCG and we know how amazing it can generate stuff so we want to embrace it more. Generate the main character (his back story, why he is going to the dungeon). Generate variable weapons like teleportation, mines, bombs. Also our game still needs music. Since we have lots of PCG so we need lots of testing to make sure it works correctly.

SuperWHack-Pitch.007
We plan to finish the game and release it by the end of the year over Desktop such as Steam and Itch.io as Desktop has always been the land of roguelikes and the hugest fanbase. Since the game has simple controls and small decisions to take at each step. We believe it will do well on Mobile markets such as App Store and Google Play. We are going to send our game to all the major events such as IGF, IndieCade, and PAX. We believe with the help of the incubator we will be able to reach all these goals.

SuperWHack-Pitch.008
Thanks everyone for listening any questions.

Level Layout
(Then we played this video in the background while taking questions)

We got couple of questions and concern about the play session time, ensuring the game is playable and interesting to the player, and what’s a roguelike.

I just wanted to share my talk about the game and here is the link (www.amidos-games.com/super-w-hack/) to the alpha version if anyone wanna try it. In the current state its still a little hard to understand in the beginning but as soon as you understand it. It so intuitive and interesting to be played.

ByeBye

Video Game Description Language (VGDL) & General Video Game Playing Framework (GVG-AI)

Hello,
This post is a presentation I did couple of weeks ago at Game Innovation Lab (GIL). It supposes to help people at the lab to understand VGDL and GVG-AI framework. I think that if we want VGDL to evolve, more people should know about it and use it. This evolution won’t happen without showing to people the power of GVG-AI Framework and VGDL. There is lots of development happening to improve the framework and language and making it more accessible to people (creating an Interactive Visual Editor with computer assist). The following paragraphs are my slides with a description for each slide.

Slide1

Slide2

General Video Game Playing (GVGP) is creating an AI agent that can play different video games (not a certain game) efficiently. The hard constrain on these agents that they need to have a response time in about 40 msec.

Slide3

Video Game Description Language (VGDL) was invented to help to prototype different games quickly for the GVGP and have a common framework to work with. VGDL was initially written in python but now ported for java (to be faster). The language is tree structured like xml files. It supports grid physics like old arcade games (PcMan, Space Invaders, …etc). It is human readable and easy to prototype lots of different games using it (PcMan, Frogs, Space Invaders, Sokoban, …etc)

Slide4

The current drawbacks of the VGDL: It hasn’t a visual editor, It hasn’t a good online documentation for the language, It has limited physics (no continuous physics to prototype games like Cut the Rope), and It has limited events (all game events are restricted with collision events between objects). Right now people are working to improve these drawbacks and make the VGDL more accessible to more people. Check the current draft of documentation and may be you could help improve the writing and improve it (link).

Slide5

In order to write a game using VGDL, you need to provide two files (Game Description File and Level Description File). The Game Description File describes the whole game (What are the game sprites? What’s the termination condition? How do sprites interact? …etc). The Level Description File describes the level layout (Sprite arrangement).

Slide6

Let’s take an example. This game is called WaterGame. It’s super simple game where you have to move the avatar towards the exit. The problem is the path is always blocked by water. If avatar touches water, it will die. In order to pass the water, the avatar should push boxes over it (Box destroys the water, you can think it floats).

Slide7

That’s the Game Description File for that game. It is divided into 4 sections (SpriteSet, TerminationSet, InteractionSet, and LevelMapping).

  • SpriteSet: explains all the game sprites (their type, their rendered image). For example “avatar” is defined as of type “MovingAvatar” which means it can move in all 4 directions and it has an image called “avatar” (All images must be in sprites folder).
  • TerminationSet: explains how should the game ends? For example “SpriteCounter stype=avatar limit=0 win=False” means if the number of “avatar” sprites are equal to zero, you lose the game.
  • InteractionSet: explains the result of collision between sprites. For example the first collision says if “avatar” collides with “wall”, the “avatar” should “stepBack” which means undo its last movement.
  • LevelMapping: just helps the VGDL engine to parse the Level Description File. The VGDL engine just replace each character with the corresponding sprites.

Slide8

The Level Description File is a 2D matrix of characters described in the LevelMapping section. The VGDL engine just replace each character with the correct sprites and voila the level appears.

Slide9

Let’s now talk about the different types of sprites we can define. There is several amount of sprites but I just categorize it into the following:

  • Portal & Spawn Points: Like doors, teleports, portals that spawn objects, and …etc
  • NPC: there is chasing npc (follows a certain sprite), fleeing npc (runs away from certain sprite), random npc (moves randomly), and …etc
  • Resource: objects that can be collected and change certain defined variable value. This value can be anything like score, health, ammo, …etc
  • Avatar: It is controlled by the player (using keyboard or an agent). It can be moving avatar (moves everywhere), shooting avatar (which moves and can shoot), …etc
  • Movable: It is an object that is affected with physics like missiles.
  • Static: It is not affected with any physics even its applied on it like walls.

Slide10

There is only three different types of termination condition:

  • SpriteCounter: It terminates the game when the number of certain sprite is larger than or equal to certain value.
  • MultiSpriteCounter: It terminates the game when the summation of two different sprites equal to certain value.
  • TimeOut: It terminates the game when the game time is larger than or equal to certain value.

Slide11

There is lots of different interactions that can be used on collision between different sprites. The following are categorization for them:

  • Kill Sprite
  • Spawn Sprite
  • Undo Movement
  • Change Orientation
  • Change Position
  • Collect Resource

Slide12

The following slides will focus on the GVG-AI framework and what does it offer? For more details check GVG-AI website documentation (link).

Slide14

You can integrate an AI Agent that plays VGDL games just by extending AbstractPlayer class and providing a constructor and an act function which returns the avatar action every single game step.

Slide15

The framework also supports a StateObservation class that wraps the current game status (winning, score, and time), avatar status (speed, position, and orientation), grid observation for all the game (also it supports arrays for different sprite types), and Event History for all collisions happened due to the avatar or a sprites spawned by it.

Slide16

The StateObservation class provides forward model that can predict the future but not exactly as most games are some how stochastic.

Slide17

Last thing the framework comes with couple of sample agents to help you understand how to write your AI agent. For example: Random Agent, One Look Ahead, Genetic Algorithm, and Monte Carlo Tree Search.

Slide18

That’s the whole presentation. I hope it encourages you to use VGDL to prototype your games or even participate in the next GVG-AI competition (link). The Game Innovation Lab is trying to improve all the drawbacks of the VGDL language and even start a PCG competition track (link).

Bye Bye

Literature Review of PCG in Puzzle Games

Hello,
Long time since posting (the usual me) but This post will be short and long at same time.

“How is that?” That’s easy, the post itself will be very short (just few words) but it will have an attached document (around 16 pages) which is the third chapter in my Master’s Thesis. This chapter is the literature review chapter (the third biggest chapter in my thesis) which I think one of the most entertaining chapters (to read obviously not to write :D).

“Why do I think its entertaining?” That’s also easy to reply, I combined lots of previous work about level and rule generation (look at the references), and a friend of mine enjoyed reading it and thought its the most entertaining chapter.

“You just said its a short post.” Yes, sorry for that but I want also to improve my writing capabilities. Here is the link to the document: http://amidos-games.com/documents/LiteratureReviewPCG.pdf.

Bye Bye

PCG in my Games

Hello everybody,
Long time with no posts or updates here. It seems like desert, sorry for that but I am sure people who follow me on twitter knows I was busy with my Master’s Thesis in Procedural Content Generation (PCG). I have always used PCG in my games as an excuse for being lazy and not designing levels (as I am not amazing level designer). In this post I will wrap up quickly some of the PCGs I used in my games. In the next post will talk about PCG in my Master’s Thesis.

Slide27
As most of people noticed lots of my arcade games used PCG especially top down shooters (Clean’Em Up and Alone in the Park). All these games don’t have levels designed in advance, but instead they have enemy numbers and types to be generated. The system afterwards choose the most suitable location (away from the player position) and insert them. Pace Maker was a little different where the system generates the types and numbers based on the level of difficulty so as difficulty increase the number of enemies and variety of types increased.

Slide82
Match a Number used PCG technique to generate the map. The idea is super easy

  • Insert random tiles (numbers and types) over the whole grid
  • Choose the solution length based on the player score (define the difficulty).
  • Generate a random path of the specified length without any loops.
  • Calculate the value of this path and consider it as player target

For the puzzle mode instead of generating paths, the whole playground is divided into sets according to the number of sets required at the beginning and then calculate the value of each set separately.

Slide84
Atomic+ bullet pattern was generated based on a certain equation of difficult. The bullet generator is divided into the following features and by combining these features we can get a new shooter

  • Bullet Path (bp): how the bullet moves in the game (straight line, sin wave, spring, and circular path).
  • Number of Spawner (ns): how many places bullets should fire from the center (1, 2, 3, and 4).
  • Rate of Spawning (rs): how many milliseconds does the spawner need to spawn a bullet (800, 750, 700, 650, and 600).
  • Number of Burst bullets (nbb): how many bullets should the spawner generate at everyshot (1, 2, and 3).
  • Number of Bullets (nb): how many bullets the spwaner should shoot after each other (1, 2, and 3).
  • Spawner movement (sm): how the spawner update its position (no movement, circular movement, and ping pong circular movement)

Each of values for each feature has a specific difficulty score. This score is inserted in a difficulty equation and if the output difficulty is near the target difficulty then this generator is used else repick another random generator. The difficult equation is:

difficulty = sm * rs * bp * ns * nbb * nb

Slide73
Last game I am going to talk about is DivCircle. The music and the rotation are both chosen by the computer. For the game music. The music is divided into several tracks overlayed over each other as the rotation speed increased each layer of the music got activated and as the rotation speed decrease the layers gets lower. Also as the player approach more towards the death, all layers volume decreased while sounds of talking people increases. That’s everything with the music and Ben Burnes did an amazing job in helping me to reach that. About the rotations, I divided the game into 14 sequence each one with its own difficulty score. These sequences are:

  • Speed Up
  • Speed Up Fast
  • Slow Down
  • Slow Down Fast
  • Reverse
  • Speed Reverse
  • Slow Reverse
  • Reverse, Reverse
  • Speed Up Fast, Speed Up Fast, Slow Down Fast
  • Slow Down Fast, Speed Up Fast
  • Speed Reverse, Slow Down Fast, Speed Reverse
  • Reverse, Speed Up Fast, Reverse, Slow Down, Reverse
  • Speed Up Fast, Speed Up Fast, Reverse
  • Speed Reverse, Slow Reverse, Speed Reverse

All actions are stored in a queue and every amount of time an action is activated and new action sequence is inserted in the list based on the current player score and current rotation speed and how old is the reverse. The amount of time for inserting and applying new action is decreased as the score increase.

This is everything for now, Hope its a little bit entertainment and useful. Stay tuned for the next post which is gonna be about General Level Generation for Puzzle Script (which is a part of my Master’s Thesis).

Bye Bye for now

Help is Needed

Hello everyone,

Sokobn

Sorry for being away for long time, but as you all know I am working on my master’s thesis in Procedural Content Generation (PCG) of puzzle games and levels for Puzzle Script engine by Stephan Lavelle. I generated lots of levels using different methods for 5 different games and I need some human feedback on everything.

If you have some free time to help me with it please consider playing a handcrafted game and then one of the techniques (playing handcrafted give you reference to the best designed games) (link). Do the assessment after finishing every level to remember it because after playing 16 levels you may forget some games.

Please try playing some of the game at the end of the list such DestroyGame, GemGame, BlockFaker. As most of assessment is done on Sokoban and slightly on LavaGame.

Thanks everyone, I will publish my thesis and my code and everything once its done to be open source with all the results and data. Hope my work in PCG helps game developers in understanding more about games and how to design it and may be use or improve on my techniques.

The link for the games and the assessments: http://amidos-games.com/puzzlescript-pcg/

Bye Bye

DivCircle is out today for Free

Hello Everybody,
I don’t know if there is still some followers to my blog, but if there I wanna say DivCircle is now OUT on AppStore and on GooglePlay. Get your headphones and try that experimental game and experience how different people feels toward developed societies.

Here a trailer for the game

Now Go and Try it (AppStore) and (GooglePlay) and here is the (Website) too :) Spread the word and make everyone try it :) Hope the world become a better place for everyone :)

That’s everything for now :) I am so busy right now applying for PhD degree so Pray god I got accepted in a PhD degree so I can work on Procedural Generation and stuff I love and I can get out of my country at same time. Thanks for supporting me all this time.

Bye Bye

DivCircle is Next Month

Hello Everyone,
I know I have long time away but as usual busy working on games, master thesis and trying to apply for PhD for next fall so I can leave Egypt and work on stuff I love :) Let’s not talk about my akward feeling towards Egyptians (not Egypt btw) and let’s show you all the new trailer for the game and the website (http://www.amidos-games.com/divcircle/)

The game will be released in December for Free on Android and iOS :) and its about Diversity and supporting We heart Campaign (http://weheart.github.io) :) That’s everything for now :)

Bye Bye

AmidosEngine: a FlashPunk inspired game engine based on Starling

Hello Everybody,
That’s a short quick post :) I have decided to release my game engine I have been using for all my mobile games lately and desktop games to the internet.

I designed that engine to be fast and quick way to make games based on concepts of FlashPunk but at same time used Starling so it can render very fast on mobile devices making use of the new Stage3D rendering.

I know there are lots of better engines out there but I didn’t find any engine that resemble FlashPunk very well that’s why I build my engine over Starling, I will continue updating it with each game I create whenever I find a need for something, I will create it.

I know the name is very narcissistic because I used my name in it, I know but I am bad at names so I named it after myself (Sorry for that) and Thanks for Chevy Ray and Starling for making it possible.

Hope someone can find it useful and help him to make better games, That’s everything for now :)

github: https://github.com/amidos2006/AmidosEngine
github Page: http://amidos2006.github.io/AmidosEngine/

Bye Bye

Atomic+ Android Version

Hello Everybody,
Happy Feast for all Muslims in entire world and celebrating that I released Atomic+ on Google Play Store. Hope people will love it.

ReleasedImage

So to keep it short just tell your friends and go buy the game :D YaaaaaY :D The game is on 50% discount for limited time so what are you waiting for :) Go Go Go :) (Link)

That’s everything for now :)

Bye Bye