COMP316A: Artificial Intelligence Techniques and Applications

- Assignment 2: GA mania and alpha beta pruning -

This assignment is marked out of 60, with a maximum of 25 marks each for the first two parts, and a maximum of 10 marks for the last part.
  1. Implement a genetic algorithm for solving the set cover problem. Your program will be given strings of characters (you can assume that they are sets, i.e. a character occurs at most once in any one string) and should find the smallest subset of these strings that covers (i.e. contains) all the characters present in the union of the strings. For example, with input strings ABC A BC C the program should output the solution ABC, which is a one-element subset of the set of strings that covers all three characters that occur in the union of the four input strings. A binary representation of the individuals in the population, indicating whether a particular string is present or not in the corresponding candidate solution, is probably the best way to represent this so that a genetic algorithm can be applied.

    Your program must accept command-line arguments in the following format:

    java SetCover <population size> <mutation rate> <number of iterations> <string 1> <string 2> ...

    and output the best individual (i.e. set of strings) found in the given number of iterations. The strings must be output on a single line, separated by spaces.

    For example, the command-line:

    java SetCover 50 0.05 50 ABC ACD D A C

    should produce the output

    ABC ACD

    In this example, the best solution was found, a two-element set with no missing characters, but this may obviously not be the case in general for a fixed number of iterations. You should design your genetic algorithms so that the likelihood of an optimum solution is maximized for a given number of iterations.

  2. Implement a tic-tac-toe playing program with a computer player based on minimax search. The program must allow a human player to enter moves at the command-line, and show a textual description of the board after each move. When a computer move has been performed the program must also output the number of nodes in the game tree that have been explored to generate that move.

  3. Implement alpha-beta pruning in your program. Make sure you give the modified program a different name.

Make sure ALL the code you submit is your own code. Also, make sure your code is well-documented with lots of comments.

Other Information

Value: 11% of the final grade
Due date: Wednesday, 26 March, midday

No extensions will be granted except for sound, documented, medical reasons.