Week 10: Exercises

1. Tic-Tac-Toe

Consider the Tic-Tac-Toe program that we saw in the lecture. Make the following improvements:

  1. Modify the minimax player to calculate and print out the number of game states that it has considered when it makes each move.

  2. Modify the minimax player to print out the number of milliseconds that it takes to make each move.

  3. Add an unmove() method to the Game class, and modify the minimax() method to use it instead of calling clone(). Does this make the minimax player significantly faster?

  4. If the minimax() method finds a move for player 1 that results in a state with minimax value 1, then there is no need to consider any other moves, which cannot be any better. The same is true for player 2 if a move produces a state with minimax value -1. Implement this optimization, which is called extreme value pruning. Does this make the minimax player significantly faster? How does it affect the number of states that the agent considers when choosing a move from the initial state?

2. Coin Game

Consider the following game. There is a row of N coins on the table, with values V1, V2, ... VN. On each player's turn, they can take either the first coin in the row or the last coin in the row. Write a method that takes an array with the values of the coins, and returns the maximum amount of money that the first player can win if both players play optimally.

3. Ghost

Consider the following game. Let W be a set of words, each containing only lowercase letters from 'a' to 'z'. Two players take turns adding a letter to a string S, which is initially empty. A player loses if after their turn either

  1. they have made a word (i.e. S is a word in W), or

  2. no more words are possible (i.e. S is not a prefix of any word in W).

For example, suppose that W = { "chirp", "cat", "dark", "dog", "donate", "donut" }. The game might proceed as follows:

  1. A chooses d

  2. B chooses o

  3. A chooses n

  4. B chooses u

Now A has lost: if he chooses 't' he has made the word 'donut', and he cannot choose any other letter since then no other word will be possible.

Write a program that can play Ghost. Read the list of possible English words from this file. Only use words that consist only of lowercase letters a-z from the Latin alphabet. Your program should be able to play either as player 1 or 2.

Can you defeat your own program? If not, make it easier by modifying your program to choose its first move randomly from the set of all possible moves that don't lose immediately.