Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

Chinmay,

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

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