Module 4

Question 1

What is a local search and it’s pros and cons

Answer 1

Operates by searching from start state to neighbouring states

Pros

• Uses less memory
• Can find reasonable solutions in large / infinite state spaces

Cons

• does not keep track of paths or set of reached states
• not systematic, may never explore a portion where solution exists

Question 2

Can local search solve optimization problem

Answer 2

Yes, where objective function is utilized

Question 3

What is hill climbing

Answer 3

When aim is to find highest peak/ global maximum

Question 4

What is gradient descent

Answer 4

When aim is to find lowest valley / global minimum

Question 5

Describe the hill climbing algorithm idea

Answer 5

• Start wherever
• move to neighbouring state
• if no neighbour better than current state then quit
• does not look beyond direct neighbours of current state

Question 6

Local search complexities

Answer 6

State space - set of complete configurations

Question 7

What is local maxima, ridge, shoulder and plateau

Answer 7

Local maxima - higher than neighbourhood , lower than global maxima

Ridge - sequence of local max , /\/\

Shoulder - flat neighbour’s then ascends

Plateau - No uphill or shoulder , flat

Question 8

How to increase hill climbing efficiency

Answer 8

Increase sideways moves

Question 9

What are sideways moves

Answer 9

When reaching plateau, restart search from another point. Moves can be limited but is also more expensive

Question 10

Variations of hill climbing

Answer 10

Stochastic - chose randomly among uphill neighbours

First-choice - generate random successors until one is better

Random restart - conducts a series of hill climbing searches

Evolutionary - stores potential solutions and performs random mutations. Keeps mutations that are better states ( ancestor of GA )

Question 11

What is simulated annealing

Answer 11

Minimizing algorithm Variation that Allows for bad moves according to temperature. Combines random walk with hill climbing

Question 12

When are bad/good moves allowed in simulated annealing

Answer 12

High temp - more bad moves

Question 13

How does simulated annealing expand

Answer 13

Change in energy
E > 0 - move to neighbour
E < 0 - move to neighbour with probability e ^ (-DE/T)

Question 14

What is local beam search

Answer 14

K copies of local search are initialized

Question 15

What does each iteration of local beam search do

Answer 15

Generates all successors from k current states and chooses the best k to be current state - searches communicate with each other - evolution hc

Question 16

What is Genetic algorithm

Answer 16

Directed search algorithm based on biological evolution

Question 17

What are the components of GA

Answer 17

• Encoding technique ( Gene / chromosome)
• Initialization procedure ( creation )
• Evaluation function ( environment )
• Selection of parents ( reproduction )
• Genetic operator ( mutation )
• Parameter settings ( practice )

Question 18

Flow chart of GA

Answer 18

Population initialization -> fitness function -> crossover -> Mutation -> Survivor selection -> terminate + return best

Loops fitness - survivor until termination condition reached

Question 19

What is a fitness calculation

Answer 19

Compromises of fitness function which takes solution candidate and measures the solution using fitness score

Question 20

What is a selection process

Answer 20

Selects individuals to be parents

Select individuals with probably proptional to fitness score or randomly where (n>p) and select p most fit parents

Question 21

What is GA crossover

Answer 21

Recombination procedure , combines different parts of parents to create offspring

• one with 1P1 and 2P2
• one with 2P1 and 1P2

Question 22

What is mutation rate

Answer 22

How often offspring have random mutations

Every bit in offspring composition is flipped with probability = mutation rate

Question 23

What is elitism

Answer 23

Make up of next generation

• could be offspring or elite parents
• guarantees overall fitness never decreases

Question 24

What is culling

Answer 24

Removing parents below certain thresholds

Question 25

What is a solution and evaluation function for games

Answer 25

Solution is strategy - evaluation function is evaluation goodness of game position.

Question 26

What are the environment type for games

Answer 26

Fully observable , Multi agent , sequential, discrete

Question 27

What is a game

Answer 27

Task env with more than 1 agent

Question 28

List game axes

Answer 28

``` Determ or stochastic Fully observable Players Teams/indiv Turns/simul Zero sum ```

Question 29

Which plan do algorithms help with in game search trees

Answer 29

Contingent plan / strategy

Question 30

List different types of games

Answer 30

Standard, zero sum, general sum , team

Question 31

List env types of standard games

Answer 31

Observable, deterministic, two player, turn taking, zero sum

Question 32

List formulation of standard game

Answer 32

``` Initial state Players Actions Transition model -Results(s,a) Terminal test , true when game over Terminal value, utility for player ```

Question 33

What is the search objective of standard games

Answer 33

Find sequence of players decisions maximizing utility / pay off Also considers opponent moves/utility

Question 34

List basic idea of zero sum games

Answer 34

Agents have opposite utilities , pure competition, one maximizes other minimizes

Question 35

List basic idea of general sum games

Answer 35

Agents have independent utilities. Here cooperation, indifference, competition, shifting alliance is possible.

Question 36

List basic idea of team games

Answer 36

Common pay off for players in a team

Question 37

Key feature of zero sum

Answer 37

Gain or loss is exactly balanced through opponents. Adds to 0

Question 38

How does minmax algorithm traverse and what does it assume

Answer 38

Back tracking algorithm with recursion using dfs | Assumes opponent will be rational and optimize, and all future moves are optimal

Question 39

What if minmax doesn’t not play optimally

Answer 39

Opponent benefits further

Question 40

What is minmax efficiency

Answer 40

``` Search O(b^m) Space O(bm) ```

Question 41

What if more than one player / zero sum

Answer 41

Terminal nodes are tuples associated with tuple node. Each player maximizes their tuple.

Question 42

What is alpha beta

Answer 42

Modified version of mini max , cuts depth to half. Utilizes alpha beta as thresholds.

Question 43

Initial value of beta

Answer 43

Positive infinity , min changes

Question 44

Initial value of alpha

Answer 44

Negative infinity, max can change