CPSC 3750 - AI 2009-01 Resources for problems/puzzles/games ---------------- 8 or 15 puzzle. See text. TSP = travelling salesman problem. http://en.wikipedia.org/wiki/Traveling_salesman_problem - Some problem instances (difficult ones) are at: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ Rubik's cube: http://www.rubiks.com http://en.wikipedia.org/wiki/Rubik's_Cube (3x3 cube is the classic. Also try: 2x2, 4x4 and 5x5) Gomoku (aka 5 in a row Tic tac toe) http://en.wikipedia.org/wiki/Gomoku http://www.sharewarejunkies.com/01zwd3/tictactoe.htm Reversi (aka Othello) http://en.wikipedia.org/wiki/Reversi Checkers http://en.wikipedia.org/wiki/Checkers http://www.cs.ualberta.ca/~chinook/ Lines of Action http://www.cs.ualberta.ca/~darse/LOA/ Scrabble* http://en.wikipedia.org/wiki/Scrabble http://en.wikipedia.org/wiki/Scrabble_letter_distributions - word lists: http://www.picozip.com/prt/download_Dictionary.html?df=english.zip http://wordlist.sourceforge.net/ Coding resources - some of the algorithms described in your text are implemented in a code repository, available from: http://aima.cs.berkeley.edu/ You are free to use it if it helps you. Proposed projects ------------------ For each of the projects described here and for any other project you might propose to examine, you need to submit a short written report. You will also be required to demo your project. 1) Exercise 4.18 from p. 136 in text, for the 8 and 15 puzzle. You must also use Gaschnig's heuristic (see Exercise 4.9). Compare your results. 2) Exercise 4.18 from p. 136 in text, for the TSP. Implement a hill-climbing heuristic for TSP, compare with A* and RBFS, and discuss your results. 3) Exercise 4.16 4) Design an agent that solves Rubik's cube puzles. Design a heurisitic function and apply A* search and RBFS on a set of randomly generated puzzles for 2x2 3x3 4x4 and 5x5 cubes. Compare the performance of the algorithms by counting the number of states generated. Discuss your findings. 5) Exercise 6.4 from p. 191 with any of the games described in the first part of this file (except for scrabble). 6) Exercise 6.6 for the game Scrabble. For this project ONLY, you are allowed to work in a team of two. SCHEDULE - decide on a project by Feb 13. You need to confirm your project with me before Feb 13. - week 14 (April 7-9): project report due. Demos will be organized.