EPGY Day 5

Question of the Day: Rank these from Most Instantial to Most Procedural

• Movie, Basketball, Paper Pong, Regular Pong, Roller Coaster, Jam Session, Boxed Cake Baking, Ping Pong

Projects!

• Proposal
• Literature Review
• Doesn't start until Wednesday
• Competition Topics:
  • Mario AI
    • Player Modeling
    • Procedural Content Generation
  • Traveling Sales Person
    • TSP
    • A*
    • Mazes
    • Graph Search
  • PacMan
    • A*
    • Decision Trees/Graphs
    • Pathfinding
    • Finite State Machines
  • Flashlight Tag
    • Pathfinding
    • Case Based Reasoning
    • Finite State Machines

Lisp

• Lambda - a function without a name
• Anonymous function
• Alonzo Church - Lambda Calculus

What is AI?

• Calculators, Bicycles, Siri?
• Problem Solving
  • Science
  • Engineer
  • Professional
    • Journalism
    • Education
    • Business
    • Artisan
  • Artist
• Algorithms vs AI
  • What's your take on Problem Solving?

For the purpose of this course, we are letting the Turing Test guide our pursuit of AI.

Review

• Abstract Data Type: TREES!!
  • Lisp!
  • insert/delete
• Heaps
• http://www.sinbadsoft.com/blog/a-recursive-and-iterative-merge-sort-implementations/
• Compare Merge Sort with Heap

Math!

• Induction (logic): n^2
• Recurrence Merge Sort
  • http://www.cs.duke.edu/~ola/ap/recurrence.html
  • http://homepages.ius.edu/RWISMAN/C455/html/notes/chapter4/Recurrence%20Tutorial.htm
• NP - nondeterministic polynomial time
• Satisfiability
• Heuristics

Search: search is the process of examining future options to determine what immediate action should be taken

• Depth First: Stack
  • CYOA
  • Mouse Maze
  • Queens Problem
• Breadth First: Queue
  • Graphs!!!

Graphs

• Shortest Distance - Flood Fill
• A*: Using Heuristics
  • Manhattan Distance

Application - NP: Hard

• Declarative Optimization-Based Drama Management

Finite State Machines

http://www.willamette.edu/~gorr/classes/cs231/lectures/chapter9/arrays2d.htm

• Monday Meetings
• Journal 5
• Assignment 5
• Feedback