Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

JKU: "Introduction to AI" by Johannes Fürnkranz (2024W) > Game Playing (part of exam 2/3) > Flashcards

Game Playing (part of exam 2/3) Flashcards

1
Q

What two forms of multi-agent environments (games) are there?

A

cooperative vs competitive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Why study games?

A
  • fun
  • historically entertaining
  • interesting subject of study bc they are hard
  • easy to represent
  • agents are restricted to small number of actions
  • problem and success are easy to communicate
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

True or False: Games have no adversary, Searches do.

A

False. Searches have no adversary, but Games do.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

True or False: In Search, the solution is to create a method for finding the goal.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

True or False: In Games, the solution is to win the game.

A

False. The solution is the strategy that specifies the next move for every possible opponent reply.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

True or False: In Search, due to heuristics and CSP techniques an optimal solution can never be found, only an approximate one.

A

False. Heuristics and CSP techniques can find an optimal solution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

True or False: In Games, due to time limits an optimal solution can never be found, only an approximate one.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

True or False: The evaluation function in Search estimates the cost from start to end.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

True or False: The evaluation function in Games estimates how many moves it will take to win the game.

A

False. The evaluation function evaluates the “goodness” of the current game position.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are Zero-Sum-Games?

A

One player’s gain is the other player’s/players’ loss.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Types of games are separated into a two-dimensional table. What are the two axes’ of the table?

A
  • deterministic games vs games of chance
  • perfect information vs imperfect information
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are deterministic games?

A

games without random components

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are games of chance?

A

games with random components

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does ‘perfect information’ mean, in regards to Games?

A

every player is able to see the entire game situation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does ‘imperfect information’ mean, in regards to Games?

A

not every player/no player is able to see the entire game situation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are examples of deterministic games with perfect information?

A

chess, checkers, GO, Othello

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are examples of deterministic games with imperfect information?

A

Battleship, Kriegsspiel, matching pennies, Roshambo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are examples of games of chance with perfect information?

A

Backgammon, Monopoly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are examples of games of chance with imperfect information?

A

Bridge, Poker, Scrabble

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Who was responsible for the following achievements in the history of Search in Game Playing?

  1. Computer considers possible lines of play.
  2. Algorithm for perfect play.
  3. Finite horizon, approximate evaluation.
  4. First computer chess game.
  5. Machine learning to improve evaluation accuracy.
  6. Selective Search Programs.
  7. Pruning to allow deeper search.
  8. Breakthrough of Brute-Force Programs.
A
  1. Babbage
  2. Zermelo, Von Neumann
  3. Zuse, Wiener, Shannon
  4. Turing
  5. Samuel
  6. Newell, Shaw, Simon, Greenblatt, Eastake, Crocker
  7. McCarthy
  8. Atkin, Slate
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What was Quevedo’s KRK machine?

A

A machine “El Ajedrecista” that was able to automatically play and win the KRK chess endgame.

  • white Rook and King are on fixed position
  • black King is anywhere within a specific area of the chess board
  • depending on the starting position of the black King the machine followed a basic strategy of moves
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Was is Zermelo’s Theorem?

A

Ernst Zermelo provided a first general formalization of game playing for…
* deterministic
* 2-person
* perfect information
games.

Theorem states in such games either one player can force a win or both players can force a draw.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

How does the Retrograde Analysis Algorithm work?

A
  1. generate all possible positions
  2. find all possible or terminal positions that win for player A and mark them “A”.
  3. find all positions that will directly lead to a position marked “A” also mark it “A”.
  4. repeat 2 and 3 for player “B”.
  5. all remaining positions are marked “draw”.
  6. put all these positions and marks in a database.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is ultra-weak Game-Solving?

A
  • prove from the starting position whether the first player of a game will win/lose/draw, given perfect play on both sides.
  • can be a non-constructive proof, which doesn’t help in play
  • can be done via a complete minimax or alpha-beta search
25
Q

What is weak Game-Solving?

A

from the starting position, provide an algorithm which secures a win/draw for one player, against any possible moves of the opponent

26
Q

What is strong Game-Solving?

A

from any position, provide an algorithm which can produce a perfect play

27
Q

For what (kind of) games is Retrograde Analysis working well/not well?

A
  • best for small games: Tic-Tac-Toe, Go-Moku, Connect-4,…
  • the bigger the board, figures moves etc, the more possible game states need to be stored –> RA is too complex for most games
  • Checkers: only recently solved
28
Q

How does the game of Nim work?

A

There are five matches. On turn, players remove either one, two or three matches. The player who takes the last match wins the game.

29
Q

What is a game tree?

A

a graphical representation of all possible states of a game

30
Q

What is the Minimax Principle (Neumann)?

A

In a zero-sum game with two players, both players try to maximize their score and minimize the other’s score.

Search can proceed by propagating…
* the maximum score of all moves, if it’s player 1 to move.
* the minimum score of all moves, if it’s player 2 to move.

31
Q

What is the Alpha-Beta-Search?

A
  • a very efficient variant of Minimax
  • computes the same result als Minimax
  • doesn’t visit every node in the tree
  • can search twice as deep as Minimax
32
Q

What is the Shannon Number?

A

It’s a number for formalizing chess, calculated by Claude Shannon.

It combines…
* the average number of possible moves each player can make from any game state (30)
* and the average number of chess moves of each player in a game (40)

30^(2x40) = 30^80 = 10^120

33
Q

What is a plie in a game of chess?

A

1 plie = half a move = one player make one move
2 plies = one move = each player makes one move

34
Q

When is solving any kind of chess state easy for a computer?

A

when there are very few possible moves to make (bc then there is less computing to complete to find the best next move).

35
Q

When is solving any kind of chess state easy for a human?

A

if the figures on the board form game states that are well known or easily recognizable for certain strategies.

36
Q

When is solving any kind of chess state hard for a computer?

A

when there are a lot of possible moves to make (bc then there is a lot of computing to complete to find the best next move).

37
Q

When is solving any kind of chess state hard for a human?

A

if the figures are randomly put on the board and form no plausible or usual game states which would be well known or easily recognizable for certain strategies.

38
Q

What are Imperfect Real-World Decisions?

A

The problem with complex games (Chess, Checkers) is that the search tree is too big to reach the terminal states.
The key idea (by Shannon) is to cut off the search earlier and use heuristic evaluation function to evaluate how promising each position is at the cut-off and if a position needs to be searched deeper.

39
Q

What is Shannon Type-A Search?

A

Brute Force Search.
Search all positions until a fixed cut-off-horizon.

40
Q

What is Shannon Type-B Search?

A

Selective Search.
Like humans, it prunes uninteresting lines.

41
Q

What is more effective: Brute-Force or Selective Search?

A

Shannon preferred Selective Search but Brute-Force Search outperformed it later on.
Current programs use a mixture.

42
Q

If the complete game tree is not searchable, what possibilities are there to limit the search?

A
  1. limit the depth of the search: search all variations to a certain depth, then apply the evaluation function at the search horizon
  2. limit the breadth of the search tree: only search the n most promising moves (determained by heuristic function) but search those until the end.
43
Q

What is a search horizon?

A

It’s the level of a game tree until which the search is run.

44
Q

Under the zero-sum assumption, which of the following evaluation functions and their statements are correct?

  1. f(n) = 0
    means the current game state is neutral.
  2. f(n) &laquo_space;0
    means the current game state is good for me and bad for you.
  3. f(n) = +infinity
    menas the current game state is a win for me.
A
  1. is correct.
  2. is incorrect. A result smaller zero is bad for me and good for you.
  3. is correct.
45
Q

What is an Heuristic Evaluation Function?

A

The idea of it is to produce an estiamte of the expected utility of the game, given a specific position.

46
Q

What are the requirements of an Heuristic Evaluation Function?

A
  1. the evaluation function should order terminal nodes in the same way as the (unknown) true function.
  2. computation should not take too long.
  3. for non-terminal states the evaluation function should be strongly correlated with the actual chance of winning.
47
Q

What are Linear Evaluation Functions, and what are its advantages and disadvantages?

A

They are combinations of features. A feature encodes a certain characteristic of a position and is weighted according to its importance.

+ conceptually simple
+ typically fast to compute

  • tuning of the weights may be very hard
  • adding up the weighted features makes the assumption that each feature is independent of the other features
  • evaluation functions are typically very brittle (it’s hard to write a function that works for every situation)
48
Q

In chess, what are quiescent states?

A

they’re also called quiet positions and they’re positions where captures or checks are not possible.

49
Q

What is Quiescence Search?

A

When the search depth is reached the algorithm computes the quiescence state evaluation heuristic.
If the state is quiescent it proceeds as usual. Otherwise it increases the search depth.

50
Q

What is the Horizon Effect?

A

It’s a problem that can occur with fixed-depth searches.
If we only search n moves ahead it may be possible that the best moves won’t be found. Or that a strategy with n+1 moves won’t be found and thus not considered.

51
Q

What are Search Extensions?

A

The basic idea is to extend the search when a forced move is found that limits the possible replies to few possible actions.

Then programs extend the search depth by skipping the step that increments the current search depth. Search then continues as usual until the horizon is reached.

This has to be designed carefully so that the search will terminate within a reasonable time.

52
Q

True or False: The further down the game tree is searched the more gain it results in.

A

False. The Gain of deeper searches goes down with the depth.

53
Q

What are Transposition Tables?

A

It’s a way to increase efficiency. Hash tables store already found positions. If a position occurs a second time the value of the node doesn’t have to recomputed.

54
Q

What are Zobrist Hash Keys?

A

They’re what is stored in Transposition Tables: generated 3d-array of 64-bit numbers describing the type of (chess) piece, location and color.

55
Q

What is Chinook?

A

First computer to win human world championship in Checkers.

56
Q

What is AlphaGo?

A

First win of a computer against a professional GO player (2015).

57
Q

What is AlphaZero?

A

Improved version of AlphaGo. Can play GO, chess and Shogi (Japanese Chess).
In 2017 it beats the strongest programs in all three games after only hours or days (GO) of training.

58
Q

How can the Horizon Effect be countered?

A

with Search Extensions

JKU: "Introduction to AI" by Johannes Fürnkranz (2024W) (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions