Week 2 Search in Games

Question 1

what is the search space size

Answer 1

still dont get this work it this out

Question 2

what is a tree search ?

Answer 2

is a category of search
methods that uses a tree structure to
navigate through possible solutions. In Tree
Search, the root of the tree represents the
state where the search starts. Each edge
from this state is an decision (or, in a
game, an action an agent takes) that leads
to another state in the search space.

Question 3

what is uninformed search or blind search

Answer 3

the algorithm performs the search without any information about the goal, e.g brute force algorithms.

Question 4

what is BFS and what does iit do

Answer 4

Breadth-first search (BFS) it completes one level at a time

• Advantage: Very simple to implement.
• Disadvantage: Heavy memory requirements

Question 5

what is DFS and what does iti do

Answer 5

depth-frist-seach , runs down each branch of the tree till terminal state (wiitch can be gaol or not )

Advantage: Not heavy memory requirements.
• Disadvantage: Non complete, can enter infinite loops

Question 6

what is best first search

Answer 6

it is a search function it use’s knowledge about the goal to conduct search, thiis is implemented in the form of an heuristic

Question 7

ex of best first search

Answer 7

A* is used for pathfinding(good youtube video on this ) is based off something else Dijkstra(polynomial runtime).

Question 8

what is A*?

Answer 8

it is a best-first search aglo for find the shortest distances from A to B, but iit cant work with the geometry that makes up the game level so that we have to construct a graph that we search

Question 9

how do we talk about the graph in A*

Answer 9

we talk about the pathfinding in terms of nodes,

Question 10

talk about nodes in pathfinding ?

Answer 10

nodes repersent pints in 2d or 3d space

2. nodes have neighbours (adjacent nodes)
3. neighbouring nodes may have different (positvie) diistances/costs
4. • Nodes (i.e., their locations) can be constructed manually or automatically

Question 11

Dijkstra ?

Answer 11

Diijkstra’s algorithm is a classical pathfinding algo (efficient with polynomial runtime ) it finds the shortest discations between two poiint it is a variation of breadth first search

iits is a priiority queue

Question 12

how is A* different from Dijkstra ?

Answer 12

a* USES A HEURIISTIC, to estitmate the utility of a node with repect to the target this

Question 13

what does the heuristic have to be about to do

Answer 13

admissible:An admissible heuristic never

over-estimates the distance from A to B

Question 14

what are the different types of heiristic?

Answer 14

if h = 0 (no heuristic ) then A* works just like Dijsktra
manhattan distances
euclidean distances
chebyshev distances

Question 15

• Rectangular grid, 4-way connectivity: which are admissible?

Answer 15

if you look at the manhattan witch is linear moves, that will always be the correct disctances the euclidean distances will understerment the distances,

(i think both of them are admissible )

Question 16

• Rectangular grid, 4-way connectivity: which are admissible?
• Rectangular grid, 8-way connectivity: which are admissible?

Answer 16

if you look at the manhattan witch is linear moves, that will always be the correct disctances the euclidean distances will understerment the distances,

(i think both of them are admissible )

• Rectangular grid, 4-way: Euclidean, Manhattan or Chebyshev.
• Rectangular grid, 8-way: Euclidean or Chebyshev (Diagonal).
• In some cases we can also use a pre-computed exact heuristic.

Question 17

Some Facts about A*

Answer 17

• If h(n) is 0, only g(n) matters, and A* equals Dijkstra’s algorithm.
• If h(n) is never more than the actual distance, then A* is guaranteed to
find a shortest path. The lower h(n), the more node A* expands.
• If h(n) is exactly equal to the actual distances, then A* will only follow the
best path and never expand anything else.
• If h(n) is sometimes greater than the cost of moving from n to the goal,
then A* is not guaranteed to find a shortest path.
• If h(n) is very high relative to g(n), then only h(n) plays a role, and A*
turns into Best-First-Search.

Question 18

what else can A* be used for

Answer 18

A* it can be used to search in the game tree, this is A* can be used for planning,

Question 19

What is MCTS

Answer 19

monte Carlo Tree Search

Question 20

what is a MCTS in trems of what does it do

Answer 20

is a highly selective best first search, MCTS builds an asymmetric tree search exploring the most promising
part of the search space.

Question 21

, if the game tree is large, how does it manage to search efficiently?

Answer 21

it sampling randomly actions from states iit requires a forward model (FM)

Question 22

What is a Forward or Predictive model

Answer 22

is an internal simulator of the game that the agent has access to , the agent uses this to simulate the effect of applying certain actions on a given state.

Question 23

what is the notetastion for this

Answer 23

current state St and an Action At applied too St, the forward model will provide the next state St+1

Question 24

what are the 4 steps in MCTS ?

Answer 24

1. Selection
2. Expansion
3. Play-out
4. Back propagation

SEPB

Question 25

Evolutionary Computation apply what type of ideas from natural selection (applying genetic operators)

Answer 25

reproduction, mutation, recombination, and selection

Question 26

talk about evolutionary algorithms,

Answer 26

an EA iis an optimization alogo that consider complete solutions to a problem, therefor requires an objective function(evaluation or fitness function)this funntion can be max or minimized [. An optimization algorithm can be seen as a process that searches in the space of solutions those with the highest (or lowest) value of that utility]

Question 27

what is the simplest optimisation Algo

Answer 27

hill climber

Question 28

what is the hill cliimber algo

Answer 28

need to look at this !!

Question 29

what is stochastic hill climber??

Answer 29

its is a better vesion of the hill climber, Stochastic hill climbing chooses at random from among the uphill moves; the probability of selection can vary with the steepness of the uphill move. This usually converges more slowly than steepest ascent, but in some state landscapes, it finds better solutions. First-choice hill climbing implements stochastic hill climbing by generating successors randomly until one is generated that is better than the current state. This is a good strategy when a state has many (e.g., thousands) of successors.

Question 30

what are the problems with SHC

Answer 30

can get stuch in local min

Question 31

what is a typical EA ?

Answer 31

1. Initialize the population of N individuals, t = 0. 2. For each generation t, until convergence or max T: 2.1 Evaluate the population Pt (i.e. evaluate all its individuals) 2.2 Promote the best E individual(s) from Pt to the next generation’s population (Pt+1). 2.3 For each N − E position in Pt+1: 2.3.1 Select two parents from population Pt. 2.3.2 Create new individual from them by crossover. 2.3.3 Mutate individual. 2.3.4 Insert individual in the next generation Pt+1 2.4 Advance to the next generation’s population (Pt → Pt+1).