Программист головоломка: кодирование состояния шахматной доски на протяжении всей игры

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



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



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



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



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



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



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



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



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

1223   30  

30 ответов:

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

Проблема

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

начальная шахматная позиция http://img222.imageshack.us/img222/5970/chess.png

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

  1. e4 e5
  2. Nf3 Nc6
  3. ...

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

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

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

раннее открытие http://img222.imageshack.us/img222/371/chessx.png

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

так чего же не хватает или неоднозначно? Много как выясняется.

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

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

рокировка

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

  1. e4 e5
  2. Nf3 Nc6
  3. BB5 по А6
  4. Ba4 Bc5

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

later opening

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

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

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

En Passant

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

мимоходом http://img37.imageshack.us/img37/6535/chessa.png

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

  1. e4 e5
  2. Nf3 Nc6
  3. Bb5 a6
  4. Ba4 Bc5
  5. O-O b5
  6. ход BB3 В4
  7. c4

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

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

продвижение

продвижение пешки http://img689.imageshack.us/img689/5970/chess.png

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

  1. h8=Q

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

тупик

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

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

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

Чья Очередь?

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

Две Проблемы

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

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

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

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

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

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

Кодировка Базы 13

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

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

в базе 10 число 234 эквивалентно 2 x 102 + 3 x 101 + 4 x 100.

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

таким образом, мы можем кодировать нашу позицию как p0 x 1363 + p1 x 1362 + ... + p63 x 130 где pя представляет содержимое квадрата Я.

2256 равна приблизительно 1.16e77. 1364 равняется приблизительно 1. 96e71,что требует 237 бит пространства для хранения. Эта экономия всего лишь 7,5% происходит за счет значительно увеличение затрат на манипуляции.

Переменная Кодировка Базы

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

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

Переменной Ширины Буквы

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

morse code

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

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

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

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

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

так как же это относится к нашей проблеме?

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

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

Huffman code tree

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

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

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

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 х 1 + 16 х 3 + 12 х 5 + 4 х 6 = 164 бит.

Разница В Состоянии

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

Итак, что вы делаете, это XOR 256-битный ток положение платы с 256-битной начальной позицией, а затем кодировать это (используя кодирование Хаффмана или, скажем, какой-то метод выполнить кодировку длины). Очевидно, что это будет очень эффективно для начала (64 0s, вероятно, соответствует 64 битам), но увеличение объема памяти требуется по мере развития игры.

Кусок Должность

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

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

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

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

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

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

Он должен следует отметить, что их меньше 488 возможности потому что пешки не могут все быть в одном квадрате первый имеет 48 возможностей, второй 47 и так далее. 48 х 47 Х ... Х 41 = 1.52e13 = 44 бита для хранения.

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

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

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

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

Игры

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

аннотации

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

  1. класс BB5!! Nc4?

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

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

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

Алгебраическая Нотация

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

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

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

вывод

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

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

шахматные позиции, взятые в качестве скриншотов из Тренер Шахматной Позиции.

129  
2017-02-08 16:17:50

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

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

например.

[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  
2009-12-02 11:51:19

большая загадка!

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

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

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

  • 0 для пустых квадратов
  • 1c0 для ломбарда
  • 1c100 Грач
  • 1c101 для рыцарь
  • 1c110 для епископа
  • 1c1110 для королевы
  • 1c1111 для король

для всей платы в ее первоначальной ситуации у нас есть

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

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

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

  • оставляя менее частые части и сохраняя их положение отдельно. Но это не поможет... замена короля и королевы пустым квадратом экономит 5 бит, которые являются именно 5 битами, которые вам нужно кодировать их положение другим способом.
  • "нет пешек на заднем ряду" можно легко закодировать, используя другую таблицу Хаффмана для задних строк, но я сомневаюсь, что это очень помогает. Вы, вероятно, все равно закончите с тем же деревом Хаффмана.
  • "один белый, один черный слон" может быть закодирован путем введения дополнительных символов, которые не имеют c бит, который может тогда выводите из квадрата, что епископ находится на. (Пешки, продвигаемые к епископам, нарушают эту схему...)
  • повторения пустых квадратов могут быть закодированы по длине, введя дополнительные символы, например," 2 пустых квадрата в строке "и"4 пустых квадрата в строке". Но не так-то просто оценить их частоту, и если вы ошибетесь, это скорее навредит, чем поможет.
14  
2009-12-02 11:47:06

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

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

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

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

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

9  
2009-12-03 07:54:55

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

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

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

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

4  
2009-12-03 12:11:30

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

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

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

4  
2009-12-03 20:08:05

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

простое решение

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

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

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

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

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

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

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

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

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

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

4  
2009-12-04 15:57:16

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

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

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

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

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

EDIT:

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

при каждом движении мы добавляем информацию о размер

num_of_moves = get_number_of_possible_moves(postion) ;

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

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

n=n*num_of_moves+ index_current_move

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

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

пример хранения в info бассейн

предположим, что мы знаем стартовые позиции и делаем 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(п) ansd емкостная сложность составляет o(Н). Edit: временная сложность на самом деле 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 пешка может быть в одном из 8 мест), 16 (4 бита) для рокировки ограничений и один бит для сайта, который имеет движение. Мы в конечном итоге с 142+3+4+1= 150bits

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

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

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

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

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

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

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

4  
2010-02-02 18:58:48

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

бит на фрагмент:

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

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

3  
2009-12-02 12:46:48

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

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

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

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

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

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

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

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

3  
2009-12-02 13:01:29

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

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

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

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

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

изменить: Как лохматая лягушка, нам нужен еще один бит в конце, чтобы указать, чья очередь ;^)

3  
2010-02-02 17:30:28

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

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

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

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

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

2  
2009-12-02 11:17:13

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

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

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

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

2  
2009-12-02 11:26:27

существует 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. Король тоже должен взять несколько кусочков.

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

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

2  
2009-12-02 11:47:26

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

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

каждая часть будет иметь назначенный идентификатор. Поскольку есть 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  
2009-12-02 11:55:21

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

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

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

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

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

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

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

2  
2009-12-03 13:34:46

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

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

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

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

2  
2009-12-03 16:39:10

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

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

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

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

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

2  
2009-12-23 12:49:44

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

предположим:

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

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

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

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

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

теперь, следующие правила применимы только тогда, когда игрок apllies для ничьей, это не автоматически! Так что считайте, что это 90 ходов без a захват или пешечный ход возможен, если ни один игрок не требует ничьей! Это означает, что все движения должны быть записаны... и доступно.

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

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

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

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

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

2  
2012-11-03 15:33:20

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

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

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

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

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

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

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

1  
2009-12-02 10:29:23

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

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

1  
2009-12-02 10:34:23

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

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

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

1  
2009-12-02 10:45:52

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

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

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

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

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

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

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

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

1  
2009-12-02 11:09:30

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

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

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

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

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

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

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

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

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

начальные положения = максимальные 384 бита (32 части, 6 + 6 битов) Каждый ход = 12 бит (to-position, piece-id)

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

1  
2009-12-02 11:22:56

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

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

ходам не нужно записывать состояние; декодер может отслеживать состояние, а также то, что движется законно в любой заданной точке. Все ходы нужно записывать, что из различных правовых альтернатив выбирается одна. Поскольку игроки чередуются, движение не нужно записывать цвет игрока. Поскольку игрок может перемещать только свои собственные цветные фигуры, первый выбор-это то, какую часть игрок перемещает (я вернусь к альтернативе, которая использует другой выбор позже). С не более чем 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 n, затем добавить C до c. Декодирование числа отменяет это: если полученный c>= C вычесть C и установите первый бит для следующего числа в 1. Если c n -C, затем установите первый бит для следующего числа в 0. Если 2n -C c C, то ничего не делать. Назовем эту схему "насыщением".

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

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

1  
2009-12-02 13:50:24

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

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

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

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

1  
2009-12-03 07:09:15

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

  • 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  
2009-12-03 10:00:14

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

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

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

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

  • пешка : 2
  • Грач: 4
  • рыцарь: 4
  • епископ: 4
  • Король: 5
  • Королева: 5

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

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

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

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

8*8 + 100 = 164



Хранение Ходов
Первое, что нам нужно знать, это то, какая часть движется туда. Учитывая, что на доске есть не более 32 штук, и мы знаем, что такое каждая часть, а не an целое число, представляющее квадрат, мы можем иметь целое число, представляющее смещение части, что означает, что нам нужно только соответствовать 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 бит]

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

1  
2009-12-03 14:00:29

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

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

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

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

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

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

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

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

1  
2009-12-07 17:52:49

Comments

    Ничего не найдено.
Click here to cancel reply.