AI_2013_Repeat.md

Artificial Intelligence: 2013 Repeat

Multiple Choice

1.  5
2.  6
3.  3
4.  Didn't do
5.  Didn't do
6.  1
7.  1
8.  3
9.  2
10. 2

Long Questions

Question 1

Part A

Part B

9 initial moves, 8 replies... Total = 9! = 362,880

Part C

No the number of paths is not the same as the number of states because you can get to the same state from multiple paths.

Part D

• The number of x's - number of o's can't have an elevation greater than 1
• Both players can't win

Part E

i) No this can't exist.

ii) Yes this can exist, O went first, O wins.

iii) Yes this can exist, X went first, O wins.

Part F

Yes X's and O's could be solved by exhaustive search.

Part G

Using a symetrically reducing algorithim x's and o's could be simplified greatly since a huge amount of states are syetrical to eachother when rotated.

Question 2

Part A

An evaluation function might be used in search to tell how close to the desired goal the current state is, bassically a huristic can be used to rate a particular state.

Part B

• Heuristic evaluation functions that are too simple don't give reliable answers taking a path based on this heuristic could fail immediatly.
• Heuristic evaluation functions that are too complicated take to long to evaluate for each state and time issues are ran into.

Part C

When designing heuristics we can keep in mind number of winning formations that include one of my pieces, we can immediatly strop transversal of sub trees that include a move that a win isn't possible from this could reduce the search space greatly.

Part D

If we always pick the best next state first it's called a best first search, yes best first can get stuck in loops where the next state is the same as current, when we move onto the next state we're back in the same situation.

Part E

In a game like N-Puzzle it may be necessary to go to a state thats preceived as worse by the heuristic in order to get to a better state in the next move.

Part F

Hill climbing works differently to best first, best first only searches one ply deep it evaluates all states and goes to the best, hill climbing get dropped in an environment randomely and try and find the optima by grouping near promising areas

Question 3

Part A

Genetic Algorithim is evolution as an algorithim, start off with a number of creatures each with relatively random DNA, allow fittest to reproduce using mutation and crossover.

Part B

Core Genetic Algorithim:

1. Start of with a relatively random selection of creatures
2. Loop indefinitely:
	1. Allow creatures to try and solve some problem
	2. Rate creatures fitness
	3. Allow fittest to reproduce using combination (mutation, crossover)
	4. Delete old population

Necessary for genetic algorithim:

• Mutation rate
• Crossover rate
• Population size
• Population of creatures with varied DNA

Part C

It has no idea what the global maximum looks like. It could possibly find it over an infinte period of time but even then it can't be sure.

Part D

If variable population size is allowed it's possible that the population will grow too large, exceeding expected size (explode) or they could go entirely extinct.

Part E

• If p(m) = 1 Then every bit would flip upon being inherited from the parent, this would leave us with a very limited search space, repeat itself over and over.
• If p(m) = 0 Then no mutation would occur at all, this is bad because crossover isn't guaranteed to be able to produce all possible secuences of bits it depends entirely upon the original population.

Part F

• If p(c) = 1 Then crossover will occur every time. This is good because the child is going to have a mix of attributes from it's fit parents.
• If p(c) = 0 Then crossover will never occur, this is bad because if mutation is the only thing deciding the next generation then good attributes of parents could be discarded.

Bonus Question

;)