Why doesn't Pac-Man eat the dot? Berkeley's AI course 188

[Korisnik]

TL;DR Summary

why doesn't pac-man eat the dot, minimax algorithm

Hello!

I've been following Berkeley's AI course, and I'm a little stuck. In this video , at 1 hour, 11 minutes, and 55 seconds, there's a short simulation of what they claim to be a depth-2 minimax algorithm applied to the Pac-Man scenario with two dots. Pac-Man begins in the corner.

The video shows Pac-Man moving left so that it's above the dot, and then makes another left. Now, if you watch the video, that exact scenario isn't explained; the subsequent one is (a minute after the simulation in the video). I sketched the first simulation in the similar manner, but I simply cannot get a tree that's 2 levels deep that would yield the action of going to the left. (The action of going to the right afterwards is alright but not the next one where it goes left, and so on.)

I assume the cost is -1 for a single step, and +10 for eating a dot. (The -1 still applies.)

Once Pac-Man's above the dot, there are three possible states it can enter: it can (1) eat the dot (go down), (2) go left, or (3) go right. The first choice gets Pac-Man +10 points with -1 for the step. The other two only cost Pac-Man -1 point. Since we're talking about a depth-2 minimax, we include the subsequent scenarios as well.

1. From the first one we get 4 possible scenarios, left, right, down, and up. All of these are away from the previously eaten dot (so no extra points, only the -1 for the step).
2. From the second one it can go down, left, and right, and again, we get nothing but lose that one point.
3. From the third one it can go left and down – same situation, no extra points.

From the above it seems the only rational thing it can do is go down first (option (1)), and then wherever because everything else results in a change of score of -2, while the first option together with any of the four ones it can subsequently make yield a total of +8. (+8 > -2)

Please, could someone explain why it doesn't eat the dot?

 

[rcgldr]

I'm not familiar with this type of logic, but it appears the issue is considering that being adjacent to the dot gets the same score as actually eating the dot. It's also not clear what the logic is in the "replanning agent". Is the "agent" aware of every dot's position or only those with in 3 steps?

I also question the logic behind using a depth of 2 tree, when considering 3 or more step cases (where the dot doesn't get eaten until the 3rd or later step, with a corresponding score of 7 or less.

I think the goal of this was to show an issue with "replanning agents", but the example seems like a poor choice.

 

[Korisnik]

I'm not familiar with this type of logic, but it appears the issue is considering that being adjacent to the dot gets the same score as actually eating the dot. It's also not clear what the logic is in the "replanning agent". Is the "agent" aware of every dot's position or only those with in 3 steps?

I also question the logic behind using a depth of 2 tree, when considering 3 or more step cases (where the dot doesn't get eaten until the 3rd or later step, with a corresponding score of 7 or less.

I think the goal of this was to show an issue with "replanning agents", but the example seems like a poor choice.

Thank you for your reply. Do you see the example the professor shows next, where there's a very simple one-row "game space" (this blue environment Pacman moves in) of only a few possible spaces, with a dot in each corner, left and right.

So, this is a different scenario where at the beginning Pacman plans 2 levels ahead. It's obvious here that it can happen that it simply follows the first right arm of the tree, but then it replans, which means it gets this same tree (with subtrees symmetrically flipped):

So now because the minimax algorithm gives it the same values for both subtrees, it can again reasonably take the left subtree. And so on, it paces back and forth, never eating the dot.


In the situation I described above, this doesn't happen. I have sketched the tree on a paper for each step of the planning.

So, it first plans and takes the A route (it could've taken B just as well), which puts it above the dot. Then it plans again, and in step 2 it should take B because it can get the most out of it.

Yes, it can see the other dot, and I suspect there might be something going on with it taking it into account, but as shown in the other example, it doesn't seem like it considers it at all; only the score.

Yes, this is to show that replanning can sometimes lead to starvation (or thrashing, or whatever it's called), but I'm just not sure how it works on that particular example.

 

[MidgetDwarf]

Find a forum where top pac man players congregate. I am sure there would be a few members that can answer this.

 

[rcgldr]

the example the professor shows next

I'm wondering about possible "tree pruning" (I'm only aware of this because of chess programs). Possible options:

Score a path that eats a dot sooner higher than one that eats a dot later.

Eliminate any move that results in a mirror image of the current state (no progress).

Eliminate any path with any leaf that results in the original state or a mirror image of the original state (potential no progress).

 

[QuantumQuest]

As far as I remember - I was about fifteen years old when I played the original pacman game, we had something we called "system of moves" - translated from my language, cheat in common parlance, which had different moves for the first four stages - if I remember the number well, as they were easier and then for the fifth level on, it had a different cheat that was kept the same for all the stages after fifth as well - till ghosts were moving so fast that your eyes could not help anymore or you had become so tired that could not go on anyway.

Now, the interesting thing has to do with the evaluation function mentioned in the video. Playing in the unique way of cheats, you had to move back and forth and not eat a dot in several instances during playing, until "Oikake" (the red chief ghost in the original 1980 version) came close to your pacman - dragging the other three ghosts with him as well, and so you had to go in a unique path which at the same time it guaranteed that you would "eat" even all the fruits appeared and you would use the bigger dots that changed the ghosts to "eatable" poor creatures in an optimal way and of course, you would eat all dots without losing a pacman.

Also, a very crucial part was utilizing the two exits with the purpose of fooling the red ghost ("Oikake" again) and consequently the other ghosts as well. The moves were very specific and should be executed in very specific ways. One small mistake, delay etc. and pacman was dead. Needless to say that we had to memorize all these.

I think that the evaluation function which will give the directions to a potential optimal algorithm for pacman, has to take into account both maximum score including the bigger dots that change ghosts which, ideally, must be "eaten" (all four of them), four times in each and every stage (with the progressive score given by the game) - besides the simple dots, and following a secure path which is guaranteed only if you always manage to fool the red ghost and attract it, so it is chasing you along with the other three, always from behind.

This second thing again guarantees a progressively maximum score as it ensures that pacman is staying alive, so it goes every time to the next stage but it's obviously a different issue compared to the first one. In other words, just following a greedy approach of a maximum score in and of itself, obviously, doesn't get you far. On the other hand the way you can fool ghosts is unique - if I remember well, and I guess that it was a way used by the programmers of the game in order to test it and see how it goes for a big number of stages, so this was transferred as a gift, in some way, to a player and then learned by a lot of others.

One of the extra difficulties is that ghosts run faster from a point on, so this effectively changes the optimal path which guarantees both being alive and getting maximum score. Obviously, if there was no cheat, or if the ghosts were allowed to move in completely random ways, it would be very difficult for a human player - if at all, to beat the ghosts.