Как написать шахматы на python

«Программное приложение на Python – игра «Шахматы»»

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

Актуальность выбранной темы проекта связана с актуальностью профессионального изучения информатики и программирования в современном мире.

Новизна проекта заключается в сочетании теории и практики, использовании различных ресурсов для написания кода.

Цель проекта – Создать графический интерфейс на основе PyQt для игры в шахматы для 2 игроков

1. Реализовать классы фигур, механики передвижения.
2. Создать поле для игры, механику атаки
3. Реализовать таймер, обработку событий мыши.
4. С помощью PyQt создаем графический интерфейс

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

Если представить доску в виде матрицы, то можно определять местоположение фигур с помощью координат х и у.

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

def can_move ( self , board , row , col , row1 , col1):
# Пешка может ходить только по вертикали
# "взятие на проходе" не реализовано
if col != col1:
return False

if not self .is_path_clear(board , row , col , row1 , col1):
return False

# Пешка может сделать из начального положения ход на 2 клетки
# вперёд, поэтому поместим индекс начального ряда в start_row.
if self .color == WHITE:
direction = 1
start_row = 1
else :
direction = — 1
start_row = 6

# ход на 1 клетку
if row + direction == row1:
return True

# ход на 2 клетки из начального положения
if row == start_row and row + 2 * direction == row1:
return True

def can_attack ( self , board , row , col , row1 , col1):
direction = 1 if ( self .color == WHITE) else — 1
return (row + direction == row1
and (col + 1 == col1 or col — 1 == col1))

Эта фигура может двигаться только по вертикали и горизонтали, т.е. должны совпадать координаты до передвижения и после лтбо по вертикали либо по горизонтали. Зная это, реализуем класс:

def can_move ( self , board , row , col , row1 , col1):
# Невозможно сделать ход в клетку, которая не лежит в том же ряду
# или столбце клеток.
if row != row1 and col != col1:
return False
if not self .is_path_clear(board , row , col , row1 , col1):
return False

Конь двигается буквой «Г», т.е. на 2 по вертикали и 1 по горизонтали и наоборот. При этом направление не важно, значит нужно использовать ф-цию abs(), т.е. модуль.

class Knight(Piece):
ch = 'N'

def can_move ( self , board , row , col , row1 , col1):
# Конь двигается буквой Г (2 вертикально, 1 горизонтально)
if abs (row — row1) == 2 and abs (col — col1) == 1 :
return True
# Конь двигается буквой Г (1 вертикально, 2 горизонтально)
if abs (row — row1) == 1 and abs (col — col1) == 2 :
return True

Слон двигается по диагонали т.е. его смещение по вертикали должно быть равно смещению по горизонтали:

class Bishop(Piece):
ch = 'B'

def can_move ( self , board , row , col , row1 , col1):

if not self .is_path_clear(board , row , col , row1 , col1):
return False

# Слон двигается по диагонали
# Смещение по строка должно равняться смещению по столбцам
if abs (row — row1) == abs (col — col1):
return True

Королева двигается по всем сторонам (по горизонтали, вертикали, диагонали). Копируем эти механики из слона и ладьи и получаем:

class Queen(Piece):
ch = 'Q'

def can_move ( self , board , row , col , row1 , col1):

if not self .is_path_clear(board , row , col , row1 , col1):
return False

# Ферзь двигается вертикально
if col == col1:
return True

# Ферзь двигается горизонтально
if row == row1:
return True

# Ферзь двигается по диагонали
# Смещение по строка должно равняться смещению по столбцам
if abs (row — row1) == abs (col — col1):
return True

Король двигается в любую сторону на расстояние 1:

def can_move ( self , board , row , col , row1 , col1):

if not self .is_path_clear(board , row , col , row1 , col1):
return False

# Король двигается в любую клетку с рассотоянием равным 1
if max ( abs (row — row1) , abs (col — col1)) == 1 :
return True

А теперь необходимо реализовать некоторые особые механики игры, например «Превращение пешки» и «Рокировка».

Когда пешка доходит до противоположного конца доски она может стать Ферзем, Ладьей, Слоном или Конем. Для этого мы можем просто изменить класс фигуры, в том месте, где стоит пешка.

Для рокировки нам нужно знать: двигались ли король и ладья, есть ли между ними фигуры, приведет ли рокировка к шаху короля. От этого будет зависеть успешность рокировки или её невозможность.

Представим доску в виде матрицы на координатной оси. Тогда расположение фигур на доске будет записано в двухмерном списке. Записыаем стартовые значения матрицы:

self .field = [[ None ] * 8 for _ in range ( 8 )]
self .field[ 0 ] = [
Rook(WHITE) , Knight(WHITE) , Bishop(WHITE) , Queen(WHITE) ,
King(WHITE) , Bishop(WHITE) , Knight(WHITE) , Rook(WHITE)
]
self .field[ 1 ] = [
Pawn(WHITE) , Pawn(WHITE) , Pawn(WHITE) , Pawn(WHITE) ,
Pawn(WHITE) , Pawn(WHITE) , Pawn(WHITE) , Pawn(WHITE)
]
self .field[ 6 ] = [
Pawn(BLACK) , Pawn(BLACK) , Pawn(BLACK) , Pawn(BLACK) ,
Pawn(BLACK) , Pawn(BLACK) , Pawn(BLACK) , Pawn(BLACK)
]
self .field[ 7 ] = [
Rook(BLACK) , Knight(BLACK) , Bishop(BLACK) , Queen(BLACK) ,
King(BLACK) , Bishop(BLACK) , Knight(BLACK) , Rook(BLACK)
]

Цвет фигуры определяют константы WHITE и BLACK.

Каждая клетка имеет свое значение, так белая пешка обозначена как «wP». В дальнейшем это обозначение определит графическую модель фигурки на доске.

В этом классе создаем ф-цию проверки возможности движения:

def check_move ( self , row: int , col: int , row1: int , col1: int ):
"""Проверка перемещения фигуру из точки (row, col) в точку (row1, col1).
Если перемещение возможно, метод выполнит его и вернет True.
Если нет — вернет False"""
check = self .check() # Есть ли шах к перед ходом
if not correct_coords(row , col) or not correct_coords(row1 , col1):
return False
if row == row1 and col == col1:
return False # нельзя пойти в ту же клетку
piece = self .field[row][col]
target = self .field[row1][col1]
if piece is None :
return False
if piece.get_color() != self .color:
return False

if isinstance (piece , King) and self .is_under_attack(row1 , col1 , opponent( self .current_player_color())):
return False

if not (piece.can_move( self .field , row , col , row1 , col1) and target is None ) and \
not (piece.can_attack( self .field , row , col , row1 , col1) and
(target is not None and not isinstance (target , King)
and target.get_color() == opponent( self .current_player_color()))):
return False

old_field = [x.copy() for x in self .field] # Сохранить поле
self .field[row][col] = None # Снять фигуру.
self .field[row1][col1] = piece # Поставить на новое место.
if check and self .check(): # В результате хода избежать шаха не удалось
# Возвращаемся в исходное состояние
self .field = old_field
return False
# Возвращаемся в исходное состояние
self .field = old_field
return True

Ф-ция проверяет сразу все факторы: выход за пределы доски, походила ли фигурка на свое же место, приведет ли ход короля к его шаху или мату и т.д.

Реализуем ф-цию движения в которой используется ф-ция проверки:

def move_piece ( self , row , col , row1 , col1):
"""Переместить фигуру из точки (row, col) в точку (row1, col1).
Если перемещение возможно, метод выполнит его и вернет True.
Если нет — вернет False"""
if self .check_move(row , col , row1 , col1):
piece = self .field[row][col]
self .field[row][col] = None # Снять фигуру.
piece.moved()
self .field[row1][col1] = piece # Поставить на новое место.
if self .check_promotion(piece , row1):
self .promotion = True
self .color = opponent( self .color)
self .change = True
return True
return False

Также здесь реализуем механику атаки:

def is_under_attack ( self , row , col , color):
for row1 in range ( 8 ):
for col1 in range ( 8 ):
if self .field[row1][col1] is not None :
if self .field[row1][col1].get_color() == color and \
self .field[row1][col1].can_attack( self .field , row1 , col1 , row , col):
return True
return False

Для короля мы должны реализовать «Шах» и «Мат». Это довольно таки сложно из-за того, что у короля пропадает много возможностей, например «Рокировка». Поэтому я все ещё не полностью смог воссоздать эту механику из шахмат. Но все же в случае шаха игроку будут недоступны ходы, которые приведут к мату.

Таймер и обработка событий мыши

С помощью класса QtTimer от PyQt реализуем таймер для каждого игрока с механикой смены после окончания хода. Также с помощью механизма слотов и сигналов PyQt мы сможем обрабатывать события мыши для удобного взаимодействия с графическим интерфейсом.

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

Дополняем последние детали в виде кнопок «Новая игра» и «Выйти».

Проект завершен, создан рабочий вариант шахмат.

Во время разработки проекта я узнал о многих механиках программирования, получил знания о классах объектов, познакомился с QT. Этот проект ждет ещё множество новых механик и нововведений: добавление ИИ, реализация более сложных механик, которыми пользуются проффесиональные игроки(прим.: «Взятие на проходе»). В дальнейшем я не собираюсь останавливаться на этом проекте, так как меня ждет ещё множество нереализованных идей, ждущих своего часа.

Machine Learning and Chess

In late 2020, Netflix released the Queen’s Gambit, a TV show taking place in the 1950’s where we follow the journey of a young women thriving to become the best chess player.

However, unlike the protagonist Beth Harmon, chess isn’t really my strongest suit. So I did the next best thing by building my own python chess engine to compensate my poor chess skills.

Episode I: Strategies

When it comes to building any board game engine, there are multiple strategies:

• Reinforcement Learning
• Minimax
• ML model trained on human knowledge
• …

I opted for an hybrid of the second and third strategies: As a Data scientist, I am fond of working with large datasets and machine learning models. Also, despite being a little slower, Minimax is a quite reliable algorithm and does a good job at capturing enemy pieces. Reinforcement learning is simply too complex.

My strategy is simple:

• First of all, using the machine learning model, the engine will dismiss 50% of the possible moves given a board. It does so by finding the probability of a move being a ‘good move’. All the moves are sorted according to this probability and only the 50th percentile remains.
• Secondly, the engine will perform the Minimax algorithm on the remaining moves. Depending on the complexity of the board, the search tree will go to a certain depth.

Episode II: Data

In order to make accurate predictions, we need a lot of data. For this project, I will be using a dataset that I found on Kaggle. This dataset is a collection of thousands of games played by chess grand masters in the .pgn format (portable game notation).

The next step is to extract all the moves from all the games and label them as good or bad.

In my opinion, a ‘good move’ is a move that the winner played at some point during the game. A ‘bad move’ is a legal move that the winner chose not to play.

This python script got the job done leaving me with a brand new .csv dataset.

Создаем несложный шахматный ИИ: 5 простых этапов

Перевели для вас статью Лори Хартикка (Lauri Hartikka) о создании простейшего ИИ для шахмат. Она написана еще в 2017 году, но базовые принципы остались теми же. Все файлы, которые использовал Лори, тоже доступны.

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

1. 1. Перемещение;
2. 2. Оценка доски; ; . На каждом этапе работы с алгоритмом будет использоваться одна из них, это позволит постепенно совершенствовать игровые способности ИИ.

Напоминаем: для всех читателей «Хабра» — скидка 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.

— Lauri Hartikka (@lhartikk) March 28, 2017

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

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

При клике на картинке она откроется в полном разрешении.

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

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

Этап 2. Оценка позиции

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

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

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

Черные получили возможность брать белые фигуры. (Исходники и игра здесь).

Этап 3. Дерево поиска с минимакс

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

Здесь рекурсивное дерево с отображением всех возможных ходов анализируется до заданной глубины. Позиция же оценивается по листьям нашего дерева.

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

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

С минимакс-алгоритмом наш ИИ уже стал понимать базовую тактику шахмат.

Минимакс с глубиной 2 (Исходники и игра здесь)

Стоит отметить, что эффективность минимакс-алгоритма увеличивается с глубиной поиска. За это отвечает следующий этап.

Этап 4. Альфа-бета-отсечения

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

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

На результат минимакса оптимизация не влияет, но все начинает работать быстрее.

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

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

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

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

Этап 5. Улучшенная функция оценки

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

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

И теперь наш алгоритм играет уже весьма неплохо, конечно, по сравнению со средним игроком.

Исходники и игра доступны здесь

Заключение

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