프로그래머 퍼즐 : 게임 내내 체스 판 상태 인코딩

lottoking 2020. 8. 31. 08:05

프로그래머 퍼즐 : 게임 내내 체스 판 상태 인코딩

엄격하게 질문이 아니라 퍼즐에 가깝습니다 ...

수년에 몇 가지 저는 신입 사원에 대한 몇 가지 기술 인터뷰에 참여했습니다. 표준 "X 기술을 알고 계십니까"질문을하는 것입니다 그들이 문제에 어떻게 접근하는지에 대한 느낌을 얻으려고 노력했습니다. 일반적으로 인터뷰 전날 이메일로 질문을 보내고 다음 날까지 해결을 기대합니다.

종종 결과는 매우 흥미 롭습니다. 틀렸지 만 흥미로울 것입니다. 그리고 그 사람은 접근 방식을 사용하여 접근 할 수 있습니다.

그래서 저는 Stack Overflow 청중을 위해 제 질문 중 하나를 던질 생각했습니다.

질문 : 체스 게임 (또는 그 하위 집합)의 상태를 인코딩하기 위해 생각할 수있는 가장 공간적인 방법은 무엇입니까? 모든 법적 즉, 합법적으로 배열 된 조각이있는 체스 판이 주어지면이 초기 상태와 게임에서 플레이어가 취하는 모든 법적 즉 동작을 인코딩합니다.

답변에 필요한 코드는 사용할 알고리즘에 대한 설명 만 있으면됩니다.

편집 : 포스터 중 하나가 지적했듯이 나는 움직임 사이의 시간 간격을 고려하지 않습니다. 추가 옵션으로도 고려하십시오. :)

EDIT2 : 추가 설명을 ... 기억하십시오, 요청 / 위해는 규칙을 인식합니다. 실제로 저장해야하는 유일한 것은 플레이어의 선택입니다. 다른 것은 추측 할 수 있습니다.

EDIT3 : 여기서 우승 할 때 선택하는 것이 어려울 것입니다. :) 많은 훌륭한 답변!

업데이트 : 저는 프로그래밍 퍼즐, 체스 포지션, 허프만 코딩을 썼습니다 . 제출 읽어 보면 완전한 게임 상태를 저장하는 유일한 방법은 전체 동작 목록을 저장하는 것을 결정했습니다 . 이유를 읽어 내십시오. 그래서 저는 조각 레이아웃에 대해 단순화 된 버전의 문제를 사용합니다.

문제

이 이미지는 시작 체스 위치를 보여줍니다. 체스는 8x8 보드에서 발생하며 각 플레이어는 8 개의 폰, 2 개의 루크, 2 개의 기사, 2 개의 비숍, 1 개의 퀸, 1 개의 킹으로 이루어진 동일한 16 개의 조각 세트로 시작합니다.

위치는 일반적으로 열의 문자와 행의 숫자로 기록 흰색의 여왕은 d1에 있습니다. 이동은 대부분의 경우 대수 표기법으로 저장하고 , 이는 일반적으로 필요한 최소한의 정보 만 지정합니다. 이 오프닝을 고려하십시오.

e4 e5
Nf3 Nc6
…

다음으로 번역됩니다.

White는 왕의 폰을 e2에서 e4로 이동합니다 (e4에 도달 할 수있는 유일한 조각 "e4").
Black은 왕의 폰을 e7에서 e5로 이동합니다.
흰색은 기사 (N)를 f3으로 이동합니다.
검은 색은 기사를 c6로 이동합니다.
…

보드는 다음과 가변적입니다.

프로그래머에게 중요한 모든 능력 은 문제 를 정확하고 명확하게 지정할 수 있다는 을 구석으로 입니다.

그래서 어떤 존재인지 모호? 밝혀진대로 많이.

보드 상태 대 게임 상태

가장 먼저 결정해야 할 것인지 아니면 보드에있는 조각의 위치를 저장할 게임입니다. "모든 법적 법적 이동"이라고 말하면 조각의 위치를 인코딩하는 것은 하나이지만 문제입니다. 문제는 또한이 시점까지의 움직임을 아는 것에 대해 아무것도 말하지 않습니다. 제가 설명 하겠지만 실제로 문제입니다.

캐슬 링

게임은 다음과 같이 진행되었습니다.

e4 e5
Nf3 Nc6
Bb5 a6
Ba4 Bc5

보드는 다음과 같이 시청합니다.

나중에 개봉

흰색에는 캐슬 링 옵션이 있습니다. 이것에 대한 요구 사항의 일부는 왕과 관련 루크가 실행 일 수 있기 때문에 왕이나의 루크가 이동 여부를 저장해야한다는 것입니다. 분명히 그들로부터 시작 위치에 있지 않다면, 그들이 그것을하지 않고 그것을 지정해야합니다.

이 문제를 처리하는 데 사용할 수있는 몇 가지 가지 전략이 있습니다.

첫째, 그 조각이 움직 였는지 여부를 나타냅니다. 내기 위해 6 비트의 추가 정보 (각 루크와 킹에 대해 1 개)를 지정 수 있습니다. 올바른 조각이있는 경우 6 개의 사각형 중 하나에 대해 약간만 저장하여이를 쉽게 할 수 있습니다. 또는 움직이지 않은 각 조각을 다른 조각 유형으로 취급 할 수 있으므로 각면에 6 개의 조각 유형 (폰, 루크, 나이트, 비숍, 퀸 및 킹) 대신 8 개 (움직이지 않은 루크 및 움직이지 않은 킹 추가)가 있습니다.

En Passant

Chess에서 독특하고 자주 무시되는 또 다른 규칙은 En Passant 입니다.

게임이 진행되었습니다.

e4 e5
Nf3 Nc6
Bb5 a6
Ba4 Bc5
OO b5
Bb3 b4
c4

b4에있는 Black의 폰은 이제 b4에있는 그의 폰을 c4에있는 White 폰을 가져와 c3로 선택할 수있는 옵션이 있습니다. 이 첫 번째 기회 발생합니다. 즉, Black이 옵션을 통과하면 다음 이동을 수행 할 수 없습니다. 그래서 우리는 저장해야합니다.

이전 움직임을 알고 있습니다. Passant가 가능한지 확실히 대답 할 수 있습니다. 또는 4 순위에있는 각 폰이 두 번 앞으로 이동하여 방금 이동했는지 여부를 선택할 수 있습니다. 또는 우리는 보드에서 가능한 각 En Passant 위치를보고 가능한지 여부를 플래그를 사용할 수 있습니다.

프로모션

화이트의 움직임입니다. White가 자신의 폰을 h7에서 h8로 다른 말로 승격 될 수 있습니다 (왕은 아님). 99 %의 경우 여왕으로 승진 맞습니다. 일반적으로 그것은 승리 할 때 교착 상태가 될 수 있기 때문입니다. 이것은 다음과 같이 작성됩니다.

h8 = Q

이것은 우리가 각면에 고정 된 수의 조각이있는 것을 의미하는 것이 중요합니다. 8 개의 폰이 모두 승격 널 한 쪽이 9 명의 퀸, 10 명의 루크, 10 명의 비숍 또는 10 명의 명의 기사로 끝날 가능성은 전적으로 가능합니다.

수가 막히게하다

당신이 이길 수없는 위치에있을 때 당신의 최선의 전술은 교착 상태 를 시도하는 것 입니다. 가장 가능성이 높은 변형은 합법적 인 이동을 할 수없는 경우입니다 (일반적으로 킹을 체크 할 때 이동하기 때문에). 이 경우 무승 어 어떤 경우에도 사용할 수 있습니다. 이것은 음식을 제공하기 위해서입니다.

두 번째 변형은 3 중 반복 입니다. 같은 보드 위치가 게임에서 세 번 발생하면 (또는 다음 이동에서 세 번 발생) 무승부가 청구될 수 있습니다. (즉, 순서의 동작을 세 번 반복 할 수 없습니다). 이 이전의 모든 보드 위치를 기억해야하기 때문에 크게 복잡하게 만듭니다. 이것이 문제의 요구 사항 인 경우 문제에 대한 유일한 해결책은 이전의 모든 이동을 저장하는 것입니다.

마지막으로 50 개의 이동 규칙이 있습니다. 플레이어는 폰이 움직이지 갑자기 고 이전 50 개 연속 이동 지에서 조각을 가져와야 할 경우 무승 어 청구 할 수 있으므로 폰이 이동 한 이후 또는 조각을 저장해야 할 것입니다. 6 비트 (0-63).

누구의 차례인가?

물론 우리는 누구의 차례인지 알 필요가 있으며 하나의 정보입니다.

두 가지 문제

교착 상태로 인해 게임 상태를 저장하는 유일하고 현명한 방법은이 위치로 이어진 모든 동작을 저장하는 것입니다. 그 한 가지 문제를 해결하겠습니다. 보드 상태 문제는 다음과 같이 단순화됩니다. 캐슬 링, en passant, 교착 상태 및 차례를 무시하고 보드에있는 모든 조각의 현재 위치를 저장합니다 .

조각 레이아웃은 각 사각형의 내용을 저장하거나 각 조각의 위치를 저장하는 두 가지 방법 중 하나로 처리 할 수 있습니다.

간단한 내용

6 가지 유형 (폰, 루크, 나이트, 비숍, 퀸, 킹)이 있습니다. 각 조각은 흰색 또는 검은 색 색일 수 있으므로 사각형에는 12 개의 가능한 조각 중 하나가 사용할 수 있습니다. 비어있어 13 개의 가능성이 있습니다. 13은 4 비트 (0-15)로 저장 될 수 있으므로 가장 간단한 방법은 각 제곱에 대해 4 비트를 64 제곱 또는 256 비트 정보로 저장하는 것입니다.

이 방법의 장점은 조작이 매우 유사 빠르다는 것입니다. 저장 공간 요구 사항을 늘리지 않고 3 개의 가능성을 더 추가하여 확장 할 수도 있습니다. 이전에 언급 된 문제의

그러나 우리는 더 잘할 수 있습니다.

Base 13 인코딩

많은 수로 생각하면 도움이됩니다. 이것은 종종 컴퓨터 과학에서 수행됩니다. 예를 들어, 중지 문제 는 컴퓨터 프로그램을 (올바르게) 많은 수로 취급합니다.

첫 번째 솔루션은 위치를 64 자리 16 진수로 처리하지만이 정보에 두성이 있으므로 ( "숫자"당 사용되지 않는 것이 3 가지 가능성) 숫자 공간을 64 진수 13 자리로 수 있습니다. 물론 수행 할 수없는 저장 요구 사항을 절약 할 수 있습니다 (저장 공간 최소화가 목표입니다).

베이스 (10)의 수 (234)는 2 × 동등 ² + 3 × 10 ¹ + 4 × 10 ⁰ .

16 진법에서 숫자 0xA50은 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (십진수)과 가변됩니다.

따라서 위치를 p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ^0으로 인코딩 할 수 있습니다. 여기서 p _i 는 제곱 i 의 내용을 나타냅니다 .

2 ²⁵⁶ 등호 약 1.16e77. 13 ^64는 약 1.96e71과 같으며 237 비트의 저장 공간이 필요합니다. 7.5 % 만 절약 하면 조작 비용 이 크게 증가합니다.

가변베이스 인코딩

법적 게시판에서는 특정 조각이 특정 사각형에 나타날 수 없습니다. 예를 들어, 폰은 첫 번째 또는 여덟 번째 등급에서 인벤토리 수있는 사각형의 가능성을 11로 줄입니다. 그러면 가능한 보드가 11 ¹⁶ x 13 ⁴⁸ = 1.35e70 (대략)으로 233 비트의 저장 공간이 필요합니다.

코드는 값을 십진수 (또는 이진수)로 인코딩하고 사용하는 것이 좀 더 복잡하지만 안정적으로 수행 할 수 있습니다.

가변 폭 알파벳

앞의 두 가지 방법은 모두 고정 너비 인코딩으로 설명 할 수 있습니다 . 알파벳의 11, 13 또는 16 멤버 각각은 다른 값으로 대체됩니다. 각 "문자"는 너비가 같지만 각 문자의 가능성이 같지 않다는 점을 고려하면 효율성이 향상 될 수 있습니다.

모스 식 부호

모스 부호를 고려하십시오 (위 그림 참조). 메시지의 문자는 인코딩의 대시와 점으로 인코딩됩니다. 이제 대시와 점은 라디오 (일반적으로)를 통해 전송되며 사이에 일시 중지되어 있습니다.

문자 E ( 영어에서 가장 일반적인 문자 )가 단일 점, 가능한 가장 짧은 시퀀스 인 반면 Z (최소 빈도)는 대시 2 개와 경고음 2 개입니다.

체계는 이러한 예상되는 메시지 의 크기를 크게 줄일 수 있지만 무작위 문자 시퀀스의 크기를 증가시키는 비용이 발생합니다.

모스 코드에는 또 다른 내장 기능이 점에 유의해야합니다. 대시는 점 3 개만큼 길기 때문에 대시 사용을 최소화하기 위해 위의 코드가이를 염두에두고 생성합니다. 1과 0 (빌딩 블록)은 문제가 없기 때문에 복제해야 할 기능이 아닙니다.

마지막으로 모스 부호에는 두 가지 종류의 쉼표가 있습니다. 짧은 휴식 (점의 길이)은 점과 대시를 구분하는 데 사용됩니다. 더 긴 간격 (대시 길이)은 문자를 구분하는 데 사용됩니다.

검증이 우리 문제에 어떻게 검증?

허프만 코딩

Huffman 코딩 이라는 가변 길이 코드를 처리하는 알고리즘이 있습니다 . Huffman 코딩은 일반적으로 기호의 예상 빈도를 사용하여 더 일반적인 기호에 더 짧은 값을 할당하는 가변 길이 코드 대체를 생성합니다.

위의 트리에서 문자 E는 000 (또는 왼쪽 왼쪽 왼쪽)으로 인코딩되고 S는 1011입니다. 인코딩 체계는이 명확해야 우리 합니다.

이것은 모스 부호와의 중요한 차이점입니다. 모스 부호는 문자 구분 기호가 있으므로 모호한 대체를 수행 할 수 있습니다 (예 : 4 개의 점은 H 또는 2 개의 경우).하지만 1과 0은 대신 명확한 대체를 선택합니다.

다음은 간단한 구현입니다.

private static class Node {
  private final Node left;
  private final Node right;
  private final String label;
  private final int weight;

  private Node(String label, int weight) {
    this.left = null;
    this.right = null;
    this.label = label;
    this.weight = weight;
  }

  public Node(Node left, Node right) {
    this.left = left;
    this.right = right;
    label = "";
    weight = left.weight + right.weight;
  }

  public boolean isLeaf() { return left == null && right == null; }

  public Node getLeft() { return left; }

  public Node getRight() { return right; }

  public String getLabel() { return label; }

  public int getWeight() { return weight; }
}

정적 데이터 사용 :

private final static List<string> COLOURS;
private final static Map<string, integer> WEIGHTS;

static {
  List<string> list = new ArrayList<string>();
  list.add("White");
  list.add("Black");
  COLOURS = Collections.unmodifiableList(list);
  Map<string, integer> map = new HashMap<string, integer>();
  for (String colour : COLOURS) {
    map.put(colour + " " + "King", 1);
    map.put(colour + " " + "Queen";, 1);
    map.put(colour + " " + "Rook", 2);
    map.put(colour + " " + "Knight", 2);
    map.put(colour + " " + "Bishop";, 2);
    map.put(colour + " " + "Pawn", 8);
  }
  map.put("Empty", 32);
  WEIGHTS = Collections.unmodifiableMap(map);
}

과 :

private static class WeightComparator implements Comparator<node> {
  @Override
  public int compare(Node o1, Node o2) {
    if (o1.getWeight() == o2.getWeight()) {
      return 0;
    } else {
      return o1.getWeight() < o2.getWeight() ? -1 : 1;
    }
  }
}

private static class PathComparator implements Comparator<string> {
  @Override
  public int compare(String o1, String o2) {
    if (o1 == null) {
      return o2 == null ? 0 : -1;
    } else if (o2 == null) {
      return 1;
    } else {
      int length1 = o1.length();
      int length2 = o2.length();
      if (length1 == length2) {
        return o1.compareTo(o2);
      } else {
        return length1 < length2 ? -1 : 1;
      }
    }
  }
}

public static void main(String args[]) {
  PriorityQueue<node> queue = new PriorityQueue<node>(WEIGHTS.size(),
      new WeightComparator());
  for (Map.Entry<string, integer> entry : WEIGHTS.entrySet()) {
    queue.add(new Node(entry.getKey(), entry.getValue()));
  }
  while (queue.size() > 1) {
    Node first = queue.poll();
    Node second = queue.poll();
    queue.add(new Node(first, second));
  }
  Map<string, node> nodes = new TreeMap<string, node>(new PathComparator());
  addLeaves(nodes, queue.peek(), &quot;&quot;);
  for (Map.Entry<string, node> entry : nodes.entrySet()) {
    System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
  }
}

public static void addLeaves(Map<string, node> nodes, Node node, String prefix) {
  if (node != null) {
    addLeaves(nodes, node.getLeft(), prefix + "0");
    addLeaves(nodes, node.getRight(), prefix + "1");
    if (node.isLeaf()) {
      nodes.put(prefix, node);
    }
  }
}

가능한 출력은 다음과 가변적입니다.

         White    Black
Empty          0 
Pawn       110      100
Rook     11111    11110
Knight   10110    10101
Bishop   10100    11100
Queen   111010   111011
King    101110   101111

시작 위치의 경우 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 비트와 가변적입니다.

국가 차이

또 다른 가능한 접근 방식은 첫 번째 접근 방식을 Huffman 코딩과 결합하는 것입니다. 이 (무작위로 생성되는 것이 아니라) 대부분의 예상 체스 보드가 중간 적으로는 시작과 만나지 않을 가능성이 더 많은 가정을 기반으로합니다.

그래서 여러분이하는 일은 256 비트 시작 위치로 256 비트 현재 보드 위치를 XOR 한 다음이를 인코딩합니다 (허프만 코딩 또는 실행 길이 인코딩 방법 사용 ). 분명히 이것은 (64 비트에 해당하는 64 0s) 시작하는 데 매우이지만 저장 게임이 진행됨에 따라 필요한 공간이 증가합니다.

조각 위치

많은 언급 했듯이이 문제를 해결하는 또 다른 방법은 플레이어가 가지고있는 각 조각의 위치를 저장하는 것입니다. 이것은 대부분의 사각형이 비어있는 최종 게임 위치에서 특히 잘 작동합니다 (그러나 Huffman 코딩 방식에서는 빈 사각형이 어쨌든 1 비트 만 사용합니다).

각면에는 킹과 0-15 개의 다른 조각이 있습니다. 승진으로 인해서 조각의 정확한 구성은 시작 위치를 기반으로 한 숫자가 최대라고 가정 할 수 있고 다양하게 할 수 있습니다.

두 개의 개의면 (흰색과 검은 색)으로 분할하는 방법을 저장하는 것입니다. 각에는 다음이 있습니다.

킹 : 위치에 대해 6 비트;
폰 있음 : 1 (예), 0 (아니오)
모든 폰 수 : 3 비트 (0-7 + 1 = 1-8);
참조, 각 폰의 위치가 인코딩됩니다 : 45 비트 (아래 참조);
비 폰의 수 : 4 비트 (0-15);
각 조각 : 유형 (퀸, 루크, 나이트, 비숍의 경우 2 비트) 및 위치 (6 비트)

폰 위치와 관련하여 폰은 48 개의 가능한 사각형에있을 수 있습니다 (다른 것과 같은 64 개가 아닌). 따라서 폰당 6 비트를 사용하는 경우 사용할 경우 추가 16 개의 값을 사용할 수없는 것이 좋습니다. 따라서 폰이 8 개인 경우 28,179,280,429,056에 해당 하는 48 ⁸ 가능성 이 있습니다 . 많은 값을 인코딩 비용으로 45 비트가 필요합니다.

이 비트 당 105 비트 또는 총 210입니다. 시작 위치는이 방법의 경우 최악의 경우이며 조각을 제거하면 상당히 좋아합니다.

48 ^{8 개} 미만의 가능성 이 있으므로 모두 같은 사각형에있을 가능성 이 있습니다. 첫 번째는 48 개, 두 번째는 47 개 등입니다. 48 x 47 x… x 41 = 1.52e13 = 44 비트 저장.

다른 조각 (다른면 포함)이 차지하는 사각형을 제거하여이를 더욱 개선 할 수 있으므로 먼저 흰색 비폰을 배치 한 다음 검은 색 비폰을 배치 한 다음 흰색 폰과 마지막으로 검은 폰을 배치 할 수 있습니다. 시작 위치에서이 저장 요구 사항을 흰색의 경우 44 비트, 검은 색의 경우 42 비트로 줄입니다.

결합 된 접근 방식

또 다른 가능한 최적화는 방식 방식에 장단점이 있습니다. 예를 들어, 가장 좋은 4 개를 선택한 다음 처음 2 개 비트에서 시스템 선택기를 인코딩 한 다음 그 이후에 체계 별 저장소를 인코딩 할 수 있습니다.

오버 헤드가 너무 작기 때문에 최고의 접근 방식이 될 것입니다.

게임 상태

나는 위치 보다는 게임 을 저장하는 문제로 돌아 간다 . 3 중 반복 때문에이 지점까지 문제 목록을 저장해야합니다.

주석

결정해야 할 한 가지는 주석 동작 목록을 저장하는 것입니까? 체스 게임에는 종종 주석이 추가됩니다. 예를 들면 다음과 같습니다.

BB5 !! Nc4?

White의 움직임은 두 개의 느낌표가 훌륭하게 표시되는 반면 Black은 실수로 처리됩니다. 체스 구두점을 참조하십시오 .

또한 이동이 설명 된대로 자유 텍스트를 저장해야 할 수도 있습니다.

나는 움직임이 충분하여 주석이 없을 것이라고 가정합니다.

대수 표기법

여기에 이동 텍스트 ( "e4", "Bxb5"등)를 간단히 정리할 수 있습니다. 종료 바이트를 포함하여 이동 당 약 6 바이트 (48 비트)를보고 있습니다 (최악의 경우). 처음으로 처음으로 발음합니다.

두 번째 시도는 시작 위치 (6 비트)와 끝 위치 (6 비트)를 저장하여 이동 당 12 비트를 저장하는 것입니다. 훨씬 낫습니다.

또는 우리가 선택한 예측 가능하고 결정적인 방식과 상태로 현재 위치에서 모든 법적 이동을 선택할 수 있습니다. 그런 다음 언급 된 한 가변 기본 인코딩으로 돌아갑니다. 화이트와 블랙은 첫 번째 이동에서 각각 20 개의 이동이 가능하고 두 번째 이동에서 더 많은 이동이 가능합니다.

결론

이 질문에 대한 절대적으로 정답은 없습니다. 위의 몇 가지 가능한 접근 방식이 많이 있습니다.

이 문제와 문제에 대해 내가 좋아하는 점은 사용하는 패턴을 고려하고 요구 사항을 정확하게 결정하고 코너 케이스에 대해 생각하는 것과 같이 모든 프로그래머에게 중요한 능력이 필요하다는 것입니다.

Chess Position Trainer 에서 스크린 샷으로 찍은 체스 위치 .

체스 게임을 사람이 읽을 수있는 표준 형식으로 저장하는 것이 좋습니다.

휴대용 게임 표기법은 (있지만 표준 시작는 위치를 가정 할 필요가 없습니다 ) 그냥 움직임을 나열 회전에 의해 전원 을 켭니다 . 사람이 읽을 수있는 표준 형식입니다.

예

[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

더 작게 콘텐츠를 압축 하세요. 완료되었습니다!

멋진 퍼즐!

나는 대부분의 사람들이 각 조각의 위치를 저장하고있는 것을 볼 수 있습니다. 좀 더 단순한 접근 방식을 취하고 각 사각형의 내용을 저장하는 것은 무엇입니까? 승진을 처리하고 조각을 자동으로 처리합니다.

그리고 그것은 Huffman 인코딩을 허용합니다 . 실제로 보드에있는 조각의 초기 주파수는 거의 완벽합니다. 사각형의 절반은 비어 있고 나머지 사각형의 절반은 폰입니다.

각 조각의 빈도를 고려하여 종이에 허프만 나무 를 만들 때마다 반복하지 않습니다. 결과 c는 색상을 나타냅니다 (흰색 = 0, 검은 색 = 1).

빈 사각형의 경우 0
폰의 경우 1c0
루크의 경우 1c100
기 사용 1c101
비숍 용 1c110
여왕을위한 1c1110
왕을위한 1c1111

초기 상황의 전체에 대해

빈 사각형 : 32 * 1 비트 = 32 비트
폰 : 16 * 3 비트 = 48 비트
루크 / 나이츠 / 비숍 : 12 * 5 비트 = 60 비트
queens / kings : 4 * 6 비트 = 24 비트

전체 : 초기 보드 상태의 경우 164 비트 . 현재 가장 많이 투표 한 답변의 235 비트보다 훨씬 적습니다. 그리고 게임이 진행됨에 따라 더 작아 질 것입니다 (프로모션 이후 제외).

나는 삽화에있는 조각들의 위치만을. 추가 상태 (턴, 캐슬 링 한 사람, 패전트, 반복 동작 등)은 보강해야합니다. 최대 16 비트가 추가 될 수 있으므로 전체 게임 상태에 대해 180 비트 입니다. 가능한 최적화 :

자주 사용하지 않는 부분은 제외하고 위치를 저장합니다. 그러나 그것은 도움이되지 않을 것입니다. 왕과 여왕을 빈 사각형으로 바꾸면 5 비트를 절약 할 수 있습니다. 이는 다른 방식으로 위치를 인코딩하는 데 필요한 정확히 5 비트입니다.
"뒷줄에 폰 없음"은 뒷줄에 다른 Huffman 테이블을 사용하여 쉽게 인코딩 할 수 많은 도움이되지 않습니다. 당신은 아마도 여전히 같은 Huffman 나무로 끝날 것입니다.
"하나의 흰색, 하나의 검은 색 비숍"은 c비트 가없는 추가 기호를 도입하여 인코딩 할 수 있습니다. 그런 다음 비숍이있는 사각형에서 추론 할 수 있습니다. (주교로 승진 한 폰은이 계획을 방해합니다 ...)
빈 사각형의 반복은 "행에 빈 사각형 2 개"및 "행에 빈 사각형 4 개"에 대한 추가 기호를 도입하여 실행 길이로 인코딩 될 수 있습니다. 그러나 그 빈도를 추정하는 것은 그리 쉽지만, 잘못 이해하면 도움이되기 때문에 상처를 입을 것입니다.

정말 큰 조회 테이블 접근 방식

위치 -18 바이트
합법적 인 위치의 예상 수는 10입니다. ⁴³
모든 위치를 열거하면 위치를 143 비트에 등록 할 수 있습니다. 다음에 플레이 할 팀을 표시 할 1 비트가 더 필요합니다.

열거 된 형은 실용적이지 않지만 최소한 144 개의 비트가 필요하다는 것을 보여줍니다.

이동 -1 일반적 으로 각
위치에 대해 약 30-40 개의 합법적 인 이동이 숫자는 최대 218 개일 수 있습니다. 각 위치에 대한 모든 합법적 인 이동을 열거합니다. 이제 각 이동을 1 바이트로 인코딩 할 수 있습니다.

우리는 여전히 사임을 나타냅니다. 내기 위해 0xFF와 같은 특별한 움직임을 행사할 수 있습니다.

최악의 경우 대신 인간이 플레이하는 일반적인 게임의 평균 케이스 크기 를 최적화하는 데 관심이 추가 됩니다. (문제의 경우 어느 것을 말하지 않습니다.)

이동 시퀀스의 경우 좋은 체스 엔진이 각 위치에서 이동을 생성합니다. 퀄리티 순위에 따라 순서대로 k 개의 가능한 이동 목록을 생성합니다. 일반적으로 무작위 동작보다 좋은 동작을 더 자주 선택 목록의 각 위치에서 사람들이 '좋은'동작을 선택할 확률에 대한 매핑을 배워야합니다. 이러한 확률 (일부 인터넷 체스 데이터베이스의 게임 코퍼스 기반)을 사용하여 산술 코딩으로 동작을 인코딩합니다 . (디코더는 동일한 체스 엔진과 매핑을합니다.)

시작 위치의 경우 ralu의 접근 방식이 적용됩니다. 확률에 따라 선택에 부여를 부여하는 방법이 소유권 산술 코딩으로이를 다듬을 수 있습니다. 예를 들어, 종종 무작위가 아닌 서로를 방어하는 구성에 나타납니다. 그 지식을 통합하는 쉬운 방법을 찾기가 더 어렵습니다. 한 가지 아이디어 : 위의 이동 인코딩을 대신 사용하여 표준 개방 위치에서 시작하여 원하는 보드에서 끝나는 시퀀스를 찾으십시오. (마지막 위치에서 조각의 거리를 합한 것과 같은 휴리스틱 거리로 A * 검색을 시도 할 수 있습니다.) 이것은 이동 순서를 과도하게하는 것과 체스 플레이를 활용하는 지정 효율성의 비 효율성을 교환합니다. 지식.

어떤 통계를 수집하지 않고 얼마나 많은 비용을 내고 효과를 얻을 수 있습니다. 그러나 모든 움직임의 시작점은 이미 여기에서 대부분의 제안을 할 생각합니다. 산술 코딩에는 움직임 당 정수 비트 수가 필요하지 않습니다.

초기 위치가 인코딩 된 후 단계 인코딩의 하위 문제를 공격합니다. 접근 방식은 단계의 "연결된 목록"을 만드는 것입니다.

게임의 각 단계는 "이전 위치-> 새 위치"쌍으로 인코딩됩니다. 당신은 체스 게임이 시작될 때의 초기 위치를 알고 있습니다. 단계 단계 목록을 순회하면 X가 이동 한 후 상태에 도달 할 수 있습니다.

각 단계를 인코딩 후 시작 위치를 인코딩하는 데 64 개의 값이 필요합니다 (보드의 64 개 사각형의 경우 6 비트 -8x8 사각형), 끝의 경우 6 비트가됩니다. 각면의 1 이동에 대해 16 비트입니다.

주어진 게임을 인코딩하는 데 필요한 공간의 양은 이동 횟수에 비례합니다.

10 x (흰색 이동 수 + 검은 색 이동 수) 비트.

업데이트 : 승격 된 폰의 강화 인 합병증. -특수 비트가 필요할 수 있습니다. (폰 승격은 극히 드물기 때문에 공간을 절약하기 위해 회색 코드를 사용합니다).

업데이트 2 : 끝 위치의 전체 좌표를 인코딩 할 필요가 없습니다. 대부분의 경우 이동중인 조각은 X 개 이하로 실행할 수 있습니다. 예를 들어 폰은 주어진 지점에서 최대 3 개의 이동 옵션을 수 있습니다. 각 조각 유형에 대한 최대 이동 수를 인식하여 "대상"인코딩에 대한 비트를 절약 할 수 있습니다.

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

따라서 검은 색 또는 흰색의 이동 당 공간은

초기 위치 + (이동되는 사물의 유형에 따라 가변 비트 수)에 대해 6 비트.

어제 밤 에이 질문을 봤는데 흥미 로웠 기 때문에 침대에 앉아 해결을 생각했습니다. 내 최종 답변은 int3와 매우 유사합니다.

기본 솔루션

표준 체스 게임을 실행하고 규칙을 인코딩하지 않는다고 가정하면 (예 : White가 항상 진행됨) 각 조각이 만드는 동작 만 인코딩 많은 비용을 절약 할 수 있습니다.

총 32 개의 조각이 필요한 각 이동에서 어떤 색이 움직이는 지 알 수 있으니 걱정할 사각형은 16 개뿐 .이 조각은 이번 턴에 이동하는 4 비트 입니다.

각 조각에는 많고 다양한 방식으로 으로든 열거 할 수 있습니다.

폰 : 4 개 옵션, 2 비트 (1 단계 앞으로, 2 단계 앞으로, 각 대각선 1 개)
루크 : 14 개 옵션, 4 비트 (각으로 방향 최대 7 개)
비숍 : 13 개 옵션, 4 비트 (하나의 대각선에 7 개가있는 경우 다른 대각선에 6 개만 있음)
Knight : 8 가지 옵션, 3 비트
퀸 : 27 개 옵션, 5 비트 (Rook + Bishop)
킹 : 9 가지 옵션, 4 비트 (8 개의 단계 이동 및 캐슬 링 옵션)

승진을 위해 선택할 수있는 4 개의 조각 (Rook, Bishop, Knight, Queen)이 있으므로 해당 이동에 2 비트 를 추가 하여 지정합니다. 다른 모든 규칙은 자동으로 적용됩니다 (예 : en passant).

추가 최적화

8 개 조각을 먼저 한 후 조각 인코딩을 3 비트로 줄인 다음 4 조각에 대해 2 비트 등으로 수 있습니다.

그러나 주요 최적화 는 게임의 각 지점에서 가능한 이동 만 열거 하는 것입니다. Pawn의 움직임 {00, 01, 10, 11}을 추가 1 단계 앞으로, 2 단계 앞으로, 대각선 왼쪽 및 오른쪽으로 저장 가정합니다 . 일부 이동이 불가능한 경우 이번 턴에 인코딩에서 제거 할 수 있습니다.

(모든 동작을 따라 가면서) 우리는 모든 단계의 움직일 게임 상태를 알고 있습니다. 어떤 조각이 움직일 것인지 게임 읽은 후에 우리는 항상 읽어야 할 비트 수를 선택할 수 있습니다. 이 지점에서 폰의 유일한 움직임이 오른쪽으로 오른쪽으로 움직이거나 앞으로 이동하는 것을 인식하면 1 비트 만 읽는다는 것을 알고 있습니다.

요컨대, 각 조각에 대해 위에 있고 비트는 최대 값 입니다. 거의 모든 움직임에 더 많은 수의 옵션과 약간 더 약간의 비트가 있습니다.

각 위치에서 가능한 모든 이동 수를 얻습니다.

다음 이동은 다음과 같이 생성됩니다.

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

무작위로 생성 된 필요를 저장하기위한 최고의 공간 게임을 30-40 개의 이동이 가능하게 평균적으로 약 5 비트 / 이동이합니다. 스토리지를 조립하면 n이 역순으로 생성됩니다.

두성이 높기 때문에 위치를 저장하는 것이 더 어렵습니다. (한 사이트에 최대 9 개의 경우에는 폰이없고 보드에있는 경우 비숍이 반대 색상의 사각형에 있음) 그러나 일반적으로 나머지 사각형 위에있는 조각을 조합하여 저장하고 사용할 수 있습니다.)

편집하다 :

무브 저장의 포인트는 무브 강화 만 저장하는 것입니다. Kc1-c2를 저장하고이 정보를 줄이는 대신 결정적 movegenerator (position)에서 생성 된 이동을 추가해야합니다.

움직일 때마다 크기 정보를 추가합니다.

num_of_moves = get_number_of_possible_moves(postion) ;

이 수는 없습니다.

정보 풀 생성은

n=n*num_of_moves+ index_current_move

특별한

최종 위치에서 사용 가능한 이동이 하나만있는 경우 이전에 수행 한 강제 이동 수로 저장합니다. 예 : 시작 위치에 각각 1 개의 강제 이동 (2 개 이동)이 있고 하나의 이동 게임으로 저장됩니다.

정보 풀에 저장하는 예

우리가 시작 위치를 알고 있고 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

그리고 우리는 7 개의 가능한 움직임이있는 위치에 우리를 가져다주는 움직임을 3을 취합니다.

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) 등.

두 사이트에 대해이 값을 곱하면 약 142 비트 인 4634726695587809641192045982323285670400000이됩니다. 가능한 en-passant (en-passant 폰은 8 개 중 하나에있을 수 있음)에 대해 8을 더해야합니다. 이동이있는 사이트의 경우 1 비트입니다. 우리는 142 + 3 + 4 + 1 = 150 비트로 끝납니다.

하지만 이제는 32 개 조각을 가지고있는 보드에서 가지고있는 것을 찾아 보겠습니다.

흑백 폰은 모두 같은 기둥에 있고 서로 마주보고 있습니다. 각 폰은 다른 폰을 향하고 있습니다. 즉, 흰색 폰은 최대 6 개 위가 될 수 있습니다. 이 정보를 56 비트 감소시키는 C (64/8) * C (48/8) 대신 8 * C (6/2)를 가져옵니다.
캐슬 링 가능성도 있습니다. 루크가 시작 장소에 그 루크의 캐슬 링 가능성이 없습니다. 그래서 우리는 상상 으로이 루크를 캐슬 링이 가능하고 캐슬 링 비트 4 개를 제거하면 추가 정보를 추가 위해 보드에 4 개의 사각형을 할 수 있습니다. 따라서 C (56/2) * C (40/2) * 16 대신 C (58/2) * C (42/2)가 3.76 비트가 감소 (거의 4 비트).
en-passant : 8 개의 위치 en passant possibilites 중 하나를 사용할 때, 우리는 black pawn의를 알고 정보 용 redindancy를 줄입니다 (흰색 이동이고 3 번째 pawn en-passant가 있으면 검은 색 폰이 c5에 있고 흰색 폰이 c2, c3 또는 c4) C (6/2)를 삽입하면 3 개가 있고 2.3 비트가 추가되었습니다. 우리가 수행 할 수있는 기능 (3 가능성-> 왼쪽, 오른쪽, 가지 다)과 함께 whit en-passant 번호를 저장하면 약간의 추가 기능, en-passant를 사용할 수있는 폰의 가능성을 알고 있습니다. (예를 들어 엉 passant 예에서 c5의 whit black on 왼쪽, 오른쪽 또는 둘 다에있을 수 있습니다. 한 사이트에 있으면 2 * 3 (psissibilites를 저장하는 데 3 개, 7 또는 6 랭크에 검은 폰에 대해 2 개의 이동 가능)) C (6/2)를 삽입하고 우리는 1.3 비트로 밖으로 줄입니다. 당신은 2.3 + 1.3 = 3.6 비트로 수 있습니다.
bishops : bisop은 오 포스 타이트 사각형에만있을 수 있습니다. 이렇게하면 각 사이트에 대해 설교 성이 1 비트 씩씩 있습니다.

요약하면 체스 위치를 저장하기 위해 150-56-4-3.6-2 = 85 비트 가 필요합니다.

(그러나 누군가가 긴 게시물이 유용하다고 생각한다면 나중에 논의 할 것입니다) 그리고 고려하여 고려한 승진과 고려가 있다면 아마 그다지 많지 않을 것입니다.

대부분의 사람들은 보드 상태를 인코딩했지만 이동 자체에 .. 비트 인코딩 설명이 있습니다.

조각 당 비트 :

Piece-ID : 한 면당 16 개 조각을 이미지하기위한 최대 4 비트. 흰색 / 검정을 유추 할 수 있습니다. 조각에 정의 된 순서가 있습니다. 조각의 수가 각 2의 제곱 아래로 떨어지면 나머지 조각을 설명하는 데 더 약간의 비트를 사용합니다.
Pawn : 첫 번째 이동에 3 가지 가능성이 있으므로 +2 비트 (1 개 또는 2 개의 사각형 앞으로 이동, 통과) 이후 이동은 2 개씩 앞으로 이동하는 것을 허용하지 않습니다 +1 비트이면 충분합니다. 승진은 폰이 마지막 순위에 도달했을 때를 기록 할 수 있습니다. 폰이 승격 된 기기에있는 경우에는 4 개의 주요 부분 중 어느 것이 승격이있는 것이 또 다른 2 개의 비트를 예상합니다.
Bishop : 사용되는 대각선의 경우 +1 비트, 대각선을 따른 거리의 경우 최대 +4 비트 (16 가지 가능성). 길이는 조각이 해당 대각선을 따라 설치된 최대 가능한 최대 가능한를 추론 할 수 있으므로 더 짧은 거리이면 더 약간의 비트를 사용합니다.
기사 : 8 개 이동 가능, +3 비트
루크 : 수평 / 수직의 경우 +1 비트, 선을 따른 거리의 경우 +4 비트.
킹 : 8 개의 이동 가능, +3 비트. 캐슬 링을 '불 심각한'움직임으로 표시하십시오. 캐슬 링은 왕이 1 순위에있을 때만 가능합니다.이 움직임을 킹을 '뒤로'이동 지시 지시 (예 : 보드 외)로 인코딩하십시오.
퀸 : 8 개의 가능한 방향, +3 비트. 선 / 대각선을 따라 거리에 대해 최대 +4 비트 추가 (비숍의 경우와 같이 대각선이 더 짧은 경우 더 적음)

모든 조각이 보드에 가정 할 때, 다음은 이동 당 비트입니다. Pawn- 첫 번째 이동시 6 비트, 이후 5 비트. 승진하는 경우 7입니다. Bishop : 9 비트 (최대), Knight : 7, Rook : 9, King : 7, Queen : 11 (최대).

일반적인 체스 게임에 가장 효율적인 인코딩을 제공하는 것이 문제입니까? 아니면 최악의 경우 인코딩이 가장 짧은 것입니까?

후자의 경우 가장 효율적인 방법은 또한 가장 불투명합니다. 가능한 모든 쌍 (초기 보드, 합법적 인 이동 순서)의 열거를 생성합니다. -마지막 전당포 이동 또는 짓 규칙 이후 50 번 이동은 재귀 적입니다. 그런 다음이 유한 시퀀스의 위치 보안은 가장 최악의 경우 인코딩을 제공하지만 일반적인 경우에도 동일하게 긴 인코딩을 제공하며 계산하는 데 매우 비쌉니다. 가능한 가장 긴 체스 게임은 5000 개 이상의 이동해야하며, 일반적으로 각 플레이어에게 각 위치에서 20 ~ 30 개의 이동이 가능합니다.

위의 인코딩 동작에 대한 Henk Holterman의 제안에 설명 된대로 열거 개념을 적용하여 다루기 쉬운 솔루션을 할 수 있습니다. 내 제안 : 최소한 짧고 합리적으로 다루기.

위치 유 된 사각형 (점유 점유 점유 점유 점유있는 조각 64 비트와 각 점유 된 사각형에있는 조각 목록 (폰은 3 비트, 다른 것은 4 비트) : 시작에 190 비트가 제공됩니다. 보드에 32 개 이상의 조각이있을 수 있기 때문에 점유 매트릭스 위치와 같은 인코딩이 포함 된 공통 보드 목록과 같은 것입니다 (예 : 공통 보드 목록의 보드 목록의 보드 33 세트 비트).
누가 먼저 움직 일지 1 비트
Henk의 제안에 따라 코드 이동 : 일반적으로 흰색 / 검정 이동 쌍당 10 비트이지만, 플레이어가 대체 이동이없는 경우 일부 이동은 0 비트를 사용합니다.

이것은 일반적인 30 개 이동을 코딩하는 데 490 비트를 제안하며 일반적인 게임에 대해 합리적으로 게임 표현입니다.

마지막 폰 이동 또는 배치 규칙 이후 세 번째 반복 위치 및 50 개 이하의 움직임을 인코딩하는 방법 : 과거를 인코딩하면 마지막 폰 이동 또는 로봇으로 돌아갑니다. 이 규칙의 적용 여부를 수있는 충분한 정보가 있어야합니다. 전체 게임 기록이 필요하지 않습니다.

보드의 위치는 7 비트로 정의 할 수 있습니다 (0-63 및 더 이상 보드에 없음을 지정하는 1 값). 따라서 보드의 모든 조각에 대해 위치를 지정하십시오.

32 개 * 7 비트 = 224 비트

편집 : Cadrian이 지적했듯이 ... 우리는 또한 '승진 전당포에서 여왕으로'케이스가 있습니다. 어떤 폰이 승격하도록 표시하기 위해 끝에 추가 비트를 추가하는 것이 좋습니다.

승격 된 모든 폰에 대해 승격 된 폰의 고급을 5 비트와 목록의 끝인 경우 11111로 224 비트를 사용합니다.

따라서 최소 케이스 (프로모션 없음)는 224 비트 + 5 (프로모션 없음)입니다. 승격 된 모든 폰에 대해 5 비트를 추가합니다.

편집 : 얽히고 설킨 개구리가 지적했듯이, 우리는 그것이 누구의 차례인지 나타냅니다. 내기 위해 끝에 또 다른 비트가 필요합니다; ^)

실행 길이 인코딩을 사용합니다. 일부 조각은 고유하거나 두 번만 존재하는 그 뒤의 길이를 생략 할 수 있습니다. cletus와 사용할 수 13 개의 고유 상태가 필요합니다. 조각을 인코딩하는 데 니블 (4 비트)을 사용할 수 있습니다. 초기 보드는 다음과 가변적입니다.

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

8 + 2 + 4 + 2 + 8 니블 = 24 니블 = 96 비트로 남습니다. 16 개를 니블로 인코딩 할 수는 없지만 "Empty, 0"은 의미가 "0"을 "16"으로 취급 할 수 있습니다.

"Pawn, 1, Empty, 16, Empty, 16, Empty 16, Empty, 15"= 10 nibbles = 40 bits입니다.

최악의 경우는 각 조각 사이에 빈 사각형이있을 때입니다. 그러나 조각을 인코딩하려는 경우 16 개 값 중 13 개만 필요 다른 값을 사용하여 "Empty1"이라고 말할 수 있습니다. 그런 다음 64 니블 == 128 비트가 필요합니다.

움직임의 경우 조각에 3 비트 (흰색이 항상 먼저 이동한다는 사실에 의해 색상이 지정됨)에 새 위치에 대해 5 비트 (0..63)를 더한 값 = 움직임 당 1 바이트가 필요합니다. 대부분의 경우 한 조각 만 유전자가 있기 때문에 이전 위치가 필요하지 않습니다. 이상한 경우에는 사용하지 않는 단일 코드 (조각을 인코딩하는 데 7 개의 코드 만 필요)를 다음 이전 위치에 5 비트, 새 위치에 5 비트를 사용합니다.

이렇게하면 캐슬 링을 13 바이트로 인코딩 할 수 있습니다 (내가 의도 한 바를 말할 수있는 Rook쪽으로 King을 사용할 수 있음).

[편집] 스마트 한 것을 허용하는 경우 초기 설정에 0 비트가 필요합니다 (어떤 식 으로든 인코딩 할 필요가 없기 때문입니다. 정적 임) + 이동 당 1 바이트.

[EDIT2] 폰 변환을 남깁니다. 폰이 마지막 행에 도달하면 "변형"이라고 말한 다음 교체 할 조각에 대해 3 비트를 추가 할 수 있습니다. (퀸을 사용할 수 없습니다. 폰을 다른 교체 할 수 없습니다. 그러나 왕).

책과 종이에 게임을 인코딩하는 것처럼 모든 조각에는 기호가 있습니다. "합법적 인"게임 시작이 먼저 이동합니다. 흰색 또는 검은 색 색을 등록 할 필요가 없습니다. 이동 횟수를 세어 누가 이동했는지 확인하세요. 또한 모든 움직임은 '종료 위치'가 모호함을 이미지 할 수있는 최소한의 기호 (0 일 수 있음)로 축소 (조각, 종료)로 인코딩됩니다. 게임의 길이는 이동 횟수를 결정합니다. 모든 단계에서 시간 (마지막 이후)을 분 단위로 인코딩 할 수도 있습니다.

조각의 인코딩은 추가에 기호를 할당하거나 (총 32 개) 클래스에 기호를 할당하여 수행 할 수 있고 끝 위치를 사용하여 조각이 이동 된 부분을 이해합니다. 예를 들어, 폰은 6 개의 가능한 종료 위치를 가지고 있습니다. 그러나 평균적으로 매 턴마다 몇 명만 사용할 수 있습니다. 통계적으로 끝 위치 별 인코딩이 시나리오에 가장 적합 할 수 있습니다.

인코딩 인코딩이 계산 신경 과학 (AER)의 스파이크 트레인에 사용됩니다.

단점 : 연결 목록을 순회하는 것처럼 현재 상태에 도달하고 하위 집합을 생성하려는 전체 게임을 재생해야합니다.

64 개의 가능한 보드 위치가 있으므로 위치 당 6 비트가 필요합니다. 32 개의 초기 조각이 있으므로 지금까지 총 192 비트가 있습니다. 여기서 6 비트마다 주어진 조각의 위치를 나타 있는지. 어느 쪽인지 필요가 없습니다.

조각이 보드에서 벗어난다면? 글쎄, 우리는 다른 조각과 같은 위치에 조각을 놓아 보드에서 벗어 났던 것입니다. 사실상 불법입니다. 그러나 우리는 또한 첫 번째 작품이 보드에 올지 여부도 괜찮습니다. 그래서 우리는 어떤 조각이 첫 번째 조각인지 5 비트를 추가합니다 (32 개 가능성 = 첫 번째 조각을 5 비트). 그런 다음 보드에서 벗어난 다음 조각에 해당 지점을 사용할 수 있습니다. 총 197 비트가됩니다. 보드에 연기 하나의 조각이 작동합니다.

그 다음 우리는 198 비트 가 될 차례 인 1 비트가 필요합니다 .

폰 프로모션은 어떻습니까? 폰당 3 비트를 추가하고 42 비트를 추가하여 나쁜 방법으로 할 수 있습니다. 하지만 대부분의 경우에는 승격되지 않습니다.

따라서 보드에있는 모든 폰에 대해 비트 '0'은 승격되지 않습니다. 폰이 보드에 우리는 조금도 필요하지 않습니다. 그런 다음 그가 승진 한 가변 길이 비트를 사용할 수 있습니다. 대부분의 경우 여왕이 될 것 "10"은 여왕을 의미 할 수 있습니다. "110"은 루크, "1110"은 비숍, "1111"은 나이트를 의미합니다.

16 개의 폰이 모두 발생하기 때문에 승격되지 않았기 때문에 초기 상태는 198 + 16 = 214 비트 를 사용합니다. 2 명의 명의 승격 된 폰이있는 최종 게임은 198 + 4 + 4와 같은 값을 수 있습니다. 즉, 승격되지 않은 4 개의 폰과 2 개의 퀸 폰 ( 총 206 비트)을 의미 합니다. 꽤 튼튼한 것입니다!

===

다른 사람들이 지적했듯이 Huffman 인코딩은 다음 단계가 될 것입니다. 수백만 개의 게임을 관찰하면 각 조각이 특정 사각형에 가능성이 더 많음이 있습니다. 예를 들어, 대부분의 경우에는 직선으로 유지되거나 하나는 왼쪽 / 오른쪽으로 유지됩니다. 왕은 일반적으로 홈베이스에 있습니다.

즉, 인코딩의 위치에 대해 Huffman 인코딩 체계를 고안합니다. 폰은 6 비트가 아닌 평균 3-4 비트 만 가져갈 것입니다. 킹도 몇 비트를 가져와야합니다.

또한이 계획에서 가능한 위치로 "취득"을 포함하십시오. 이것은 또한 캐슬 링을 매우 견고하게 처리 할 수 있습니다. 각 루크와 킹은 추가 "원래 위치, 이동"상태를 사용합니다. 또한 이런 방식으로 폰에서 패전트를 인코딩 할 수 있습니다.- "원래 위치, 패전트 가능".

데이터가 충분하면 방법을 사용하면 정말 좋은 결과를 얻을 수 있습니다.

Huffman 인코딩 을 사용합니다 . 이것의 배후에있는 이론은-모든 체스 게임에는 많이 움직일 수있는 말들이 있고 많이 움직이지 조기 제거되는 말들이있을 것입니다.시작 위치에 이미 일부 조각이 있으면 더 좋습니다. 사각형의 경우도 마찬가지입니다. 일부 사각형은 모든 동작을 볼 수있는 반면, 일부는 별 영향을받지 않습니다.

따라서 나는 두 개의 Huffman 테이블을 사용할 수 있습니다. 하나는 조각 용이고 다른 하나는 사각형 용입니다.실제 게임을 생성합니다. 나는 모든 조각 정사각형 쌍에 대해 하나의 큰 테이블을 누릴 수있는 것 같은 조각이 같은 정사각형에서 다시 움직이는 인스턴스 가지 않기 때문에 매우 비효율적이라고합니다.

모든 조각에는 할당 된 ID가 있습니다. 32 개의 다른 조각이 있기 때문에 조각 ID로 5 비트 만합니다.조각 ID는 게임마다 변경되지 않습니다. 6 비트가 필요한 정사각형 ID도 마찬가지입니다.

Huffman 트리는 순서대로 순회 될 때 각 노드를 기록하여 인코딩됩니다 (즉, 먼저 노드가 출력 된 다음 해당하는 노드에서 오른쪽으로). 모든 노드에는 리프 노드인지 노드인지는 지정하는 1 비트가 있습니다.리프 노드 인 경우 ID를 제공하는 비트가 뒤 그런.

시작 위치는 설치의 조각 위치 쌍으로 지정됩니다. 그 후 모든 이동에 대해 하나의 조각 위치 쌍이 있습니다. 두 번의 언급 된 첫 번째는 조각을 끝으로 시작 위치 설명 자의 끝까지 (및 이동 설명 자의 시작) 있습니다.2 개의 추가 비트가 추가 될 것이지만, 조각 ID는 변경되지 않습니다.

게임이 시작될 때 폰이 승격 가능성을 설명하기 위해 허프만 트리와 데이터 사이에 "프로모션 테이블"도 있습니다. 처음에는 업그레이드되는 폰 수를 지정하는 4 비트가 있습니다. 그런 다음 각 폰에 대해 허프만 인코딩 ID와 그것이 무엇인지를 지정하는 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 기반 ID를 제공 할 수 있습니다. 동일한 ID가 모든 조각에 추가 총 21 개의 다른 ID가 있습니다. (여왕은 21 개의 가능한 이동 옵션을 사용할 수 있습니다.)필드 대신 허프만 테이블에 기재십시오.

그러나 이것은 원래 상태를 유지하는 데 어려움을 제공합니다. 조각의 동작을 생성하여 각 조각을 제자리에 놓을 수 있습니다.이 경우 초기 상태의 끝과 이동의 시작을 어떻게해야하는지 표시해야합니다.

또는 압축되지 않은 6 비트 정사각형 ID를 사용하여 배치 할 수 있습니다.

이것이 전체적인 크기 감소를 지 여부-모르겠습니다. 아마도 약간의 실험이 필요합니다.

추가 2 : 하나 더 특별한 경우. 게임 상태는 다음으로 이동하는 사람을 구별하는 것이 중요합니다. 이를 위해 끝에 하나 더 추가하십시오. :)

[질문을 제대로 읽은 후] 초기 위치 ( "법적"의 가능한 정의)에서 모든 법적 위치에 도달 할 수있는 편집 할 수있는 가정하면 모든 위치는 시작부터 이동 순서로 표현할 수 있습니다. 비표준 위치에서 시작하는 플레이 스는 필요한 작업의 동작, 카메라를 켜는 스위치, 동작으로 표현할 수 있습니다.

따라서 초기 보드 상태를 단일 비트 "0"이라고합시다.

어떤 위치에서든 이동은 정사각형에 번호를 매기고 이동 순서를 (시작, 끝) 순으로 할 수 있고 기존의 2 제곱 점프는 캐슬 링을 나타냅니다. 보드 위치와 규칙이 항상 이미 있기 때문에 불법 이동을 인코딩 할 필요가 없습니다.카메라를 켜는 플래그는 특수 대역 내 이동으로 표현하거나 대역 외 이동 번호로 더 현명하게 표현할 수 있습니다.

양쪽에 24 개의 오프닝 무브가 있고, 5 비트에 맞습니다. 이동은 항상 열거 가능하게 증가하거나 확장 할 수 있습니다.계산하지 단어 7 비트 위치가 드물다고 생각합니다.

이 시스템을 사용하면 100 개의 반 동작 게임을 약 500 비트로 인코딩 할 수 있습니다. 그러나 시작되는 책을 사용하는 것이 현명 할 수 있습니다. 백만 개의 시퀀스가 존재합니다. 그러면 이니셜 0은 표준 보드에서 시작을 1에서 20 비트 번호는 해당 시작 시퀀스에서 시작을 나타냅니다.다소 오프닝이있는 게임은 예를 들어 20 개 반 동작 또는 100 비트로 단축 될 수 있습니다.

이것은 가능한 가장 큰 압축은 (개봉 책) 이미 체스 모델을 가지고 있다면 구현하기가 매우 쉬울입니다.

더 적은 비용으로 임의의 순서가 아닌 가능성에 따라 이동 순서를 지정하고 가능한 시퀀스를 더 약간의 비트로 인코딩해야합니다 (예 : Huffman 토큰 사용).

계산 시간이 문제가되지 않는 경우 결정 가능한 위치 생성기를 사용하여 주어진 위치에 고유 한 ID를 할당 할 수 있습니다.

주어진 위치에서 먼저 결정 론적 매너에서 가능한 위치의 수를 생성합니다. 예를 들어 왼쪽 하단에서 오른쪽 상단으로 이동합니다. 이는 다음 동작에 필요한 비트 수를 결정하며 일부 상황에서는 1만큼 작을 수 있습니다.그런 다음 이동이 이루어지면 해당 이동에 대한 ID 만 저장합니다.

승진 및 기타 규칙은 예를 들어 퀸, 루크, 비숍과 같이 결정적인 방식으로 처리되는 한 유효한 이동으로 처리됩니다.

초기 위치는 가장 어렵고 약 2 억 5 천만 개의 가능한 위치를 생성 할 수 있습니다 (내 생각에).이 위치는 이동을 결정하기 위해 약 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 이동 목록'은 체크 상황을 변경하는 유효한 이동 만 반환합니다.

대부분의 답변은 3 배 반복을 간과했습니다. 안타깝게도 3 겹 반복의 경우 지금까지 플레이 한 모든 포지션을 저장해야합니다 ...

이 질문은 우리가 이동 목록에서 구성 할 수있는 한 (표준 시작 위치가있는 경우) 실제로 위치를 지정해야하는 경우에 효율적인 방식으로 저장해야합니다. PGN을 최적화 할 수 있습니다. Bellow는 간단한 계획입니다.

보드에는 64 개의 사각형이 있습니다. 64 = 2 ^ 6. 12 비트를 사용하는 각 이동의 초기 및 마지막 사각형 만 저장하면 (승진은 나중에 다룹니다). 이 계획은 이미 플레이어의 이동, emphassant, 조각 공사, 캐슬 링 등을 포함합니다. 이것들은 이동 목록을 재생하여 구성 할 수 있습니다.

승진을 위해 우리는 "이동 N 승격에서 조각 XYZ"라는 별도의 벡터를 배열 할 수 있습니다. (int, byte)의 벡터를 사용할 수 있습니다.

(To, From) 벡터도 최적화하려는 유혹이 있습니다. (To, From) 벡터 중 상당수가 체스에서는 불가능하기 때문입니다. 예. e1에서 d8 등으로의 이동은 없을 것입니다. 그러나 나는 어떤 계획도 생각할 수 없습니다. 추가 아이디어는 가장 환영받습니다.

나는 오랫동안 오랫동안 (+ -2 시간) 생각했습니다. 그리고 분명한 답은 없습니다.

가정 :

시간 상태 무시 (플레이어가 시간 제한을 사용하지 않음 즉시 플레이하지 강제로 무승부 할 수 있음)
언제 게임을 했습니까?!? 시간이 지남에 따라 규칙이 변경 되었기 때문에 중요합니다 (이후 현대 게임은 게임이라고 가정합니다 ...) 예를 들어 죽은 폰 규칙을 참조하십시오 (위키피디아에는이 있습니다. 매우 유명한 문제가 있습니다). 시간을 거슬러 올라가는 행운을 빕니다 감독은 천천히 움직이고 주사위를 사용했습니다. 롤.

... 그래서 최신의 현대 규칙입니다. 첫 번째는 반복에 관계없이 반복 제한을 이동합니다.

-C 25 바이트 반올림 (64b + 32 * 4b + 5b = 325b)

= 64 비트 (무언가 / 무) + 32 * 4 비트 [1bit = color {black / withe} + 3bit = 조각 유형 {King, Queen, Bishop, kNight, Rook, Pawn, MovedPawn} NB : Moved pawn ... 예 를 들어 이전 턴에서 마지막으로 이동 한 폰이었던 경우 'en passant'가 가능함을 나타냅니다. ] 실제 상태에 대해 +5 비트 (누가 차례, en passant, 루킹 가능성 여부)

여태대로 그런대로 잘됐다. 가변 길이와 프로모션이있을 것입니다!?

이제 다음 규칙은 플레이어가 추첨에 응모 할 때만 적용됩니다. 자동이 아닙니다! 90 개의 동작을 수행하거나 무승 구매하지 않는 폰 이동이 가능하다고 생각하십시오! 모든 동작을 기록하고 사용할 수 있어야 함을 의미합니다.

-D 위치 반복 ... 예 : 언급 언급 한 보드 상태 (C 참조) 여부 ... (FIDE 규칙에 대한 다음 참조) -E 포획 또는 폰 이동없이 50 허용이라는 복잡한 문제를 남깁니다. 카운터가 필요합니다 ...하지만.

그래서 어떻게 처리합니까? ... 글쎄요 정말 방법이 없습니다. 어느 플레이어도 그리기를 사용하지 않습니다. 이제 E의 경우 카운터로 충분할 수 있고 여기에 트릭이 있고 FIDE 규칙 (http://www.fide.com/component/handbook/?id=124&view=article)도 읽을 수 없습니다. ... 루킹 능력 상실은 어떻습니까? 반복인가요? 나는 명확하지 않고 명확하지 않은 주제입니다.

그래서 여기에 인코딩을 시도하는 것 복잡하거나 정의되지 않은 두 가지 규칙이 있습니다. 건배.

따라서 게임을 진정으로 인코딩하는 유일한 방법은 처음부터 모든 것을 기록하는 것입니다. 그러면 "보드 상태"질문과 충돌 (또는 또는 자격이 있습니까?)됩니다.

이 도움이되기를 바랍니다 ... 수학이 너무 많지 않습니다. :-) 어떤 질문이 그렇게 쉽지 않고 해석이나 사전 지식이 개방되어 있다는 것이 너무 어렵습니다. 웜 캔을 너무 많이 열었 기 때문에 인터뷰를 고려할 사람은 없습니다.

Yacoby 솔루션의 시작 위치에서 가능한 개선

법적 지위는 각 색상의 조각이 16 개 초과하지 않습니다. 64 개의 정사각형에 최대 16 개의 검은 색 조각과 16 개의 흰색 조각을 배치하는 방법의 수는 약 3.63e27입니다. Log2 (3.63e27) = 91.55. 즉, 모든 조각의 위치와 색상을 92 비트로 인코딩 할 수 있습니다. 이는 위치의 경우 64 비트보다 작으며 Yacoby 솔루션에 필요한 색상의 경우 최대 32 비트입니다. 인코딩이 복잡해지면서 최악의 경우 4 비트를 절약 할 수 있습니다.

반면에 5 개 이상의 조각이 누락 된 위치의 경우 크기가 증가합니다. 하지만 위치는 모든 위치의 4 % 위치에 있습니다.

이것은 완전한 솔루션으로 이어집니다

위의 방법에 따라 조각의 위치와 색상을 인코딩하십시오. 92 비트 .
각 조각의 유형을 지정하십시오 Huffman 코드 : pawn : '0', rook : '100', knight : '101', bishop : '110', queen : '1110', king : '1111'을 사용하십시오. 전체 조각 세트에 대해 (16 * 1 + 12 * 3 + 4 * 4) = 68 비트가 됩니다. 전체 보드 위치는 최대 92 + 68 = 160 비트로 인코딩 할 수 있습니다 .
추가 게임 상태 추가 : 턴 : 1 비트, 어떤 캐슬 링이 가능 지 : 4 비트, "en passant"가능 : 최대 4 비트 (1 비트는 케이스를 3 비트는 어느 것을 나타냄). 시작 위치는 = 160 + 9 = 169 비트로 인코딩됩니다.
이동 목록의 경우 주어진 위치에 대해 가능한 모든 이동을 열거하고 이동 위치를 목록에 저장합니다. 이동 목록에는 모든 특수 사례 (캐슬 링, en passant 및 사임)이 포함됩니다. 가장 높은 위치를 저장하는 데 필요한만큼만 비트를 사용하십시오. 평균적으로 이동 당 7 비트를 초과하지 않습니다 (평균 16 개 가능한 조각 및 조각 당 8 개의 합법적 인 이동). 어떤 경우에는 강제로 이동하면 1 비트 만 필요합니다 (이동 또는 사임).

보드에는 32 개의 조각이 있습니다. 각 조각에는 위치가 있습니다 (64 사각형 중 하나). 따라서 32 개의 양의 정수가 필요합니다.

64 개의 포지션이 6 비트에 있다고 생각하지 않을 것입니다. 나는 몇 개의 깃발을 위해 마지막 비트를 보관할 것입니다 (드롭 된 조각, 여왕의 폰)

cletus 의 대답은 좋지만 그는 누구의 차례인지 인코딩하는 것을 잊었습니다. 현재 상태의 일부는 해당 상태를 사용하여 검색 알고리즘 (예 : 알파-베타 파생물)을 구동하는 경우 필요합니다.

나는 체스는 선수, 또 하나의 코너 케이스가 믿습니다. 얼마나 많은 움직임이 반복되는지입니다. 각 플레이어가 같은 동작을 세 번하면 게임은 무승부입니다. 해당 정보를 상태에 저장해야합니다. 세 번째 반복 후에는 상태가 이제 터미널이되기 때문입니다.

더 많은 사람들이 언급했듯이 32 개 조각에 대해 어떤 사각형이 존재하는지, 보드에 있는지에 따라 32 * (log2 (64) + 1) = 224 비트가 있습니다.

그러나 비숍은 검은 색 또는 흰색 사각형 만 차지할 수 있으므로 위치에 대해 log2 (32) 비트 만 필요하며 28 * 7 + 4 * 6 = 220 비트가됩니다.

그리고 폰은 뒤에서 시작하지 않고 앞으로 만 사용할 수 있기 때문에 56 개에만있을 수 있습니다.이 제한을 사용하여 폰에 필요한 비트 수를 사용할 수 있습니다.

보드에는 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 비트)입니다.

각 조각은 4 비트 (폰 투 킹, 6 가지 유형), 블랙 / 화이트 = 12 개 값으로 표현 될 수 있습니다.

보드의 사각형 각은 6 비트 (x 좌표, y 좌표)로 수 있습니다.

초기 위치에는 최대 320 비트 (32 개, 4 + 6 비트)가 필요합니다.

이후의 각 이동은 16 비트 (from-position, to-position, piece)로 표현 될 수 있습니다.

Castling은 이중 이동 추가 추가 16 비트가 필요합니다.

Queened 폰은 4 비트 중 4 개의 예비 값 중 하나로 표현 될 수 있습니다.

계산을 자세히 수행하지 32 * 7 비트 (사전 정의 된 조각 배열) 또는 64 * 4 비트 (사전 정의 사각형 할당)를 저장하는 것과 비교하여 첫 번째 이동 후 공간을 절약하기 시작합니다.

양쪽에서 10 번 이동 한 후 필요한 최대 공간은 640 비트입니다.

...하지만, 각 조각을 고유하게 다시 말하지만 (5 비트) 퀸드 폰을 표시하기 위해 6 번째 비트를 추가하면 각 이동에 대해 조각 ID + 위치 지정 만 필요합니다. 이것은 계산을 다음과 같이 변경합니다.

초기 위치 = 최대 384 비트 (32 개 조각, 6 + 6 비트) 각 이동 = 12 비트 (위치로, 조각 ID)

그런 다음 각 별에서 10 번 이동 한 후 필요한 최대 공간은 624 비트입니다.

Robert G와 많은 PGN은 표준이고 다양한 도구에서 사용할 수 있기 때문에 사용하는 경향이 있습니다.

그러나 내가 만약 먼 우주 탐사선에있는 체스 AI를 플레이하고 있고 모든 부분이 소중하다면, 그것이 내가 움직임을 위해 할 일입니다. 나중에 초기 상태를 인코딩하는 방법에 대해 알아 보겠습니다.

움직임은 상태를 기록 할 필요가 없습니다. 주어진 주어진 지점에서 합법적 인 움직임이 아니라 상태를 추적 할 수 있습니다. 기록해야 할 모든 움직임은 다양한 법적 대안 중 어느 것이 선택을 선택합니다. 플레이어가 번갈아 가며 움직이기 때문에 플레이어 색상을 기록 할 필요가 없습니다. 플레이어는 자신의 색상 조각만이 있기 때문에 첫 번째 선택은 플레이어가 이동하는 조각입니다 (나중에 다른 선택을 사용하는 대안으로 돌아올 것입니다). 최대 16 개 조각으로 최대 4 비트가 필요합니다. 플레이어가 조각을 잃으면 선택의 수가 없습니다. 또한 특정 게임 상태는 말의 선택을 제한 할 수 있습니다. 왕이 자신을 체크하지 않고 움직일 수없는 선택의 수가 1 개 있습니다. 킹이 체크에 권한 부여 킹을 체크에서 빼낼 수없는 피스는 실행 가능한 선택이 아닙니다.

특정 수의 법적 목적지 만 사용됩니다. 숫자 숫자는 보드 레이아웃과 게임 이력에 따라 크게 다르지만 최대 값과 예상 값을 얻을 수 있습니다. 한 조각이 다른 조각을 통과 할 수 없습니다. 이것은 이동 제한의 큰 원천이 될 것이지만 정량화하기는 어렵습니다. 조각은 보드 고도 수준 높은 수준의 목적지 수를 크게 제한합니다.

우리는 W, NW, N, NE 순서로 줄을 따라 사각형에 번호를 매겨 대부분의 조각의 대상을 인코딩합니다 (검은면은 N). 선은 이동 진행되는 합법적 인 방향으로 가장 먼 정사각형에서 시작하여쪽으로합니다. 방해받지 않는 왕의 경우 이동 목록은 W, E, NW, SE, N, S, NE, SW입니다. 기사의 경우 2W1N으로 시작하여 시계 방향으로 진행합니다. destination 0 은이 순서에서 첫 번째 유효한 목적지입니다.

폰 : 움직이지 않은 폰은 목적지를 2 개 선택할 수 있으므로 1 비트가 필요합니다. 폰이 즉 또는 en passant (디코더가 상태를 추적하고 있기 때문에 가능합니다)를 설치할 수있는 경우 2 개 또는 3 개의 이동 선택이 있습니다. 그 외에는 폰은 하나의 선택 만 할 수있는 비트가 필요하지 않습니다. 폰이 7에있을 때 ^일 순위, 우리는 또한 홍보의 선택에 압정. 폰은 일반적으로 여왕으로 승진 한 후 기사로 승격되기 때문에 선택 항목을 다음과 같이 인코딩합니다.
- 여왕 : 0
- 기사 : 10
- 비숍 : 110
- 루크 : 111
Bishop : 4 비트에 대해 {d, e} {4,5}에 최대 13 개의 대상이있을 수 있습니다.
Rook : 최대 14 개의 목적지, 4 비트.
목적지 : 최대 8 개의 목적지, 3 비트.
Kings : 캐슬 링이 옵션 일 때, 왕은 S로 돌아가서 아래로 최고의 수 없습니다. 이 총 7 개의 목적지를 제공합니다. 나머지 시간 동안 킹은 최대 8 개의 동작을 수행하여 최대 3 비트를 제공합니다.
Queen : 비숍 또는 루크의 선택과 동일하며 총 27 개의 선택 항목 (5 비트)

선택의 수가 항상 2의 제곱이 아니기 때문에 위는 여전히 비트를 사용할 수 있습니다. 선택 항목의 수가 C 이고 특정 항목의 번호 가 c 이고 n = ceil (lg ( C )) (선택 항목을 인코딩하는 데 필요한 비트 수)이라고 가정합니다. 우리는 다음 선택의 첫 번째 비트를 검사하여 사용할 수있는 값을 사용합니다. 0이면 아무 작업도하지 않습니다. 1이고 c + C <2 ⁿ 이면 C 를 c에 추가 합니다. 다수의 샴페인이 역으로 상기 수신한다면 C > = C는 , 감산 C를 과 1 인 경우에, 다음 번호의 첫번째 비트 세트 C <2 ⁿ - C 이면 다음 숫자의 첫 번째 비트를 0으로 설정합니다. 2ⁿ - C <= c < C 이면 아무 작업도 수행하지 않습니다. 이 구성표를 "포화"라고합니다.

인코딩을 단축 할 수있는 또 다른 유형은 강화할 상대 조각을 선택하는 것입니다. 이 기껏해야 할 추가 비트 (현재 플레이어가 움직일 수있는 말의 수에 따라 달라짐)에 대해 고르는 움직임의 첫 번째 부분에 대한 선택의 수를 증가 시켰습니다. 이 선택 기능은보다 많은 적을 선택하는 것입니다. 말은 어떤 추기경에서든 하나의 말과 기사를 합하여 최대 10 개의 공격 말로만 공격 할 수 있습니다. 평균적으로 7 비트를 예상하지만 이동에 대해 총 9 비트를 제공합니다. 이는 종종 합법적 인 목적지가 많기 때문에 여왕의 도시에 유리합니다.

포화 상태에서는 인코딩이 이점을 제공하지 못합니다. 사용되는 초기 상태를 지정하여 두 옵션을 모두 허용 할 수 있습니다. 채도를 사용하지 않는 선택 번호 ( C <= c < ²ⁿ )를 사용하여 게임 중에 옵션을 사용 가능합니다. 모든 시간 C는 우리가 옵션을 설명 수 2의 거듭 제곱이다.

Thomas는 보드 인코딩에 대한 올바른 접근 방식을 가지고 있습니다. 그러나 이는 동작을 저장하는 ralu의 접근 방식과 결합되어야합니다. 가능한 모든 움직임의 목록을 만들고 숫자를 표현하는 데 필요한 비트 수를 기록하십시오. 얼마나 많은 것이 가능한지 알고 있고 얼마나 많은 비트를 읽을 수 있는지 알 수 있으므로 길이 코드가 필요하지 않습니다.

따라서 우리는 조각에 대해 164 비트, 캐슬 링 정보에 대해 4 비트를 얻습니다 (게임 조각을 저장 가정하면, 명명 될 수 있음), en passant 자격 정보에 대해 3 비트-이동이 열을 (ko passant가 가능하지 않을 경우 불가능한 곳에 열을 저장하고 (열이 있어야 함) 저장됩니다.

이동은 일반적으로 5 또는 6 비트를 사용하지만 1에서 8까지 다양 할 수 있습니다.

하나의 추가 단축키 (인코딩이 12 1 비트로 시작하는 경우 (상황 상황-조각도 한쪽에 두 개의 킹이 없음))을 중단하고 보드를 지우고 새 게임을 설정합니다. 다음 비트는 이동 비트입니다.

알고리즘은 각 이동에서 가능한 모든 대상을 결정적으로 열거해야합니다. 목적지 수 :

비숍 2 개, 목적지 13 개 = 26
루크 2 개, 목적지 14 개 = 28
기사 2 명, 목적지 8 개 = 16
퀸, 27 개 목적지
왕, 8 개 목적지

8 개의 발은 모두 최악의 경우 (열거 형) 여왕이 될 수 있으므로 가능한 가장 많은 수의 목적지가 9 * 27 + 26 + 28 + 16 + 8 = 321이됩니다. 따라서 모든 이동의 모든 대상은 9 비트 번호로 열거 될 수 있습니다.

양의 최대 이동 수는 100입니다 (내가 틀리지 않은 경우 체스 플레이어가 아닙니다). 따라서 모든 게임을 900 비트로 기록 할 수 있습니다. 또한 각 조각의 초기 위치는 총 32 * 6 = 192 비트 인 6 비트 번호를 사용하여 기록 할 수 있습니다. "누가 먼저 움직이는 지"기록에 대한 추가 정보. 따라서 900 + 192 + 1 = 1093 비트를 사용하여 모든 게임을 녹화 할 수 있습니다.

보드 상태 저장

내가 생각한 가장 간단한 방법은 너무 먼저 각 조각의 위치를 나타내는 8 * 8 비트 배열을 위해서입니다 (조각이 있으면 1이고 0). 길이가 고정되어 있으므로 종결자가 필요하지 않습니다.

다음은 위치 순서대로 모든 체스 조각을 나타냅니다. 조각 당 4 비트를 사용하면 32 * 4 비트 (총 128 비트)가 필요합니다. 정말 가능합니다.

바이너리 트리를 사용하면 폰을 1 바이트로, 나이트와 루크와 비숍을 3으로, 킹과 퀸을 4로 표현할 수 있습니다. 조각의 색상을 저장해야 할 추가 바이트가 필요합니다. (이것이 틀렸다면 용서하십시오 . 이전 에 Huffman 코딩 을 살펴본 적이 없습니다 .)

폰 : 2
루크 : 4
기사 : 4
비숍 : 4
왕 : 5
여왕 : 5

총계가 주어지면 :

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

고정 된 크기의 비트 세트를 사용하여 28 비트보다 낫습니다.

그래서 내가 가장 좋은 방법은 8 ² + 100 비트 배열 에 저장하는 것입니다.

8*8 + 100 = 164

무브 저장하기
가장 먼저 알아야 할 것은 어떤 조각이 어디로 이동하는지입니다. 보드에 최대 32 개의 조각이있는 사각형을 정수가 아니라 무엇인지 알 수 있습니다. 즉, 가능한 값을 32 개만 입력하면됩니다. 조각.

안타깝게도 왕을 전복하거나 공화국을 형성하는 것과 같은 다양한 특수 규칙이 있습니다 (Terry Pratchett 참조). 따라서 높은 수준의 조각을 저장하기 전에 특수한 이동인지 여부를 단일 비트가 필요합니다.

따라서 필요한 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 비트 범위) 과 유사합니다 .

특수 이동 인 경우
정수 유형과 추가 정보 (예 : 캐슬 링)가 있어야합니다. 필살기 횟수가 기억 나지 않아서 필살기라고 표시하는 것만으로도 괜찮을지도 모른다 (만있는 경우)

초기 보드와 기본 사례에서 다음을 고려하십시오.

체스 프로그램을 사용하여 가능한 모든 동작에 확률을 할당하십시오. 예를 들어 e2-e4의 경우 40 % d2-d4의 경우 20 % 등입니다. 일부 이동이 합법적이지만 해당 프로그램에서 고려되지 않는 낮은 확률을 제공합니다. 산술 코딩을 사용하여 선택한 항목을 저장하십시오. 첫 번째 이동은 0과 0.4 사이, 두 번째 이동에는 0.4와 0.6 사이의 숫자가됩니다.

다른 쪽도 똑같이하십시오. 예를 들어 e2-e4에 대한 응답으로 e7-e5의 확률이 50 % 인 경우 인코딩 된 숫자는 0에서 0.2 사이가됩니다. 게임이 끝날 때까지 반복하십시오. 결과는 매우 작은 범위입니다. 그 범위에 맞는 가장 작은 밑을 가진 이진 분수를 찾으십시오. 그것은 산술 코딩입니다.

이것은 부분 비트 때 인코딩으로 생각할 수 있기 때문에 Huffman보다 낫습니다 (게임이 끝 날림 일부를 전체 비트로 반올림).

결과는 Huffman보다 더 간결해야하며 승진, en passant, 50 규칙 이동 및 기타 세부 사항에 대한 특별한 경우는 없습니다. 이는 체스 평가 프로그램에서 처리되기 때문입니다.

다시 플레이하는 체스 프로그램을 다시 사용하여 보드를 평가하고 각 동작에 확률을 할당합니다. 산술로 인코딩 된 값을 사용하여 실제로 재생 된 동작을 확인합니다. 끝날 때까지 반복하십시오.

체스 프로그램이 충분히 좋다면 2 상태를 사용하여 더 나은 압축을 얻을 수 있습니다. 여기서 확률은 흑백의 움직임을 기반으로 정의됩니다. 약 200 개 이상의 상태 중 가장 극단적 인 경우에는 모든 체스 게임의 전체 세트를 인코딩 실행 가능하지 않습니다.

이것은 Darius가 이미 말하는 것을 말하는 것과 거의 다른 방식으로 산술 코딩이 어떻게 작동하는지에 대한 약간의 예와 기존 체스 프로그램을 사용하여 다음 움직임 (들)의 확률을 평가하는 데 도움이되는 실제 예를 사용하여 .

참고 URL : https://stackoverflow.com/questions/1831386/programmer-puzzle-encoding-a-chess-board-state-throughout-a-game

'IT' 카테고리의 다른 글

목록에있는 개체 수 계산 (0)	2020.08.31
Apple의 Swift에서 노드를 부동으로 변환 (0)	2020.08.31
MySQL은 처음 10 개의 결과를 건너 뛰었습니다. (0)	2020.08.31
ImportError : NUMPY_MKL 이름이 없습니다. (0)	2020.08.31
다중 바인딩에서 1 바인딩에 대한 상수 값을 어떻게합니까? (0)	2020.08.31

현재글프로그래머 퍼즐 : 게임 내내 체스 판 상태 인코딩

내가 바로 로또왕!

볼거리, 영화순위, 행사, 관광, javascript, 무비순위, spring3, jquery, 뮤지컬, 자바, spring, 축제, Java, DVD순위, 여행, 공연, 연극, C#, 놀거리, c++,

Today :
Yesterday :

lottoking

프로그래머 퍼즐 : 게임 내내 체스 판 상태 인코딩

프로그래머 퍼즐 : 게임 내내 체스 판 상태 인코딩

문제

보드 상태 대 게임 상태

캐슬 링

En Passant

프로모션

수가 막히게하다

누구의 차례인가?

두 가지 문제

간단한 내용

가변베이스 인코딩

가변 폭 알파벳

허프만 코딩

국가 차이

조각 위치

결합 된 접근 방식

게임 상태

주석

대수 표기법

결론

정말 큰 조회 테이블 접근 방식

기본 솔루션

추가 최적화

'IT' 카테고리의 다른 글

'IT'의 다른글

티스토리툴바

« 2025/02 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

프로그래머 퍼즐 : 게임 내내 체스 판 상태 인코딩

프로그래머 퍼즐 : 게임 내내 체스 판 상태 인코딩

문제

보드 상태 대 게임 상태

캐슬 링

En Passant

프로모션

수가 막히게하다

누구의 차례인가?

두 가지 문제

간단한 내용

가변베이스 인코딩

가변 폭 알파벳

허프만 코딩

국가 차이

조각 위치

결합 된 접근 방식

게임 상태

주석

대수 표기법

결론

정말 큰 조회 테이블 접근 방식

기본 솔루션

추가 최적화

'IT' 카테고리의 다른 글

'IT'의 다른글

관련글

티스토리툴바