Please post your solutions to the Sep 21 In-Class Exercise to this thread.

Best,

Chris

In my algorithm, I will associate each square with a probability that can be found using this formula: neighbor_square.value /highest value among the squares. Looking at all the calculated probabilities, take the highest one and move our agent to the square associated with that highest probability.

Stochastic-Hill-Climb(INITIAL-STATE): Find the highest value in the grid Loop do: If current square (node) is the goal: end loop From initial square, find all neighbors of current square Calculate probabilities associated with each neighbor (neighbor.square/highest value) Pick the highest probability Move to the next square (node) with that probability

HIGHEST_VALUE = 9

Loop 0: Current node: 1 Neighbors are 2, 4 and 5 Probabilities = {0.22: 2, 0.44: 4, 0.56: 5} Next node = 5

Loop 1: Current node: 5 Neighbors are 1,2,3, 4, 6,7,8,9 Probabilities = {0.11: 1, 0.22: 2, 0.33: 3, 0.44: 4, 0.67: 6, 0.78: 7, 0.89: 8, 1: 9} Next node: 9

Loop 2: Current node: 9 End loop

1. start at initial location
2. look at neighbours (left, right, up, down)
3. calculate probabilities

• sum (S) up the neighbouring location values (V)
• assign probabilities using V/S in discovery order

- so if we always discover squares in left, right, 
    up, down order and say the probabilities are 10, 40, 
     30, 20, then numbers 1-10 are for left, 11-50 are for 
     right, 51-80 are for up, 81-100 are for down

1. move to next location

• use a random number generator to find which location to move to
• say for example we get 55 as our random number
• based on this we would move UP

simulation

9 8 7 6 5 4 3 2 1@

turn 1:

step 1: initial location is not the max step 2: neighbours = up, left

step 3: sum = 6 probability assignment based on discovery order so 2/6 = 0.33 = 33 -> 1-33 mapped to left 4/6 = 0.667 = 67 -> 34-100 mapped to up

step 4: get a random number (google) = 45 move up new current location = 4

turn 2:

step 1: current location 4 is not the max step 2: neighbours = left, up, down

step 3: sum = 13 probability assingment: left = 5/13 = 0.38 -> 1-38 mapped to left up = 7/13 = 0.54 -> 39-92 mapped to up down = 1/13 = 0.08 -> 93-100 mapped to down

step 4: random number (google) = 70 move up new current location = 7

continue until you reach 9

<nowiki> function hill_climbing(problem): uphill_neigbors = each neigbor of current square where neigbor.utility - current.utility > 0 if no uphill_neighbors, return current square pick random square from list [[square]*square.utility for square in uphill_neighbors] move to the randomly selected square </nowiki>

<nowiki> First iteration: Uphill neighbors = tiles with 2, 4, 5 uphill neighbors is not empty so continue pick random square from [2, 2, 4, 4, 4, 4, 5, 5, 5, 5, 5] square with 5 was chosen, becomes current square

Second iteration uphill neighbors: squares with6, 7, 8, 9 uphill neighbors is not empty so continue pick random square from [6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9] square with 9 was chosen, becomes current square

Third iteration: uphill neighbors: empty uphill neighbors is empty, return current square (square with 9) </nowiki>

• Sum the utility of local adjacent nodes
• while summing each node, check for local maximum state
  • if local maximum return current state
• assign different ranges between zero and Sum to each node with the size of the range proportional to the utility of the local node ex: N1:2 N2:5 N3:4 -> sum = 11 N1 range[0,2], N2 range(2,7], N3 range(7,11]
• generate a random number between zero and sum
• move to the node with the range including the randomly generated number
• repeat until return for local maximum

Simulation to be continued

First only continue if the utility is greater than current utility. Then do the goal test. Then calculate probability by utility / sum of all possible utility.

Step 0: 2 / 6 4 / 6

Step 1: Move -> 4 (by random function) 5 / 12 7 / 12

Step 2: Move -> 5 (by random function) 6 / 14 8 / 14

Step 3: Move -> 8 (by random function) 9 / 9 = 1

Step 4: Move -> 9 Pass the goal test.

I would set up my algorithm to look at the potential neighbors we could move to. I would add the value of the neighbor to the manhattan distance to the goal state. I would divide each value by 9 then select the highest probability of the neighbors. If the values are the same select the neighbor with the lowest manhattan cost to distance. The first move would evaluate 2,4,5=> probabilities 5/9, 7/9, 7,9 neighbor 5 is selected since its manhattan distance to the goal state is the smallest. next the algorithm evaluates neighbors 1,2,3,4,6,7,8,9 => probabilities 5/9, 5/9, 5/9, 7/9, 7,9, 9/9, 9/9 since 9 is the goal state its manhattan distance is 0 so we select the square with 9 to move to and we have reached our goal.

Algorithm: Look at the number of choices and give every move a base value. Ex. 2 possible space --> 50% base; 3 possible --> 33% base, 4 possible --> 25% base. Then look at all the spaces to find the largest and smallest number. The space with the smallest number has its chance halved, with the difference being added to the space with the largest number. Nothing occurs to the other spaces. Running the algorithm by hand: Start at 1: Neighbors --> 2, 4 Chance for 2 --> 50% / 2 = 25% Chance for 4 --> 50% + 25% = 75% Dice Roll: 0.48 --> Move to 4 Start at 4: Neighbors --> 1, 5, 7 Chance for 1 --> 33% / 2 = 16% Chance for 5 --> 33% Chance for 7 --> 33% + 16% = 49% Dice Roll: 0.11 --> Move to 1 Start at 1: Neighbors --> 2, 4 Chance for 2 --> 50% / 2 = 25% Chance for 4 --> 50% + 25% = 75% Dice Roll: 0.60 --> Move to 4 Start at 4: Neighbors --> 1, 5, 7 Chance for 1 --> 33% / 2 = 16% Chance for 5 --> 33% Chance for 7 --> 33% + 16% = 49% Dice Roll: 0.64 --> Move to 7

Start at 7: Neighbors --> 4, 8 Chance for 4 --> 50% / 2 = 25% Chance for 8 --> 50% + 25% = 75% Dice Roll: 0.45 --> Move to 8

Start at 8: Neighbors --> 5, 7, 9 Chance for 5 --> 33% / 2 = 16% Chance for 7 --> 33% Chance for 9 --> 33% + 16% = 49% Dice Roll: 0.60 --> Move to 9

Done

One thing to do is we can have the agent choose from the nodes in an upward or sideways direction(left or right depending on which direction is closer to the goal node). Then the agent would choose the maximum value within this group of nodes. Simple equation: f = n1 - n where n1 is a child or potential move and n is value of current node.

step 1: curVal = 0 Choices = [1] Choose 1 step 2: curVal = 1 Choices = [2, 4, 5] Choose 5 (5 - 1 = 4) step 3: curVal = 5 Choices = [6, 8, 9] Choose 9 (9 - 5 = 4) Done

Probability for each square will be be ((neighbor.value-current.value)^2/Sum of all the values) The probability that is the highest is where our agent will go.

We go to 1 because (1-0)^2/45 = 1/45 The adjacent nodes are 2 and 4 Probability of 2 is (2-1)^2/45 = 1/45 Probability of 4 is (4-1)^2/45 = 4/45 So we go to 4 1->4

Adjacent nodes are 5 and 7 Prob of 5 is 1/45 Prob of 7 is 9/45 We go to 7