Шахматы на php и javascript: Признание ничьи и отмена хода

Что сегодня сделаем?

Сегодня сделаем две вещи: признание ничьи по правилам 50-и ходов и троекратного повтора позиции, и возможность для человека "переходить", "взять ход назад", отменить ход на любое количество ходов назад. Отмена хода - это как раз не по правилам шахмат, но мы тут и не собирались соблюдать строгие турнирные правила. В реальной игре, в семье например, обычно дают переходить более слабому игроку. Да и без отмены хода играть с компьютером будет менее интересно.

Для признания ничьи будем пользоваться двумя правилами: "правило пятидесяти ходов" и правило "троекратного повторения позиции".

Правило пятидесяти ходов

В шахматах есть правило - если в течении 50 ходов не было ни одного хода пешкой, и не было ни одного взятия фигуры, то игрок, чья сейчас очередь хода может "потребовать ничью". Есть правило 75-и ходов, расширяющее правило 50-и ходов: если в течении 75 ходов не было ни одного хода пешкой, и не было ни одного взятия фигуры, то партия автоматически признаётся сыгранной в ничью.

Т.е. после 50-и ходов "без экшена" игрок может потребовать ничью, а может и не потребовать, и играть дальше, если конечно его соперник сам не потребует ничью. А вот после 75-и ходов "без экшена" партия автоматически заканчивается вничью, независимо от желания оппонентов продолжать.

Что в реальном шахматном турнире значит "потребовать ничью"? Игрок, которых хочет воспользоваться этим правилом, записывает свой ход, но не делает его. Зовёт судью, заявляет что хочет воспользоваться этим правилом, и показывает записанный (не сделанный) ход. Судья проверяет что после этого хода требования правила "50-и ходов" выполняются, и объявляет ничью.

У нас нет судьи. Мы сделаем так: компьютер сам "требует" и объявляет ничью, сразу после своего хода, после которого выполняются правила 50-и ходов. Можно считать что он "потребовал ничью", а потом показал свой ход.

Для реализации правила 50-и ходов у нас есть счётчик полуходов "без экшена" - поле non_action_semimove_counter в классе состояния игры GameState

Правило троекратного повторения позиции

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

Как мы реализуем это правило? Будем считать число повторов каждой позиции! Заведём ассоциативнй массив, где ключами будут выступать "хеши позиции", а значениями - количество повторов. И будем обновлять этот счётчик после каждого хода.

Ничья по правилам 50-и ходов и троекратного повтора позиции

Сначала напишем метод для определения состояния ничьи (состояния при котором можно требовать ничью). Это будет метод класса ChessGame, и называться будет checkDraw:

engine/chess_game.php// Проверка ничьи по правилам 50-и ходов и троекратного повторения позиции
protected function checkDraw() {
    if ($this->game_state->non_action_semimove_counter >= 100) {
        $this->game_state->text_state = 'Ничья. Компьютер потребовал ничью по правилу 50 ходов';
        return true;
    }
    if ($this->game_state->positionRepeatCount() >= 3) {
        $this->game_state->text_state = 'Ничья. Компьютер потребовал ничью по правилу троекратного повторения позиции';
        return true;
    }
    return false;
}

Всё просто. Для правила пятидесяти ходов просто проверем счётчик полуходов "без экшена". А вот для правила троекратного повторения позиции использовали несуществующий пока метод positionRepeatCount класса GameState. Идём в этот класс и добавляем метод:

engine/game_state.phppublic function positionRepeatCount() {
    $key = $this->getCurrentPositionHash();
    if (!isset($this->position_hashes[$key])) {
        return 0;
    }
    return $this->position_hashes[$key];
}

Да, мы опять пользуемся тем, чего пока нет. Счётчик повторов мы храним в поле класса position_hashes. Добавим сразу его к списку полей:

engine/game_state.phpprivate $position_hashes = array();

А ключ, по которому будем хранить счётчик повторов, мы вычисляем методом getCurrentPositionHash. Добавляем этот метод:

engine/game_state.phpprivate function getCurrentPositionHash() {
    return $this->getPositionHash($this->getHash());
}

Опять пользуемся ненаписанным пока методом - getPositionHash. В него передаём хеш - ассоциативный массив с данными о текущей позиции. Забегая чуть вперёд - нам понадобится вычислять хеш не только для текущей позиции, поэтому я вынес вычисление в отдельный метод, который принимает на вход хеш - ассоциативный массив с данными о позиции. Добавляем метод:

engine/game_state.phpprivate function getPositionHash(array $state) {
    $state_for_rule_repeat = $this->getStateForRuleRepeat($state);
    return md5(json_encode($state_for_rule_repeat, JSON_UNESCAPED_UNICODE));
}

Что здесь происходит? С помощью опять-таки ненаписанного пока метода мы получаем ассоциативный массив с информацией о позиции, потом кодируем его в json-строку, берём md5-хеш от этой строки, и возвращаем. У нас уже есть метод, отдающий ассоциативный массив с информацией о позиции - getHash. Зачем нам понадобился ещё один метод? Делов в том, что в метод getHash возвращает кроме прочего и номер хода, и информацию о предыдущем ходе, и текстовое состояние игры, и количество полуходов "без экшена". Эти данные не нужны для определения повтора позиции, они даже будут мешать, с этими данными "позиция" никогда не повторится, хотя бы потому, что хранит номер хода.

В начало класса добавляем константу - массив с именами полей, которые нам нужны для правила повтора позиции:

engine/game_state.phpconst FIELDS_FOR_RULE_REPEAT = array(
    'position', 'current_player_color', 'enable_castling_white_king', 'enable_castling_black_king', 'enable_castling_white_queen', 'enable_castling_black_queen',
    'crossed_field'
);

И добавляем метод, отдающий информацию для правила повтора позиции:

engine/game_state.phpprivate function getStateForRuleRepeat($state_hash) {
    $result = array();
    foreach (self::FIELDS_FOR_RULE_REPEAT as $key) {
        $result[$key] = $state_hash[$key];
    }
    return $result;
}

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

engine/game_state.phppublic function savePositionHash() {
    // сохраняем счётчик хешей позиций
    $key = $this->getCurrentPositionHash();
    if (!isset($this->position_hashes[$key])) {
        $this->position_hashes[$key] = 1;
    } else {
        $this->position_hashes[$key] += 1;
    }
}

Теперь идём в класс ChessGame, и добавляем вызов только что написанного метода в два места. Первое - в конце метода createNewGame, перед строкой $this->saveGame();:

$this->game_state->savePositionHash();
$this->saveGame();

Второе место - в конце метода makeMove, тоже перед строкой $this->saveGame();.

Вызываем метод проверки ничьи

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

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

engine/chess_game.phppublic function generateAvailableMoves() {
    if ($this->checkDraw()) {
        return array();
    }
    …

И второе место - в методе makeComputerMove, сразу после вызова метода makeMove:

engine/chess_game.php$this->makeMove($move['from'], $move['to'], false);
    if ($this->checkDraw()) {
        $this->saveGame();
        return;
    }

    // проверим - есть ли ходы у человека?
    …

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

Отмена хода

Начнём с интерфейсной части. В файле index.html сразу после доски, т.е. после блока div с классом board, добавим блок с "кнопкой" - ссылкой "Ход назад":

index.html<div class="nav"><a href="#" class="move_back hidden">&lt;&lt;Ход назад</a></div>

Здесь мы указали для нашей "кнопки" два класса. move_back - для визуального оформения в виде кнопки. И hidden - для сокрытия кнопки. Она не должна быть видна, когда ход назад нельзя взять - когда его ещё нету, когда человек ещё не сделал ни одного хода.

Напишем сразу css-правила:

chess.css.nav {
    width: 480px;
    margin-top: 10px;
    text-align: center;
}
.move_back {
    display: inline-block;
    text-decoration: none;
    padding: 4px;
    border: 1px solid #06f;
    border-radius: 6px;
    background-color: #edb;
    color: #000;
    font-weight: bold;
}
.hidden {
    display: none;
}

Отмена хода на стороне javascript в браузере

Открываем наш javascript-файлик chess.js. После строки

let available_moves = {}; // допустимые ходы текущего игрока - человека

добавим переменные, в которых будем хранить номер хода, и dom-элемент - кнопку "назад":

chess.jslet move_number = 0;
let button_move_back = null;

Кнопка есть. Хотя пока и невидимая. Добавим обработчик клика по кнопке. В самом конце функции initButtons добавляем:

chess.js// кнопка "Ход назад"
button_move_back = document.querySelector('.nav a.move_back');
button_move_back.addEventListener('click', (event) => moveBack(event));

Кстати, в начале функции, лучше дописать let перед button = document.querySelector…, забыл сразу это сделать. Пусть будет локальной переменной.

Ну и пишем сам обработчик клика. Добавляем функцию:

chess.jsfunction moveBack(event) {
    event.preventDefault();
    if (move_number < 2) {
        return;
    }

    if (selected_cell_index !== null) {
        deselectCell(selected_cell_index); // снимаем выделение с текущей выделенной клетки
    }
    createRequest({
        method: 'POST',
        url: 'move_back.php',
        callback: function(response) {
            setGameState(response);
        }
    });
}

В строках 3 - 5 проверяем - возможен ли вообще ход назад. Хотя мы и будем поддерживать невидимость кнопки "Ход назад" в нужных ситуациях, но дополнительная проверка не помешает. И самая суть функции - в строках 10 - 16. Шлём запрос на новый обработчик - move_back.php, и как обычно получаем в ответе состояние игры, и передаём его в функцию setGameState для "отрисовки".

В самой функции setGameState перед строкой // обновляем позицию добавляем:

chess.js// обновляем номер хода
move_number = game_state.move_number;
if (move_number > 1) {
    button_move_back.classList.remove('hidden');
} else {
    button_move_back.classList.add('hidden');
}

Бекенд-обработка хода назад

Переместимся на сторону php. На стороне javascript мы уже вызываем новый скрипт для "хода назад". Создадим новый файл в веб-корне - move_back.php:

move_back.php<?php
require_once('engine/chess_game.php');
$game = new ChessGame();
$game->loadGame();
$game->moveBack();
$data = $game->getClientJsonGameState();
header('Content-Type: application/json');
echo json_encode($data, JSON_UNESCAPED_UNICODE);

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

Добавляем историю состояний игры

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

Причём можно сохранять состояния только для ситуаций, когда текущий ход - у человека. Зачем нам отматывать на ход компьютера? Чтобы он переходил? Нам не это надо было.

Итак, идём в класс GameState, после поля position_hashes добавляем поле, в котором будем хранить историю состояний игры:

engine/game_state.phpprivate $state_history = array();

Чтобы сохранять и историю состояний в хранилище, нам надо изменить формат сохраняемых данных. Идём в метод serializeState (мы всё ещё находимся в классе GameState). В этом методе была всего одна строка:

engine/game_state.phppublic function serializeState() {
    return json_encode($this->getHash(), JSON_UNESCAPED_UNICODE);
}

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

engine/game_state.phppublic function serializeState() {
    $data = array(
        'state' => $this->getHash(),
        'history' => $this->state_history
    );
    return json_encode($data, JSON_UNESCAPED_UNICODE);
}

Ну и раз мы изменили сериализатор, то надо изменить и "рассериализатор". Метод unserializeState теперь будет выглядеть так:

engine/game_state.phppublic function unserializeState(string $serialized_state) {
    try {
        $data = json_decode($serialized_state, true);
        $this->state_history = $data['history'];
        foreach (self::PROPERTY_NAMES as $key) {
            $this->$key = $data['state'][$key];
        }
        $this->recalculatePositionHashes();
        return true;
    } catch(Exception $e) {
        return false;
    }
}

В строке 8 вызываем ненаписанный пока метод recalculatePositionHashes. Он будет пересчитывать счётчик хешей позиций - тот самый счётчик, который нужен для обнаружения повтора позиций.

Мы изменили формат хранения данных об игре, поэтому давайте изменим и имя ключа сессии, по которому будем хранить эти данные. Иначе получим ошибку когда новым кодом попытаемся прочитать уже записанные когда-то данные в старом формате. Вообще это не страшно, можем просто создать новую игру. Но если изменим имя ключа сессии, то и старый код, и новый код без проблем будут работать одновременно. Итак, открываем файл engine/session_storage.php, и меняем значение константы с именем ключа:

engine/session_storage.phpconst SESSION_KEY = 'chess_game_state_v3';

Пишем в историю состояний

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

engine/game_state.phppublic function isHumanMove() {
    return $this->current_player_color == $this->human_color;
}

Добавим сам метод для записи позиции в историю:

engine/game_state.phppublic function savePositionHistory() {
    $this->state_history[] = $this->getHash();
}

И теперь добавим запись в историю в нужные места. Первое место - сразу после создания игры, если сейчас ход человека. Это в классе ChessGame, в самом конце метода createNewGame, перед строкой $this->saveGame(); (После недавно добавленной строки $this->game_state->savePositionHash();) Пишем там:

engine/chess_game.phpif ($this->isHumanMove()) {
    $this->game_state->savePositionHistory();
}

Второе место - после совершения хода. Это тоже в том-же классе, в конце метода makeMove, тоже перед строкой $this->saveGame();, и тоже после недавно добавленного вызова $this->game_state->savePositionHash(); Вставляем точно такой-же код:

engine/chess_game.phpif ($this->isHumanMove()) {
    $this->game_state->savePositionHistory();
}

Третье место не очевидно. Я сам понял что там нужно сохранение только при дебаге проблем, обнаруженных при тестировании. Это место - в том-же классе ChessGame, в методе makeComputerMove. Когда обнаруживается, что у компьютера нет допустимых ходов, мы определяем что сейчас у нас или мат или пат, и записываем состояние игры. Что будет если мы захотим взять ход назад? К примеру мы случайно поставили пат, но мы хотим выиграть и решили взять ход назад. Мы ещё не написали сам метод, делающий ход назад, так что я немного забегу вперёд. При взятии хода назад, мы удаляем последнюю запись из истории состояний, и "воспроизводим" ту запись, которая была перед той, извлечённой. Но если мы после пата (или мата) не записали состояние в историю, то из этой истории удалится запись, соответствующая пред-предыдущему ходу. Т.е. мы возьмём два хода назад, а не один. Так что после того как компьютеру объявили мат или пат, тоже надо записать состояние игры в историю состояний.

И тут ещё один подвох, связанный с "не очень хорошей архитектурой" нашего приложения. После пата мы записали состояние игры в историю. … Что будет, если обновить страницу в этом состоянии? Игра загрузится из хранилища, в состоянии записано что сейчас ход компьютера, он попытается найти возможные ходы, у него не получится - у нас же мат или пат. И состояние игры запишется в историю. Опять. Ещё раз обновим страницу, и опять история пополнится тем-же самым состоянием.

Если мы пять раз перезагрузим страницу, в истории будем шесть записей с одинаковой позицией. И нам понадобится 6 раз назад кликнуть по кнопке "Ход назад", чтобы отображаемая позиция стала той, что была перед матом или патом. Это нам совсем не нужно. Чтобы не переписывать из за этого систему сохранения состояний, я добавил такие "грабли": записываю позицию в историю, только если количество повторов этой позиции равно нулю.

Итак, идём в метод makeComputerMove, почти в начале метода, в ветке if (!$move) { …, перед строкой $this->saveGame(); пишем:

engine/chess_game.phpif ($this->game_state->positionRepeatCount() === 0) {
    $this->game_state->savePositionHistory();
}

Отменяем ход

Перейдём к самой реализации метода отмены хода. В класс ChessGame добавляем метод:

engine/chess_game.phppublic function moveBack() {
    $this->game_state->moveBack();
    $this->saveGame();
}

Т.е. вызываем одноименный метод на объекте состояния игры, и сохраняем игру. Идём теперь в класс GameState и добавляем метод:

engine/game_state.phppublic function moveBack() {
    array_pop($this->state_history);
    $hash = end($this->state_history);
    foreach (self::PROPERTY_NAMES as $key) {
        $this->$key = $hash[$key];
    }
    $this->recalculatePositionHashes();
}

В строке 2 извлекаем последний элемент из истории состояний. В строке 3 берём текущее последнее состояние, которое осталось после извлечения на предыдущей строке. Это и есть то состояние, тот "предыдущий ход" к которому хотим вернуться. В цикле (строки 4 - 6) устанавливаем свойства в объекте состояния.

В строке 7 вызываем метод пересчёта счётчика хешей позиций. Помните мы уже вызывали этот метод в методе рассериалиации? Напишем уже наконец этот метод пересчёта счётчика хешей. Добавляем:

engine/game_state.phpprivate function recalculatePositionHashes() {
    $this->position_hashes = array();
    foreach ($this->state_history as $state) {
        $hash = $this->getPositionHash($state);
        if (!isset($this->position_hashes[$hash])) {
            $this->position_hashes[$hash] = 1;
        } else {
            $this->position_hashes[$hash] += 1;
        }
    }
}

Пишем пустой массив в счётчик (в свойство position_hashes класса). Проходим в цикле по истории состояний, для каждого состояния вычисляем хеш методом getPositionHash и обновляем счётчик.

Исправляем баг с превращением пешки

При подготовке статьи нашёл баг, связанный с превращением пешки компьютера. Баг появляется когда компьютер играет за белых, и его пешка попадает на поле A8. Это последняя горизонталь для белой пешки, но тем не мене, она остаётся пешкой. Не превращается ни в какую фигуру.

Причина оказалось в классе пешки (файл engine/figures/pawn.php), в методе makeMove. Оказывается срабатывало условие в этой строке:

} elseif ($crossed_field == $to_cell_index) { 

В переменной $crossed_field - NULL, это "пересечённое поле". А в переменной $to_cell_index записан 0. Поле A8 имеет нулевой индекс! А для нестрогого сравнения NULL "равен" нулю. Для исправления бага достаточно добавить один символ "=", чтобы сравнение стало строгим:

} elseif ($crossed_field === $to_cell_index) { 

Итоги

Мы научились "отматывать" игру на любое количество ходов назад, делать "переход" хода. Сделали признание ничьи по правилу "50-и ходов" и по правилу троекратного повтора позиции.

исходные коды проекта на github.

Демо №13 игры

В следующей части научим компьютер выбирать не случайные ходы, а более-менее "осмысленные"