• 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

Updated code is up. Here's the detail:

v0.1.3 Updates
--------------

Windows now update during the evolution step thus preventing significant freezing of the application during one epoch.

The console window now tells you whether PacMan will run or not after the current epoch and has (almost) instant feedback from pressing 'B'. The title bar of the console window (PacMan maze) states "Active" or "Sleeping" depending on the current state of the application.

Small optimizations to speed up the simulation.

Ghosts now allowed to reevaluate their direction after PacMan eats PowerPellet, and ghosts made more aggressive. Hopefully this will discourage chance collisions forcing PacMan to be more active in pursuit.

When the console window was running a spontaneous crash would occur the seemed to stem from the Windows message queue. A DoEvents() function was implemented to allow window events to be processed while the Console was active. This seems to have solved the problem.
0

Share this post


Link to post
Share on other sites
with a score of only 520 it plays a lot better now. I notice that sometimes the simulation timeouts, is that because pacman gets stuck? it stops when pacman reaches the highest fitnes value, why don't you let it run until he dies?

[Edited by - owl on February 12, 2008 4:26:20 PM]
0

Share this post


Link to post
Share on other sites
Hmmmm....I'm not sure if I know what you mean. Currently it times out when he gets stuck in place or when he gets stuck in a non-scoring cycle. You can adjust the amount of time allowed for both of these in the parameters file:


MaximumUpdates 1000
MaximumStall 25
ScoreStall 25


MaximumUpdates is the maximum number of "steps" the simulation will take. I set this to 1000 after playing it manually a few times to determine how many updates would be required for me to clear the level. Usually I took about 600 (I think), so I set this to 1000. The primary reason for this limit is so that the overall simulation doesn't take quite so long to run while evaluating each net during the GA.

MaximumStall is a limit on the number of updates in which PM's position does not change. The number is arbitrary.

ScoreStall is a limit on the number of updates in which PM's score does not change. Again, this one is arbitrary.

These limits also define when the visualization itself stops. Possibly what you're seeing is a stall (stuck in a corner with no change in position) that is fairly short - 25 steps - so it appears to stop rather immediately. Try increasing the value for ScoreStall and MaximumStall to 100. Most likely he'll sit in the corner for a while before the visualization ends.

-Kirk

0

Share this post


Link to post
Share on other sites
Hi I am very interested with this field of work as I at the moment am trying to prove that the problem of pacman can be solved with a rule based system prioritizing the pacmans goals and acting accordingly.

Here is the source, its a totally different approach but my tutor is eager to prove that this practice could compete to a suitable level;

http://devweb2007.cis.strath.ac.uk/~lmcmilla/pacmansol2%20(4).zip
0

Share this post


Link to post
Share on other sites
Hi I am very interested with this field of work as I at the moment am trying to prove that the problem of pacman can be solved with a rule based system prioritizing the pacmans goals and acting accordingly.

Here is the source, its a totally different approach but my tutor is eager to prove that this practice could compete to a suitable level;

http://devweb2007.cis.strath.ac.uk/~lmcmilla/pacmansol2%20(4).zip
0

Share this post


Link to post
Share on other sites
Very nice. I'll take a look at it for certain. Given a rules-based approach, do you have any idea how it responds to randomness? The original PacMan had deterministic ghost movements and I believe there is information out there that shows it to be solvable if not solved. Ms. PacMan introduced a degree of randomness to ghost movements creating a less solvable or unsolvable scenario. My version has some randomness in ghost directional choices.

As for my version, there is yet another update available. Here's the detail on changes to v0.1.4:

v0.1.4 Updates
--------------

A few bugs were fixed. Specifically, some issues with whether PowerPellets and Ghosts were visible or not were addressed.

The ability to ignore walls or dots was added to the Windowed AI. In the parameters file the following keywords control this as follows:

DotWallSingleInput - If set to 1, the input will be -1 for a wall, 0 if empty, and 1 for a dot. If set to 0, there will be two sets of inputs - one for dots one for walls.

DotsWallsOnly - If set to 0, both dots and walls will be used for inputs. If set to -1, only the walls will be seen. If set to 1, only the dots will be seen.
0

Share this post


Link to post
Share on other sites
I've been playing around with this for a few hours, and it occurs to me that part of the reason that PM gets stuck, is the fact that he is allowed to turn back on his previous direction. As far as I'm aware, the actual pack man games did not allow this. And it would also solve the issue of PM going into 'loops' where he simply walks back and forward within a corner. One other thing of note, is during the entire time I have been playing with this, I have never once seen PM move towards the left side of the screen, and tends to favour moving upward. Meaning that the vast majority of attempts have ended with PM stuck in the top right hand corner.

Anyway, that's just my two cents. Thanks for providing some interesting things to think on!
0

Share this post


Link to post
Share on other sites
Thanks for your comments. I'm excited to see interest from the opposite side of the planeet!! 8^)

Regarding PacMan moving back on his own path, in the original game he can move in any direction he wants at any time. Given that the player controls his motion, there are no limitations on what direction he can go at what time. My intent was to allow the controlling neural net the same freedoms as a human player. Ghosts, on the other hand, are only rarely allowed to reverse their current direction in the original.

I had considered putting additional constraints into place and in my current version (not yet on SourceForge) I have an additional parameter called EnforceIntersctions which will only allow PacMan to choose a new direction at an intersection rather than at any time during the simulation. I have not enforced a limit on reversing direction, though.

I have also seen a preference for certain areas of the game board during multiple runs. I have often seen PacMan get stuck in all four corners, however. I'll do some investigation into the random number controls to make sure they are behaving as they should.

-Kirk
0

Share this post


Link to post
Share on other sites
Well, I left the process running overnight, 37520 generations down and I finally see PM move left! Yay! :) (best fitness of 4100) By the way, what is the chance that you'll implement some sort of saving and loading feature? So that a: it becomes possible to stop and restart(continue) the training, and b: So that when I've had PM running around for a week, there's something to show for it :D

I figure some sort of serialization of the strongest NN from each species would be all that's needed.

Also, any chance you would consider threading this? The ability to run multiple tests at once would greatly increase the speed of improvement I believe.

By the way, I'm running PM with 4 ghosts, maximum stall of 10, and maximum score stall of 100. This greatly reduces the chance of PM stopping in corners, however there is still a tendency to run back and forward on his own track :/

Anyway, sorry if I'm being overly demanding >.< just trying to offer a few helpful suggestions.

Looking forward to more!
- Grey
0

Share this post


Link to post
Share on other sites
You are certainly NOT being too demanding. I truly appreciate your comments.

Regarding your suggestions, serialization of the best neural nets in each generation is planned, I just haven't gotten to it yet. I hadn't thought about using that to halt training and then restart, but I like the idea. I'll put that on the agenda as well.

I hadn't considered threading primarily because the application is quite demanding of processor cycles as it is. If you ran multiple threads/instances simultaneously on the same machine each thread would have to share the processor and be slowed down. This would be improved on a duo core or quad core machine, though. One thought I had was to try to integrate PVN so that it could be distributed on a network. I have access to ~150 processors and PVN would let me run a huge number of simultaneous instances or have a VERY fast evaluation. Again, something I'd like to do if I have time.

Another thing I would like to get into place eventually is evolving ghost AI. The ability to run a competitive co-evolution - now that might be interesting.

All that being said, you should feel free to grab the code and make those very modifications. ;^)

-Kirk

0

Share this post


Link to post
Share on other sites
Grab the code? I hadn't actually thought of that! :D The only downside being that I've got absolutely no experience with either serialization of data, -or- threading. (Yes I have several multi-core PCs, thus why I mentioned threading :) ) I'll definitely take a look at the source now however, and see what I can wrangle together. And if I make something that is "good enough" i'll make a copy available for you to rip apart :)

<edit> Is the zip on sourceforge the latest code? As it seems a little, broken. :| It may very well be a problem with me using VS 2k8 so i'll keep slowly fixing the errors (down to 8 from about 20) </edit>

[Edited by - TheGreyOne on February 27, 2008 11:02:48 PM]
0

Share this post


Link to post
Share on other sites
The code on SourceForge is almost the latest. I have a 1 step newer version, but it is only a soft modification of what is there.

One difference is that I'm using Code::Blocks as my IDE, so transferring to VS may require some wrangling. Of course you can always get Code::Blocks and GCC for free. 8^)

-Kirk

0

Share this post


Link to post
Share on other sites
While it's oh-so-tempting to get into a conversation on the relative merits of IDEs, I think I'll leave that for another place and time. ;)

I have given up trying to compile the code that is available to me. Mainly as I'm worried any attempts to 'fix' the seeming problems will only land me with more problems to fix (this time of my own creation.) As such, I will patiently look forward to your next release, hopefully with at least the save and load functions (*grin*) as that seems the most useful at this point in my opinion.

Anyway, I've nothing more useful to add at this stage, so i'll leave it at that! :)

- Grey
0

Share this post


Link to post
Share on other sites
Sounds like a cop-out to me! 8^) Seriously, distribution of code can be tricky. I assure you, however, that the exact code you have compiles and runs nicely using GCC (MinGW) and Code::Blocks.

The next release I plan to put up will contain the Intersection Enforcement option I mentioned earlier - PacMan can only change direction at an intersection. I have also implemented a Vectorial Representation in which the inputs consist of angles and distances from PacMan to Ghosts, power pellets, and the centroid of the currently remaining dots. In this version I leave walls as a windowed representation. I also want to fix a couple of aesthetic bugs.

After that I plan to work on persistence of the nets, just as you've suggested here. Once that works, I can start thinking about evolving ghost AI simultaneously.

-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