S>Лично я обудмывал как можно написать, но вижу такую проблему: алгоритм отбора лучших вариантов всегда получается сложнее, чем те варианты, которые он способен проверить на полезную сложность. И мы всегда упираемся в лимит сложности, который обусловлен алгоритмом самой проверки и среды развития.
S>Решена ли данная задача? Можно ли однозначно утверждать, что повышение сложности без лимита возможно?

Я думаю уже решена. Вот прямо сейчас проходит чемпионат по игре StarCraft, для которой сделали ИИ на нейросетях AlphaStar. Сама среда — фиксированная, и её сложность имеет однозначный предел. Выкинуть оттуда все красивости для людей, типа графики, звука, спецэффектов, и наверное влезет в 64к линейного и очень понятного кода. Программа которая запускает нейросети — тоже имеет фиксированный предел сложности, и тоже небольшой. А вот предела того сколько туда можно впихать нейронов и сколько времени их можно обучать стравливая разные нейросети друг с другом нету. Как и практически нет предела той сложности которую два ИИ могут друг-другу создать на карте, расставляя юниты триллионами разных вариантов. После одной-двух недель обучения эта штука в своей среде превосходит топовых людей на планете. Думаю рукопашное написание ИИ которых бы мог этому AlphaStar в сегодняшнем виде составить достойную конкуренцию практически нереально, т.е. далеко за пределами сложности создания StarCraft+движка для ИНС (иначе бы давно сделали). При этом продолжая соревноваться сама с собой AlphaStar будет продолжать расти, и если туда вкорячить условие создания новых слоёв нейросети, война уйдёт в совершенно непостижимые для людей уровни противостояния, типа как сейчас шахматные программы даже не жертвуют а пытаются казалось-бы подарить друг-другу фигуры (см. видео). И это простейшая война 1 на 1, загнать тысячи таких на гигантский "военный полигон", дать им простейшие средства коммуникации (типа передать один байт на вход противника), и наверняка через какое-то время они научатся и об альянсах договариваться, и вероломно предавать.

most hilarious Engine troll in Chess History?