**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]