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 > Flashcards

Game Playing 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

18
Q

What are examples of games of chance with perfect information?

A

Backgammon, Monopoly

19
Q

What are examples of games of chance with imperfect information?

A

Bridge, Poker, Scrabble

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

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.
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
A

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

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