Наука о данных

Как собрать кубик Рубика с помощью генетических алгоритмов

30.09.2020

Введение

В качестве эксперимента я решил собрать кубик Рубика с помощью генетических алгоритмов (ГА). Их основная концепция заключается в том, чтобы найти решение путем имитации естественного отбора и эволюции. В целом, нам потребуется выполнить следующие шаги:

Создать популяцию вариантов решений (обычно они генерируются случайным образом).
Определить показатель пригодности для оценки того, насколько близок вариант к достижению цели.
Оценить все варианты решения и отсортировать их по степени пригодности.
Определить стратегию развития популяции. Обычно сохраняются лучшие исполнители и вносятся случайные изменения, например небольшое изменение варианта решения или объединение двух решений.
После появления новой популяции продолжать очистку и повторять шаги до нахождения решения (возврат к шагу 3).
Порой «генетического пула» недостаточно, чтобы найти решение. В этом случае наиболее распространенный подход — уничтожить популяцию и начать с начала.

Но прежде чем перейти к деталям реализации, рассмотрим базовую теорию кубика Рубика.

Нотация кубика Рубика

Вращение отдельных букв выполняется по часовой стрелке.
Вращения, обозначенные штрихом, выполняются против часовой стрелки.
Чтобы определить направление вращения, нужно посмотреть прямо на указанную сторону. Например, для D и D’ представьте, что перед вами нижняя сторона.
U2 аналогично двум вращениям U.
Обратите внимание, что в некоторых случаях (x, y, z) вращается весь куб, а не только одна сторона.

Реализация кубика Рубика

Грани

Для представления кубика есть множество подходов, но я решил воспользоваться простым словарем, содержащим шесть матриц numpy 3×3 (по одной для каждой грани):

self.faces = {
    FRONT: np.full((3, 3), GREEN),
    LEFT: np.full((3, 3), ORANGE),
    RIGHT: np.full((3, 3), RED),
    TOP: np.full((3, 3), WHITE),
    BOTTOM: np.full((3, 3), YELLOW),
    BACK: np.full((3, 3), BLUE),
}

Для передней грани интуитивно ясно, что [0, 0] будет левым верхним углом. Однако значения back[0, 0], left[0, 0] и bottom[0, 0] зависят от того, с каком стороны вы смотрите на куб. Изображение ниже поможет избежать путаницы. Позиция [0, 0] обозначена фиолетовым. Схема согласована с тем, как определяется способ вращения.

Вращения

Numpy включает множество полезных методов, таких как rot90 и flip, которые отлично подходят для реализации вращения куба. В качестве примера проанализируем R:

Как видите, сначала мы выполняем вращение на матрице правой грани, а затем меняем значения нижней, передней, верхней и задней матриц соответственно.

def R(self):
    self.faces[RIGHT] = np.rot90(self.faces[RIGHT], axes=CLOCKWISE)
    # __swap_y получает четыре значения из трехзначных кортежей
    # Каждый такой кортеж состоит из:
    # - index 0 = грань
    # - index 1 = столбец
    # - index 2 = перевернутые значения (булевы)
    #
    # Это означает: 
    # - переместить столбец "bottom" 2 в столбец "front" 2
    # - переместить столбец "front" 2 в столбец "top" 2
    # - переместить столбец "top" 2 в столбец "back" 0, перевернув значения
    # - переместить столбец "back" 0 в столбец "bottom" 2, перевернув значения
    self.__swap_y((BOTTOM, 2, False), (FRONT, 2, False), (TOP, 2, True), (BACK, 0, True))

Единственная сложность заключается в том, что при работе с обратной стороной необходимо инвертировать значения, как показано на изображении:

TOP[0, 2] -> BACK[2, 0]
TOP[1, 2] -> BACK[1, 0]  
TOP[2, 2] -> BACK[0, 0]

Полную реализацию можно посмотреть в исходном коде.

Генетический алгоритм

Создание популяции

Как было сказано выше, для этой симуляции нужно создать популяцию кубика Рубика. Мы воспользуемся следующим скремблом, полученным с помощью этого онлайн-скремблера.

D’ B2 D2 L2 U’ L R’ F L2 R2 U’ L2 B’ L D’ B2 R2 B’ R F U2 R B2 F’ L’ B2 L2 R F2 L’

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

После скремблирования всех кубиков мы рандомизируем их, выполнив два случайных хода, таких как R, L’, U, D2 и т. д.

# Создание популяции
cubes = []
for i in range(0, self.population_size):
    cube = Cube()
    cube.execute(scramble)
    # Рандомизация
    cube.execute(self.__rnd_single_move())
    cube.execute(self.__rnd_single_move())
    cubes.append(cube)

Функция пригодности

Напоминаю: с помощью функции пригодности определяются наиболее близкие к решению варианты. Один из подходов — подсчитать количество правильно размещенных частей куба. Однако подсчетов будет много. Например, угол следует считать за одну часть, хотя он взаимодействует с тремя гранями. Вместо этого мы можем подсчитать стикеры. Подсчет потерянных стикеров проще, поэтому цель — минимизировать их количество. Другими словами, чем меньше, тем лучше, и если пригодность равна нулю, значит куб решен.

def __calculate_fitness(self):
    misplaced_stickers = 0

    for k, face in self.faces.items():
        # Центры закреплены в кубике Рубика
        center = face[1, 1]

        for i in range(0, 3):
            for j in range(0, 3):
                if face[i, j] != center:
                    misplaced_stickers += 1

    return misplaced_stickers

Стратегия эволюции

Мои первые попытки включали случайную генерацию ходов (R, L, U и т. д.), но эта стратегия не принесла результатов. Чтобы понять причину, посмотрим, что происходит при выполнении одного вращения:

В этом случае изменилось положение 20 стикеров (по 3 на каждой стороне + 8 на верхней грани). У куба 54 стикера, поэтому при каждом вращении состояние куба изменяется на 37%, и это слишком много, чтобы применить эволюционный подход. Что же делать? Можем ли мы найти способ внести меньшие изменения? Да! Для этой цели можно использовать хорошо известные алгоритмы кубика Рубика. Например, R U’ R U R U R U’ R’ U’ R2 перемещает только три стикера, как показано на изображении ниже.

F’ L’ B’ R’ U’ R U’ B L F R U R’ U также вносит небольшое изменение (перестановка двух ребер на верхнем слое).

Вот список всех перестановок, которые мы будем использовать:

PERMUTATIONS = [
    # Перестановка двух ребер: грань U, нижнее и правое ребра
    "F' L' B' R' U' R U' B L F R U R' U",
    # Перестановка двух ребер: грань U, нижнее и левое ребра
    "F R B L U L' U B' R' F' L' U' L U'",
    # Перестановка двух углов: грань U, нижний левый и нижний правый
    "U2 B U2 B' R2 F R' F' U2 F' U2 F R'",
    # Перестановка трех углов: грань U, нижний левый и верхний левый
    "U2 R U2 R' F2 L F' L' U2 L' U2 L F'",
    # Перестановка трех углов: грань F, верхний, правый, нижний
    "U' B2 D2 L' F2 D2 B2 R' U'",
    # Перестановка трех центров: грань F, верхний, правый левый
    "U B2 D2 R F2 D2 B2 L U",
    # Грань U: нижний угол <-> правый угол, нижний правый угол <-> верхний правый угол
    "D' R' D R2 U' R B2 L U' L' B2 U R2",
    # Грань U: нижний угол <-> правый угол, нижний правый угол <-> левый правый угол
    "D L D' L2 U L' B2 R' U R B2 U' L2",
    # Грань U: верхний угол <-> нижний угол, нижний левый угол <-> верхний правый угол
    "R' U L' U2 R U' L R' U L' U2 R U' L U'",
    # Грань U: верхний угол <-> нижний угол, нижний правый угол <-> верхний левый угол
    "L U' R U2 L' U R' L U' R U2 L' U R' U",
    # Перестановка трех углов: грань U, нижний правый, нижний левый и верхний левый
    "F' U B U' F U B' U'",
    # Перестановка трех углов: грань U, нижний левый, нижний правый и верхний правый
    "F U' B' U F' U' B U",
    # Перестановка трех ребер: нижняя часть грани F, верхняя часть грани F, верхняя часть грани B
    "L' U2 L R' F2 R",
    # Перестановка трех углов: верхняя часть грани F, верхняя часть грани B, нижняя часть грани B
    "R' U2 R L' B2 L",
    # Перестановка H: грань U, меняет местами ребра по горизонтали и вертикали
    "M2 U M2 U2 M2 U M2"
]

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

Продвигаем лучших исполнителей к следующему поколению без изменений (в ГА этот процесс называется элитарностью).
Отбрасываем оставшиеся варианты решения и заменяем их следующим образом:
- получаем копию случайного лучшего исполнителя;
- случайным образом добавляем перестановки или вращения к копии;
- заменяем вариант решения новой копией.

# Цель - минимизировать функцию пригодности
# 0 означает, что куб собран
    for i in range(0, len(cubes)):
    if cubes[i].fitness == 0:
        print("Solution found")
        print(f"{cubes[i].get_algorithm_str()}")
        return

    # Элитарность: лучшие исполнители переходят к следующему поколению без изменений
        if i > self.elitism_num:
        # Копируем случайный куб с лучшим исполнителем
        self.__copy(cubes[i], cubes[rnd.randint(0, self.elitism_num)])
        evolution_type = rnd.randint(0, 5)

        if evolution_type == 0:
            cubes[i].execute(self.__rnd_permutation())
        elif evolution_type == 1:
            cubes[i].execute(self.__rnd_permutation())
            cubes[i].execute(self.__rnd_permutation())
        elif evolution_type == 2:
            cubes[i].execute(self.__rnd_full_rotation())
            cubes[i].execute(self.__rnd_permutation())
        elif evolution_type == 3:
            cubes[i].execute(self.__rnd_orientation())
            cubes[i].execute(self.__rnd_permutation())
        elif evolution_type == 4:
            cubes[i].execute(self.__rnd_full_rotation())
            cubes[i].execute(self.__rnd_orientation())
            cubes[i].execute(self.__rnd_permutation())
        elif evolution_type == 5:
            cubes[i].execute(self.__rnd_orientation())
            cubes[i].execute(self.__rnd_full_rotation())
            cubes[i].execute(self.__rnd_permutation())

Если вы читали исходный код, то заметили такое понятие, как ориентация. По причинам, которые я объясню ниже, лучшие результаты принесло разделение полных вращений куба на две группы: вращения и ориентации:

ROTATIONS = ["x", "x'", "x2", "y", "y'", "y2"]
ORIENTATIONS = ["z", "z'", "z2"]

Вернемся к перестановкам — в списке у нас есть только два варианта, которые изменяют значения двух ребер:

# Перестановка двух ребер: грань U, нижнее и правое ребра
"F' L' B' R' U' R U' B L F R U R' U",

# Перестановка двух ребер: грань U, нижнее и левое ребра
"F R B L U L' U B' R' F' L' U' L U'",

Но как поменять местами значения двух ребер нижнего или заднего слоя? Один из вариантов — охватить все возможные перестановки, а не только две предыдущие. Однако работы будет много и риск возникновения ошибок слишком велик. Поэтому в стратегии эволюции и появляются вращения и ориентации. Таким образом, если нам нужно поменять местами два ребра на задней грани, вращения и ориентации будет достаточно, чтобы переместить куб в позицию, которая обрабатывается доступными перестановками.

Для полноты картины добавлю, что в теории ГА есть две важные концепции: мутация и кроссовер. Мутация предполагает изменение части существующего решения. Например:

R L U2 D B’ R
R R U2 D B’ R

В данном случае добавление ходов — это своего рода мутация.

Кроссовер же предполагает выбор двух возможных решений и создание потомства путем объединения их «генов». В случае с кубиком Рубика он может выглядеть так:

Родитель 1 : R L U2 D B’ R
Родитель 2 : F B R2 L U’ D
Ребенок : R L U2 L U’ D

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

Что касается параметров, то с этой конфигурацией я получил хорошие результаты. Они означают, что в популяции будет 500 кубиков, 50 из которых мы продвинем к следующему поколению без изменений. Следовательно, оставшиеся 450 кубиков будут заменены мутацией, примененной к 50 случайным лучшим исполнителям. Если через 300 поколений решение не будет найдено, то придется уничтожить популяцию и начать заново (и так до 10 раз).

population_size = 500
elitism_num = 50
max_generations = 300
max_resets = 10

Если вы захотите поэкспериментировать с этими значениями, учтите, что меньшая численность популяции хоть и ускорит поколения, но также повысит риски застрять на месте из-за нехватки случайности в популяции.

Запуск

python -m src.solver

Проверим правильность решения с помощью симулятора куба:

Получилось! А запустив программу несколько раз, вы заметите, что решения будут различны.

Хорошее ли это решение?

Чтобы ответить на этот вопрос, понадобится больше теории. Здесь можно прочитать целую статью об этом, но вот самый важный вывод:

«Команда исследователей (при поддержке Google) решила каждую позицию кубика Рубика и установила, что каждая из них занимает не более двадцати ходов».

В предыдущем запуске решение состояло из 276 ходов, что далеко от оптимального. Однако имейте в виду, что в данном случае перестановки вносили постепенные изменения в очень маленькие части куба в качестве требования для работы ГА, поэтому это не очень справедливое сравнение. Для нашего подхода более близки методы, используемые для решения вслепую, а такие решения нередко находятся в диапазоне сотен ходов. Поэтому наше решение, возможно, не такое уж и плохое. ?

Итак, какие же недостатки у ГА:

Трудность нахождения лучшего решения. Обычно генетический алгоритм находит «достаточно хорошее» и продолжает работать над ним.
Настройка параметров может потребовать много времени и экспериментов.
Результаты недетерминированы. Вы получите разные решения, и время на их поиск во многих случаях может существенно различаться.

Заключение

Это был интересный проект, а результаты получились вполне удовлетворительными. Если вы хотите поэкспериментировать или улучшить программу, то ловите исходный код на GitHub.

Благодарим за чтение!

Как собрать кубик Рубика с помощью генетических алгоритмов

Введение

Нотация кубика Рубика

Реализация кубика Рубика

Грани

Вращения

Генетический алгоритм

Создание популяции

Функция пригодности

Стратегия эволюции

Запуск

Хорошее ли это решение?

Заключение

Читайте также

Миграция REST API на GraphQL

Реальные возможности WASM

redis-hawk: детализированное отслеживание и контроль развертывания Redis

Тесты

Насколько хорошо вы знаете Python?

Хорошо ли вы разбираетесь в структурах данных и алгоритмах?

Насколько хорошо вы знакомы с основами C?