Статистический подход к шахматам?

Question

Чтение о том, как Google решает проблему перевода заставило меня задуматься. Можно ли построить сильный шахматный движок, проанализировав несколько миллионов игр и определив наилучший возможный ход, в значительной степени (полностью?) Основанный на статистике? Существует несколько таких шахматных баз данных (, в этой есть 4,5 миллиона игр), и можно потенциально взвешивать ходы в идентичных (или зеркальных или отраженных) позициях, используя такие факторы, как рейтинги участвующих игроков, как старая игра (с учетом улучшений в теории шахмат) и т. д. Какие-либо причины, по которым этот не будет целесообразным подходом к созданию шахматного движка?

Answer 1

Нечто подобное уже сделано: это основная концепция открытия книг .

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

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

Некоторые люди также могут запомнить вводные книги (именно поэтому Фишер изобрел свой вариант случайные шахматы , так что запоминание открытий становится гораздо менее эффективным). Отчасти из-за этого иногда нетрадиционный ход делается вначале, не потому, что это статистически лучший ход по истории, а с точностью до наоборот: это не «известная» позиция, и она может занять вашего противника (человека или компьютера) » вне книги ".

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

Поиск шаблонов

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

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

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

Answer 6

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

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

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

Answer 7

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

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

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

Answer 8

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

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

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

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

Answer 9

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

Answer 10

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

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

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