Не совсем вопрос, скорее загадка ...

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

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

Поэтому я подумал, что брошу один из своих вопросов аудитории Stack Overflow.

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

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

РЕДАКТИРОВАТЬ: Как указано на одном из плакатов, я не учел временной интервал между ходами. Не стесняйтесь учитывать это как дополнительную опцию :)

EDIT2: Просто для дополнительного пояснения ... Помните, кодировщик / декодер учитывает правила. Единственное, что действительно нужно сохранить, - это выбор игрока - все остальное может быть известно кодировщику / декодеру.

EDIT3: здесь будет сложно выбрать победителя :) Множество отличных ответов!

Обновление: мне так понравилась эта тема, что я написал « Пазлы для программирования», «Шахматные позиции» и «Кодирование Хаффмана» . Если вы прочитаете это, я определил, что единственный способ сохранить полное состояние игры - это сохранить полный список ходов. Читайте почему. Поэтому я использую несколько упрощенный вариант задачи для разметки деталей.

Эта проблема

Это изображение показывает начальную позицию в шахматах. Шахматы происходят на доске 8x8, где каждый игрок начинает с идентичного набора из 16 фигур, состоящего из 8 пешек, 2 ладей, 2 коней, 2 слонов, 1 ферзя и 1 короля, как показано здесь:

Позиции обычно записываются в виде буквы в столбце, за которой следует номер ряда, так что ферзь белых находится на d1. Ходы чаще всего хранятся в алгебраической нотации , которая недвусмысленна и обычно указывает только минимальную необходимую информацию. Рассмотрим это открытие:

1. e4 e5
2. Кf3 Кc6
3. …

что переводится как:

1. Белые перемещают королевскую пешку с е2 на е4 (это единственная фигура, которая может добраться до е4, отсюда «е4»);
2. Черные перемещают королевскую пешку с е7 на е5;
3. Белые перемещают коня (N) на f3;
4. Черные переводят коня на c6.
5. …

Плата выглядит так:

Важное умение любого программиста - уметь правильно и однозначно указать проблему .

Так что отсутствует или неоднозначно? Оказывается, много.

Состояние доски против состояния игры

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

Рокировка

Игра проходила следующим образом:

1. e4 e5
2. Кf3 Кc6
3. Сb5 а6
4. Ba4 Bc5

Плата выглядит следующим образом:

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

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

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

Мимоходом

Еще одно своеобразное правило в шахматах, которым часто пренебрегают, - это En Passant .

Игра прогрессирует.

1. e4 e5
2. Кf3 Кc6
3. Сb5 а6
4. Ba4 Bc5
5. OO b5
6. Сb3 b4
7. c4

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

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

Продвижение

Это ход белых. Если белые перемещают свою пешку с h7 на h8, она может быть переведена на любую другую фигуру (но не на короля). В 99% случаев он повышается до королевы, но иногда это не так, обычно потому, что это может привести к тупику, когда в противном случае вы бы выиграли. Это записывается как:

56. h8 = Q

Это важно в нашей задаче, потому что мы не можем рассчитывать на фиксированное количество частей на каждой стороне. Вполне возможно (но невероятно маловероятно), что одна из сторон получит 9 ферзей, 10 ладей, 10 слонов или 10 коней, если все 8 пешек будут продвинуты.

Тупик

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

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

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

Чья очередь?

Конечно, нам также нужно знать, чья это очередь, и это один бит информации.

Две проблемы

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

Компоновку элементов можно широко обрабатывать одним из двух способов: путем сохранения содержимого каждого квадрата или путем сохранения положения каждого элемента.

Простое содержание

Есть шесть типов фигур (пешка, ладья, конь, слон, ферзь и король). Каждая фигура может быть белой или черной, поэтому квадрат может содержать одну из 12 возможных фигур, или он может быть пустым, поэтому существует 13 вариантов. 13 может храниться в 4-х битах (0-15). Таким образом, самое простое решение - хранить 4 бита для каждого квадрата, умноженные на 64 квадрата или 256 бит информации.

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

Но мы можем добиться большего.

Кодировка Base 13

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

Первое решение рассматривает позицию как 64-значное число с основанием 16, но, как показано, в этой информации присутствует избыточность (3 неиспользованных возможности на «цифру»), поэтому мы можем уменьшить числовое пространство до 64 цифр по основанию 13. Конечно, это не может быть сделано так эффективно, как base 16, но это позволит сэкономить на требованиях к хранилищу (и наша цель - минимизировать пространство для хранения).

В базе 10 число 234 эквивалентно 2 x 10 ² + 3 x 10 ¹ + 4 x 10 ⁰ .

В базе 16 число 0xA50 эквивалентно 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (десятичное).

Таким образом, мы можем закодировать нашу позицию как p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ^0, где p _i представляет содержимое квадрата i .

2 ²⁵⁶ примерно равно 1,16e77. 13 ⁶⁴ примерно равно 1,96e71, что требует 237 бит дискового пространства. Эта экономия всего 7,5% достигается за счет значительного увеличения затрат на манипуляции.

Базовое кодирование переменных

На официальных досках определенные фигуры не могут появляться в определенных клетках. Например, пешки не могут появиться в первом или восьмом разряде, что снижает вероятность этих полей до 11. Это сокращает возможные доски до 11 ¹⁶ x 13 ⁴⁸ = 1,35e70 (приблизительно), что требует 233 бита места для хранения.

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

Алфавиты переменной ширины

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

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

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

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

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

Наконец, в азбуке Морзе есть два вида пауз. Короткая пауза (длина точки) используется для различения точек и тире. Более длинный пробел (длина тире) используется для разделения символов.

Итак, как это применимо к нашей проблеме?

Кодирование Хаффмана

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

В приведенном выше дереве буква 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(), &quot;&quot;);
  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 битам), но по мере прохождения игры требуется увеличение объема памяти.

Штучная позиция

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

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

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

• Король: 6 бит на локацию;
• Имеет пешки: 1 (да), 0 (нет);
• Если да, количество пешек: 3 бита (0-7 + 1 = 1-8);
• Если да, положение каждой пешки кодируется: 45 бит (см. Ниже);
• Количество пешек: 4 бита (0-15);
• Для каждой фигуры: тип (2 бита для ферзя, ладьи, коня, слона) и расположение (6 бит)

Что касается расположения пешек, пешки могут быть только на 48 возможных полях (а не на 64, как остальные). Таким образом, лучше не тратить лишние 16 значений, которые использовались бы при использовании 6 бит на пешку. Итак, если у вас 8 пешек, есть 48 ⁸ возможностей, что равняется 28 179 280 429 056. Для кодирования такого количества значений вам потребуется 45 бит.

Это 105 бит на сторону или 210 бит всего. Однако исходное положение - наихудший случай для этого метода, и он будет значительно улучшаться по мере удаления частей.

Следует отметить, что существует менее 48 возможностей ^8, потому что все пешки не могут быть в одном поле. Первая имеет 48 возможностей, вторая 47 и так далее. 48 x 47 x… x 41 = 1,52e13 = 44-битное хранилище.

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

Комбинированные подходы

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

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

Состояние игры

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

Аннотации

Вам нужно определить одну вещь: просто храните ли вы список ходов или комментируете игру? Шахматные партии часто снабжены аннотациями, например:

17. Сb5 !! Nc4?

Ход белых отмечен двумя восклицательными знаками как блестящий, а ход черных считается ошибкой. См. Раздел « Шахматная пунктуация» .

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

Я предполагаю, что ходов достаточно, поэтому аннотаций не будет.

Алгебраические обозначения

Здесь можно просто сохранить текст хода («e4», «Bxb5» и т. Д.). Включая завершающий байт, вы смотрите около 6 байтов (48 бит) на ход (худший случай). Это не особенно эффективно.

Второе, что нужно попробовать, - это сохранить начальное местоположение (6 бит) и конечное местоположение (6 бит), так что 12 бит на ход. Это значительно лучше.

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

Вывод

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

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

Шахматные позиции взяты как скриншоты из Chess Position Trainer .

Лучше всего хранить шахматные партии в удобном для чтения стандартном формате.

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

Например

[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Если вы хотите сделать его меньше, просто застегните его . Работа выполнена!

Отличная головоломка!

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

И это позволяет кодировать Хаффмана . Собственно, начальная частота фигур на доске почти идеальна для этого: половина полей пустые, половина оставшихся полей - пешки и т. Д.

Учитывая частоту каждого фрагмента, я построил дерево Хаффмана на бумаге , которое я здесь повторять не буду. Результат, где cобозначает цвет (белый = 0, черный = 1):

• 0 для пустых квадратов
• 1c0 за пешку
• 1c100 за ладью
• 1c101 для рыцаря
• 1c110 для слона
• 1c1110 для королевы
• 1c1111 для короля

Для всей платы в исходном состоянии мы имеем

• пустые квадраты: 32 * 1 бит = 32 бита
• пешки: 16 * 3 бита = 48 бит
• ладьи / кони / слоны: 12 * 5 бит = 60 бит
• королевы / короли: 4 * 6 бит = 24 бита

Итого: 164 бита для начального состояния платы. Значительно меньше, чем 235 бит ответа, получившего наибольшее количество голосов. И он будет только уменьшаться по мере прохождения игры (кроме случаев продвижения по службе).

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

• Исключение менее частых частей и сохранение их позиции отдельно. Но это не поможет ... замена короля и ферзя пустым квадратом экономит 5 бит, а это именно те 5 бит, которые вам нужны, чтобы закодировать их положение другим способом.
• «Нет пешек на заднем ряду» можно легко закодировать, используя другую таблицу Хаффмана для задних рядов, но я сомневаюсь, что это сильно помогает. Вы, вероятно, все равно получите то же дерево Хаффмана.
• «Один белый, один черный слон» можно закодировать, введя дополнительные символы, у которых нет cбита, которые затем могут быть выведены из клетки, на которой находится слон. (Превращение пешек в слона нарушает эту схему ...)
• Повторения пустых квадратов можно кодировать по длине серии, вводя дополнительные символы, например, для «2 пустых квадратов в ряду» и «4 пустых квадратов в ряду». Но оценить их частоту не так просто, и если вы ошибетесь, это скорее навредит, чем поможет.

Подход действительно большой таблицы поиска

Позиция - 18 байт.
Предполагаемое количество допустимых позиций - 10 ^43.
Просто перечислите их все, и позиция может быть сохранена всего в 143 битах. Еще 1 бит необходим, чтобы указать, какая сторона будет играть следующей

Перечисление, конечно, непрактично, но это показывает, что требуется как минимум 144 бита.

Ходы - 1 байт
Обычно существует около 30-40 разрешенных ходов для каждой позиции, но их количество может достигать 218. Давайте перечислим все допустимые ходы для каждой позиции. Теперь каждый ход можно закодировать в один байт.

У нас все еще есть много возможностей для специальных ходов, таких как 0xFF, чтобы обозначить отставку.

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

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

Для исходной позиции подход ралу подойдет. Мы могли бы улучшить это с помощью арифметического кодирования и там, если бы у нас был способ взвешивать варианты по вероятности - например, части часто появляются в конфигурациях, защищающих друг друга, а не случайным образом. Труднее найти простой способ применить эти знания. Одна идея: вместо этого вернуться к вышеуказанной кодировке ходов, начиная со стандартной начальной позиции и находя последовательность, которая заканчивается на желаемой доске. (Вы можете попробовать поиск A * с эвристическим расстоянием, равным сумме расстояний между фигурами от их конечных позиций, или что-то в этом роде.) Это дает некоторую неэффективность из-за чрезмерного определения последовательности ходов по сравнению с эффективностью за счет использования преимуществ игры в шахматы. знание.

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

Атака на подзадачу кодирования шагов после того, как начальная позиция была закодирована. Подход состоит в создании «связанного списка» шагов.

Каждый шаг в игре кодируется как пара «старая позиция-> новая позиция». Вы знаете исходную позицию в начале шахматной партии; Просматривая связанный список шагов, вы можете перейти в состояние после X перемещений.

Для кодирования каждого шага необходимо 64 значения для кодирования начальной позиции (6 бит для 64 квадратов на доске - 8x8 квадратов) и 6 бит для конечной позиции. 16 бит на 1 ход каждой стороны.

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

10 x (количество ходов белых + количество ходов черных) бит.

ОБНОВЛЕНИЕ: потенциальные осложнения с повышенными пешками. Необходимо указать, на что повышается пешка - могут потребоваться специальные биты (для экономии места используется серый код, так как повышение пешки происходит крайне редко).

ОБНОВЛЕНИЕ 2: вам не нужно кодировать полные координаты конечной позиции. В большинстве случаев перемещаемая фигура может переместиться не более чем на X позиций. Например, у пешки может быть максимум 3 варианта хода в любой момент. Понимая это максимальное количество ходов для каждого типа фигуры, мы можем сэкономить биты на кодировании «места назначения».

Pawn: 
   - 2 options for movement (e2e3 or e2e4) + 2 options for taking = 4 options to encode
   - 12 options for promotions - 4 promotions (knight, biship, rook, queen) times 3 squares (because you can take a piece on the last row and promote the pawn at the same time)
   - Total of 16 options, 4 bits
Knight: 8 options, 3 bits
Bishop: 4 bits
Rook: 4 bits
King: 3 bits
Queen: 5 bits

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

6 бит для начальной позиции + (переменное количество бит в зависимости от типа перемещаемого объекта).

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

Базовое решение

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

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

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

• Пешка: 4 варианта, 2 бита (1 шаг вперед, 2 шага вперед, по 1 каждой диагонали)
• Ладья: 14 вариантов, 4 бита (максимум 7 в каждом направлении)
• Bishop: 13 вариантов, 4 бита (если у вас 7 на одной диагонали, у вас только 6 на другой)
• Рыцарь: 8 вариантов, 3 бита
• Ферзь: 27 вариантов, 5 бит (ладья + слон)
• Король: 9 вариантов, 4 бита (8 одношаговых ходов плюс вариант рокировки)

Для повышения есть 4 фигуры на выбор (ладья, слон, конь, ферзь), поэтому на этом ходу мы добавляем 2 бита, чтобы указать это. Я думаю, что все остальные правила охватываются автоматически (например, en passant).

Дальнейшие оптимизации

Во-первых, после захвата 8 фрагментов одного цвета вы можете уменьшить кодирование фрагментов до 3 бит, затем 2 бита для 4 фрагментов и так далее.

Основная оптимизация состоит в том, чтобы перечислять только возможные ходы в каждой точке игры. Предположим, мы храним ходы пешки как{00, 01, 10, 11} на 1 шаг вперед, 2 шага вперед, по диагонали влево и вправо по диагонали соответственно. Если некоторые ходы невозможны, мы можем удалить их из кодировки для этого хода.

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

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

В каждой позиции получите количество всех возможных ходов.

следующий ход генерируется как

index_current_move =n % num_of_moves //this is best space efficiency
n=n/num_of_moves

Доказано лучшая эффективность использования пространства для хранения случайно сгенерированной игры и в среднем требуется около 5 бит на ход, так как у вас есть 30-40 возможных ходов. Сборка хранилища просто генерирует n в обратном порядке.

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

РЕДАКТИРОВАТЬ:

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

На каждом ходу добавляем информацию о размере

num_of_moves = get_number_of_possible_moves(postion) ;

в бассейне и это количество не может быть уменьшено

создание информационного пула

n=n*num_of_moves+ index_current_move

дополнительный

Если в конечной позиции доступен только один ход, сохраните как количество ранее сделанных форсированных ходов. Пример: если исходная позиция имеет 1 принудительный ход для каждой стороны (2 хода), и мы хотим сохранить это как игру с одним ходом, сохраните 1 в пуле n.

пример сохранения в информационном пуле

Предположим, что мы знаем стартовые позиции и делаем 3 хода.

Для первого хода доступно 5 ходов, и мы берем индекс хода 4. Во втором ходу доступно 6 ходов, и мы берем индекс позиции 3, а на 3-м ходу для этой стороны доступно 7 ходов, и он решил выбрать индекс хода. 2.

Векторная форма; индекс = [4,3,2] n_moves = [5,6,7]

Мы кодируем эту информацию в обратном порядке, поэтому n = 4 + 5 * (3 + 6 * (2)) = 79 (умножение на 7 не требуется)

Как это разобрать? Сначала у нас есть позиция, и мы выясняем, что доступно 5 ходов. Так

index=79%5=4
n=79/5=15; //no remainder

Мы берем индекс хода 4 и снова исследуем позицию, и с этого момента мы обнаруживаем, что есть 6 возможных ходов.

index=15%6=3
n=15/6=2

И мы берем ход с индексом 3, который приводит нас к позиции с 7 возможными ходами.

index=2%7=2
n=2/7=0

Делаем последний ход с индексом 2 и попадаем в финальную позицию.

Как видите, временная сложность - O (n), а пространственная сложность - O (n). Изменить: временная сложность на самом деле равна O (n ^ 2), потому что число, которое вы умножаете, увеличивается, но не должно быть проблем с сохранением игр до 10000 ходов.

сохранение позиции

Может быть сделано близко к оптимальному.

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

Что мы должны сохранить: 1. позицию каждого мира 2. возможности рокировки 3. возможности проходного пасса 4. сторону, имеющую доступный ход

Предположим, что каждая фигура может стоять где угодно, но не две части в одном месте. Количество способов размещения 8 пешек одного цвета на доске: C (64/8) (биномиальное), что составляет 32 бита, затем 2 ладьи 2R-> C (56/2), 2B -> C (54/2) , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1) и то же самое для другого сайта, но начиная с 8P -> C (48/8) и т. Д. .

Умножив это вместе для обоих сайтов, мы получим номер 4634726695587809641192045982323285670400000, который составляет примерно 142 бита, мы должны добавить 8 для одного возможного прохода (пешка на проходе может быть в одном из 8 мест), 16 (4 бита) для ограничений рокировки и один бит для сайта, у которого есть переезд. В итоге получаем 142 + 3 + 4 + 1 = 150 бит

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

1. обе черные и белые пешки находятся на одной колонне и обращены друг к другу. Каждая пешка обращена к другой пешке, что означает, что белая пешка может находиться не более чем на 6-й горизонтали. Это дает нам 8 * C (6/2) вместо C (64/8) * C (48/8), что уменьшает информацию на 56 бит.

2. возможность рокировки тоже избыточна. Если ладьи не на стартовом месте, рокировка с этой ладьей невозможна. Таким образом, мы можем воображаемо добавить 4 клетки на доске, чтобы получить дополнительную информацию, если рокировка с этой ладьей возможна, и удалить 4 части рокировки. Итак, вместо C (56/2) * C (40/2) * 16 у нас есть C (58/2) * C (42/2), и мы потеряли 3,76 бита (почти все 4 бита)

3. на проходе: когда мы сохраняем одну из 8 возможностей прохода на проходе, мы знаем положение черной пешки и уменьшаем информационную избыточность (если это ход белых и есть 3-я пешка на проходе, это означает, что черная пешка находится на c5, а белая пешка либо c2, c3 или c4), поэтому вместо C (6/2) мы имеем 3 и потеряли 2,3 бита. Мы уменьшаем некоторую избыточность, если мы сохраняем с проходным номером также сторону, с которой можно сделать (3 возможности -> слева, справа, обе), и мы знаем возможность пешки, которая может занять проход. (например, из предыдущего примера en passant с черным на c5, что может быть слева, справа или обоими. если он находится на одном участке, у нас есть 2 * 3 (3 для хранения псиссибилитов и 2 возможных хода для черной пешки на 7-м или 6-м месте ) вместо C (6/2), и мы уменьшаем на 1,3 бита, а если с обеих сторон мы уменьшаем на 4,2 бита. Таким образом, мы можем уменьшить на 2,3 + 1,3 = 3.

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

Подводя итог, нам понадобится 150-56-4-3.6-2 = 85 бит для хранения шахматной позиции, если бы не было сборов.

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

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

Бит на штуку:

• Идентификатор изделия : максимум 4 бита для идентификации 16 деталей на каждой стороне. Можно сделать вывод о белом / черном. Определите порядок деталей. По мере того, как количество частей становится меньше соответствующих степеней двойки, используйте меньшее количество битов для описания оставшихся частей.
• Пешка: 3 возможности на первый ход, поэтому +2 бита (вперед на одно или два квадрата, на проходе). Последующие ходы не позволяют двигаться вперед на два, поэтому +1 бит достаточно. О повышении можно судить в процессе декодирования, отмечая, когда пешка достигла последней позиции. Если известно, что пешка продвинута, декодер будет ожидать еще 2 бита, указывающих, в какую из 4 основных фигур она была переведена.
• Bishop: +1 бит для используемой диагонали, до +4 бит для расстояния по диагонали (16 вариантов). Декодер может определить максимально возможное расстояние, на которое кусок может перемещаться по этой диагонали, поэтому, если это более короткая диагональ, используйте меньше битов.
• Конь: 8 возможных ходов, +3 бита
• Ладья: +1 бит для горизонтали / вертикали, +4 бита для расстояния по линии.
• Король: 8 возможных ходов, +3 бита. Обозначьте рокировку с «невозможным» ходом - поскольку рокировка возможна только, когда король находится на первом ряду, закодируйте этот ход с инструкцией переместить короля «назад», то есть за пределы доски.
• Королева: 8 возможных направлений, + 3 бита. До +4 бит для расстояния по линии / диагонали (меньше, если диагональ короче, как в случае слона)

Предполагая, что все фигуры на доске, это биты на ход: Пешка - 6 бит на первом ходу, 5 на последующем. 7 в случае повышения. Слон: 9 бит (максимум), Конь: 7, Ладья: 9, Король: 7, Ферзь: 11 (максимум).

Проблема в том, чтобы дать кодировку, наиболее эффективную для типичных шахматных игр, или ту, которая имеет кратчайшую кодировку наихудшего случая?

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

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

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

2. 1 бит, чтобы сказать, кто делает первый ход

3. Кодовые ходы согласно предложению Хенка: обычно 10 бит на пару ходов белых / черных, хотя некоторые ходы занимают 0 бит, когда у игрока нет альтернативных ходов.

Это предполагает 490 бит для кодирования типичной игры с 30 ходами и будет достаточно эффективным представлением для типичных игр.

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

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

32 штуки * 7 бит = 224 бит

РЕДАКТИРОВАТЬ: как указал Кадриан ... у нас также есть случай «превращение пешки в ферзя». Я предлагаю добавить дополнительные биты в конце, чтобы указать, какая пешка была повышена.

Таким образом, для каждой пешки, которая была повышена, мы следуем за 224 битами с 5 битами, которые указывают индекс пешки, которая была повышена, и 11111, если это конец списка.

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

РЕДАКТИРОВАТЬ: как указывает лохматая лягушка, нам нужен еще один бит в конце, чтобы указать, чья это очередь; ^)

Я бы использовал кодировку длины прогона. Некоторые изделия уникальны (или существуют только дважды), поэтому я могу опустить длину после них. Как и Cletus, мне нужно 13 уникальных состояний, поэтому я могу использовать полубайт (4 бита) для кодирования фрагмента. Тогда исходная плата будет выглядеть так:

White Rook, W. Knight, W. Bishop, W. Queen, W. King, W. Bishop, W. Knight, W. Rook,
W. Pawn, 8,
Empty, 16, Empty, 16
B. Pawn, 8,
B. Rook, B. Knight, B. Bishop, B. Queen, B. King, B. Bishop, B. Knight, B. Rook

что оставляет мне 8 + 2 + 4 + 2 + 8 полубайтов = 24 полубайта = 96 бит. Я не могу закодировать 16 с помощью полубайта, но поскольку «Пусто, 0» не имеет смысла, я могу рассматривать «0» как «16».

Если доска пуста, но для одной пешки в верхнем левом углу, я получаю «Пешка, 1, Пусто, 16, Пусто, 16, Пусто 16, Пусто, 15» = 10 полубайтов = 40 бит.

Худший случай - это когда между каждой фигурой остается пустой квадрат. Но для кодирования фрагмента мне нужно всего 13 значений из 16, так что, возможно, я могу использовать другое, чтобы сказать «Empty1». Затем мне нужно 64 полубайта == 128 бит.

Для движений мне нужно 3 бита для фигуры (цвет задается тем, что белый всегда идет первым) плюс 5 бит (0..63) для новой позиции = один байт на движение. В большинстве случаев мне не нужна старая позиция, так как только одна фигура будет в пределах досягаемости. В нечетном случае я должен использовать единственный неиспользованный код (мне просто нужно 7 кодов для кодирования фрагмента), а затем 5 бит для старой и 5 бит для новой позиции.

Это позволяет мне кодировать рокировку в 13 укусов (я могу переместить короля в сторону ладьи, чего достаточно, чтобы сказать то, что я собираюсь сказать).

[РЕДАКТИРОВАТЬ] Если вы разрешаете интеллектуальный кодировщик, то мне нужно 0 бит для начальной настройки (потому что это не нужно каким-либо образом кодировать: это статично) плюс один байт на ход.

[EDIT2] Что оставляет преобразование пешки. Если пешка достигает последнего ряда, я могу переместить ее на место, чтобы сказать «трансформируется», а затем добавить 3 бита к фигуре, которой она заменяется (вам не нужно использовать ферзя; вы можете заменить пешку чем угодно но король).

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

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

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

Недостатки: вам нужно воспроизвести всю игру, чтобы добраться до текущего состояния и сгенерировать подмножество, как при просмотре связанного списка.

Имеется 64 возможных положения платы, поэтому вам нужно 6 бит на позицию. Есть 32 начальных фрагмента, так что у нас всего 192 бита, где каждые 6 битов указывают положение данного фрагмента. Мы можем заранее определить порядок появления частей, поэтому нам не нужно говорить, что есть что.

Что делать, если фигура не на доске? Что ж, мы можем разместить фигуру на том же месте, что и другая, чтобы указать, что она находится вне доски, иначе это было бы незаконно. Но мы также не знаем, будет ли первая фигура на доске или нет. Итак, мы добавляем 5 битов, указывающих, какая часть является первой (32 варианта = 5 битов для представления первой части). Затем мы можем использовать это место для последующих фигур, выходящих за пределы доски. Это приводит нас к 197 битам. На доске должна быть хотя бы одна фигура, чтобы она работала.

Затем нам нужен один бит, чья очередь - доводит до 198 бит .

А как насчет пешечного продвижения? Мы можем сделать это плохо, добавив 3 бита на пешку, добавив 42 бита. Но затем мы можем заметить, что в большинстве случаев пешки не продвигаются.

Итак, для каждой пешки на доске бит «0» указывает, что она не продвинута. Если пешки нет на доске, то бит нам совсем не нужен. Затем мы можем использовать битовые строки переменной длины, для которых он получил повышение. Чаще всего это королева, поэтому «10» может означать КОРОЛЕВУ. Тогда «110» означает ладью, «1110» - слона, «1111» - коня.

Начальное состояние займет 198 + 16 = 214 бит , так как все 16 пешек на доске и не прокручены. Эндшпиль с двумя продвинутыми пешками-ферзями может занять что-то вроде 198 + 4 + 4, что означает 4 живые и непродвиженные пешки и 2 ферзевые пешки, всего 206 бит . Выглядит довольно надежно!

===

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

Поэтому разработайте схему кодирования Хаффмана для каждой отдельной позиции. Пешки, скорее всего, возьмут в среднем только 3-4 бита вместо 6. Королю также следует взять несколько битов.

Также в этой схеме укажите «занято» как возможную позицию. Это также может очень надежно справиться с рокировкой - каждая ладья и король будут иметь дополнительное состояние «исходная позиция, ход». Так же можно закодировать в пешках на проходе - «исходная позиция, можно на проходе».

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

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

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

Каждой части будет назначен идентификатор. Поскольку существует 32 разных элемента, мне понадобится всего 5 бит для идентификатора части. Идентификаторы фигур не меняются от игры к игре. То же самое и с квадратными идентификаторами, для которых мне понадобится 6 бит.

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

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

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

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

Подводя итог в графическом виде:

<Game> := <Pieces huffman tree> <squares huffman tree> <promotion table> <initial position> (<moves> | <1 bit for next move - see Added 2 below>)

<Pieces huffman tree> := <pieces entry 1> <pieces entry 2> ... <pieces entry N>
<pieces entry> := "0" | "1" <5 bits with piece ID>

<squares huffman tree> := <squares entry 1> <squares entry 2> ... <squares entry N>
<Squares entry> := "0" | "1" <6 bits with square ID>

<promotion table> := <4 bits with count of promotions> <promotion 1> <promotion 2> ... <promotion N>
<promotion> := <huffman-encoded piece ID> <2 bits with what it becomes>

<initial position> := <position entry 1> <position entry 2> ... <position entry N>
<moves> := <position entry 1> <position entry 2> ... <position entry N>
<position entry> := <huffman-encoded piece ID> <huffman-encoded squre ID> (<2 bits specifying the upgrade - optional>)

Добавлено: это еще можно оптимизировать. У каждой фигуры есть только несколько допустимых ходов. Вместо простого кодирования целевого квадрата можно было бы присвоить идентификаторы, отсчитываемые от 0, для возможных ходов каждой фигуры. Одни и те же идентификаторы будут повторно использоваться для каждой фигуры, поэтому в общей сложности будет не более 21 разных идентификаторов (у ферзя может быть не более 21 различных возможных вариантов хода). Поместите это в таблицу Хаффмана вместо полей.

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

В качестве альтернативы они могут быть размещены с использованием несжатых 6-битных квадратных идентификаторов.

Я не знаю, приведет ли это к общему уменьшению размера. Наверное, но стоит немного поэкспериментировать.

Добавлено 2: Еще один особый случай. Если в игровом состоянии НЕТ ходов, важно различать, кто ходит следующим. Добавьте еще один бит в конце для этого. :)

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

Так что давайте назовем начальное состояние платы одиночным битом «0».

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

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

Используя эту систему, игра из 100 полуходов может быть закодирована примерно в 500 битах. Однако было бы разумно использовать вступительную книгу. Предположим, он содержит миллион последовательностей. Пусть тогда начальный 0 означает начало со стандартной платы, а 1, за которой следует 20-битное число, указывает начало этой последовательности открытия. Игры с несколько обычным началом можно сократить, скажем, на 20 полуходов или 100 бит.

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

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

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

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

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

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

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

for each row
    for each column
        add to list ( get list of possible moves( current piece, players turn) )

'получить список возможных ходов' будет делать что-то вроде:

if current piece is not null 
    if current piece color is the same as the players turn
        switch( current piece type )
            king - return list of possible king moves( current piece )
            queen - return list of possible queen moves( current piece )
            rook - return list of possible rook moves( current piece )
            etc.

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

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

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

На доске 64 квадрата, 64 = 2 ^ 6. Если мы сохраним только начальную и конечную клетки каждого хода, который займет 12 бит (продвижение будет рассмотрено позже). Обратите внимание, что эта схема уже охватывает перемещение игрока, выделение, взятие фигуры, рокировку и т. Д .; поскольку они могут быть построены путем простого воспроизведения списка ходов.

для продвижения мы можем сохранить отдельный массив векторов, в котором говорилось бы «на ходу N продвигаться к Фигуре XYZ». мы можем сохранить вектор (int, byte).

Заманчиво также оптимизировать вектор (To, From), поскольку многие из этих векторов (To, From) недопустимы в шахматах. например. не будет хода с e1 на d8 и т.д. Но я не смог придумать никакой схемы. Любые дальнейшие идеи приветствуются.

Я долго думал об этом (+ - 2 часа). И нет однозначных ответов.

Предполагая:

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

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

-C Округление 25 байтов (64b + 32 * 4b + 5b = 325b)

= 64 бита (что-то / ничего) + 32 * 4 бита [1 бит = цвет {черный / лоза} + 3 бит = тип фигуры {Король, Ферзь, Слон, kNight, Ладья, Пешка, MovedPawn} NB: Перемещенная пешка ... например, если это была последняя пешка в предыдущем ходу, указывающая на то, что «проходным путём» возможно. ] + 5 бит для фактического состояния (кто ход, на проходе, возможность ладьи или нет с каждой стороны)

Все идет нормально. Вероятно, можно улучшить, но тогда следует учитывать переменную длину и продвижение !?

Теперь следующие правила применимы, только когда игрок подает заявку на ничью, ЭТО НЕ АВТОМАТИЧЕСКИ! Так что считайте, что эти 90 ходов без взятия или пешки возможны, если ни один игрок не требует ничьей! Это означает, что все ходы должны быть записаны ... и доступны.

-D повторение позиции ... например, состояние доски, как упомянуто выше (см. C) или нет ... (см. Ниже о правилах ФИДЕ) -E Это оставляет сложную проблему разрешения 50 ходов без взятия или хода пешки, нужна фишка ... Впрочем.

Так как же ты с этим справишься? ... На самом деле выхода нет. Потому что ни один из игроков может захотеть нарисовать или понять, что это произошло. Теперь, в случае E, счетчика может хватить ... но вот трюк и даже читая правила ФИДЕ (http://www.fide.com/component/handbook/?id=124&view=article), я не могу найти ответ ... а как насчет потери способности ладить. Это повторение? Я думаю, что нет, но тогда это размытая тема, которую не рассматривают, не проясняют.

Итак, вот два правила, которые являются сложными или неопределенными даже для попытки кодирования ... Ура.

Таким образом, единственный способ по-настоящему кодировать игру - это записывать все с самого начала ... что затем конфликтует (или нет?) С вопросом «состояние доски».

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

Возможное улучшение стартовой позиции в решении Якоби

Никакая допустимая позиция не может содержать более 16 фигур каждого цвета. Количество способов разместить до 16 черных и 16 белых фигур на 64 квадратах составляет примерно 3.63e27. Log2 (3,63e27) = 91,55. Это означает, что вы можете кодировать положение и цвет всех частей в 92 бита. Это меньше, чем 64 бита для позиции + до 32 бит для цвета, которые требуются для решения Якоби. В худшем случае можно сэкономить 4 бита за счет значительной сложности кодирования.

С другой стороны, он увеличивает размер позиций, в которых отсутствует 5 или более фигур. Эти позиции представляют только <4% всех позиций, но они, вероятно, являются большинством случаев, когда вы хотите записать начальную позицию, отличную от начальной позиции.

Это приводит к полному решению

1. Закодируйте положение и цвет фигур, как описано выше. 92 бит .
2. Чтобы указать тип каждой фигуры, используйте код Хаффмана: пешка: «0», ладья: «100», конь: «101», слон: «110», ферзь: «1110», король: «1111». Для этого требуется (16 * 1 + 12 * 3 + 4 * 4) = 68 бит для полного набора частей. Положение всей платы может быть закодировано максимумом 92 + 68 = 160 бит .
3. Должно быть добавлено дополнительное состояние игры: поворот: 1 бит, возможна рокировка: 4 бита, возможна «на проходе»: до 4 бит (1 бит указывает на случай, а 3 бита - на какой). Начальная позиция кодируется = 160 + 9 = 169 бит
4. Для списка ходов перечислите все возможные ходы для данной позиции и сохраните позицию хода в списке. В список ходов включены все частные случаи (рокировка, проходной ход и сдача). Используйте столько битов, сколько необходимо для сохранения самой высокой позиции. В среднем он не должен превышать 7 бит на ход (в среднем 16 возможных фигур и 8 допустимых ходов на фигуру). В некоторых случаях, когда ход принудительный, требуется всего 1 бит (ход или отставка).

На доске 32 фигуры. У каждой фигуры есть позиция (одна на 64 квадрата). Итак, вам нужно всего 32 натуральных числа.

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

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

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

Как упоминали некоторые другие, вы можете для каждой из 32 фигур сохранить, на каком квадрате они находятся, и если они на доске или нет, это дает 32 * (log2 (64) + 1) = 224 бита.

Однако слоны могут занимать только черные или белые квадраты, поэтому для них вам понадобится только log2 (32) бита для позиции, что дает 28 * 7 + 4 * 6 = 220 бит.

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

Доска имеет 64 квадрата и может быть представлена ​​64 битами, показывающими, пустая клетка или нет. Нам нужна только часть информации, если в квадрате есть кусок. Поскольку игрок + кусок занимает 4 бита (как показано ранее), мы можем получить текущее состояние в 64 + 4 * 32 = 192 бита. Добавьте текущий поворот, и у вас будет 193 бита.

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

Пешка: Вперед, первый ход два вперед, на проходе * 2, продвижение = 7 бит. Вы можете объединить первый ход вперед и повышение в один бит, так как они не могут происходить из одной и той же позиции, поэтому у вас есть 6. Ладья: 7 вертикальных квадратов, 7 горизонтальных квадратов = 14 бит Конь: 8 квадратов = 8 битов Слон: 2 диагонали * 7 = 14 бит Королева: 7 по вертикали, 7 по горизонтали, 7 по диагонали, 7 по диагонали = 28 бит Король: 8 окружающих квадратов

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

Так как у нас 16 пешек, 4 ладьи / коня / слона и 2 ферзя / короля, это 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = еще 312 бит, в результате чего всего до 505 бит.

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

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

EDIT1: забыл о рокировке и продвижении пешки на любую фигуру. Это может довести общее количество с явными позициями до 557 ходов (еще 3 бита для пешек, 2 для королей).

Каждая фигура может быть представлена ​​4 битами (пешка королю, 6 типов), черное / белое = 12 значений.

Каждый квадрат на доске может быть представлен 6 битами (координата x, координата y).

Начальные позиции требуют максимум 320 бит (32 штуки, 4 + 6 бит)

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

Рокировка потребует дополнительных 16 бит, так как это двойной ход.

Ферзевые пешки могут быть представлены одним из 4 запасных значений из 4 бит.

Без подробных математических вычислений это начинает экономить место после первого хода по сравнению с хранением 32 * 7 бит (предопределенный массив частей) или 64 * 4 бит (предопределенное назначение квадратов).

После 10 ходов с обеих сторон максимальное необходимое пространство составляет 640 бит.

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

Начальные позиции = макс. 384 бита (32 штуки, 6 + 6 бит) Каждый ход = 12 бит (в позицию, идентификатор фигуры)

Затем после 10 ходов с каждой стороны максимальное необходимое пространство составляет 624 бит.

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

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

Ходы не нуждаются в записи состояния; декодер может отслеживать состояние, а также то, какие ходы допустимы в любой момент. Все ходы, которые необходимо записать, - это то, какая из различных правовых альтернатив была выбрана. Поскольку игроки чередуются, ход не требует записи цвета игрока. Поскольку игрок может перемещать только свои цветные фишки, первый выбор - это то, какую фишку игрок переместит (позже я вернусь к альтернативе, которая использует другой выбор). Максимум 16 штук, это требует максимум 4 бита. Когда игрок теряет фишки, количество вариантов уменьшается. Кроме того, конкретное состояние игры может ограничивать выбор фигур. Если король не может двигаться, не поставив себя под шах, количество вариантов уменьшается на один. Если король под шахом, любая фигура, которая не может вывести короля из-под шаха, не является жизнеспособным выбором.

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

Мы кодируем назначение большинства фигур, нумеруя квадраты вдоль линий в следующем порядке: W, NW, N, NE (черная сторона - N). Линия начинается в квадрате, наиболее удаленном в заданном направлении, в котором разрешено движение, и продолжается в направлении. Для свободного короля список ходов: W, E, NW, SE, N, S, NE, SW. Для коня мы начинаем с 2W1N и продолжаем движение по часовой стрелке; пункт назначения 0 - первый действительный пункт назначения в этом порядке.

• Пешки: у неподвижной пешки есть 2 варианта назначения, поэтому требуется 1 бит. Если пешка может захватить другую, как обычно, так и на проходе (что может определить декодер, поскольку он отслеживает состояние), у нее также есть 2 или 3 варианта хода. Помимо этого, у пешки может быть только 1 выбор, не требующий битов. Когда пешка находится в 7- ^м ряду, мы также делаем выбор в пользу превращения. Поскольку пешки обычно превращаются в ферзей, а за ними следуют кони, мы кодируем варианты так:
  • королева: 0
  • рыцарь: 10
  • епископ: 110
  • ладья: 111
• Епископ: не более 13 пунктов назначения в {d, e} {4,5} для 4 бит.
• Ладья: не более 14 направлений, 4 бита.
• Рыцари: максимум 8 направлений, 3 бита.
• Короли: когда возможна рокировка, король возвращается к S и не может двигаться вниз; это дает в общей сложности 7 направлений. В остальное время у короля есть максимум 8 ходов, что дает максимум 3 бита.
• Ферзь: такой же, как для слона или ладьи, всего 27 вариантов, что составляет 5 бит.

Поскольку количество вариантов не всегда является степенью двойки, вышеизложенное по-прежнему теряет биты. Предположим, что количество вариантов равно C, а конкретный вариант пронумерован c , а n = ceil (lg ( C )) (количество битов, необходимых для кодирования выбора). Мы используем эти потерянные в противном случае значения, исследуя первый бит следующего выбора. Если 0, ничего не делать. Если это 1 и c + C <2 ⁿ , добавьте C к c . Декодирование числа меняет это на противоположное: если полученное c > = C , вычтите C и установите первый бит для следующего числа равным 1. Если c<2ⁿ - C , затем установите первый бит следующего числа в 0. Если 2 ⁿ - C <= c < C , ничего не делать. Назовите эту схему «насыщением».

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

При насыщении кодирование захвата, вероятно, не дает преимущества. Мы могли бы учесть оба варианта, указав в исходном состоянии, которые используются. Если насыщенность не используется, кодировка игры может также использовать неиспользуемые числа выбора ( C <= c <2 ⁿ ) для изменения параметров во время игры. Каждый раз, когда C представляет собой степень двойки, мы не можем изменить параметры.

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

Таким образом, мы получаем 164 бита для фигур, 4 бита для информации о рокировке (при условии, что мы сохраняем фрагмент игры, в противном случае он может быть восстановлен), 3 бита для полной информации о праве на участие - просто сохраните столбец, в котором произошел ход ( Если на проходе невозможно сохранить столбец там, где это невозможно - такие столбцы должны существовать) и 1 для того, кто должен двигаться.

Движения обычно занимают 5 или 6 бит, но могут варьироваться от 1 до 8.

Еще один ярлык - если кодирование начинается с 12 1 бит (недопустимая ситуация - даже у фрагмента не будет двух королей с одной стороны), вы прерываете декодирование, стираете доску и настраиваете новую игру. Следующий бит будет битом хода.

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

• 2 епископа, по 13 направлений каждый = 26
• 2 ладьи по 14 ударов = 28
• 2 рыцаря по 8 направлений = 16
• королева, 27 направлений
• король, 8 направлений

Все 8 лап могут стать ферзями в худшем (с точки зрения перечисления) случае, что делает наибольшее количество возможных пунктов назначения 9 * 27 + 26 + 28 + 16 + 8 = 321. Таким образом, все пункты назначения для любого хода могут быть пронумерованы 9-битным числом.

Максимальное количество ходов у обеих сторон - 100 (если не ошибаюсь, не шахматист). Таким образом, любая игра может быть записана в 900 битах. Плюс начальная позиция, каждая часть может быть записана с использованием 6-битных чисел, что в сумме составляет 32 * 6 = 192 бит. Плюс один бит для записи «кто ходит первым». Таким образом, любая игра может быть записана с использованием 900 + 192 + 1 = 1093 бит.

Сохранение состояния платы

Самый простой способ, о котором я подумал, - это сначала иметь массив из 8 * 8 бит, представляющий расположение каждой фигуры (так 1, если есть шахматная фигура, и 0, если ее нет). Поскольку это фиксированная длина, нам не нужен терминатор.

Затем представьте каждую шахматную фигуру в порядке ее расположения. Используя 4 бита на кусок, это занимает 32 * 4 бита (всего 128). Что действительно очень расточительно.

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

• Пешка: 2
• Ладья: 4
• Рыцарь: 4
• Епископ: 4
• Король: 5
• Королева: 5

Учитывая итоги:

2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100

Что превосходит использование набора бит фиксированного размера на 28 бит.

Итак, лучший метод, который я нашел, - сохранить его в массиве 8 ² + 100 бит

8*8 + 100 = 164

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

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

Итак, для каждого нормального хода у нас есть необходимые 1 + 5 = 6биты. (1 бит, 5 бит на штуку)

После того, как номер фигуры был декодирован, мы узнаем тип фигуры, и каждая фигура должна представлять свой ход наиболее эффективным образом. Например (если мои правила шахмат на высоте) у пешки всего 4 возможных хода (левый, правый, один вперед, два вперед).
Итак, чтобы представить ход пешки, нам нужно 6 + 2 = 8 бит. (6 бит для заголовка начального хода, 2 бита для какого хода)

Перемещение ферзя было бы более сложным, так как было бы лучше иметь направление (8 возможных направлений, то есть 3 бита) и в общей сложности 8 возможных квадратов для перемещения для каждого направления (то есть еще 3 бита). Итак, чтобы представить движение ферзя, потребуются 6 + 3 + 3 = 12биты.

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

Результирующий формат
Итак, формат файла будет выглядеть примерно так

[64 бита] Расположение начальных фрагментов
[100 бит макс.] Начальные фрагменты [1 бит] Ход игрока
[n бит] Движения

Где Move - это
[1 бит] Тип перемещения (специальный или нормальный)
[n бит] Детали перемещения

Если Движение является обычным ходом, Детализация Движения выглядит примерно как
[5 бит] кусок
[n бит] конкретный ход (обычно в диапазоне от 2 до 6 бит)

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

В базовом случае начальной доски и последующих ходов учитывайте следующее.

Используйте шахматную программу, чтобы определить вероятности всех возможных ходов. Например, 40% для e2-e4, 20% для d2-d4 и так далее. Если некоторые ходы допустимы, но не учитываются этой программой, дайте им низкую вероятность. Используйте арифметическое кодирование, чтобы сохранить, какой выбор был сделан, каким будет число от 0 до 0,4 для первого хода, от 0,4 до 0,6 для второго и т. Д.

Проделайте то же самое с другой стороной. Например, если есть 50% вероятность того, что e7-e5 в качестве ответа на e2-e4, то закодированное число будет между 0 и 0,2. Повторяйте, пока игра не закончится. Результат - потенциально очень маленький диапазон. Найдите двоичную дробь с наименьшим основанием, попадающим в этот диапазон. Это арифметическое кодирование.

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

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

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

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

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