Solution and implementation for Q6 from Machine Learning (ml).
# Reinforcement Learning
# Maze Environment
import numpy as np
import random
# Create a 4x4 maze
maze = np.array([
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
[0, 1, 0, 0]
])
# 0 = Free path
# 1 = Wall
rows, cols = maze.shape
# Start and goal positions
start = (0, 0)
goal = (3, 3)
# Actions: Up, Down, Left, Right
actions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Q-table
q_table = np.zeros((rows, cols, 4))
# Learning parameters
learning_rate = 0.8
discount = 0.9
epsilon = 0.2
# Training
for episode in range(1000):
state = start
for step in range(100):
# Choose action
if random.random() < epsilon:
action = random.randint(0, 3)
else:
action = np.argmax(q_table[state[0], state[1]])
# Calculate new position
new_row = state[0] + actions[action][0]
new_col = state[1] + actions[action][1]
# Check whether move is valid
if (new_row < 0 or new_row >= rows or
new_col < 0 or new_col >= cols or
maze[new_row, new_col] == 1):
reward = -10
next_state = state
else:
next_state = (new_row, new_col)
if next_state == goal:
reward = 100
else:
reward = -1
# Update Q-value
old_value = q_table[state[0], state[1], action]
next_max = np.max(
q_table[next_state[0], next_state[1]]
)
new_value = old_value + learning_rate * (
reward + discount * next_max - old_value
)
q_table[state[0], state[1], action] = new_value
state = next_state
# Stop if goal is reached
if state == goal:
break
# Display learned Q-table
print("Training completed!")
print("\nQ-Table:")
print(q_table)
# Test the learned path
state = start
path = [state]
for step in range(20):
action = np.argmax(
q_table[state[0], state[1]]
)
new_row = state[0] + actions[action][0]
new_col = state[1] + actions[action][1]
if (new_row < 0 or new_row >= rows or
new_col < 0 or new_col >= cols or
maze[new_row, new_col] == 1):
break
state = (new_row, new_col)
path.append(state)
if state == goal:
break
print("\nLearned Path:")
print(path)
# Q6B: Q-learning Taxi problem on a simple 5x5 grid. import numpy as np import matplotlib.pyplot as plt
# The agent must pick up at (0, 0) and drop off at (4, 4).
# State: taxi row, taxi column, passenger on board (0/1).
pickup, destination = (0, 0), (4, 4)
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
action_names = ["up", "down", "left", "right", "pick up", "drop off"]
def step(state, action):
row, col, onboard = state
reward, done = -1, False
if action < 4:
dr, dc = moves[action]
row = int(np.clip(row + dr, 0, 4))
col = int(np.clip(col + dc, 0, 4))
elif action == 4:
if (row, col) == pickup and onboard == 0:
onboard, reward = 1, 5
else:
reward = -10
elif action == 5:
if (row, col) == destination and onboard == 1:
reward, done = 20, True
else:
reward = -10
return (row, col, onboard), reward, done
# Train from random taxi positions, with an empty taxi each episode.
rng = np.random.default_rng(42)
q = np.zeros((5, 5, 2, 6))
alpha, gamma = 0.2, 0.95
successes = []
for episode in range(8000):
state = (int(rng.integers(5)), int(rng.integers(5)), 0)
epsilon = max(0.05, 1 - episode / 6000)
done = False
for _ in range(100):
action = int(rng.integers(6)) if rng.random() < epsilon else int(np.argmax(q[state]))
next_state, reward, done = step(state, action)
target = reward if done else reward + gamma * np.max(q[next_state])
q[state][action] += alpha * (target - q[state][action])
state = next_state
if done:
break
successes.append(done)
print("Completion rate in final 100 episodes:", round(np.mean(successes[-100:]), 3))
# Test one trip: start at (4, 0), collect the passenger, then drop off.
state = (4, 0, 0)
trip = [state]
for _ in range(50):
action = int(np.argmax(q[state]))
next_state, reward, done = step(state, action)
print(state, "->", action_names[action], "->", next_state, "reward:", reward)
state = next_state
trip.append(state)
if done:
break
print("Passenger delivered:", done)
assert done, "Increase the training episodes if the policy has not converged."
coordinates = np.array([(row, col) for row, col, _ in trip])
plt.plot(coordinates[:, 1], coordinates[:, 0], marker="o")
plt.scatter([pickup[1], destination[1]], [pickup[0], destination[0]],
c=["green", "red"], s=100, label="Pickup / destination")
plt.xlim(-0.5, 4.5); plt.ylim(4.5, -0.5)
plt.xticks(range(5)); plt.yticks(range(5))
plt.title("Learned taxi route")
plt.grid(); plt.show()
# Q6C(a-b): Set up the Tic-Tac-Toe environment and game rules.
from collections import defaultdict
import numpy as np
WIN_LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),
(0, 3, 6), (1, 4, 7), (2, 5, 8),
(0, 4, 8), (2, 4, 6)]
def winner(board):
for a, b, c in WIN_LINES:
if board[a] != 0 and board[a] == board[b] == board[c]:
return board[a]
return 0
def available(board):
return [i for i, value in enumerate(board) if value == 0]
def show(board):
symbols = {1: "X", -1: "O", 0: "."}
print("\n".join(" ".join(symbols[v] for v in board[i:i + 3])
for i in (0, 3, 6)))
# Q6C(c): Q-learning agent X plays against a random opponent O.
# The state is the board immediately before X's turn.
q = defaultdict(lambda: np.zeros(9))
rng = np.random.default_rng(42)
alpha, gamma = 0.25, 0.95
def choose_action(board, epsilon):
legal = available(board)
if rng.random() < epsilon:
return int(rng.choice(legal))
values = q[tuple(board)][legal]
best = [a for a, value in zip(legal, values) if value == max(values)]
return int(rng.choice(best))
def play_episode(epsilon, learn=True):
board = [0] * 9
while True:
state = tuple(board)
action = choose_action(board, epsilon)
board[action] = 1
if winner(board) == 1:
reward, result = 1.0, "win"
break
if not available(board):
reward, result = 0.2, "draw"
break
board[int(rng.choice(available(board)))] = -1
if winner(board) == -1:
reward, result = -1.0, "loss"
break
if not available(board):
reward, result = 0.2, "draw"
break
if learn:
next_state = tuple(board)
target = gamma * max(q[next_state][available(board)])
q[state][action] += alpha * (target - q[state][action])
if learn:
q[state][action] += alpha * (reward - q[state][action])
return result, board
# Q6C(d): Train through repeated games, gradually reducing exploration.
training_results = {"win": 0, "draw": 0, "loss": 0}
for episode in range(30000):
epsilon = max(0.05, 1 - episode / 24000)
result, _ = play_episode(epsilon)
training_results[result] += 1
print("Training results:", training_results)
print("Learned board states:", len(q))
# Q6C(e): Test the learned greedy policy against new random games.
test_results = {"win": 0, "draw": 0, "loss": 0}
for _ in range(1000):
result, _ = play_episode(epsilon=0, learn=False)
test_results[result] += 1
print("Test results (1000 games):", test_results)
print("Win rate:", round(test_results["win"] / 1000, 3))
print("Example game (X=agent, O=random opponent):")
result, final_board = play_episode(epsilon=0, learn=False)
show(final_board)
print("Result:", result)