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

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..

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

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.

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.

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

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

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??

here is similiar project for you to look at for ideas.

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.