Exam 2 games Flashcards
Draw game tree for the game of nim
Rules: Players remove on turn 1, 2, or 3 matches.
The player who takes the last
Players remove on turn 1, 2, or 3 matches.
See image
In the game of Nim What initial move should player choose to win
Rules: Players remove on turn 1, 2, or 3 matches.
The player who takes the last
If player 1 plays move 1
then regardless of what
player 2 plays, player 1
always has a winning reply.
In a zero-sum game both players try to optimize (maximize) their result. If Player 2 maximizes its score, it minimizes the score of Player 1.
Search can thus proceed by propagating?
- maximum score of all moves if it is player 1 to move
- minimum score of all moves it it is player 2 to move
Name the search principle
that proceed by propagating
- maximum score of all moves if it is player 1 to move
- minimum score of all moves if it is player 2 to move
Minimax principle (Neumann)
What is alpha-beta-search
- an efficient variant of minimax
- computs exactly the same result as minimax
- without visiting every node in the tree
How fast is alpha-beta-search in comparison with Minimax?
With a good move ordering, it can search twice as deep as minimax in the sam amount of time
Chess
- Average number of possible moves for each player in a position is 30
- The average length of a (human) chess game is about 40 moves for each player (80 half-moves or „plies“)
What is the nmber of possible move in a chess game (also referred to as Shannon Number)?
30^(2x40) = 10^120
What conclusions can we draw from Shannons Number
- chess connot be solved in practice
- a chess program must approximate perfect play
Match each game with the size of a game tree
- Nim-5
- Checkers
- Chess
- Go
a. 10^5 nodes
b. 10^360 nodes
c. 10^123 nodes
d. 10^31 nodes
1a
2d
3c
3b
What is Shannon Type-A and Type-B search also called?
Brute Force and Selective Search
What does Selective Search do?
prunes uninterestiong lines (as humans do)
What kind of search does the drawing refer to?
alpha-bea - seach all variations to a certain depth
What kind of search does the drawing refer to?
Selective Search
- limit the breadth of the search tree
- only search the n most promising moves
Selective Search
What kind of function decides which moves are most promising?
a heuristic function
What does an evaluation function or stativ valuator do
it evaluate the “goodness” of a game position
