Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Integrate an advanced A* heuristic with optimized neighbors into the Q-learner for…

  1. 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()
    
  2. 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

    1. 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).

    2. 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.
    3. 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.

    4. 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

    1. *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_set to keep track of visited nodes, preventing redundant evaluations.
    2. 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.
    3. 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.
      • Benefit: This approach ensures that the agent leverages the optimal path when confident while still exploring other possibilities to learn from diverse experiences.
    4. 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.
    5. 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.

    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.