Как сделать шахматную доску в js
Обновлено: 17.05.2024
. с условием, что данный AI будет играть получше, чем вот это, хотя насчёт этого не уверен :)
1. Генерация ходов и отрисовка доски
Эти рутинные задачи способны съесть значительную часть времени разработки.
- генерацию ходов и проверку всех правил шахмат может сделать chess.js, с её помощью мы рассчитаем все возможные из текущей позиции ходы;
- с визуализацией доски поможет chessboard.js, мы её выкачаем и единственное, что изменим - настроим путь по умолчанию к картинкам (установкой свойства cfg.pieceTheme ), чтобы не зависить от внешнего сервера.
Сами картинки с шахматными фигурами легко найти где угодно.
Для работы понадобится также общепринятая сегодня Javascript-библиотека JQuery, можно скачать и её, но мы просто подключим её извне.
В программе нам останется сделать что-то вроде:
Таким образом, рутина выполнена, а предстоит лишь реализовать алгоритм выбора лучшего хода из тех, что предложит библиотека.
Начнём с функции, которая выберет случайный ход из всех возможных, она не слишком интеллектуальна, но отправной точкой может служить, своего рода Monkey Chess:
2. Оценка позиции
Попробуем вычислить, какая из сторон сильнее в некоторой заданной позиции. Для этого нам понадобится таблица относительной силы фигур. Существуют разные версии этих таблиц, мы остановимся на следующей:
Сила короля так велика потому, что его надо защищать от шаха ("взятия"). Для чёрных фигур значения силы будут браться с отрицательным знаком, чтобы оценку позиции можно было выразить одним числом, как в реальных "движках", где знак "+" в числе оценки означает перевес белых, а "-" - чёрных.
Теперь имеет смысл изменить метод calculateBestMove так, чтобы он выбирал ход с наивысшей (или с "наинизшей", если для чёрных) оценкой:
Предполагается, что метод evaluateBoard возвращает оценку переданной ему позиции, а остальные методы уже есть в подключённых библиотеках.
Единственное преимущество, которого мы пока что достигли - теперь алгоритм съест фигуру, если это возможно.
3. Дерево поиска и минимакс
Оценка позиции зависит не только от того, что сейчас на доске, но и от того, каких преимуществ можно добиться ближайшими ходами или каких опасностей нужно ими избежать.
Для пошаговых игр с нулевой суммой, к которым относятся и шахматы, изобретать велосипед не нужно, ведь давно придуман алгоритм минимакс. Его суть в том, что рекурсивное дерево всех возможных ходов игры исследуется до заданной глубины, а позиция оценивается на "листьях" этого дерева.
После этого функция возвращает либо наименьшее, либо наибольшее значение потомка в родительский узел, в зависимости от того, чей просчитывается ход, то есть, мы стараемся минимизировать или максимизировать результат на каждом уровне.
Для простых игр, вроде крестиков-ноликов, существует полное дерево игры, следовательно, можно реализовать "непобедимый" алгоритм, для шахмат построение такого дерева нереально, но с небольшой глубиной расчета depth в 2-3 хода Javascript вполне справится:
Ожидаемое улучшение работы - с минимаксом алгоритм начинает понимать основную тактику шахмат, такую как создание угрозы или уход от неё.
Эффективность минимакса в значительной степени зависит от достижимой глубины поиска, но с её увеличением количество оцениваемых позиций растёт слишком быстро.
Именно эту проблему предстоит решать любому шахматному программисту на следующем шаге.
4. Альфа-бета отсечение
Так называется метод оптимизации алгоритма "Минимакс", позволяющий игнорировать некоторые "бесперспективные" ветви в дереве поиска. Это даёт возможность на тех же самых вычислительных ресурсах повысить глубину оценивания для "перспективных" вариантов и не оценивать варианты бессмысленные.
Альфа-бета отсечение основано на том соображении, что мы можем перестать оценивать часть дерева поиска, если найдем шаг, который приводит к худшей ситуации чем та, к которой приводил ранее обнаруженный шаг.
Конечно, "красивым жертвам" это отсечение наш алгоритм не научит, но глубже просчитать форсированный выигрыш поможет.
Алгоритм будет более эффективен, если мы сначала проверим те пути, которые ведут к "хорошим" ходам, то есть, имеющим лучшую оценку за текущий цвет. Отсечение может существенно улучшить работу минимакса.
5. Улучшение функции оценки
Первоначальная функция оценки позиции очень примитивна, она просто подсчитывает суммарный вес материала на доске. Чтобы улучшить оценку, нужно учесть положение фигур. Например, конь сильнее в центре доски, чем на её краю, а слон в углу контролирует меньше полей, чем на другом поле.
Для учёта этого позиционного фактора имеются квадратные таблицы (Piece-Square Tables), описанные в Chess Programming Wiki. Скорректировав или подобрав нужные веса, добавим в программу массивы размерностью 8x8 для каждого из типов фигур - pawnEvalWhite , pawnEvalBlack , bishopEvalWhite и т.д. Функция getPieceValue , возвращающая "силу" фигуры, будет учитывать её положение как "плюс" или "минус" к базовой силе фигуры:
Применив это улучшение, мы получаем код, который играет в шахматы уже чуть сильнее условной "обезьяны", по крайней мере, зевать в один ход не должен. Хотя стратегического видения ситуации, разумеется, алгоритму недостаёт.
Внимательный анализ файла js/script.js из прилагаемого листинга поможет вам понять детали, а нам остаётся написать служебные методы для настройки параметров игры и разметку HTML, которая всё подключит и запустит (файл index.html ):
Увы, Javascript - медленный язык и при глубине расчёта выше 3 скрипт может довольно заметно "тормозить".
- более гибкий выбор ходов - например, при нескольких ходах с близкой оценкой можно брать любой из них;
- улучшение генерации ходов; ; .
Данная статья является вольным переводом и дополнением вот этого первоисточника, там можно почитать несколько меньший текст на английском и посмотреть больше картинок :)
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
17 contributors
Users who have contributed to this file
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
chess.js is a Javascript chess library that is used for chess move generation/validation, piece placement/movement, and check/checkmate/stalemate detection - basically everything but the AI.
chess.js has been extensively tested in node.js and most modern browsers.
Run the following command to install the most recent version of chess.js from NPM:
TypeScript type definitions for chess.js are provided by the community-supported DefinitelyTyped repository and can be installed via:
The code below plays a random game of chess:
By design, chess.js is headless and does not include user interface. Many developers have had success integrating chess.js with the chessboard.js library. See chessboard.js - Random vs Random for an example.
Constructor: Chess([ fen ])
The Chess() constructor takes an optional parameter which specifies the board configuration in Forsyth-Edwards Notation.
Returns a string containing an ASCII diagram of the current position.
Returns an 2D array representation of the current position. Empty squares are represented by null .
Clears the board.
Delete and return the comment for the current position, if it exists.
Delete and return comments for all positions.
Returns the FEN string for the current position.
Returns true if the game has ended via checkmate, stalemate, draw, threefold repetition, or insufficient material. Otherwise, returns false.
Retrieve the comment for the current position, if it exists.
Retrieve comments for all positions.
Allows header information to be added to PGN output. Any number of key/value pairs can be passed to .header().
Calling .header() without any arguments returns the header information as an object.
Returns a list containing the moves of the current game. Options is an optional parameter which may contain a 'verbose' flag. See .moves() for a description of the verbose move fields.
Returns true or false if the side to move is in check.
Returns true or false if the side to move has been checkmated.
Returns true or false if the game is drawn (50-move rule or insufficient material).
Returns true or false if the side to move has been stalemated.
Returns true or false if the current board position has occurred three or more times.
Returns true if the game is drawn due to insufficient material (K vs. K, K vs. KB, or K vs. KN) otherwise false.
The board is cleared, and the FEN string is loaded. Returns true if the position was successfully loaded, otherwise false.
Load the moves of a game stored in Portable Game Notation. pgn should be a string. Options is an optional object which may contain a string newline_char and a boolean sloppy .
The newline_char is a string representation of a valid RegExp fragment and is used to process the PGN. It defaults to \r?\n . Special characters should not be pre-escaped, but any literal special characters should be escaped as is normal for a RegExp. Keep in mind that backslashes in JavaScript strings must themselves be escaped (see sloppy_pgn example below). Avoid using a newline_char that may occur elsewhere in a PGN, such as . or x , as this will result in unexpected behavior.
The sloppy flag is a boolean that permits chess.js to parse moves in non-standard notations. See .move documentation for more information about non-SAN notations.
The method will return true if the PGN was parsed successfully, otherwise false .
Attempts to make a move on the board, returning a move object if the move was legal, otherwise null. The .move function can be called two ways, by passing a string in Standard Algebraic Notation (SAN):
Or by passing .move() a move object (only the 'to', 'from', and when necessary 'promotion', fields are needed):
An optional sloppy flag can be used to parse a variety of non-standard move notations:
Returns a list of legal moves from the current position. The function takes an optional parameter which controls the single-square move generation and verbosity.
The piece, captured, and promotion fields contain the lowercase representation of the applicable piece.
The flags field in verbose mode may contain one or more of the following values:
- 'n' - a non-capture
- 'b' - a pawn push of two squares
- 'e' - an en passant capture
- 'c' - a standard capture
- 'p' - a promotion
- 'k' - kingside castling
- 'q' - queenside castling
A flag of 'pc' would mean that a pawn captured a piece on the 8th rank and promoted.
Returns the game in PGN format. Options is an optional parameter which may include max width and/or a newline character settings.
Place a piece on the square where piece is an object with the form < type: . color: . >. Returns true if the piece was successfully placed, otherwise, the board remains unchanged and false is returned. put() will fail when passed an invalid piece or square, or when two or more kings of the same color are placed.
Remove and return the piece on square.
Reset the board to the initial starting position.
Comment on the current position.
Returns the color of the square ('light' or 'dark').
Returns the current side to move.
Takeback the last half-move, returning a move object if successful, otherwise null.
Returns a validation object specifying validity or the errors found within the FEN string.
- The en passant square and castling flags aren't adjusted when using the put/remove functions (workaround: use .load() instead)
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.
chess.js is a Javascript chess library that is used for chess move generation/validation, piece placement/movement, and check/checkmate/stalemate detection - basically everything but the AI.
chess.js has been extensively tested in node.js and most modern browsers.
Run the following command to install the most recent version of chess.js from NPM:
TypeScript type definitions for chess.js are provided by the community-supported DefinitelyTyped repository and can be installed via:
The code below plays a random game of chess:
By design, chess.js is headless and does not include user interface. Many developers have had success integrating chess.js with the chessboard.js library. See chessboard.js - Random vs Random for an example.
Constructor: Chess([ fen ])
The Chess() constructor takes an optional parameter which specifies the board configuration in Forsyth-Edwards Notation.
Returns a string containing an ASCII diagram of the current position.
Returns an 2D array representation of the current position. Empty squares are represented by null .
Clears the board.
Delete and return the comment for the current position, if it exists.
Delete and return comments for all positions.
Returns the FEN string for the current position.
Returns true if the game has ended via checkmate, stalemate, draw, threefold repetition, or insufficient material. Otherwise, returns false.
Retrieve the comment for the current position, if it exists.
Retrieve comments for all positions.
Allows header information to be added to PGN output. Any number of key/value pairs can be passed to .header().
Calling .header() without any arguments returns the header information as an object.
Returns a list containing the moves of the current game. Options is an optional parameter which may contain a 'verbose' flag. See .moves() for a description of the verbose move fields.
Returns true or false if the side to move is in check.
Returns true or false if the side to move has been checkmated.
Returns true or false if the game is drawn (50-move rule or insufficient material).
Returns true or false if the side to move has been stalemated.
Returns true or false if the current board position has occurred three or more times.
Returns true if the game is drawn due to insufficient material (K vs. K, K vs. KB, or K vs. KN) otherwise false.
The board is cleared, and the FEN string is loaded. Returns true if the position was successfully loaded, otherwise false.
Load the moves of a game stored in Portable Game Notation. pgn should be a string. Options is an optional object which may contain a string newline_char and a boolean sloppy .
The newline_char is a string representation of a valid RegExp fragment and is used to process the PGN. It defaults to \r?\n . Special characters should not be pre-escaped, but any literal special characters should be escaped as is normal for a RegExp. Keep in mind that backslashes in JavaScript strings must themselves be escaped (see sloppy_pgn example below). Avoid using a newline_char that may occur elsewhere in a PGN, such as . or x , as this will result in unexpected behavior.
The sloppy flag is a boolean that permits chess.js to parse moves in non-standard notations. See .move documentation for more information about non-SAN notations.
The method will return true if the PGN was parsed successfully, otherwise false .
Attempts to make a move on the board, returning a move object if the move was legal, otherwise null. The .move function can be called two ways, by passing a string in Standard Algebraic Notation (SAN):
Or by passing .move() a move object (only the 'to', 'from', and when necessary 'promotion', fields are needed):
An optional sloppy flag can be used to parse a variety of non-standard move notations:
Returns a list of legal moves from the current position. The function takes an optional parameter which controls the single-square move generation and verbosity.
The piece, captured, and promotion fields contain the lowercase representation of the applicable piece.
The flags field in verbose mode may contain one or more of the following values:
- 'n' - a non-capture
- 'b' - a pawn push of two squares
- 'e' - an en passant capture
- 'c' - a standard capture
- 'p' - a promotion
- 'k' - kingside castling
- 'q' - queenside castling
A flag of 'pc' would mean that a pawn captured a piece on the 8th rank and promoted.
Returns the game in PGN format. Options is an optional parameter which may include max width and/or a newline character settings.
Place a piece on the square where piece is an object with the form < type: . color: . >. Returns true if the piece was successfully placed, otherwise, the board remains unchanged and false is returned. put() will fail when passed an invalid piece or square, or when two or more kings of the same color are placed.
Remove and return the piece on square.
Reset the board to the initial starting position.
Comment on the current position.
Returns the color of the square ('light' or 'dark').
Returns the current side to move.
Takeback the last half-move, returning a move object if successful, otherwise null.
Returns a validation object specifying validity or the errors found within the FEN string.
- The en passant square and castling flags aren't adjusted when using the put/remove functions (workaround: use .load() instead)
About
A Javascript chess library for chess move generation/validation, piece placement/movement, and check/checkmate/draw detection
Для реализации мы воспользуемся библиотеками JavaScript: chessboard.js позволит визуализировать доску, а chess.js – сгенерировать возможные перемещения.
Но не все так просто. Библиотеки JavaScript создадут только базис, а самое интересное – это алгоритм для определения оптимального хода. Начнем с функции, которая возвращает случайный ход из всех возможных:
Такой алгоритм шахмат не самый лучший, но это лишь отправная точка.
Определяем значимость каждой фигуры:
С помощью приведенного кода создаем алгоритм шахмат, который выбирает ход в соответствии с оценкой важности каждой фигуры:
Создаем дерево поиска, с помощью которого выбирается лучший ход. Для этого используется алгоритм минимакс. Рекурсивное дерево всех возможных перемещений исследуется до заданной глубины, а сама позиция – это «листья». После анализа возвращается или наименьшее, или наибольшее значение, в зависимости от того, какой цвет шахмат задействован.
Алгоритм начинает понимать тактику, но эффективность зависит от глубины поиска, что мы улучшим на следующих этапах.
Это оптимизация алгоритма минимакс, благодаря которой некоторые ветки поиска игнорируются. Принцип действия альфа-бета-отсечения основывается на том, что часть дерева не оценивается, если найден ход, гарантирующий худшее развитие, чем в шаге более раннем. Таким образом, алгоритм минимакс ускоряется и становится эффективным, если сперва находит хорошие варианты.
Изначальная оценка позиции в шахматах малоэффективна, ведь просто подсчитывается все то, что есть на доске. Это улучшается добавлением фактора, который учитывает положение фигур. Например, слон в центре предоставляет больше возможностей, чем слон на краю доски. Мы используем скорректированную версию, взятую с Wikispaces.
На выходе получаем ИИ шахматы на JavaScript с алгоритмом, который может продемонстрировать неплохую игру.
Рассмотрим некоторые базовые концепции, которые помогут нам создать простой искусственный интеллект, умеющий играть в шахматы:
- перемещение;
- оценка шахматной доски;
- минимакс;
- альфа-бета-отсечение.
На каждом шаге мы будем улучшать наш алгоритм с помощью одного из этих проверенных временем методов шахматного программирования. Вы увидите, как каждый из них влияет на стиль игры алгоритма.
Готовый алгоритм можно найти на GitHub.
Шаг 1. Генерация ходов и визуализация шахматной доски
Мы будем использовать библиотеки chess.js для генерации ходов и chessboard.js для визуализации доски. Библиотека для генерации ходов реализует все правила шахмат. Исходя из этого, мы можем рассчитать все ходы для данного состояния доски.
Визуализация функции генерации движения. Исходное положение используется как вход, а на выходе — все возможные ходы из этой позиции.
Использование этих библиотек поможет нам сосредоточиться только на самой интересной задаче — создании алгоритма, который находит лучший ход. Мы начнем с написания функции, которая возвращает случайный ход из всех возможных ходов:
Хотя этот алгоритм не очень солидный шахматист, но это хорошая отправная точка, поскольку его уровня достаточно, чтобы сыграть с нами:
Черные играют случайными ходами
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Шаг 2. Оценка доски
Теперь попробуем понять, какая из сторон сильнее в определенном положении. Самый простой способ добиться этого — посчитать относительную силу фигур на доске, используя следующую таблицу:
С помощью функции оценки мы можем создать алгоритм, который выбирает ход с наивысшей оценкой:
Единственным ощутимым улучшением является то, что теперь наш алгоритм съест фигуру, если это возможно:
Черные играют с помощью простой функции оценки
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Шаг 3. Дерево поиска и минимакс
Затем мы создадим дерево поиска, из которого алгоритм может выбрать лучший ход. Это делается с помощью алгоритма «минимакс».
Прим. перев. В одной из наших статей мы уже имели дело с минимаксом — учились создавать ИИ, который невозможно обыграть в крестики-нолики.
В этом алгоритме рекурсивное дерево всех возможных ходов исследуется до заданной глубины, а позиция оценивается на «листьях» дерева.
После этого мы возвращаем либо наименьшее, либо наибольшее значение потомка в родительский узел, в зависимости от того, чей просчитывается ход (то есть мы стараемся минимизировать или максимизировать результат на каждом уровне).
Визуализация минимакса в искусственном положении. Лучший ход для белых — b2-c3, так мы можем гарантировать, что доберемся до позиции, где оценка равна -50
С минимаксом наш алгоритм начинает понимать основную тактику шахмат:
Минимакс с уровнем глубины 2
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Эффективность минимакса в значительной степени зависит от достижимой глубины поиска. Именно это мы улучшим на следующем шаге.
Шаг 4. Альфа-бета-отсечение
Альфа-бета-отсечение — это метод оптимизации алгоритма «минимакс», который позволяет игнорировать некоторые ветви в дереве поиска. Это позволяет нам намного глубже оценить дерево поиска, используя те же ресурсы.
Альфа-бета-отсечение основано на ситуации, когда мы можем прекратить оценивать часть дерева поиска, если найдем шаг, который приведет к худшей ситуации, чем та, к которой приводил ранее обнаруженный шаг.
Альфа-бета-отсечение не влияет на результат минимакса, оно только ускоряет его.
Этот алгоритм будет более эффективным, если мы сначала проверим те пути, которые ведут к хорошим ходам:
Позиции, которые нам не нужны, если используется альфа-бета-отсечение. Дерево посещается в описанном порядке.
С альфа-бета-отсечением мы получаем значительное улучшение минимакса, как показано в следующем примере:
Количество позиций, которые нужно оценить в случае поиска с глубиной 4 и начальной позицией, изображённой на картинке.
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Шаг 5. Улучшенная функция оценки
Первоначальная функция оценки довольно наивна, поскольку мы просто подсчитываем очки фигур, которые находятся на доске. Чтобы улучшить её, мы начнём учитывать положение фигур. Например, конь в центре доски «дороже», потому что он имеет больше доступных ходов и, следовательно, более активен, чем конь на краю доски.
Мы будем использовать слегка скорректированную версию квадратных таблиц, первоначально описанных в вики Chess Programming.
Визуализация квадратных таблиц. Мы можем уменьшить или увеличить оценку в зависимости от местоположения фигуры.
Применив это улучшение, мы получим алгоритм, который неплохо играет в шахматы, по крайней мере, с точки зрения простого игрока:
Улучшенная оценка и альфа-бета-отсечение с глубиной поиска 3
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Заключение
Сила даже простого шахматного алгоритма состоит в том, что он не совершает глупых ошибок. Тем не менее, ему по-прежнему не хватает стратегического взгляда на ситуацию.
С помощью методов, которые представлены здесь, мы смогли запрограммировать шахматный алгоритм, который может неплохо играть в шахматы. В финальном алгоритме реализация ИИ занимает всего 200 строк кода — это означает, что базовые принципы довольно просты. Вы можете посмотреть окончательную версию программы на GitHub.
Вот некоторые дополнительные улучшения, которые мы могли бы внести в алгоритм:
- упорядочивание ходов;
- ускорение генерации ходов;
- оценка эндшпиля.
Если вы хотите узнать о шахматных алгоритмах больше, зайдите на Chess Programming Wiki.
Читайте также: