Статистический подход к шахматам?
Чтение о том, как Google решает проблему перевода, получило меня взгляды. Было бы возможно создать сильный шахматный механизм путем анализа нескольких миллионов игр и определения самого лучшего перемещения, базирующегося в основном (полностью?) на статистике? Существуют несколько таких шахматных баз данных (это - то, которое имеет 4,5 миллиона игр), и можно было потенциально взвесить, приближается идентичный (или зеркально отраженный или отраженный) положения с помощью факторов, таких как оценки вовлеченных плееров, какого возраста игра (к фактору в улучшениях теории шахматной игры) и т.д. Какие-либо причины, почему это не было бы выполнимым подходом к созданию шахматного механизма?
6 ответов
Что-то вроде этого уже сделано: это основная концепция открытия книг .
Из-за природы игры компьютерные ИИ заведомо плохи вначале, когда существует так много возможностей, а конечная цель еще далеко впереди.Он начинает улучшаться к середине, когда начинают формироваться тактические возможности, и может отлично играть в конце игры, намного превосходя возможности большинства людей.
Чтобы помочь ИИ делать правильные ходы вначале, многие движки вместо этого полагаются на открывающие книги: в основном, на статистически выведенную блок-схему ходов. Многие игры между игроками с высокими рейтингами были проанализированы, и рекомендации жестко закреплены в «книге», и, хотя позиции все еще находятся в «книге», ИИ даже не «думает», а просто следит за тем, что «книга» говорит.
Некоторые люди могут также запоминать дебютные книги (в основном именно поэтому Фишер изобрел свой вариант случайных шахмат , так что запоминание дебютов становится гораздо менее эффективным). Отчасти из-за этого вначале иногда делается нетрадиционный ход, не потому, что это статистически лучший ход в соответствии с историей, а как раз наоборот: это не «известная» позиция, и она может занять вашего оппонента (человека или компьютера) » из книги ».
На противоположном конце спектра находится так называемая база данных эндшпиля , которая в основном представляет собой базу данных ранее проанализированных позиций в эндшпиле. Поскольку позиции ранее были тщательно изучены, это можно использовать для обеспечения идеальной игры: для любой позиции можно сразу решить, выигрывает она, проигрывает или ничья, и как лучше всего достичь / избежать результата.
Однако в шахматах нечто подобное возможно только в дебюте и эндшпиле. Сложность средней игры - вот что делает игру интересной.Если бы можно было играть в шахматы, просто взглянув на стол, то игра не была бы такой захватывающей, интересной и глубокой, как она есть.
В шахматах примерно 10 123 деревьев игр, из которых у вас примерно 4,5 × 10 6 в эта база данных. Мы можем игнорировать игровые деревья и рассматривать только сложность в пространстве состояний, для которой существует где-то между 10 43 и 10 50 законными состояниями. Предположим, что все игры в этой базе данных имеют уникальные ходы, и что в среднем за игру приходится 1000 ходов, что дает нам 4,5 × 10 9 состояний. Принимая оценочную нижнюю границу 10 43 возможных состояний, которая покрывает только 4,5 × 10 -34 всех состояний. Я не знаю, каково общее количество уникальных позиций доски, исключающих повороты или отражения, но это уменьшит его только примерно в два раза, что не очень помогает.
Вам нужно будет добавить больше знаний о предметной области в статистический механизм и выяснить уровень сходства между двумя заданными позициями платы, так как вероятность того, что вы не найдете подходящей платы, составляет 1 из 10 35 . положение (включая отражения и вращения). Я думаю, что самый важный момент здесь будет заключаться в том, насколько похожи две заданные позиции в совете директоров. Это будет включать в себя гораздо больше знаний в предметной области, чем просто простые преобразования.
Тем не менее, это отличная идея, которую стоит изучить дальше, хотя я подозреваю, что ее уже опробовали, учитывая сложность шахмат и интерес к ним.
Эта общая стратегия была опробована для множества игр. Очень часто люди создают достаточно большую базу данных игр, заставляя компьютер играть сам. Быстрый поиск в Интернете открывает http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/chess-RL.pdf , который основан на предыдущей работе в Backgammon. Однако в шахматах упреждающий метод грубой силы очень эффективен для компьютеров - и в целом статистика намного более эффективна, когда вы можете смешать всю ранее известную информацию о проблеме, а не пытаться повторно изучить ее на основе данных. . Я отмечаю, что по этой ссылке компьютер узнал, что представляет собой функция оценки в нижней части упреждающего просмотра, а не весь процесс.
Есть нечто подобное, что очень хорошо работает в компьютерном Go - метод UCT . Он не использует известный набор игр, а вместо этого играет в огромное количество случайных игр, сохраняя статистику, ходы которой приводят к более высокому соотношению выигрышей. Это происходит, начиная с текущей позиции.
Статистика хранится в дереве ходов (аналогично тому, что используется в минимаксе) и влияет на выбор следующей случайной игры - ходы с более высоким коэффициентом выигрыша выбираются чаще. Рост дерева также определяется играми - обычно каждая игра добавляет к дереву лист. Это ведет к более глубокому изучению многообещающих путей.
Мне нравится эта идея, но аналогия [с переводом текста] кажется неадекватной, если учесть, что контекст предложения на естественном языке требует гораздо меньше элементов, чем контекст позиции на шахматной доске (даже если элементы таких предложений, а именно слова, могут происходить из большего набора, чем элементы шахматной игры, а именно игровые фигуры, конь, пешка и т. д. .)
Кроме того, доступность многоязычного корпуса (документов разного характера, на разных языках) намного превышает количество шахматных партий, которые можно найти в цифровая форма , в частности, если учесть, что для шахматного анализа нужна вся игра, в результате чего для целей перевода можно использовать каждое предложение независимо от остального текста.
В результате, за возможным исключением начальной части игр (когда позиции на доске не имели большой возможности расходиться по сравнению с другими играми), количество требуемых шахматных партий для введения некоторой статистической значимости должно быть астрономическое значение ...
Надо бежать, но я вернусь с конкретными оценками количества возможных шахматных партий (в абсолютном и в подмножестве правдоподобных игр) и должно эффективно доказать, что 4,5 миллиона игр - это относительно небольшая выборка.
Что ж, 4,5 миллиона игр по-прежнему покрывают лишь очень маленькую (бесконечно малую) часть всех возможных игр.
И хотя у вас будет большое количество выигрышных и проигрышных позиций, останется проблема свести это число до пригодного для использования набора параметров. Очень старая проблема с нейронными сетями в качестве стандартного подхода. Но NeuralNets не выигрывают шахматные турниры.