Вопросы Теги

Загадка программиста: Кодирование шахматной доски указывает всюду по игре

Thread.Sleep(50);

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

Этот метод не выполняет стандартный COM и нагнетание SendMessage. Если необходимо спать на потоке, который имеет STAThreadAttribute, но Вы хотите выполнить стандартный COM и нагнетание SendMessage, рассмотреть использование одной из перегрузок метода Соединения, который определяет интервал тайм-аута. 

Thread.Join
92
задан 5 revs, 2 users 100% 3 December 2009 в 08:56
поделиться

29 ответов

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

Проблема

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

starting chess position

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

  1. e4 e5
  2. Nf3 Nc6
  3. …

, что означает:

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

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

early opening

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

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

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

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

Рокировка

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

  1. e4 e5
  2. Nf3 Nc6
  3. Bb5 a6
  4. Ba4 Bc5

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

later opening

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

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

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

En Passant

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

en passant

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

  1. e4 e5
  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 на доске и иметь флажок, чтобы указать, возможно ли это.

Продвижение

pawn promotion

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

  1. h8 = Q

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

Пат

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

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

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

Чья очередь?

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

Две проблемы

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

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

Simple Contents

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

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

Но мы можем сделать лучше.

Кодирование Base 13

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

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

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

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

Таким образом, мы можем закодировать нашу позицию как p 0 x 13 63 + p 1 x 13 62 + ... + p 63 x 13 0 где p i представляет содержимое квадрата i .

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

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

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

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

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

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

morse code

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

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

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

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

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

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

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

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

Huffman code tree

В приведенном выше дереве буква E кодируется как 000 (или слева-слева-слева) и S равно 1011. Должно быть ясно, что эта схема кодирования однозначна .

Это важное отличие от кода Морзе. Код Морзе имеет разделитель символов, поэтому он может выполнять неоднозначную замену (например, 4 точки могут быть H или 2 Is), но у нас есть только единицы и нули, поэтому вместо этого мы выбираем однозначную замену.

Ниже представлена ​​простая реализация: 

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 8 возможностей, что равняется 28 179 280 429 056. Для кодирования такого количества значений вам потребуется 45 бит.

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

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

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

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

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

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

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

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

Аннотации

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

  1. Bb5 !! Nc4?

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

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

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

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

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

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

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

Заключение

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

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

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

132
ответ дан 24 November 2019 в 06:25
поделиться

Сохранение состояния доски

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

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

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

  • Pawn: 2
  • Rook: 4
  • Конь: 4
  • Слон: 4
  • Король: 5
  • Королева: 5

Учитывая итоговые значения: 

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

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

Итак, лучший метод, который я нашел, - сохранить его в 8 2 + 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 бит.

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



Resultant Format
Таким образом, формат файла будет выглядеть примерно так

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

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

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

Мы кодируем назначение большинства фигур, нумеруя квадраты вдоль линий в следующем порядке: 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 n , то добавьте C к c . Декодирование числа меняет это на противоположное: если полученный c > = C , вычтите C и установите первый бит для следующего числа равным 1. Если c <2 n - C , затем установите первый бит для следующего числа равным 0. Если 2 n - C ] <= c < C , то ничего не делать. Назовите эту схему «насыщением».

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

Доска состоит из 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 бит.

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

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

РЕДАКТИРОВАТЬ1: Забыл про рокировку и переход пешки на любую фигуру. В результате общее количество с явными позициями может составить 557 ходов (еще 3 бита для пешек, 2 для королей)

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

Каждой фигуре будет назначен идентификатор. Поскольку есть 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: Еще один частный случай. Если в состоянии игры НЕТ ходов, важно различать, кто ходит следующим. Добавьте еще один бит в конце для этого. :)

2
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

48
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

4
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

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

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

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

2
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

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

9
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

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

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

  4. епископов:

4
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

3
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

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

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

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

2
ответ дан 24 November 2019 в 06:25
поделиться

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

Бит на кусок:

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

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

3
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

2
ответ дан 24 November 2019 в 06:25
поделиться

Существует 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. Королю также следует брать несколько битов.

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

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

2
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

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

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

1
ответ дан 24 November 2019 в 06:25
поделиться

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

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

2
ответ дан 24 November 2019 в 06:25
поделиться

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

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

ОБНОВЛЕНИЕ 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 бит для начальной позиции + (переменное количество бит в зависимости от типа перемещаемого объекта).

ОБНОВЛЕНИЕ 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 бит для начальной позиции + (переменное количество бит в зависимости от типа перемещаемого объекта).

мы можем сэкономить биты на кодировании «места назначения». 

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 бит для начальной позиции + (переменное количество бит в зависимости от типа перемещаемого объекта).

мы можем сэкономить биты на кодировании «места назначения». 

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 бит для начальной позиции + (переменное количество бит в зависимости от типа перемещаемого объекта).

4
ответ дан 24 November 2019 в 06:25
поделиться

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

32 элемента * 7 бит = 224 бит

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

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

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

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

3
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

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

2
ответ дан 24 November 2019 в 06:25
поделиться

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

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

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

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

Вот как я бы кодировал шаги игры. Для партии с 40 шагами это займет около 180 бит или около того.

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

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

В результате вы получите список, подобный этому:

[[10, 3], # choose white pawn at index #3
 [2, 0],  # move it one step forward
 [10, 2], # choose black pawn #2 
 [2, 1],  # move it two steps forward
 ...
]

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

[[10, 3], # 10 choices => 4 bits
 [2, 0],  # 2 choices => 1 bit
 [10, 2], # 10 choices => 4 bits
 [2, 1],  # 2 choices => 1 bit
 ...
]

Totalals 4+1+4+1=10 бит для первых двух ходов. Но несколько битов растрачиваются впустую, используя 4 бита для 10 вариантов выбора, мы теряем 6 возможных вариантов.

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

n = 0         # last position
n = n*2 + 1   # from [2, 1]   n=1
n = n*10 + 2  # from [10, 2]  n=12
n = n*2 + 0   # from [2, 0]   n=24
n = n*10 + 3  # from [10, 3]  n=243

Теперь у нас есть число 243, двоичное 11110011, которое кодирует все вышеперечисленные шаги всего в 8 бит.

Для расшифровки мы знаем, что начальная открывающая позиция имеет 10 возможных вариантов. Вычислить

n = 243
choice = n % 10  # we know there are 10 moveable pieces. => choice=3
n /= 10          # n=24
choice = n % 2   # we know 2 possible moves for selected pawn => choice=0
n /= 2           # n=12
choice = n % 10  # 10 moveable pieces for black player. => choice=2
n /= 10          # n=1
choice = n % 2   # 2 possible moves for pawn => choice=1
n /= 2           # n=0, finished decoding

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

1
ответ дан 24 November 2019 в 06:25
поделиться
Другие вопросы по тегам:

Похожие вопросы: