Why are games important in the field of AI?
Games are a form of multi-agent environment –> What do other agents do and how do they affect our success; Cooperative vs. competitive multi-agent environments; Competitive multi-agent environments give rise to adversarial search a.k.a. games
Fun; historically entertaining
Interesting subject of study because they are hard
Easy to represent and agents restricted to small number of actions
Problem (and success) is easy to communicate
What is the relation of games and search?
opponent –> solution is strategy; time limits force an approximate solution
no opponent –> solution is method for finding the goal; heuristics and CSPs help finding the optimal solution
evaluation function –> estimate of cost from start
to goal through given node
evaluation function –> evaluate the quality of the position
examples –> path planning, scheduling activities
examples –> chess, checkers, Othello, backgammon
What are the different types of games?
Zero-Sum Games –> win, lose or draw
turn-taking –> player alternate moves
deterministic games –> no random components influence the game
games of chance –> random components influence the game
perfect information –> every player has all the information about the current position of the game
imperfect information –> not every player has the entire information about the game situation
What was Quevedos KRK machine?
A completely mechanical based piece of machinery which could automatically play the king against king and rook endgame of chess
It had a basic strategy and divided the board into 3 zones and therefore dependently made moves
What was Zermelos theorem?
The theorem stated that for perfect information, deterministic games, 2 player game either one of the two players can force a win or both players can force a draw
What is the retrograde analysis?
retrograde analysis is an algorithm which is based on Zermelos theorem which builds up a database if we want to strongly solve a game
Chess as an exapmple: has a database for all different endgames, cannot solve all positions of chess (especially the midgame and beginning game positions) since chess is very complex and not all positions can be stored
Several not too complex games are already solved by retrograde analysis
What are different methods to solve a game?
prove whether the first player will win, lose, or draw from the initial position, given perfect play on both sides
could be a non-constructive proof, which does not help in play
white cannot (forcibly) lose in chess if first move may be a pass
weak –> provide an algorithm which secures a win for one player, or a draw for either, against any possible moves by the opponent, from the initial position only
strong –> provide an algorithm which can produce perfect play from any
What is the Game of Nim?
Starts with a certain amount of matches
The moves of the players alter and each player is allowed to remove 1, 2 or 3 matches
The player who does not have any moves left looses
One can solve the game of Nim by building a tree, e.g. Nim5 (i.e. with 5 matches) –> if all possibilities are listed one can see that player one cannot lose if he/she picks only one match at the beginning
What is Minimax search?
The Minimax principle of Neumann is that both players want to optimize their result –> that means in a zero-sum game it also minimizes the result of the opponent
Aplha-Beta Search is a variant of Minimax, it works very similiar but is more efficient –> can search twice as deep as Minimax in the same amount of time
What is the Shannon number?
Shannon number: 10^120 is the approximate number of possible chess games evaluated by the average possible moves in a position and the average length of a chess game
Shannon is proven to be wrong, the actual number is with 10^3000 even higher, taking the different order of moves into account
Why can’t Chess be solved by Minimax?
Not every two-person-game can be solved by Minimax since there are complex games which outcomes cannot be evaluated by any computer (Shannon number)
Therefore chess cannot be solved by a computer –> chess program must approximate perfect play
What is the difference beteween human und machine thinking?
A computer can search until a certain depth in seconds –> some (for humans) quite difficult positions are evaluated in an instant by a chess program
A human has intuition and a abstract level of thinking, therefore he could be better in some some situations were positional play comes in hand –> computers are limited to a certain depth and therefore cannot see these patterns
What is the key idea for imperfect real world decisions?
Since most of the games are to complex to be fully solved by a search tree Shannon proposed that one should cut off the search earlier and use a heuristic evaluation function for the position
What search types do chess programs use?
The early chess programs first used selective, then exhaustive search and at the end they combined the two search types (at first exhaustive search and then selective search near the leaves)
What is forward analysis?
It’s a more natural way of analyzing a game because it proceeds forward and not backwards (e.g. retrograde analysis)
Common examples are:
What is Brute Force and Selective Search?
Shannon Type-A (Brute Force) –> search all positions until a fixed horizon , positions after that hotizon are ignored
Shannon Type-B (Selective Search) –> prunes uninteristing lines because of their not promising evaluation
What are evaluation functions and how do we use them?
The complete tree is not searchable –> Minimax is applied up until a certain depth (serch horizon)
Evaluation functions truncate the tree (depth & selecetion)
They use a static heuristic evaluation function –> the goodness of a position is evaluated
Positive values are good for player 1, negative for the other player
The performance of the quality of the evaluation function
The computation should not take too long
Most evaluation functions are linear combinations of features
How does selcetive search work?
The complete tree is not searchable –> the scope of the search tree is limited, therefore only promising moves evaluated by an heuristic function are taken into account
Why is evaluation not very robust?
small changes may affect the current position drastically
evaluation and search are not independent –> what is taken care of by search must not be evaluated
evaluation should only be applied in to stable (quiescent) positions
What are different examples for evaluation functions?
Tic-Tac-Toe –> f(n) = 3-lenghts open for me - 3-lengths open for you (3-lenghts are columns, rows and diagonals9
Chess –> f(n) = w(n)/b(n) (w(n) and b(n) are the sum of the point values of the remaining pieces), DeepBlue used over 6000 features
State of the art programs use non-linear functions
What is quiescence search?
Only useful for quiescent positions (stable positions, where no winning moves are at hand)
Search depth is reached –> compute quiescence state evaluation heuristic
If state is quiescent:
proceed as usual
Else (state is volatile):
increase search depth
Goal: tries to simulate the human intuition about whether to abandon a bad-looking move or search a promising move to a great depth. It makes sure that there are no hidden traps and to get a better estimate of its value
It tries to prevent the horizon effect
What is the horizon effect?
The horizon effect, is the behavior that if we search until depth n, it may be that n + 1 or other closely following sequences may be dramatically change the evaluation of the game
(very good moves or hidden traps cannot be found)
What are transposition tables?
Problem: repeated states can occur –> may lead to exponential growth of the tree
basic idea: store found positions in a hash table if it occurs a second time the values of the nodes do not have to be computed a second time
What are zobrist hash keys?
Zobrist hash keys are an implementation of transposition tables
each position has a 64 string, with every move the position is altered (may be that different positions have the same hash key
Why should deeper search work?
If we have a perfect evaluation function, we do not need search
If not, we need search but does the deepness of the search actually help
Game Tree Pathologies –> deeper search constructed in the wrong way can actually resutlt in bad performance
Diminishing returns –> the gain of deeper searches goes down with the depth
How did the match between Kasparov and Deep Blue go?
Kasparov won the first match in 1996 –> he paid his respect to the program
Kaspoarov lost the second math in 1997 –> he was surprised by the human-like moves and accused IBM of cheeting
What were the different views on the game between Kasporov and Deep Blue?
There were different reactions on the win of Deep Blue against Kasparov
“Saying Deep Blue doesn’t really think about chess is like saying an airplane doesn't really fly because it doesn't flap its wings” - Drew McDermott
“Chess is the Drosophila of artificial intelligence. However, computer chess has developed much as genetics might have if the geneticists had concentrated their efforts starting in 1910 on breeding racing Drosophila. We would have some science, but mainly we would have very fast fruit flies.” - John McCarthy
What are search extensions?
Search extensions try to expand the search by skipping possible forced moves (recaptures or checks)
Search extensions have to be designed, so that they finish in a finite amount of time
What is forward pruning and what is a common exmample of forward pruning?
There different techniques and algorithms of forward pruning, but the basic idea is to exclude possible moves, because of their bad evaluation
e.g.: Null-Move Pruning:
Idea: in most games, making a move improves the position
Approach: add a „null-move“ to the search, i.e., assume that current player does not make a move, if the null-move search results in a cutoff, assume that making a move will do the same
Danger: There are positions in which not making a move is better for the evaluation –> but that can be improved by a condition, when the null-move pruning algorithm should not be used
How does iterative deepening work?
Algorithm: It follows one path until the horizon instead of checking all different nodes on one level
Goal: Less memory and sometimes faster results then Breadth First Search
It can be improved with dynamic move ordering, e.g. what worked last move well is the first iteration on the next move
It simplifies the time management –> since one could calculate how long it takes to iterate one path and therefore how long the next probably will take
What are the differences between human and computer game playing?
Humans work on a pattern base and computer on a search base. As a result, it is more difficult for people to solve a chess puzzle that enables checkmate in 2 moves than a game state that one recognizes but still lasts 120 moves. For computers it is exactly the opposite.
What is a game tree and how is it constructed?
A game tree represents all possible moves and game states during a game from the selected beginning to all finishes. A game tree connects positions by moves. Where positions or game states are nodes and moves are edges. The root of the tree is the initial game state. From there an edge is drawn for each possible move of the player. This continues for each node until all leaves are finished game states. By applying heuristic functions this tree can be used to find the best path.
How does Retrograde analysis work?
Generate all possible positions (preferable with a database, still a problem with bigger games)
Find all positions that are won from player A ()
i.) mark all terminal positions that are won for A
ii.) mark all positions from which A can get to a position
iii.) mark all positions where B is to move and all moves lead to
iv.) if there are positions that not have been considered goto
Find all positions that are won from player B analouge to 1
All remaining positions are draw
Why is exhaustive search infeasible and what strategies can you employ to solve that problem?
Shannon did proove that there are in average 10120 different chess games. This number is bigger than the amount of atoms in the universe. It simply cannot be computed. The best solution would be a Shannon Strategy.
What are Shannon‘s strategies?
Finish the search earlier and determine whether current depth is sufficient enough. For this we use heuristic evaluation functions. Two Examples of strategeies are:
Shanon - A: Brute Force search all position till a certain depth
Shanon - B: Selective Search; drop uninteresting paths, like humans do
What is the horizon effect and how can it be countered?
The horizon effect comes from the fact that machines do search only a small portion of the possible moves. So there is a possibility that the chosen move is an error which can not be “seen” because it is outside the search perimeter (i.e., beyond its “horizon”).
Search Extensions by example with. Forward Pruning, Null-Move Pruning, Iterative Deepening, Move Ordering, Transposition Tables
What are the differences between selective search and (depth limited) exhaustive search?
Selective search uses techniques and algorithms, so that it does not search all possible paths but only those which are relevant. (depth limited) exhaustive search searches all possible paths to a certain depth.
What strategies have been used to combine these two?
Quiescence Search, Search Extension
What are the key ideas behind techniques such as transition tables, Zobrist keys, null-move pruning, …?
Add a null-move to the search i.e. assume taht the current player doesn’t make a move. If the null-move results in a cutoff, assume that making a move will do the same.
Different sequences of the same moves come to the same result: Find them and save them in Hash Tables, so that you have to compute / search only once.
Zobrist (Hash) Keys
A way to store the sequences of moves in the transposition table. Take an 3d-array with arbitrary long random int numbers (for example 64 bit or even longer) as values. The coordinates are piece type, location and color. Initialize a 64 bit Hash Key with 0. Now each turn you need to look up the value from the moved piece in your array and xor it with the last position of the piece and afterwards xor the result with the hash key. If the last position is empty use 0 instead. Biggest plus is that it can be updated incrementally.
Pruning is part of a heuristic, which removes completely certain branches of the search tree. You can do this because the algorithm knows, or thinks (Dangerous!) that the tree does not change the result of the search. Forward pruning in particular always involves some risks to overlook something, with influence on the root score.
A deterministic, perfect information, 2 player game can be sorted in one of three categories:
Player 1 wins
Player 2 wins
Both Player can force a draw
Solving a Game ultra weakly
Prove whether the first player will win, lose or draw from the initial position, given perfect play from both sides
by non-constructive proof, which does not help in the play
by complete min-max or alpha-beta search
Solving a Game weakly
Provide an algorithm which secures a win for one player or a draw for either, against any possible moves from the opponent, from the initial starting position only
Solving a Game strongly
Provide an algorithm, which can produce perfect play from any position ⇒ mostly with some kind of database
We do evaluation only during quiescent states.
Those states are without wild swings in value in the near future
states in the middle of exchange are not
When search depth is reached look whether this is a quiescence state
if not search further until you find one. Evaluate Heuristic
When a force move is found look further. The reason is that a forced move narrows width of the tree. Be careful, search must always terminate somehow.
Crucial to the performance of alpha-beta search
Domain dependent heuristics: capture and forward moves first
Domain independent heuristics: killer heuristic (if there is a strong threat, this should be searched first; history heuristic (if a move produces a cutoff, its value is increased)
Do Deeper Searches necessarily help?
It does but only to a certain degree of deepness. The deeper the less efficient.
Game tree pathologies
What have been the key events in game playing?
1912, Quevedo´s KRK machine
1912, Zermelo’s Theorem
1950, Shannon´s proposal
1975, Alpha-Beta Search
1996, Garry Kasparov vs Deep Blue 1st match
1997, Garry Kasparov vs Deep Blue 2nd match
2015, AlphaGo beats Fan Hui
2016, AlphaGo beats Lee Sedol
2017, Alpha Zero beats the best programs in Shogi, Chess and Go