Есть ли шахматный движок, который НЕ использует перебор?

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

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

Есть ли какой-нибудь шахматный движок, который не использует подход грубой силы, чтобы найти свои ходы?

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

Обучение нейронной сети, чтобы выбрать ходы кандидатов, кажется многообещающим направлением исследований. Здесь и здесь могут быть две соответствующие статьи. (FWIW, это не моя область Comp Sci)

Вы можете взглянуть на Жирафа, который недавно был в новостях:

https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/

Шумиха заключается в том, что за 3 дня он обучил себя игре и достиг уровня IM. С другой стороны, исследование на

http://arxiv.org/abs/1509.01549

Я хотел бы добавить подробности к ответу @ Ian_Bush о жирафе.

В ответе @ Ian_Bush отмечается, что Жираф не использует вычисления грубой силы. Это не правильно , потому что Жираф по-прежнему является альфа-бета (nega-max) движком. Только разница со стандартным двигателем является то , что функция оценки настраивается автоматически при глубоком обучении. Поэтому движок учится играть самостоятельно.

Традиционно программист двигателя самонастраивает параметры в двигателе. Я много сделал сам. Например, какой вес вы должны придать епископу и рыцарю? 3,0? 3,1? 3,2? Сложно сказать.

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

РЕДАКТИРОВАТЬ : Жираф моделирует узлы дерева как вероятность того, что они попадают в главное изменение. Проверьте бумагу для деталей. Лично я не верю этому подходу, и в статье мало доказательств того, насколько он был бы полезен.

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

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

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

Клод Шеннон предложил два типа алгоритмов для создания шахматных движков. Движок «типа А» проверяет все возможные ходы на некоторую конечную глубину, минимизирует дерево, а затем воспроизводит ход с наивысшей оценкой из минимаксного дерева (иначе говоря, грубой силы). Двигатели типа B ограничивают свой поиск только подмножеством возможных ходов на основе некоторых критериев. Я полагал, что он предпочитал Тип B как более многообещающий.

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

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

В 1990-х Крис Уиттингтон высказался за использование большего количества знаний о шахматах и ​​создал программу под названием Chess System Tal, которая была довольно сильной для своего времени.

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

В основном все они!

Шахматные двигатели действительно используют грубую силу только тогда, когда:

• сказал
• анализируем позиции (решение проблем)
• Ищем мат (решение проблем, а не при игре против, например, проблемы со стилем "найди помощника в N")

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

Они также склонны использовать грубую силу в качестве последней линии защиты, если вы видели шансы на поражение матом, он может увидеть, что он приближается, и он захочет изо всех сил потянуть, и не может найти выход (эффект Horizon «это проблема с двигателями, предположим, что она потеряет свою королеву, и она ограничена, чтобы идти только на 4 игры; если она может торговать пешками и отложить потерю королевы на 4 хода, она будет думать, что спасла королеву в процессе он потеряет по крайней мере 1 пешку (так как следующий ход приближает горизонт раньше), и вес, который он придает спасению королевы, может означать, что он жертвует некоторой защитой, даром, если смерть выходит за горизонт) ,

Это также перебор, когда выборочный поиск не очень полезен. Вот почему двигатели занимают больше времени, когда у них осталось около 3 штук. Они должны перебор, потому что алгоритм выбора не может оценить ход. Алгоритм выбора хорош во время мидгама, потому что он может выглядеть как «Оооо, делая это с пешкой, блокирует его [что угодно] и резервирует мои [что угодно] и [что угодно], которые я защищаю меньше, чем атакующий» - например, ,

Если у вас есть король в середине доски, то есть 8 ходов, выборочный поиск будет похож на «Ни один из них не делает ничего полезного, я не могу сказать».

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

Двигатель тогда делает то же самое с вашей точки зрения, и туда-сюда, и туда-сюда.

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

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

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

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

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

Грубая сила из стартовой позиции может найти того известного помощника в 4, который включает в себя ферзя f7, покрытого слоном, и если бы он оценил это высоко (Я НАШЕЛ ПРОВЕРИТЬ! РАБОТА ЗАВЕРШЕНА! ИГРАТЬ!) Это было бы неправильно, потому что черные явно противостоят. Выборочный поиск оценивает позицию (для дальнейшей оценки), потому что это, кажется , хорошо. Это означает, что когда он рассматривает ваш ответ, он может решить, что будет хорошо для вас ....

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

Следовательно, Каковы первые выбранные ходы (белые) шахматными двигателями грубой силы?