Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Уфимский государственный авиационный технический университет»

Кафедра вычислительной математики и кибернетики

Отчет по расчётно-графической работе

по дисциплине: «Методы искусственного интеллекта»

«Игра в шашки 6х6»

Выполнили:

студенты группы МО-417

Шакиров А.Р.

Ибрагимова К.Б.

Проверил:

Ризванов Дмитрий Анварович

Уфа 2022

Задание

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

Выбор игры

В качестве игры были выбраны шашки с полем 6х6.

Игровое поле

6		●		●		●
5	●		●		●
4
3
2		○		○		○
1	○		○		○
	A	B	C	D	E	F

Игровое поле состоит из 6 горизонтальных (далее горизонтали) и 6 вертикальных рядов (далее вертикали) последовательно чередующихся светлых и тёмных клеток.

Все горизонтали пронумерованы арабскими цифрами (от «1» до «6»), а вертикали – буквами латинского алфавита (от A до F).

Правила

Каждый участник играет набором шашек своего цвета. В каждом наборе по 5 шашек.

Шашки могут занимать только темные клетки. На старте игры белые шашки занимают темные клетки 1 и 2 горизонтали, а черные – 5 и 6 горизонтали.

Игру начинают «белые» шашки, после этого участники ходят по очереди друг за другом.

Правила перемещения и взятия шашек:

• Каждым ходом игрок перемещает одну свою шашку на 1 клетку по диагонали.

• Шашки перемещаются только «вперёд», т. е. по направлению к противоположному концу поля.

• Шашка не может переместиться на клетку, занятую другой шашкой.

• Если шашка игрока оказывается на соседней по диагонали клетке с клеткой, занятой шашкой противника, и за шашкой противника по диагонали имеется свободная клетка, шашка игрока обязана переместиться через шашку противника на эту свободную клетку. При этом шашка противника убирается с поля и считается «взятой», а данное действие именуется «взятием».

• Если после взятия шашка игрока может взять ещё одну шашку противника, то обязана это сделать.

• Взятие шашки может происходить как вперед, так и назад.

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

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

Дамка

Если шашка достигает противоположного конца поля (горизонталь «6» для «белых», горизонталь «1» для «чёрных»), то сразу превращается в «дамку».

Подобно обычным шашкам, дамки перемещаются только по диагонали, но перемещаются не на одну клетку, а на любое количество клеток до конца игрового поля, и не только вперёд, но и в обратном направлении.

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

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

Конец игры

Игра заканчивается в одном из четырёх следующих случаев.

• Один из игроков не может сделать ход, либо он лишился всех шашек и дамок. Его противник становится победителем.

• Если у одного игрока осталась только дамка, а у соперника есть как минимум одна дамка и в сумме шашек больше.

• Один из игроков сдался. Его противник становится победителем.

• Игроки создали на поле ничейную ситуацию, а именно:

  • игроки в третий раз повторили одно и то же расположение шашек и дамок (причём не обязательно три раза подряд);

  • ни у одного из игроков нет возможности выиграть;

    • в течение последних 5 ходов игроки перемещали одни лишь дамки, не делая взятия шашками.

    • игроки сами договорились признать ничью.

Стратегии выбора

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

Пусть

m1 – кол-во шашек противника, которых можно будет взять.

m2 – кол-во собственных шашек, которых сможет взять соперник.

m3 – кол-во шашек противника на собственной половине поля.

m4 – кол-во собственных дамок.

m5 – кол-во дамок противника.

m6 – дельта, т.е. разница между своими шашками и противника.

Функции

Первый игрок

F1 = 3*m1 – 6*m2 – m3 + m4 – 5*m5 + 10*m6

Второй игрок

F2 = 4*m1 – 2*m2 + 2*m4 – 3*m5 + 3*m6

Ход игры