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

In summary, the video shows an example of a depth-2 minimax algorithm applied to the Pac-Man scenario, but the example is flawed and does not work as intended.
  • #1
62
1
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?
 
Technology news on Phys.org
  • #2
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.
 
  • #3
rcgldr said:
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.

245379


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):

245381


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.

245382


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.
 
  • #4
Find a forum where top pac man players congregate. I am sure there would be a few members that can answer this.
 
  • #5
Korisnik said:
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).
 
  • #6
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.
 

1. Why doesn't Pac-Man eat the dot?

The answer lies in the programming of the game. In the original Pac-Man game, the dots are not considered as food, but rather as a way to score points and progress through the game. Therefore, Pac-Man is not programmed to "eat" the dots, but rather to collect them and move on to the next level.

2. How does Berkeley's AI course 188 relate to Pac-Man?

Berkeley's AI course 188 is a course on artificial intelligence and its applications. In this course, students learn about different AI algorithms and techniques, which can be applied to various real-world problems, including developing intelligent agents for video games like Pac-Man.

3. Can Pac-Man be programmed to eat the dots?

Yes, it is possible to program Pac-Man to eat the dots instead of just collecting them. However, this would require modifications to the original game's code and may change the gameplay and overall experience for players.

4. What is the significance of Pac-Man not eating the dot?

The decision to not have Pac-Man eat the dots in the original game was a design choice made by the game developers. It adds an element of strategy to the game, as players must navigate Pac-Man through the maze to collect the dots while avoiding the ghosts. It also adds a sense of progression as players can see the dots disappearing as they collect them, indicating their progress through the level.

5. Are there any other games similar to Pac-Man where the main character doesn't eat the dots?

Yes, there are other games that have a similar gameplay mechanic where the main character does not "eat" the objects on the screen. Examples include games like Snake, where the snake grows longer as it collects objects, and Qix, where the player draws lines to claim territory without actually "eating" the lines.

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

Replies
7
Views
1K
Replies
4
Views
980
Replies
1
Views
1K
Replies
1
Views
836
Replies
2
Views
867
Back
Top