Учу свой компьютер играть со мной

Реализация шахматного движка с нуля

Шахматы - это древняя настольная стратегическая игра для двух игроков. Существует огромное количество возможностей, поскольку после каждого 5 ходов появляется 69 352 859 712 417 возможных игр. Таким образом, практически невозможно предсказать каждое движение.

Как скромный любитель шахмат, я поставил перед собой задачу: разработать простую, красивую шахматную игру с ИИ, которая может победить меня без машинного обучения. Эта статья о моем пути к ее достижению состоит из 4 частей: правила, вычисления, стратегия и игра.

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

Я назвал его Бобби, как дань уважения Роберту« Бобби Джеймсу Фишеру», который был чемпионом мира по шахматам и одним из моих героев в молодости.

1. Правила

Шт

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

  • ♔ - Король
  • ♕ - Королева
  • ♖ - Две ладьи
  • ♗— Два епископа
  • ♘ - Два рыцаря
  • ♙ - Восемь пешек

Исходные позиции

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

Доска представляет собой квадратную сетку из ящиков 8x8 (то есть двумерный массив), чередующиеся темным и светлым фоном. Пришло время визуально представить эту доску.

Визуальный дисплей

Когда я подумал о рисовании фигур, я сначала подумал о бесплатных графических ресурсах. Но это вынудило бы меня управлять картинками, что было нежелательно для быстрого развития. К счастью, я обнаружил, что каждый символ является частью Юникода: простой текстовой метки, таким образом, достаточно, чтобы нарисовать кусок! Отлично, я уже смог распечатать плату в журналах консоли, чтобы визуализировать ее:

♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜ 
♟ ♟ ♟ ♟ ♟ ♟ ♟ ♟ 
 
 
 
 
♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙ 
♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖

Забавно, но не так красиво, как то, что я имел в виду, поэтому я решил создать базовый графический интерфейс: плата представляет собой единый фрейм с сеткой, управляемой архитектурой MVC.

Я начал с определения темного и светлого фона, где каждый квадрат представляет собой метку, содержащую либо пустое значение, либо символ Unicode части.

Если вы знакомы с шахматами, вы, вероятно, знаете, что сетка доски имеет систему координат, состоящую из букв (горизонтальная ось или файлы) и цифр (вертикальная ось, ранги), которые используется для обозначения игры, то есть для сценария ходов. Наконец, я добавил их по бокам моей доски, и вот результат, простая сетка 10x10:

Движется

Давай продолжим. Каковы правила? Какие действия разрешены? В основном есть 4 типа ходов, которые можно комбинировать в зависимости от фигуры:

  1. Стрит (используется для ладей, ферзя и короля)
  2. Диагональ (слоны, королева, король)
  3. «L» (рыцари)
  4. Ходы пешек

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

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

Я также разработал дополнительную цветную рамку вокруг квадратов, чтобы выделить ходы:

  • Красный - выбранный в данный момент кусок
  • Синий - возможное место назначения выбранной фигуры
  • Зеленый - последний ход, сделанный противником

Правила

Теперь, когда мы можем перемещать фигуры, мы должны принять во внимание правила игры: есть вещи, которые можно сделать, а также вещи, которые должны сделать (обычно , избегая проверки).

Это выходит за рамки объяснения здесь каждого правила, но я попытался реализовать большинство ограничений, среди прочего:

  • Ходы игроков;
  • Определение того, находится ли король в шахе, и когда нет возможности избежать этого, определение того, что король мат (игра проиграна);
  • Оба короля всегда находятся на расстоянии квадрата друг от друга;

Окончание игры

Теперь, как игра заканчивается? Возможны два сценария: либо игрок выигрывает, либо ни один (ничья) не выигрывает.

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

Но вы рисуете, если:

  • Нет возможных ходов, но ваш король не под шахом (пат); или
  • Оба игрока повторяют 3 одинаковых хода подряд; или
  • Оба короля находятся на доске одни (или у них недостаточно материала для победы).

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

Согласно приведенным выше правилам, два человека могут играть в игру, но мы хотим играть против компьютера, поэтому давайте перейдем к сути дела.

2. Расчет

Глупый ИИ

Какой может быть самый низкий интеллект? Выбор разрешенного хода без какой-либо стратегии. Это был первый уровень «интеллекта», который я реализовал как бот: вычислить все возможные ходы и случайным образом выбрать один из них. Хорошо, это было весело, но теперь давайте будем серьезными.

Оценка ситуации

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

По сути, и согласно правилам игры, когда ход приводит к мату, прекратите поиск, потому что это лучший ход. С другой стороны, я реализовал штрафной счет, если ход приводит к ничьей, потому что я хотел сделать ИИ максимально агрессивным.

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

Наивная оценка

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

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

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

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

Помимо прочего, предсказание 1, 2 или 3 ходов позволяет ИИ:

  • Сделайте выигрышный ход, ведущий к немедленному мату (глубина 1)
  • Сразу после этого сделайте ход, предотвращающий проигрыш (глубина 2)

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

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

3. Стратегия

Я часто спрашивал себя, какие советы мне давали, когда я начинал играть, то есть, что сделало ход хорошим или плохим.

Управление центром

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

Я реализовал это с помощью концепции тепловой карты:

  • 4 наиболее центрированных квадрата приносят по 2 очка каждый;
  • 12 квадратов вокруг них стоят 1 очко;
  • Все оставшиеся квадраты приносят 0 очков.

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

Приближаясь к мату

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

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

  • 3 очка при ударе по королю, потому что очень хорошо, когда король находится под шахом;
  • 2 очка вокруг короля, потому что вы препятствуете ему убежать;
  • 1 очко вокруг области короля, потому что это в конечном итоге приводит к ограничению его ходов;
  • 0 для всех остальных квадратов.

Открытия

Как и во многих играх или спорте, есть теоретическая часть, которой нельзя пренебрегать. Стратегия, основанная на вышеприведенной эвристике, хороша, но может быть недостаточной для хорошего старта, а несовершенный старт в шахматах может быстро привести к поражению в битве. Чтобы избежать раннего неудачного хода, игроки заучивают дебюты наизусть, и это то, что я реализовал. Конечно, есть библиотеки с множеством открытий, но поскольку моей целью было сделать ИИ сопоставимым со мной, я решил сообщить ему только 15 основных открытий, по 2–3 хода в каждом.

Я использовал древовидную структуру для классификации проемов: движение ведет к узлу, а лист - это последнее известное движение для данного проема.

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

Бонусы и штрафы за развитие

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

Бонус начисляется, когда:

  • Рокировка окончена

Штраф назначается, когда:

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

4. Игра

Тестирование игры

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

  • Глупый бот, играющий наугад
  • Боты соответственно вычисляют ходы с глубиной 1, 2 и 3
  • Другой бот-вычислитель движется с глубиной 3, но также испытал некоторые открытия
  • Я, любитель шахмат

Все участники встречались друг с другом, играя дважды белыми и дважды черными в каждом матче. Вот итоговое табло:

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

Неудивительно, что боты с самым высоким уровнем вычислений занимают второе место, а случайный - последним. Интересным фактом является то, что последний смог заработать 0,5 балла, сделав ничью против более сильного бота. Что касается обоих ботов с уровнем 3, то они почти победили всех остальных ботов, и их очная встреча завершилась со счетом 2–2, что тоже вполне логично. Наконец, нельзя сказать, что освоение теоретических дебютов дает значительное преимущество, по крайней мере, не по сравнению с другими ботами, играющими ту же стратегию, но я уверен, что это имеет значение при столкновении с людьми.

Попробуйте

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

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



Игра в шахматы Бобби
Эта базовая игра в шахматы - дань уважения знаменитому шахматисту Роберту Джеймсу« Бобби Фишеру, чемпиону мира по шахматам. Это… www.bobby-chess.com »



Примечание.. Если вам интересно прочитать, как я представил настольное приложение Java Swing через веб-сайт, я написал еще одну статью, посвященную этому техническому аспекту:



Превращение приложения Java Swing в чистое, элегантное веб-приложение без изменения кода
Говорят, что Java Swing - это старая, устаревшая технология для разработки настольных приложений. Однако есть простые способы изменить… codeburst.io



Заключение

Ограничения и сильные стороны ИИ

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

Более того, я полностью убежден, что для таких игр нет ничего лучше машинного обучения или, может быть, тонкой комбинации машинного обучения и традиционных вычислительных машин. AlphaGo был первым движком на базе машинного обучения, который победил чемпиона мира в го. Затем, в 2017 году, был представлен AlphaZero, который в значительной степени победил лучший традиционный Chess движок, а именно StockFish.

Но когда мой отец любезно тестировал мой Chess Engine, он сделал интересное заявление:

Современные шахматные движки утомительны.

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

Движок Бобби пытается уйти от этого, благодаря случайности в проемах, а также при вычислении эквивалентных ходов.

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

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

Заключительные соображения

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

Я очень доволен конечным результатом, хотя считаю, что в будущем многое можно улучшить. Мне было бы особенно интересно разработать ИИ с глубоким обучением и заставить их бороться с ним.

Ресурсы