- #1
Korisnik
- 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.
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?
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.
- 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).
- From the second one it can go down, left, and right, and again, we get nothing but lose that one point.
- 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?