Games, Search and AI Agents

1 Explain how minimax with alpha-beta pruning chooses a move in a two-player game. 5

One mark for each of the following, to a maximum of 5.

• The game is represented as a tree of moves and replies
• Leaf positions are scored (by the result or an evaluation function)
• Scores are passed up: maximum at MAX's turn, minimum at MIN's turn
• Assumes the opponent plays their best reply
• Alpha-beta skips branches that cannot affect the result, once a move is shown to be worse than one already found
• It gives the same move as minimax with less searching

Model answer. The game is represented as a tree in which each branch is a legal move and the replies to it. Positions at the bottom of the tree, the end of the game or the search's depth limit, are given scores, using an evaluation function if the game is not over. The scores are passed back up the tree: at MAX's turns the highest child score is taken, and at MIN's turns the lowest, because minimax assumes the opponent always plays their best reply. The move at the root with the best backed-up score is chosen. Alpha-beta pruning keeps track of the best score each player is already guaranteed, and skips the remaining replies to any move once one reply shows it is worse than an option already found, so it reaches exactly the same move as minimax while searching far fewer positions.

2 Explain how AlphaZero learned to play chess to a superhuman level. 4

One mark for each of the following, to a maximum of 4.

• It was given only the rules, with no human games or strategy
• It played games against itself (self-play)
• Monte Carlo tree search guided by its neural network chose the moves
• The network was trained to predict the search's moves and the games' winners, so it improved, and the loop repeated

Model answer. AlphaZero was given only the rules of chess and no human games or strategy. It played millions of games against itself, choosing each move with Monte Carlo tree search guided by a neural network that suggested promising moves and estimated who was winning. After the games, the network was trained to predict the moves the search had chosen and the eventual winners, which made it better, so the next round of search and self-play was stronger still. Repeating this loop, it reached a superhuman level within a day of training.

3 A company wants an AI agent that can manage staff calendars and send emails. Evaluate the risks and suggest safeguards. 6

One mark for each of the following, to a maximum of 6.

• Risk: harmful or irreversible actions, e.g. deleting meetings or sending wrong emails
• Safeguard: least privilege / only the permissions needed
• Safeguard: human approval before sending emails or other risky actions
• Risk: prompt injection from incoming emails telling it to do things
• Safeguard: treat email contents as data, not instructions; limit actions they can trigger
• Other: errors compound over many steps; logs, testing and step limits
• Privacy risk: access to personal data in calendars and emails

Model answer. The agent could take harmful or irreversible actions, such as deleting meetings or sending a wrong or embarrassing email to a client, so it should be given only the permissions it needs, for example read access to calendars plus the ability to draft but not send, and a person should approve every email before it goes out. Because it reads incoming email, it is exposed to prompt injection: a message could contain instructions such as forwarding confidential files, so email contents must be treated as data, never as instructions, and the actions they can trigger limited. It also handles personal data, so access should be restricted and logged for privacy. Finally, small errors compound over many steps, so the company should test it on realistic tasks, set step limits, and keep logs of every action for review. With these safeguards the benefits of saved time can outweigh the risks, but it should start with low-risk tasks.