Spiiin's blog

Попробовал решить задачу Джеймса Бонда-младшего с помощью openai.

Из интереса, где-то с 30 запросов (притом на русском языке) к 3-й версии ChatGPT получилось объяснить условие задачи. Часть запросов “отладочные”, чтобы понять, то, что пытается делать ИИ с моделью.

Примеры:
“Попробуй выполнить операции - сдвиг вправо 2-й строки, сдвиг вправо 3-й строки, сдвиг вправо 4-й строки. Примени каждую из них к начальной позиции”

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

Сдвиг вправо 2-й строки на одну позицию:

Copy code
11 12 13 14
24 21 22 23
31 32 33 34
41 42 43 44
Сдвиг вправо 3-й строки на одну позицию:

Copy code
11 12 13 14
21 22 23 24
34 31 32 33
41 42 43 44
Сдвиг вправо 4-й строки на одну позицию:

Copy code
11 12 13 14
21 22 23 24
31 32 33 34
44 41 42 43
В каждом случае соответствующая строка сдвинулась на одну позицию вправо, и последний элемент строки перешел на первое место.

“Теперь попробуй выполнить операцию «сдвиг 4го столбца вверх» по шагам”

Конечно! Вот пошаговое описание:

Выделяем 4-й столбец:
(11 12 13 14) (21 22 23 24) (31 32 33 34) (41 42 43 44)

14 24 34 44

Сдвигаем 4-й столбец вверх:
(11 12 13 14) (21 22 23 24) (31 32 33 34) (41 42 43 44)

14 24 34 44
11 21 31 41

Вставляем 4-й столбец обратно на своё место:
(11 12 13 14) (21 22 23 24) (31 32 33 34) (41 42 43 44)

12 13 14 44
22 23 24 21
32 33 34 31
42 43 11 41

Таким образом, получаем следующую конечную позицию.

Во втором шаге ошибка — столбец 14 24 34 44 при сдвиге вверх станет 24 34 44 14

Извините за ошибку в предыдущем ответе. Правильно будет так:

Выделяем четвертый столбец: (14, 24, 34, 44)
Сдвигаем его вверх: (24, 34, 44, 14)
Вставляем сдвинутый столбец обратно в исходный квадрат:
(11, 12, 13, 24)

(21, 22, 23, 34)

(31, 32, 33, 44)

(41, 42, 43, 14)

Ощущения — как от объяснения не очень умному школьнику, 4-я версия наверное быстрее уловит смысл. Но с момента, когда просишь переписать решение на Python, “школьник” безошибочно пишет функцию применения всех операций к исходной позиции, и поиск в ширину.

Дальше — интересней, ИИ может дописать оптимизацию с сортировкой с помощью функции оценки — предлагает эвклидово расстояние, а также манхеттенское расстояние и расстояние чебышева. C расстоянием эвклида он доходит до хорошей скорости выполнения. ИИ использовал для хранения списка открытых вершин PriorityQueue. Это даёт отличающийся от моей самой первой программы (которая использует для хранения list и сортирует его каждые N шагов) результат — находит путь в 10 шагов, а не 9.

ИИ предложил добавить в код замену функции оценки с эвклидова расстояния на манхеттенское (при этому утверждает, что для “пятнашек”, за которые он принял эту задачу, эта функция гарантированно даёт лучшую оценку, хотя я не стал бы ему доверять в таких утверждениях). С jupyter notebook обращение к ИИ за переписыванием кода может выглядеть примерно так:

//cell1, тут недописанный код
...
def find_astar_path(start, end, operations):
    queue = PriorityQueue()
    queue.put((0, [start]))
    visited = set()
  
    while not queue.empty():
        _, path = queue.get()
        vertex = path[-1]
        if vertex == end:
            print("hash ", len(visited), " queue ", queue.qsize())
            return path
        if tuple(vertex) not in visited:
            for operation in operations:
                possible_path = path + [operation(vertex)]
                queue.put((len(path) + euclide_distance(possible_path[-1], target), possible_path))
            visited.add(tuple(vertex))
    return None
...

//cell2
ss = "Rewrite function find_astar_path for using manhattan distance instead of euclide distance:\n"
ss += _i1 #обращение к тексту cell1

import os, openai

openai.api_key = os.getenv("OPENAI_API_KEY")

response = openai.Completion.create(
  model="text-davinci-003",
  prompt=ss,
  temperature=0.7,
  max_tokens=256,
  top_p=1,
  frequency_penalty=0,
  presence_penalty=0
)

Это позволило ИИ дойти до решения в 9 шагов, однако увеличило время выполнения с 2 до 10 секунд. Дальнейшие предложенные ChatGPT методы оптимизации — распараллеливание работы, построение предпросчитанной базы решений и переход на С++.

Ни одним из них он не справился сам. Мне не удалось заставить его реализовать свою наивную идею, или предложить её — “если мы знаем, что функции оценки не очень хорошие, то вместо использования очереди приоритетов на каждом шаге, проверим заодно еще группу решений с немного худшей оценкой и посмотрим, не нашлось ли там решения лучше”. Скорее всего, я просто не знаю “правильного” названия этого метода, поэтому пришлось дописать эту логику самому.

Интересно, что при этом я случайно обнаружил, что существует решение не в 9, а 8 шагов:

source = [1, 2, 2, 1, 3, 4, 4, 3, 3, 4, 4, 3, 2, 4, 4, 2]
target = [4, 3, 4, 2, 3, 1, 2, 4, 4, 2, 4, 3, 2, 4, 3, 1]

path:
    [1, 2, 2, 1, 3, 4, 4, 3, 3, 4 ,4, 3, 2, 4, 4, 2] source
    [1, 2, 2, 1, 3, 4, 4, 3, 3, 3, 4, 4, 2, 4, 4, 2] Right(2)
    [2, 2, 1, 1, 3, 4, 4, 3, 3, 3, 4, 4, 2, 4, 4, 2] Left(0)
    [2, 2, 1, 3, 3, 4, 4, 4, 3, 3, 4, 2, 2, 4, 4, 1] Down(3)
    [2, 4, 1, 3, 3, 2, 4, 4, 3, 4, 4, 2, 2, 3, 4, 1] Up(1)
    [4, 1, 3, 2, 3, 2, 4, 4, 3, 4, 4, 2, 2, 3, 4, 1] Left(0)
    [4, 1, 3, 2, 3, 2, 4, 4, 4, 4, 2, 3, 2, 3, 4, 1] Left(2)
    [4, 1, 4, 2, 3, 2, 2, 4, 4, 4, 4, 3, 2, 3, 3, 1] Down(2)
    [4, 3, 4, 2, 3, 1, 2, 4, 4, 2, 4, 3, 2, 4, 3, 1] Up(1) == target

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

Код: https://github.com/spiiin/james_bond_jr_problem/blob/main/james_bond_jr_openai.ipynb