Run value iteration for a fixed number of steps and read off the policy.
What to build
A program that runs k iterations of value iteration in a deterministic grid world and prints the values and the greedy policy.
Requirements
- Cells:
.open,#wall,Ggoal andPpit (both terminal, value 0). Moves N, E, S, W go one cell; into a wall or off the grid, the agent stays. The reward is +10 for entering G, −10 for entering P and −1 otherwise. All open cells start at 0; each iteration updates every open cell from the previous values. - Print
values:and the grid of values (two decimal places;#,G,Pas themselves), thenpolicy:and the grid of best actions for the final values as^ > v <(ties: N, E, S, W order).
Input
Line 1: rows, columns, γ and k. Then the grid.
Output
values:, the rows, policy:, the rows.
Constraints
At most 10 × 10 cells; k ≤ 100.
Example
Input:
1 4 1 3
...G
Output:
values:
8.00 9.00 10.00 G
policy:
> > > G
Why it works
After k iterations each value is the best total reward reachable in k moves, so values spread outward from the goal one cell per iteration.
Examples
1 4 1 3 ...G
values: 8.00 9.00 10.00 G policy: > > > G
1 4 0.5 2 ...G
values: -1.50 4.00 10.00 G policy: > > > G
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Each iteration computes new values for every open cell from the old values: the best over N, E, S, W of reward + γ × V(next).
Hint 2
Entering G earns +10, entering P earns −10, any other move earns −1; G and P always have value 0.
Solution
Show one correct solution (try it yourself first)
rows, cols, gamma, k = input().split()
rows, cols, gamma, k = int(rows), int(cols), float(gamma), int(k)
grid = [input() for _ in range(rows)]
MOVES = [("^", -1, 0), (">", 0, 1), ("v", 1, 0), ("<", 0, -1)]
V = {(r, c): 0.0 for r in range(rows) for c in range(cols) if grid[r][c] != "#"}
def outcome(r, c, dr, dc):
nr, nc = r + dr, c + dc
if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] == "#":
nr, nc = r, c
reward = {"G": 10, "P": -10}.get(grid[nr][nc], -1)
return reward, (nr, nc)
def q(values, r, c, dr, dc):
reward, nxt = outcome(r, c, dr, dc)
return reward + gamma * values[nxt]
for _ in range(k):
V = {cell: (max(q(V, *cell, dr, dc) for _, dr, dc in MOVES) if grid[cell[0]][cell[1]] == "." else 0.0) for cell in V}
print("values:")
for r in range(rows):
print(" ".join(f"{V[(r, c)]:.2f}" if grid[r][c] == "." else grid[r][c] for c in range(cols)))
print("policy:")
for r in range(rows):
line = []
for c in range(cols):
if grid[r][c] != ".":
line.append(grid[r][c])
continue
best = None
for name, dr, dc in MOVES:
value = q(V, r, c, dr, dc)
if best is None or value > best[1]:
best = (name, value)
line.append(best[0])
print(" ".join(line))