Комментарии 56
Первые несколько абзацев статьи были мысли «шо, опять?», но, к моменту про constexpr проверки позиций настрой сменился на «неплохо, годно».
Я не поклонник шахмат, не знаю, найдут ли полезное в статье именно любители шахмат, но как материал для раздумий над реализацией позиционных игр сгодится (у меня в моем проекте была часть с тактической битвой, что-то похожее применял).
Отличная статья, отличное введение в шахматные движки! Очень хорошо, спасибо :)
Спасибо за статью. Если прикрутите к своему движку UCI интерфейс, энтузиасты компьютерных шахмат, например с computerchess.org.uk, возьмут его в свои соревнования и Вы сможете поточнее узнать его силу игры, ну и просто поболеть. Но это при условиях, что движок стабильный, то есть не зависает и не вылетает, понимает все правила шахмат, можно задать размер хэша, можно отключить встроенную книгу. И главное, у движка есть exe-файл.
В программировании особо не разбираюсь, но шахматы люблю, как и околошахматную тематику. Прочитал поэтому с удовольствием, даже несмотря на то, что из кода мало что понял. Спасибо большое Автору!
Очень порадовало что то, какие Автор вбирал критерии оценки позиции, практически отсылает к "человеческой" оценке, коей тот же стокфиш похвастаться зачастую не может: иной раз смотришь на позицию, оцениваешь её, а движок предлагает ну явно "нечеловеческие" ходы и "нечеловеческий" анализ (не истину сам не претендую, уровень не тот - много подобных разборов с гроссмейстерами можно найти при желании, натыкался частенько).
У компьютерных шахмат есть одна особенность: у людей шахматы - это битва не только интеллектов, но и нервов, выдержки, психики, а иногда (внезапно) и физической подготовки (посиди-ка 2 часа за доской с пульсом под 130 в пиках в стрессе); а у машины - только интеллекта (в данном случае, наверное, логики). Тема сложная, потому что сегодня шахматисты всех мастей, конечно, постоянно пользуются движками (даже такой любитель как я), и в "заготовленных" позициях тоже делают "компьютерные" ходы. Но к той позиции нужно еще прийти, правильно оценить нюансы, идеи... И где сегодня начинаются человеческие шахматы сказать уж очень сложно. Скоро победит тот, у кого память на шаблоны лучше?
Лично мне нравятся оба направления. С одной стороны - я за прогресс, за ИИ, за развитие: за нечеловеческим ходом зачастую следует глубокая тактика, которая превращается в шикарные атаки с жертвами. Но и романтику игры очень уж хочется сохранить. Вы посмотрите на партии классиков, шахматистов эпохи романтических шахмат, как они чувствовали позицию, какие ходы делали - их стокфиш часто критикует и опровергает в пух и прах, но они выигрывали и то было искусство. Не потеряем ли что-то важное здесь? Может эти 2 направления нужно как-то разделить? Как думаете?
движок предлагает ну явно "нечеловеческие" ходы и "нечеловеческий" анализ
В последних версиях Стокфиша коэффициенты подобраны нейросеткой в триллионах игр самим с собой. Да, это не человеческие коэффициенты, это коэффициенты математического бога :).
Может эти 2 направления нужно как-то разделить?
Давно разделили, окончательно - примерно после игры Каспарова против Deep Blue :). Человеческие и компьютерные шахматы - две отдельные дисциплины.
В последних версиях Стокфиша коэффициенты подобраны нейросеткой в триллионах игр самим с собой. Да, это не человеческие коэффициенты, это коэффициенты математического бога :)
Да, он стал очень хорош )
Давно разделили, окончательно - примерно после игры Каспарова против Deep Blue :). Человеческие и компьютерные шахматы - две отдельные дисциплины.
Да, вы конечно правы, формально оно так. Я скорее хотел сказать, что когда почти каждый шахматист анализируя свои партии и готовясь к матчам в дисциплине "человечьи шахматы" использует движок (помните, я чуть выше написал про память и шаблоны), границы этого разделения затираются. Но тут как-будто тупик, и можно наверное только побрюзжать - не запретишь же людям пользоваться достижениями прогресса. Así es la vida. А брюзжать не будем, не надо )
Шестой фактор - потерянная рокировка. Если король потерял рокировку не рокировавшись, то это считается серьезной слабостью для безопасности короля.
Я бы тут не согласился полностью с таким утверждением. Да, в большинстве случаев это верно, но не в 100% и даже не в 90%. Чем меньше фигур на доске, тем менее важна становится рокировка, т.к. король становиться очень сильной фигурой и должен не прятаться от нападений с помощью рокировки, а наоборот двигаться в гущу событий.
Многие гроссмейстеры часто даже в самом начале игры выбирают вариант с потерей рокировки (например размен центральных пешек и после этого размен ферзей, где один король теряет право на рокировку), т.к. там имеються свои преимущества.
Да, там есть такие детали, тоже подметил: при закрытом центре например ничего плохого в короле в центре не бывает обычно, или либо в раннем эндшпиле... Там еще критерий эндшпиля в статье спорный - насколько я понимаю, у людей эндшпиль там, где ферзей поменяли (хотя тут более субъективно, есть и эндшпили при ферзях). Но в целом же для самодельного движка неплохо! Мне показалось что при прочих критериях кроме рокировки эта потеря в оценке позиции при нерокированом короле должна нивелироваться более-менее за счет других плюшек если они есть.
Можно считать штрафные пункты в зависимости от общего количества фигур (своих и противника) на доске, например от 50 до 0. Просто отсутствие ферзей еще особо ничего не меняет (можно поставить штраф 45), а вот если осталось на доске ладья + одна легкая фигура или две-три легких фигуры - там ценность рокировки стремиться уже к нулю.
А может тогда пойти чуть дальше и условно выделить классические "малый центр" и "центр"? Например, отсутствие ферзей при отсутствии связанных пешек на вертикалях "малого центра" - штраф за (не)рокировку больше, чем при их наличии (закрытый центр). И скомбинировать это с Вашей идеей. А вот при ферзях и закрытом центре без рокировки уже немного хуже. А при ферзях и при открытом центре - туши свет )
Кстати, контроль над центром либо по флангам же тоже должны оцениваться при оценке позиции.
Я бы предложил некоторые улучшения:
Запоминать main variation - наилучшую последовательность ходов в поиске и использовать ее при поиске следующего хода в алфа-бета отсечении в сортировке ходов.
Вместо простого альфа-бета отсечения использовать поиск с нулевым окном.
Вместо std::set использовать std::unordered_set.
Спасибо, почитал про битовые манипуляции, с темой не был знаком.
А для чего на титульной картинке пылесос?
В свое время читал книгу "Программирование шахмат и других логических игр" Евгений Корнилов, там достаточно подробно разбиралось программирование движка. Насколько я помню, примеры кода были больше на C, но теория разработки была подробной.
"Не так давно я захотел написать свой шахматный движок. На удивление в
Интернете нашлось не так много хороших статей на эту тему."
Значит плохо искал либо искал преимущественно на русскоязычных ресурсах. На тему компьютерных шахмат в англоязычных ресурсах МОРЕ полезной информации. Есть даже такой замечательный сайт https://www.chessprogramming.org/ с кучей теории и большим количеством ссылок.
Про perft ничего в статье не сказано, а это чуть ли не первое, что должен реализовать разработчик шахматной программы, чтобы потом не было мучительно обидно)
И классические шенноновские механизмы сейчас малоинтересны, там сказали уже почти всё и продвижения особого там нет. Сейчас state-of-the-art - это движки наподобие AlphaZero и Leela Chess Zero (глубокие нейросети + Monte Carlo Tree Search). Там сейчас совершаются открытия.
Неплохо. Таких статей не хватает на хабре.
Когда статья началась с описания оптимизаций, мне показалось, что шахматный движок в итоге не будет дописан. Но рейтинг 2000 говорит, что движок не просто существует, но и играет примерно на уровне других не топовых ботов.
ELO 2000 - это очень и очень мало((
"2000—2199 — кандидат в мастера спорта;" - какое-то "мало" у вас странное
для компьютерных шахмат - это катастрофически мало. Там уже штурмуют 3600-4000
1) с чего вы решили что автору нужно 4000 чтобы заявить о своей работе?
2) даже в представленном рейтинге по ссылке список из 500 заканчивается на 1400 баллах, то есть автор попал в 500 - это отличный результат
3) автор не ставил целью написать что-то что "штурмует" 4000, вы вводную часть статьи прочитайте
Объясню. Мой шахматный движок, написанный на Delphi (!) в 2010 году (!!), играл в силу 2200. И уже тогда это был крайне посредственный результат, что я побоялся его включать в CCRL Rating List
Это кандидат в мастера. Для простенькой программы вполне хороший результат. Первые шахматные программы до 80-х годов имели примерно 2000-2100 максимум.
А потом опа, и некто релизит полноценные шахматы с приличным Ai и кое-какой графикой, занимающие 1к :)
Вообще я давно мечтаю написать статью для хабра про историю развития компьютерных шахмат, начиная с Клода Шеннона и матча между программами советского института и Стэнфордского университета и заканчивая глубокими нейросетями и Leela Chess Zero. На этом пути было столько интересного и столько ярких событий, движков, идей. Сейчас мало кто помнит, что был такой шахматный компьютер, как Мефисто, про которого в свое время говорили "перворазрядник, который видит всё" (вроде так). А опубликованные исходники Fruit, после которого произошел взрыв? А Deep Blue, Rebel, Fritz, Houdini, Рыбка, какого-то странного, анонимного происхождения, но чудовищной силы движки IvanHoe, Ippolit, RobboLito. Нынешний Стокфиш, шумиха с AlphaZero. Там столько всего было.
1K ZX Chess — это компьютерная шахматная программа 1982 года (с недостающими тремя правилами) для нерасширенной версии Sinclair ZX81.
...
1K ZX Chess использует только 672 байт оперативной памяти, но реализует большинство шахматных правил (не хватает рокировки, превращения пешек и взятия на проходе) и соперника, за которого играет компьютер. Это была самая маленькая реализация шахматной программы для ЭВМ, пока это место в январе 2015 года не заняла программа BootChess, хоть её искусственный интеллект и слабее, чем у 1K ZX Chess.
Он будет абсолютно детерминированным и все партии будут 1 в 1. Играть против такого противника довольно скучно, поэтому стоит добавить базу дебютов из которой будут выбираться случайные ходы.
Когда-то давно писал шахматы, совсем простые, и конечно без всякой базы. Для недетерминированности минимакс брал один из лучших найденных ходов случайным образом :)
Крутая статья, огромное спасибо, хабр - торт!
Во введении верно отмечено, что в большинстве статей либо подробно описывается создание слабого движка, играющего чуть лучше рандома, либо движок сильный, но очень мало деталей реализации. К автору два вопроса:
Какой у Вас рейтинг на шахматном сайте заблокированном в РФ?
Не рассматривали вариант вместо альфа/бета поиска использовать Monte Carlo Tree Search?
Рейтинга на шахматном сайте заблокированном в РФ у меня нет, так как я им не пользуюсь (: Туда заходил чисто из-за наличия ботов с обозначенным уровнем игры. Основной аккаунт на lichess, там Эло около 1500, в шахматах обычный любитель.
Поиск по дереву Монте-Карло сперва рассматривал, но потом отказался так как алгоритм довольно сложный и редко использующийся.
Есть вопросы к автору по поводу этого:
Идея в том, что после завершения основного поиска не возвращать статическую оценку, а запускать новый без лимита по глубине, но с рассмотрением только взятий. Разумеется, если взятия не улучшают оценку, то надо прерывать такой просмотр, а не возвращать оценку после всех взятий.
Что такое «поиск без лимита по глубине»? Что значит «рассмотрение только взятий»? Разве можно что-то делать после завершения основного поиска, если он завершается по допустимому времени?
Рассмотрим этот псевдокод, он был в статье:
int alphaBetaMax( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMin( alpha, beta, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}
int alphaBetaMin( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMax( alpha, beta, depthleft - 1 );
if( score <= alpha )
return alpha; // fail hard alpha-cutoff
if( score < beta )
beta = score; // beta acts like min in MiniMax
}
return beta;
}В нем видно, что после того как заканчивается глубина происходит возврат статической оценки текущей позиции.
Идея в том, чтобы возвращать не статическую оценку, а результат выполнения другого поиска, по большей части похожего на оригинальный альфа-бета алгоритм, но без лимита по глубине и с рассмотрением только взятий. У меня в итоговом коде класса ИИ этот момент реализован.
Очень впечатлен статьёй!
Один мой друг как-то написал шахматы и я даже использовал их для игры через инет со знакомой (как в книге/фильме "Если наступит завтра" ))). В критический момент в программе нашлась ошибка... неправильно делалась длинная рокировка - и .... мне пришлось играть самому с середины партии.
Интересно - думается должна быть библиотека где учитываются все правила/интерфейс и самому надо придумывать только логику. Или я много хочу?
Интересно, сложно ли написать самообучающийся нейросетевой движок?
"Интересно, сложно ли написать самообучающийся нейросетевой движок?"
Пожалуйста, вот исходники: https://github.com/LeelaChessZero/lc0 , можно изучать. Но тут проблема в другом. Для создания сильного движка уровня гроссмейстера и выше нужны либо вычислительные мощности, как у Гугла, либо создание распределенной сети, как поступили разработчики Leela Chess Zero.
В чём причина того, что репозиторий с кодом в режиме read-only? Вы же фактически отказываетесь от любых обновлений и багфиксов. И, кстати, я бы убедительно рекомендовал перевести документацию на английский, вплоть до того, что даже сам (теоретически) был бы готов создать PR, не будь эта возможность заблокирована.
Не программист, но статью просмотрел с интересом. Как я понимаю, программа сейчас находится в положении state of art по состоянию примерно на середину 1970-х. Значит можно начинать улучшать:)
Для сортировки тихих ходов стандартными методами являются "киллеры" и сортировка по истории.
Основным источником силы подобных программ является отсечение 99% заведомо не лучших ходов. Для этого существует множество эффективных методов. В первую очередь нужно пробовать "нулевой ход", "LMR", различные отсечения на предельных глубинах (например Futility, Razoring).
Но лучше, наверное, посмотреть как реализованы эти методы в коде Стокфиша. По сути, бОльшая часть силы этой программы проистекает из небольшого участка кода (шаги с 7 по 18):
https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp#L776-L1230
В-пятых, счетчик ходов. Это просто float переменная, добавляющая по 0.5 за каждый ход. Если переменная круглая, то ход белых. Если у нее есть дробная часть, то ход черных.
а вот это зачем? почему не простой int (uint, фиксированный 32, 64 - что хочется), и добавляем +1 (ну как обычно) и проверяем последний бит (четность). Быстро, безопасно в плане float и дробной части... понятно, наглядно... в общем, одни плюсы.
Разница в производительности между int и float одной длины находится на уровне погрешности, по крайней мере, когда использование ограничивается одной-двумя примитивными операциями за ход.
Про безопасность не совсем понял. Вы про погрешность float типов? Если для проверки стороны использовать что-то вроде
move_ctr - std::floor(move_ctr) == 0то, естественно, это будет не безопасно, но если что-то такое (это я и использую)
move_ctr - std::floor(move_ctr) > 1e-7то вряд-ли это когда-то подведет.
А читаемость и наглядность вещи, во многом, субъективные. Мне float счетчик кажется более понятным.
У меня ощущение, что
move_ctr - std::floor(move_ctr) > 1e-7
Медленнее, чем
(count & 0x1) == 0В любом случае пара операций на ход не критична.
Спасибо за статью, очень познавательно
Это аукнется только в оооочень длинных партиях.
Вы меня уж очень разволновали с вопросом про безопасность этой штуки, так что я решил ее протестировать.
Есть такой вот код:
#include <iostream>
#include <cmath>
#include <iomanip>
int main() {
std::cout << std::setprecision(8);
float move_ctr = 0;
for (int i = 0; i < 1e+6; i = i + 1) {
move_ctr = move_ctr + 0.5f;
}
std::cout << "Ctr: " << move_ctr << std::endl;
std::cout << "Black move: " << (move_ctr - std::floor(move_ctr) > 1e-7) << std::endl;
return 0;
}Он эмитирует применение миллиона ходов. В конце выполняется проверка какой стороне принадлежит ход.
Если скомпилировать и запустить то видно, что даже спустя миллион ходов счетчик работает корректно, а в шахматах нельзя сделать более 6000 ходов из-за правил троекратного повторения позиции и 50 ходов, так что метод абсолютно безопасный.
(ведь 1 бит из 64 при использовании знаковых переменных отвечает за знак числа и его компьютер трогать не будет)
Это не совсем так. Неизвестно, что будет делать тот или иной компилятор. В стандарте это описано как UB. http://eel.is/c++draft/expr.shift
Это UB только если ПРАВЫЙ операнд отрицательный. Если же отрицателен ЛЕВЫЙ операнд (а в статье этот Bitboard везде слева), то в C++20 поведение полностью определено, и в случае сдвига влево будет выполнен логический сдвиг с затиранием знакового бита тем, что находится правее него, а вправо - арифметический с размножением знакового бита. До C++20 же сдвиг отрицательного числа влево действительно был UB.
Шахматы на C++