COMP3411 Artificial Intelligence
Session 1, 2011

Week 8 Tutorial

  1. Suppose that a training set contains only a single example, repeated 100 times. In 80 of the 100 cases, the single output value is 1; in the other 20, it is 0. What will a back-propagation neural network predict for this example, assuming that it has been trained and reaches a global optimum? (Hint: to find the global optimum, differentiate the error function and set to zero.)

  2. Discuss how a neural network might be applied to each of the following tasks. For each task, describe how the inputs and outputs could be encoded, what network architecture and transfer function would be appropriate, what kind of pre- or post-processing might be helpful, and how the output of the network would be used within an overall system.
    1. playing tic-tac-toe
    2. recognizing postcodes written on letter envelopes
    3. predicting a person's risk of developing lung cancer, diabetes or heart disease
    4. making money on the stock market, or foreign currency exchange.

  3. Apply the alpha-beta search algorithm to the following game tree, indicating clearly the values of alpha and beta at each node as the algorithm progresses, and circling the nodes that would not be evaluated.

  4. The Chinook checkers program makes extensive use of endgame databases, which provide exact values for every position with eight or fewer pieces. How might such databases be efficiently generated, stored and accessed?

  5. Discuss how AI techniques might be applied to the following games:

  6. What is the time complexity of alpha-beta search, if the best move is always examined first (at every branch of the tree)?

  7. Bonus Challenge: Draw a game tree of depth 4, where each internal node has exactly two children. Assign the numbers 0 to 15 to the leaf nodes in such a way that the alpha-beta algorithm prunes as many nodes as possible. (one way to achieve this is to ensure that, at each branch of the tree, all the leaves in the left subtree are preferable to all the leaves in the right subtree, for the player whose turn it is to move). Trace through the algorithm and draw the shape of the pruned tree. Now draw another game tree of depth 4, but where each internal node has exactly three children. Assume that the leaves have been assigned in such a way that the alpha-beta algorithm prunes as many nodes as possible. Draw the shape of the pruned tree. How many of the original 81 leaves will be evaluated? Based on what you have found, can you explain why the time complexity of alpha-beta search is what it is?