AI Fall 2007 Assignments and shell programs

Assignments Q2
- Written reviews:
  - Review 1 (.doc vers) Blind searching
  - Review 2 (.doc vers) Heuristic searching
  - Review 3 (.doc vers) Random methods
  - Review 4 (.doc vers) Look ahead, Minimax, Alpha-beta pruning
- Othello
  - Shell: see Course webpage, with referee.rb. First step is to make "pick()" beat "pick_rand()".
    As an example of an alternative look, here's a Tk version to start: othello_demo.rb
  - othello_referee with comments, explanation of the board
  - Write smart programs to play Othello
    - othello01.rb - Strategy 1: Pick max count versus Random pick, Sample output
      Strategy 2: Pick min count versus Pick max count, Sample output
    - othello02A.rb, othello02B.rb, etc - Investigate various strategies to determine your best strategy. For example:
      - If the space choice is a corner square, take this move. $corners = [11,81,18,88]
      - If the space choice is adjacent to a corner square, try not to take this move. $adjacents=[12,21,22,17,27,28,82,71,72,78,77,87] Sample output
    - othello3.rb Minimax (also with alph-beta pruning?) - look ahead several moves in order to evaluate your best and most realistic next move. In this process, give your opponent the benefit of the doubt (a good pick) when assume what the opponent move will be. This is a minimax concept.
      You'll need an "evaluate_board" method to give scores to particular boardstates.
      Example pseudo-code: Minimax, Minimax with Alpha beta pruning
  - Strategies to try
    - Strategy guide (scroll down to Introduction to Strategy)
    - Basic othello strategy
    - Othello strategy opening, midgame, endgame
  - evaluation functions
    - Strategy and board game programming (UCI)
    - Learning of Position Evaluation in the Game Othello (.ps)
    - Othello tournament player assignment from U Mass, Lowell
    - Project Othello at Columbia
- GHOST - also see course website
  - Minimax links
    - Slides from Russell/Norvig (see slide 6 for a picture)
    - Minimax tree, Game of Nim (McGill Univ)
  - For a complete description see Wikipedia.
  - dictionary.txt (or dictionaryshort.txt "aback" through "abating", 24 words, for initial experimenting)
  - Assignment One - ghost01.rb, Human vs Human, multi-player
    Write a program that facilitates two or more humans playing ghost. Players alternate naming letters which are appended to a string. If a player names a letter that forms a word, or if he or she names a letter that makes it impossible for the string to eventually form a word, and the next player challenges, then the offending player receives a letter (in order, G-H-O-S-T) and the challenging player begins a new string. If a player challenges incorrectly then he or she loses the round and the next player begins a new string. If a player receives all five letters to spell GHOST then he or she is out. Play continues until only one player is left, the winner.
    
    Example
    Player 1: C
    Player 2: C-A
    Player 3: C-A-T
    Player 1: C-A-T-E
    Player 2: C-A-T-E-G
    Player 3: C-A-T-E-G-O
    Player 1: C-A-T-E-G-O-R
    Player 2: C-A-T-E-G-O-R-I
    Player 3: C-A-T-E-G-O-R-I-C
    Player 1: C-A-T-E-G-O-R-I-C-A
    Player 2: C-A-T-E-G-O-R-I-C-A-L
    Player 3: *challenge*
    
    In this example Player 2 gets a G and Player 3 starts a new string.
    Note that in ghost "words" must have at least four letters, so Player 3 does not lose on CAT.
    
    ghost00.rb and ghost00.out1, a basic file reading program, reads dictionaryshort.txt
    sample game start 1: ghost01game, sample game start 2: ghost01game2
    sample game 1: ghost01sampleGame, sample game 2: ghost01sampleGame2
    example "proc calls" for a list of players or strategies: sample proc calls, or see array_of_methods.txt
  - Assignment Two - ghost02.rb, Multi-strategies in same game, computer plays
    Program the computer to play ghost.
    
    Sample output, smart computer, and Sample output, not smart computer
  - Assignment Three - ghost03.rb, Use recursion and minimax tree, player points of view alternate at different levels of recursive tree calls
    Program the computer to play ghost well.
    
    Minmax output1 + algorithm, output2 using "faster" algorithm (takes first good choice, not random) output3 using "faster" algorithm (takes first good choice, random)
N-Queens Problem
- ANSI Color Codes
- queens.rb - or see AI course website
- queens00.rb - Generate legal board configurations 1 queen per column. Print the evalution of the board, for N=4 and N=8
- queens01.rb - Hill climbing
  - Consider all 56 possible next boards formed by moving any one queen.
  - Evaluate h(board) for each of these.
  - If none is better than current h(board), quit.
  - Else, take the best as new current board and repeat.
  - One problem is local min, use random re-start.
  - Another problem is plateau, allow sideways moves.
  - Example algorithms for queens01.rb
  - Sample output for queens01.rb
- queens02.rb - Stochastic search
  - Consider all 56 possible next boards formed by moving any one queen.
  - Evaluate h(board) for each of these.
  - If none is better than current h(board), quit.
  - Else, weight each better board and choose the next current board at random.
  - One possible implementation is first choice, generates successor boards at random until one has a better h(board).
  - Example algorithms for queens02.rb
  - Sample output for queens02.rb
- queens03.rb - Local beam search
  - Use k hill climbs or stochastic searches in parallel.
  - But, at each step take the next best k successor boards from all searches.
  - Alternative would be for each separate search to take its own next best successor.
  - Sample output for queens03.rb
- queensStats.rb - basic example, also see Mr. Torbert's version from the ai website
- queensGA.rb - Genetic algorithm version, with crossovers and mutations
  - Generate 4 boards randomly
  - Clone the top ranked board and remove the lowest ranked board
  - Crossover "mate" each of the cloned top ranked board with one of the other two boards picked randomly. Randomly pick a crossover point.
  - If any of the 4 children from the crossover are duplicates, randomly mutate to generate a different child, so that all 4 children are unique.
  - You can also introduce mutations with a given probability at certain times in the process.
  - Sample output - solved 6 generations for queensGA.rb (storing conflicts with board state), another version (storing conflicts and non-conflicts with the board state)
- functionGA.rb (solve 1 or 2 of the following functions) (also see course website)
  - Function of a single variable
    - f(x)=|x|+cos(x), x in [-20,20], y in [0,25]
    - f(x)=(x^2+x)*cos(x), x in [-10,10], y in [-150,50]
    Steps
    1. Random population
    2. Sort
    3. Kill the worst half
    4. Pair up for breeding, use 0.4 0.7 0.9 1.0
    5. Blending
      - Beta=rand()
        newX1=Beta*x1+(1-Beta)*x2
        newX2=(1-Beta)*x1+Beta*x2
      - newX1=0.5*x1+0.5*x2
        newX2=1.5*x1-0.5*x2
        newX3=-0.5*x1+1.5*x2
        If newX out of bounds then add or subtract xmax-xmin (thanks to Alex Krzepicki)
        Take best two out of these three newX values
    6. Mutation
    7. Repeat from Sort
Assignments Q1
- Ladder programs, beginning search - depth first, breadth first, iterative deepening
  - ladder_shell.rb
  - ladder00.rb, sample output - input start word followed by 5 valid continuations (change 1 letter, stay in dictionary, same length, new word not already used)
  - ladder01.rb, sample output - same as ladder00 except the program randomly picks a word from a list of valid continuations. It's possible that the continuation list is empty, stopping the program
  - ladder02.rb, sample output - same as ladder01 except the final word needs to have different letters than the start word (letters can match but need to be in different possitions). The length of the ladder is not limited to 5, and it's possible to reach a deadend. Extra - can your program handle deadends, backtracking to find non-deadend path?
  - ladder03.rb, shell vers 1 or shell vers 2, sample output and another sample (uses ladder[-1] for next continuation word) - follow the algorithm on p. 77, depth limited search
  - ladder04.rb - iterative deepening: Start with a level limit of 1 and keep increasing until a path is found or you reach some higher limit level - iterative deepening- sample output
  - Depth-limited search algorithm from p. 77 in our text
  - ladder05.rb - breadth first: construct a list of possible paths, a list of lists and show breadth first search. sample output, discussion of output (.doc version)
  - Queue (breadth first) and stack (depth first) non-recursive, iterative, algorithm
- INTERIM GRADE-ALL LABS TO THIS POINT (pre-Romania)
- Romanian map problems - heuristic searches - informed search algorithms
  - romania00.rb: Build the Romanian map with a ruby program. Write a program to:
    1. read this file of cities: romania.csv (on the main AI course website) (romania1.txt) and
    2. convert the information to a ruby hash structure looking like this: map1.rb. Your program doesn't need to generate the %w syntax. The lists of cities need to be comma separated strings.
  - romania01.rb: (example starter hash table) Using the Romanian map, find a non-heuristic path, breadth first, from a start city to a goal city. This path does not need to be optimal and does not analyze distances. It only looks at connecting cities. Example output
  - romania02.rb:
    - Part A: Build a "hash of hashes" table, City1 => City2 => distance City1 to City2.
    - Part B: Using this new hash table, calculate the cost of your path start to goal city.
    - Example output
  - romania03.rb: Uniform cost search. Choose the next city in the path according to the cheapest path cost of known distances between the cities. Cost is the actual distance traveled from start city to the current city.
    - Example output
  - romania04.rb: Best First Search. Use the coordinates of each city, calculate estimated distances between each city and the goal city. Choose the next city in the path according to the cheapest path cost.. Cost is the estimated distance from current city to the goal city. locations.csv from from course website,
    - Example output
  - romania05.rb: AStar Search. Use the evaluation function for the cheapest cost: f(n) = g(n) + h(n). g(n) is the total actual distance traveled (see Uniform Cost search), h(n) is the estimated distance from the current city to the goal (see Best First Search).
    - Example output
  - romania06.rb: Heap version of sort. Use a heap data structure to keep the list of potential paths in a priority queue, the shortest path is always at the top of the heap. Each new path is added directly to the heap, so no separate sort is needed. Verify that your heap works for Uniform cost, Best First, and AStar searches.
    - Example output demonstrating a heap structure
    - Example output using a city list demonstrating a heap structure
    - Example output for uniform cost demonstrating a heap structure
    - Example output for astar demonstrating a heap structure
  - Extra credit map problems:
    - Heap sort version for AStar
    - River problem, see course website for data and Brian Hamrick's sample longest paths
  - Maps, best first, and AStar supplemental material:
    - Romanian map (pdf) and Romanian map (ppt) - for ppt files, save and then open with OpenOffice
    - Romanian map - heuristic (pdf) and Romanian map heuristic (ppt) - for ppt files, save and then open with OpenOffice
    - Best first slides (pdf) and Best first slides (ppt) - for ppt files, save and then open with OpenOffice
    - AStar slides (pdf) and AStar slides (ppt) - for ppt files, save and then open with OpenOffice
- Tile game programs:
  - tile_demo.rb
  - another tile_demo.rb
  - tile00.rb: mouse click on a tile adjacent horizontally or vertically to the white space tile and interchange "move" to the space (interchange the space and numbered tiles)
  - tile01.rb: board evaluator, underneath the tile grid print three heuristic evaluations of the current board state:
    - # of tiles in the incorrect spot (0 if the board is in the goal configuration)
    - manhattan distance: the sum of the distances of the tiles from their goal positions
    - linear conflict: for every two of the tiles being evaluated manhattan distance, if two are in the same row or column, add two to the manhattan score for these two tiles.
    - Goal board state:
```
           1  2  3  4
	   5  6  7  8
	   9 10 11 12
	  13 14 15 sp
    
```
  - Russell/Norvig Slides from Chap. 4 of our text, see pages 26, 27
  - Richard Korf slides - Design and Analysis of Admissable Heuristic Functions analyzing Tile puzzle class of problems
Ruby program examples
- add_string.rb
- add_string_2.rb
- add_string_3.rb
- demo_string.rb
- Example hash list for Romanian map

AI Fall 2007 Assignments and shell programs

Assignment One - ghost01.rb, Human vs Human, multi-player

Example

Assignment Two - ghost02.rb, Multi-strategies in same game, computer plays

Assignment Three - ghost03.rb, Use recursion and minimax tree, player points of view alternate at different levels of recursive tree calls