ТЕХНИЧЕСКОЕ ЗАДАНИЕ: Агент с tree search (MCTS) для математической задачи

1. Цель задачи

Разработать агента, использующего метод Monte Carlo Tree Search (MCTS) для решения математической задачи с тремя вариантами действий. Агент должен на основе симуляций строить дерево состояний и выбирать оптимальную последовательность операций, приводящую к целевому числу. Ключевой результат агент находит решение за ≤5000 симуляций в 9 из 10 запусков, превосходя baseline (случайный перебор) по доле успешных решений и среднему числу шагов.

2. Исходные данные

Задача для решения Начальное число: 1.
Действия (всегда применимы, если не оговорено):

• A: умножить на 2 (*2)
• B: прибавить 3 (+3)
• C: возвести в квадрат (**2)

Цель: получить число 100.
Ограничение: максимальная глубина поиска — 10 шагов (иначе задача считается нерешаемой).

Если нет готового окружения — симулируем:

1. Создать Python-файл math_env.py с классом MathEnv.
2. Написать класс MCTSAgent в файле mcts_agent.py.
3. Проверить на примере: start=1, goal=100.

3. Технологический стек

4. Этапы выполнения

Этап 1: Проектирование среды и действий (1 час)

Действия

1. Определить структуру состояния

   • State : int (текущее число).
   • is_terminal : True, если число равно цели (100) или превысило 1000 (выход за разумные пределы).
   • is_goal : True, если число == 100.

2. Реализовать класс MathEnv

   • init(self, start=1, goal=100, max_depth=10)
   • get_actions(state) → список строк ['*2', '+3', '^2']
   • step(state, action_name) → next_state (вычисление)
   • reward(state) → 1.0 если state == goal, иначе 0.0 (или -0.01 за шаг, чтобы поощрять короткие пути)

3. Проверить среду

   env = MathEnv()
   state = 1
   for a in ['*2', '+3', '^2']:
       print(f"{a}: {state} -> {env.step(state, a)}")
   

Ожидаемый результат этапа Рабочий класс MathEnv, проходит минимальные тесты (например, test_goal_reached).

Этап 2: Реализация MCTS с UCT (2–3 часа)

Действия

1. Создать класс MCTSNode

   • Поля: state, parent, children, visits, total_reward, action_that_led_here, untried_actions.
   • Метод is_fully_expanded() → len(self.untried_actions) == 0.
   • Метод best_child(c=1.41) → выбор по UCB1.

2. Создать класс MCTSAgent

   • init(self, env, iterations=1000, c=1.41, max_depth=10)
   • search(state) → выполняет итерации MCTS:
     • Selection спуск по дереву с помощью best_child до терминального или не полностью раскрытого узла.
     • Expansion если узел не терминальный и не полностью раскрыт – добавить один новый дочерний узел (случайное действие из untried_actions).
     • Simulation (Rollout): из нового узла симулировать случайные действия до терминала или max_depth; подсчитать накопленную награду.
     • Backpropagation: обновить visits и total_reward на всём пути от нового узла до корня.
   • best_action(state) → после всех итераций выбрать действие с максимальным visits или средним reward.

3. Детали реализации симуляции

   def rollout(self, state, depth=0):
       if env.is_terminal(state) or depth >= self.max_depth:
           return env.reward(state)
       action = random.choice(env.get_actions(state))
       next_state = env.step(state, action)
       return self.rollout(next_state, depth+1)
   

Ожидаемый результат этапа Агент способен делать осмысленный ход для задачи.

Этап 3: Интеграция агента и тестирование (1–2 часа)

Действия

1. Написать скрипт solve_with_mcts.py

   • Инициализация env и agent с параметрами iterations=2000.
   • Запуск цикла: пока state != goal и steps < max_depth:
     • action = agent.best_action(state)
     • state = env.step(state, action)
     • Добавить узел в дерево (или перестроить заново).
   • Вывод последовательности действий и финального числа.

2. Реализовать baseline

   def random_agent(env, start, max_steps=10):
       state = start
       path = []
       for _ in range(max_steps):
           if env.is_goal(state):
               return path
           action = random.choice(env.get_actions(state))
           state = env.step(state, action)
           path.append(action)
       return None
   

3. Сравнить результаты (10 запусков):

   • MCTS: доля успешных решений, среднее число шагов, среднее кол-во симуляций.
   • Random: аналогично.

Ожидаемый результат этапа Агент MCTS находит решение чаще и быстрее, чем случайный.

Этап 4: Визуализация и анализ (1 час)

Действия

1. Построить дерево поиска для лучшего решения:

   • Использовать networkx.DiGraph.
   • Узлы — числа, рёбра — действия.
   • Раскрасить узлы по количеству посещений (чем больше — тем темнее).
   • Подписать число посещений и среднюю награду.

2. Построить график сходимости

   • По оси X — номер итерации MCTS.
   • По оси Y — максимальная награда среди листьев.
   • Показать, как улучшается оценка.

3. Собрать статистику

   • Размер дерева (количество узлов) для каждой итерации.
   • Количество узлов на каждом уровне глубины.

Ожидаемый результат этапа Визуализация дерева и кривая сходимости.

Этап 5: Документация и фиксация артефактов (0.5 часа)

Действия

1. Оформить README с описанием задачи, архитектуры, результатов сравнения.
2. Закоммитить все файлы в репозиторий (или папку проекта).
3. Написать краткий post-hoc анализ: что бы изменили для ускорения (например, эвристики, расширение действий, уменьшение iterations).

Ожидаемый результат этапа Готовый проект с кодом, визуализациями и документацией.

5. Критерии приемки (Definition of Done)

• Среда MathEnv корректно реализует переходы и терминальные условия.
• MCTS с UCB1 выбирает действие за ≤5 вызовов после обучения (1000+ симуляций).
• Агент находит решение для start=1, goal=100 за ≤10 шагов хотя бы в 8 из 10 запусков.
• Baseline (случайный) решает задачу менее чем в 30% запусков за 10 шагов.
• Дерево поиска визуализировано с помощью networkx; на рисунке указаны числа.
• Кривая сходимости показывает рост максимальной награды.
• Код покрыт минимум 3 тестами (test_env, test_mcts_node, test_full_solve).
• README содержит инструкцию по запуску и пример вывода.

6. Ожидаемый результат

Основной артефакт Python-скрипты (math_env.py, mcts_agent.py, solve.py), файл с результатами (results.md или stats.json), визуализации (tree.png, convergence.png).

Содержание результатов

• Лог лучшего найденного пути (например: 1 -> *2=2 -> +3=5 -> ^2=25 -> *2=50 -> *2=100)
• Статистика по 10 запускам (таблица: метод, успех, шаги, симуляции)
• Графики

Опционально

• Сравнение с разными константами C (exploration) и числом итераций.
• Добавление четвёртого действия (например, /2).

7. Возможные сложности и их решение

8. Бюджет времени (оценка)

Примечание для первого раза Рекомендуется заложить +2 часа на отладку UCB1 и настройку параметров. Если задача решается слишком легко/сложно — изменить действия (добавить -2 или заменить квадрат на куб).

9. Связанные вопросы из базы знаний

10. Чек-лист самопроверки

• Я реализовал среду и проверил её на простых примерах (1 -> *2 -> 2).
• Я написал класс MCTSNode с корректным подсчётом UCB1.
• Я проверил, что после 1000 симуляций для state=1 агент выбирает разумное действие.
• Я сравнил MCTS с baseline и получил значимое превосходство.
• Я создал визуализацию дерева и график сходимости, и они выглядят содержательно.