webdonsk.ruКак сделать на python шахматы
Добавил пользователь Владимир З. Обновлено: 04.09.2024
Я использую numpy для инициализации массива пикселей на серой шахматной доске (классическое представление для “без пикселей” или прозрачное). Кажется, что должен быть какой-то свистящий способ сделать это с помощью numpy amazing array assign/slicing/dicing, но это лучшее, что я придумал:
Это работает, но я надеялся на что-то более простое.
это должно это сделать
любой размер шахматной доски, который вы хотите (просто пройдите по ширине и высоте, как w, h); также я имею жестко заданную высоту/ширину ячейки до 1, хотя, конечно, это также можно было бы параметризовать так, чтобы произвольное значение передавалось в:
с этим 2D-массивом, просто сделать изображение шахматной доски, например:
Я бы использовал продукт Kronecker kron :
Шахматная доска в этом примере имеет 2 * 4 = 8 полей размером 10x10 в каждом направлении.
Вот еще один способ сделать это, используя ogrid , который немного быстрее:
Вот результаты тайм-аута:
Самый компактный, возможно самый быстрый, а также единственное решение, которое обобщает на n-мерные размеры.
Я уже давно собирался заняться изучением Theano, кроме того, мне хотелось создать искусственный интеллект (ИИ) для игры в шахматы. Так почему бы не совместить два этих начинания? Таким был ход моих мыслей, и в итоге я посвятил немало времени этим вопросам.
Теория
Шахматы – игра с конечным числом состояний. Это означает, что, обладая бесконечными вычислительными ресурсами, мы смогли бы найти решение этой игры. Каждая позиция в шахматах это: либо победа для белых, либо победа для черных, либо ничья. Мы можем обозначить это с помощью функции f(позиция). Если бы у нас был бесконечно быстрый компьютер, мы могли бы вычислить ее следующим образом:
- Присвоим всем финальным позициям значения –1, 0, 1, в зависимости от исхода игры.
- Применим рекурсивное правило f(p) =maxp->p‘–f(p‘), где p->p‘ обозначает все допустимые ходы из позиции p. Знак минус используется потому, что игроки делают ходы поочередно, то есть, если позиция p соответствует ходу белых, тогда позиция p‘ соответствует ходу черных.
Этот подход эквивалентен процедуре минимакс (minimax).
Количество возможных позиций в шахматах составляет около 10 43 . Вычисления такого масштаба выполнить невозможно. Следовательно, необходимо прибегнуть к аппроксимации f(p).
Как применить машинное обучение для решения этой задачи?
Машинное обучение, по своей сути, сводится к аппроксимации функций на основе некоторых данных. Следовательно, если у нас будет достаточный объем данных, мы сможем аппроксимировать функцию f(p).
Я загрузил 100 миллионов сыгранных партий из базы данных FICS и приступил к обучению. Обучение функции f(p) основано на двух принципах:
- Игроки выбирают оптимальные или близкие к оптимальным ходы. Это означает, что для двух последовательных позиций p->q мы имеем f(p) = –f(q).
- По той же причине, если из позиции p игрок ходит не в позицию q, а в случайную позицию r (p->r), должно выполняться неравенство f(r) > f(q), потому что случайная позиция более выгодна для игрока, который будет делать следующий ход, и менее выгодна для игрока, сделавшего данный ход.
Модель
В общей сложности сеть имеет 10 миллионов неизвестных параметров.
Чтобы обучить сеть, я использовал триплеты (p, q, r). Если обозначить сигмоиду, как
тогда общая целевая функция будет иметь следующий вид:
?(p, q, r) log S(f(q) – f(r)) + k log(f(p) + f(q)) + k log(–f(q) – f(p)).
Это лог-правдоподобие (log-likelihood) неравенств f(r) > f(q), f(p) > –f(q), и f(p)
Рассмотрим некоторые базовые концепции, которые помогут нам создать простой искусственный интеллект, умеющий играть в шахматы:
- перемещение;
- оценка шахматной доски;
- минимакс;
- альфа-бета-отсечение.
На каждом шаге мы будем улучшать наш алгоритм с помощью одного из этих проверенных временем методов шахматного программирования. Вы увидите, как каждый из них влияет на стиль игры алгоритма.
Готовый алгоритм можно найти на 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.
Ходы коня
На шахматной доске стоит конь. Отметьте положение коня на доске и все клетки, которые он бьет. Клетку, где стоит конь, отметьте английской буквой “K”. Клетки, которые он бьёт, отметьте символами “*”. Остальные клетки заполните точками.
Программа получает на вход два числа — координаты коня на шахматной доске. Каждая координата вводится на отдельной строке. Первое число обозначает номер строки, а второе — номер столбца. Все числа принимают значения от 1 до 8.
Выведите на экран изображение доски так, как это показано в примере.
1) Создаешь двумерный массив шахматной доски:
array=[['.']*8 for _ in range (8)]
2) Вводишь координаты коня x и y. Отними 1 от этих значений, так как индексы в массиве начинаются с 0.
3) Помещаешь в массив букву "К" по полученным координатам
array[x][y]='K'
4) Далее аналогично рисуешь '*' в тех координатах, куда конь может бить "буквой Г". Для понимания этого нужно хотя-бы раз в жизни сыграть в шахматы. Соответственно, координаты будут варьироваться (x+2 y+1), (x+2 y-1) и т. д. и т. п. - всего максимум 8 клеток.
При этом не забывай, что если конь находится на границе доски, то координаты "боя" могут оказаться отрицательными, то есть, их нужно пропускать.
5) В итоге выводишь полученный массив:
for i in range (8):
~~~~print (*array[i])
Экспериментальная функция:
Ниже вы видите текст статьи по ссылке. По нему можно быстро понять ссылка достойна прочтения или нет
Просим обратить внимание, что текст по ссылке и здесь может не совпадать.
python-chess: a pure Python chess library
python-chess is a pure Python chess library with move generation and validation and handling of common formats. This is the scholars mate in python-chess:
Supports Python 2.6+, Python 3.3+ and PyPy.
IPython notebook integration. SVG rendering docs.
Chess variants: Standard, Chess960, Suicide, Giveaway, Atomic, King of the Hill, Racing Kings, Horde, Three-check, Crazyhouse. Variant docs.
Make and unmake moves.
Show a simple ASCII board.
Detects checkmates, stalemates and draws by insufficient material.
Detects repetitions. Has a half move clock.
With the new rules from July 2014 a game ends drawn (even without a claim) once a fivefold repetition occurs or if there are 75 moves without a pawn push or capture. Other ways of ending a game take precedence.
Detects checks and attacks.
Parses and creates SAN representation of moves.
Parses and creates FENs, extended FENs and Shredder FENs.
Parses and creates EPDs.
Read Polyglot opening books. Docs.
Read and write PGNs. Supports headers, comments, NAGs and a tree of variations. Docs.
Probe Gaviota endgame tablebases (DTM, WDL). Docs.
Probe Syzygy endgame tablebases (DTZ, WDL). Docs.
Communicate with an UCI engine. Docs.
Download and install the latest release:
Selected use cases
If you like, let me know if you are creating something intresting with python-chess, for example:
python-chess is licensed under the GPL3. See the LICENSE file for the full copyright and license information.
Thanks to Sam Tannous for publishing his approach to avoid rotated bitboards with direct lookup (pdf) alongside his GPL2+ engine Shatranj. Some of the bitboard move generation parts are ported from there.
Читайте также: