Что точнее/быстрее - нейросети или обычные алгоритмы?

[grizzly]

mustitz в сообщении #1278665 писал(а):

Человек это животное?

Должно быть "от других животных". Подловили :)

А в остальном Вы вполне ответили на мой вопрос, спасибо. Даже если наши оценки разнятся, я надеюсь Вы поняли, какие меня интересуют критерии.

[Sonic86]

Dmitriy40 в сообщении #1276229 писал(а):

Человек не смог полностью формализовать критерии ... выбора лучшего хода в шахматах, потому в частности и ГА тут человеку не соперники, а НС справилась лучше, не идеально, но лучше. Думаю этим надо гордиться, что мы смогли придумать и создать такой совершенный механизм себе в помощь (как к примеру и радиотехнику), а не комплексовать что породили дьявола.

Меня больше интересовала своего рода "неоптимальность" построения алгоритма. Люди не смогли устроить некий "детерминированный", "классический" перебор алгоритмов для поиска лучшего алгоритма игры, зато смогли запустить самообучение нейросети и потратить кучу тактов работы ЦП на то, чтобы в ней найти лучший алгоритм, но в закодированном виде. Причем извлекать его оттуда, по-видимому, никто не собирается.
Представьте, если они так начнут искать, например, группу рациональных точек на эллиптических кривых! Конечно, это сильно фантастично, но это выглядело бы именно как бессмыслица.
Это примерно как ситуация, когда построили компьютерное доказательство теоремы о 4-х красках - доказательство строгое, но часть народа считала его "некошерным", только еще хуже: там доказательство можно было бы хотя бы читать, а здесь алгоритм спрятан внутри нейросети.

mustitz в сообщении #1278612 писал(а):

Победа AlphaZero над Stockfish нелёгкая и, честно говоря, под вопросом. В целом нужен матч, в котором бы команда Stockfish сама бы настроила железо как считает нужным.

Согласен.
Но "рекламный" матч до моего мозга дошел.

mustitz в сообщении #1278612 писал(а):

Опять же, проведём мысленный эксперимент. Если таблицы Налимова, где каждой позиции прописана оценка: ничья или сколько ходов до мата.... Сможет ли нейросеть добиться безошибочной игры в этом классе позиций?

Я думаю, что не сможет, причем нейросеть при этом должна кушать сильно больше ресурсов, чем поиск по таблицам, при условии, что в поиске по таблицам ничего "нельзя сжать". Здесь уже нужен критерий сравнения ресурсоемкости хотя бы по двум параметрам: число операций + объем памяти. А я его еще так и не узнал Ну еще играло бы роль число ничейных партий

mustitz в сообщении #1278665 писал(а):

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

Я плохой шахматист, но мне казалось, что идеальная оценочная функция в шахматах не д.б. настолько страшная, чтобы плохо влазить в сознание исследователя. Я сильно заблуждаюсь?
Условно говоря, пусть $n$ - число ходов от начала игры, $L(n)$ - минимальная длина оценочных функций позиции в некотором выбранном ЯП (пофиг в каком), при использовании которого программа не проигрывает первые $n$ ходов в любой партии (против идеального противника). Мне представляется, что $L(n)=O(n^a)$ для какого-то $a$, я ошибаюсь? Для конечных переборных игр с максимальным коэффициентом ветвления $k$ $L(n)=O (k^n)$ (если просто выписывать в коде полный перебор начала игры), т.е. это неинтересный случай. Не хотелось бы, чтобы шахматы оказались в этом смысле неинтересной игрой.

(Оффтоп)

mustitz в сообщении #1278665 писал(а):

Человек это животное?

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

[Dmitriy40]

Sonic86 в сообщении #1278726 писал(а):

Не хотелось бы, чтобы шахматы оказались в этом смысле неинтересной игрой.

Что значит не хотелось бы? Разве может быть иначе? Количество фигур ограничено, количество клеток тоже, а значит в любой позиции ограничено сверху и количество вариантов допустимых ходов. Взяв максимум этого количества для всех возможных позиций за $k$ получим ровно вашу оценку. Да, лишь сверху, ну и что, коэффициент то может исчезнуть в $O()$.

Sonic86 в сообщении #1278726 писал(а):

а здесь алгоритм спрятан внутри нейросети

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

[Sender]

Dmitriy40 в сообщении #1278752 писал(а):

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

Вот, кстати, интересно. Есть несколько вдоль и поперёк изученных стандартных эндшпилей: мат ферзём, ладьёй, двумя слонами и т.д. Уж их-то точно можно хорошо алгоритмизировать. Интересно бы взглянуть, как выглядят формальные алгоритмы для оптимальной игры в этих случаях.

[mustitz]

Sender в сообщении #1278844 писал(а):

Вот, кстати, интересно. Есть несколько вдоль и поперёк изученных стандартных эндшпилей: мат ферзём, ладьёй, двумя слонами и т.д. Уж их-то точно можно хорошо алгоритмизировать. Интересно бы взглянуть, как выглядят формальные алгоритмы для оптимальной игры в этих случаях.

Что значит «оптимальная игра»? С точки зрения результата нам надо поставить мат, и в общем случае неважно, сделаем мы это за 20 ходов или за 30. Больше победы ничего не дадут.

Если стоит задача заматовать за минимальное число ходов, то ретроанализ + построение таблиц. Например, идём на сайт shredderchess.com, нажимаем кнопку Input FEN, вводим 6k1/5n2/8/8/8/5n2/1RK5/1N6 w - - 0 1 и наслаждаемся матом в 262 хода. Есть ещё сайт таблиц Ломоносова, там уже мат в 549 ходов.

-- 26.12.2017, 12:41 --

Sonic86 в сообщении #1278726 писал(а):

Условно говоря, пусть $n$ - число ходов от начала игры, $L(n)$ - минимальная длина оценочных функций позиции в некотором выбранном ЯП (пофиг в каком), при использовании которого программа не проигрывает первые $n$ ходов в любой партии (против идеального противника). Мне представляется, что $L(n)=O(n^a)$ для какого-то $a$, я ошибаюсь? Для конечных переборных игр с максимальным коэффициентом ветвления $k$ $L(n)=O (k^n)$ (если просто выписывать в коде полный перебор начала игры), т.е. это неинтересный случай.

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

[Sender]

mustitz в сообщении #1278855 писал(а):

С точки зрения результата нам надо поставить мат, и в общем случае неважно, сделаем мы это за 20 ходов или за 30. Больше победы ничего не дадут.

Победу могут и не дать, если правило 50 ходов будет нарушено. По-моему, задача о мате за минимальное количество ходов вполне естественна, под «оптимальной игрой» я подразумевал именно её. Я говорю о более компактном описании алгоритма, чем с помощью таблиц эндшпилей. Например, в виде некоей функции, вычисляющей следующий ход по заданной позиции. Есть и более простые случаи, чем мат в 549 ходов, скажем, мат ферзём при оптимальной игре ставится максимум через 10 ходов.

[mustitz]

Sender в сообщении #1278862 писал(а):

Победу могут и не дать, если правило 50 ходов будет нарушено. По-моему, задача о мате за минимальное количество ходов вполне естественна, под «оптимальной игрой» я подразумевал именно её.

Есть разные метрики построения таблиц Налимова. Например, DTZ50 (минимизируем расстояние до обнуления счётчика 50-ти ходов с учётом правила 50 ходов). Каждая из них даст свой вариант «оптимальной игры». Как я понял, Вам интереснее всего метрика DTM50, она тоже доступна. Просто не так интересна, потому как правило 50-ти ходов это всё-таки немного искусственное ограничение, чтобы не затягивать игру людей :)

[Sender]

mustitz в сообщении #1278871 писал(а):

Как я понял, Вам интереснее всего метрика DTM50, она тоже доступна.

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

[mihaild]

Sender, эта стратегия может привести к проигрышу: мы ставим крестик в $(1, 1)$, противник нолик в $(0, 0)$, мы крестик в $(0, 2)$, противник нолик в $(2, 0)$, мы крестик в $(0, 1)$, противник нолик в $(2, 0)$ и из этой позиции противник может выиграть при любых наших действиях.
Но не очень понятно, к чему была эта стратегия:)

Вообще про таблицы Налимова интересны два вопроса:
-сумеет ли AlphaZero выиграть в каждой из выигрышных позиций, и свести к ничьей каждую ничейную (я подозреваю, что да)
-можно ли обучить нейросеть выигрывать в каждой из них за оптимальное число ходов

[mustitz]

mihaild в сообщении #1278904 писал(а):

Вообще про таблицы Налимова интересны два вопроса:
-сумеет ли AlphaZero выиграть в каждой из выигрышных позиций, и свести к ничьей каждую ничейную (я подозреваю, что да)
-можно ли обучить нейросеть выигрывать в каждой из них за оптимальное число ходов

Большинство позиций — да. Но заковыристые позиции только в случае, если сеть учить на этом классе позиций, и то врядли. Если учить из начальной позиции, то возникающее окончание будет возникать недостаточно часто для обучения, имхо. Да, перебор монте-карло лучше подходит для анализа таких позиций, но всё равно вариантов много, логики и закономерностей мало. С другой стороны никто не запрещает AlphaZero использовать таблицы Налимова в практической игре, это бы однозначно усилило бы её.

Нейросеть можно обучить аппроксимировать любую функцию. Вопрос в том, что это будет жутко неэффективно и долго.

[Sender]

mihaild в сообщении #1278904 писал(а):

мы ставим крестик в $(1, 1)$, противник нолик в $(0, 0)$, мы крестик в $(0, 2)$, противник нолик в $(2, 0)$, мы крестик в $(0, 1)$

Вообще-то, если в $(0,0)$ и $(2,0)$ стоят нолики с угрозой $(1,0)$, стратегия прямо предписывает ставить крестик в $(1,0)$. И потом, у вас почему-то 2 нолика в $(2,0)$. В сущности, я привёл её, чтобы продемонстрировать, как можно задать стратегию компактнее, чем таблицей эндшпилей.

[mihaild]

И правда. Что-то я сегодня много бреда несу

[mustitz]

Ну... в крестики-нолики таки можно обдурить: $(1,1)$ — $(0,0)$ — угроз нету, случайный ход — $(0,1)$ — $(2,1)$ — угроз нету, случайный ход — $(0,2)$ — $(2,0)$ вилка.

Еще вопрос только в том, что в правила оценки уже добавлено просмотр варианта на ход вперёд.

[Dmitriy40]

Sender в сообщении #1278844 писал(а):

Вот, кстати, интересно.

Sender в сообщении #1278893 писал(а):

Можно, конечно, построить полное дерево игры, но мы пойдём другим путём.

Sender в сообщении #1278912 писал(а):

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

Я лучше приведу аналогию, мне кажется она уместной и достаточно точной. Любую логическую функцию от $n$ входных переменных можно представить в виде сумм логических произведений входных переменных (возможно с инверсией), получится длинная и малоудобная запись (прямой аналог матрице весов в нейронке). Можно её свернуть в многоуровневую функцию, произведений и сумм (и инверсий) может стать существенно меньше (аналог что Вы хотите проделать с нейронкой), но представление уже не будет единственным и будет зависеть от критериев оптимизации при сворачивании. Плюс я не уверен что существует полностью формальный алгоритм такого сворачивания (несмотря на карты Карно и прочее). Плюс задача сворачивания может сама оказаться NP полной ...
Что я хотел сказать. Свернуть матрицу весов скорее всего можно, но не так уж существенно (ну пусть даже на пару порядков), а вот дальше потребуется слишком сложный анализ и будет неустойчивость решения (в зависимости от критериев оптимизации решения будут не единственны). Первая же свёртка оставит матрицу всё ещё лишком сложной для человека (алгоритма просматриваться всё ещё не будет).
Всё это не более чем досужие размышления.

-- 26.12.2017, 18:33 --

И кстати Вы правы, на примере крестиков-ноликов вполне можно увидеть эти возможности и недостатки, помнится была забавная статейка типа "самообучающийся автомат игры в крестики-нолики из спичечных коробков" (по коробку на каждый вариант хода в каждой позиции, в коробках семечки, по итогам игры семечки в задействованных коробках убавляются/прибавляются) - натуральная нейронка, доступная даже для ручной симуляции человеком. К сожалению не помню критерия прекращения её обучения из статьи, интуиция подсказывает что надо обойти всё дерево игры, но не в каждой позиции есть один единственный правильный ход, а значит нельзя ждать пока матрица вероятностей примет значения ровно 1 для какого-то одного хода во всех позициях. Зато остановив обучение на любой желаемой стадии можно получить ту самую матрицу весов, вполне обозримую человеком, и попытаться свернуть её до понятного человеку алгоритма. Если обучение проведено до конца, то алгоритм должен получиться известный гарантированно оптимальный (ну это чисто из-за простоты дерева игры).

[Sender]

mustitz в сообщении #1278943 писал(а):

Ну... в крестики-нолики таки можно обдурить: $(1,1)$ — $(0,0)$ — угроз нету, случайный ход — $(0,1)$ — $(2,1)$ — угроз нету, случайный ход — $(0,2)$ — $(2,0)$ вилка.

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