Jump to content

  • Log In with Google      Sign In   
  • Create Account

Evolving PacMan AI


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
38 replies to this topic

#21 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 12 February 2008 - 04:54 AM

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



Sponsor:

#22 owl   Banned   -  Reputation: 364

Like
0Likes
Like

Posted 12 February 2008 - 05:40 AM

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.

#23 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 12 February 2008 - 06:51 AM

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]

#24 tok_junior   Members   -  Reputation: 229

Like
0Likes
Like

Posted 12 February 2008 - 07:47 AM

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.

#25 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 12 February 2008 - 09:01 AM

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

#26 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 12 February 2008 - 10:04 AM

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.

#27 owl   Banned   -  Reputation: 364

Like
0Likes
Like

Posted 12 February 2008 - 10:26 AM

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]

#28 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 12 February 2008 - 11:01 AM

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



#29 lewismcm86   Members   -  Reputation: 122

Like
0Likes
Like

Posted 18 February 2008 - 10:15 AM

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

#30 lewismcm86   Members   -  Reputation: 122

Like
0Likes
Like

Posted 18 February 2008 - 10:17 AM

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

#31 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 18 February 2008 - 11:53 AM

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.

#32 TheGreyOne   Members   -  Reputation: 122

Like
0Likes
Like

Posted 27 February 2008 - 02:24 AM

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!

#33 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 27 February 2008 - 05:29 AM

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

#34 TheGreyOne   Members   -  Reputation: 122

Like
0Likes
Like

Posted 27 February 2008 - 02:42 PM

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

#35 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 27 February 2008 - 03:13 PM

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



#36 TheGreyOne   Members   -  Reputation: 122

Like
0Likes
Like

Posted 27 February 2008 - 05:02 PM

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]

#37 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 28 February 2008 - 04:15 AM

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



#38 TheGreyOne   Members   -  Reputation: 122

Like
0Likes
Like

Posted 28 February 2008 - 07:13 AM

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

#39 kirkd   Members   -  Reputation: 505

Like
0Likes
Like

Posted 28 February 2008 - 09:13 AM

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS