algorithms, themselves could be compared. If we were to do this project again, we Based on our results and the time would have tried to find an evaluation complexities involved with acquiring such function that would work well for all results, we can draw a few overall algorithms, even reflex agent. In addition, conclusions. First, one can see how much coming up with a better utility function in randomness mattered within the context of general would have been a good idea. A Pac-Man as there appears to be a large utility function is fairly subjective due to the discrepancy between the results of the programmer deciding what states are minimax and expectimax algorithms. If we desirable. These subjectivities may not have were to do this experiment again, it would been ideal for winning at Pac-Man. A lot of have been beneficial to run the same the decisions involving the utility function algorithms on a game board where the were made based on guessing and checking ghosts did, in fact, move optimally to see until the behavior evident in Pac-Man what differences could be found. Another coincided with our preferences for how to conclusion drawn from this project is the play the game. Looking back on this project, noticeable power of a properly trained there is probably a better way for how to algorithm. When considering the come up with a utility function. time taken make the decisions and the results, q-learning was far and away the best If we were to do this project again it algorithm. Q-learning was able to retrieve would also be worth exploring future depths similar results to expectimax depth four in a of minimax and expectimax. Due to fraction of the time. For future problems computer limitations and the amount of similar in nature to the one explored in this trials needed to draw conclusions, we could paper, it would be wise to apply the only explore up to depth four reasonably for algorithm. both algorithms. It would be interesting to see how close to a perfect 100% rating we There are a couple of concerns worth could obtain by investigating larger depths. mentioning in regards to this project. First, The same goes for q-learning. By adding reflex agent had the potential to do much more games to the training count it would be better than it did with a different utility interesting to see how close to perfection we function, but we wanted to have consistency could get. across algorithms for evaluation so that the
Based on our results and the time complexities involved with acquiring such results, we can draw a few overall conclusions. First, one can see how much randomness mattered within the context of Pac-Man as there appears to be a large discrepancy between the results of the minimax and expectimax algorithms. If we were to do this experiment again, it would have been beneficial to run the same algorithms on a game board where the ghosts did, in fact, move optimally to see what differences could be found. Another conclusion drawn from this project is the noticeable power of a properly trained algorithm. When considering the time taken make the decisions and the results, q-learning was far and away the best algorithm. Q-learning was able to retrieve similar results to expectimax depth four in a fraction of the time. For future problems similar in nature to the one explored in this paper, it would be wise to apply the algorithm. There are a couple of concerns worth mentioning in regards to this project. First, reflex agent had the potential to do much better than it did with a different utility function, but we wanted to have consistency across algorithms for evaluation so that the algorithms, themselves could be compared. If we were to do this project again, we would have tried to find an evaluation function that would work well for all algorithms, even reflex agent. In addition, coming up with a better utility function in general would have been a good idea. A utility function is fairly subjective due to the programmer deciding what states are desirable. These subjectivities may not have been ideal for winning at Pac-Man. A lot of the decisions involving the utility function were made based on guessing and checking until the behavior evident in Pac-Man coincided with our preferences for how to play the game. Looking back on this project, there is probably a better way for how to come up with a utility function. If we were to do this project again it would also be worth exploring future depths of minimax and expectimax. Due to computer limitations and the amount of trials needed to draw conclusions, we could only explore up to depth four reasonably for both algorithms. It would be interesting to see how close to a perfect 100% rating we could obtain by investigating larger depths. The same goes for q-learning. By adding more games to the training count it would be interesting to see how close to perfection we could get.
Pacman%20Paper%20Final.docx