Как я шашки писал

Предыстория

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

Правила игры

• Игра ведётся на доске 8х8 клеток, только на черных ячейках


• Шашки в начале игры занимают первые три ряда с каждый стороны


• Бить можно произвольное количество шашек в любых направлениях


• Простые шашки ходят только вперёд


• Простая шашка может срубить назад


• Дамка ходит на любое число полей в любую сторону


• Проигрывает тот, у кого не остается фигур, либо ходов


• Шашка снимается с поля после боя (можно перефразировать так: одну шашки нельзя срубить дважды за один ход)


• Бить обязательно


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


• Если шашка во время боя проходит через дамочное поле, то она превращается в дамку и следующие бои (если они возможны) совершает уже как дамка

Реализация

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

• name: a1 //Имя клетки на реальной доске


• color: 1 //Цвет шашки, 1 — белая, 2 — черная, 0 — клетка пустая


• queen: false //Является ли шашка дамкой


• border: false //подсвечено ли поле


• doubleWay: false


• goldWay: true //эти два поля будут объяснены чуть позже

Разумеется, это не все необходимые свойства, однако приводить все я не вижу смысла. Что касается методов, то их немного и они выполняют несложные действия типа изменения полей queen, color и прочих, а затем обновляют изображение. Так, при бое будут вызваны функции для «очищения» той клетки, с которой идёт бой и той клетки, на которой стоит срубленная шашка, а так же для отрисовки шашки на том поле, куда происходит бой.

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

• GoldWay: a1, b2, c3, d4, e5, f6, g7, h8 //Так называемая «Большая дорога»


• DoubleWayG1A7: g1, f2, e3, d4, c5, b6, a7 //Двойники


• DoubleWayH2B8: h2, g3, f4, e5, d6, c7, b8


• TripleWayC1A3: c1, b2, a3 //Тройники


• TripleWayC1H6: c1, d2, e3, f4, g5, h6


• TripleWayH6F8: h6, g7, f8


• TripleWayA3F8: a3, b4, c5, d6, e7, f8


• UltraWayA5D8: a5, b6, c7, d8 //Косяки


• UltraWayH4D8: h4, g5, f6, e7, d8


• UltraWayE1A5: e1, d2, c3, b4, a5


• UltraWayE1H4: e1, f2, g3, h4

Разбивка на диагонали происходит именно так. Обратите внимание, что все диагонали перечислены снизу-вверх. Это сделано для удобства программиста, хотя и не является обязательным. В свойствах объектов перечислены все эти диагонали, а у тех диагоналей, на которых клетка лежит, стоит true, на остальных — false.

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

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

«шашка(1) — шашка (2) — пустое поле» (где 1 и 2 — игроки и ход сейчас делает игрок №1), либо «пустое поле — шашка(2) — шашка (1)» [для боя в обе стороны], то присвоить свойству первой клетки, отвечающему за информацию о том, должна ли она рубить, единичку. Кроме этого присвоить некой общей переменной(назовем её jumpInd), отвечающей за бои, единичку. Это нужно, потому что может возникнуть ситуация, в которой у игрока будет выбор какой из шашек рубить.

Когда игрок нажимает на какую-либо шашку, первым делом проверяется условие jumpInd. Если jumpInd=1, а шашка, на которую кликнул игрок, не должна бить, то ничего не происходит, либо выводится сообщение о том, что игрок обязан рубить. Если jumpInd=0, то проверяется, может ли эта шашка сделать ход. Проверка выполняется аналогично проверке на бой, только немного короче: если на одной из диагоналей встречается ситуация: «шашка(1) — пустое поле(для белых) и пустое поле — шашка(1)» [для черных], то подсветить это поле. Если jumpInd=1 и игрок выбрал шашку, которой этот бой и будет производиться, то клетка, на которую будет произведен бой, также подсвечивается. Можно подсветить и шашку, которой будет сделан ход. Эти действия нужны лишь для удобства игрока. Следующим действием игрок может кликнуть по другой шашке и тогда алгоритм начнется сначала, а может кликнуть по подсвеченному полю и совершить таким образом ход.

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

Нам удалось реализовать простые передвижения шашки, но это только начало. Теперь мы должны реализовать движение дамок. Здесь всё несколько сложнее в реализации, по крайней мере я с ними изрядно попотел, хотя сама суть похожа.

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

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

Проверка для боя: если встречается ситуация: «дамка — z пустых полей — шашка(дамка) противоположного цвета — n пустых полей» (z>=0, n>0), то подсветить все n пустых полей после шашки соперника (если встретится ещё одна шашка противника, то прекратить) и проделать все те манипуляции с переменными, хранящими информацию о боях, что и в случае с обычной шашкой. После того, как игрок кликнет на подсвеченную клетку, следует проверить возможность ещё одного боя в любую сторону, кроме той, из которой мы пришли. Реализация всех этих проверок и условий заняла у меня много времени и места, но, возможно, я просто что-то упустил и можно было реализовать всё короче и красивее.

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

(Дамка черных обязана рубить следующим путём: h4:e1:c3:e5 и останавливаться, так как шашка g3 всё ещё на доске. После этого белые рубят в дамки и выигрывают)

Весь этот алгоритм можно очень кратко описать следующей блок-схемой:

Первый клик:

Второй клик:

Чтобы программа поняла, где первый клик, а где второй, — создадим логическую переменную, false = первый клик, true = второй клик.

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

Искусственный Интеллект

Однако на этом наши приключения не заканчиваются. Замечательно, что мы научили шашки двигаться, но с кем же мы будем играть? Нам необходимо создать искусственный интеллект для игры. К сожалению, полноценно его реализовать у меня так и не получилось, так как из-за плохой оптимизации программа начинала виснуть при просчете далее, чем на 5-6 ходов (порядка 20-25 тысяч позиций). При реализации я пользовался книгой Программирование шахмат и других логических игр и рекомендую её всем, кто заинтересуется проблемой ИИ в логических играх. Я остановился на улучшенном алгоритме «альфа-бета отсечений», но описывать здесь я его не буду, потому что он уже много раз на Хабре был описан до меня, например:

Применение машинного обучения в построении ИИ для игры в японские шахматы (сёги)

Минимакс на примере игры в зайца и волков

и другие.

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

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.