Как написать игру шашки

Один из лучших способов научиться веб-разработке — создать игру. Используя основные инструменты javascript, вы можете приступить к работе. Для новичка это может быть непросто. Легко попасть в ловушку «адского учебника», потому что вы думаете, что вам нужно продолжать учиться, прежде чем вы сможете начать творить. Я докажу вам, что это не так, пройдя через процесс создания шашек для настольных игр.

Я рассматриваю только HTML, JavaScript (включая DOM) и очень небольшое количество CSS, поэтому я предполагаю, что вы знаете, как использовать их основы. Вы также должны знать, как играть в шашки, конечно …

Если вы хотите увидеть готовый код, вы можете посетить репозиторий GitHub здесь: https://github.com/RyanBranco/Checkers

Во-первых, это HTML.

Чтобы нарисовать доску для пользователя, я использую <table>. Шашечную доску можно легко создать, используя таблицу, потому что это именно то, чем является шашечная доска; стол 8х8. Между открывающим и закрывающим <table> тегами нам нужно 8 <tr> (строка таблицы). The<tr> на самом деле не создает ячейки в строках, он только определяет новую строку, в которую вы можете ввести ячейки; поэтому внутри каждого из 8 <tr>, которые вы только что создали, должно быть 8 <td> (данные таблицы), которые будут создавать фактические ячейки для платы.

Вот как должен выглядеть скелет:

Вы еще не увидите ничего, отображаемого на веб-странице, потому что внутри таблицы нет данных. Это будет следующим шагом.

Теперь это HTML, который должен иметь каждый <td>.

На доске есть клетки, в которых никогда не будет фигур, я даю им class=”noPieceHere”. Это важно для логики javascript (рассматривается позже) и CSS (поэтому они имеют другой цвет). Самый первый <td> должен иметь класс noPieceHere и должен чередоваться по всей доске (создавая эффект шахматной доски). Вот как будет выглядеть одна строка:

Теперь это нужно продублировать для всех остальных 7 строк, и помните, что это нужно чередовать. Это означает, что следующий <tr> начнется с <td>, не имеющего класса noPieceHere.

Теперь CSS для ячеек.

Каждый <td> имеет background-color: #BA7A3A, Width & Height 65px (поэтому каждая ячейка выглядит как квадрат) и text-align: center (для центрирования каждой части). Затем .noPieceHere заменяет цвет <td> на #F0D2B4 (чтобы он выглядел как шахматная доска).

* Ячейки могут быть настроены по вашему желанию *

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

В каждом <td>, не имеющем class=”noPieceHere”, будут лежать куски. Я использую пустые теги <p> для красных фигур и пустые <span> теги для черных фигур; это не является абсолютно необходимым, но я думаю, что это упрощает итерацию по частям после перехода на JavaScript.

Красные фигуры имеют class=”red-piece”, а черные фигуры имеют class=”black-piece”, и каждая фигура должна иметь свой уникальный id.

У каждого цвета по 12 штук на противоположных концах, а в середине должно остаться 2 ряда.

Вот пример одной строки на каждом конце:

В JavaScript нам нужно будет присвоить элементам class=”king”, когда элемент достигнет противоположного конца доски, поэтому нам нужно определить .king в CSS, когда он будет добавлен JS.

Вот CSS для фигур и класса короля:

* Детали могут быть настроены по вашему желанию *

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

Цвет текста будет изменен с помощью JavaScript, но вот статический HTML:

Не забудьте добавить классы к каждому <div>, потому что нам нужно будет ссылаться на них в JavaScript, чтобы мы могли изменять стиль в зависимости от хода игрока.

Вы можете стилизовать их по своему усмотрению, но я начинаю с того, что задаю .black-turn-text серый цвет, чтобы он выглядел блеклым (чтобы пользователь знал, что игра начинается на красном ходу).

Окончательный результат HTML и CSS должен выглядеть примерно так:

Отлично! HTML и CSS завершены! Теперь начинается самое интересное … JavaScript!

В логике JavaScript произойдут три основных события:

1. Когда по кусочку щелкают
2. при нажатии на ячейку
3. Данные, которые изменяются после щелчка по ячейке

Но прежде чем мы перейдем к логике, нам нужно инициализировать данные состояния игры и объявить переменные, которые ссылаются на элементы в DOM. Давайте начнем!

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

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

Затем нам нужно установить переменные, которые мы будем использовать для ссылки на вещи (в свойствах DOM и player).

Сначала, используя DOM, мы берем весь cells (строка 23), все части с каждой стороны (строки 24 и 25), текст поворота для каждой стороны, чтобы пользователь мог видеть, кто сейчас ход (строка 26 и 27), затем divider (строка 28). Не беспокойтесь о разделителе, если у вас его нет, все, что я собираюсь сделать, это изменить display: none, чтобы он исчезал, когда отображается победитель.

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

Я использую переменную turn для представления хода текущего игрока (true === красный ход & false === черный ход [строка 31]). Как только у игрока остается 0 фишек, побеждает противоположный игрок, поэтому нам нужно отслеживать «счет» каждого игрока (строки 32 и 33). Наконец, переменная playerPieces. Эта переменная позволяет нам динамически удерживать все фишки текущих игроков. Преимущество этого состоит в том, что нам не нужно писать код дважды (для красных и черных цветов). Мы будем динамически изменять, на какие части игрока ссылаются, поэтому нам нужно написать код только один раз.

Если переменная playerPieces немного сбивает с толку, не волнуйтесь, я скоро рассмотрю ее.

Теперь идет объект, который будет содержать свойства частей.

При щелчке по объекту selectedPiece object будет динамически изменяться в зависимости от свойств объекта, по которому щелкнул пользователь. Мы запрограммируем Javascript для анализа возможных ходов вокруг него и изменим истинные / ложные значения в зависимости от возможных ходов. Я покажу, как это делается позже. Он включает массив board, который был создан ранее.

Когда щелкают по фигуре, нам нужно взять несколько вещей: конкретный id для фигуры (строка 38), индекс доски, на которой находится фигура (строка 39), если это король (строка 40), и все возможные ходы, которые доступны (строки 41–48).

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

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

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

Теперь нам нужно дать частям click прослушиватель событий. Функция givePiecesEventListeners() предоставит деталям прослушиватель событий, который вызовет функцию getPlayerPieces. getPlayerPieces() — это начало цепочки функций, которые будут управлять объектом selectedPiece, который я показал ранее.

Итак, в самом низу файла JavaScript вызовите функцию, которая инициализирует прослушиватели событий, например: givePiecesEventListeners().

Следующие несколько функций поначалу могут показаться запутанными, потому что в них будут задействованы вещи, которые я еще не рассмотрел в коде. Они сбрасывают черты, которые еще не были изменены в коде. Но это должно быть сделано первым в цепочке, потому что, если пользователь щелкает фигуру, чтобы переместить, все будет проанализировано, и ячейки вокруг него получат «onclick» в зависимости от положения, в котором фигуры могут перемещаться. Но что тогда, если пользователь решит, что не хочет двигать этот кусок? Вместо этого они должны иметь возможность выбрать другой кусок. Поэтому для того, чтобы это произошло, в коде необходимо сбросить определенные свойства, чтобы новая выбранная часть могла двигаться правильно.

Здесь будет изменена переменная playerPieces. Просто if (turn) (что означает его красный поворот), установите переменную playerPieces на redsPieces, else… (что означает его черный ход) установите playerPieces на blacksPieces. Затем вызовите функцию removeCellonclick(). Затем, когда removeCellonclick() закончится, запустите resetBorders().

Во-первых, давайте рассмотрим removeCellonclick().

Эта функция перебирает все ячейки на плате (строка 81). Затем удаляет атрибут onclick (строка 82).

Позже я покажу вам, почему onclick для ячеек должны быть атрибутами, но пока все, что вам нужно знать, это то, что нам нужно будет динамически добавлять и удалять их.

Теперь рассмотрим resetBorders(), который назывался ранее.

Позже мы добавим к выбранной фигуре зеленую границу (чтобы показать, что фигура выбрана для перемещения), но если пользователь выберет другую фигуру, более старая фигура должна вернуться к значению по умолчанию. Таким образом, эта функция проходит через все playerPieces (это было установлено ранее) и заменяет части так, чтобы они имели строку border = “ 1px solid white” (89). Как только это закончится, вызывается resetSelectedPieceProperties(), затем getSelectedPiece().

Сначала давайте рассмотрим, что делает resetSelectedPieceProperties().

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

Теперь переходим на getSelectedPiece().

Нам нужно найти место на доске. Вот когда в игру вступает getSelectedPiece().

Если щелкнуть элемент, он выдаст вам event. Мы можем получить id фрагмента, набрав event.target.id. event.target.id возвращает строку id, и мы хотим, чтобы это было число, чтобы JavaScript мог правильно прочитать его, когда мы помещаем его в массив board. Итак, окружив parseInt() (строка 112), мы можем превратить строку в число. Также нам нужно найти, где находится фигура на доске. Здесь в игру вступает функция findPiece.

findPiece() принимает один параметр — идентификатор детали. Как только мы сохраняем parseInt() версию фрагмента (строка 18), мы передаем ее в метод javascript indexOf (строка 19) и return его. Это даст вам точное положение индекса, где находится выбранная фигура.

Следующим в цепочке функций идет isPieceKing().

Функция isPieceKing() не требует пояснений, она определяет, является ли выбранная фигура королем или нет.

Используя .classList.contains(“king”) в выбранном элементе HTML (строка 119), мы можем определить, король это или нет. Легкий! Позже вы увидите, как фигуре присваивается класс короля.

Затем вызовите getAvailableSpaces()

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

Если вы считаете клетки, фигуры могут перемещаться на +/- 7 ячеек или +/- 9 ячеек (плюс или минус, в зависимости от того, красная или черная фигура). Давайте посмотрим на первый if оператор, потому что, как только вы поймете одно из них, вы поймете остальное (строки 129–131).

Если selectedPiece.indexOfBoardPiece + 7 === null (что означает, что место доступно) и та же самая ячейка не имеет класса noPieceHere (строка 130), фигура может двигаться! Поэтому мы устанавливаем это свойство в строке selectedPiece = true (131).

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

Теперь давайте посмотрим на checkAvailableJumpSpaces().

checkAvailableJumpSpace() делает то же самое, что и checkAvailableSpaces(), за исключением … как вы уже догадались … прыгать по кусочкам.

Функция почти такая же, разница в том, что это +/- 14 или +/- 18 (плюс или минус в зависимости от того, красный или черный кусок). Дополнительным условием внутри оператора if является то, если позиция, на которую выполняется переход, равна >= 12, что означает, что фигура черная (поскольку у черных фигур id больше или равно 12), а у красных фигур id меньше 12.

К сожалению, этой функции необходимо дублировать код для каждой стороны (красной и черной). Это из-за того, как мы должны указывать детали id’s. Вероятно, есть способ избавиться от дублированного кода, но я не уверен, как это сделать. Так что, если кто-то сможет найти способ избавиться от необходимости дублировать код, не стесняйтесь оставлять сообщения в комментариях ниже.

Убедитесь, что после этой функции мы вызываем следующую, checkPieceConditions(). Я не показываю это на картинке, но это абсолютно необходимо, потому что нам нужно продолжать цепочку.

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

Поскольку король имеет полное движение и не имеет значения, на какой он стороне, нам не нужно манипулировать никакими свойствами. Итак, мы можем просто перейти к следующей функции — givePieceBorder() (строка 199).

Если это не король, нам нужно удалить все «минусовые» свойства движения для красных фигур и удалить нормальные свойства движения для черных фигур. Так мы ограничиваем движение.

Затем… мы переходим к следующей функции, givePieceBorder().

Чтобы кусок выглядел выделенным, нам нужно выделить его зеленым цветом. Итак … если какое-либо из свойств selectedPiece движения истинно, мы меняем document.getElementById(selectedPiece.pieceId).style.border = “3px solid green”. Затем перейдите к следующей функции giveCellsClick() (строка 221).

Если ничего из этого не соответствует действительности, а это означает, что фигура не имеет возможного хода, ничего не делайте (return;)

Теперь нам нужно присвоить ячейкам атрибут onclick на основе возможных ходов selectedPiece.

Итак, если selectedPiece.[movement property] истинно, присвойте этой ячейке атрибут onclick, равный makeMove().

makeMove() будет принимать в качестве аргумента число или место, в которое будет перемещена фигура. Если фигура собирается переместиться на семь делений (selectedPiece.seventhSpace), присвойте ячейке onclick из makeMove(7), и это будет сделано для всех возможных ходов.

Вот причина, по которой нам нужно присвоить ячейкам атрибут onclick вместо event listener: если бы мы дали ячейкам прослушиватель событий и передали параметр, функция немедленно запустится, потому что технически она вызывается. Об использовании анонимной функции не может быть и речи, потому что ее нужно удалить, и вы не можете удалить анонимные прослушиватели событий.

Это конец цепочки функций, когда вы щелкаете по фрагменту, поэтому нам больше не нужно автоматически вызывать какие-либо функции. Следующая функция (makeMove()) — это то, что будет вызываться при щелчке по ячейке ПОСЛЕ выбора части.

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

Сначала нам нужно удалить часть на передней панели, мы можем легко сделать это с помощью .remove() (строка 259) и изменить .innerHTML ячейки на пустые строки (строка 260). С комбинацией этих двух ячейка будет выглядеть так, как будто там ничего не было.

Теперь о заявлении if…else. if (turn) (строка 261), затем… if (selectedPiece.isKing) мы хотим создать новый HTML-элемент части, которая имеет класс короля в новой ячейке, по которой щелкнули (строка 263). Затем сбросьте переменную redPieces на querySelectorAll(“p”) (строка 264); это очень важно, потому что, если этого не сделать, только что созданный новый фрагмент не будет сохранен в памяти JavaScript. Поэтому, когда вы щелкаете новый элемент, когда наступает следующий поворот, ничего не произойдет, потому что JavaScript не предоставил ему прослушиватель событий. Поэтому убедитесь, что эта строка добавлена.

Дублируйте этот код для оператора else в строке 265, но без класса короля.

Приведенный выше код можно продублировать для внешнего оператора else (строка 269), но измените все, что касается красных частей, на черные части и не забудьте изменить “p” на “span” (строки 272 и 275).

Теперь я сохраняю selectedPiece.indexOfBoardPiece в переменной (строка 279). Я не совсем уверен, почему, но вы не можете передавать свойства объекта непосредственно в аргументы функции, поэтому это необходимо сохранить как переменную.

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

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

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

Сначала мы меняем исходное положение выбранной фигуры на null (строка 289), потому что фигуры там больше нет; затем измените положение новой фигуры, равное id той части, которая была перемещена (строка 290).

Выражение if в строке 291 говорит: если его красные поворачиваются, а selectedPiece.pieceId < 12, а его новое положение — >= 51 (≥ 51 — последняя строка на доске), тогда присвойте фигуре класс “king”. Затем сделайте обратное для хода черных (строки 294–296).

Теперь, если параметр removePiece существует (строка 297), измените удаленную часть массива board на null. Теперь, если его красный цвет станет красным (строка 299), заставьте фигуру исчезнуть на переднем конце и удалите счет с черного (строка 301). Тогда наоборот, если ходят черные.

Как только все это будет завершено, вызовите 3 функции: resetSelectedPieceProperties(), removeCellonclick() и removeEventListeners(). Первые два мы уже написали, поэтому я не буду их рассматривать, но их необходимо вызвать, чтобы все данные можно было сбросить для следующего хода (вот почему мы не вызывали никаких других новых функций внутри этих двух: чтобы их можно было использовать повторно).

Пришло время для removeEventListeners().

Не волнуйтесь … мы почти закончили.

Если это красный ход (строка 315), пропустите весь redsPieces и удалите прослушиватель событий click, тогда в операторе else сделайте то же самое для blacksPieces.

Затем вызовите функцию checkForWin() .

Если какой-либо счет равен 0, измените противоположный текст хода на .style.display = “none”, а игрока, который выиграл, на «КРАСНАЯ ПОБЕДА!».

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

Пара примечаний: если у вас не было разделителя, не беспокойтесь об этом, а петли, которые вы видите в строках 331 и 338, вызваны тем, что у меня несколько [player]TurnText (один для мобильных устройств и один для настольных компьютеров), поэтому, если у вас только один [player]TurnText, цикл не нужен.

Теперь последняя функция changePlayer()!

Если его красный поворот, измените переменную turn на false, затем измените цвет blackTurnText на черный и redTurnText на светло-серый (наоборот, если поворот был ложным, то есть это был поворот черных).

Та же логика цикла применяется к предыдущей функции. Так что, если у вас только один [player]TurnText, цикл не нужен.

Наконец, вызовите функцию, которая была с самого начала: givePiecesEventListeners(), чтобы заново перезапустить весь цикл.

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

🎉 Поздравляю! Теперь у вас есть рабочая настольная игра в шашки! 🎉

Если вы хотите получить мой код, вы можете скачать его здесь: https://github.com/RyanBranco/Checkers

Теперь вы должны понимать, как можно использовать инструменты JavaScript (даже большинства языков программирования). Я призываю вас создать что-то самостоятельно, потому что это лучший способ учиться! Теперь тебе нет оправдания.

Об идее

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

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

• Шашки ходят только по клеткам черного цвета по диагонали.

• Простая шашка ходит только вперед на одно поле, а бьет — вперед и назад, перепрыгивая одно поле (в checkers — бьет только вперед)

• Дамка ходит и бьет вперед и назад на любое количество полей (в checkers — ходит вперед и назад только на 1 поле; бьет, перепрыгивая только 1 поле)

• Бить обязательно! При наличии нескольких вариантов боя — можно выбрать любой.

• Проигрывает тот, кто не может сделать ход.

Изначально я хотел писать на python, но потом решил сделать крутую красивую игру и выбрал Unity (C#). Спойлер: красивую игру я так и не сделал.

Реализация алгоритма

Разумеется классы, отвечающие за шашки на экране и в памяти алгоритма, разные. Я не буду останавливаться на MonoBehaviour Unity-скриптах и подробнее расскажу именно про мою реализацию алгоритма.

Сначала опишу, как я храню доску в памяти.

Класс шашки довольно прост: содержит, главное, тип шашки и ее позицию на поле, а также несколько вспомогательных переменных:

public enum PieceType
{
    EMPTY, WHITE_MAN, WHITE_KING, BLACK_MAN, BLACK_KING
}

public class Piece
{
    public PieceType Type { get; private set; }
    public Vector2Int Pos { get; private set; }
    public bool IsWhite { get; private set; }
    public bool IsKing { get; private set; }


    public Piece(PieceType type, Vector2Int pos)
    {
        Type = type;
        Pos = pos;
        IsWhite = type == PieceType.WHITE_MAN || type == PieceType.WHITE_KING;
        IsKing = type == PieceType.WHITE_KING || type == PieceType.BLACK_KING;
    }

    public void ChangePos(Vector2Int newPos)
    {
        Pos = newPos;
    }
    public void BecomeKing()
    {
        Type = IsWhite ? PieceType.WHITE_KING : PieceType.BLACK_KING;
        IsKing = true;
    }
    public void BecomeMan()
    {
        Type = IsWhite ? PieceType.WHITE_MAN : PieceType.BLACK_MAN;
        IsKing = false;
    }
}

Думаю, тут комментировать нечего.

Доска же это набор шашек и их ходов. Это не полный код доски, а только важное:

    public class Board
    {
        private Piece[,] _board = new Piece[8, 8]; // фигуры
        public List<Piece> Pieces { get; private set; } = new List<Piece>(); // те же фигуры, но в виде списка
        private List<Move> _currentMoves; // список возможных ходов
        private int[] _countCheckers = new int[5]; // счетчик шашек определенных групп (всех, белых обычных, белых дамок, черных обычных, черных дамок)
        private List<MemorisedMove> LastMoves = new List<MemorisedMove>();

      ...

        // Конструктор для установки доски по строке
        // searchAllMoves -- надо ли искать возможных ходы
        public Board (string arr, bool whitesMove = true, bool searchAllMoves = true)
        {
            int index = 0;
            // Проход по всем клеткам
            for (int y = 0; y < 8; y++)
            {
                for (int x = (y+1) % 2; x < 8; x += 2)
                {
                    if (arr[index] != '0')
                    {
                      // Индекс фигуры
                        int num = int.Parse(arr[index].ToString());
                      // Получаем фигуру
                        Piece piece = new Piece((PieceType) num, new Vector2Int(x, y));

                      // Устанавливаем и заносим в списки
                        _board[y, x] = piece;
                        Pieces.Add(piece);
                        _countCheckers[num]++;
                    }

                    index++;
                }
            }
            WhitesMove = whitesMove;
            _rowKingsMoves = 0;
            _jumpIndex = 0;
            _countCheckers[0] = _countCheckers[1] + _countCheckers[2] + _countCheckers[3] + _countCheckers[4];

            // Если нужно, ищем возможные ходы
            if (searchAllMoves)
                FindAllMoves();
        }

      ...
    }

• Конструктор Board() здесь строит доску по строке из цифр, где каждая цифра обозначает конкретную шашку (см. перечисление PieceType в классе Piece).

• Также есть конструктор, создающий глубокую копию доски.

(Разобью весь класс на части, чтобы не было пелены кода и можно было дать пояснения)

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

public void FindAllMoves ()
{
    List<Move> takingMoves = new List<Move>(); // взятия
    List<Move> simpleMoves = new List<Move>(); // простые ходы

    foreach (Piece piece in Pieces)
    {
        if (piece.IsWhite == WhitesMove)
        {
          // Для каждой фигуры сначала ищем все взятия
            takingMoves.AddRange(GetAllTakingMovesOfPiece(piece));
          // Если взятий нет, ищем простые ходы
            if (takingMoves.Count == 0)
                simpleMoves.AddRange(GetAllSimpleMovesOfPiece(piece));
        }
    }

    // Если есть взятия, отбрасываем простые ходы; иначе есть только простые ходы
    if (takingMoves.Count > 0)
    {
        // Взятия сортируем по убыванию количеству побитых шашек, чтобы сначала шли самые лучшие
        // Это поможет нам более эффективно искать сильнейшие ходы, оценивая потенциально лучшие первыми
        takingMoves.Sort((Move a, Move b) => -a.Taken.Count.CompareTo(b.Taken.Count));

        AllMoves = _currentMoves = takingMoves;
    }
    else
        AllMoves = _currentMoves = simpleMoves;
}

// Рекурсивная функция поиска взятий фигуры
// В массиве exc хранятся поля, шашки на которых мы уже побили, так как в русских шашках,
// согласно турецкому правилу, шашки снимаются с доски уже после хода (см. комментарий под кодом)
private List<Move> GetAllTakingMovesOfPiece (Piece piece, List<Vector2Int> exc = null)
{
    if (exc == null)
        exc = new List<Vector2Int>();
    List<Move> moves = new List<Move>(); // все взятия
    List<Move> movesWithFollowingTake = new List<Move>(); // взятия, после которых можно побить еще

    if (piece.IsKing)
    {
      // Перебираем все 4 направления движения
        for (int x = 1; x > -2; x -= 2)
        {
            for (int y = 1; y > -2; y -= 2)
            {
                bool opp_found = false;
                Vector2Int pos_opp = Vector2Int.zero;

              // Куда дамка встанет после прыжка
                Vector2Int target = piece.Pos + new Vector2Int(x, y);
                while (InField(target)) // Функция InField проверяет, что координаты (x, y) принадлежат полю
                {
                    if (IsEmpty(target)) // Функция IsEmpty проверяет, что поле не занято
                    {
                        if (opp_found) // Если, прыгнув на клетку target мы перепрыгнем шашку соперника, то это взятие
                            AddMove(piece.Pos, target, pos_opp); // Косвенно рекурсивно продолжаем поиск дальнейших прыжков со взятием
                    }
                    else if (_board[target.y, target.x].IsWhite == piece.IsWhite) // Если уперлись в свою шашку — то усё
                        break;
                    else
                    {
                        if (!opp_found) // Если уперлись в шашку соперника, запоминаем это
                        {
                            opp_found = true;
                            pos_opp = target;
                        }
                        else // Если уткнулись во 2-ю шашку соперника, то дальше прыгнуть не получится
                            break;
                    }
                    target += new Vector2Int(x, y);
                }
            }
        }
    }
    else
    {
      // Тут перебираем все 4 варианта взятия обычной шашки (для краткости показано только одно)
        // target - поле куда приземлимся, middle - поле, которое перепрыгнем. В данном случае прыгаем на увеличение обеих координат (вниз вправо)
        Vector2Int target = new Vector2Int(piece.Pos.x + 2, piece.Pos.y + 2);
        Vector2Int middle = new Vector2Int(piece.Pos.x + 1, piece.Pos.y + 1);
        if (InField(target) && IsEmpty(target) && !IsEmpty(middle) && _board[middle.y, middle.x].IsWhite != piece.IsWhite)
            AddMove(piece.Pos, target, middle);
        ...
        ...
        ...
    }
    if (movesWithFollowingTake.Count > 0)
        return movesWithFollowingTake;
    return moves;



    bool AddMove (Vector2Int fr, Vector2Int to, Vector2Int taken)
    {
      // Турецкий удар (см. в комментарии ниже)
        if (exc.Contains(taken))
            return false;

      // Моделируем доску, на которйо этот ход сделан
        Board nextBoard = new Board(this, deepCopyMoves:false);
        Piece thisPiece = nextBoard.MovePiece(fr, to);
        List<Vector2Int> newExc = new List<Vector2Int>(exc);
        newExc.Add(taken);

      // Проверяем, не превратилась ли наша шашка в дамку этим ходов
        bool isThisMoveKinging = !piece.IsKing && IsKinging(to, piece.IsWhite);
        List<Move> nextTakes = nextBoard.GetAllTakingMovesOfPiece(thisPiece, newExc);

        if (nextTakes.Count == 0)
        {
            moves.Add(new Move(new List<Vector2Int>() { fr, to }, new List<Vector2Int>() { taken }, isThisMoveKinging));
            return false;
        }
        else
        {
            foreach (Move nextTake in nextTakes)
            {
                List<Vector2Int> pos = nextTake.Pos;
                pos.Insert(0, fr);
                List<Vector2Int> takes = nextTake.Taken;
                takes.Add(taken);
                moves.Add(new Move(pos, takes, isThisMoveKinging || nextTake.IsKinging));
                movesWithFollowingTake.Add(new Move(pos, takes, isThisMoveKinging || nextTake.IsKinging));
            }
            return true;
        }
    }
}
// Эта функция ищет все простые ходы шашки. Она очень простая и не представляет особого интереса
private List<Move> GetAllSimpleMovesOfPiece (Piece piece)
{
    ...
}

• Здесь стоит обратить внимание на то, что все обычные ходы считаются равноценными, а взятия — нет: сильнейшие взятия это те, которые бьют больше шашек соперника.

• В функции GetAllTakingMoves, которая ищет все ходы-взятия, важную роль играет т.н. турецкое правило, согласно которому побитые шашки снимаются с доски после хода и могут мешать продолжить взятия. Например в позиции ниже, если белые возьмут дамкой e1:a5:d8:f6:d4, они не смогут взять еще и шашку c5, так как, хотя шашка b6 к тому времени уже будет побита, она все еще будет стоять на доске, мешаясь дамке белых.

  

• В функции AddMove() интерес также представляет отдельная обработка ситуации, когда шашка своим ходом превращается в дамку — в таком случае можно продолжить взятие по ее правилам.

Функция MakeMove совершает ход на доске:

public void MakeMove(Move move, bool memoriseMove = false)
{
    // Хапоминаем ход, если надо
    if (memoriseMove)
        LastMoves.Add(new MemorisedMove(move.Fr, move.To, null, move.IsKinging, _rowKingsMoves));

    // Двигаем фигуру (обновляет массив _board и позицию  в экземпляре самой фигуры,
    // возможно, также превращает экземпляр фигуры в дамку)
    MovePiece(move.Fr, move.To);

    // Удаляем из массивов побитые шашки
    foreach (Vector2Int taken in move.Taken)
    {
        Piece takenPiece = GetPiece(taken);
        _countCheckers[(int)takenPiece.Type]--;
        _countCheckers[0]--;

        Pieces.Remove(takenPiece);
        _board[taken.y, taken.x] = null;

        if (memoriseMove)
            LastMoves[LastMoves.Count - 1].AddTakenPiece(takenPiece);
    }
}

Разумеется, это только основные функции. Полный код, мониторящий доску, занимает почти 500 строк. Это довольно много, но не думаю, что можно как-то разделить ответственность: все относится непосредственно к свойствам нынешнего состояния игры.

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

Перейдем к более интересным вещам

Разработка победного алгоритма

Выбранный алгоритм — минимакс. Это набор правил для принятия решений для игр с нулевой суммой (один выиграл — другой проиграл). Он основывается на том, чтобы для всех возможных ходов, предугадать ответы соперника, и для каждого ответа — выбрать свой ответ, на который опять предугадать возможные ответы соперника.

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

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

Итак, к алгоритму.

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

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

Класс AI.sc умеет оценивать позицию, подсчитывая качества шашек обоих цветов на доске. Качество рассчитывается как произведение стоимости шашки, специального бонуса клетки (например, шашки в центре дороже шашек с левого или правого края доски) и Y-бонуса (бонус по вертикали: простая шашка тем дороже, чем ближе она к дамочным полям).

Качество шашки = value * _squareBonus * yBonus

Значения стоимостей и бонусов я выбрал такие:

int _checkerValue = 100; // стоимость простой шашки
int _kingValue = 250; // стоимость короля
float[,] _squareBonus = new float[8, 4] // бонус клетки
    {
        { 1.2f, 1.2f, 1.2f, 1.2f },
        { 1.15f, 1.2f, 1.2f, 1.15f },
        { 1.15f, 1.2f, 1.2f, 1.13f },
        { 1.0f, 1.2f, 1.15f, 1.0f },
        { 1.0f, 1.2f, 1.2f, 1.0f },
        { 1.0f, 1.0f, 1.0f, 1.0f },
        { 1.0f, 1.0f, 1.0f, 1.0f },
        { 1.0f, 1.0f, 1.0f, 1.0f },
    }; 

private float[] _yBonus = new float[8]; // Y-бонус

public float EvaluateMaterialAndPosition (Board board)
    {
        float eval = 0;
        // Рассчитываем качество каждой шашки
        foreach (Piece piece in board.Pieces)
        {
            Vector2Int coord = piece.Pos;
            switch (piece.Type)
            {
                case PieceType.WHITE_MAN:
                    eval += _checkerValue * _yBonus[coord.y] * _squareBonus[coord.y, coord.x / 2];
                    break;
                case PieceType.BLACK_MAN:
                    eval -= _checkerValue * _yBonus[7 - coord.y] * _squareBonus[7 - coord.y, 3 - coord.x / 2];
                    break;
                case PieceType.WHITE_KING:
                    eval += _kingValue;
                    break;
                case PieceType.BLACK_KING:
                    eval -= _kingValue;
                    break;
            }
        }
        return eval;
    }

Теперь, когда мы умеем оценивать позицию, будем рекурсивно перебирать все наши ходы, ответы на них соперника, наши ответы на ответы соперника и т.д.

Так как мы не знаем, насколько сложная нынешняя позиция и сколько таких итераций потребуется, то будем увеличивать количество итераций, т.е. сначала проанализируем позицию на глубину 2 хода, потом 4, 6 и т.д. Это называется поиск в глубину с итеративным углублением. При этом чтобы избежать бесконечного поиска введем максимальное время анализа: после его истечения мы немедленно выходим из всех функций и используем результат последней полностью завершенной итерации.

// Функция активного поиска хода запускает поиск лучшего ход в позиции
public void ActiveSearch ()
{
    int depth = 0,  startDepth = 2;
    CurrentBestMove = Move.None;
  // Единственный в позиции ход делается без раздумий
    if (_board.AllMoves.Count == 1)
    {
        CurrentBestMove = _board.AllMoves[0];
        return;
    }
    // Делаем копию доски, на которой будет проводить анализ
    // Это нужно, так как во время анализа мы будем передвигать фигуры
    Board boardCopy = new Board(_board, deepCopyMoves: true);
    _searchStartTime = DateTime.Now;
    IterativeDeepeningMinimax(boardCopy, _timeLimit, startDepth, ActiveSearchDepth, ref CurrentBestMove, ref depth, true);

    if (CurrentBestMove == Move.None)
        CurrentBestMove = boardCopy.AllMoves[new System.Random().Next(0, boardCopy.AllMoves.Count)];
}

// Функция минимакса с итеративным углублением: запускает минимакс со все большей и большей глубиной,
// при этом следя за ограничением во времени
public void IterativeDeepeningMinimax (Board board, float timeLimit, int minDepth, int maxDepth, ref Move bestMove, ref int depth, bool isWhileActiveSearch)
    {
        for (depth = minDepth; depth <= maxDepth; depth++)
        {  
            (float eval, Move tempBestMove) = Minimax(board, depth, board.WhitesMove, timeLimit);
            // Если успели полностью завершить итерацию, сохраняем ее результат
            if ((DateTime.Now - _searchStartTime).TotalSeconds < timeLimit && tempBestMove is not null && tempBestMove != Move.None)
            {    
                bestMove = (Move) tempBestMove.Clone();
            }
          // Если не успели и итерация завершилась экстренно, она неполная и ее результат нам не нужен
            else
            {
                depth -= 1;
                break;
            }
  
            // Мы перестаем искать, если на какой-то итерации найдем форсированный выигрыш
            if (eval >= Infinity && board.WhitesMove || eval <= -Infinity && !board.WhitesMove)
                break;
        }
    }

// Функция минимакса находит лучший ход в позиции за конкретного игрока
// Возвращает сам ход, а также оценку позиции, которая получится, если этот ход сделать
// depth показывает, на сколько еще итераций-рекурсий нам осталось углубиться (с каждым новым рекурсивным вызовом depth уменьшается)
// maximizingPlayer показывает, за какого игрока мы ищем лучший ход, т.е. позицию для какого игрока мы пытаемся улучшить
public (float, Move) Minimax (Board board, int depth, bool maximizingPlayer, float timeLimit)
        {
          // Проверка времени 
            if ((DateTime.Now - _searchStartTime).TotalSeconds >= timeLimit)
                return (0, null);

          // Проверяем нынешнее состояние позиции (возможно, уже гейм овер)
            GameState state = board.GetGameState();
            if (state != GameState.IN_PROCESS)
            {
                if (state == GameState.WHITE_WIN)
                    return (Infinity + depth, Move.None);
                if (state == GameState.BLACK_WIN)
                    return (-Infinity - depth, Move.None);
                else
                    return (0, Move.None);
            }

            // Если это последняя итерация, просто возвращаем оценку позиции
              // Ход здесь не важен, так как лучшим станет именно ход, ведущий к позиции с наилучшей оценкой
            if (depth == 0)
            {
                float eval = Evaluate(board);
                return (eval, Move.None);
            }

            // Если ход единственный -- см. комментарии под кодом
            if (board.AllMoves.Count == 1)
            {
                Move move = board.AllMoves[0];

                board.MakeMove(board.AllMoves[0], memoriseMove: true);
                board.OnMoveFinished(board.AllMoves[0]);
                float eval = Minimax(board, depth, alpha, beta, !maximizingPlayer, timeLimit, isWhileActiveSearch).Item1;
                board.UnmakeLastMove();
                _transpositions.Add(new Transposition(PositionCache, eval, Infinity, board.AllMoves[0]));
                return (eval, board.AllMoves[0]);
            }

            // Ищем лучший ход (за белых)
            Move bestMove = Move.None;
            if (maximizingPlayer)
            {
                float maxEval = -Infinity;
              // Проходимся по всем ходам
                foreach (Move move in board.AllMoves)
                {
                  // Делаем его
                    board.MakeMove(move, memoriseMove: true);
                    board.OnMoveFinished(move);
                  // И запускаем минимакс из полученной позиции, но со стороны ПРОТИВНИКА
                    (float eval, Move compMove) = Minimax(board, depth - 1, alpha, beta, false, timeLimit, isWhileActiveSearch);

                  // Отменяем сделанный ход
                    board.UnmakeLastMove();

                  // Проверка, что минимакс со стороны противника не завершился экстренно из-за нехватки времени
                    if (compMove == null)
                        return (0, null);
                  // Проверяем, является ли этот ход лучше наилучшего найденного
                    if (eval > maxEval)
                    {
                        maxEval = eval;
                        bestMove = move;
                    }
                }
                return (maxEval, bestMove);
            }
          // Аналогично за черных
            else
            {
                float minEval = Infinity;
                foreach (Move move in board.AllMoves)
                {
                    board.MakeMove(move, memoriseMove: true);
                    board.OnMoveFinished(move);

                    (float eval, Move compMove) = Minimax(board, depth - 1, alpha, beta, true, timeLimit, isWhileActiveSearch);
                    board.UnmakeLastMove();

                    if (compMove == null)
                        return (0, null);
                    if (eval < minEval)
                    {
                        minEval = eval;
                        bestMove = move;
                    }
                }
                return (minEval, bestMove);
            }
        }

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

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

Я считаю очень важным здесь то, что я не копирую доску, чтобы проанализировать каждый ход: ВЕСЬ поиск лучшего хода выполняется на одной доске (копии игровой), просто мы умеем совершать (make) и отменять ходы (unmake). Таким образом тяжелая функция глубокого копирования доски вызывается лишь единожды.

В целом, такой код уже способен более менее играть и даже не зевать фигуры в один-два хода!

Profit!

Улучшениe №1: alpha-beta pruning

Первым улучшением, которое в разы улучшило скорость анализа, стало альфа-бета отсечение.

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

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

Таким образом, мы можем отсечь (prune) много лишних ветвей, избавившись от заведомо ненужных вычислений. В интернете много информации об этом улучшении, поэтому я не буду дальше его разжевывать, просто скажу, как я его реализовал.

Функции минимакс я добавил аргументы alpha и beta, которые при первом вызове из IterativeDeepeningMinimax передаются как -Infinity и Infinity соответственно.

После 115-й строки я добавил проверку на отсечение по альфе:

...
alpha = Mathf.Max(alpha, eval);
if (beta <= alpha)
  break;
...

А после 139-й — по бете:

...
beta = Mathf.Min(beta, eval);
if (beta <= alpha)
    break;
...

Double profit!

Улучшениe №2: транспозиции

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

Стоит понимать, что если в позиции X на глубине d найден лучший ход n, то этот же ход является лучшим в той же позиции и на глубинах меньше d. А вот на глубинах больше d — не факт: возможно, нам казалось, что он лучший, но мы просто не досчитали и на самом деле ход проигрывающий. Если же в позиции X ход n ведет к форсированной победе, то глубину можно считать бесконечной, так как мы точно знаем, что ход выигрывающий.

Позиции считаются одинаковыми, если не только все шашки стоят на одинаковых местах, но и очередность хода совпадает.

Транспозиции будут храниться в списке private List<Transposition> _transpositions = new List<Transposition>();

Где класс транспозиции выглядит так:

public class Transposition
{
    public string Pos { get; private set; }
    public float Eval { get; private set; }
    public int Depth { get; private set; }
    public Move BestMove { get; private set; }

    public Transposition(string pos, float eval, int depth, Move bestMove)
    {
        Pos = pos;
        Eval = eval;
        Depth = depth;
        BestMove = bestMove;
    
    }
    public bool IsSameTo (string otherPos)
        => Pos == otherPos;
}

В начале функции Minimax() (после, конечно, проверки на истечение времени) будем проверять, не встречали ли мы ранее данную позицию на подходящей глубине:

string PositionCache = board.Board2Number(); // Переводит позицию в строку

Transposition pos_trans = null;
pos_trans = _transpositions.FirstOrDefault(tr => tr.IsSameTo(PositionCache));
if (pos_trans != null)
{
    if (pos_trans.Depth >= depth)
    {
        return (pos_trans.Eval, pos_trans.BestMove);
    }
}

Позиции, кстати, сравниваются как строки, т.к. каждую позицию можно однозначно представить как строку из 32 символов — фигур на черных полях (+1 символ для очередности хода).

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

// за белых
AddTransposition(new Transposition(PositionCache, maxEval, depth, bestMove));
return (maxEval, bestMove);

// за черных
AddTransposition(new Transposition(PositionCache, minEval, depth, bestMove));
return (minEval, bestMove);

Функция AddTransposition просто добавляет транспозицию в список, не забывая убедиться, что там уже нет такой же позиции, но на меньшей глубине. В таком случае она стирается, так как зачем нам менее глубокий анализ, если уже подоспел более глубокий?!

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

Triple profit!

Улучшение №3: книга дебютов и эндшпилей

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

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

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

Однако мне удалось найти стандартизированные записи шашечных партий и выудить из них дебюты и эндшпили (несколько первых ходов из каждой партии и несколько последних). Поэтому я подключаю к своему алгоритму два блока:

private OpeningBook _openingBook;
private EndgameBook _endgameBook;

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

public abstract class TheoryBook
{
    protected abstract string TheoryPath { get; }
    private BookRecord _records;

    public TheoryBook()
    {
        Debug.Log(TheoryPath);
        using (StreamReader reader = new StreamReader(TheoryPath))
        {
            _records = JsonUtility.FromJson<BookRecord>(reader.ReadToEnd());
        }
        _records.BuildUpDictionary();
    }

    public bool TryGetBestMove(string pos, out string move)
    {
        if (_records.ContainsPosition(pos))
        {
            move = _records.GetMoveFor(pos, BookRecord.BookMoveSelector.Random);
            return true;
        }
        else
        {
            move = null;
            return false;
        }
    }
}

[System.Serializable]
public class BookRecord
{
    public List<string> positions;
    public List<string> moves;
    public int CountRecords => moves.Count;

    private Dictionary<string, List<string>> _pairs;

    public enum BookMoveSelector
    {
        Random, First, Last
    }

    public BookRecord()
    {
        positions = new List<string>();
        moves = new List<string>();
    }

    public void AddRecord(string pos, string move)
    {
        positions.Add(pos);
        moves.Add(move);
    }

    public void BuildUpDictionary()
    {
        _pairs = new Dictionary<string, List<string>>();
        for (int i = 0; i < CountRecords; i++)
        {
            if (_pairs.ContainsKey(positions[i]))
                _pairs[positions[i]].Add(moves[i]);
            else
                _pairs.Add(positions[i], new List<string>() { moves[i] });
        }
    }

    public bool ContainsPosition(string pos)
    {
        return _pairs.ContainsKey(pos);
    }
    public string GetMoveFor(string pos, BookMoveSelector selector)
    {
        switch (selector)
        {
            case BookMoveSelector.Random:
                return _pairs[pos][new System.Random().Next(0, _pairs[pos].Count)];
            case BookMoveSelector.First:
                return _pairs[pos][0];
            case BookMoveSelector.Last:
                return _pairs[pos][_pairs[pos].Count - 1];
            default:
                return _pairs[pos][0];
        }
    }
}

Теперь наша программа умеет делать первые 4-5 ходов моментально, пока у нее не закончится теория.

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

Анализ результатов

Мы получили работающую программу для игры в русские шашки.

Лично меня она разносит в пух и прах (возможно, потому что еще за пару месяцев до начала разработки я не умел нормально играть в шашки и зевал фигуры каждый ход). Я также дал ей сыграть с некоторыми приложениями в плеймаркете и она обыгрывает многие из них на большинстве уровней сложности. Оно также обыгрывает любителей в приложении Quick Checkers.

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

Например, возможно, отношение стоимости обычной шашки к дамке должно быть не 100:250, а 100:150 или 100:500. Возможно, стоять в центре, а не на краю шашкам выгоднее не в 1.25 раза, а в 1.1 или 1.5.

Возможно, возможно, возможно…

Разумеется, это все можно настроить, если реализовать «турнир» между компьютерами и постепенно мутировать эти числа, однако чтобы программа могла адекватно играть, ей нужно 10-15 секунд на КАЖДЫЙ ХОД (что дает глубину анализа 9-10 ходов вперед). Так как в шашечной партии в среднем ходов 30, одна такая партия может занять 5-8 минут, а чтобы построить нормальный процесс мутационной эволюции потребуется организовать, пожалуй, сотни и тысячи партий.

Надеюсь, кому-то мой опыт окажется полезным и интересным. Самому мне также интересна эта тема, поэтому я буду рад, если в комментариях найдутся знающие люди, которые смогут подсказать другие возможные улучшения и ускорения алгоритма. Я также не отрицаю, что определенный потолок скорости может задавать Unity, так как, скорее всего, на чистом C++ алгоритм будет работать быстрее, чем на Unity+C#, но переписывать все на С++ я не хочу, к тому же я не знаком с графическими библиотеками С++, чтобы выводить все это на экран.

P.S. Предложениям буду рад, конечно, всем, но что-то высшематематическое вряд ли смогу реализовать. Уровень продвинутой школьной математики:)

Автором статьи является один из читателей нашего форума — Елевферий Васильевич Миронов (elevferii_pechori@mail.ru).

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

Методы алгоритмизации ИИ бывают разные, например:

1. Метод перебора (полный, альфа-бета перебор, перебор с амортизацией отказов, перебор с нулевым окном и др.). Например для игр: шахматы, шашки, кристики-нолики;
2. На основе знаний (база правил эксперта — в Прологе это факты и правила);
3. Машинное обучение (нейронная сеть).

1. Причины написания программы

Игра в шашки с компьютером не «ново», а алгоритмизацией ИИ для шахмат вообще занимаются более 50 лет. Мне же было интересно попробовать себя в написании ИИ для шашек на Прологе, так как хотелось увидеть насколько просто написать на Прологе такую непростую программу. Пролог позволяет написать программу гораздо быстрее, короче и читабельней, чем на вычислительных языках, например С++. Он как раз и предназначен для решения задач с искусственным интеллектом (англ. AI).

2. Причины опубликования статьи

В Интернете я не нашёл подобной статьи или программы (именно написанной на Прологе) со способом алгоритмизации ИИ использованном в моей программе, что и побудило меня опубликовать данную статью. Кроме того, программа запускается в приложении работающем на Андроиде (см. статью о приложении Prolog Classic и ссылку на скачивание [1]), что для многих может иметь удобство.

3. Алгоритм работы ИИ

Для алгоритмизации ИИ я выбрал метод полного перебора и метод с использованием базы знаний. Основным методом является метод на основе знаний.
Почему я выбрал именно этот метод основным, тут две причины:

1. Полный перебор для такой игры невозможен (слишком много вариаций). Перебор с ограниченной глубиной, для такой игры, очень ресурсоёмок, даже при не очень большой глубине (стек приложения Prolog Classic будет есть много памяти; программа будет сильно тормозить из-за очень большого количества просчётов ходов), а с оптимизированными алгоритмами перебора я плохо знаком (альфа-бета перебор, перебор с амортизацией отказов и т.д.);
2. Метод на основе знаний способен дать лучшие комбинации, даже если они очень длинные и поэтому тяжелы для просчёта.

Алгоритм работы ИИ следующий:

1. Сначала, программа ищет в базе комбинаций ход, для состояния текущей доски (это могут быть как просто ходы, так и ходы-удары): среди дебютных ходов, если нет дебютной комбинации- тогда среди обычных комбинаций:
   1. В дебютных ходах определяется точное расположение каждой шашки, каждой пустой клетки, так как от каждой мелочи зависит тот или иной розыгрыш дебюта;
   2. В остальных же ходах, когда шашек на доске уже довольно меньше, определение состояния доски в базе правил является довольно вольным («абстрактным»), т.е. в правиле указывается точное расположение необходимых шашек и пустых клеток про остальные же указывается, что где-то могут стоять как простые шашки, так и дамки; где-то — шашка чёрная, или белая, или пустая клетка; и др. возможные комбинации;
2. Если программа не находит готовый ход, то затем она сначала проверяет нужно ли какой-нибудь шашкой бить, и если да — то ищет какой лучше. Вот здесь уже используется алгоритм полного перебора:
   1. Собирается в список все возможные удары разными шашками компьютера;
   2. Каждому ходу-удару компьютера приписывается оценочный вес. Он находится путем сложения веса хода (за выигрыш одной шашки игрока приписывается, скажем, +100) и лучшего веса удара игрока (наименьшее число), который будет после этого хода компьютера. Для ход-ударов игрока, в свою очередь, также считается оценочный вес: вес хода (за выигрыш одной шашки приписывается, скажем, -100) и лучший вес удара компьютера (наибольшее число), который будет после этого хода игрока. Для лучшего понимания сказанного, можно представить себе дерево, у которого первые ветки идущие от корня — это первые ходы-удары компьютера. От каждой этой ветки расходятся другие ветки представляющие собой ходы-удары противника. От последних веток расходятся ещё ветки опять являющимися ударами компьютера и т.д. пока кому-нибудь нечем будет бить (см. рис.).

      

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

   3. Из найденных ходов-ударов компьютера выбирается ход с наибольшим весом, то есть, лучший ход;
3. Если и бить не надо, тогда просчитывается лучший простой ход:
   1. Сначала программа собирает список всевозможных простых ходов шашками (не забывая про дамок).
   2. Для каждого хода присваивается вес или по другому очки, значение которого зависит от:
      1. Станет ли шашка дамкой на этом ходе (стать дамкой это как съесть около 2 пешек);
      2. Если в правом или левом верхнем углу есть простые шашки противника, а у компьютера есть дамка, то предпочтительнее сделать простой ход дамкой (для этого к весу прибавятся соответствующие очки) причём такой, чтобы прийти потом к диагонали, которая не даст пройти шашкам игрока к дамке (для этого идёт подсчёт с какой стороны больше шашек противника);
      3. Если есть дамка, которая уже стоит на диагонали, на которой не даст пройти шашкам игрока, то ход простой шашкой предпочтительнее, чем этой дамкой (для этого к весу прибавляются соответствующие очки, но меньше чем в предыдущем пункте.
      4. После всех выше сказанных пунктов для ходов, после которых игрок бьёт шашкой, методом полного перебора, вычисляется дополнительный вес, представляющий из себя наименьший вес из весов ответных ходов-ударов игрока, который и прибавляется (так же как при полном переборе для ударов компьютером, см. выше). Благодаря этому пункту, компьютер избежит не только нежелательных ходов, но и сможет совершать подставные ходы, зная, что его, после этого хода, ждёт выигрыш);
   3. После всего и берётся лучший ход.

4. Разбор программы

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

Итак, по порядку:

1) Перед началом игры на экран выводится начальная позиция шашечной доски, игрок играет белыми (см. рисунок).

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

2) Ядром программы является предикат game, который состоит из нескольких правил:

game:-
    pos(P0),
    moveMe(P0,P1),
    retractA(pos(_)),    
    assertA(pos1(P1)),
    false;
    
    pos1(P1),
    noWayOrEnd(P1,-),
    write(вы_победили!),nl;

    exit;

    pos1(P0),
    moveAI(P0,P1),
    retractA(pos1(_)),
    assertA(pos(P1)),
    false;
    
    pos(P1), 
    noWayOrEnd(P1,+),
    write(ai_победил!),nl;

    pos(P1),
    draw(P1,0),
    drawRead;
    
    game.

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

Второе правило истинно, если побиты все шашки компьютера, или ему некуда ходить (предикат noWayOrEnd/2), и при доказательстве его программа заканчивает свою работу;

Третье правило истинно, если истинен предикат exit/0, для которого существует единственный факт при вводе игроком в консоли слово выход, после чего программа прекращает свою работу;

Четвёртым правилом компьютер совершает ход при помощи предиката moveAI/2 и перезаписыванием факта о расположении шашек на доске. Снова в конце правила стоит ложный предикат false, чтобы при продолжении игры вернуться к первому правилу (к ходу игроком). Ложный предикат false стоит в конце ещё с той целью, чтобы он своим откатом делал и откат стека программы, т.к., иначе, память устройства переполнится или же программа будет подтормаживать;

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

Шестое правило проверяет остались ли на доске одна дамка игрока и одна дамка компьютера, если да, то компьютер предлагает игроку завершить игру ничьёй, на что игрок может или согласиться, или отказаться (см. «Ничья в партии русских шашек» [2]);

И последнее седьмое правило, в случае продолжения игры, отсылает нас снова на первое правило.

3) Предикат moveMe/2:

moveMe(P0,P):-
  readMe(P0,P),
  writeMove(P).

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

4) Предикат moveAI/2. Состоит из одного правила, где, вначале, предикат moveAI_1/3 возвращает сделанный компьютером ход и новое состояние доски, а после выводится на экран сделанный компьютером ход и предикатом writePos/1 новое состояние доски;

moveAI(P0,P):-
  moveAI_1(P0,AB,P),
  write(ai_ходит:),tab(1),write(AB),write(.),nl,
  write(ai_сделал_ход:),nl,
  writePos(P).

5) Предикат moveAI_1/3:

moveAI_1(P,AB,P1):-
  moveHitComb_ai(P,AB,P1), !;%Удар в комбинации

  moveSimpleComb0_ai(P,AB,P1), !;%Простой ход из точных комбинаций

  write(ждите...),nl,
  false;

  moveSimpleComb_ai(P,AB,P1), !;%Простой ход из комбинаций

  moveHit_ai(P,AB,P1), !;

  moveSimple_ai(P,AB,P1).%Простой ход шашкой или такой ход, чтобы потом съесть побольше шашек

Рассмотрим правила данного предиката:

1. Сначала с помощью предиката moveHitComb_ai/3 ищется — есть ли возможность ударить шашкой с помощью записанного хода в базе знаний рассчитанного на определённую комбинацию (тот самый дополнительный файл). Заметим, что программа может сама производить сложные комбинации ударов: считает количество побитых шашек противника против своих (даже при обоюдных ударах), учитывает, если будет побита дамка (об этом подробно см. ниже). Но, поскольку бывает, что есть случаи, когда нужно бить в убыток себе, зная, что в будущем это даст сокрушительную комбинацию против противника, то для таких случаев и записаны в базе знаний ходы-удары выходящие из общего правила программы. Обратим внимание, что здесь среди записанных ходов в базе знаний есть как точные (то есть, когда точно известно где какая шашка должна стоять или пустая клетка), так и «абстрактные» (когда при помощи разных цифр мы даём компьютеру понять где должна быть обязательно пустая клетка или, скажем белая шашка, а где может быть как чёрная так и белая шашка и т.д.). Точные ходы нужны для дебютов (см. выше). «Абстрактные» ходы используются в середине и в конце партии, где нужно чтобы некоторые определённые шашки были на месте и пустые клетки, в остальных местах же могут присутствовать шашки, а могут и нет, или даже дамки, в других местах могут быть как белые, так и черные шашки и т.д. (подробнее читайте в начале файла базы комбинаций);
2. Если записанного удара для текущей доски нет, тогда в следующем правиле, с помощью предиката moveSimpleComb0_ai/3 ищется — есть ли для текущей доски записанный простой ход разыгрывающий лучшую комбинацию для данного дебюта (из точных ходов);
3. Если второе правило тоже потерпело неудачу, то следующее правило выводит сообщение: «ждите…», т.к. четвёртое, а может и пятое правило займут немалое время (иногда полминуты на процессоре 3 ГГц), в конце стоит false, чтобы начало работать следующее правило;
4. Четвёртое правило и в нём предикат moveSimpleComb_ai/3 ищет простой ход, но из «абстрактных» ходов. Обратите внимание, в начале каждого факта базы знаний, первые два аргумента содержат количество белых шашек и количество чёрных (это значение либо точное, либо указаны пределы «от и до» — для «абстрактных» ходов). Это помогает быстро отсеивать ненужные для проверки факты, т.к. сравнивать матрицу 8х8 текущей доски с матрицей каждого факта, для большого количества фактов это очень накладно;
5. Пятое правило, при неудачах предыдущих правил, пытается сделать ход ударом с помощью предиката moveHit_ai/3. Рассмотрим как программа выбирает какой шашкой бить:

   moveHit_ai(P,AB,P1):-
     getHitsBoard_ai(P,P,[8,7,6,5,4,3,2,1]),  
     hits(_,_,_,_,_),
     assertZ(assert_hit),
     setAllHits_ai,       
     getMaxNum_ai(1,N),     
     setMaxMinList_ai(N),    
     retractZ(hits(s(P1,AB),_,_,0,end)).

   1. Предикат getHitsBoard_ai/3 находит все чёрные шашки на доске, которые могут ударить по белым, и записывает их всевозможные ходы-удары фактами hits/5 (если записывать в список, потом им пользоваться, при многом его использовании стек приложения будет быстро расти в объёме памяти»);
   2. Далее предикат setAllHits_ai/0 берёт начальные ходы и ищет есть ли белые шашки, которые обратно могут ударить. Потом снова ищет есть ли чёрные шашки, которые ответно могут ударить по белым. И так, до тех пор, пока не на какой позиции не смогут ответить (см. выше полный перебор), при этом в каждом факте записывается список с историей (например [c3-e5,b6-d4,a3-c5]) обоюдных ходов-ударов, каждый альтернативный вариант порождает новый факт со своим списком. Каждый список истории имеет список весов, то есть каждому ходу соответствует оценочный вес;
   3. После записи всех этих списков, предикат setMaxMinList_ai/1 берёт факты с самыми длинными историями и сгруппировав их по одинаковой историей, но с разным концом — из каждой группы берёт один факт у которого сумма веса последнего хода от ударов является: наименьшей — если это ход игрока (т.к. компьютер ожидает худшего), и наибольший — если это ход компьютера. Сохранённая сумма веса хода (очки за простой ход или удар) прибавляется к найденной сумме веса предыдущего хода и последний ход из истории убирается. В результате, в своей рекурсии, предикат setMaxMinList_ai/1 дойдёт до того, что останется один факт с одним наибольшим весом и одним ходом. Вместе с этим фактом мы получаем нужный нам ход-удар;
6. Последнее правило включает в себя предикат moveSimple_ai/3. Суть его в том, что он собирает в фактах все возможные простые ходы шашками (не забывая про дамок) и находит лучший простой ход, как написано выше. К вышесказанному добавлю, что за выигрыш простой шашки компьютеру даётся плюс 105 очков, а игроку минус 100 — эта разница нужна для того, чтобы компьютеру было выгодно бить и при равном выигрыше простых шашек или дамок (см. стратегии игры в шашки [3]);

   moveSimple_ai(P,AB,P1):-
     getStepBoard_ai(P,P,[8,7,6,5,4,3,2,1]), 
     hits(_,_,_,_,_), 
     assertZ(assert_hit),
     setAllHits_ai,             
     getMaxNum_ai(1,N), 
     setMaxMinList_ai(N),     % write('----'),nl,writeR,%...
     retractZ(hits(s(P1,AB),_,_,0,end)).

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

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

Программа по шашкам и файл с комбинациями находятся здесь. Файл с комбинациями (Combs.txt) нужно скопировать в папку Download внутренней памяти.

Приложение скачать можно с Яндекса здесь: https://disk.yandex.ru/d/5ED-43Uveub1ew.

Список литературы

1. Исполнение Пролог-программ на Android. URL: https://pro-prof.com/forums/topic/исполнение-пролог-программ-на-android00
2. Правила игры в шашки. URL: https://minigames.mail.ru/info/article/shashki_pravila
3. Как выиграть в шашки. URL: https://ru.wikihow.com/выиграть-в-шашки

Welcome to CodeReview! I’ll start by saying thank you for posting a somewhat-complex package of code. At first blush, your code appears to be written in the generally-accepted style and appears well organized and somewhat documented.

Functionality

Before I actually review the code, I’ll point out that I tried to play the game. Here’s my experience:

Your color is: ○
     1 2 3 4 5 6 7 8

A   | |●| |●| |●| |●|   A
B   |●| |●| |●| |●| |   B
C   | |●| |●| |●| |●|   C
D   | | | | | | | | |   D
E   | | | | | | | | |   E
F   |○| |○| |○| |○| |   F
G   | |○| |○| |○| |○|   G
H   |○| |○| |○| |○| |   H

     1 2 3 4 5 6 7 8
Choose you checkerf1
Enter coordinatese1
Choose you checkerf1
Enter coordinatese2
Test Error
Your color is: ●
     1 2 3 4 5 6 7 8

A   | |●| |●| |●| |●|   A
B   |●| |●| |●| |●| |   B
C   | |●| |●| |●| |●|   C
D   | | | | | | | | |   D
E   | |○| | | | | | |   E
F   | | |○| |○| |○| |   F
G   | |○| |○| |○| |○|   G
H   |○| |○| |○| |○| |   H

     1 2 3 4 5 6 7 8

So I have some comments on the actual operation of the game :-).

Playability

First, the game board does not color black/white squares. This makes it harder to play, since the alternating colors help with distinguishing different rows/columns, as well as providing a visual crutch for understanding move possibilities.

Next, the coordinate system is perfectly functional, but not at all intuitive. I’d suggest you consider some alternatives, like labelling the individual checkers with letters A-L instead of circles. Similarly, you might consider enumerating the possible destinations for movement. Either explicitly (redraw the board with 1..4 markers) or implicitly (draw a compass rose with 1..4 on it alongside the board).

Input/Output

The prompt needs to include a space at the end. Otherwise, you get what I got:

Choose you checkerf1

There is no indication of a help system. If someone doesn’t know how to play checkers, or doesn’t remember, how do they get help? Where are the rules of play?

If I enter a bad move, as I did, there’s no rebuff message. Instead, just a new prompt. You should explain that my move is invalid, and either print a rule summary («You must move 1 space diagonally, or jump over an enemy piece diagonally») or print an enumeration of valid moves for the piece.

I don’t know what a Test Error is. But I’m pretty sure that it shouldn’t be appearing during gameplay.

Naming

I have two comments on your file naming. First, instead of game_loop.py you should have named the file checkers.py or main.py (or __main__.py). Because there’s nothing obvious about what game this is, just looking at the file names. I mean, deck_and_cheez.py? What game did you start writing before you switched to checkers?

Second, there just isn’t that much code in these files:

aghast@laptop:~/Code/so/checkers$ wc -l *py
  312 bot.py
  692 deck_and_cheez.py
   58 game_loop.py
 1062 total

Why not just move all the code into checkers.py? This isn’t java, there’s no requirement to have a bunch of little files laying around.

game_loop.py

Structure

Everything in this file should be in a function. Possibly a different function in a different class, but definitely in a function. The standard idiom for python scripts is this:

def main():
    ... all the stuff that isn't in a function ...

if __name__ == '__main__':
    main()

Use this idiom. It makes it possible to do a bunch of things, including writing unit tests, that will benefit you. It doesn’t cost much (just one line, and some tabs), and pays off quickly.

Modularity

What do I learn from this code? (I deleted some vertical space for convenience.)

colors = ['○', '●']
deck = deck_and_cheez.Deck(random.choice(colors))
checker_pos = deck_and_cheez.CurrentChecker()
ALLIES = None
ENEMY = None

while True:
    print(f'Your color is: {deck.color}')
    deck.print_current_deck()

    if ALLIES is None:
        ALLIES = deck.color
    elif ENEMY is None:

Three things. First, is that your deck_and_cheez.Deck class is broken. Second, your deck_and_cheez.CurrentChecker class is even worse! Third, you aren’t taking a broad enough view.

class Deck

A class is supposed to be self-sufficient. If you give it the required arguments at creation time, the returned instance will stand alone.

Let’s look:

• Naming: checkers is a «board game». A better name for Deck would be GameState or Board. In English, a deck is either a floor on a ship, or an alias for a pack of cards. Poker and Pinochle are played with a Deck, while Checkers and Chess are played with a Board.

• From the colors = [...] variable, you don’t have a Deck.COLORS that provides this data to callers. Yet, this is a pretty important part of the Deck so why isn’t it there?

• From the Deck(random.choice(colors)), it seems you don’t need to tell Deck what both colors are (you only pass in one color). Thus, I sense there is a second copy of the colors = [...] over in the Deck class somewhere. (In fact, it’s worse. See below.)

• The code to set ALLIES and ENEMY is determining the value of the random choice you passed in as a parameter. And the two «constants» are only used to determine whose turn it is to play. This could be a part of Deck. It also could be implemented in code, just by writing player_turn() ; computer_turn().

Suggestions

I don’t think you need to «specify» a player color on creation of a new Deck. I think you should just randomly pick one, and make it available to users of the class:

deck = Deck()
player_color, bot_color = deck.player_colors

Once you have the colors allocated inside Deck, you can write a method that cycles the player-turn tracking without having to pass in any parameters:

deck.end_turn()

You should provide a mechanism for determining the end of the game. That could be a method on Deck or an exception raised by the turn handlers. Doing this makes the game loop clearer.

while deck.in_progress:

or

try:
    while True:
        player_turn()
        robot_turn()
except GameOver:
    pass

class CurrentChecker

This class is so low-key that I almost didn’t catch it. Your usage model is that you create an instance of the class:

checker_pos = deck_and_cheez.CurrentChecker()

and then later, during the human-player handling, you update it:

checker = input('Choose you checker').upper()

if deck.check_position(checker):
    if deck.check_checker_pos(checker):
        current_checker = checker_pos.coord(checker)

Problematically, you are calling methods on the deck class before you update the current_checker instance.

Suggestions

This class doesn’t do anything. Either delete it and just put all the functionality in the Deck class, or make it an internal class of the Deck.

Since you have most of the functionality implemented in Deck already, I suggest just deleting this class and letting the deck handle everything.

Narrow View

In your main loop, you are doing a bunch of things:

• Tracking the current-player
• Invoking the player or bot turn code
• Implementing the move input mechanics
• Looping to validate input
• Updating the state of the Deck at each turn

To me, this says you need to work on the Deck class (see above), and also create another class or two. You need some code to handle player input mechanics and input validation logic. You need code to handle the simple gameplay mechanics.

I’d suggest creating a Player class, similar to the Bot class. Then you could just invoke the «play_turn()» method on two different objects.

The current-player problem can be solved by just calling players in sequence, as shown above.

The move mechanics and input validation are both part of the player interface. You could actually write different classes with different mechanics, and try them. Or make them play options, if you find that different people like different mechanics.

There should be no reason to update the deck state at the end of the turn. The deck should know enough about game play to update itself (it’s just to track whose turn it is…).

deck_and_cheez.py

First, what’s with the name? Why and_cheez?

class Deck

You have methods in this class that begin with __. Don’t do this.

print_current_deck

Your numbers list should just be a string.

Your loop could use enumerate to eliminate the letter_count variable.

I’d suggest just hard-coding 10 print statements. It would be about the same length and would make the output more clear:

print(f"t 1 2 3 4 5 6 7 8n")

print(f"At{'|'.join(self.deck[0])}tA")
print(f"Bt{'|'.join(self.deck[1])}tB")
...

But really, it isn’t the job of this class to communicate with the user. So instead of printing anything, just join the strings with a newline and return the resulting string:

return "n".join(f"t 1 2 3 4 5 6 7 8n",
        f"At{'|'.join(self.deck[0])}tA",
        ...)

__coordinates

Delete the ‘__’.

Rename this to express what it does: parse_user_coordinates

Use str.index to parse the input. It produces a more compact function:

row = "ABCDEFGH".index(usr_inp[0].upper())
col = "12345678".index(usr_inp[1])

return (row, col)

This will raise an exception if either input character is not matched. I think that’s a good way to return control to the code that’s driving the user interface, but you may want to catch the exception and do something different.

check_position

This is redundant with the method above. You print error messages, but it isn’t the job of this class to communicate with the user. Better, IMO, to return a value or raise an exception.

calculate_possible_moves

I don’t understand this method. You spend a fair amount of code computing two variables that are local to the method. Then you return, without storing, processing, or returning those variables.

The code is not dead — there are two references to this method. But I think it isn’t doing anything.

calculate_possible_move_for_check

This function is described as «calculate». But your return values are boolean. This is not a calculation at all.

You use the color of the checker to determine a direction of movement. This means that the code applies to «men» but not to queens. That in turn suggests to me that you probably want to make the individual pieces members of a class, instead of just character strings.

Finally, the board is fixed in size. You should pre-compute the results of this function and store them in static data. That reduces the function to a lookup.

attack

You can use unpacking to assign multiple variables:

u_x, u_y = *usr_inp

There are three possibilities for a square. You check two of them to make sure the third is true:

if self.deck[u_x][u_y] != ' ' and self.deck[u_x][u_y] != self.color:

Just test for what you want:

if self.deck[u_x][u_y] == self.color:

Checking for ‘ ‘ and for self.color at a target address suggests that your class needs more methods:

if self.deck[u_x - 1][u_y + 1] == ' ':  # Up right

Could become:

target = self.up_right_of(usr_inp)
if self.is_empty(target):

With function self.is_enemy_of(color, location) available as well.

If you write methods for the various directions, you can iterate over the methods, which should shorten this code a lot. Instead of separate sections for x+1, y-1 and x-1,y-1 and …, just make a tuple and iterate over it:

for direction in self.up_right_of, self.up_left_of, self.down_right_of, self.down_left_of:
    target = direction(usr_inp)

move

You behave in different ways based on some attribute of the data. That is a key indicator that you need a class. I suggest making two classes: «men» and «queens», and defining the __str__ method to return the current string values.

This code is too complex:

if self.color == '●' and cur_check in self.queen_list_w or self.color != '●' and cur_check in self.queen_list_b:

You check for (color is black) or (color is not black). That’s always going to be true. Just delete the color discrimination, and check for membership in the queen lists.

But really, just make classes for the pieces and delete all this code.

bot.py

class Bot

There’s a lot of redundant data stored in this class. You’ve got the deck, the checkers, enemy checkers, queens. All of which is also in the deck.

I suggest that you look hard at how you are using the data, and implement methods in the Deck class to provide that data instead.
This would mean data being in just one place, eliminating a source of error.

I’m going to skip further review of this, since I think the suggestion to create objects for the pieces and move the data back into the Deck class will change this class pretty much everywhere.

Welcome to CodeReview! I’ll start by saying thank you for posting a somewhat-complex package of code. At first blush, your code appears to be written in the generally-accepted style and appears well organized and somewhat documented.

Functionality

Before I actually review the code, I’ll point out that I tried to play the game. Here’s my experience:

Your color is: ○
     1 2 3 4 5 6 7 8

A   | |●| |●| |●| |●|   A
B   |●| |●| |●| |●| |   B
C   | |●| |●| |●| |●|   C
D   | | | | | | | | |   D
E   | | | | | | | | |   E
F   |○| |○| |○| |○| |   F
G   | |○| |○| |○| |○|   G
H   |○| |○| |○| |○| |   H

     1 2 3 4 5 6 7 8
Choose you checkerf1
Enter coordinatese1
Choose you checkerf1
Enter coordinatese2
Test Error
Your color is: ●
     1 2 3 4 5 6 7 8

A   | |●| |●| |●| |●|   A
B   |●| |●| |●| |●| |   B
C   | |●| |●| |●| |●|   C
D   | | | | | | | | |   D
E   | |○| | | | | | |   E
F   | | |○| |○| |○| |   F
G   | |○| |○| |○| |○|   G
H   |○| |○| |○| |○| |   H

     1 2 3 4 5 6 7 8

So I have some comments on the actual operation of the game :-).

Playability

First, the game board does not color black/white squares. This makes it harder to play, since the alternating colors help with distinguishing different rows/columns, as well as providing a visual crutch for understanding move possibilities.

Next, the coordinate system is perfectly functional, but not at all intuitive. I’d suggest you consider some alternatives, like labelling the individual checkers with letters A-L instead of circles. Similarly, you might consider enumerating the possible destinations for movement. Either explicitly (redraw the board with 1..4 markers) or implicitly (draw a compass rose with 1..4 on it alongside the board).

Input/Output

The prompt needs to include a space at the end. Otherwise, you get what I got:

Choose you checkerf1

There is no indication of a help system. If someone doesn’t know how to play checkers, or doesn’t remember, how do they get help? Where are the rules of play?

If I enter a bad move, as I did, there’s no rebuff message. Instead, just a new prompt. You should explain that my move is invalid, and either print a rule summary («You must move 1 space diagonally, or jump over an enemy piece diagonally») or print an enumeration of valid moves for the piece.

I don’t know what a Test Error is. But I’m pretty sure that it shouldn’t be appearing during gameplay.

Naming

I have two comments on your file naming. First, instead of game_loop.py you should have named the file checkers.py or main.py (or __main__.py). Because there’s nothing obvious about what game this is, just looking at the file names. I mean, deck_and_cheez.py? What game did you start writing before you switched to checkers?

Second, there just isn’t that much code in these files:

aghast@laptop:~/Code/so/checkers$ wc -l *py
  312 bot.py
  692 deck_and_cheez.py
   58 game_loop.py
 1062 total

Why not just move all the code into checkers.py? This isn’t java, there’s no requirement to have a bunch of little files laying around.

game_loop.py

Structure

Everything in this file should be in a function. Possibly a different function in a different class, but definitely in a function. The standard idiom for python scripts is this:

def main():
    ... all the stuff that isn't in a function ...

if __name__ == '__main__':
    main()

Use this idiom. It makes it possible to do a bunch of things, including writing unit tests, that will benefit you. It doesn’t cost much (just one line, and some tabs), and pays off quickly.

Modularity

What do I learn from this code? (I deleted some vertical space for convenience.)

colors = ['○', '●']
deck = deck_and_cheez.Deck(random.choice(colors))
checker_pos = deck_and_cheez.CurrentChecker()
ALLIES = None
ENEMY = None

while True:
    print(f'Your color is: {deck.color}')
    deck.print_current_deck()

    if ALLIES is None:
        ALLIES = deck.color
    elif ENEMY is None:

Three things. First, is that your deck_and_cheez.Deck class is broken. Second, your deck_and_cheez.CurrentChecker class is even worse! Third, you aren’t taking a broad enough view.

class Deck

A class is supposed to be self-sufficient. If you give it the required arguments at creation time, the returned instance will stand alone.

Let’s look:

• Naming: checkers is a «board game». A better name for Deck would be GameState or Board. In English, a deck is either a floor on a ship, or an alias for a pack of cards. Poker and Pinochle are played with a Deck, while Checkers and Chess are played with a Board.

• From the colors = [...] variable, you don’t have a Deck.COLORS that provides this data to callers. Yet, this is a pretty important part of the Deck so why isn’t it there?

• From the Deck(random.choice(colors)), it seems you don’t need to tell Deck what both colors are (you only pass in one color). Thus, I sense there is a second copy of the colors = [...] over in the Deck class somewhere. (In fact, it’s worse. See below.)

• The code to set ALLIES and ENEMY is determining the value of the random choice you passed in as a parameter. And the two «constants» are only used to determine whose turn it is to play. This could be a part of Deck. It also could be implemented in code, just by writing player_turn() ; computer_turn().

Suggestions

I don’t think you need to «specify» a player color on creation of a new Deck. I think you should just randomly pick one, and make it available to users of the class:

deck = Deck()
player_color, bot_color = deck.player_colors

Once you have the colors allocated inside Deck, you can write a method that cycles the player-turn tracking without having to pass in any parameters:

deck.end_turn()

You should provide a mechanism for determining the end of the game. That could be a method on Deck or an exception raised by the turn handlers. Doing this makes the game loop clearer.

while deck.in_progress:

or

try:
    while True:
        player_turn()
        robot_turn()
except GameOver:
    pass

class CurrentChecker

This class is so low-key that I almost didn’t catch it. Your usage model is that you create an instance of the class:

checker_pos = deck_and_cheez.CurrentChecker()

and then later, during the human-player handling, you update it:

checker = input('Choose you checker').upper()

if deck.check_position(checker):
    if deck.check_checker_pos(checker):
        current_checker = checker_pos.coord(checker)

Problematically, you are calling methods on the deck class before you update the current_checker instance.

Suggestions

This class doesn’t do anything. Either delete it and just put all the functionality in the Deck class, or make it an internal class of the Deck.

Since you have most of the functionality implemented in Deck already, I suggest just deleting this class and letting the deck handle everything.

Narrow View

In your main loop, you are doing a bunch of things:

• Tracking the current-player
• Invoking the player or bot turn code
• Implementing the move input mechanics
• Looping to validate input
• Updating the state of the Deck at each turn

To me, this says you need to work on the Deck class (see above), and also create another class or two. You need some code to handle player input mechanics and input validation logic. You need code to handle the simple gameplay mechanics.

I’d suggest creating a Player class, similar to the Bot class. Then you could just invoke the «play_turn()» method on two different objects.

The current-player problem can be solved by just calling players in sequence, as shown above.

The move mechanics and input validation are both part of the player interface. You could actually write different classes with different mechanics, and try them. Or make them play options, if you find that different people like different mechanics.

There should be no reason to update the deck state at the end of the turn. The deck should know enough about game play to update itself (it’s just to track whose turn it is…).

deck_and_cheez.py

First, what’s with the name? Why and_cheez?

class Deck

You have methods in this class that begin with __. Don’t do this.

print_current_deck

Your numbers list should just be a string.

Your loop could use enumerate to eliminate the letter_count variable.

I’d suggest just hard-coding 10 print statements. It would be about the same length and would make the output more clear:

print(f"t 1 2 3 4 5 6 7 8n")

print(f"At{'|'.join(self.deck[0])}tA")
print(f"Bt{'|'.join(self.deck[1])}tB")
...

But really, it isn’t the job of this class to communicate with the user. So instead of printing anything, just join the strings with a newline and return the resulting string:

return "n".join(f"t 1 2 3 4 5 6 7 8n",
        f"At{'|'.join(self.deck[0])}tA",
        ...)

__coordinates

Delete the ‘__’.

Rename this to express what it does: parse_user_coordinates

Use str.index to parse the input. It produces a more compact function:

row = "ABCDEFGH".index(usr_inp[0].upper())
col = "12345678".index(usr_inp[1])

return (row, col)

This will raise an exception if either input character is not matched. I think that’s a good way to return control to the code that’s driving the user interface, but you may want to catch the exception and do something different.

check_position

This is redundant with the method above. You print error messages, but it isn’t the job of this class to communicate with the user. Better, IMO, to return a value or raise an exception.

calculate_possible_moves

I don’t understand this method. You spend a fair amount of code computing two variables that are local to the method. Then you return, without storing, processing, or returning those variables.

The code is not dead — there are two references to this method. But I think it isn’t doing anything.

calculate_possible_move_for_check

This function is described as «calculate». But your return values are boolean. This is not a calculation at all.

You use the color of the checker to determine a direction of movement. This means that the code applies to «men» but not to queens. That in turn suggests to me that you probably want to make the individual pieces members of a class, instead of just character strings.

Finally, the board is fixed in size. You should pre-compute the results of this function and store them in static data. That reduces the function to a lookup.

attack

You can use unpacking to assign multiple variables:

u_x, u_y = *usr_inp

There are three possibilities for a square. You check two of them to make sure the third is true:

if self.deck[u_x][u_y] != ' ' and self.deck[u_x][u_y] != self.color:

Just test for what you want:

if self.deck[u_x][u_y] == self.color:

Checking for ‘ ‘ and for self.color at a target address suggests that your class needs more methods:

if self.deck[u_x - 1][u_y + 1] == ' ':  # Up right

Could become:

target = self.up_right_of(usr_inp)
if self.is_empty(target):

With function self.is_enemy_of(color, location) available as well.

If you write methods for the various directions, you can iterate over the methods, which should shorten this code a lot. Instead of separate sections for x+1, y-1 and x-1,y-1 and …, just make a tuple and iterate over it:

for direction in self.up_right_of, self.up_left_of, self.down_right_of, self.down_left_of:
    target = direction(usr_inp)

move

You behave in different ways based on some attribute of the data. That is a key indicator that you need a class. I suggest making two classes: «men» and «queens», and defining the __str__ method to return the current string values.

This code is too complex:

if self.color == '●' and cur_check in self.queen_list_w or self.color != '●' and cur_check in self.queen_list_b:

You check for (color is black) or (color is not black). That’s always going to be true. Just delete the color discrimination, and check for membership in the queen lists.

But really, just make classes for the pieces and delete all this code.

bot.py

class Bot

There’s a lot of redundant data stored in this class. You’ve got the deck, the checkers, enemy checkers, queens. All of which is also in the deck.

I suggest that you look hard at how you are using the data, and implement methods in the Deck class to provide that data instead.
This would mean data being in just one place, eliminating a source of error.

I’m going to skip further review of this, since I think the suggestion to create objects for the pieces and move the data back into the Deck class will change this class pretty much everywhere.