Integrate an advanced A* heuristic with optimized neighbors into the Q-learner for…
- User
Integrate an advanced A* heuristic with optimized neighbors into the Q-learner for faster learning and optimized usage of snake AI decision.
import pygame import sys import random from collections import deque import heapq # Initialize Pygame pygame.init() # Game Constants CELL_SIZE = 20 GRID_WIDTH = 30 GRID_HEIGHT = 20 WINDOW_WIDTH = CELL_SIZE * GRID_WIDTH + 200 # Extra width for UI WINDOW_HEIGHT = CELL_SIZE * GRID_HEIGHT FPS = 10 # Boost Constants BOOST_DURATION = 50 # Number of frames boost is active BOOST_COOLDOWN = 100 # Number of frames before boost can be activated again BOOST_SPEED_MULTIPLIER = 2 # Multiplier for FPS when boost is active # Q-Learning Constants ACTIONS = [ ("UP", False), ("DOWN", False), ("LEFT", False), ("RIGHT", False), ("UP", True), ("DOWN", True), ("LEFT", True), ("RIGHT", True) ] REWARD_FOOD = 100 REWARD_STEP = 1 REWARD_BOOST = 10 PENALTY_COLLISION = -100 PENALTY_BOOST = -10 # Colors WHITE = (255, 255, 255) GREY = (40, 40, 40) BLACK = (0, 0, 0) GREEN = (0, 255, 0) RED = (255, 0, 0) BLUE = (0, 0, 255) YELLOW = (255, 255, 0) # Set up display screen = pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT)) pygame.display.set_caption("Advanced Snake AI with Q-Learning and Boost") clock = pygame.time.Clock() # Initialize Font pygame.font.init() FONT_SIZE = 20 FONT = pygame.font.SysFont('Calibri', FONT_SIZE, bold=True) def render_text(text, color, position): """ Renders text on the screen at the given position. """ text_surface = FONT.render(text, True, color) screen.blit(text_surface, position) def render_text_with_background(text, color, position, bg_color=(0, 0, 0, 150)): """ Renders text with a semi-transparent background. """ text_surface = FONT.render(text, True, color) bg_surface = pygame.Surface((text_surface.get_width() + 10, text_surface.get_height() + 5), pygame.SRCALPHA) bg_surface.fill(bg_color) screen.blit(bg_surface, (position[0] - 5, position[1] - 2)) screen.blit(text_surface, position) class Snake: def __init__(self): self.positions = deque([(GRID_WIDTH // 2, GRID_HEIGHT // 2)]) self.direction = (0, -1) # Initially moving upwards self.grow = False self.hamiltonian = generate_hamiltonian_cycle() self.cycle_index = self.hamiltonian.index(self.head()) if self.head() in self.hamiltonian else 0 # Boost attributes self.boost_active = False self.boost_duration = 0 self.boost_cooldown = 0 def head(self): return self.positions[0] def move(self, direction): if direction is not None: self.direction = direction new_x = self.head()[0] + self.direction[0] new_y = self.head()[1] + self.direction[1] new_position = (new_x, new_y) # Check wall collision if (0 <= new_x < GRID_WIDTH) and (0 <= new_y < GRID_HEIGHT) and new_position not in self.positions: self.positions.appendleft(new_position) if not self.grow: self.positions.pop() else: self.grow = False return True # Successful move else: return False # Collision occurred def grow_snake(self): self.grow = True def follow_hamiltonian(self): """ Follows the next step in the Hamiltonian cycle. """ self.cycle_index = (self.cycle_index + 1) % len(self.hamiltonian) next_cell = self.hamiltonian[self.cycle_index] direction = (next_cell[0] - self.head()[0], next_cell[1] - self.head()[1]) return direction def activate_boost(self): if self.boost_cooldown == 0 and not self.boost_active: self.boost_active = True self.boost_duration = BOOST_DURATION self.boost_cooldown = BOOST_COOLDOWN def update_boost(self): if self.boost_active: self.boost_duration -= 1 if self.boost_duration <= 0: self.boost_active = False if self.boost_cooldown > 0: self.boost_cooldown -= 1 class Food: def __init__(self, snake_positions): self.position = self.random_position(snake_positions) def random_position(self, snake_positions): while True: pos = (random.randint(0, GRID_WIDTH - 1), random.randint(0, GRID_HEIGHT - 1)) if pos not in snake_positions: return pos def respawn(self, snake_positions): self.position = self.random_position(snake_positions) def generate_hamiltonian_cycle(): cycle = [] for y in range(GRID_HEIGHT): row = list(range(GRID_WIDTH)) if y % 2 == 1: row.reverse() for x in row: cycle.append((x, y)) return cycle def draw_grid(): for x in range(0, GRID_WIDTH * CELL_SIZE, CELL_SIZE): pygame.draw.line(screen, GREY, (x, 0), (x, GRID_HEIGHT * CELL_SIZE)) for y in range(0, GRID_HEIGHT * CELL_SIZE, CELL_SIZE): pygame.draw.line(screen, GREY, (0, y), (GRID_WIDTH * CELL_SIZE, y)) def draw_snake(snake): for pos in snake.positions: rect = pygame.Rect(pos[0] * CELL_SIZE, pos[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, GREEN, rect) def draw_food(food): rect = pygame.Rect(food.position[0] * CELL_SIZE, food.position[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, RED, rect) def draw_path(path): for pos in path: rect = pygame.Rect(pos[0] * CELL_SIZE, pos[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, BLUE, rect, 2) # Draw path with blue lines def draw_hamiltonian_cycle(snake, cycle_length=50): start_index = snake.cycle_index end_index = (start_index + cycle_length) % len(snake.hamiltonian) if start_index < end_index: cycle_path = snake.hamiltonian[start_index:end_index] else: cycle_path = snake.hamiltonian[start_index:] + snake.hamiltonian[:end_index] for pos in cycle_path: rect = pygame.Rect(pos[0] * CELL_SIZE, pos[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, WHITE, rect, 1) # Draw cycle with white lines def get_state(snake, food): head_x, head_y = snake.head() food_x, food_y = food.position # Relative position of food food_direction = ( 1 if food_x > head_x else -1 if food_x < head_x else 0, 1 if food_y > head_y else -1 if food_y < head_y else 0 ) # Immediate obstacles obstacles = [ 1 if (head_x + dx, head_y + dy) in snake.positions or not (0 <= head_x + dx < GRID_WIDTH and 0 <= head_y + dy < GRID_HEIGHT) else 0 for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)] ] # Boost availability boost_available = 1 if snake.boost_cooldown == 0 else 0 # Current direction direction = snake.direction direction_binary = { (0, -1): [1, 0, 0, 0], # Up (0, 1): [0, 1, 0, 0], # Down (-1, 0): [0, 0, 1, 0], # Left (1, 0): [0, 0, 0, 1] # Right } state = tuple(direction_binary.get(direction, [0,0,0,0]) + list(food_direction) + obstacles + [boost_available]) return state class QLearningAgent: def __init__(self, actions, alpha=0.1, gamma=0.9, epsilon=1.0, epsilon_decay=0.995, min_epsilon=0.01): self.q_table = {} # {(state): {action: value}} self.actions = actions self.alpha = alpha # Learning rate self.gamma = gamma # Discount factor self.epsilon = epsilon # Exploration rate self.epsilon_decay = epsilon_decay self.min_epsilon = min_epsilon def get_q(self, state, action): return self.q_table.get(state, {}).get(action, 0.0) def choose_action(self, state): import random if random.random() < self.epsilon: return random.choice(self.actions) else: q_values = self.q_table.get(state, {}) max_q = max(q_values.values(), default=0) max_actions = [action for action, q in q_values.items() if q == max_q] return random.choice(max_actions) if max_actions else random.choice(self.actions) def learn(self, state, action, reward, next_state, done): old_q = self.get_q(state, action) if done: target = reward else: next_qs = self.q_table.get(next_state, {}) target = reward + self.gamma * max(next_qs.values(), default=0) new_q = old_q + self.alpha * (target - old_q) if state not in self.q_table: self.q_table[state] = {} self.q_table[state][action] = new_q # Decay epsilon if done: self.epsilon = max(self.min_epsilon, self.epsilon * self.epsilon_decay) def parse_action(action): direction, use_boost = action dir_map = { "UP": (0, -1), "DOWN": (0, 1), "LEFT": (-1, 0), "RIGHT": (1, 0) } return dir_map.get(direction, (0, -1)), use_boost def draw_boost_indicator(snake): if snake.boost_active: head = snake.head() rect = pygame.Rect(head[0] * CELL_SIZE, head[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, YELLOW, rect, 3) # Highlight the head with a yellow border def main(): snake = Snake() food = Food(snake.positions) running = True high_score = 0 debug_mode = True # Initialize debug mode as on agent = QLearningAgent(actions=ACTIONS) state = get_state(snake, food) action = agent.choose_action(state) direction, use_boost = parse_action(action) if use_boost: snake.activate_boost() while running: # Adjust FPS based on boost status if snake.boost_active: clock.tick(FPS * BOOST_SPEED_MULTIPLIER) else: clock.tick(FPS) for event in pygame.event.get(): if event.type == pygame.QUIT: running = False elif event.type == pygame.KEYDOWN: if event.key == pygame.K_d: debug_mode = not debug_mode # Toggle debug mode # Take action moved = snake.move(direction) done = False reward = REWARD_STEP # Default reward for surviving a step if not moved: # Collision occurred reward = PENALTY_COLLISION done = True # Check food collision if snake.head() == food.position: snake.grow_snake() food.respawn(snake.positions) reward = REWARD_FOOD # Update boost status snake.update_boost() # Observe new state next_state = get_state(snake, food) # Learn from the experience agent.learn(state, action, reward, next_state, done) # Choose next action if not done: action = agent.choose_action(next_state) direction, use_boost = parse_action(action) if use_boost: snake.activate_boost() # Update state state = next_state # Update high score current_score = len(snake.positions) - 1 if current_score > high_score: high_score = current_score # Rendering screen.fill(BLACK) draw_grid() draw_snake(snake) draw_food(food) # Draw boost indicator draw_boost_indicator(snake) # Draw a segment of the Hamiltonian cycle for reference draw_hamiltonian_cycle(snake) # Render Scores render_text_with_background(f"Score: {current_score}", WHITE, (GRID_WIDTH * CELL_SIZE + 10, 10)) render_text_with_background(f"High Score: {high_score}", WHITE, (GRID_WIDTH * CELL_SIZE + 10, 40)) # Render Debug Information if debug_mode: render_text_with_background(f"Boost Active: {snake.boost_active}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 70)) render_text_with_background(f"Boost Duration: {snake.boost_duration}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 100)) render_text_with_background(f"Boost Cooldown: {snake.boost_cooldown}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 130)) render_text_with_background(f"AI Epsilon: {agent.epsilon:.2f}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 160)) render_text_with_background(f"Cycle Index: {snake.cycle_index}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 190)) pygame.display.flip() pygame.quit() sys.exit() if __name__ == "__main__": main() - Assistant
Integrating an advanced A* heuristic with optimized neighbor exploration into the Q-Learning framework can significantly enhance the Snake AI's decision-making efficiency and learning speed. The A* algorithm provides an informed pathfinding approach that complements Q-Learning by guiding the agent towards the food while avoiding obstacles, thereby reducing the exploration space and accelerating convergence.
Overview of the Integration
-
A Pathfinding Implementation*: We introduce an A* pathfinding function that computes the optimal path from the snake's head to the food, considering the current state of the grid (including obstacles like the snake's body).
-
Heuristic Integration with Q-Learning:
- Action Biasing: Utilize the A* computed path to bias the action selection process in the Q-Learning agent. Actions that are part of the A* path are given higher priority, encouraging the agent to follow optimal paths.
- Reward Shaping: Enhance the reward structure by incorporating heuristic-based rewards. For example, actions that lead closer to the food according to the A* path can receive additional rewards.
-
Optimized Neighbor Exploration: Optimize the neighbor selection in the A* algorithm to ensure faster computations. This includes using efficient data structures like priority queues (
heapq) and minimizing redundant checks. -
Combined Decision-Making: The AI uses both Q-Learning and A* heuristics to make informed decisions. While Q-Learning handles the learning aspect, A* provides real-time guidance, ensuring the snake takes optimal steps towards the food.
Updated Code with A* Integration
Below is the enhanced version of your Snake AI code with the integrated A* heuristic:
import pygame import sys import random from collections import deque import heapq # Initialize Pygame pygame.init() # Game Constants CELL_SIZE = 20 GRID_WIDTH = 30 GRID_HEIGHT = 20 WINDOW_WIDTH = CELL_SIZE * GRID_WIDTH + 200 # Extra width for UI WINDOW_HEIGHT = CELL_SIZE * GRID_HEIGHT FPS = 10 # Boost Constants BOOST_DURATION = 50 # Number of frames boost is active BOOST_COOLDOWN = 100 # Number of frames before boost can be activated again BOOST_SPEED_MULTIPLIER = 2 # Multiplier for FPS when boost is active # Q-Learning Constants ACTIONS = [ ("UP", False), ("DOWN", False), ("LEFT", False), ("RIGHT", False), ("UP", True), ("DOWN", True), ("LEFT", True), ("RIGHT", True) ] REWARD_FOOD = 100 REWARD_STEP = 1 REWARD_BOOST = 10 PENALTY_COLLISION = -100 PENALTY_BOOST = -10 # Colors WHITE = (255, 255, 255) GREY = (40, 40, 40) BLACK = (0, 0, 0) GREEN = (0, 255, 0) RED = (255, 0, 0) BLUE = (0, 0, 255) YELLOW = (255, 255, 0) # Set up display screen = pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT)) pygame.display.set_caption("Advanced Snake AI with Q-Learning and Boost") clock = pygame.time.Clock() # Initialize Font pygame.font.init() FONT_SIZE = 20 FONT = pygame.font.SysFont('Calibri', FONT_SIZE, bold=True) def render_text(text, color, position): """ Renders text on the screen at the given position. """ text_surface = FONT.render(text, True, color) screen.blit(text_surface, position) def render_text_with_background(text, color, position, bg_color=(0, 0, 0, 150)): """ Renders text with a semi-transparent background. """ text_surface = FONT.render(text, True, color) bg_surface = pygame.Surface((text_surface.get_width() + 10, text_surface.get_height() + 5), pygame.SRCALPHA) bg_surface.fill(bg_color) screen.blit(bg_surface, (position[0] - 5, position[1] - 2)) screen.blit(text_surface, position) class Snake: def __init__(self): self.positions = deque([(GRID_WIDTH // 2, GRID_HEIGHT // 2)]) self.direction = (0, -1) # Initially moving upwards self.grow = False self.hamiltonian = generate_hamiltonian_cycle() self.cycle_index = self.hamiltonian.index(self.head()) if self.head() in self.hamiltonian else 0 # Boost attributes self.boost_active = False self.boost_duration = 0 self.boost_cooldown = 0 def head(self): return self.positions[0] def move(self, direction): if direction is not None: self.direction = direction new_x = self.head()[0] + self.direction[0] new_y = self.head()[1] + self.direction[1] new_position = (new_x, new_y) # Check wall collision if (0 <= new_x < GRID_WIDTH) and (0 <= new_y < GRID_HEIGHT) and new_position not in self.positions: self.positions.appendleft(new_position) if not self.grow: self.positions.pop() else: self.grow = False return True # Successful move else: return False # Collision occurred def grow_snake(self): self.grow = True def follow_hamiltonian(self): """ Follows the next step in the Hamiltonian cycle. """ self.cycle_index = (self.cycle_index + 1) % len(self.hamiltonian) next_cell = self.hamiltonian[self.cycle_index] direction = (next_cell[0] - self.head()[0], next_cell[1] - self.head()[1]) return direction def activate_boost(self): if self.boost_cooldown == 0 and not self.boost_active: self.boost_active = True self.boost_duration = BOOST_DURATION self.boost_cooldown = BOOST_COOLDOWN def update_boost(self): if self.boost_active: self.boost_duration -= 1 if self.boost_duration <= 0: self.boost_active = False if self.boost_cooldown > 0: self.boost_cooldown -= 1 class Food: def __init__(self, snake_positions): self.position = self.random_position(snake_positions) def random_position(self, snake_positions): while True: pos = (random.randint(0, GRID_WIDTH - 1), random.randint(0, GRID_HEIGHT - 1)) if pos not in snake_positions: return pos def respawn(self, snake_positions): self.position = self.random_position(snake_positions) def generate_hamiltonian_cycle(): cycle = [] for y in range(GRID_HEIGHT): row = list(range(GRID_WIDTH)) if y % 2 == 1: row.reverse() for x in row: cycle.append((x, y)) return cycle def draw_grid(): for x in range(0, GRID_WIDTH * CELL_SIZE, CELL_SIZE): pygame.draw.line(screen, GREY, (x, 0), (x, GRID_HEIGHT * CELL_SIZE)) for y in range(0, GRID_HEIGHT * CELL_SIZE, CELL_SIZE): pygame.draw.line(screen, GREY, (0, y), (GRID_WIDTH * CELL_SIZE, y)) def draw_snake(snake): for pos in snake.positions: rect = pygame.Rect(pos[0] * CELL_SIZE, pos[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, GREEN, rect) def draw_food(food): rect = pygame.Rect(food.position[0] * CELL_SIZE, food.position[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, RED, rect) def draw_path(path): for pos in path: rect = pygame.Rect(pos[0] * CELL_SIZE, pos[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, BLUE, rect, 2) # Draw path with blue lines def draw_hamiltonian_cycle(snake, cycle_length=50): start_index = snake.cycle_index end_index = (start_index + cycle_length) % len(snake.hamiltonian) if start_index < end_index: cycle_path = snake.hamiltonian[start_index:end_index] else: cycle_path = snake.hamiltonian[start_index:] + snake.hamiltonian[:end_index] for pos in cycle_path: rect = pygame.Rect(pos[0] * CELL_SIZE, pos[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, WHITE, rect, 1) # Draw cycle with white lines def get_state(snake, food, path_length=None): head_x, head_y = snake.head() food_x, food_y = food.position # Relative position of food food_direction = ( 1 if food_x > head_x else -1 if food_x < head_x else 0, 1 if food_y > head_y else -1 if food_y < head_y else 0 ) # Immediate obstacles obstacles = [ 1 if (head_x + dx, head_y + dy) in snake.positions or not (0 <= head_x + dx < GRID_WIDTH and 0 <= head_y + dy < GRID_HEIGHT) else 0 for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)] ] # Boost availability boost_available = 1 if snake.boost_cooldown == 0 else 0 # Current direction direction = snake.direction direction_binary = { (0, -1): [1, 0, 0, 0], # Up (0, 1): [0, 1, 0, 0], # Down (-1, 0): [0, 0, 1, 0], # Left (1, 0): [0, 0, 0, 1] # Right } state = tuple(direction_binary.get(direction, [0,0,0,0]) + list(food_direction) + obstacles + [boost_available]) # Optionally include A* path length as part of the state if path_length is not None: # Normalize path length to a range, e.g., [0, 1] max_possible_length = GRID_WIDTH * GRID_HEIGHT normalized_length = path_length / max_possible_length state += (normalized_length,) return state class QLearningAgent: def __init__(self, actions, alpha=0.1, gamma=0.9, epsilon=1.0, epsilon_decay=0.995, min_epsilon=0.01): self.q_table = {} # {(state): {action: value}} self.actions = actions self.alpha = alpha # Learning rate self.gamma = gamma # Discount factor self.epsilon = epsilon # Exploration rate self.epsilon_decay = epsilon_decay self.min_epsilon = min_epsilon def get_q(self, state, action): return self.q_table.get(state, {}).get(action, 0.0) def choose_action(self, state, preferred_actions=None): import random if random.random() < self.epsilon: return random.choice(self.actions) else: q_values = self.q_table.get(state, {}) max_q = max(q_values.values(), default=0) max_actions = [action for action, q in q_values.items() if q == max_q] return random.choice(max_actions) if max_actions else random.choice(self.actions) def learn(self, state, action, reward, next_state, done): old_q = self.get_q(state, action) if done: target = reward else: next_qs = self.q_table.get(next_state, {}) target = reward + self.gamma * max(next_qs.values(), default=0) new_q = old_q + self.alpha * (target - old_q) if state not in self.q_table: self.q_table[state] = {} self.q_table[state][action] = new_q # Decay epsilon if done: self.epsilon = max(self.min_epsilon, self.epsilon * self.epsilon_decay) def parse_action(action): direction, use_boost = action dir_map = { "UP": (0, -1), "DOWN": (0, 1), "LEFT": (-1, 0), "RIGHT": (1, 0) } return dir_map.get(direction, (0, -1)), use_boost def draw_boost_indicator(snake): if snake.boost_active: head = snake.head() rect = pygame.Rect(head[0] * CELL_SIZE, head[1] * CELL_SIZE, CELL_SIZE, CELL_SIZE) pygame.draw.rect(screen, YELLOW, rect, 3) # Highlight the head with a yellow border def a_star_search(start, goal, snake_positions): """ Performs A* search from start to goal avoiding snake_positions. Returns the path as a list of positions from start to goal, inclusive. If no path found, returns an empty list. """ def heuristic(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) # Manhattan distance open_set = [] heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start, [start])) closed_set = set() while open_set: estimated_total, cost, current, path = heapq.heappop(open_set) if current == goal: return path if current in closed_set: continue closed_set.add(current) for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: neighbor = (current[0] + dx, current[1] + dy) if (0 <= neighbor[0] < GRID_WIDTH and 0 <= neighbor[1] < GRID_HEIGHT and neighbor not in snake_positions and neighbor not in closed_set): new_cost = cost + 1 estimated = new_cost + heuristic(neighbor, goal) heapq.heappush(open_set, (estimated, new_cost, neighbor, path + [neighbor])) return [] def integrate_a_star(agent, snake, food): """ Integrates A* by influencing the action selection to prefer actions along the A* path. """ path = a_star_search(snake.head(), food.position, set(snake.positions)) if len(path) < 2: # No path found or already at food return None next_step = path[1] action_direction = (next_step[0] - snake.head()[0], next_step[1] - snake.head()[1]) # Map direction to action dir_map = { (0, -1): "UP", (0, 1): "DOWN", (-1, 0): "LEFT", (1, 0): "RIGHT" } action_dir = dir_map.get(action_direction, "UP") # Prefer actions that are on the A* path preferred_action = (action_dir, False) # Not using boost for path following return preferred_action def main(): snake = Snake() food = Food(snake.positions) running = True high_score = 0 debug_mode = True # Initialize debug mode as on agent = QLearningAgent(actions=ACTIONS) path = [] state = get_state(snake, food) action = agent.choose_action(state) direction, use_boost = parse_action(action) if use_boost: snake.activate_boost() while running: # Adjust FPS based on boost status if snake.boost_active: clock.tick(FPS * BOOST_SPEED_MULTIPLIER) else: clock.tick(FPS) for event in pygame.event.get(): if event.type == pygame.QUIT: running = False elif event.type == pygame.KEYDOWN: if event.key == pygame.K_d: debug_mode = not debug_mode # Toggle debug mode # Integrate A* to get preferred action preferred_action = integrate_a_star(agent, snake, food) # Decide whether to follow A* or Q-Learning based on epsilon if preferred_action and random.random() > agent.epsilon: # Follow A* path action = preferred_action direction, use_boost = parse_action(action) else: # Q-Learning chooses action action = agent.choose_action(state) direction, use_boost = parse_action(action) if use_boost: snake.activate_boost() # Take action moved = snake.move(direction) done = False reward = REWARD_STEP # Default reward for surviving a step if not moved: # Collision occurred reward = PENALTY_COLLISION done = True # Check food collision if snake.head() == food.position: snake.grow_snake() food.respawn(snake.positions) reward = REWARD_FOOD # Update boost status snake.update_boost() # Observe new state # Optionally, include path length as part of the state path = a_star_search(snake.head(), food.position, set(snake.positions)) path_length = len(path) if path else None next_state = get_state(snake, food, path_length) # Learn from the experience agent.learn(state, action, reward, next_state, done) # Update state state = next_state # Update high score current_score = len(snake.positions) - 1 if current_score > high_score: high_score = current_score # Rendering screen.fill(BLACK) draw_grid() draw_snake(snake) draw_food(food) # Optionally draw the A* path for visualization if path: draw_path(path) # Draw boost indicator draw_boost_indicator(snake) # Draw a segment of the Hamiltonian cycle for reference draw_hamiltonian_cycle(snake) # Render Scores render_text_with_background(f"Score: {current_score}", WHITE, (GRID_WIDTH * CELL_SIZE + 10, 10)) render_text_with_background(f"High Score: {high_score}", WHITE, (GRID_WIDTH * CELL_SIZE + 10, 40)) # Render Debug Information if debug_mode: render_text_with_background(f"Boost Active: {snake.boost_active}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 70)) render_text_with_background(f"Boost Duration: {snake.boost_duration}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 100)) render_text_with_background(f"Boost Cooldown: {snake.boost_cooldown}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 130)) render_text_with_background(f"AI Epsilon: {agent.epsilon:.2f}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 160)) render_text_with_background(f"Cycle Index: {snake.cycle_index}", YELLOW, (GRID_WIDTH * CELL_SIZE + 10, 190)) pygame.display.flip() pygame.quit() sys.exit() if __name__ == "__main__": main()Key Enhancements Explained
-
*A Pathfinding Function (
a_star_search)**:- Purpose: Computes the shortest path from the snake's head to the food while avoiding obstacles (the snake's body).
- Heuristic: Uses the Manhattan distance, which is suitable for grid-based movement.
- Optimizations:
- Utilizes a priority queue (
heapq) for efficient retrieval of the next node with the lowest estimated total cost. - Employs a
closed_setto keep track of visited nodes, preventing redundant evaluations.
- Utilizes a priority queue (
-
Integration Function (
integrate_a_star):- Functionality: Determines the preferred action based on the A* path.
- Mechanism: If a valid path exists, it identifies the next step and maps it to the corresponding action (e.g., moving "UP", "DOWN").
- Usage: This preferred action is then used to bias the action selection in the main loop.
-
Modified Action Selection in
main():- Logic: Combines both A* and Q-Learning for action selection.
- Exploit: With a probability of
1 - epsilon, the agent prefers actions suggested by the A* path. - Explore: With a probability of
epsilon, the agent selects random actions as per the standard Q-Learning exploration strategy.
- Exploit: With a probability of
- Benefit: This approach ensures that the agent leverages the optimal path when confident while still exploring other possibilities to learn from diverse experiences.
- Logic: Combines both A* and Q-Learning for action selection.
-
State Representation Enhancement (
get_state):- Inclusion of Path Length: Optionally, the length of the A* path (
path_length) is incorporated into the state. This additional feature provides the agent with more contextual information, potentially enhancing learning efficiency. - Normalization: The path length is normalized to maintain consistency and prevent scaling issues within the Q-Table.
- Inclusion of Path Length: Optionally, the length of the A* path (
-
Visualization Enhancements:
- Path Drawing (
draw_path): For debugging and visualization purposes, the computed A* path is drawn on the game grid. This helps in understanding the agent's decision-making process. - Hamiltonian Cycle Reference: Maintains the existing visualization of the Hamiltonian cycle, providing an additional layer of strategy overview.
- Path Drawing (
Benefits of the Integration
-
Accelerated Learning: By guiding the agent with the A* path, the exploration space is effectively reduced, allowing the agent to learn optimal behaviors more quickly.
-
Enhanced Decision-Making: Combining heuristic-based pathfinding with Q-Learning ensures that the agent not only learns from experience but also follows logical, goal-oriented paths.
-
Flexibility: The integrated approach allows the agent to adapt to dynamic scenarios, such as when the food relocates or when the snake grows longer, by recalculating the optimal path in real-time.
Potential Further Enhancements
-
Dynamic Heuristics: Incorporate more sophisticated heuristics that consider factors like potential traps or tail availability to further refine the agent's pathfinding capabilities.
-
Function Approximation: Transition from a Q-Table to function approximation methods (e.g., neural networks) to handle larger state spaces more efficiently.
-
Multi-Step Planning: Enhance the A* integration to consider multi-step planning, allowing the agent to foresee and avoid potential future collisions.
This integration strikes a balance between heuristic-based pathfinding and reinforcement learning, leveraging the strengths of both approaches to create a more robust and efficient Snake AI.
-