Как двигатели улучшились после Deep Blue?

Компьютерные шахматные движки стали лучше с тех пор, как Deep Blue победил Каспарова в 1997 году.

Алгоритмы стали лучше, или улучшения были в основном из-за того, что те же алгоритмы работали быстрее благодаря более быстрому оборудованию и т. Д.?

Если первое, являются ли эти алгоритмические улучшения публичными?

И если да, то каковы были улучшения? Где я могу прочитать о них?

Может быть, вы можете взглянуть на TalkChess , форум, посвященный компьютерным шахматам. Я нашел недавнюю ветку, которая может быть вам интересна: прогресс за 30 лет с четырьмя интервалами по 7-8 лет

Пара матчей между (бывшими) топовыми движками играются на одном и том же оборудовании . Тест показывает, что в последние годы (2002-2017), выигрыш в основном достигается за счет улучшений программного обеспечения. В тесте Stockfish (2017) набрал впечатляющие 94/100 против RobboLito (2009), в то время как RobboLito, в свою очередь, раздавил Шреддер (2002) со счетом 92/100.

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

Stockfish двигатель с открытым исходным кодом, поэтому алгоритмические улучшения общественности. Много документации можно найти на https://chessprogramming.wikispaces.com

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

https://chessprogramming.wikispaces.com/ - отличный источник, но по нему сложно ориентироваться.

Для улучшения шахматного движка есть три основные функции: оценка, генерация ходов и функции поиска.

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

Генерация ходов, наряду с созданием и снятием ходов, занимает много памяти, потому что ее нужно формировать очень много раз. Наиболее распространенными функциями генерации являются почтовый ящик, битовая доска, 0x88, 8x8, расширенные доски (10x10, 10x12) и предопределенный массив / таблица перемещений (* Я использую индексированную таблицу перемещений). В настоящее время принято считать, что битборды быстрее, а использование волшебных битбордов ускоряет это до 30%. Доктор Роберт Хаятт, профессор и создатель ленивого шахматного двигателя, не заявляет о существенном увеличении скорости.

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

ПРИМЕЧАНИЕ. Моя таблица индексов. GNUChess и Jester оба используют индексный массив для генерации своих ходов. Они инициализируют двигатель, заполняя массив возможными ходами. Возьмите шесть частей и вычислите законные ходы, которые доступны из каждого квадрата. Таким образом, каждый кусок имел массив [64] [8]. Я взял эту идею и сжал ее до двух индексов и таблицы. Таблица содержит значение, которое сообщает, возможны ли 16 ходов, один индекс содержит смещение хода, а другой - маску.

смещение [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};

mask [] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};

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

Алгоритмы стали лучше?

Очевидно, да немного.

или улучшения были в основном за счет того, что те же алгоритмы работают быстрее благодаря более быстрому аппаратному и программному обеспечению?

Незначительный интерес: если алгоритмы стали лучше, значит, программное обеспечение становится лучше, поэтому нет «или».

Закон Мура говорит нам, что скорость процессора удваивается примерно каждые 18 месяцев. Это означает, что он удвоился примерно в 13 раз за 20 лет. Это делает современные процессоры где-то в 8000 раз быстрее. Таким образом, самое большое улучшение производительности двигателя, безусловно, связано с более быстрым аппаратным обеспечением.

Если первое, являются ли эти алгоритмические улучшения публичными?

И если да, то каковы были улучшения? Где я могу прочитать о них?

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

Это все об алгоритмах.

Взяв человека-шахматиста, он взял один из самых мощных компьютеров в мире в то время. Такой подход к грубой силе позволил Deep Blue посмотреть на шесть-восемь шагов вперед. В жесткой борьбе машина в итоге победила Каспарова с 3 1/2 игры до 2 1/2.

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

Отказ от ответственности: не эксперт.

Алгоритмы стали лучше, и лучшие на сегодняшний день двигатели, работающие в 1995 году (вспомним, что Deep Blue был 1999), с легкостью победят Каспарова. Насколько я понимаю, есть два аспекта алгоритмов:

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

Стандартный алгоритм поиска - это альфа-бета-обрезка , и он использовался в самых ранних шахматных компьютерах. Я не знаю, использовал ли Deep Blue обрезку альфа-бета, но современные двигатели этого не делают. В результате их поиски «небезопасны» - они могут, например, пропустить, что какой-то другой ход, кроме возвращения королевы, выиграл бы игру. Однако такое случается редко, а взамен они очень сильно толкают свои глубины. («Глубина» - это технический термин, определяющий глубину поиска двигателя, поэтому, например, двигатель, который ищет на глубине 30, скорее всего, превзойдет тот, который ищет только на глубине 20, при прочих равных условиях).

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

• Если у одной стороны есть дополнительный материал / пространство, дайте ей бонус к оценке.
• Если у белых есть продвинутый рыцарь, которого поддерживает пешка, дайте белым бонус к прохождению.
• Если черный король зашел в тупик, дайте белым бонус к прохождению.
• Если у белых есть ладья на 7-м ранге, дайте белым бонус для оценки.
• Если это эндшпиль (и есть алгоритмы, позволяющие определить, является ли позиция эндшпилем), и у обеих сторон есть разноцветные слоны, наложите штраф на eval (то есть подтолкните его к 0,00).

Современные двигатели оценивают позиции намного лучше, чем Deep Blue.

Что касается того, являются ли алгоритмы общедоступными, Stockfish в настоящее время является самым мощным в мире движком с открытым исходным кодом. Вы можете скачать код самостоятельно с Github .