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?

Games

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

1912

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?

ultra-weak

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

position

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:

Minimax

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)

Algorithm:

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

i.)

ii.) mark all positions from which A can get to a position i

ii.)

i

iii.) mark all positions where B is to move and all moves lead to i

iii.)

iv.) if there are positions that not have been considered goto ii.

iv.)

ii

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”).

Solutions:

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, …?

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.

Transposition Tables

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.

Forward Pruning

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.

Zermelo Theorem

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

Quiescence Search

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

Search Extensions

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.

Move Ordering

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

diminishing returns

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

Last changed5 months ago