Introduction to AI - concepts Flashcards
current trends in AI
exploit the strengths of the computer and don’t model human thought processes
focus on particular tasks and not on solving AI as a whole
strong scientific standards
conference series
Biennial International Joint Conference on AI
Annual National Conference on AI
Biennial European Conference on AI
The birth of AI
1956, Dartmouth Conference
symbolic AI
model knowledge and planning in a way that is understandable to programmers
subsymbolic AI
model intelligence similar to a neuron
Why did the initial expectations of AI not work out?
lack of scalability
difficulty of knowledge representation
limitations on techniques and representations
Forward checking
Search
Keeping track of remaining legal values for unassigned variables
Terminate search if any variable has no more legal values
Local search for CSP
search
Work with complete states
Allow unsatisfied constraints
Min-conflict heuristic: select a conflicted variable and choose the value that violates the fewest constraints
Zermelo
Game-playing
One player can force a win or both players can force a draw
Retrograde analysis
Zermelo, game-playing
Generate all possible positions
Mark all positions where A would win…
Horizon effect
Game-playing
The catastrophy can be delayed by a sequence of moves that don’t make any progress
Forward pruning
Game-playing
Alpha-beta only prunes search trees when it is safe to do so
Null-move-pruning
game-playing
add a “null-move” to the search (assume the current player does not make a move)
if the null-move results in a cutoff, assume that making a move will do the same
Iterative deepening
game-playing
repeated fixed-depth search which works well for transposition tables
move ordering - heuristics
game-playing
domain-dependent heuristics:
capture moves first
forward moves first
domain-independet heuristics:
killer heuristics (manage a list of moves that produced cutoffs at the current level of search)
history heuristics (maintain a table of all possible moves; if a move produces a cutoff, its value is increased)
transposition tables - what does an entry store?
game-playing
state evaluation value
search depth of the stored value
hash key of the position
best move from the position (optional)
What techniques does AlphaGo use?
game-playing
deep learning
reinforcement learning
monte-carlo tree search
Inductive learning
Machine learning
Learn a function from examples
Ignores prior knowledge
Assumes examples are given
Credit assignment problem
Machine learning games
Delayed reward
Knightcap
Machine learning games
Learned to play expertly in chess
Improvements over TD gammon:
Temporal difference learning with deep searches
Played against partners on the internet (instead of self-play)
Simulation search
Machine learning games
Estimate the expected value of each move by counting the number of wins
At each chance node select one of the options at random
Make all move choices quicky
Often works well even if the move selection is not that strong - fast algorithm
UCT Search
Machine learning games
Best-known formulation of MCTS
Combines a UCB-based tree policy with random roll-outs
Exploitation vs Exploration
Choose move that has been visited most often (reliability) not necessarily the one with the highest value (high variance)
AlphaGo
MCTS, deep learning, reinforcement learning from self-play
MCTS: roll-out policy, learned evaluation function instead of real game outcomes
Policy networks
Machine learning games
How “good” is it to move to a position
Input position
Output position
