user9671079

Если анализировать первый граф (орграф), то задача поиска наибыстрейшего выигрыша в игре сводится к задаче нахождения минимального пути на этом орграфе от начальной ноды A до выигрышной ноды Y. Этот минимальный путь способен находить алгоритм BFS, причём он это делает за O(V+E) (количество вершин + количество рёбер).

Также мы понимаем, что можем найти компоненты сильной связности на этом орграфе, и если компонента — сток и в ней нет выигрышной ноды Y, то все другие ноды этой компоненты тоже не выигрышные.

С точки зрения динамического программирования ускорить поиск BFS можно, если мы знаем, что у ноды Y (поиск от обратного), как и у следующих перед ней нод, количество рёбер, входящих в неё, не особо велико; тогда часть нод можно явно отсечь.

Очевидно, что алгоритм BFS на орграфе — это в каком-то смысле перебор вариантов, и проблемы начинаются, когда рёбер и нод становится слишком много (как в кубике Рубика или пятнашках). BFS найдёт путь и выигрыш для них, но будет делать это очень долго. Нужен способ отсечения ненужных путей (выходных рёбер) из ноды состояний игры. И тогда возникает действительно важный вопрос: а есть ли какая-то надструктура, которая порождает этот орграф игры, и можно ли этот орграф как-то сжать или получить через конечные правила?

Важная особенность орграфа игры в том, что из него в принципе не всегда можно установить наличие выигрышной стратегии даже через BFS. Для примера можно привести такую игру. Пусть есть лягушка, которая прыгает по числовой прямой на +2 и −2 шага от нулевой ноды. Выигрыш — если лягушка попадёт на ноду 13. Если мы построим орграф игры и попытаемся через BFS найти, можно ли попасть на ноду 13, то мы уйдём в бесконечный поиск выигрышной ноды 13. Причём мы даже не сможем сказать, что в ноду 13 невозможно попасть в принципе, хотя бы потому, что в неё можно попасть из нод 11 и 15 и т. д. Важно, что эта задача решается элементарно через описание правил игры и использование на этих правилах квантора всеобщности, логики предикатов и двух видов доказательств по индукции. То есть мы можем доказать конечным доказательством, что лягушка никогда не попадёт в ноду 13, а значит, выигрыш невозможен. Соответственно, можем ли мы утверждать, что математическая теория и логика предикатов важнее в игре на одного в целом, чем собственно анализ орграфа игры?

...

Эту таблицу можно назвать кэш-функцией. Она позволяет ускорить вычисления через хэш-фукнцию или через прямую адресацию к памяти. Причем время обращения 0(константа).

Эта кэш-функция не требует многопоточности для своего выполнения , даже если вычисление из аргументов результата использовало активно многопоточность (хоть и требует много памяти).

Соответствеенно , если мы пока исключаем требование для кеш-функции большого количества памяти а смотрим только на скорость выполнения функции , то параллельность бы использовалсь только для добычи новой информации и изучении новых алгоритмов - именно ее параллельность могла бы ускорить.

В научном сообществе есть исследователи (те, которые строят доказательства) и есть рецензенты научных журналов (те, которые проверяют доказательства). То есть в каком-то смысле научное сообщество можно было бы считать над-агентом в смысле ИИ — сообществом агентов, выполняющих одну задачу (доказательство гипотезы Римана). Если мы проанализируем сходство этого над-агента с моделью ИИ, о которой я писал, то роль сознания в нём выполняют учёные-исследователи: они ищут доказательства и общаются между собой, обмениваются промежуточными леммами (или не общаются) для того, чтобы его найти. Рецензенту же не обязательно в этом смысле обладать сознанием — его может заменить алгоритм проверки доказательства (к примеру, Lean), хотя это немного спорный вопрос. В этом смысле, если у рецензента, как мы считаем, есть сознание и у учёного-исследователя есть сознание, то вроде бы есть асимметрия: рецензент может выполнять задачу, не требующую сознания , которая вроде бы должна выполняться задачей, требующей над-агента (над-сознания).

Ещё интереснее вот что. Теоретически роль научного сообщества может выполнить только один математик в своём сознании — просто это будет очень долго. Он может как придумывать доказательства гипотезы Римана, так и сам их рецензировать (если внутренний рецензент достаточно честный). То есть это над-сознание может поместиться в сознание одного человека (если он этим будет заниматься тысячу лет). Соответственно, граница между над-сознанием и сознанием этого человека должна быть какая-то другая, чем просто иерархическая вложенность.

В нашей обычной жизни то, сколько человек будет населять какую-то территорию, было связано (до урбанизации) обычно с тем, сколько земли нужно для того, чтобы этого человека прокормить. Например, охотник-собиратель в Сибири прокормится с 10 квадратных километров. А для крестьянина в Китае нужно всего лишь 10 соток, чтобы прокормиться. Разница по площади — в 10 000 раз.

Соответственно, мы понимаем, что количество рабочих мест в экономике определяется двумя соотношениями. Первое соотношение — это то, что невозможно объединить в одну функцию по физическим причинам: один медведь не может контролировать всю Сибирь, потому что у него не хватит скорости движения для этого контроля (пока он бегает, малина растёт). Второе соотношение — это то, что невозможно объединить алгоритмически: отдел рекламы Metro в Барнауле может иметь разную входящую и исходящую информацию с отделом рекламы Metro в Чите, потому что есть некая информация, которая в этих местах отличается, — местная специфика.

Тут мы приходим к мысли из предыдущего поста. По сути, именно то, что в математике существуют NP-задачи, решение которых можно получить только перебором, и заставляет системы — будь то интеллект или эволюция — создавать множество параллельных потоков для поиска решений. Например, генетическое разнообразие в природе или тот факт, что в R&D-отделах компаний постоянно создаются и закрываются направления: за каждым обычно стоит гипотеза, которую нужно проверить параллельно с другими. Соответственно, разнообразие мира — это следствие вычислительной сложности поиска оптимальных решений. И довольно интересно, что если бы P = NP и оптимальные решения можно было находить быстро на практике, то потребность в параллельном поиске — а значит, и в разнообразии — резко бы сократилась.

В этом смысле искусственный интеллект, который я описал, тоже ограничивает изменение своей модели мира требованием того, чтобы программа, которая описывает эту самую модель, генерировала максимально подробно файл истории входов. С одной стороны, ясно, что в этом ИИ есть явный запрет на изменение определённых областей памяти программы (нельзя переписать логику модуля предсказаний), и это явное ограничение «сознания» через права на запись в память (не каждый нейрон имеет право на связи с любым другим нейроном). С другой стороны, ясно, что это внутреннее ограничение на произвольное изменение логической картины мира без участия логики — это программное ограничение другого вида. Оно сходно с парольным ограничением (чтобы зайти на аккаунты сайтов, нужно использовать пароль, например) или задачным ограничением — чтобы сдать экзамен, нужно найти правильный ответ. Так же и с логической картиной мира — чтобы её поменять, нужно найти новую логическую картину мира, объясняющую больше, чем старая. И в этом смысле интересно: может ли сознание (если это действительно так) как-то взломать эту логическую систему мира и что вообще заставило бы систему поиска модели мира захотеть что-то взломать?

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

Желание новизны заставляет нас ходить на премьеры фильмов в кинотеатрах и покупать новые игры. И внутри игр разработчики всё время должны проектировать уровни и игры так, чтобы эта новая информация поступала к игрокам, а так как во времени эта новая информация должна быть новой относительно старой информации, то разработчикам всё время приходится усложнять задачи в играх, но делать это так, чтобы это было и не слишком сложно, и не слишком просто. Очевидно, структура того, что мы называем новой информацией, имеет прямое отношение к математике. В математике существует много разных видов получения новой информации, но вот четыре основных: 1) случайность, 2) длинные последовательности, 3) комбинаторика, 4) алгоритмы, которые эмулируют хаотичные системы.

Примеры того, как случайность постоянно даёт новую информацию игроку, можно найти даже в самых простейших увлекательных играх. К примеру, игры тетрис, змейка или пинг-понг. В тетрисе случайность — это то, какая фигура появится следующей; по сути, эта случайность постоянно кормит игрока неожиданностью, которая и обращает внимание его любопытства и желания новой информации. К таким же играм можно отнести рыбалку (любительскую), рулетки и казино. Игроки строят теории того, как действует случайность, и пытаются найти закономерности (хотя их там нет), но игра всё время очевидно их удивляет — потому что сложно построить модель случайности.

Примерами длинных последовательностей в играх может выступать проектирование таких уровней игры, как в Марио, или карты в таких играх, как Skyrim. По сути, то, как расположены объекты на этих картах или уровнях, постоянно удивляет игрока новыми открытиями и архитектурными решениями. Длинная последовательность может быть сгенерирована и случайной, и не случайной процедурной генерацией — но бывает, игроки это любят (Minecraft), а бывает, не любят (The Elder Scrolls II: Daggerfall). Интересно также, что и запоминание этих длинных последовательностей дарит игроку удовольствие. А также интересна связь этих последовательностей с музыкой — основная теория музыки в том, что музыка, чтобы быть хорошей, должна удивлять слушателя каждый новый момент времени, но при этом повторять часть старого мотива, чтобы слушатель не запутался.

Новая информация из комбинаторики связана с такими играми, как шахматы, пятнашки, кубик Рубика. Их существование связано с математической теорией групп и игр. Они дают в целом много удовольствия, но только если есть предрасположенность к играм с длинными последовательностями действий до выигрыша или есть сопутствующие источники удовольствия при их изучении. Например, игра Dota 2. Начальное удовольствие от игры всё-таки связано со скоростью реакции в поединках между героями, но если двигаться ближе к среднему уровню понимания игры, нужно запоминать и находить хорошие комбинации героев, предметов и спеллов в огромном комбинаторном пространстве (больше ста героев, больше ста предметов и по 30–40 способностей у героя). То есть новую информацию игрок тут получает потому, что в таких играх есть огромные математические структуры и есть мотивация их изучения (чем больше её знаешь, тем больше выигрываешь).

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

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