Python Project: Multi Agents Added To Pacman, Including Ghosts, and Using Minimax Search Design (and below this, compared to the Expectimax Search with a better evaluation function):

We designed agents for the classic version of the Pacman game which was provided to us, including ghosts.

We implemented minimax search first (and later expectimax search) and tried out evaluation function design.

We designed a Reflex Pacman Agent that had to consider both food locations and ghost locations in order to perform well.

We found that this agent would likely die if 2 ghosts were on the default board, unless the evaluation function was quite good.

We altered the distance to food by using reciprocal values to try a new feature.

The evaluation function evaluates state of the game with an action for that game state as a pair, so that in later parts of the project, you could evaluate states.

Default ghosts were random, but you could also use directional ghosts, and to determine whether our agent was improving, we ran with fixed random seeds (same random choices every game).

We then wrote an adversarial agent for Pacman in the Minimax Agent class and it had to work with any number of ghosts, with multiple min layers, one for each ghost, for every max layer.

We were given an evaluation function which scored the leaves of the minimax tree.

A single search play was considered to be one Pacman move and all the ghosts' responses, so depth 2 search will involve Pacman and each ghost moving 2 times.

The solution was to explore the correct number of game states, to know whether or not you did your implementation correctly.

The evaluation function was given to us and checked that we were evaluating game states rather than actions, as we were for the reflex agent, who evaluated both food and ghost locations to perform well.

Look ahead agents evaluate future states where as reflex agents evaluate actions from the current state.

Python Project: Multi Agents Added To Pacman, Including Ghosts, and Using Expectimax Search Design with better evaluation functions:

Playing On Large Pacman boards: Pacman was good at not dying but quite bad at winning.

He thrashed around and when next to a dot, would not eat it because he did not know where he'd go after eating the dot.

If Pacman thought his death was unavoidable, he tried to end the game ASAP, because of the constant penalty for living, and with random ghosts not always the best choice, but Minimax agents always assume the worst.

Alpha-Beta pruning agent: to more efficiently explore the minimax tree.

Alpha-Beta Agent's minimax values: were identical to the Minimax Agent minimax values, although the actions it selects can vary because of different tie breaking behavior.

The code worked if: the correct number of game states were explored and it was important that we performed alpha beta tree pruning without reordering a node's children.

Successor states had to be processed in the correct order.

Alpha-Beta pruning was not done on all of a node's children, so an equal amount of alpha-beta pruning was not done for each game state explored.

Expectimax Agent: useful for modeling probabilistic behavior of agents who may make suboptimal choices.

Random ghosts are not optimal minimax agents.

Expectimax Agents: no longer take the minimum over all ghost actions, but the expectation is according to your agent's model of how the ghosts act.

To simplify: we assumed we would be running against an adversary which chose amongst their legal action list uniformly at random.

We Noticed: a more cavalier approach in close quarters with ghosts. If Pacman perceives that he could be trapped but might escape to grab a few more pieces of food, he'll at least try.

A better evaluation function: it evaluated future states, rather than actions from the current state, as the reflex agent did.

Evaluation function features: based on how important you think it is, such as distance to food, locations of ghosts, etc.