Практика 15. Эвристические алгоритмы. Генетический алгоритм. Обучение с подкреплением

    import random
    import string

    # Целевая строка
    TARGET = "Hello world!"
    # Размер популяции
    POPULATION_SIZE = 100
    # Вероятность мутации
    MUTATION_RATE = 0.01
    # Символы, которые могут использоваться
    CHARS = string.printable

    def random_string(length):
        return ''.join(random.choice(CHARS) for _ in range(length))

    def fitness(individual):
        return sum(1 for expected, actual in zip(TARGET, individual) if expected == actual)

    def mutate(individual):
        return ''.join(
            c if random.random() > MUTATION_RATE else random.choice(CHARS)
            for c in individual
        )

    def crossover(parent1, parent2):
        split = random.randint(0, len(TARGET))
        return parent1[:split] + parent2[split:]

    # Инициализация популяции
    population = [random_string(len(TARGET)) for _ in range(POPULATION_SIZE)]

    generation = 0
    while True:
        # Оценка приспособленности
        population = sorted(population, key=fitness, reverse=True)
        best = population[0]
        print(f"Gen {generation}: {best} (fitness: {fitness(best)})")

        if best == TARGET:
            break

        # Отбор лучших и создание новой популяции
        new_population = population[:2]  # Элитизм: сохранить лучших
        while len(new_population) < POPULATION_SIZE:
            parents = random.choices(population[:50], k=2)  # Скрещивать лучших
            child = mutate(crossover(*parents))
            new_population.append(child)

        population = new_population
        generation += 1

Разберем основные элементы кода генетичесокго алгоритма

    const std::string TARGET = "Hello world!";
    const int POPULATION_SIZE = 100;
    const double MUTATION_RATE = 0.01;

Константы и настройки. Задают целевую строку, размер популяции и вероятность мутации.

    std::string random_string(size_t length);

Генерация случайной строки. Создаёт случайную строку из допустимых символов.

    int fitness(const std::string& individual);

Оценка приспособленности. Подсчитывает количество совпадающих символов с целевой строкой.

    std::string mutate(const std::string& individual);

Мутация. Случайно изменяет отдельные символы с заданной вероятностью.

    std::string crossover(const std::string& parent1, const std::string& parent2);

Скрещивание Создаёт потомка, объединяя части двух родителей.

    while (true) {
        // сортировка, отбор, создание новой популяции
    }

Цикл поколений:

• Сортировка по приспособленности
• Вывод лучшего результата
• Отбор лучших и генерация потомков
• Завершение при совпадении с TARGET

Полный код программы предсатвлен ниже

    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <random>
    #include <ctime>

    const std::string TARGET = "Hello world!";
    const int POPULATION_SIZE = 100;
    const double MUTATION_RATE = 0.01;
    const std::string CHARS =
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c";

    // Генератор случайных чисел
    std::mt19937 rng(std::time(nullptr));
    std::uniform_real_distribution<double> mutation_dist(0.0, 1.0);
    std::uniform_int_distribution<int> char_dist(0, CHARS.size() - 1);
    std::uniform_int_distribution<int> crossover_dist(0, TARGET.size());

    std::string random_string(size_t length) {
        std::string s;
        for (size_t i = 0; i < length; ++i) {
            s += CHARS[char_dist(rng)];
        }
        return s;
    }

    int fitness(const std::string& individual) {
        int score = 0;
        for (size_t i = 0; i < TARGET.size(); ++i) {
            if (i < individual.size() && individual[i] == TARGET[i]) {
                ++score;
            }
        }
        return score;
    }

    std::string mutate(const std::string& individual) {
        std::string result = individual;
        for (char& c : result) {
            if (mutation_dist(rng) < MUTATION_RATE) {
                c = CHARS[char_dist(rng)];
            }
        }
        return result;
    }

    std::string crossover(const std::string& parent1, const std::string& parent2) {
        int split = crossover_dist(rng);
        return parent1.substr(0, split) + parent2.substr(split);
    }

    int main() {
        std::vector<std::string> population;
        for (int i = 0; i < POPULATION_SIZE; ++i) {
            population.push_back(random_string(TARGET.size()));
        }

        int generation = 0;

        while (true) {
            // Сортировка по убыванию приспособленности
            std::sort(population.begin(), population.end(), [](const std::string& a, const std::string& b) {
                return fitness(a) > fitness(b);
            });

            const std::string& best = population[0];
            std::cout << "Gen " << generation << ": " << best << " (fitness: " << fitness(best) << ")\n";

            if (best == TARGET) {
                break;
            }

            std::vector<std::string> new_population = { population[0], population[1] };

            std::uniform_int_distribution<int> parent_dist(0, 49); // топ-50

            while (new_population.size() < POPULATION_SIZE) {
                const std::string& parent1 = population[parent_dist(rng)];
                const std::string& parent2 = population[parent_dist(rng)];
                std::string child = mutate(crossover(parent1, parent2));
                new_population.push_back(child);
            }

            population = new_population;
            ++generation;
        }

        return 0;
    }

    import pygame
    import random
    import math
    import sys

pygame — для отрисовки и обработки графики.

random — для генерации случайных чисел (мутация, начальные гены).

math — математические функции (здесь почти не используется).

sys — для выхода из программы.

    WIDTH, HEIGHT = 800, 600
    AGENT_RADIUS = 4
    GOAL = pygame.Vector2(WIDTH // 2, 50)
    GENE_LENGTH = 200
    POP_SIZE = 100
    MUTATION_RATE = 0.01
    MAX_SPEED = 4
    fps = 60

Размеры экрана (WIDTH, HEIGHT) Радиус агента (AGENT_RADIUS) Цель (GOAL) в верхней части экрана Длина "гена" (количество шагов движения) Размер популяции (POP_SIZE) Вероятность мутации (MUTATION_RATE) Максимальная скорость агента (MAX_SPEED)

Опишем класс, отвечающий за работу с генами (Класс DNA)

    class DNA:
        def __init__(self, genes=None):
            if genes:
                self.genes = genes
            else:
                self.genes = [pygame.Vector2(random.uniform(-1, 1), random.uniform(-1, 1)).normalize() * MAX_SPEED for _ in range(GENE_LENGTH)]

        def crossover(self, partner):
            new_genes = []
            for i in range(len(self.genes)):
                if i % 2 == 0:
                    new_genes.append(self.genes[i])
                else:
                    new_genes.append(partner.genes[i])
            return DNA(new_genes)

        def mutate(self):
            for i in range(len(self.genes)):
                if random.random() < MUTATION_RATE:
                    self.genes[i] = pygame.Vector2(random.uniform(-1, 1), random.uniform(-1, 1)).normalize() * MAX_SPEED

Объяснение:

Гены представлены как список векторов скорости Кроссовер: смешение генов родителей (чередование) Мутация: случайное изменение генов с заданной вероятностью

Опишем класс, описывающий кажду особь в популяции отдельно

    class Agent:
        def __init__(self, dna=None):
            self.pos = pygame.Vector2(WIDTH // 2, HEIGHT - 50)
            self.vel = pygame.Vector2(0, 0)
            self.acc = pygame.Vector2(0, 0)
            self.dna = dna if dna else DNA()
            self.fitness = 0
            self.step = 0
            self.reached_goal = False

        def apply_force(self, force):
            self.acc += force

        def update(self):
            if not self.reached_goal and self.step < GENE_LENGTH:
                self.apply_force(self.dna.genes[self.step])
                self.step += 1

                self.vel += self.acc
                if self.vel.length() > MAX_SPEED:
                    self.vel.scale_to_length(MAX_SPEED)
                self.pos += self.vel
                self.acc *= 0

                if self.pos.distance_to(GOAL) < 10:
                    self.reached_goal = True

        def calc_fitness(self):
            distance = self.pos.distance_to(GOAL)
            self.fitness = 1 / (distance + 1)

        def draw(self, screen):
            pygame.draw.circle(screen, (0, 255, 0), (int(self.pos.x), int(self.pos.y)), AGENT_RADIUS)

Позиция стартует снизу экрана Обновление позиции по генам (последовательность движений) Фитнес-функция: обратная зависимость от расстояния до цели

Введем Класс Population - описающий действия над всей попляцией

    class Population:
        def __init__(self):
            self.agents = [Agent() for _ in range(POP_SIZE)]
            self.generation = 1
            self.mating_pool = []
            self.best_fitness = 0

        def update(self):
            for agent in self.agents:
                agent.update()

        def draw(self, screen):
            for agent in self.agents:
                agent.draw(screen)

        def evaluate(self):
            max_fitness = 0
            for agent in self.agents:
                agent.calc_fitness()
                if agent.fitness > max_fitness:
                    max_fitness = agent.fitness

            self.best_fitness = max_fitness
            self.mating_pool.clear()
            for agent in self.agents:
                n = int((agent.fitness / max_fitness) * 100)
                self.mating_pool += [agent] * n

        def reproduce(self):
            new_agents = []
            for _ in range(POP_SIZE):
                parent_a = random.choice(self.mating_pool)
                parent_b = random.choice(self.mating_pool)
                child_dna = parent_a.dna.crossover(parent_b.dna)
                child_dna.mutate()
                new_agents.append(Agent(child_dna))
            self.agents = new_agents
            self.generation += 1

Создание пула для размножения пропорционально фитнесу Селекция: случайный выбор родителей из пула Генетические операции: кроссовер + мутация Создание нового поколения

Наконец основной цикл + отрисовка параметров

    def draw_info(screen, population):
        texts = [
            f"Поколение: {population.generation}",
            f"Лучший фитнес: {population.best_fitness:.4f}",
            f"Популяция: {POP_SIZE}",
            f"Мутация: {MUTATION_RATE*100:.1f}%",
            f"Скорость симуляции (FPS): {fps}"
        ]
        for i, text in enumerate(texts):
            render = font.render(text, True, (255, 255, 255))
            screen.blit(render, (10, 10 + i * 22))

population = Population()
frame = 0

while True:
    screen.fill((30, 30, 30))
    pygame.draw.circle(screen, (255, 0, 0), (int(GOAL.x), int(GOAL.y)), 10)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        elif event.type == pygame.KEYDOWN:
            if event.key == pygame.K_v:
                fps = min(fps + 10, 240)
            elif event.key == pygame.K_d:
                fps = max(fps - 10, 1)

    if frame < GENE_LENGTH:
        population.update()
        frame += 1
    else:
        population.evaluate()
        population.reproduce()
        frame = 0

    population.draw(screen)
    draw_info(screen, population)

    pygame.display.flip()
    clock.tick(fps)

#include <SFML/Graphics.hpp>
#include <vector>
#include <cmath>
#include <random>
#include <ctime>
#include <string>
#include <sstream>

const int WIDTH = 800;
const int HEIGHT = 600;
const int AGENT_RADIUS = 4;
const int GENE_LENGTH = 200;
const int POP_SIZE = 100;
const float MUTATION_RATE = 0.01f;
const float MAX_SPEED = 4.0f;

sf::Vector2f GOAL(WIDTH / 2, 50);

std::mt19937 rng(static_cast<unsigned>(time(nullptr)));
std::uniform_real_distribution<float> distFloat(-1.f, 1.f);
std::uniform_real_distribution<float> dist01(0.f, 1.f);

Алгоритм, как обычно наичнается с контанты и их инциализации

Здесь задаются основные параметры программы, такие как размеры окна (WIDTH, HEIGHT), радиус агентов (AGENT_RADIUS), количество шагов для движения (GENE_LENGTH), размер популяции (POP_SIZE), коэффициент мутации (MUTATION_RATE) и максимальная скорость агентов (MAX_SPEED).

Также создается цель, к которой агенты должны стремиться (GOAL). Для генерации случайных чисел используется генератор случайных чисел и два распределения:

distFloat: для случайных координат.

dist01: для вероятностей (например, мутации).

sf::Vector2f randomVector2D() {
    sf::Vector2f v(distFloat(rng), distFloat(rng));
    float len = std::sqrt(v.x * v.x + v.y * v.y);
    if (len > 0) v *= MAX_SPEED / len;
    return v;
}

Эта функция генерирует случайный вектор с нормированным направлением. Она используется для создания случайных генов агентов.

class DNA {
public:
    std::vector<sf::Vector2f> genes;
    DNA() {
        genes.resize(GENE_LENGTH);
        for (auto& gene : genes) gene = randomVector2D();
    }
    DNA crossover(const DNA& partner) const {
        DNA child;
        for (size_t i = 0; i < genes.size(); ++i) {
            child.genes[i] = (i % 2 == 0) ? genes[i] : partner.genes[i];
        }
        return child;
    }
    void mutate() {
        for (auto& gene : genes) {
            if (dist01(rng) < MUTATION_RATE)
                gene = randomVector2D();
        }
    }
};

Класс DNA представляет генетическую информацию агента:

Конструктор генерирует случайные гены (вектора).

Метод crossover выполняет операцию скрещивания двух ДНК, комбинируя гены из двух партнеров.

Метод mutate случайным образом изменяет гены с вероятностью, определенной мутацией.

class Agent {
public:
    sf::Vector2f pos, vel, acc;
    DNA dna;
    int step = 0;
    float fitness = 0;
    bool reachedGoal = false;

    Agent(const DNA& d = DNA()) : pos(WIDTH / 2, HEIGHT - 50), dna(d) {}

    void applyForce(const sf::Vector2f& f) { acc += f; }

    void update() {
        if (reachedGoal || step >= GENE_LENGTH) return;
        applyForce(dna.genes[step++]);
        vel += acc;
        float speed = std::sqrt(vel.x * vel.x + vel.y * vel.y);
        if (speed > MAX_SPEED) vel *= MAX_SPEED / speed;
        pos += vel;
        acc *= 0.f;
        if (std::hypot(pos.x - GOAL.x, pos.y - GOAL.y) < 10)
            reachedGoal = true;
    }

    void calcFitness() {
        float d = std::hypot(pos.x - GOAL.x, pos.y - GOAL.y);
        fitness = 1.0f / (d + 1);
    }

    void draw(sf::RenderWindow& win) const {
        sf::CircleShape c(AGENT_RADIUS);
        c.setFillColor(sf::Color::Green);
        c.setPosition(pos - sf::Vector2f(AGENT_RADIUS, AGENT_RADIUS));
        win.draw(c);
    }
};

Класс Agent представляет собой агента, который имеет следующие параметры:

Позиция (pos), скорость (vel), ускорение (acc).

ДНК (через объект класса DNA).

Шаг в генах (step) и фитнес агента (fitness), который определяет, насколько близок агент к цели.

Метод applyForce добавляет силу к ускорению.

Метод update обновляет состояние агента: передвижение по шагам генов и проверка достижения цели.

Метод calcFitness вычисляет фитнес на основе расстояния до цели.

Метод draw рисует агента.

class Population {
public:
    std::vector<Agent> agents;
    int generation = 1;
    float bestFitness = 0;
    std::vector<Agent*> matingPool;

    Population() {
        agents.resize(POP_SIZE);
    }

    void update() {
        for (auto& a : agents) a.update();
    }

    void draw(sf::RenderWindow& win) {
        for (auto& a : agents) a.draw(win);
    }

    void evaluate() {
        bestFitness = 0;
        matingPool.clear();
        for (auto& a : agents) {
            a.calcFitness();
            if (a.fitness > bestFitness) bestFitness = a.fitness;
        }
        for (auto& a : agents) {
            int n = static_cast<int>((a.fitness / bestFitness) * 100);
            for (int i = 0; i < n; ++i) matingPool.push_back(&a);
        }
    }

    void reproduce() {
        std::vector<Agent> newAgents;
        newAgents.reserve(POP_SIZE);
        for (int i = 0; i < POP_SIZE; ++i) {
            Agent* p1 = matingPool[rng() % matingPool.size()];
            Agent* p2 = matingPool[rng() % matingPool.size()];
            DNA childDNA = p1->dna.crossover(p2->dna);
            childDNA.mutate();
            newAgents.emplace_back(childDNA);
        }
        agents = std::move(newAgents);
        generation++;
    }
};

Класс Population представляет популяцию агентов:

Метод update обновляет всех агентов в популяции.

Метод draw рисует всех агентов на экране.

Метод evaluate вычисляет фитнес всех агентов и формирует пул для спаривания.

Метод reproduce создает новое поколение агентов через операцию кроссовера и мутации.

void drawInfo(sf::RenderWindow& win, sf::Font& font, int gen, float bestFitness, int popSize, float mutRate, int fps) {
    std::ostringstream oss;
    oss << "Поколение: " << gen << "\nЛучший фитнес: " << bestFitness
        << "\nПопуляция: " << popSize << "\nМутация: " << mutRate * 100 << "%"
        << "\nFPS: " << fps;
    sf::Text text(oss.str(), font, 16);
    text.setFillColor(sf::Color::White);
    text.setPosition(10, 10);
    win.draw(text);
}

Эта функция отображает текущую информацию на экране: номер поколения, лучший фитнес, размер популяции, вероятность мутации и текущий FPS.

int main() {
    sf::RenderWindow window(sf::VideoMode(WIDTH, HEIGHT), "Генетический алгоритм SFML");
    window.setFramerateLimit(60);
    sf::Font font;
    if (!font.loadFromFile("arial.ttf")) return 1;

    Population population;
    int frame = 0;
    int fps = 60;

    while (window.isOpen()) {
        sf::Event e;
        while (window.pollEvent(e)) {
            if (e.type == sf::Event::Closed)
                window.close();
            if (e.type == sf::Event::KeyPressed) {
                if (e.key.code == sf::Keyboard::V)
                    fps = std::min(240, fps + 10);
                else if (e.key.code == sf::Keyboard::D)
                    fps = std::max(1, fps - 10);
                window.setFramerateLimit(fps);
            }
        }

        window.clear(sf::Color(30, 30, 30));
        sf::CircleShape goal(10);
        goal.setFillColor(sf::Color::Red);
        goal.setPosition(GOAL - sf::Vector2f(10, 10));
        window.draw(goal);

        if (frame < GENE_LENGTH) {
            population.update();
            ++frame;
        }
        else {
            population.evaluate();
            population.reproduce();
            frame = 0;
        }

        population.draw(window);
        drawInfo(window, font, population.generation, population.bestFitness, POP_SIZE, MUTATION_RATE, fps);
        window.display();
    }

    return 0;
}

Основная часть программы создает окно, обрабатывает события (например, изменение FPS с помощью клавиш), обновляет и рисует популяцию агентов, а также отображает информацию о состоянии симуляции.

import random

W, H = 19, 10                 # поле в клетках
START = (1, 8)                # старт шарика
TARGET = (16, 1)              # клетка-цель

ACTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]   # вверх, вниз, влево, вправо

ALPHA = 0.5        # скорость обучения
GAMMA = 0.95       # коэффициент дисконтирования
EPS_START = 0.30   # начальная вероятность случайного хода
EPS_END = 0.01
EPISODES = 400
MAX_STEPS = 200

def step(x, y, a):
    """Среда: применяем действие, возвращаем новое состояние и награду."""
    dx, dy = ACTIONS[a]
    nx = min(max(x + dx, 0), W - 1)
    ny = min(max(y + dy, 0), H - 1)
    if (nx, ny) == TARGET:
        return nx, ny, 100.0, True    # достигли цели
    return nx, ny, -1.0, False        # каждый шаг штрафуется

def train():
    Q = [[[0.0] * 4 for _ in range(H)] for _ in range(W)]
    for ep in range(EPISODES):
        eps = EPS_START + (EPS_END - EPS_START) * ep / (EPISODES - 1)
        x, y = START
        for t in range(MAX_STEPS):
            if random.random() < eps:
                a = random.randrange(4)                      # исследование
            else:
                a = max(range(4), key=lambda k: Q[x][y][k])  # использование
            nx, ny, r, done = step(x, y, a)
            # правило обновления Q-обучения
            best_next = 0.0 if done else max(Q[nx][ny])
            Q[x][y][a] += ALPHA * (r + GAMMA * best_next - Q[x][y][a])
            x, y = nx, ny
            if done:
                break
    return Q

def greedy_path(Q):
    """Маршрут по обученной таблице: в каждой клетке лучшее действие."""
    x, y = START
    path = [(x, y)]
    for _ in range(MAX_STEPS):
        a = max(range(4), key=lambda k: Q[x][y][k])
        x, y, r, done = step(x, y, a)
        path.append((x, y))
        if done:
            return path, True
    return path, False

Q = train()
path, ok = greedy_path(Q)
optimum = abs(START[0] - TARGET[0]) + abs(START[1] - TARGET[1])
print("Дошёл:", ok, "| шагов:", len(path) - 1, "| оптимум:", optimum)

#include <iostream>
#include <vector>
#include <array>
#include <random>
#include <algorithm>

const int W = 19, H = 10;          // поле в клетках
const int START_X = 1, START_Y = 8;
const int TARGET_X = 16, TARGET_Y = 1;

const double ALPHA = 0.5;          // скорость обучения
const double GAMMA = 0.95;         // дисконтирование будущей награды
const double EPS_START = 0.30;     // начальная доля случайных ходов
const double EPS_END = 0.01;
const int EPISODES = 400;
const int MAX_STEPS = 200;

const int DX[4] = {0, 0, -1, 1};   // вверх, вниз, влево, вправо
const int DY[4] = {-1, 1, 0, 0};

std::mt19937 gen(std::random_device{}());
std::uniform_real_distribution<> uni(0.0, 1.0);

// Q[x][y][a] — ожидаемая суммарная награда за действие a в клетке (x, y)
using QTable = std::vector<std::vector<std::array<double, 4>>>;

int best_action(const QTable& Q, int x, int y) {
    int k = 0;
    for (int a = 1; a < 4; ++a)
        if (Q[x][y][a] > Q[x][y][k]) k = a;
    return k;
}

// Среда: применяем действие, возвращаем награду; true — достигнута цель
bool env_step(int& x, int& y, int a, double& r) {
    x = std::min(std::max(x + DX[a], 0), W - 1);
    y = std::min(std::max(y + DY[a], 0), H - 1);
    if (x == TARGET_X && y == TARGET_Y) { r = 100.0; return true; }
    r = -1.0; return false;
}

int main() {
    QTable Q(W, std::vector<std::array<double, 4>>(H, {0, 0, 0, 0}));

    for (int ep = 0; ep < EPISODES; ++ep) {
        double eps = EPS_START + (EPS_END - EPS_START) * ep / (EPISODES - 1);
        int x = START_X, y = START_Y;
        for (int t = 0; t < MAX_STEPS; ++t) {
            int a = (uni(gen) < eps) ? (int)(uni(gen) * 4) : best_action(Q, x, y);
            int px = x, py = y;
            double r;
            bool done = env_step(x, y, a, r);
            double best_next = done ? 0.0
                : *std::max_element(Q[x][y].begin(), Q[x][y].end());
            Q[px][py][a] += ALPHA * (r + GAMMA * best_next - Q[px][py][a]);
            if (done) break;
        }
    }

    // жадный маршрут по обученной таблице
    int x = START_X, y = START_Y, steps = 0;
    bool ok = false;
    for (int t = 0; t < MAX_STEPS && !ok; ++t) {
        double r;
        ok = env_step(x, y, best_action(Q, x, y), r);
        ++steps;
    }

    int optimum = std::abs(START_X - TARGET_X) + std::abs(START_Y - TARGET_Y);
    std::cout << (ok ? "Дошёл" : "НЕ дошёл") << " за " << steps
              << " шагов (оптимум " << optimum << ")\n";
    return 0;
}

import pygame
import random
import sys

WIDTH, HEIGHT = 800, 600
CELL = 40                              # поле 20 x 15 клеток
COLS, ROWS = WIDTH // CELL, HEIGHT // CELL
AGENT_RADIUS = 4
GOAL_CELL = (COLS // 2, 1)             # цель в верхней части экрана, как в ГА
START_CELL = (COLS // 2, ROWS - 2)     # старт снизу экрана, как в ГА
ACTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]   # вверх, вниз, влево, вправо

ALPHA = 0.5        # скорость обучения
GAMMA = 0.95       # коэффициент дисконтирования
EPS_START, EPS_END = 0.30, 0.01
EPISODES = 400     # к этому эпизоду исследование затухает до минимума
MAX_STEPS = 300
fps = 60

Q = [[[0.0] * 4 for _ in range(ROWS)] for _ in range(COLS)]

def env_step(x, y, a):
    """Среда: применяем действие, возвращаем новое состояние и награду."""
    dx, dy = ACTIONS[a]
    nx = min(max(x + dx, 0), COLS - 1)
    ny = min(max(y + dy, 0), ROWS - 1)
    if (nx, ny) == GOAL_CELL:
        return nx, ny, 100.0, True
    return nx, ny, -1.0, False

def cell_center(cx, cy):
    return cx * CELL + CELL // 2, cy * CELL + CELL // 2

pygame.init()
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption("Q-обучение: шарик ищет цель")
font = pygame.font.SysFont(None, 24)
clock = pygame.time.Clock()

episode, steps, reached = 0, 0, 0
x, y = START_CELL

def draw_info(screen, eps):
    texts = [
        f"Эпизод: {episode}",
        f"Шагов в эпизоде: {steps}",
        f"Исследование eps: {eps:.2f}",
        f"Дошёл до цели: {reached} раз",
        f"Скорость симуляции (FPS): {fps}",
    ]
    for i, text in enumerate(texts):
        render = font.render(text, True, (255, 255, 255))
        screen.blit(render, (10, 10 + i * 22))

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()
        elif event.type == pygame.KEYDOWN:
            if event.key == pygame.K_v:
                fps = min(fps + 10, 240)
            elif event.key == pygame.K_d:
                fps = max(fps - 10, 1)

    # один шаг Q-обучения на кадр — движение шарика видно глазами
    eps = EPS_START + (EPS_END - EPS_START) * min(episode, EPISODES) / EPISODES
    if random.random() < eps:
        a = random.randrange(4)                      # исследование
    else:
        a = max(range(4), key=lambda k: Q[x][y][k])  # использование
    nx, ny, r, done = env_step(x, y, a)
    best_next = 0.0 if done else max(Q[nx][ny])
    Q[x][y][a] += ALPHA * (r + GAMMA * best_next - Q[x][y][a])
    x, y = nx, ny
    steps += 1
    if done or steps >= MAX_STEPS:
        if done:
            reached += 1
        episode += 1
        x, y = START_CELL
        steps = 0

    # отрисовка — та же сцена, что в версии с генетическим алгоритмом
    screen.fill((30, 30, 30))
    q_max = max(1.0, max(max(max(c) for c in col) for col in Q))
    for cx in range(COLS):                 # подсветка выученных клеток
        for cy in range(ROWS):
            q = max(Q[cx][cy])
            if q > 0:
                g = 40 + int(90 * q / q_max)
                pygame.draw.rect(screen, (0, g, 0),
                                 (cx * CELL + 1, cy * CELL + 1, CELL - 2, CELL - 2), 1)
    pygame.draw.circle(screen, (255, 0, 0), cell_center(*GOAL_CELL), 10)
    pygame.draw.circle(screen, (0, 255, 0), cell_center(x, y), AGENT_RADIUS)
    draw_info(screen, eps)
    pygame.display.flip()
    clock.tick(fps)

// Сборка (нужна установленная SFML):
//   g++ -O2 rl_shariki_sfml.cpp -o rl_shariki_sfml -lsfml-graphics -lsfml-window -lsfml-system
#include <SFML/Graphics.hpp>
#include <algorithm>
#include <random>
#include <string>

const int WIDTH = 800, HEIGHT = 600;
const int CELL = 40;                          // поле 20 x 15 клеток
const int COLS = WIDTH / CELL, ROWS = HEIGHT / CELL;
const float AGENT_RADIUS = 4.f;
const int GOAL_X = COLS / 2, GOAL_Y = 1;      // цель в верхней части экрана
const int START_X = COLS / 2, START_Y = ROWS - 2;

const int DX[4] = {0, 0, -1, 1};              // вверх, вниз, влево, вправо
const int DY[4] = {-1, 1, 0, 0};

const double ALPHA = 0.5;                     // скорость обучения
const double GAMMA_ = 0.95;                   // дисконтирование
const double EPS_START = 0.30, EPS_END = 0.01;
const int EPISODES = 400;
const int MAX_STEPS = 300;

double Q[COLS][ROWS][4] = {};

std::mt19937 gen(std::random_device{}());
std::uniform_real_distribution<> uni(0.0, 1.0);

int best_action(int x, int y) {
    int k = 0;
    for (int a = 1; a < 4; ++a)
        if (Q[x][y][a] > Q[x][y][k]) k = a;
    return k;
}

// Среда: применяем действие, возвращаем награду; true — цель достигнута
bool env_step(int& x, int& y, int a, double& r) {
    x = std::min(std::max(x + DX[a], 0), COLS - 1);
    y = std::min(std::max(y + DY[a], 0), ROWS - 1);
    if (x == GOAL_X && y == GOAL_Y) { r = 100.0; return true; }
    r = -1.0; return false;
}

int main() {
    sf::RenderWindow window(sf::VideoMode(WIDTH, HEIGHT), "Q-обучение: шарик ищет цель");
    unsigned fps = 60;
    window.setFramerateLimit(fps);

    sf::Font font;
    font.loadFromFile("C:/Windows/Fonts/arial.ttf");   // системный шрифт

    int episode = 0, steps = 0, reached = 0;
    int x = START_X, y = START_Y;

    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed)
                window.close();
            else if (event.type == sf::Event::KeyPressed) {
                if (event.key.code == sf::Keyboard::V) fps = std::min(fps + 10u, 240u);
                if (event.key.code == sf::Keyboard::D) fps = (fps > 10u) ? fps - 10u : 1u;
                window.setFramerateLimit(fps);
            }
        }

        // один шаг Q-обучения на кадр
        double eps = EPS_START + (EPS_END - EPS_START) *
                     std::min(episode, EPISODES) / double(EPISODES);
        int a = (uni(gen) < eps) ? int(uni(gen) * 4) : best_action(x, y);
        int px = x, py = y;
        double r;
        bool done = env_step(x, y, a, r);
        double best_next = done ? 0.0
            : *std::max_element(Q[x][y], Q[x][y] + 4);
        Q[px][py][a] += ALPHA * (r + GAMMA_ * best_next - Q[px][py][a]);
        ++steps;
        if (done || steps >= MAX_STEPS) {
            if (done) ++reached;
            ++episode;
            x = START_X; y = START_Y; steps = 0;
        }

        // отрисовка — та же сцена, что в версии с генетическим алгоритмом
        window.clear(sf::Color(30, 30, 30));

        double q_max = 1.0;
        for (int cx = 0; cx < COLS; ++cx)
            for (int cy = 0; cy < ROWS; ++cy)
                q_max = std::max(q_max, *std::max_element(Q[cx][cy], Q[cx][cy] + 4));
        for (int cx = 0; cx < COLS; ++cx)          // подсветка выученных клеток
            for (int cy = 0; cy < ROWS; ++cy) {
                double q = *std::max_element(Q[cx][cy], Q[cx][cy] + 4);
                if (q > 0) {
                    sf::RectangleShape cell(sf::Vector2f(CELL - 2.f, CELL - 2.f));
                    cell.setPosition(cx * CELL + 1.f, cy * CELL + 1.f);
                    cell.setFillColor(sf::Color::Transparent);
                    cell.setOutlineThickness(1.f);
                    cell.setOutlineColor(sf::Color(0, sf::Uint8(40 + 90 * q / q_max), 0));
                    window.draw(cell);
                }
            }

        sf::CircleShape goal(10.f);
        goal.setOrigin(10.f, 10.f);
        goal.setPosition(GOAL_X * CELL + CELL / 2.f, GOAL_Y * CELL + CELL / 2.f);
        goal.setFillColor(sf::Color::Red);
        window.draw(goal);

        sf::CircleShape agent(AGENT_RADIUS);
        agent.setOrigin(AGENT_RADIUS, AGENT_RADIUS);
        agent.setPosition(x * CELL + CELL / 2.f, y * CELL + CELL / 2.f);
        agent.setFillColor(sf::Color::Green);
        window.draw(agent);

        std::wstring info =
            L"Эпизод: " + std::to_wstring(episode) +
            L"\nШагов в эпизоде: " + std::to_wstring(steps) +
            L"\nДошёл до цели: " + std::to_wstring(reached) + L" раз" +
            L"\nСкорость симуляции (FPS): " + std::to_wstring(fps);
        sf::Text text(info, font, 18);
        text.setPosition(10.f, 10.f);
        text.setFillColor(sf::Color::White);
        window.draw(text);

        window.display();
    }
    return 0;
}