Что ж, 4,5 миллиона игр покрывают лишь очень малую (бесконечно малую) часть всех возможных игр.

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

Эта общая стратегия была опробована для множества игр. Очень часто люди создают достаточно большую базу данных игр, заставляя компьютер играть сам. Быстрый поиск в Интернете выдает http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf, который основан на предыдущей работе по нардам. Однако в шахматах грубая сила упреждения очень эффективна для компьютеров - и в целом статистика намного эффективнее, когда вы можете смешать всю ранее известную информацию о проблеме, а не пытаться заново узнать ее из данных. . Я отмечаю, что в этой ссылке компьютер узнал, что составляет функция оценки в нижней части просмотра вперед, а не весь процесс.

Есть нечто подобное, что очень хорошо работает в компьютерном Go — метод UCT. Он не использует известный набор игр, а вместо этого играет огромное количество случайных игр, сохраняя при этом статистику, ходы которой приводят к более высоким коэффициентам выигрышей. Он делает это, начиная с текущей позиции.

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

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

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

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

В шахматах примерно 10¹²³ игровых деревьев, из которых в этой базе данных примерно 4,5 × 10⁶. Мы можем игнорировать игровые деревья и рассматривать только сложность в пространстве состояний, где допустимых состояний может быть от 10⁴³ до 10⁵⁰. Предположим, что все игры в этой базе данных имеют уникальные ходы и что в среднем на игру приходится 1000 ходов, что дает нам 4,5 × 10⁹ состояний. Беря оценочную нижнюю границу 10⁴³ возможных состояний, мы покрываем только 4,5 × 10^–34 всех состояний. Я не знаю, каково общее количество уникальных позиций на доске, исключая вращения или отражения, но это уменьшит его только примерно в два раза, что не очень полезно.

Вам нужно будет добавить дополнительные знания предметной области в статистический механизм и выяснить уровень сходства между двумя заданными позициями на доске, поскольку существует вероятность 1 из 10³⁵, что вы не найдете совпадающую позицию на доске ( включая отражения и вращения). Я думаю, что самым важным ключом здесь будет выяснить, чем похожи две заданные позиции на доске. Это будет включать гораздо больше знаний в предметной области, чем просто простые преобразования.

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

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

В поисках шаблонов

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

Такие шаблоны могут быть эффективно запрограммированы в 64-битных масках. У вас будут битовые маски для важных позиций и битовые маски для ожидаемых фигур в этих позициях. Для сопоставления каждого шаблона требуется время, поэтому было бы важно найти те, которые имеют значение. Вот где будет использоваться статистический подход Google. Он мог запускать «исторические» игры и искать закономерности. После того, как он найдет шаблон, он должен будет вычислить вес шаблона и посмотреть, перевешивает ли улучшенная оценка накладные расходы.

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

В последнее время машинное обучение значительно продвинулось вперед, особенно после того, как команда Google победила чемпиона по GO с помощью машинного обучения. Это теперь также было продемонстрировано с шахматами. Взгляните на статью в MIT technology Review, https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/

Глубокое обучение ML — это усовершенствование старых алгоритмов искусственного интеллекта с самонастройкой нейронной сети. Демонстрация Лая не научила машину основным правилам игры в шахматы и не заботилась об исходе игры. Он просто скормил машине большую базу данных игр, а машина вычислила остальное и играла на разумном «человеческом» уровне.

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

Алгоритм глубокого обучения, похожий на программу GO, которая победила игрока Master Human, может быть убийцей. Хотя это потребует больших затрат. Однако можно использовать изученные шаблоны глубокого обучения из GO и применить их к шахматам.

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

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

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

Интересны как база данных, так и компьютерный анализ, но их легко неверно истолковать. Остерегаться.

Чинмай,

Я знаю, что это старая тема, но это тема, которую я изучаю в последнее время. Большинство людей, которые ответили выше, действительно не поняли вашего вопроса. Я думаю, что да, стоит проанализировать многочисленные партии в прошлом, чтобы разработать предлагаемые ходы. Покроет ли он все возможные ходы? Нет, очевидно, нет. Но он охватывает все реалистичные ходы из реальных игр. Человеку (или другому компьютерному алгоритму) пришлось бы начать делать очень странные ходы, чтобы сбить ситуацию с толку. Итак, вы не можете построить «идеальный» алгоритм, который выигрывает все время, но если он выигрывает много, скажем, рейтинг ФИДЕ> 2200, это неплохо, верно? И если вы включите дебюты и эндшпили, а не просто полагаетесь на анализ прошлых ходов, это сделает его еще лучше.

Существует астрономически большое количество возможных позиций на доске, но оно конечно, и если вы уберете глупые позиции, это число немного уменьшится. Возможно ли, чтобы 4, 5 или 6 пешек одного игрока выстроились в одну линию? Да, произойдет ли это в реальной игре? Сомневаюсь. Включите базовый шахматный мозг в свою логику для ситуаций, когда противник идет «не по правилам». Например, Micro Max — это всего пара сотен строк кода. Если противник сыграл глупо, чтобы помешать вашим ходам, его, вероятно, можно победить с помощью простого движка.