In the 3 white and 3 black tiles problem, there are 7 tiles, 3 are white and 3 are black and there is a white space in the middle. All the black tiles are placed left and all the white tiles are placed right. Each of the white or black tiles can move to the blank space and they can hope over one or two tiles to reach the blank space.
- Analyze the state-space of the problem.
- Propose a heuristic for this problem to move all the white tiles left to all the while tiles, the position of the blank space is not important.
Initial State
POS: | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
TILES: | B | B | B | W | W | W |
Goal State
POS: | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
TILES: | W | W | W | B | B | B |
AI Assumptions
- Heuristics for Black Tile = tile-distance to the first white tile to its right
- Heuristics for White Tile = tile-distance to the first black tile to its left * -1
- We will run the script as long as we will have a non zero value for a tile.
- If any black tile does not contain any white tile to its left then that tile will have Zero Heuristics
- If any white tile does not contain any black tile to its right then that tile will have Zero Heuristics
- We will have a selector value initially set as White.
- For each iteration, we will change the value to black and white and so no.
- Depending on the selector we will choose that colored tile with the highest tile says, Tile X.
- X will be moved to the blank space.
- If the tile jumps to its next tile the cost:= 1 if hop one tile then cost:= 2 if jumps 2 tiles then cost:= 3.
3 white and 3 black tiles problem Algorithm
Selector:= white Foreach black tile b do h(b):= tile-distance to the first white tile to its right Foreach white tile w do h(w):= tile-distance to the first black tile to its left * -1 While any tile has a non-zero h value Do If selector:= white then, Select the while-tile with the highest h value, say X If the h(X):= 0 and it does not have the blank space to its left then, Select another while-tile with the next-highest h value, say X Selector := black Else Select the black-tile with the highest h value, say X If the h(X):= 0 and it does not have the blank space to its left then, Select another black-tile with the next-highest h value, say X Selector:= white If X and the blank space is in 2-tiles distance then, Move X to the blank space and record the cost Foreach black tile b do h(b):= tile-distance to the first white tile to its right Foreach white tile w do h(w):= tile-distance to the first black tile to its left * -1 End while
Steps:
Step 1: Selector: Null – INITIAL STATE
Value: | 4 | 3 | 2 | -2 | -3 | -4 | |
TILES: | B | B | B | W | W | W |
cost = 0
Step 2: Selector: W
POS: | 3 | 2 | 1 | -1 | -3 | -4 | |
TILES: | B | B | B | W | W | W |
cost = 1
Step 3: Selector: B
POS: | 3 | 1 | -1 | 1 | -1 | -2 | |
TILES: | B | B | W | B | W | W |
cost = 3
Step 4: Selector: W
POS: | 1 | -1 | 3 | 1 | -1 | -2 | |
TILES: | B | W | B | B | W | W |
cost = 2
Step 5: Selector: B
POS: | 1 | -1 | 2 | 1 | -1 | -2 | |
TILES: | B | W | B | B | W | W |
cost = 1
Step 6: Selector: W
POS: | 1 | -1 | -2 | 3 | 2 | -2 | |
TILES: | B | W | W | B | B | W |
cost = 3
Step 7: Selector: B
POS: | 1 | -1 | -2 | 2 | 1 | -1 | |
TILES: | B | W | W | B | B | W |
cost = 2
Step 8: Selector: W
POS: | 1 | -1 | -2 | -1 | 2 | 1 | |
TILES: | B | W | W | W | B | B |
cost = 3
Step 9: Selector: B
POS: | 1 | -1 | -2 | -3 | 0 | 0 | |
TILES: | B | W | W | W | B | B |
cost = 2
Step 10: Selector: W
POS: | 2 | -2 | -3 | -4 | 0 | 0 | |
TILES: | B | W | W | W | B | B |
cost = 3
Step 11: Selector: B
POS: | 1 | -1 | -2 | -3 | 0 | 0 | |
TILES: | B | W | W | W | B | B |
cost = 1
Step 12: Selector: W
POS: | 0 | 2 | -2 | -3 | 0 | 0 | |
TILES: | W | B | W | W | B | B |
cost = 2
Step 13: Selector: B
POS: | 0 | 1 | -1 | -2 | 0 | 0 | |
TILES: | W | B | W | W | B | B |
cost = 1
Step 14: Selector: W
POS: | 0 | 0 | 1 | -2 | 0 | 0 | |
TILES: | W | W | B | W | B | B |
cost = 2
Step 15: Selector: B
POS: | 0 | 0 | 1 | -1 | 0 | 0 | |
TILES: | W | W | B | W | B | B |
cost = 1
Step 16: Selector: W
POS: | 0 | 0 | 0 | 1 | 0 | 0 | |
TILES: | W | W | W | B | B | B |
cost = 2