Создаем несложный шахматный ИИ: 5 простых этапов
Перевели для вас статью Лори Хартикка (Lauri Hartikka) о создании простейшего ИИ для шахмат. Она написана еще в 2017 году, но базовые принципы остались теми же. Все файлы, которые использовал Лори, тоже доступны.
Простой искусственный интеллект, который умеет играть в шахматы, можно создать на базе четырех концепций:
Напоминаем: для всех читателей «Хабра» — скидка 10 000 рублей при записи на любой курс Skillbox по промокоду «Хабр».
Готовый исходный код можно найти на GitHub.
I’m having trouble beating a chess program I wrote.
Not sure if I’m a bad player or the algorithm is decent.
Этап 1. Визуализация шахматной доски с генерацией ходов
На этом этапе мы будем использовать библиотеки chess.js для генерации ходов и chessboard.js для визуализации доски. Библиотека, которая отвечает за генерацию ходов, позволяет применять все шахматные правила, так что мы можем рассчитывать каждое действие для конкретного расположения фигур.
При клике на картинке она откроется в полном разрешении.
Работа с этими библиотеками позволяет сконцентрироваться на главной задаче — поиске и создании алгоритма, который позволяет найти оптимальный ход. Работу начинаем с написания функции, которая возвращает случайный ход из списка всех возможных.
Несмотря на то, что алгоритм не является идеальным игроком в шахматы, для большинства игроков его уровня этого будет вполне достаточно.
Черные ходят случайным образом. (исходники и игра онлайн)
Этап 2. Оценка позиции
Теперь давайте разберемся, у какой стороны преимущество в том или ином положении. Самый простой путь — подсчитать относительную силу фигур на доске, это можно сделать при помощи таблицы.
Используя функцию оценки, мы получаем возможность создать алгоритм, который выбирает ход с максимальной оценкой.
В принципе, уровень прежний, но алгоритм уже может взять чужую фигуру, когда такая возможность есть.
Черные получили возможность брать белые фигуры. (Исходники и игра здесь).
Этап 3. Дерево поиска с минимакс
После этого мы создаем дерево поиска. Теперь программа может выбрать из него лучший ход. Это делается при помощи минимакс-алгоритма.
Здесь рекурсивное дерево с отображением всех возможных ходов анализируется до заданной глубины. Позиция же оценивается по листьям нашего дерева.
Далее мы возвращаем минимальное или максимальное значение потомка в родительский узел. Все зависит от того, ход какой стороны сейчас просчитывается. Другими словами, результат максимизируется или минимизируется на каждом из уровней.
С минимакс-алгоритмом наш ИИ уже стал понимать базовую тактику шахмат.
Минимакс с глубиной 2 (Исходники и игра здесь)
Стоит отметить, что эффективность минимакс-алгоритма увеличивается с глубиной поиска. За это отвечает следующий этап.
Этап 4. Альфа-бета-отсечения
Это метод оптимизации минимакс-алгоритма, дающий возможность игнорировать некоторые ветви в дереве поиска. А это позволяет увеличить глубину поиска, затрачивая прежний объем ресурсов.
Альфа-бета-отсечение основано на ситуации, когда мы можем остановить оценку определенной ветви, если обнаруживается, что новый ход приведет к худшей ситуации, чем та, которую мы видели при оценке предыдущего.
На результат минимакса оптимизация не влияет, но все начинает работать быстрее.
Этот алгоритм гораздо более эффективен в том случае, если сначала проверить пути, ведущие к хорошим ходам.
Изображение демонстрирует ходы, которые становятся ненужными в процессе использования альфа-бета-отсечения.
Как видите, с альфа-бета-отсечением минимакс оптимизируется, и весьма значительно.
Количество позиций, которые требуется оценить в случае поиска с глубиной 4 и начальной позицией, которая изображена выше. (исходники и игра доступны здесь)
Этап 5. Улучшенная функция оценки
Изначальная функция оценки достаточно простая, поскольку она просто считает очки фигур, находящихся на доске. Для ее оптимизации можно учитывать положение фигур. К примеру, если разместить коня в центре доски, то он становится дороже — спектр доступных ходов для этой фигуры расширится.
На этом этапе мы будем работать с несколько видоизмененной версией квадратных таблиц, изначально описанной в вики Chess Programming.
И теперь наш алгоритм играет уже весьма неплохо, конечно, по сравнению со средним игроком.
Исходники и игра доступны здесь
Заключение
Достоинством предложенного алгоритма является то, что он не делает совсем уж глупых ошибок. Конечно, стратегию здесь сложно назвать совершенной, но тем не менее.
Реализация нашего алгоритма выполнена всего в 200 строк кода, так что базовые принципы достаточно просты. Финальную версию программы можно github.com/lhartikk/simple-chess-ai’>видеть на GitHub.
В алгоритм можно добавить и другие модули, включая:
Больше о шахматных алгоритмах можно узнать на Chess Programming Wiki.
Как написать шахматы на python
Python Easy Chess GUI
A Chess GUI based from Python using PySimpleGUI and Python-Chess modules. Users can also load a chess engine and play with it. This program is based on a demo chess against ai from PySimpleGUI.
If you want to run from the python source the following are required or see the installation section below.
Or you can just download the executable file along with other files such as book and images.
1. Save games to repertoire pgn files
2. Install uci engine of your choice
2.1 It is recommended to configure the engine setting after installation
Configure engine via Engine->Manage->Edit, select engine and press modify.
3. Need book assistance? Right-click on BOOK 2 and press show
4. Need what engine adviser will think about the position? Right-click on Adviser and press start
To set opponent engine book options
To Hide/Unhide engine search info
To Hide/Unhide Book info
To request Adviser search info
To select opponent engine
To set time control of engine
To set time control of user
To delete engine from config file
About
A Chess GUI based from Python using PySimpleGUI and Python-Chess.
Making Chess in Python
I will first describe what’s happening and then show the code afterward.
This is a large project that me and a friend in school conducted. This is pretty funny because we had plans on doing this over several months and 7 days later we have the entire thing completed. I must say, this would not have been possible if it weren’t for the help of my friend Edwin. Firstly we abstracted the entire game since this is a very complex game to code and we decided that I would be responsible for the interface(what the user can see) while Edwin was responsible for the actual behaviour of each piece. They both have their own forms of difficulties to make and we did have to co-ordinate a lot so it wasn’t like we didn’t help each other make each other’s parts eg. i did teach him a bit of list comprehension to speed up his code while he exposed my pretty stupid mistake of doing column row instead of row column.
This code is everything that I wrote alongside some of the dictionary and methods above it. First we create the window object which is the window that comes up when we run the chess game on. We set the dimensions to 800×800 which is the tuple argument which we passed into it. We specifically chose 800 x 800 because the images for the chess pieces that we hard were all 100×100 which meant it would fit perfectly if the board was 800×800.
The main thing that makes my program work are these node objects and they are just the containers which hold the chess pieces(they are simulated as the tiles of the chess board in this case. They have their attributes which are their row, column,x,y co-ordinates. We need these separately because all these nodes are going to be stored in a 8×8 2d list so if we call it we would need to call it using its row and col numbers while if we were drawing it onto the screen we need its x,y pixel values(we could just do row*100 but that would risk us forgetting to add that 1 time in the entire code and watching the entire thing break).
The draw function is used to used to draw the tile onto the screen(so the black and white pattern) while the setup method is used to draw any images onto the screen if we had a piece on the screen at that position. You draw onto the screen using blit.
Draw grid draws the boundaries to the grid(so the black horizontal and vertical lines that separate the tiles) and draw grid and make grid is creating the 2d list which are going to use to access all the nodes later. Update display is used to update the screen every-time the tick. I think to avoid the CPU being overloaded, we chose to run the program at 20fps which is ofc completely unreasonable for chess but we didn’t want too much delay.
When the user clicks on the screen, we need to figure out what tile they have clicked on which is what find_node does. Display_potential_moves is a function edwin made but it just takes a list of potential moves and for those moves, changes the colour of the tile so that it stands out.
Do_move is used to acc make the swap on the screen but swapping the values on my dictionary, when the screen updates, this change will be visible on the screen.
remove_highlight is used because it is hard to remove the highlights for specific tiles so we decided to just to redraw the black colours for all the tiles instead.
The main function then contains a lot fo standard logic which I would hope you would have a grasp on if you know pygame. I will attach a video here too just incase you don’t
If I were to explain the entirety of the code, this would take hours on hours to write so I am going to explain the functions and any complex concepts which may be in them and leave you to solve out the rest.
We used pygame to write this program since it can easily give us the interface and I have experience from my A* algorithm on how to make a grid so most of the grid is just recycled code from that.
Except from the starting order dict, all of this was edwins code and all of it used for the move calculations. Theoretically you could have done this with only one of either a dictionary or a 2d list like he has done but since we both needed access to an array for our parts while we were coding and we couldn’t share a python script, we made our own versions. Edwin makes a class for the pieces since it is easier to manage and at the bottom he is setting up his 2d list so all the pieces are in their starting positions. In my dictionary, I hard wrote all the positions automatically since I needed to put the name of each of the individual image files into the load. pygame.image.load() is going to load an image onto the python file and then we only need to draw the image onto the screen. It is better this way than loading the image and then drawing because it means we only need to load the image once for the entire program and then just translate this image onto new positions on the screen.
The rest of edwins code is pretty self-explanatory and is just choosing the correct positions that each piece can move to and then putting those ‘legal’ tiles on the chessboard for us to use on the interface as a way of highlighting the board.
Как написать шахматы на python
python-chess: a chess library for Python
python-chess is a chess library for Python, with move generation, move validation, and support for common formats. This is the Scholar’s mate in python-chess:
Download and install the latest release:
Supports Python 3.7+. Includes mypy typings.
IPython/Jupyter 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 as a draw (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.
Reads Polyglot opening books. Docs.
Reads and writes 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.
If you like, share interesting things you are using python-chess for, for example:
A website to probe Syzygy endgame tablebases
A human-like neural network chess engine
Oppinionated wrapper to use python-chess from the R programming language
Deep learning for Crazyhouse
A GUI to play against UCI chess engines
A multi-agent reinforcement learning environment
Thanks to the Stockfish authors and thanks to Sam Tannous for publishing his approach to avoid rotated bitboards with direct lookup (PDF) alongside his GPL2+ engine Shatranj. Some move generation ideas are taken from these sources.
Thanks to Ronald de Man for his Syzygy endgame tablebases. The probing code in python-chess is very directly ported from his C probing code.
Thanks to Kristian Glass for transferring the namespace chess on PyPI.
python-chess is licensed under the GPL 3 (or any later version at your option). Check out LICENSE.txt for the full text.
About
A chess library for Python, with move generation and validation, PGN parsing and writing, Polyglot opening book reading, Gaviota tablebase probing, Syzygy tablebase probing, and UCI/XBoard engine communication
python-chess: a chess library for Python¶
Introduction¶
python-chess is a chess library for Python, with move generation, move validation, and support for common formats. This is the Scholar’s mate in python-chess:
Installing¶
Download and install the latest release:
Documentation¶
Features¶
Supports Python 3.7+. Includes mypy typings.
IPython/Jupyter 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 as a draw (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.
Reads Polyglot opening books. Docs.
Reads and writes 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.
Selected projects¶
If you like, share interesting things you are using python-chess for, for example:
A website to probe Syzygy endgame tablebases
A human-like neural network chess engine
Oppinionated wrapper to use python-chess from the R programming language
Deep learning for Crazyhouse
A GUI to play against UCI chess engines
A multi-agent reinforcement learning environment
a stand-alone chess computer based on DGT board – http://www.picochess.org/
a bridge between Lichess API and chess engines – https://github.com/careless25/lichess-bot
an HTTP microservice to render board images – https://github.com/niklasf/web-boardimage
building a toy chess engine with alpha-beta pruning, piece-square tables, and move ordering – https://healeycodes.com/building-my-own-chess-engine/
Django Rest Framework API for multiplayer chess – https://github.com/WorkShoft/capablanca-api
Acknowledgements¶
Thanks to the Stockfish authors and thanks to Sam Tannous for publishing his approach to avoid rotated bitboards with direct lookup (PDF) alongside his GPL2+ engine Shatranj. Some move generation ideas are taken from these sources.
Thanks to Ronald de Man for his Syzygy endgame tablebases. The probing code in python-chess is very directly ported from his C probing code.
Thanks to Kristian Glass for transferring the namespace chess on PyPI.