2022-09-20
Sep 21 In-Class Exercise.
Please post your solutions to the Sep 21 In-Class Exercise to this thread.
Best,
Chris
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:
(Edited: 2022-09-21) Current node: 9 End loop
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
4. 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(Edited: 2022-09-21)
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
4. 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
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
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>
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
- 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
(Edited: 2022-09-21) Pass the goal test.
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.
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
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(Edited: 2022-09-21)
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
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
(c) 2025 Yioop - PHP Search Engine