Ответ 1

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

Эта проблема

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

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

1. е4 е5
2. Nf3 Nc6
3. ...

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

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

Доска выглядит так:

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

Так чего не хватает или неоднозначно? Как оказалось много.

Board State vs Game State

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

Рокировка

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

1. е4 е5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5

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

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

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

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

Мимоходом

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

Игра прогрессировала.

1. е4 е5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5
5. OO b5
6. Bb3 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 цифр. Конечно, это не может быть сделано так же эффективно, как база 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 (наименее часто встречающаяся) - две черты и два звуковых сигнала.

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

Следует отметить, что азбука Морзе имеет еще одну встроенную функцию: длина штрихов составляет три точки, поэтому приведенный выше код создается с учетом этого, чтобы свести к минимуму использование штрихов. Так как 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(), &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 ⁸ возможностей, потому что пешки не может все быть в той же площади Первые имеют 48 возможностей, второй 47 и так далее. 48 x 47 x… x 41 = 1.52e13 = 44-битное хранилище.

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

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

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

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

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

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

Аннотации

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

17. Bb5 !! Nc4?

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

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

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

Алгебраическая запись

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

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

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

Заключение

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

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

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

Ответ 2

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

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

например.

[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

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

Ответ 3

Великая головоломка!

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

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

Учитывая частоту каждой части, я построил на бумаге дерево Хаффмана, что я не буду здесь повторять. Результат, где 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 пустых квадрата в строке". Но оценить их часто не так просто, и если вы ошибетесь, это будет больно, а не поможет.

Ответ 4

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

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

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

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

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

Ответ 5

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

Каждый шаг в игре кодируется как пара "старая позиция → новая позиция". Вы знаете начальную позицию в начале игры в шахматы; пройдя связанный список шагов, вы можете перейти к состоянию после того, как 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 бит для начальной позиции + (переменное число бит в зависимости от типа перемещаемой вещи).

Ответ 6

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

следующее перемещение создается как

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

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

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

EDIT:

Точка сохранения движений - хранить только индекс перемещения. Вместо того, чтобы хранить 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), потому что число, которое вы умножаете, увеличивается, но не должно быть проблем с сохранением игр до 10 000 ходов.

экономия позиции

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

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

Что нам нужно сохранить: 1. Положение каждого мира 2. Возможности рокинга 3. возможности en-passant 4. сторона, которая имеет доступ к движению

Предположим, что каждый кусок может стоять где угодно, но не 2 части в одном месте. На борту может быть установлено 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 для одного возможного en-passant (en-passant pawn может находиться в одном из 8 мест), 16 (4 бит) для ограничения для рокинга и один бит для сайта, который перемещается. В итоге мы получаем 142 + 3 + 4 + 1 = 150 битц

Но теперь отпустите на охоту за избыточность на доске с 32 штуками и не возьмите.

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

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

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

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

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 9

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

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

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

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

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

EDIT: Как указывает мохнатая лягушка, нам нужно еще немного в конце указать, чей это ход: ^)

Ответ 10

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

Биты за штуку:

• Piece-ID: Максимум 4 бит для идентификации 16 штук на сторону. Белый/черный может быть выведен. Определите порядок на кусках. Поскольку количество штук падает ниже соответствующих степеней двух, используйте меньшее количество бит, чтобы описать оставшиеся части.
• Пароля: 3 варианта на первом ходу, поэтому +2 бит (вперед на один или два квадрата, en passant.) Последующие перемещения не позволяют двигаться вперед на два, поэтому +1 бит достаточно. Продвижение может быть выведено в процессе декодирования, отметив, когда пешка достигла последнего ранга. Если известно, что пешка продвигается, декодер ожидает еще 2 бита, указывающих, какая из 4 основных частей, на которую он был повышен,.
• Бишоп: +1 бит для используемой диагонали, до +4 бит для расстояния по диагонали (16 возможностей). Декодер может вывести максимально возможное расстояние, которое кусок может перемещаться по этой диагонали, поэтому, если он имеет более короткую диагональ, используйте меньше бит.
• Рыцарь: 8 возможных ходов, +3 бит
• Грач: +1 бит для горизонтальной/вертикальной, +4 бит для расстояния вдоль линии.
• Король: 8 возможных ходов, +3 бит. Укажите рокировку с невозможным движением - так как рокировка возможна только тогда, когда король находится на первом ранге, закодируйте этот ход с инструкцией по перемещению короля "назад", то есть вне доски.
• Королева: 8 возможных направлений, + 3 бит. До +4 бит для расстояния по линии/диагонали (меньше, если диагональ короче, как в случае с епископом)

Предполагая, что все части находятся на доске, это бит за ход: Пешка - 6 бит при первом ходу, 5 в дальнейшем. 7 в случае повышения. Епископ: 9 бит (макс.), Рыцарь: 7, ладья: 9, король: 7, королева: 11 (макс.).

Ответ 11

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

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

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

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

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

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

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

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

Ответ 12

Я бы использовал кодировку длины пробега. Некоторые части уникальны (или существуют только два раза), поэтому я могу опустить длину после них. Как 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 nibbles = 24 nibbles = 96 бит. Я не могу кодировать 16 с полубайтом, но поскольку "Пустое, 0" не имеет смысла, я могу рассматривать "0" как "16".

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

В худшем случае у меня есть пустой квадрат между каждой частью. Но для кодирования части мне просто нужно 13 из 16 значений, поэтому, возможно, я могу использовать еще один, чтобы сказать "Empty1". Тогда мне нужно 64 nibbles == 128 бит.

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

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

[EDIT] Если вы разрешаете смарт-кодировщик, то для начальной настройки мне нужно 0 бит (потому что его не нужно кодировать каким-либо образом: он статический) плюс один байт за ход.

[EDIT2] Который оставляет пешечную трансформацию. Если пешка достигает последней строки, я могу переместить ее на место, чтобы сказать "трансформирует", а затем добавить 3 бита для части, которую она заменяет (вам не нужно использовать королеву, вы можете заменить пешку чем-нибудь но король).

Ответ 13

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

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

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

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

Ответ 14

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

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

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

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

Исходная позиция будет просто задаваться рядом пар-точек. После этого на каждом ходу будет одна пара патчей. Вы можете найти конец дескриптора начальной позиции (и начала дескриптора движений), просто найдя первую часть, которая упоминается дважды. В случае, если пешка будет повышена, будет добавлено 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 различных вариантов перемещения). Поместите это в таблицу huffman вместо полей.

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

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

Было ли это общее снижение размера - я не знаю. Возможно, но немного экспериментировать.

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

Ответ 15

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

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

Тогда нам понадобится один бит, для которого он есть - приводит нас к 198 бит.

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

Итак, для каждой пешки, которая находится на доске, бит "0" указывает, что она не продвигается. Если пешка не находится на доске, нам совсем не нужно ничего. Затем мы можем использовать битовые строки переменной длины, для которых у него есть продвижение. Чаще всего это будет королева, поэтому "10" может означать QUEEN. Затем "110" означает ладья, "1110" означает епископ, а "1111" означает рыцарь.

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

===

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

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

Также в этой схеме включить "взято" как возможную позицию. Это может очень эффективно справиться с кастингом - каждая ладья и король будут иметь дополнительное "исходное положение, перемещенное" состояние. Вы также можете кодировать en passant в пешки таким образом - "исходное положение, может быть passass".

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

Ответ 16

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

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

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

Исходная позиция наиболее сложна и может генерировать около 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.

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

Ответ 17

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

Итак, позвольте начальному состоянию платы указать один бит "0".

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

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

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

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

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

Ответ 18

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

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

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

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

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

Ответ 19

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

Предполагая, что:

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

... так что современные современные правила. Сначала, независимо от повторения и ограничения на пересадку.

-C 25 bytes rounded (64b + 32 * 4b + 5b = 325b)

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

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

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

-D повторение положения... например. как указано выше (см. C) или нет... (см. следующие правила FIDE) -Е Это оставляет сложную проблему с 50-процентным пособием без захвата или пешки, там необходим счетчик... Однако.

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

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

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

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

Ответ 20

Возможное улучшение исходной позиции в решении Yacoby

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

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

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

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

Ответ 21

На доске есть 32 штуки. Каждая часть имеет позицию (одна на 64 квадрата). Таким образом вам просто нужно 32 положительных целых числа.

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

Ответ 22

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

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

Ответ 23

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

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

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

Ответ 24

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

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

Исходные позиции требуют максимум 320 бит (32 штуки, 4 + 6 бит)

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

Для Castling потребуются дополнительные 16 бит, так как это двойной ход.

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

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

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

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

Исходные позиции = макс. 384 бит (32 штуки, 6 + 6 бит) Каждый ход = 12 бит (позиция, кусок-идентификатор)

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

Ответ 25

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

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

Пешка: Вперед, сначала повернуть два вперед, en passant * 2, promotion = 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 для королей)

Ответ 26

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

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

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

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

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

• Пешки: у неподвижной пешки есть 2 варианта назначения, поэтому требуется 1 бит. Если пешка может захватить другую, либо обычную, либо en passant (которую декодер может определить, так как он отслеживает состояние), он также имеет 2 или 3 варианта ходов. Кроме того, у пешки может быть только один выбор, не требующий бит. Когда пешка находится в своем ранге 7 ^th мы также придерживаемся выбора продвижения. Поскольку пешки обычно продвигаются к королеве, за которыми следуют рыцари, мы кодируем выбор как:
  • королева: 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 является степенью двух, мы не могли изменять параметры.

Ответ 27

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

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

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

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

Ответ 28

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

• 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 бит.

Ответ 29

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

Самый простой способ, с которым я думал, - это сначала иметь массив из 8 * 8 бит, представляющий местоположение каждой части (So 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 бит] Перемещает

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

Если перемещение является нормальным ходом, деталь перемещения выглядит примерно так: [5 бит] шт.
[n бит] перемещение конкретного элемента (обычно в диапазоне от 2 до 6 бит)

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

Ответ 30

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

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

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

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

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

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

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

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