• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
kirkd

Evolving PacMan AI

38 posts in this topic

For those who are interested in such things, I have just updated my Evolutionary PacMan project on SourceForge: http://sourceforge.net/projects/aipac/ The most significant change is addressing instability issues. Apparently many users had problems with the application shutting down unexpectedly. I have made a number of changes which should address this problem. Please don't hesitate to let me know if problems of this sort still occur. Two representation methods are in place: Windowed, in which a window around PacMan constitutes the inputs. Each tile in the window (except under PacMan himself) has an input associated with dots/walls, power pellets, and ghosts. Users can select which inputs are used through the parameters file. Global, in which details of the maze are used as inputs, e.g., PacMan's X and Y coordinates, ghost X and Y coordinates, ghost state, power pellet state, presence of walls or dots around PacMan. Again, the specifc inputs used are selectable through the parameters file. I hope this can be useful and/or entertaining. -Kirk
0

Share this post


Link to post
Share on other sites
can one see the pacman playing at some point? only the statistics gets updated here, when does it stop and the game plays?
0

Share this post


Link to post
Share on other sites
Thanks for your interest!

Yes, you can opt to have the PacMan run after each generation using the best neural net thus far. To get this to work, while one of the application's windows is activated (the PacMan game maze is probably the best), press the 'B' key. After the current evolutionary step, PacMan will become active. You can turn it off - go back to having PacMan not run - by pressing the 'B' key again.

BE PATIENT after you press the 'B' key as the evolutionary step will have to complete before PacMan runs and sometimes this will take a while depending on how many inputs you have and how large the population is. Also, if you get impatient and hit the 'B' key a second time, you will end up toggling the display off so you'll be back where you started. Just hit the 'B' key once.

Please let me know that you get this working.

-Kirk


0

Share this post


Link to post
Share on other sites
Alright, now I see it play. What does exactly the pac-man learns here? I've the feeling that you measure the fitness based on the amount of pills he eats, and that the genome is a fixed sucession of moves that leads the pacman to eat determined amount of pills. I mean, the pacman will always play the same game, isn't it?
0

Share this post


Link to post
Share on other sites
There's a lot to your question. Here's the detail:

A neural net controls PacMan's movements through the maze and you can control the types of inputs going into the PacMan. The default version associated with the executable has no ghosts and uses a Window around PacMan with a radius of 4 tiles. This results in four tiles in each direction around him, plus the two tiles in each direction that he occupies, or 4+4+2 (4 to the right, 4 to the left, 2 for PacMan) left/right and up/down. This gives 100 total tiles. I also have the tiles that PacMan covers removed from this set, so you get 96 inputs.

Each tile can have 3 possible inputs - 1 for ghosts (-1 if a baddie, 0 if no ghost there, and 1 if a blue one), 1 for a dot/wall (-1 if there's a wall, 0 if nothing there, and 1 if a dot is there), and 1 for a pellet (0 for no pellet, 1 for a pellet). The default version you have has no ghosts (you can control the number of ghosts in the input file), so you have dots/walls and pellets as inputs for each tile. The grand total is now 96 * 2 or 192 inputs.

At each step that PacMan takes, the neural network is evaluated. The net has 4 outputs, one for each direction (up, down, left, right). The output with the highest value gives the direction that PacMan takes.

In the absence of ghosts, the game map is deterministic so yes, PacMan will take the same path when using the same neural network. The ghosts have a strong random component to their movements, so adding these will cause some random variation in PacMan's movement from run to run.

The Neural Nets are evolved using an Evolutionary Computation process. The fitness I'm using is the score that PacMan gets for one run through the maze. The time one run can take is limited (you can also control this in the parameters file). The goal is to maximize the score that PacMan gets.

I've found it most interesting to look at PacMan's navigation early in the process and compare that to what happens after it has run for a while. No surprise that early in the process PacMan's movements are more or less random - often he just drifts one direction or the other, hits a wall, and stops. Then after it has run for a while and his score is over 1000, his behavior is much more interesting. So far the maximum score I've seen (with no ghosts) is about 2600 out of a maximum of 2840.

I hope that answers your question - without putting you to sleep!

-Kirk



0

Share this post


Link to post
Share on other sites
That's pretty nice. How good does pac-man play when there are ghosts? I'm editing the .param file to see how it goes...
0

Share this post


Link to post
Share on other sites
Thank you! Tell your friends. (Get my rating up on SourceForge!) 8^)

What I've found so far is this:

Using the combined dot/wall input I described is MUCH better than having them as separate inputs. I'm sure this is due to the fact that the network becomes much simpler and easier to deal with in a short time. I'm concerned, however, that this is a bit of cheating. Should I allow the evolution to learn this relationship on its own??

The best window radius I've found so far is 2. I've tried many sizes and this seems to perform very well with only a few inputs - 32 to be exact.

Adding the inputs for the PowerPellets and the Ghosts has not yet seemed to help much. My guess is that with either of these providing inputs, they are only turned "on" a very small amount of the time. For example, power pellet inputs are only equal to 1 when there's a pellet within PacMan's window, which is not very often. The result is that learning is very slow and limited in its impact. The same goes for ghosts.

That being said, when I have turned ghosts on and have dot/wall, power pellet, and ghost inputs, I've seen some interesting results. Many times, PacMan will just eat a power pellet and then wait for a ghost to bump into him. (The ghosts are rather stupid, so they don't avoid him like they perhaps should - I'm working to fix this.) Often, though, I've seen PacMan run back and forth in a corridor just below a power pellet waiting for a ghost to come by. When a ghost gets close, he grabs the power pellet. I've not yet seen him pursue the ghosts, though.

If you get any interesting results, let me know. If you can grab a movie of the screen (like I have done and uploaded onto SourceForge), please do. I'll load it up on the project page as well. Eventually I want to be able to write the neural nets to a file which can be loaded in again later. This would allow any interesting behaviors to be saved and shared.

-Kirk

0

Share this post


Link to post
Share on other sites
Thank you again. I truly appreciate the positive feedback.

Feel free to offer suggestions. If you have an idea of something you would like to see, let me know. I'm always open to suggestions and constructive criticism.

-Kirk
0

Share this post


Link to post
Share on other sites
Have you seen this research into making a ms pac man AI? I think they used simple handcrafted rules and searched for policies to apply those rules effectively. Maybe try replacing your outputs with rules and see how that works, where the network chooses which rule to apply. Of course, the big question is how to automatically build effective rules, given just the basic inputs and outputs.
0

Share this post


Link to post
Share on other sites
I had not seen that one. There are a few other examples of learning PacMan and Ms. PacMan, but that's a new one. I briefly scanned the paper and the problem I have is that they have a set of hand coded rules from which the agent can choose. My hope was to supply raw game information without any influence on what the agent does with that information. I think their work is very good, but I would like to see more of an organic development of the rules - much as you mentioned.

I have thought about something more like Genetic Programming, but have just not had the time to implement it. Again, if the raw game information is supplied and subroutines are allowed to develop, it might serve as an organic rule development process. Then GP could develop the rule importance process.

Interesting paper.

-Kirk

0

Share this post


Link to post
Share on other sites
I think the pac-man should know the entire map and the position of every object all the time because that's what a human player knows when playing. But I guess that'd be a lot of input to process..
0

Share this post


Link to post
Share on other sites
Yes, I've tried that version as well. Currently the small windowed version seems to perform best (as I mentioned above), but I've tried much larger windows and a full screen input. Like you mentioned the complexity of the neural net becomes huge and not much progress is made. Perhaps if I were to let the simulation run for a few weeks it might find some interesting behavior.

I've also tried a non-tile based input scheme. In the parameters file you can switch to a Global type in which there are only about 38 inputs maximum - PacMan X and Y, Ghost X and Y, Ghost state, Power pellet X and Y, Power Pellet state, the direction having the most dots, the number of dots remaining in each direction, walls. It also does reasonably well but I'm convinced the inputs aren't very good and could be greatly improved.

Right now I'm running the small window version (radius = 2) with 4 ghosts and inputs for ghosts, dots/walls, power pellets (96 total inputs). After running for almost 24 hours the score is around 1300. The most interesting behavior is PacMan follows a similar path for each run but if a ghost is in the way, he'll deviate that path a bit. He also hesitates to eat a Power Pellet until a ghost is nearby. He still doesn't pursue blue ghosts.

Any ideas for other input schemes?

-Kirk

0

Share this post


Link to post
Share on other sites
How are you calculating the "direction with the most dots"? Maybe giving scores to the tiles based on if there is a pill, a wall, emptiness or a ghost, dividing the map in sectors and taking into account the distance of pac.man to those areas could be a way to doit. You could score the tiles also with the times the pac-man passed through (say, negatively), so if the pac-man got stuck in some area, the function should make the pacman change the direction that's making it be stuck.
0

Share this post


Link to post
Share on other sites
I left it running overnight with all inputs enabled, 4 ghosts and a window-radius of 2. I achieved a best fitness of 3770, but more than 18000 generations without improvement. No wonder, since it moved to the upper left corner and got stuck.
0

Share this post


Link to post
Share on other sites
Quote:
Original post by owl
How are you calculating the "direction with the most dots"? Maybe giving scores to the tiles based on if there is a pill, a wall, emptiness or a ghost, dividing the map in sectors and taking into account the distance of pac.man to those areas could be a way to doit. You could score the tiles also with the times the pac-man passed through (say, negatively), so if the pac-man got stuck in some area, the function should make the pacman change the direction that's making it be stuck.




For the Global version of the AI (non-windowed AI type), I have the following inputs:

CheckForWalls gives 4 inputs, one for each direction around PacMan. The input is 1 if there is a wall there, 0 if PacMan can move that direction

CheckDots gives 4 inputs (1 for each direction around PacMan), each with the total number of dots on that side of PacMan's current position. For this I look at the entire maze and count the number of remaining dots. My hope was that he would gravitate toward regions of high dot density.

MaxDotDirection gives 4 inputs, 1 of which will be set to 1 (others 0) corresponding to the direction in which most dots are present.

GhostX, Y and State - 3 inputs for each ghost

PowerUpX, Y and State - 3 inputs for each power pellet

PacManX, Y - hopefully to give a relative position to the ghosts and power pellets


Regarding PacMan getting stuck, I have in place a stall out timer which will stop the simulation early if his position doesn't change for a certain number of clock ticks. I also have another timer that will end the simulation early if his score does not increase for a certain number of ticks. This should prevent him getting stuck for too long in cycles. You can adjust both of these in the parameters file as well.

Scoring the tile based on PacMan passing through them is interesting. Essentially creating a deterrence to follow the same path multiple times. I'll have to think about this one and the scoring/sectoring idea. Hmmmm....

-Kirk


0

Share this post


Link to post
Share on other sites
Quote:
Original post by tok_junior
I left it running overnight with all inputs enabled, 4 ghosts and a window-radius of 2. I achieved a best fitness of 3770, but more than 18000 generations without improvement. No wonder, since it moved to the upper left corner and got stuck.


3770 is quite good! Given that he drift to the upper left and gets stuck I'll bet that he goes to the Power Pellet, waits for the ghosts to come along, gets the Pellet, and then waits for ghosts to bump into him. I've seen this happen a lot.

One of the problems is with the ghost AI. I currently have it set up such that every time a ghost hits an intersection it has a random probability of moving toward PacMan or in a random direction. For the 4 ghosts the probability of moving toward PacMan is 20%, 40%, 60%, and 80%. When they are vulnerable (blue) they have the same probabilities of moving away from PacMan or in a random direction. This causes the first couple of ghost to be quite stupid and bump into PacMan a lot. I changed this in the code to be 50%, 60%, 70%, and 80% and this helps a little. I will probably put these probabilities into the parameters file, too, allowing users access to the ghost movements.

-Kirk

0

Share this post


Link to post
Share on other sites
I just had an idea for a way to represent the game - please offer feedback if you have any.

Ideally, I would like to represent the entire game board. This provides all the information all the time, much like someone mentioned in a previous post. The current Window AI type only represents a small portion of the game board at a time so any planning or reaction is limited to the current window of interest. The upside of this method is that the number of inputs are relatively small and, most importantly I think, the world is represented relative to PacMan's location. The Global representation (PacMan X, Y, Ghost X, Y, and state, Pellet X, Y, and state) packs information about the entire game board into only 38 inputs, but the content is limited and it isn't truly relative to PacMan himself. Actually, PacMan's location is part of the input, so he would have to learn that this represents him.

So what I'm looking for is a compact set of inputs that can represent the entire game board relative to PacMan himself. How about a set of vectors? For each ghost, for example, we could have the angle and distance to the ghost from PacMan's current location. Same for the Power Pellets. Dots could be represented in the current window format (seems to work well and allows the inclusion of walls) or a vector from PacMan to the centroid of all current dots - I'd want to experiment with this one a bit. I've also struggled with the inclusion of fruit in the game and how to represent it. The windowed version wouldn't be very useful for this as it will represent another set of inputs that are set to zero the vast majority of the time (due to fruit only being present intermittently and likely not being in the window at all if it were present).

Comments??

0

Share this post


Link to post
Share on other sites
Quote:
Original post by kirkd

3770 is quite good! Given that he drift to the upper left and gets stuck I'll bet that he goes to the Power Pellet, waits for the ghosts to come along, gets the Pellet, and then waits for ghosts to bump into him. I've seen this happen a lot.

One of the problems is with the ghost AI. I currently have it set up such that every time a ghost hits an intersection it has a random probability of moving toward PacMan or in a random direction. For the 4 ghosts the probability of moving toward PacMan is 20%, 40%, 60%, and 80%. When they are vulnerable (blue) they have the same probabilities of moving away from PacMan or in a random direction. This causes the first couple of ghost to be quite stupid and bump into PacMan a lot. I changed this in the code to be 50%, 60%, 70%, and 80% and this helps a little. I will probably put these probabilities into the parameters file, too, allowing users access to the ghost movements.

-Kirk


Actually i got stuck just to the right of the pellet. When a ghost got near moving in Pacmans direction he started moving towards the dot, but a bit too late, so the ghost got him. And he repeated the same every time I saw it.
0

Share this post


Link to post
Share on other sites
I've seen similar things happen. One problem that I've noticed is that given the random nature of the ghosts a particular network can receive a very high score simply due to the fact that on one run through the maze all the ghosts were in just the right place at the right time for PM to get a very high score. Most of the subsequent runs have much poorer scores, but due to the one good run, that network gets an excessively high score. This usually causes the population to converge very early to a less interesting neural net.

To combat this I put in the concept of Replicates. Each network is run multiple times and you have the option to take the average, median, or minimum score that particular network achieved over all its runs. I've found that if I set the replicates to 7 and take the minimum (you can adjust these in the parameters file), this usually helps take care of the problem of a fortuitously high score.

So far in the presence of ghosts the results are less than spectacular. I think the concepts are being learned, but having ghosts present presents a very difficult problem. I still question whether the inputs are appropriate. In the most recent link sent by owl the intention was to try and replicate what a human player would do in a certain situation. For every step in the game with a human player, they generated a series of integers describing the state of the game and how the human player moved. After collecting a large amount of this data, they used it in more of a data mining sense using a decision tree to determine how PM should move given the current game state. Very interesting idea, but again I was hoping for a situation with raw game state in giving PM control out.

As I mentioned before, my next experiments will be to install a vector based approach. A series of vectors centered on PM and providing the angle and distance to ghosts and power pellets will be used. I'm not certain of what to do with dots and walls just yet, but I may leave them in their current windowed version.

Finally, I'll try to update the SourceForge page again this week. I've made a couple of modifications to the code that speed it up and fix some additional, small bugs.

-Kirk

0

Share this post


Link to post
Share on other sites
You also gotta check the related works link. Very specially this paper, that guy got some interesting outputs there.

Another data you could consider is the shortest path's distance between the pacman and the ghost, to give pacman the chance to try to maximize/minimize it accordingly.
0

Share this post


Link to post
Share on other sites
I scanned through the thesis briefly and it is certainly a unique approach. It seems that they modeled the maze space as a series of turns and look for an assessment of what to do at each turn given the current ghosts states, etc. I also notice that they have only 1 ghost. I will run some tests with my code using only 1 ghost and see what my relative score is compared to their's.

EDIT: I also notice that they do not seem to have any power pellets. It appears that the ghost represents an additional constraint on PM's actions, but does not contribute to his scoring ability.

[Edited by - kirkd on February 12, 2008 1:51:21 PM]
0

Share this post


Link to post
Share on other sites
Quote:
Original post by kirkd
To combat this I put in the concept of Replicates. Each network is run multiple times and you have the option to take the average, median, or minimum score that particular network achieved over all its runs. I've found that if I set the replicates to 7 and take the minimum (you can adjust these in the parameters file), this usually helps take care of the problem of a fortuitously high score.


I was actually running with 2 or 4 (can't remember which) replications :) Must've been a serious fluke some time during the night.
0

Share this post


Link to post
Share on other sites
I used to always run with 5 replicates and found that an excessively high score can occur 5 times in a row with some regularity. Needless to say I was quite surprised. It seems that 7 works reasonably well, albeit slowing down the process quite a lot.

I've also tried to make the ghosts more aggressive to try and cut down on accidental collisions with PM while they're blue:

I increased the rate at which they move toward/away from PM when hunting/blue. It used to be 20%, 40%, 60%, and 80%, but I've changed that to 50%, 60%, 70%, 80%.

I allow the ghosts to change directions immediately after PM eats a power pellet whereas before they could only change direction if they were at an intersection.

These seem to have helped somewhat. I'll try to get the latest code up on SourceForge this afternoon.

-Kirk
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0