Обновление: Мне очень понравилась эта тема, которую я написал Программирование головоломок, шахматных позиций и кодирования Хаффмана . Если вы прочитали это, я решил, что only способ сохранить полное состояние игры - это сохранить полный список ходов. Продолжайте читать, почему. Поэтому я использую слегка упрощенную версию задачи для разметки.
Проблема
Это изображение иллюстрирует начальную шахматную позицию. Шахматы происходят на доске 8х8, где каждый игрок начинает с одинакового набора из 16 фигур, состоящих из 8 пешек, 2 ладей, 2 коней, 2 слонов, 1 королевы и 1 короля, как показано здесь:
Позиции обычно записываются в виде буквы для столбца, за которой следует номер строки, поэтому ферзь белых находится на уровне d1. Ходы чаще всего хранятся в алгебраической записи , которая однозначна и, как правило, определяет только минимальную необходимую информацию. Рассмотрим это открытие:
- e4 e5
- Nf3 Nc6
- ...
, что означает:
- Белые перемещают пешку короля с e2 на e4 (это единственная фигура, которая может добраться до e4, следовательно, «e4»);
- черные перемещают пешку короля с е7 на е5;
- Белые перемещают коня (N) на f3;
- Черные перемещают коня в с6.
- ...
Доска выглядит так:
Важной возможностью для любого программиста является умение правильно и однозначно указать проблему .
Так чего не хватает или неоднозначно? Как оказалось много.
Состояние Совета против Game State
Первое, что вам нужно определить, - сохраняете ли вы состояние игры или расположение фигур на доске. Простое кодирование положения фигур - это одно, но проблема говорит о «всех последующих юридических шагах». Проблема также ничего не говорит о знании движений до этого момента. Это на самом деле проблема, как я объясню.
Рокировка
Игра прошла следующим образом:
- e4 e5
- Nf3 Nc6
- Bb5 a6
- Ba4 Bc5
Плата выглядит следующим образом:
Белый имеет опцию рокировка . Частью требований для этого является то, что король и соответствующая ладья никогда не могли двигаться, поэтому необходимо будет сохранить положение короля или любой ладьи с каждой стороны. Очевидно, что если они не находятся на своих начальных позициях, они переместились, в противном случае это необходимо указать.
Существует несколько стратегий, которые можно использовать для решения этой проблемы.
Во-первых, мы могли бы хранить дополнительные 6 битов информации (по 1 для каждой ладьи и короля), чтобы указать, перемещалась ли эта фигура. Мы могли бы упростить это, сохранив немного для одного из этих шести квадратов, если в нем окажется нужный фрагмент. В качестве альтернативы мы можем рассматривать каждую неподвижную фигуру как другой тип фигуры, поэтому вместо 6 типов фигуры на каждой стороне (пешка, ладья, рыцарь, слон, королева и король) их 8 (с добавлением неподвижной ладьи и короля).
En Passant
Другое своеобразное и часто игнорируемое правило в шахматах: En Passant .
Игра прогрессирует.
- e4 e5
- Nf3 Nc6
- Bb5 a6
- Ba4 Bc5
- O-O b5
- Bb3, b4
- c4
У пешки черных на b4 теперь есть возможность переместить пешку на b4 на с3, взяв белую пешку на с4. Это происходит только при первой возможности, то есть если черные переходят к варианту, то теперь они не могут сделать следующий ход. Таким образом, мы должны хранить это.
Если мы знаем предыдущий месяцМы можем определенно ответить, если En Passant возможен. В качестве альтернативы мы можем хранить информацию о том, перемещалась ли каждая пешка на ее 4-м уровне с двойным движением вперед. Или мы можем посмотреть на каждую возможную позицию En Passant на доске и иметь флаг, чтобы указать, возможно это или нет.
Promotion
Это ход белых. Если белые перемещают свою пешку на h7 на h8, ее можно повысить на любую другую фигуру (но не на короля). В 99% случаев он повышается до королевы, но иногда нет, обычно потому, что это может привести к тупику, если в противном случае вы выиграете. Это написано как:
Это важно в нашей задаче, потому что это означает, что мы не можем рассчитывать на то, что на каждой стороне будет определенное количество фигур. Вполне возможно (но невероятно маловероятно), что одна сторона получит 9 ферзей, 10 ладей, 10 слонов или 10 рыцарей, если все 8 пешек получат повышение.
Пат
Когда вы находитесь в позиции, из которой вы не можете выиграть, ваша лучшая тактика - попытаться получить пат . Наиболее вероятный вариант - это когда вы не можете сделать законный ход (обычно потому, что любой ход ставит вашего короля под контроль). В этом случае вы можете претендовать на ничью. Этот легко обслуживать.
Второй вариант - тройное повторение . Если одна и та же позиция на доске происходит трижды в игре (или будет происходить в третий раз на следующем ходу), можно получить ничью. Позиции не должны располагаться в каком-либо определенном порядке (то есть нет необходимости в той же последовательности ходов, повторенных три раза). Это сильно усложняет проблему, потому что вы должны помнить каждую предыдущую позицию доски. Если это требование проблемы, единственным возможным решением проблемы является сохранение каждого предыдущего хода.
Наконец, есть правило пятьдесят ходов . Игрок может претендовать на ничью, если пешка не сдвинута, и ни одной фигуры не было взято в течение предыдущих пятидесяти последовательных ходов, поэтому нам нужно было бы сохранить количество ходов с тех пор, как пешка была перемещена или взята фигура (последний из двух. Это требует 6 бит (0-63).
Чей это поворот?
Конечно, нам также нужно знать, чья это очередь, и это один бит информации.
Две проблемы
Из-за патовой ситуации единственный реальный или разумный способ сохранить состояние игры - сохранить все ходы, которые привели к этой позиции. Я займусь этой проблемой. Задача о состоянии доски будет упрощена до этого: сохранит текущую позицию всех фигур на доске, игнорируя условия рокировки, прохождения, патовые состояния и чей ход .
Компоновка фигуры может широко рассматриваться одним из двух способов: путем сохранения содержимого каждого квадрата или путем сохранения положения каждой фигуры.
Простое содержание
Существует шесть типов фигур (пешка, ладья, рыцарь, слон, королева и король). Каждая часть может быть Белой или Черной, поэтому квадрат может содержать одну из 12 возможных частей, или он может быть пустым, так что есть 13 возможностей. 13 может храниться в 4 битах (0-15). Поэтому самое простое решение - хранить 4 бита для каждого квадрата, умноженного на 64 квадрата или 256 битов информации.
Преимущество этого метода в том, что невероятно легко и быстро. Это можно даже расширить, добавив еще 3 возможности без увеличения требований к хранилищу: пешка, которая переместилась на 2 пробела в последний ход, король, который не сдвинулся, и ладья, которая не сдвинулась, что обслужит много ранее упомянутых вопросов.
Но мы можем сделать лучше.
База 13 Кодировка
Часто полезно думать о позиции доски как об очень большом числе. Это часто делается в информатике. Например, проблема остановки рассматривает компьютерную программу (по праву) как большое число.
ПервыйВ решении рассматривается позиция как 64-значное число из 16 основных чисел, но, как было продемонстрировано, в этой информации есть избыточность (то есть 3 неиспользуемые возможности на «цифру»), поэтому мы можем сократить пространство до 64 базовых 13 цифр. Конечно, это не может быть сделано так же эффективно, как базовая 16, но это сэкономит на требованиях к хранилищу (и наша цель - минимизировать объем хранилища).
В базе 10 число 234 эквивалентно 2 x 10 2 + 3 x 10 1 + 4 x 10 0 .
В базе 16 число 0xA50 эквивалентно 10 x 16 2 + 5 x 16 1 + 0 x 16 0 = 2640 (десятичное число).
Таким образом, мы можем закодировать нашу позицию как p 0 x 13 63 + p 1 x 13 62 + ... + p 63 x 13 0 , где p i представляет содержимое квадрата i .
2 256 равно приблизительно 1,16e77. 13 64 равно приблизительно 1,96e71, что требует 237 бит дискового пространства. Эта экономия всего 7,5% достигается за счет значительно повышенных затрат на манипуляции.
Переменная базовая кодировка
В юридических блоках определенные фигуры не могут появляться в определенных квадратах. Например, пешки не могут появляться в первом или восьмом разрядах, уменьшая возможности для этих квадратов до 11. Это уменьшает возможные доски до 11 16 x 13 48 = 1.35e70 ( приблизительно), требуется 233 бита дискового пространства.
На самом деле кодирование и декодирование таких значений в десятичную (или двоичную) и из нее немного сложнее, но это можно сделать надежно и оставить читателю в качестве упражнения.
Алфавиты переменной ширины
Оба предыдущих метода можно описать как буквенное кодирование фиксированной ширины . Каждый из 11, 13 или 16 членов алфавита заменяется другим значением. Каждый «символ» имеет одинаковую ширину, но эффективность можно улучшить, если учесть, что каждый символ не одинаково вероятен.
Рассмотрим Азбука Морзе (на фото выше). Символы в сообщении закодированы как последовательность штрихов и точек. Эти тире и точки передаются по радио (обычно) с паузой между ними, чтобы разграничить их.
Обратите внимание, что буква E ( самая распространенная буква на английском языке ) представляет собой одну точку, кратчайшую возможную последовательность, тогда как буква Z (наименее частая) - две черты и два звуковых сигнала.
Такая схема может значительно уменьшить размер ожидаемого сообщения *1254*, но за счет увеличения размера случайной последовательности символов.
Следует отметить, что азбука Морзе имеет еще одну встроенную функцию: штрихи имеют длину до трех точек, поэтому приведенный выше код создается с учетом этого, чтобы минимизировать использование штрихов. Поскольку 1 и 0 (наши строительные блоки) не имеют этой проблемы, нам не нужно копировать эту функцию.
Наконец, есть два вида отдыха в азбуке Морзе. Короткий отдых (длина точки) используется для различения точек и тире. Длинный пробел (длина тире) используется для разделения символов.
Так, как это относится к нашей проблеме?
Код Хаффмана
Существует алгоритм для работы с кодами переменной длины, который называется Кодирование Хаффмана . Кодирование Хаффмана создает подстановку кода переменной длины, обычно использует ожидаемую частоту символов для назначения более коротких значений более распространенным символам.
В приведенном выше дереве буква E кодируется как 000 (или слева-слева-слева), а S равно 1011. Должно быть ясно, что эта схема кодирования однозначна .
Это важное отличие от азбуки Морзе. В коде Морзе есть символьный разделитель, поэтому в противном случае он может выполнять неоднозначную подстановку (например, 4 точки могут быть H или 2 Is), но у нас есть только 1 и 0, поэтому мы выбираем однозначную подстановку.
Ниже приведенпростая реализация:
private static class Node {
private final Node left;
private final Node right;
private final String label;
private final int weight;
private Node(String label, int weight) {
this.left = null;
this.right = null;
this.label = label;
this.weight = weight;
}
public Node(Node left, Node right) {
this.left = left;
this.right = right;
label = "";
weight = left.weight + right.weight;
}
public boolean isLeaf() { return left == null && right == null; }
public Node getLeft() { return left; }
public Node getRight() { return right; }
public String getLabel() { return label; }
public int getWeight() { return weight; }
}
со статическими данными:
private final static List<string> COLOURS;
private final static Map<string, integer> WEIGHTS;
static {
List<string> list = new ArrayList<string>();
list.add("White");
list.add("Black");
COLOURS = Collections.unmodifiableList(list);
Map<string, integer> map = new HashMap<string, integer>();
for (String colour : COLOURS) {
map.put(colour + " " + "King", 1);
map.put(colour + " " + "Queen";, 1);
map.put(colour + " " + "Rook", 2);
map.put(colour + " " + "Knight", 2);
map.put(colour + " " + "Bishop";, 2);
map.put(colour + " " + "Pawn", 8);
}
map.put("Empty", 32);
WEIGHTS = Collections.unmodifiableMap(map);
}
и
private static class WeightComparator implements Comparator<node> {
@Override
public int compare(Node o1, Node o2) {
if (o1.getWeight() == o2.getWeight()) {
return 0;
} else {
return o1.getWeight() < o2.getWeight() ? -1 : 1;
}
}
}
private static class PathComparator implements Comparator<string> {
@Override
public int compare(String o1, String o2) {
if (o1 == null) {
return o2 == null ? 0 : -1;
} else if (o2 == null) {
return 1;
} else {
int length1 = o1.length();
int length2 = o2.length();
if (length1 == length2) {
return o1.compareTo(o2);
} else {
return length1 < length2 ? -1 : 1;
}
}
}
}
public static void main(String args[]) {
PriorityQueue<node> queue = new PriorityQueue<node>(WEIGHTS.size(),
new WeightComparator());
for (Map.Entry<string, integer> entry : WEIGHTS.entrySet()) {
queue.add(new Node(entry.getKey(), entry.getValue()));
}
while (queue.size() > 1) {
Node first = queue.poll();
Node second = queue.poll();
queue.add(new Node(first, second));
}
Map<string, node> nodes = new TreeMap<string, node>(new PathComparator());
addLeaves(nodes, queue.peek(), "");
for (Map.Entry<string, node> entry : nodes.entrySet()) {
System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
}
}
public static void addLeaves(Map<string, node> nodes, Node node, String prefix) {
if (node != null) {
addLeaves(nodes, node.getLeft(), prefix + "0");
addLeaves(nodes, node.getRight(), prefix + "1");
if (node.isLeaf()) {
nodes.put(prefix, node);
}
}
}
Один из возможных выходных данных:
White Black
Empty 0
Pawn 110 100
Rook 11111 11110
Knight 10110 10101
Bishop 10100 11100
Queen 111010 111011
King 101110 101111
Для начальной позиции это равно 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 бита.
Разница состояний
Другой возможный подход - объединить самый первый подход с кодированием Хаффмана. Это основано на предположении, что большинство ожидаемых шахматных досок (а не сгенерированных случайным образом) с большей вероятностью, по крайней мере частично, напоминают исходную позицию.
Итак, вы делаете XOR для текущей 256-битной позиции платы с 256-битной начальной позицией и затем кодируете ее (используя кодирование Хаффмана или, скажем, некоторый метод кодирование длины выполнения ). Очевидно, что это будет очень эффективно для начала (64 0, вероятно, соответствуют 64 битам), но увеличение памяти требуется по ходу игры.
Piece Position
Как уже упоминалось, еще один способ решения этой проблемы - вместо этого сохранить положение каждой фигуры, которую имеет игрок. Это особенно хорошо работает с позициями эндшпиля, где большинство квадратов будут пустыми (но в подходе кодирования Хаффмана пустые квадраты в любом случае используют только 1 бит).
У каждой стороны будет король и 0-15 других фигур. Из-за продвижения точный состав этих фигур может варьироваться настолько, что вы не сможете предположить, что числа, основанные на начальных позициях, являются максимумами.
Логический способ разделить это - сохранить позицию, состоящую из двух сторон (белой и черной). Каждая сторона имеет:
- Король: 6 бит для локации;
- Имеет пешки: 1 (да), 0 (нет);
- Если да, количество пешек: 3 бита (0-7 + 1 = 1-8);
- Если да, местоположение каждой пешки кодируется: 45 бит (см. Ниже);
- Количество не пешек: 4 бита (0-15);
- Для каждой фигуры: тип (2 бита для ферзя, ладьи, рыцаря, слона) и местоположение (6 бит)
Что касается расположения пешек, то пешки могут быть только на 48 возможных клетках (не 64, как остальные). Таким образом, лучше не тратить лишние 16 значений, которые использовались бы при использовании 6 битов на пешку. Таким образом, если у вас есть 8 пешек, то есть 48 8 возможностей, что равно 28 179 280 429 056. Вам нужно 45 бит для кодирования такого количества значений.
Это 105 бит на сторону или всего 210 бит. Стартовая позиция - наихудший вариант для этого метода, и он будет значительно лучше, когда вы снимаете фигуры.
Следует отметить, что существует менее 48 8 возможностей, поскольку все пешки не могут быть в одном квадрате. У первого есть 48 возможностей, у второго 47 и так далее. 48 x 47 x… x 41 = 1.52e13 = 44-битное хранилище.
Вы можете улучшить это, убрав квадраты, которые заняты другими фигурами (включая другую сторону), чтобы вы могли сначала разместить белых непешек, затем черных непешек, затем белых пешек и наконец черных пешек , На начальной позиции это снижает требования к памяти до 44 бит для белых и 42 бит для черных.
Комбинированные подходы
Другая возможная оптимизация заключается в том, что каждый из этих подходов имеет свои сильные и слабые стороны. Можно, скажем, выбрать 4 лучших, а затем закодировать селектор схемы в первых двух битах, а затем хранилище, специфичное для схемы.
С такими маленькими накладными расходами это, безусловно, будет лучшим подходом.
Состояние игры
Я возвращаюсь к проблеме хранения игры , а не позиции . Из-за тройного повторения мы должны сохранить список ходов, которые произошли к этой точке.
Аннотации
Одна вещь, которую вы должны определить: вы просто храните список ходов или комментируете игру? Шахматные игры часто аннотируются, например:
- Bb5 !! Nc4
WhЭтот ход отмечен двумя восклицательными знаками как блестящий, тогда как ход черных считается ошибкой. См. Шахматная пунктуация .
Кроме того, вам также может понадобиться сохранить свободный текст, как описано в движениях.
Я предполагаю, что ходов достаточно, поэтому аннотаций не будет.
алгебраическая запись
Мы могли бы просто сохранить здесь текст движения («e4», «Bxb5» и т. Д.). Включая завершающий байт, вы смотрите примерно 6 байтов (48 бит) за ход (наихудший случай). Это не особенно эффективно.
Второе, что нужно попробовать, это сохранить начальное местоположение (6 бит) и конечное местоположение (6 бит), поэтому 12 бит на ход. Это значительно лучше.
В качестве альтернативы мы можем определить все законные шаги от текущей позиции предсказуемым и детерминированным способом и состоянием, которое мы выбрали. Затем возвращается к кодированию переменной базы, указанному выше. У белых и черных по 20 возможных ходов каждый на первый ход, больше на второй и т. Д.
Заключение
Нет абсолютно правильного ответа на этот вопрос. Есть много возможных подходов, из которых вышеперечисленные являются лишь некоторыми.
Что мне нравится в этой и других подобных проблемах, так это то, что она требует способностей, важных для любого программиста, таких как учет схемы использования, точное определение требований и размышление над угловыми случаями.
Шахматные позиции, взятые как скриншоты из Шахматный Позиционный Тренер .