Week 1 Flashcards
Characteristics of Games
- Must make decisions in real time
- There are other agents who you do not control
- The benefits (or costs) of decisions you make depend on what other agents do
Strategy + interaction with other strategies = games
Blackjack is not a game since the dealer is using a fixed strategy, you know what they are going to do
s.g.
Such that
Game solving complexity
PSPACE (Harder than NP because game solving alternates existence with universal quantification)
Heuristic
Rules which are applied because they are found to have worked.
By trial and error
Notation for graphs
Nodes - represent the state of the puzzle
Edges - An edge from nodes i to j represent a direct move from state i to state j
Weights - c(i,j) represents positive distances (time or costs) associated with the move from i to j.
Otherwise use:
c(i,j) = 1 if there is a link i to j
0 otherwise
Dijkstras algorithm properties
Finds the shortest path from source to all nodes in the graph
Is complete - if there is a path from the source to the target this will find it
Finds the optimal or shortest path
Uninformed - doesn’t use any information you might have about the location of the goal
Human solving graph problems / Greedy Heuristic Search
Move to the state X seemingly “closest to the goal” with a heuristic function:
h(x) = estimated distance from x to the goal
Repeatedly move to the available node x’ connected to state x with the lowest value of h(x’)
Greedy Heuristic search properties / Human solving graph problems properties
Not complete - will not necessarily find a path even if one exists
Does not necessarily find the optimal path
Can be very fast
It is informed search: domain knowledge required to produce and evaluate a good heuristic
Can be made complete with backtracking
Dijkstra’s and Greedy prioritization
Dijkstra’s prioritises nodes closest to the source node
Greedy prioritises nodes closest to the goal, using a heuristic function to estimate the distance to the goal
A* algorithm
Combines Dijkstra and Greedy algorithms
g(x): The distance from the source s to the node x
- Dijkstras algorithm searches ordered on g(x)
h(x): the heuristic. An estimate of the distance of the node x to the goal t
- Greedy heuristic searches ordered on h(x)
A*: searches on their sum,
f(x) = g(x) + h(x)
The total estimated distance from source to goal through node x.
A* is essentially Dijkstra with f(x) replacing g(x)
What makes a good heuristic
Admissible
Monotonic
Informative
Admissible
For all nodes X, it is no longer than the true shortest distance to the goal t
h underestimates the distance to the goal
If the heuristic is admissible, when the goal is popped from the priority queue, the shortest path to the goal has been found
May still have to re-consider non-goal nodes if the heuristic is not monotonic
Monotonic
A heuristic is monotonic if h(x) <= h(y) + c(x,y)
If this is true for a heuristic when a node is popped from the priority queue the shortest distance to it has been found
Informative
Informative - As close as possible to the true distance without exceeding it
h0 is more informative than h1 if for all x, h0(x) >= h1(x) (so long as h0 and h1 are admissible
