Как создать шахматы на андроид

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

Было ли вам когда-либо интересно написать свою шахматную программу? Настраивать и развивать её, проверять её на знакомых любителях шахмат и радоваться её победам. Но как написать такую программу? Об этом я и расскажу в этой статье.

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

Программа для Windows.
Ходить можно как вводом хода в поле (E2-E4), так и мышкой — левая кнопка откуда, правая — куда.

Итак, начнём.
Для начала, стоит поискать специальную литературу о том, как же писать шахматные программы. Я из таковых использовал книжку Корнилова “Программирование шахмат и других логических задач” 2005 года. Одной этой книжки оказалось мало – автор не акцентировал внимание на кое-чём важном, а кое-что просто не рассказал. А это кое-что, между прочим, сильно сокращает дерево перебора. Сразу же предупреждаю, что в моём движке не используется генератор ходов на базе битовых массивов. Этот уровень мне пока недоступен. Впрочем, я особо и не пытался разобраться с ними, предпочитая написать как можно более прозрачный (для меня) механизм работы с ходами фигур, пусть даже в ущерб быстродействию (движок получился не очень быстрый, но вполне работоспособный).

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

А сама клетка у меня представлена битами как AHIIIIEWB0MFFF, где:

W-фигура белая
B-фигура чёрная
F-тип фигуры (0-фигуры нет)
M-ходила ли фигура
E-край доски
I-индекс фигуры в массиве для поиска фигур (0-15)
H-была короткая рокировка (флаг ставится только у короля и ладьи)
A-была длинная рокировка (флаг ставится только у короля и ладьи)

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

Дальше следует решить, какого размера будет доска. 8x8 неудобно для анализа выхода за пределы доски. Гораздо удобнее задать массив 16x16 с доской посередине, задав для всех тех клеток, которые не являются доской, флаг границы. В этом случае изменение координаты по X происходит изменением координаты X на нужный шаг, а по Y на шаг*16. Доска задаётся как

Некоторые параметры в дальнейшем будет удобно задавать для поля 8x8, для этой цели стоит завести массив перекодировки координат из поля 16x16 в поле 8x8.

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

Теперь определимся с тем, как мы будем задавать ходы. Очень удобно сделать так:

Здесь в массивах заданы изменения координат в пространстве нашей доски 16x16 для одного шага фигуры. Ходы пешки удобно рассматривать отдельно, так как у неё ходы простые, но есть специфическое взятие на проходе.
Как таким массивом пользоваться? Ну вот, например, составление всех ходов ферзя:

Как видите, всё просто. Для хранения ходов я создал структуру

Хоть массив ходов и задаётся как

, где MAX_PLY – максимальная глубина анализа (а 200 – максимальное число ходов любой фигуры (с запасом)), но указатель на следующий элемент sMove_NextPtr позволяет удобно сортировать ходы (а сортировать их придётся). std::list (или ещё что из stl) я тут не стал использовать – у нас крайне критично быстродействие (да и я не скажу, что мастер в stl и современном Си++, скорее наоборот). Впрочем, вы можете сделать и с помощью stl и сравнить скорость работы программы – я же этого не проверял.

Ну, в целом, с ходами закончили, перейдём к алгоритмам.

Во-первых, нам нужна функция оценки позиции. Тут возможностей просто море. У меня в движке в engine_score.cpp вполне читаемо описано всё то, что я использую для оценки позиции. Там представлены массивы очков за нахождение фигуры в данной клетке поля (для поля 8x8 – так просто удобно задавать).

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

В-третьих, нам нужна хэш-таблица. Дело в том, что в шахматах позиция при переборе часто повторяется – зачем нам заново анализировать то, что уже мы смотрели? Выявить такую позицию и позволяет хэш-таблица. В ней хранятся “уникальные” значения, отличающие одну позицию от другой. Стоятся эти “уникальные” значения просто выполняя операцию xor для ключей элементов, описывающих позицию. Поэтому нам нужны будут массивы уникальных 64 битных чисел (вы можете и любую другую размерность взять, весь вопрос только в том, как часто будут одинаковым значениям позиции соответствовать разные позиции – ошибки хэша). У меня таблица описана так:

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

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

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

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

В-четвертых, нам нужна такая штука, как статистика истории. Что это такое? Во время игры можно заметить, что какие-то ходы улучшают оценку позиции. Стоит этот факт отмечать, запоминать и в дальнейшем использовать при сортировке ходов. Как это сделать? Просто завести массив [64][64] ([начальная позиция фигуры на поле 8x8][конечная позиция фигуры на поле 8x8]), обнулить в начале оценки выбора лучшего хода и в дальнейшем просто увеличивать счётчик на 1 в случае хода, улучшающего для нас оценку позиции.

В-пятых, нам нужна сортировка ходов. Самыми первыми должны быть ходы с максимальной выгодой по оценке позиции. Понятно, что ходы взятия приоритетнее обычных “тихих” ходов. Ходы взятия сортируются по принципу MVV/LVA (наиболее ценная жертва – наименее ценный нападающий). При этом стоит продвигать все необычные ходы со взятием (любой ход, который не имеет тип MOVE_TYPE_SIMPLY). Так же вперёд стоит продвинуть и взятие последней ходившей фигуры противника (если взятие будет). Обычные ходы сортируются по возрастанию оценки позиции с учётом эвристики истории. Вся эта сортировка очень важна! Она и сама по себе позволяет сократить обход дерева игры, но более того, на нижних уровнях дерева можно в принципе выбрасывать почти все “тихие” ходы (и если король не под шахом) из рассмотрения без ущерба для качества игры программы! Я увидел такое в коде шахматной программы Ифрит (Ifrit) и, конечно же, применил. Это называется Late Move Reduction, насколько я понимаю.
Для этого используется следующий массив:

Здесь числа означают то, сколько “тихих” ходов анализируется в зависимости от уровня дерева (массив задан в обратном порядке). То есть, на последних для анализа 9 уровнях дерева в рассмотрении будет сначала 259 ходов, потом 131, потом 67 и так далее до 19. Это сильно ускоряет работу программы (а также об этом Корнилов вроде как тоже не рассказал в своей книжке). Разумеется, без сортировки ходов такое отсечение не заработает.

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

В-седьмых, нам нужна будет эвристика убийцы. Заключается она в том, чтобы при анализе веток дерева пробовать первым ход, вызвавший отсечение на предыдущей ветке. Такой приём также позволяет сократить перебор. Следует помнить, что такой ход может быть только “тихий”: взятия и необычные ходы использовать для таких проверок нельзя.

В-восьмых, есть такая штука, как нулевой ход. Смысл в том, что можно сделать пропуск хода и посмотреть, насколько всё станет плохо. При этом можно сократить глубину анализа дерева (сделать редукцию) – всё равно оценка предварительная. Главное, не забывать пометить хэш позиции ключом этого самого нулевого хода

В-девятых, есть ещё Futility Prunning. Что это такое? На последних двух полуходах дерева оценка позиции не точна и в ряде случаев (если мы не в нулевом ходе, если ход не является шахом, взятием и ход не продление анализа ветки), а также если разность оценки позиции была больше некоторой небольшой величины, то можно просто вернуть эту оценку и не анализировать глубже. Этот приём также ускоряет работу программы.

В-десятых, для сокращения вариантов придуман ещё и Razoring. Это почти то же самое, что и Futility Prunning, но относится к последним четырём полуходам и граница оценки задаётся в некоторую стоимость допустимых потерь фигур.

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

В-двенадцатых, есть ещё такая штука, как Principal Variation (главное изменение). Это та линия игры, которую программа считает лучшей в данный момент. Эта линия постоянно корректируется во время перебора позиций. Ход из главной линии при сортировке стоит продвигать вперёд.

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

В архиве лежит сам движок (он поддерживает UCI, так что можете подключить его к Arena), программа под Windows для игры с ним (на скорую руку), шахматы для QNX 6.3. Уровень игры я точно оценить не могу (я не шахматист, как ни странно), но вроде как играет достаточно неплохо.

Шахматы – это не просто одна из старейших настольных игр, в которые до сих пор играют люди. Это еще и отличный способ провести время в компании своего Android устройства. Можно, не напрягаясь, устроить дружеское шахматное состязание, а можно бросить вызов продвинутым и очень активным членам шахматного сообщества. Чем хороши шахматы, так это тем, что научиться играть в них просто, а вот сам игровой процесс легким не назовешь. Даже если вы впервые узнали, как ходят шахматные фигуры, много лет назад и давно относите себя к продвинутым игрокам, вам все равно будет чему поучиться. Итак, вашему вниманию предлагается подборка лучших шахматных приложений для Android!

Шахматы (Chess Free)

Шахматная игра от разработчика AI Factory Limited – одна из самых популярных игр этого жанра для мобильных устройств. Все, чего может пожелать душа шахматиста, здесь есть. В игре вас ждут 12 уровней сложности, продвинутые режимы игры, чемпионаты и достижения – и даже возможность сохранять свои результаты в облаке. Интерфейс игры прост. Однако вам доступны восемь тем оформления на выбор. В бесплатной версии вы не найдете внутриигровых покупок, но в ней вам придется иметь дело с рекламой. Чтобы избавиться от рекламы, можно купить платную версию за $0.99.

Шахматы – Играй и Учись

Шахматы – Играй и Учись вполне соответствует своему названию. Она позиционируется как одна из шахматных игр вида все-в-одном. Можно играть в одиночестве, а можно бросить вызов другим игрокам онлайн. Есть также пара режимов игры, а вдобавок – более чем 50 000 шахматных головоломок и уроков, чтобы вы могли совершенствоваться в своем мастерстве. Также вы найдете здесь более 20 тем оформления, картинок и фонов. Имеются даже статьи и форумы, так что возможностей стать настоящим гроссмейстером хоть отбавляй. Есть у этой игры и свои недостатки. Во-первых, лаги и проблемы с подключением, а во-вторых, фримиум со всеми вытекающими последствиями. Но недостатки не перевешивают неоспоримых достоинств приложения.

Шахматные головоломки

Шахматные головоломки непохожи на большинство шахматных игр. От обычных шахмат здесь не так уж и много, зато вам предлагается огромное количество шахматных задач. Сюда входят наборы офлайн-головоломок (они доступны в качестве внутриигровых покупок), ежедневные онлайн-головоломки и многое другое. Заявлено, что сложность некоторых заданий может достигать рейтинга ЭЛО свыше 2000. Хороший способ усовершенствовать свои навыки игры и поучиться новым тактическим приемам. Внутриигровые покупки позволят вам получить дополнительный контент, если вам станет мало того, что предлагается бесплатно.

Chess With Friends Free

Chess With Friends – одна из самых популярных бесплатных шахматных онлайн-игр. Здесь у вас есть возможность играть с друзьями или со случайными игроками онлайн. Также есть тренировочный режим для того, чтобы оттачивать свое мастерство. Кроме того, вам доступен внутриигровой чат, возможность переиграть партию, а также опция вести несколько партий одновременно. Игра позиционируется в большей степени как возможность приятно провести время на досуге, так что не стоит ожидать какого-то особого уровня сложности. Тем не менее, здесь отображается рейтинг ЭЛО, поэтому вам будет понятно, против кого вы играете. Игра бесплатна, но в ней есть внутриигровые покупки, которые позволят вам получить всевозможные дополнения.

CT-ART 4 Шахматные комбинации

CT-ART – одна из лучших шахматных игр для тех, кто хочет научиться играть в эту игру. Чего здесь только нет – 2 200 базовых задач, 1 800 дополнительных задач, а также интерактивные уроки для обучения. У каждой задачи своя цель, что должно помочь вам научиться различной тактике. Вдобавок по мере продвижения в игре можно отслеживать ваш прогресс в рейтинге ЭЛО. В целом, это скорее обучающее приложение, нежели игра, так его и следует расценивать.

DroidFish Chess

Droidfish – порт популярного шахматного движка Stockfish в сочетании с изобилующим функциями графическим интерфейсом. Здесь вы найдете множество возможностей, адресованных продвинутому пользователю. В их число входит поддержка файлов PGN, FEN и EPD. Также поддерживаются базы данных Syzygy и Gaviota, другие движки. Как и в других приложениях, можно настраивать уровень сложности. В целом, это отличный шахматный комбайн, который с удовольствием используют серьезные игроки. Плюс ко всему, приложение абсолютно бесплатное, без всяких внутриигровых покупок или рекламы.

iChess – одна из шахматных игр, предназначенных для казуальных игроков. В основном вы занимаетесь решением шахматных задач без необходимости играть партию целиком. Все задачи в офлайн режиме, а также вы можете загружать свои собственные задачи. Приложение поддерживает файлы PGN, но не поддерживает CBH. Задачи группируются по степени сложности. В целом доступно три уровня сложности на выбор. Бесплатная версия содержит рекламу, а про-версия от нее избавлена. А в остальном эти версии совершенно одинаковы.

lichess • Free Online Chess

lichess – еще одна из наиболее популярных шахматных игр для мобильных устройств. Основная задача здесь – игра в шахматы онлайн с другими игроками. Найти себе подходящего противника среди 150 000 игроков не составит труда. Также тут есть несколько режимов игры, турниры, а вы можете отслеживать свою игровую статистику. Если захотите, можете играть и офлайн, против компьютера. Игру отличает поддержка множества языков, их тут целых 80. Также это приложение open source, бесплатно, без рекламы или внутриигровых покупок.

Play Magnus Chess

Play Magnus Chess – приложение, название которого говорит само за себя. Оно основано на шахматном движке, который разработан так, что играет похоже на гроссмейстера Магнуса Карлсена. В игре есть возможность выбрать возраст Магнуса, и движок будет имитировать его игру соответственно стилю в этом возрасте. Эта возможность выполняет функцию выбора уровня сложности – ведь игра шахматного гранда совершенствовалась с годами. Согласно описанию приложения, некоторые игроки могут даже быть признаны играющими на уровне самого Магнуса. Хотя, возможно, это всего лишь маркетинг. Но, тем не менее, одной из лучших шахматных игр это приложение быть не перестает.

Real Chess

Real Chess – одна из самых симпатичных на вид мобильных шахматных игр. 3D шахматная доска весьма хорошо смотрится. В числе доступных в приложении функций – онлайн-мультиплеер, игровой чат, различные темы оформления доски. Если вас отвлекает 3D доска, можно переключиться и играть на обычной 2D доске. В игре доступно 2400 уровней сложности, подсказки для начинающих игроков, поддержка портретной и ландшафтной ориентации экрана. Чаще всего все работает хорошо. Приложение отлично для казуальных игроков, но в случае с более хардкорными уровнями дело пойдет уже не так быстро.

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

• перемещение;
• оценка шахматной доски;
• минимакс;
• альфа-бета-отсечение.

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

Готовый алгоритм можно найти на GitHub.

Шаг 1. Генерация ходов и визуализация шахматной доски

Мы будем использовать библиотеки chess.js для генерации ходов и chessboard.js для визуализации доски. Библиотека для генерации ходов реализует все правила шахмат. Исходя из этого, мы можем рассчитать все ходы для данного состояния доски.

Визуализация функции генерации движения. Исходное положение используется как вход, а на выходе — все возможные ходы из этой позиции.

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

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

Черные играют случайными ходами

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.

Шаг 2. Оценка доски

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

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

Единственным ощутимым улучшением является то, что теперь наш алгоритм съест фигуру, если это возможно:

Черные играют с помощью простой функции оценки

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.

Шаг 3. Дерево поиска и минимакс

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

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

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

3–5 декабря, Онлайн, Беcплатно

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

Визуализация минимакса в искусственном положении. Лучший ход для белых — b2-c3, так мы можем гарантировать, что доберемся до позиции, где оценка равна -50

С минимаксом наш алгоритм начинает понимать основную тактику шахмат:

Минимакс с уровнем глубины 2

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.

Эффективность минимакса в значительной степени зависит от достижимой глубины поиска. Именно это мы улучшим на следующем шаге.

Шаг 4. Альфа-бета-отсечение

Альфа-бета-отсечение — это метод оптимизации алгоритма «минимакс», который позволяет игнорировать некоторые ветви в дереве поиска. Это позволяет нам намного глубже оценить дерево поиска, используя те же ресурсы.

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

Альфа-бета-отсечение не влияет на результат минимакса, оно только ускоряет его.

Этот алгоритм будет более эффективным, если мы сначала проверим те пути, которые ведут к хорошим ходам:

Позиции, которые нам не нужны, если используется альфа-бета-отсечение. Дерево посещается в описанном порядке.

С альфа-бета-отсечением мы получаем значительное улучшение минимакса, как показано в следующем примере:

Количество позиций, которые нужно оценить в случае поиска с глубиной 4 и начальной позицией, изображённой на картинке.

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.

Шаг 5. Улучшенная функция оценки

Первоначальная функция оценки довольно наивна, поскольку мы просто подсчитываем очки фигур, которые находятся на доске. Чтобы улучшить её, мы начнём учитывать положение фигур. Например, конь в центре доски «дороже», потому что он имеет больше доступных ходов и, следовательно, более активен, чем конь на краю доски.

Мы будем использовать слегка скорректированную версию квадратных таблиц, первоначально описанных в вики Chess Programming.

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

Применив это улучшение, мы получим алгоритм, который неплохо играет в шахматы, по крайней мере, с точки зрения простого игрока:

Улучшенная оценка и альфа-бета-отсечение с глубиной поиска 3

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle.

Заключение

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

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

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

Если вы хотите узнать о шахматных алгоритмах больше, зайдите на Chess Programming Wiki.

Шахматы - Играй и Учись
версия: 4.2.9
Жанр: Настольная

Последнее обновление игры в шапке: 20.03.2021

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

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

ИГРА С КОМПЬЮТЕРОМ:
- Используйте подсказки при игре с компьютеров, или изучайте глубже в режиме анализа
- Отправляте ваши игры по почте, как PGN

ВИДЕО УРОКИ:
- Ищите и просматривайте сотни видео уроков созданных топ тренерами и Гроссмейстерами
- Выбирайте уроки по уровню и тематике: Стратегия, Открытия, Эндшпиль, Тактики и Удивительные игры
- Смотрите как игры и комментарии представлены на большой доске с анимированными диаграммами

Русский интерфейс: Да
Системные требования: Android 4.4+

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

Читайте также:

  
• Топ карточных игр на андроид
  
• Как управлять вертолетом в гта сан андреас на андроид
  
• Mcc что это на андроид
  
• Как зарегистрироваться в зепето на андроид
  
• Смартфоны с android 11 перестанут подключаться к некоторым сетям wi fi