Как нарисовать шахматную доску golang

Русские Блоги

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

Правила гобанга

Я просто разобрал правила Gobang и изменил их следующим образом:

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

Чтобы ознакомиться с правилами официального соревнования, вы можете нажать на энциклопедию Baidu, чтобы узнать об этом -Gobang。

Скелет кода

Реализовано здесь Gobang Мини-игра заключается в использованииjavascriptЯзык написан с использованием грамматики es6 и объектно-ориентированного мышления.

НадGobangКласс содержит конструктор и метод инициализации. Метод конструктора — это метод класса по умолчанию. Этот метод автоматически вызывается, когда экземпляр объекта создается новой командой. Класс должен иметь метод конструктора. Если он не определен явно, по умолчанию будет добавлен пустой метод конструктора. Затем есть метод инициализации. Здесь я являюсь методом входа для инициализации всего класса. Используйте для написания объектно-ориентированный метод класса, лучше управлять расширением кода и функций.

Нарисуйте шахматную доску

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

Чтобы нарисовать физическую шахматную доску, мы используем ее здесь canvas Связанные точки знаний, управляйте кистью, чтобы нарисовать шахматную доску:

Используется здесь padding,count,borderColor И так далее передаются во время создания экземпляра. Это улучшает настраиваемость и управление. Приведенный выше код предназначен для рисования физической шахматной доски, поэтому, хотя логическая шахматная доска не может быть нарисована, мы можем ее выразить. Здесь мы используем метод двумерного массива для записи логического местоположения, например (0,0) Индекс массива, соответствующий точке: [0][0] ;тогда (1,2) Нижний индекс, соответствующий точке: [1][2] . И так далее. Затем мы присваиваем этой логической точке значение 0, что означает, что в текущей точке нет движения.

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

Нарисуйте шахматные фигуры

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

Лао-цзы понимает, что все сражаются

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

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

Осознайте сожаление

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

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

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

• Верхняя левая шахматная доска
• Шахматная доска с левым краем
• Шахматная доска
• Шахматная доска нижнего края
• Шахматная доска
• Правый край шахматной доски
• Верхняя правая шахматная доска
• Шахматная доска по верхнему краю
• Средняя (безграничная) шахматная доска

Осознайте отказ от сожаления

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

Напоминание о победе / игра окончена

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

До сих пор я объяснял шаг за шагом, как разработать небольшую казуальную игру, в которую можно было бы с удовольствием играть на ПК-Гомоку. Пожалуйста, поправьте меня, если что-то не так @ ～ @

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

Как нарисовать шахматную доску golang

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Создайте приложение, которое будет рисовать шахматную доску

About

Создайте приложение, которое будет рисовать шахматную доску

Resources

Stars

Watchers

Forks

Releases

Packages 0

Languages

Footer

© 2022 GitHub, Inc.

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Пишем простой шахматный движок на Go

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

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

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

Клетки и фигуры

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

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

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

Таким образом, нам необходим отступ по краям доски в две клетки. Мы могли бы создать доску 12×12, но так как мы представляем ее в виде линейного массива, нам нужна доска 12×10, потому что крайний правый квадрат отступа в предыдущей строке может использоваться в качестве крайнего левого квадрата отступа в следующей строке (× = отступ):

В нашем обозначении “a1” выглядела бы как 9×10+1=91, а “a8” — как “2×10+1″=21.

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

Наконец мы можем начать писать код:

Фигуры имеют определенную ценность. Эти значения нужны, чтобы оценивать позиции на доске и понимать, кто выигрывает. Обычно пешка = 100, конь = 280, слон = 320, ладья = 479, ферзь = 929, а король имеет настолько высокую ценность, что она превосходит 8 ферзей (пешки, превратившиеся в ферзей) в совокупности с парами коней, слонов и ладей. Если мы обладаем всем этим богатством, но теряем короля, подсчет все равно покажет, что мы проиграем.

Каждый тип имеет метод переворота (Flip() method), который возвращает то же самое значение после переворота доски перед ходом противника. У фигур он меняет регистр символа фигуры. У клеток он возвращает 119 клеток (считая с другого конца доски). Что касается доски, он копирует все фигуры с клеток в обратном порядке, меняя их регистр.

Генератор ходов

Итак, у нас уже есть «кирпичики» для движка, и теперь мы можем подумать об игровых позициях. Позиция — это доска с фигурами и дополнительные состояния в игре, такие как квадрат прохода, блуждающий квадрат и возможности рокировки. Если бы мы хотели упростить игру, мы бы могли повторно использовать тип доски (Board type), но мы создадим отдельный тип позиции (Position type), отвечающий за ходы и оценку доски.

Что такое ход? Это комбинация двух клеток — клетка, на которой фигура находилась до совершения хода, и клетка, куда переместились фигура. Позиция — это шахматная доска со счетом, правилами рокировки для каждого игрока и квадратами прохода / блуждающими квадратами. Оба типа также имеют метод переворота (Flip() method) для ходов соперника.

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

Чтобы сгенерировать все допустимые ходы, нам нужно:

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

Чтобы сделать арифметику направлений более читаемой, мы будем использовать константы направления N/E/S/W:

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

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

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

Но как понять, что мы проигрываем?

Оценка доски

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

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

Гораздо более точный и удивительно простой подход — это таблицы соотношения фигур и клеток (PST — Piece-Square Tables). Для каждой фигуры создается таблица такого же размера, как шахматная доска, где для каждой клетки назначается соответствующая ценность. Эти значения являются эмпирическими, поэтому я просто взял их из движка Sunfish.

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

Чтобы оценить позицию после хода, нам нужно:

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

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

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

Алгоритм поиска

Наиболее распространенный алгоритм поиска в шахматных движках попроще — поиск в глубину, который начинается с корня и спускается до заданного предела глубины, повторяя все возможные ходы перед возвратом. Для каждого хода вычисляется ценность позиции с использованием алгоритма минимакс (minimax) c альфа-бета отсечением (alpha-beta pruning).

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

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

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

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

В нашем движке мы будем постепенно увеличивать глубину поиска и вызывать алгоритм MDF(f) для поиска нижних и верхних границ оптимального результата. Алгоритм MDF (f) будет использовать итерации альфа-бета отсечения с кэшем транспозиции.

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

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

Что дальше?

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

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

Да, он слабенький, но он играет настоящие шахматные партии!

Надеюсь, вам понравилась эта статья. Вы можете подписаться на меня в Github, Twitter или подписаться через rss.

Нарисуйте прямоугольник в Golang?

Это единственный способ нарисовать фигуру в Go с некоторой шириной линии, чтобы сделать это с примитивами пиксель за пикселем?

Я хочу нарисовать метку с несколькими прямоугольниками и штрих-кодами, создать и вывести PNG/PDF.

4 ответов

стандартная библиотека Go не предоставляет возможности примитивного рисования или рисования.

то, что он предоставляет модели для цвета ( image/color ) и Image интерфейс с несколькими реализациями ( image ). В блоге пакет Go Image является хорошим введением к этому.

Другим примером является игра с открытым исходным кодом Лабиринт суслика (раскрытие: я-автор), который имеет графический интерфейс, и он не использует ничего другого, только стандартная библиотека Go для сборки своего представления.

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

стандартная библиотека также поддерживает чтение и запись общих форматов изображений, таких как GIF, в формате JPEG, PNG, и поддержка других форматов из коробки: BMP, РИФ, TIFF и даже файлы WebP (только считыватель / декодер).

хотя поддержка не предоставляется стандартной библиотекой, довольно легко рисовать линии и прямоугольники на изображении. Учитывая img изображение, которое поддерживает изменение пикселя с помощью метода: Set(x, y int, c color.Color) (например, image.RGBA идеально подходит для нас) и col типа color.Color :

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

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

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

Попытка нарисовать шахматную доску с помощью Черепахи в Python — как мне заполнить все остальные квадраты?

Я нарисовал доску, но теперь мне нужно определить функцию (цикл), которая заполняет все остальные квадраты черным цветом. Некоторое время я пытался написать цикл, чтобы сделать это, может кто-нибудь помочь?

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

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

мы можем назвать это так:

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

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

Определить функцию для незаполненного квадрата легко — просто продублируйте существующую функцию, но this_turtle.fill(False) вместо этого установите ее в начале.

Каждый раз, когда что-то нужно считать в повторяющейся последовательности (1, 2, 3, 4, 1, 2, 3, 4, . ), это требует использования модуля (остаток). Модульный означает остаток , так что если по x модулю y это 0 значит x точно делится на y . Это переводится в код, как если бы x % y == 0 :

Вот простая драм-машина для демонстрации:

Чередование похоже на повторный подсчет 0, 1, 0, 1.

Итак, мы можем нарисовать такую ​​строку:

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

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

Пишем простой шахматный движок на Go

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

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

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

Клетки и фигуры

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

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

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

Таким образом, нам необходим отступ по краям доски в две клетки. Мы могли бы создать доску 12×12, но так как мы представляем ее в виде линейного массива, нам нужна доска 12×10, потому что крайний правый квадрат отступа в предыдущей строке может использоваться в качестве крайнего левого квадрата отступа в следующей строке (× = отступ):

В нашем обозначении “a1” выглядела бы как 9×10+1=91, а “a8” — как “2×10+1″=21.

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

Наконец мы можем начать писать код:

Фигуры имеют определенную ценность. Эти значения нужны, чтобы оценивать позиции на доске и понимать, кто выигрывает. Обычно пешка = 100, конь = 280, слон = 320, ладья = 479, ферзь = 929, а король имеет настолько высокую ценность, что она превосходит 8 ферзей (пешки, превратившиеся в ферзей) в совокупности с парами коней, слонов и ладей. Если мы обладаем всем этим богатством, но теряем короля, подсчет все равно покажет, что мы проиграем.

Каждый тип имеет метод переворота (Flip() method), который возвращает то же самое значение после переворота доски перед ходом противника. У фигур он меняет регистр символа фигуры. У клеток он возвращает 119 клеток (считая с другого конца доски). Что касается доски, он копирует все фигуры с клеток в обратном порядке, меняя их регистр.

Генератор ходов

Итак, у нас уже есть «кирпичики» для движка, и теперь мы можем подумать об игровых позициях. Позиция — это доска с фигурами и дополнительные состояния в игре, такие как квадрат прохода, блуждающий квадрат и возможности рокировки. Если бы мы хотели упростить игру, мы бы могли повторно использовать тип доски (Board type), но мы создадим отдельный тип позиции (Position type), отвечающий за ходы и оценку доски.

Что такое ход? Это комбинация двух клеток — клетка, на которой фигура находилась до совершения хода, и клетка, куда переместились фигура. Позиция — это шахматная доска со счетом, правилами рокировки для каждого игрока и квадратами прохода / блуждающими квадратами. Оба типа также имеют метод переворота (Flip() method) для ходов соперника.

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

Чтобы сгенерировать все допустимые ходы, нам нужно:

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

Чтобы сделать арифметику направлений более читаемой, мы будем использовать константы направления N/E/S/W:

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

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

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

Но как понять, что мы проигрываем?

Оценка доски

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

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

Гораздо более точный и удивительно простой подход — это таблицы соотношения фигур и клеток (PST — Piece-Square Tables). Для каждой фигуры создается таблица такого же размера, как шахматная доска, где для каждой клетки назначается соответствующая ценность. Эти значения являются эмпирическими, поэтому я просто взял их из движка Sunfish.

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

Чтобы оценить позицию после хода, нам нужно:

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

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

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

Алгоритм поиска

Наиболее распространенный алгоритм поиска в шахматных движках попроще — поиск в глубину, который начинается с корня и спускается до заданного предела глубины, повторяя все возможные ходы перед возвратом. Для каждого хода вычисляется ценность позиции с использованием алгоритма минимакс (minimax) c альфа-бета отсечением (alpha-beta pruning).

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

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

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

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

В нашем движке мы будем постепенно увеличивать глубину поиска и вызывать алгоритм MDF(f) для поиска нижних и верхних границ оптимального результата. Алгоритм MDF (f) будет использовать итерации альфа-бета отсечения с кэшем транспозиции.

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

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

Что дальше?

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

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

Да, он слабенький, но он играет настоящие шахматные партии!

Надеюсь, вам понравилась эта статья. Вы можете подписаться на меня в Github, Twitter или подписаться через rss.

Name already in use

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Создайте приложение, которое будет рисовать шахматную доску

About

Создайте приложение, которое будет рисовать шахматную доску

Resources

Stars

Watchers

Forks

Releases

Packages 0

Languages

Footer

© 2023 GitHub, Inc.

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.