An Introduction to to Artificial Intelligence
#Seth Juarez

A high level overview of AI concepts.

Path finding.
What is the best way to get to work?
The moving squares game (put them in order) is also a path finding problem.
We are going to look at how you could solve that with a computer.

A well defined pathing problem has 5 components:
* states
* initial state
* successor function
* goal test
* path cost

Puzzles problem:
States – 8 number tiles and a blank
Initial State – some arrangement
Successor function – swap the blank with a number
Maximum of 4 possible options: left, right, up, down
Goal test – are they in order
Path cost – 1

uninformed search options
breadth first search
uniform cost search
depth first search
depth limited search

Looking for an algorithm that is complete and optimum

Wrote the puzzle as a game

Write solvers for each of the search options to try them out

Breadth First Search
Explore each option for every move. Check that move, then check the next one. Use those as the starting point for the next level. Explore every option at each level.
It is complete – it will find a solution
It is not necessarily optimal – it might not find the shortest solution in cases where the path cost is something other than 1 (a non-decreasing cost function).

Depth First Search
Go down the entire path from a move until you exhaust the possibilities. May essentially overflow the stack and never find a solution.
Possibly not complete, probably not optimal.

Depth Limited Search
Limit how far down you go while doing a depth first search.
Complete only if you set your limit far enough. Compensate by increasing the limit if a solution is not found. Knowledge of the possible limit improves this.
Optimal – it can be if you start with the correct limit. If you set the limit to 3 when it should be 4, then you either don’t get the answer orhave to run again with a higher limit, which is waste.
If you set the limit to 5 when it should be 4, you will search more nodes than you need to.

Informed Search
Define a heuristic function (A*, for example)
Take in to account how long it has taken you to get there already to inform your depth.
Completeness depends upon your heuristic function
So for a real-world map problem, straightline distance would be a good choice
If you have an “admissible heuristic function” A* is complete and optimal

Adversarial Search
Chess solver, for example
Tic Tac Toe example – a computer solver cannot be beat (will always result in a tie unless you make a mistake)

minimax algorithm – Minimize the maximum of the other player (take the move that helps your opponet the least)

alpha-beta pruning – only expand the branches that are better than your current state
Makes the assumption that the opponent plays optimally, which may cause a problem

I should point out he has some pretty awesome visualizations of these that are available on his github account. [https://github.com/sethjuarez/grappr]