Nickolay.info. Javascript. Пример играющего шахматного скрипта на Javascript
В этой заметке можно поиграть в простенькие шахматы на Javascript, а также скачать себе исходники скрипта.
Игра в шахматы с компьютером онлайн бесплатно без регистрации
компьютер играет белыми компьютер играет черными
Превращать пешки в
Для игры в бесплатные шахматы с компьютером в Вашем браузере должна быть включена поддержка JavaScript.
Для выполнения хода Вам необходимо сделать два клика мышкой: после первого клика мышкой по фигуре на шахматном поле это поле выделяется цветом, после второго клика на другом поле фигура перемещается на это указанное поле. Если Вы передумали ходить выделенной фигурой после щелчка по ней, щёлкните ещё раз по той же фигуре для отмены.
В данной игре на JavaScript реализован простой шахматный алгоритм.
По умолчанию компьютер будет играть черными (установлен флажок «компьютер играет черными»), поэтому можете смело сделать первый ход белыми: e2-e4. Лог игры (запись проведенных игроками ходов) появится на экране под словами Лог игры.
Если Вы захотите сыграть партию с другом, тогда вам следует снять оба флажка и начнется партия для двух человек, компьютер не будет вмешиваться в игровой процесс.
Если Вы хотите понаблюдать за игрой компьютер-компьютер, то следует включить оба флажка.
Чтобы сыграть повторно, обновите эту страницу.
Правила игры в шахматы можно быстро изучить здесь.
Есть и ещё более «крутые» реализации, например, в исходнике страницы по следующей ссылке можно увидеть шахматную программу на Javascript размером. в 1 килобайт! Правда, играет она очень слабо и «забывает» о некоторых правилах, вроде рокировки:
Скачать исходник простых шахмат на Javascript в архиве ZIP (39 Кб)
. с условием, что данный AI будет играть получше, чем вот это, хотя насчёт этого не уверен 🙂
1. Генерация ходов и отрисовка доски
Эти рутинные задачи способны съесть значительную часть времени разработки.
Сами картинки с шахматными фигурами легко найти где угодно.
Для работы понадобится также общепринятая сегодня Javascript-библиотека JQuery, можно скачать и её, но мы просто подключим её извне.
В программе нам останется сделать что-то вроде:
Таким образом, рутина выполнена, а предстоит лишь реализовать алгоритм выбора лучшего хода из тех, что предложит библиотека.
Начнём с функции, которая выберет случайный ход из всех возможных, она не слишком интеллектуальна, но отправной точкой может служить, своего рода Monkey Chess:
Попробуем вычислить, какая из сторон сильнее в некоторой заданной позиции. Для этого нам понадобится таблица относительной силы фигур. Существуют разные версии этих таблиц, мы остановимся на следующей:
Теперь имеет смысл изменить метод calculateBestMove так, чтобы он выбирал ход с наивысшей (или с «наинизшей», если для чёрных) оценкой:
Предполагается, что метод evaluateBoard возвращает оценку переданной ему позиции, а остальные методы уже есть в подключённых библиотеках.
3. Дерево поиска и минимакс
Оценка позиции зависит не только от того, что сейчас на доске, но и от того, каких преимуществ можно добиться ближайшими ходами или каких опасностей нужно ими избежать.
Для пошаговых игр с нулевой суммой, к которым относятся и шахматы, изобретать велосипед не нужно, ведь давно придуман алгоритм минимакс. Его суть в том, что рекурсивное дерево всех возможных ходов игры исследуется до заданной глубины, а позиция оценивается на «листьях» этого дерева.
После этого функция возвращает либо наименьшее, либо наибольшее значение потомка в родительский узел, в зависимости от того, чей просчитывается ход, то есть, мы стараемся минимизировать или максимизировать результат на каждом уровне.
Для простых игр, вроде крестиков-ноликов, существует полное дерево игры, следовательно, можно реализовать «непобедимый» алгоритм, для шахмат построение такого дерева нереально, но с небольшой глубиной расчета depth в 2-3 хода Javascript вполне справится:
Эффективность минимакса в значительной степени зависит от достижимой глубины поиска, но с её увеличением количество оцениваемых позиций растёт слишком быстро.
Именно эту проблему предстоит решать любому шахматному программисту на следующем шаге.
4. Альфа-бета отсечение
Так называется метод оптимизации алгоритма «Минимакс», позволяющий игнорировать некоторые «бесперспективные» ветви в дереве поиска. Это даёт возможность на тех же самых вычислительных ресурсах повысить глубину оценивания для «перспективных» вариантов и не оценивать варианты бессмысленные.
Альфа-бета отсечение основано на том соображении, что мы можем перестать оценивать часть дерева поиска, если найдем шаг, который приводит к худшей ситуации чем та, к которой приводил ранее обнаруженный шаг.
Конечно, «красивым жертвам» это отсечение наш алгоритм не научит, но глубже просчитать форсированный выигрыш поможет.
Алгоритм будет более эффективен, если мы сначала проверим те пути, которые ведут к «хорошим» ходам, то есть, имеющим лучшую оценку за текущий цвет. Отсечение может существенно улучшить работу минимакса.
5. Улучшение функции оценки
Первоначальная функция оценки позиции очень примитивна, она просто подсчитывает суммарный вес материала на доске. Чтобы улучшить оценку, нужно учесть положение фигур. Например, конь сильнее в центре доски, чем на её краю, а слон в углу контролирует меньше полей, чем на другом поле.
Применив это улучшение, мы получаем код, который играет в шахматы уже чуть сильнее условной «обезьяны», по крайней мере, зевать в один ход не должен. Хотя стратегического видения ситуации, разумеется, алгоритму недостаёт.
Внимательный анализ файла js/script.js из прилагаемого листинга поможет вам понять детали, а нам остаётся написать служебные методы для настройки параметров игры и разметку HTML, которая всё подключит и запустит (файл index.html ):
Данная статья является вольным переводом и дополнением вот этого первоисточника, там можно почитать несколько меньший текст на английском и посмотреть больше картинок 🙂
На пути к Deep Blue: пошаговое руководство по созданию простого ИИ для игры в шахматы
Авторизуйтесь
На пути к Deep Blue: пошаговое руководство по созданию простого ИИ для игры в шахматы
Рассмотрим некоторые базовые концепции, которые помогут нам создать простой искусственный интеллект, умеющий играть в шахматы:
На каждом шаге мы будем улучшать наш алгоритм с помощью одного из этих проверенных временем методов шахматного программирования. Вы увидите, как каждый из них влияет на стиль игры алгоритма.
Готовый алгоритм можно найти на GitHub.
Шаг 1. Генерация ходов и визуализация шахматной доски
Мы будем использовать библиотеки chess.js для генерации ходов и chessboard.js для визуализации доски. Библиотека для генерации ходов реализует все правила шахмат. Исходя из этого, мы можем рассчитать все ходы для данного состояния доски.
Визуализация функции генерации движения. Исходное положение используется как вход, а на выходе — все возможные ходы из этой позиции.
Использование этих библиотек поможет нам сосредоточиться только на самой интересной задаче — создании алгоритма, который находит лучший ход. Мы начнем с написания функции, которая возвращает случайный ход из всех возможных ходов:
Хотя этот алгоритм не очень солидный шахматист, но это хорошая отправная точка, поскольку его уровня достаточно, чтобы сыграть с нами:
Черные играют случайными ходами
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Шаг 2. Оценка доски
Теперь попробуем понять, какая из сторон сильнее в определенном положении. Самый простой способ добиться этого — посчитать относительную силу фигур на доске, используя следующую таблицу:
С помощью функции оценки мы можем создать алгоритм, который выбирает ход с наивысшей оценкой:
Единственным ощутимым улучшением является то, что теперь наш алгоритм съест фигуру, если это возможно:
Черные играют с помощью простой функции оценки
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Шаг 3. Дерево поиска и минимакс
Затем мы создадим дерево поиска, из которого алгоритм может выбрать лучший ход. Это делается с помощью алгоритма «минимакс».
Прим. перев. В одной из наших статей мы уже имели дело с минимаксом — учились создавать ИИ, который невозможно обыграть в крестики-нолики.
В этом алгоритме рекурсивное дерево всех возможных ходов исследуется до заданной глубины, а позиция оценивается на «листьях» дерева.
1 октября – 30 ноября, Онлайн, Беcплатно
После этого мы возвращаем либо наименьшее, либо наибольшее значение потомка в родительский узел, в зависимости от того, чей просчитывается ход (то есть мы стараемся минимизировать или максимизировать результат на каждом уровне).
С минимаксом наш алгоритм начинает понимать основную тактику шахмат:
Минимакс с уровнем глубины 2
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Эффективность минимакса в значительной степени зависит от достижимой глубины поиска. Именно это мы улучшим на следующем шаге.
Шаг 4. Альфа-бета-отсечение
Альфа-бета-отсечение — это метод оптимизации алгоритма «минимакс», который позволяет игнорировать некоторые ветви в дереве поиска. Это позволяет нам намного глубже оценить дерево поиска, используя те же ресурсы.
Альфа-бета-отсечение основано на ситуации, когда мы можем прекратить оценивать часть дерева поиска, если найдем шаг, который приведет к худшей ситуации, чем та, к которой приводил ранее обнаруженный шаг.
Альфа-бета-отсечение не влияет на результат минимакса, оно только ускоряет его.
Этот алгоритм будет более эффективным, если мы сначала проверим те пути, которые ведут к хорошим ходам:
Позиции, которые нам не нужны, если используется альфа-бета-отсечение. Дерево посещается в описанном порядке.
С альфа-бета-отсечением мы получаем значительное улучшение минимакса, как показано в следующем примере:
Количество позиций, которые нужно оценить в случае поиска с глубиной 4 и начальной позицией, изображённой на картинке.
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Шаг 5. Улучшенная функция оценки
Первоначальная функция оценки довольно наивна, поскольку мы просто подсчитываем очки фигур, которые находятся на доске. Чтобы улучшить её, мы начнём учитывать положение фигур. Например, конь в центре доски «дороже», потому что он имеет больше доступных ходов и, следовательно, более активен, чем конь на краю доски.
Мы будем использовать слегка скорректированную версию квадратных таблиц, первоначально описанных в вики Chess Programming.
Визуализация квадратных таблиц. Мы можем уменьшить или увеличить оценку в зависимости от местоположения фигуры.
Применив это улучшение, мы получим алгоритм, который неплохо играет в шахматы, по крайней мере, с точки зрения простого игрока:
Улучшенная оценка и альфа-бета-отсечение с глубиной поиска 3
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.
Заключение
Сила даже простого шахматного алгоритма состоит в том, что он не совершает глупых ошибок. Тем не менее, ему по-прежнему не хватает стратегического взгляда на ситуацию.
С помощью методов, которые представлены здесь, мы смогли запрограммировать шахматный алгоритм, который может неплохо играть в шахматы. В финальном алгоритме реализация ИИ занимает всего 200 строк кода — это означает, что базовые принципы довольно просты. Вы можете посмотреть окончательную версию программы на GitHub.
Вот некоторые дополнительные улучшения, которые мы могли бы внести в алгоритм:
Если вы хотите узнать о шахматных алгоритмах больше, зайдите на Chess Programming Wiki.
Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.
Nickolay.info. JavaScript. Шахматная «ходилка» на JavaScript
updated! Показанная ниже ходилка разрабатывалась в 2009-10 гг, с тех пор и прогресс, и Javascript шагнули далеко вперёд 🙂 Новая ходилка, основанная на библиотеках chess.js и chessboard.js, доступна в этой заметке блога, а старая, увы, больше обновляться не будет.
Другие версии скрипта можно получить здесь:
Понадобилась на одном из проектов встроенная в «движок» шахматная доска с возможностью задавать расстановки фигур, двигать шахматные фигуры по правилам и сохранять полученные позиции в одном из общепринятых форматов. Разумеется, речь не о том, чтобы реализовать на JavaScipt полноценные шахматы, но вдвоём на такой доске можно даже и поиграть.
Оказалось, велосипед изобретать не нужно, а можно воспользоваться частично готовым GUI от человека с ником Мистик (возможно, есть более новая ссылка на него).
Я позволил себе немного изменить его скрипт, а именно, русифицировать интерфейс и систему сообщений, приделать русскую же помощь, исправить незначительные ошибки JavaScript и неудобства, добавить к доске всплывающие подсказки с обозначениями полей и т.п.
Выглядит «ходилка» так (фигуры уже можно перетаскивать мышкой):
Все правила шахмат учитываются, так что сходить неправильно скрипт не даёт, очередность ходов также соблюдается.
Для записи позиций используется стандартная нотация Форсайта—Эдвардса, причём, можно задать позицию с помощью соответствующей кнопки формы, а текущая позиция в этой же нотации выводится под доской.
Код для подключения на свой сайт шахматной ходилки может быть, например, таким:
можно заменить на свой URL к файлам скрипта. Но можно оставить и этот, т.к. скрипт поправленный и будет лежать здесь 🙂
3. Почему не работает вместе с JQuery?
В последней версии, выложенной здесь, функция уже переименована, так что проблемы совместимости с JQuery быть не должно.
4. Скачал, развернул, запустил, вижу только «чёрные квадратики» вместо букв в нотации?
Укажите на странице с кодами скрипта кодировку Windows-1251 мета-тегом
или перекодируйте файлы скрипта в нужную вам кодировку, например, в Юникод.
5. Не получилось подключить несколько досок на одну страницу, вывод «перепутывается»?
6. В Internet Explorer не увидел фона полей под картинками?
Рассмотрим ИИ шахматы на JavaScript и основные принципы его создания, к которым относятся генерация ходов, оценка позиции, минимакс и альфа-бета-отсечение.
Интересуетесь искусственным интеллектом? Тогда познакомьтесь с созданием шахмат 🙂
1. Визуализация доски и перебор ходов
Для реализации мы воспользуемся библиотеками JavaScript: chessboard.js позволит визуализировать доску, а chess.js – сгенерировать возможные перемещения.
Но не все так просто. Библиотеки JavaScript создадут только базис, а самое интересное – это алгоритм для определения оптимального хода. Начнем с функции, которая возвращает случайный ход из всех возможных:
Такой алгоритм шахмат не самый лучший, но это лишь отправная точка.
2. Оценка позиции в шахматах
Определяем значимость каждой фигуры:
С помощью приведенного кода создаем алгоритм шахмат, который выбирает ход в соответствии с оценкой важности каждой фигуры:
3. Правило принятия решений
Создаем дерево поиска, с помощью которого выбирается лучший ход. Для этого используется алгоритм минимакс. Рекурсивное дерево всех возможных перемещений исследуется до заданной глубины, а сама позиция – это «листья». После анализа возвращается или наименьшее, или наибольшее значение, в зависимости от того, какой цвет шахмат задействован.
Алгоритм начинает понимать тактику, но эффективность зависит от глубины поиска, что мы улучшим на следующих этапах.
4. Альфа-бета-отсечение
Это оптимизация алгоритма минимакс, благодаря которой некоторые ветки поиска игнорируются. Принцип действия альфа-бета-отсечения основывается на том, что часть дерева не оценивается, если найден ход, гарантирующий худшее развитие, чем в шаге более раннем. Таким образом, алгоритм минимакс ускоряется и становится эффективным, если сперва находит хорошие варианты.
5. Улучшенная оценка
Изначальная оценка позиции в шахматах малоэффективна, ведь просто подсчитывается все то, что есть на доске. Это улучшается добавлением фактора, который учитывает положение фигур. Например, слон в центре предоставляет больше возможностей, чем слон на краю доски. Мы используем скорректированную версию, взятую с Wikispaces.
На выходе получаем ИИ шахматы на JavaScript с алгоритмом, который может продемонстрировать неплохую игру.
Скачать исходник простых шахмат на Javascript в архиве ZIP (39 Кб)
