مبرمج اللغز:ترميز لوحة الشطرنج الدولة في جميع أنحاء اللعبة

https://stackoverflow.com/questions/1831386

11-09-2019
|

سؤال

ليس مجرد سؤال ، أكثر من لغز...

على مر السنين, لقد شاركت في عدد المقابلات مع الموظفين الجدد.بخلاف طرح القياسية "هل تعرف X تقنية" الأسئلة, كما حاولت التعود على كيفية التعامل مع المشاكل.عادة, كنت ترسل لهم السؤال عن طريق البريد الإلكتروني قبل يوم من المقابلة ، نتوقع منهم أن التوصل إلى حل في اليوم التالي.

غالبا ما تكون النتائج مثيرة للاهتمام جدا - من الخطأ ، ولكن مثيرة للاهتمام - وأن الشخص لا يزال الحصول على توصيتي إذا أنها يمكن أن يفسر لماذا أخذوا نهج معين.

حتى ظننت أنني كنت رمي واحد من أسئلتي هناك تجاوز سعة مكدس الجمهور.

السؤال: ما هو الأكثر الفضاء-طريقة فعالة يمكنك التفكير في ترميز الدولة من لعبة الشطرنج (أو مجموعة فرعية منها)?بالنظر إلى لوحة الشطرنج مع القطع مرتبة من الناحية القانونية ، ترميز كل هذه الأولية الدولة اللاحقة كافة التحركات القانونية المتخذة من قبل اللاعبين في اللعبة.

أي رمز المطلوبة للإجابة فقط وصف الخوارزمية سوف تستخدمها.

تحرير:باعتبارها واحدة من الملصقات أشارت لم تنظر في الفاصل الزمني بين التحركات.لا تتردد في الاعتبار أيضا اختيارية إضافية :)

EDIT2:فقط لمزيد من التوضيح...تذكر التشفير/فك هو حكم علم.الأشياء الوحيدة التي تحتاج حقا أن تكون مخزنة هي خيارات اللاعب - أي شيء آخر يمكن أن يفترض أن تكون معروفة من قبل التشفير/فك.

EDIT3:سيكون من الصعب اختيار الفائز هنا :) الكثير من الإجابات!

المحلول

تحديث: اعجبني هذا الموضوع كثيرا كتبته الألغاز البرمجة، ومواقع الشطرنج وترميز Huffman. وبعد إذا قرأت من خلال هذا لقد قررت أن فقط طريقة لتخزين حالة اللعبة كاملة هي تخزين قائمة كاملة من التحركات. قراءة على السبب. لذلك أنا أستخدم نسخة مبسطة قليلا من مشكلة تخطيط القطعة.

المشكلة

توضح هذه الصورة موقف البداية الشطرنج. يحدث الشطرنج على لوح 8x8 مع كل لاعب يبدأ بمجموعة متطابقة من 16 قطعة تتكون من 8 بيادق و 2 رواق وفرشتين و 2 أساقفة وملكة واحدة وملك كينغ كما هو موضح هنا:

يتم تسجيل المواقف عموما كحرف للعمود متبوعا بالرقم للصف، لذا فإن الملكة البيضاء في D1. غالبا ما يتم تخزين التحركات تدوين الجبر, ، والتي لا لبس فيها وتحديد عموما فقط الحد الأدنى من المعلومات اللازمة. النظر في هذا الافتتاح:

E4 E5.
NF3 NC6.
…

الذي يترجم إلى:

يتحرك الأبيض بيدق الملك من E2 إلى E4 (إنه القطعة الوحيدة التي يمكن أن تصل إلى E4 وبالتالي "E4")؛
يتحرك الأسود بيدق الملك من E7 إلى E5؛
يتحرك الأبيض فارس (ن) إلى F3؛
يتحرك الأسود فارس إلى C6.
…

يبدو المجلس مثل هذا:

القدرة المهمة على أي مبرمج هي أن تكون قادرة على بشكل صحيح وتحديد المشكلة بشكل لا لبس فيه.

إذن ما هو مفقود أم غامض؟ وهناك الكثير، كما تبين.

الدولة الدولة مقابل الدولة الدولة

أول شيء تحتاج إلى تحديده هو ما إذا كنت تخزين حالة اللعبة أو موضع القطع على اللوحة. ترميز ببساطة مواقف القطع هي شيء واحد ولكن المشكلة تقول "جميع التحركات القانونية اللاحقة". لا تقول المشكلة أيضا شيئا عن معرفة التحركات حتى هذه النقطة. هذا هو في الواقع مشكلة كما سأشرح.

الصدع

انتقلت اللعبة على النحو التالي:

E4 E5.
NF3 NC6.
BB5 A6.
BA4 BC5.

يبدو المجلس كما يلي:

later opening

الأبيض لديه خيار الصدع. وبعد جزء من متطلبات هذا هو أن الملك والجور الروكي ذات الصلة لا يمكن أن يتحرك أبدا، لذلك ستحتاج إلى تخزين الملك أو إما الغراب من كل جانب. من الواضح أنه إذا لم يكنوا في مواقعهم البداية، فقد انتقلوا إلى خلاف ذلك يحتاج إلى تحديد.

هناك العديد من الاستراتيجيات التي يمكن استخدامها للتعامل مع هذه المشكلة.

أولا، يمكننا تخزين 6 بت إضافية من المعلومات (1 لكل روك وملك) للإشارة إلى ما إذا كانت هذه القطعة قد تحركت. يمكننا تبسيط ذلك من خلال تخزين بعض الشيء فقط لأحد هذه المربعات الستة إذا حدث ذلك في ذلك. بدلا من ذلك، يمكننا أن نتعامل مع كل قطعة غير محددة كوعي قطعة أخرى، لذا بدلا من 6 أنواع من 6 قطع على كل جانب (البيدق، الغروخ، الفارس، الأسقف، الملكة والملك) هناك 8 (إضافة الروك غير الروكي والملك غير المرغوب فيه).

en passant.

القاعدة الغريبة وغير المهملة في كثير من الأحيان في الشطرنج en passant..

تقدمت اللعبة.

E4 E5.
NF3 NC6.
BB5 A6.
BA4 BC5.
OO B5.
BB3 B4.
C4.

لدى Black's Pawn على B4 الآن خيار نقل بيدقه على B4 إلى C3 أخذ البيدق الأبيض على C4. يحدث هذا فقط في الفرصة الأولى المعنى إذا تم تمرير أسود على الخيار الآن لا يستطيع نقله إلى الخطوة التالية. لذلك نحن بحاجة إلى تخزين هذا.

إذا كنا نعرف الخطوة السابقة، فيمكننا بالتأكيد الإجابة ما إذا كان EN Passant ممكن. بدلا من ذلك، يمكننا تخزين ما إذا كانت كل بيدق على رتبتها الرابعة قد انتقلت للتو مع تقدم مزدوج إلى الأمام. أو يمكننا أن ننظر إلى كل موقف محتمل في المباراة على اللوحة ولدي العلم للإشارة إلى ما إذا كان ذلك ممكنا أم لا.

ترقية وظيفية

إنها خطوة بيضاء. إذا كان البيض يتحرك بيدقه على H7 إلى H8، فيمكن ترقيته إلى أي قطعة أخرى (ولكن ليس الملك). 99٪ من الوقت يتم الترويج لها إلى ملكة ولكن في بعض الأحيان ليس كذلك، عادة لأن ذلك قد يجبر الجمود عند فوزه على خلاف ذلك. هذا مكتوب على النحو التالي:

H8 = س

هذا مهم في مشكلتنا لأنه يعني أننا لا نستطيع الاعتماد على وجود عدد ثابت من القطع على كل جانب. من الممكن تماما (ولكن من غير المرجح بشكل لا يصدق) أن ينتهي جانب واحد مع 9 ملكات أو 10 روائك أو 10 أساقفة أو 10 فرسان إذا تمت ترقيته 8 بيادق 8.

الجمود

عندما تكون في موقع لا يمكنك الفوز به أفضل تكتيك هو محاولة الجمود. وبعد البديل الأكثر احتمالا هو المكان الذي لا يمكنك فيه نقل حركة قانونية (عادة لأن أي خطوة عند وضع ملكك في الشيكات). في هذه الحالة، يمكنك المطالبة بالتعادل. هذا واحد سهل تلبية.

البديل الثاني هو عن طريق ثلاثة أضعاف التكرار. وبعد إذا حدث موقع اللوحة نفسه ثلاث مرات في لعبة (أو سيحدث مرة أخرى في الخطوة التالية)، فيمكن المطالبة بسحب. لا تحتاج المواقف إلى أي أمر معين (مما يعني أنه لا يحتوي على نفس تسلسل التحركات المتكررة ثلاث مرات). يعزز هذا المرء إلى حد كبير المشكلة لأنه يتعين عليك تذكر كل موقف لوحي سابقا. إذا كان هذا شرطا للمشكلة الحل الوحيد الممكن للمشكلة هو تخزين كل خطوة سابقة.

أخيرا، هناك خمسون خطوة الحكم. وبعد يمكن للاعب المطالبة بالتعادل إذا لم تتحرك البيدق ولا يتم أخذ أي قطعة في التحركات الخمسين المتتالية السابقة، لذلك سنحتاج إلى تخزين عدد التحركات منذ أن تم نقل البيدق أو قطعة تؤخذ (الأحدث من الاثنين. هذا يتطلب ذلك 6 بت (0-63).

دور من؟

بالطبع نحتاج أيضا إلى معرفة بدوره هو وهذا قليل من المعلومات.

مشاكلين

بسبب حالة الجمود، فإن الطريقة الوحيدة الممكنة أو المعقولة لتخزين حالة اللعبة هي تخزين جميع التحركات التي أدت إلى هذا الموضع. سأعالج هذه مشكلة واحدة. سيتم تبسيط مشكلة حالة مجلس الإدارة إلى هذا: قم بتخزين الوضع الحالي لجميع القطع في المجلس يتجاهل الصدع، en passant، ظروف الجمود والذين يستطفون.

يمكن معالجة تخطيط قطعة على نطاق واسع بأحد طريقتين: عن طريق تخزين محتويات كل مربع أو عن طريق تخزين موضع كل قطعة.

محتويات بسيطة

هناك ستة أنواع (بيدق، الغراب، فارس، أسقف، كوين، كينج). يمكن أن تكون كل قطعة بيضاء أو سوداء لذا فقد تحتوي مربع واحد من 12 قطعة محتملة أو قد تكون فارغة لذلك هناك 13 إمكانيات. 13 يمكن تخزينها في 4 بت (0-15) لذا فإن أبسط الحل هو تخزين 4 بت لكل مريح 64 مربعا أو 256 بت من المعلومات.

ميزة هذه الطريقة هي أن التلاعب هو بشكل لا يصدق سهل وسريع. قد يتم توسيع ذلك من خلال إضافة 3 إمكانيات أخرى دون زيادة متطلبات التخزين: البيدق الذي انتقل 2 مسافات في المنعطف الأخير، ملك لم يتحرك وجذابة لم يتحرك، مما سيعمل على تلبية الكثير القضايا المذكورة سابقا.

ولكن يمكننا أن نفعل ما هو أفضل.

قاعدة 13 الترميز

غالبا ما يكون من المفيد التفكير في موقف مجلس الإدارة كرقم كبير جدا. وغالبا ما يتم ذلك في علوم الكمبيوتر. على سبيل المثال، إيقاف المشكلة يعامل برنامج الكمبيوتر (بحظره) كرقم كبير.

الحل الأول يعامل الموضع كرقم 16 رقمي 64 رقما ولكن كما هو موضح هناك تكرار في هذه المعلومات (كونه 3 إمكانيات غير مستخدمة لكل "رقم") حتى نتمكن من تقليل مساحة الأرقام إلى 64 قاعدة 13 رقما. بالطبع لا يمكن القيام بذلك بشكل فعال كقاعدة 16، لكن سيتم حفظ متطلبات التخزين (وتقليل مساحة التخزين هو هدفنا).

في قاعدة 10، رقم 234 يعادل 2 × 10² + 3 × 10¹ + 4 × 10⁰.

في Base 16، رقم 0xa50 يعادل 10 × 16² + 5 × 16¹ + 0 × 16⁰ = 2640 (عشري).

حتى نتمكن من تشفير موقفنا ك₀ X 13.⁶³ + ص₁ X 13.⁶² + ... + ص₆₃ X 13.⁰ حيث P._أنا يمثل محتويات المربع أنا.

2²⁵⁶ يساوي حوالي 1.16E77. 13.⁶⁴ يساوي حوالي 1.9671، والتي تتطلب 237 بت من مساحة التخزين. أن توفير 7.5٪ فقط يأتي بتكلفة بشكل كبير زيادة تكاليف التلاعب.

ترميز قاعدة متغير

في لوحات قانونية لا يمكن أن تظهر بعض القطع في مربعات معينة. على سبيل المثال، لا يمكن أن تحدث بيادق في المرتبة الأولى أو الثامنة، مما يقلل من إمكانيات تلك المربعات إلى 11. التي تقلل من المجالس الممكنة إلى 11¹⁶ X 13.⁴⁸ = 1.35E70 (تقريبا)، تتطلب 233 بت من مساحة التخزين.

في الواقع ترميز وفك تشفير هذه القيم من وإلى العشرية (أو الثنائية) هو أكثر من التوظيف قليلا ولكن يمكن القيام به بشكل موثوق ويترك بمثابة تمرين للقارئ.

عرض الحروف الهجائية المتغيرة

يمكن وصف الطريقتين السابقين كلاهما العرض الأبجدية العرض الثابت. وبعد يتم استبدال كل من 11 أو 13 أو 16 عضوا في الأبجدية بقيمة أخرى. كل "حرف" هو نفس العرض ولكن يمكن تحسين الكفاءة عند النظر في أن كل حرف غير محتمل على قدم المساواة.

morse code

انصح شيفرة مورس (في الصورة أعلاه). يتم ترميز الأحرف في رسالة كتسلسل من شرطات ونقاط. يتم نقل هذه الشرطات والنقاط عبر الراديو (عادة) مع توقف مؤقت بينهما.

لاحظ كيف الحرف E (الرسالة الأكثر شيوعا باللغة الإنجليزية) هو نقطة واحدة، أقصر تسلسل ممكن، في حين أن Z (الأقل تكرارا) هو شرطة واثنين من الصفافيات.

مثل هذا المخطط يمكن أن يقلل بشكل كبير من حجم متوقع رسالة ولكن تأتي بتكلفة زيادة حجم تسلسل الأحرف العشوائية.

تجدر الإشارة إلى أن كود مورس يحتوي على ميزة أخرى من جديد: تكون شرطات طالما ثلاث نقاط حتى يتم إنشاء الرمز أعلاه بهذا في الاعتبار لتقليل استخدام الشرطات. نظرا لأن 1s و 0s (كتلنا) لا تملك هذه المشكلة، فهي ليست ميزة نحتاج إلى النسخ المتماثل.

أخيرا، هناك نوعان من السطوح في كود مورس. يتم استخدام راحة قصيرة (طول النقطة) للتمييز بين النقاط والشرطات. يتم استخدام فجوة أطول (طول Dash) لتحديد الأحرف.

فكيف تنطبق هذا على مشكلتنا؟

هوفمان الترميز

هناك خوارزمية للتعامل مع رموز طول المتغير يسمى هوفمان الترميز. وبعد يؤدي الترميز Huffman بإنشاء استبدال رمز طول متغير، عادة ما يستخدم التردد المتوقع للرموز لتعيين قيم أقصر للرموز الأكثر شيوعا.

في الشجرة المذكورة أعلاه، يتم ترميز الحرف E بنسبة 000 (أو اليسار الأيسر) و s هو 1011. يجب أن يكون واضحا أن هذا مخطط الترميز هو خالية من الغموض.

هذا تمييز مهم من كود مورس. يحتوي Code Morse على فاصل الأحرف بحيث يمكنه القيام بديل غامض خلاف ذلك (مثل 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 بت ثم تشفير (باستخدام ترميز Huffman أو، على سبيل المثال، طريقة تشغيل طول الترميز). من الواضح أن هذا سيكون فعالا للغاية لبدء (64 0s ربما يتوافق مع 64 بت) ولكن الزيادة في التخزين المطلوبة مع تقدم اللعبة.

موقف قطعة

كما ذكر، هناك طريقة أخرى لمهاجمة هذه المشكلة هي تخزين موضع كل قطعة لديه لاعب. يعمل هذا بشكل جيد بشكل جيد مع مراكز Endgame حيث ستكون معظم المربعات فارغة (ولكن في نهج الترميز Huffman، استخدم المربعات الفارغة فقط 1 بت على أي حال).

سيكون لكل جانب ملك و 0-15 قطعة أخرى. بسبب الترويج، يمكن أن تختلف التعويض الدقيق لهذه القطع بما يكفي أنه لا يمكنك تحمل الأرقام بناء على مراكز البداية مكسيما.

الطريقة المنطقية لتقسيم هذا الأمر هي تخزين موقف يتكون من الجانبين (أبيض وأسود). كل جانب لديه:

ملك: 6 بت للموقع؛
لديه البيادق: 1 (نعم)، 0 (لا)؛
إذا كانت الإجابة بنعم، عدد البيدون: 3 بتات (0-7 + 1 = 1-8)؛
إذا كانت الإجابة بنعم، يتم تشفير موقع كل بيدق: 45 بت (انظر أدناه)؛
عدد غير البيادق: 4 بت (0-15)؛
لكل قطعة: النوع (2 بت الملكة، الغراب، فارس، الأسقف) والموقع (6 بت)

بالنسبة لموقع البيدق، يمكن أن يكون البيادق فقط على 48 مربعا ممكنا (وليس 64 مثل الآخرين). على هذا النحو، من الأفضل عدم إضاعة القيم 16 الإضافية التي تستخدم 6 بت لكل بيدق ستستخدمها. لذلك إذا كان لديك 8 بيادق هناك 48⁸ الاحتمالات، يساوي 28،179،280،429،056. تحتاج إلى 45 بت ترميز أن العديد من القيم.

هذا 105 بت لكل جانب أو 210 بت كاملة. موقف البداية هو أسوأ حالة لهذه الطريقة، وسوف تحصل بشكل أفضل بكثير أثناء إزالة القطع.

يجب الإشارة إلى أن هناك أقل من 48⁸ الاحتمالات لأن البيدق لا يمكن أن يكون كلها في نفس المربع الأول لديه 48 إمكانيات، والثاني 47 وما إلى ذلك. 48 × 47 × ... X 41 = 1.52E13 = 44 بت التخزين.

يمكنك تحسين ذلك عن طريق القضاء على المربعات التي تشغلها القطع الأخرى (بما في ذلك الجانب الآخر) حتى تتمكن من وضع البيدون البيض باللونين الأبيض، ثم غير البيادق السوداء، ثم البيادق البيضاء وأخيرا البيادق السوداء. في موضع البداية، يؤدي ذلك إلى تقليل متطلبات التخزين إلى 44 بت من أجل أبيض و 42 بت من أجل الأسود.

مناهج مجتمعة

تحسين آخر محتمل هو أن كل من هذه الأساليب لها قوتها وضعفها. يمكنك أن تختار أفضل 4 ثم ترميز محدد مخطط في أول بتان ثم تخزين مخطط خاص بهذا.

مع النفقات العامة، هذا سوف يكون هذا هو أفضل نهج.

لعبة الدولة

أعود إلى مشكلة تخزين أ لعبه بدلا من وضع. وبعد بسبب التكرار ثلاثة أضعاف علينا تخزين قائمة التحركات التي حدثت لهذه النقطة.

التوضيحية

شيء واحد عليك تحديده هو ببساطة تخزين قائمة بالتحركات أم أنك تشريح اللعبة؟ غالبا ما يتم تفوحها ألعاب الشطرنج، على سبيل المثال:

BB5 !! NC4؟

تتميز خطوة White بمثابة نقطتين تعجبين كعمل رائع، حيث ينظر إلى Black's Black على أنه خطأ. يرى علامات الشطرنج.

بالإضافة إلى ذلك، يمكنك أيضا الحاجة إلى تخزين نص مجاني كما يتم وصف التحركات.

أفترض أن التحركات كافية لذلك لن تكون هناك شروح.

تدوين الجبر

يمكننا ببساطة تخزين نص التحرك هنا ("E4"، "BXB5"، إلخ). بما في ذلك البايت إنهاء كنت تبحث في حوالي 6 بايت (48 بت) لكل خطوة (أسوأ الحالات). هذا ليس فعالا بشكل خاص.

الشيء الثاني الذي يجب تجربته هو تخزين موقع البداية (6 بت) وموقع نهاية (6 بت) حتى 12 بت لكل خطوة. هذا أفضل بكثير.

بدلا من ذلك، يمكننا تحديد جميع التحركات القانونية من الموضع الحالي بطريقة يمكن التنبؤ بها والحاسمة والدولة التي اخترناها. هذا ثم يعود إلى الترميز الأساسي المتغير المذكور أعلاه. White والأسود لديهم 20 تحركات ممكنة لكل منها في أول خطوة لها، أكثر في الثانية وهلم جرا.

خاتمة

لا توجد إجابة صحيحة على هذا السؤال. هناك العديد من الأساليب الممكنة التي سبق لها عدد قليل فقط.

ما أعجبته في هذا ومشاكل مماثلة هو أنه يتطلب قدرات مهمة لأي مبرمج مثل النظر في نمط الاستخدام، وتحديد المتطلبات بدقة والتفكير في حالات الزاوية.

مناصب الشطرنج التي اتخذت كشاشة من موقف الشطرنج المدرب.

نصائح أخرى

من الأفضل تخزين ألعاب الشطرنج فقط بتنسيق قياسي مقروء الإنسان.

ال تدوين اللعبة المحمولة يفترض موقف البداية القياسي (على الرغم من أنه لا تضطر إلى ذلك) فقط يسرد التحركات، بدوره بدوره. تنسيق مدمج مقروءة بشرية، معيار.

على سبيل المثال

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

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

إذا كنت تريد أن تجعلها أصغر، ثم فقط الرمز البريدي. وبعد تم إنجاز المهمة!

لغز رائع!

أرى أن معظم الناس يخزنون موقف كل قطعة. ماذا عن اتخاذ نهج أكثر فاعلية، و تخزين محتويات كل مربعب هذا يعتني الترويج والتقاط القطع تلقائيا.

وتسمح ل هوفمان ترميز. وبعد في الواقع، فإن التردد الأولي للقطع على اللوحة مثالية تقريبا لهذا: نصف المربعات فارغة، نصف المربعات المتبقية هي بيادق، إلتاليا.

النظر في تواتر كل قطعة، أنا بناء شجرة هوفمان على الورق، الذي لن أكرر هنا. النتيجة، حيث c يقف اللون (أبيض = 0، أسود = 1):

0 للساحات الفارغة
1C0 للبيدق
1C100 ل Rook.
1C101 لفارس
1C110 للأسقف
1C1110 لملكة
1C1111 للملك

للمجلس بأكمله في وضعه الأولي، لدينا

المربعات الفارغة: 32 * 1 بت = 32 بت
بيادق: 16 * 3 بت = 48 بت
المجال / الفرسان / الأساقفة: 12 * 5 بت = 60 بت
كوينز / الملوك: 4 * 6 بت = 24 بت

المجموع: 164 بت ل مبدئي حالة مجلس الإدارة. أقل بكثير من 235 بت من الإجابة الأعلى حاليا. ويذهب فقط للحصول على أصغر لأن اللعبة تقدم (إلا بعد الترويج).

نظرت فقط في موضع القطع على السبورة؛ يجب أن يتم تشفير حالة إضافية (التي تحولها، التي كانت مضغوط، على passant، تكرار التحركات، إلخ) بشكل منفصل. ربما 16 بت آخر على الأكثر، لذلك 180 بت لحالة اللعبة بأكملها. التحسينات المحتملة:

ترك القطع الأقل تكرارا، وتخزين موقفهم بشكل منفصل. ولكن هذا لن يساعد ... استبدال الملك والملكة بواسطة مربع فارغ يوفر 5 بت، والتي هي بالضبط البتات التي تحتاجها بالضبط لترميز موقفها بطريقة أخرى.
"لا يمكن بسهولة ترميز أي بيادق على الصف الخلفي" باستخدام جدول هوفمان مختلف للصفوف الخلفية، لكنني أشك في أنه يساعد الكثير. ربما لا تزال في نهاية المطاف مع نفس شجرة Huffman.
"واحدة بيضاء، أسقف أسود واحد" يمكن ترميزها عن طريق إدخال رموز إضافية لا تملك c بت، والتي يمكن بعد ذلك استنتاج من المربع أن الأسقف قيد التشغيل. (البيادق التي تمت ترقيتها إلى الأساقفة تعطيل هذا المخطط ...)
يمكن تشغيل متكررات المربعات الفارغة مدفوعة ترميزها من خلال إدخال رموز إضافية ل، يقول "2 مربعات فارغة على التوالي" و "4 مربعات فارغة على التوالي". ولكن ليس من السهل تقدير تواتر هؤلاء، وإذا كنت تخطئ، فسيؤذي ذلك بدلا من المساعدة.

نهج الجدول البحث الكبير حقا

موضع - 18 بايت
العدد المقدر من المناصب القانونية هو 10⁴³
ببساطة تعداد لهم جميعا ويمكن تخزين الموقف في 143 بت فقط. 1 مطلوب آخر للإشارة إلى الجانب هو اللعب التالي

التعداد غير عملي بالطبع، ولكن هذا يدل على أن 144 بت على الأقل مطلوبة.

التحركات - 1 بايت
عادة ما تكون هناك حوالي 30-40 خطوة قانونية لكل موقف ولكن قد يكون الرقم يصل إلى 218 يتيح التعداد جميع التحركات القانونية لكل موقف. الآن يمكن ترميز كل خطوة في بايت واحد.

لا يزال لدينا مساحة كبيرة لتحركات خاصة مثل 0xFF لتمثيل الاستقالة.

أنه إضافة إلى الاهتمام تحسين متوسط حالة حجم نموذجي المباريات التي لعبت من قبل البشر ، بدلا من أسوأ الأحوال.(بيان المشكلة لا يقول وهو ؛ معظم الردود نفترض الأسوأ.)

للانتقال تسلسل جيد محرك الشطرنج توليد تحركات من كل موقف.انها سوف تنتج قائمة ك التحركات المحتملة التي أمرت ترتيبه من جودتها.الناس عموما اختيار التحركات الجيدة في أكثر الأحيان عشوائية التحركات ، لذلك نحن بحاجة إلى أن نتعلم رسم الخرائط من كل موقف في القائمة إلى احتمال أن اختيار الناس وهي الخطوة التي 'جيدة'.باستخدام هذه الاحتمالات (على أساس مجموعة من الألعاب من الإنترنت الشطرنج قاعدة البيانات), ترميز يتحرك مع الترميز الحسابي.(فك يجب أن تستخدم نفس محرك الشطرنج و رسم الخرائط.)

انطلاق الموقف ، ralu هذا النهج.يمكننا تحسينه مع الترميز الحسابي هناك أيضا ، إذا كان لدينا بعض الطريق إلى الوزن الخيارات من خلال الاحتمالات — على سبيل المثال ، القطع غالبا ما تظهر في تكوينات يدافع عن بعضها البعض ، وليس عشوائيا.من الصعب أن نرى طريقة سهلة لدمج تلك المعرفة.فكرة واحدة:تقع مرة أخرى على ما سبق نقل ترميز بدلا من ذلك ، بدءا من مستوى الافتتاح الموقف وإيجاد تسلسل الذي ينتهي في مجلس المرجوة.(قد حاول* البحث مع مجريات الأمور المسافة يعادل مجموع المسافات من القطع من المواقف النهائية ، أو شيء على طول هذه الخطوط.) هذا الحرف بعض القصور من overspecifying الخطوة تسلسل مقابلالكفاءة من الاستفادة من لعب الشطرنج المعرفة.(يمكنك العودة مخلب بعض القصور من خلال القضاء على التحرك الخيارات التي من شأنها أن تؤدي إلى سبق-استكشاف الموقف في* البحث:هذه يمكن الحصول على الوزن 0 في الحساب رمز.)

كما انها نوع من الصعب تقدير مدى تحقيق وفورات هذا من شأنه أن أشتري لك في متوسط حالة التعقيد ، دون جمع بعض الإحصاءات الفعلية الإحضار.ولكن نقطة الانطلاق مع كل التحركات المحتملة على حد سواء أعتقد أن فاز بالفعل معظم المقترحات هنا:الحساب الترميز لا تحتاج إلى عدد صحيح عدد البتات في التحرك.

مهاجمة مشكلة فرعية لتشفير الخطوات بعد ترميز الموضع الأولي. النهج هو إنشاء "قائمة مرتبطة" بالخطوات.

يتم ترميز كل خطوة في اللعبة كقوة زوج "الموقف القديم> الجديد". أنت تعرف الموقف الأولي في بداية لعبة الشطرنج؛ من خلال اجتياز قائمة الخطوات المرتبطة، يمكنك الوصول إلى الحالة بعد تحركات X.

لترميز كل خطوة، تحتاج إلى 64 قيما لترميز وضع البداية (6 بتات ل 64 مربعا على اللوحة - المربعات 8x8)، و 6 بت من موقف النهاية. 16 بت لنقل 1 من كل جانب.

مبلغ المساحة التي ترميز لعبة معينة ستستغرقها ثم يتناسب مع عدد التحركات:

10 × (عدد التحركات البيضاء + عدد من التحركات السوداء) بت.

تحديث: المضاعفات المحتملة مع البيادق الترويج. بحاجة إلى أن تكون قادرة على تحديد ما يتم ترقيته البيدق إلى - قد يحتاج إلى أجزاء خاصة (سيستخدم الرمز الرمادي لهذا لتوفير المساحة، كما هو أمر بيادق نادر للغاية).

تحديث 2: ليس عليك ترميز الإحداثيات الكاملة موضع النهاية. في معظم الحالات، يمكن أن تتحرك القطعة التي يتم نقلها إلى أبعد من الأماكن x. على سبيل المثال، يمكن أن يكون لدى البيدق 3 خيارات خطوة كحد أقصى في أي نقطة معينة. من خلال إدراك أن الحد الأقصى لعدد التحركات لكل نوع من النوع، يمكننا توفير البتات على ترميز "الوجهة".

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

لذا فإن التعقيد المكاني لكل خطوة من الأسود أو الأبيض يصبح

6 بت من أجل الموضع الأولي + (عدد متغير من البتات بناء على نوع الشيء الذي تم نقله).

رأيت هذه السؤال الليلة الماضية وأستغرقني لذلك جلست في حلول تفكير الفراش. إجابتي النهائية تشبه إلى حد ما في INT3 في الواقع.

الحل الأساسي

على افتراض لعبة الشطرنج القياسية وأنك لا ترمز القواعد (مثل الأبيض دائما يذهب أولا)، ثم يمكنك توفير الكثير من خلال ترميز فقط تحركات كل قطعة

هناك مجموع 32 قطعة ولكن على كل خطوة تعرف ما هو اللون الذي يتحرك لذلك هناك 16 مربعا فقط للقلق، وهو ما هو عليه 4 بت التي تنتقل قطعة هذا الدوران.

تحتوي كل قطعة فقط على Moveset محدودة، والتي ستتعداد بها بطريقة ما.

البيدق: 4 خيارات، 2 بت (1 خطوة إلى الأمام، 2 خطوات إلى الأمام، 1 كل قطري)
الروك: 14 خيارات، 4 بت (بحد أقصى 7 في كل اتجاه)
الأسقف: 13 خيارات، 4 بت (إذا كان لديك 7 في قطري واحد، فلديك فقط 6 في آخر)
نايت: 8 خيارات، 3 بت
الملكة: 27 خيارات، 5 بت (روك + أسقف)
الملك: 9 خيارات، 4 بت (8 خطوة واحدة يتحرك، بالإضافة إلى خيار الصدع)

للحصول على الترقية، هناك 4 قطع للاختيار من بينها (الرخ، الأسقف، فارس، الملكة) لذلك في هذه الخطوة 2 بت لتحديد ذلك. أعتقد أن جميع القواعد الأخرى مغطاة تلقائيا (مثل Passant).

تحسينات إضافية

أولا، بعد التقاط 8 قطع من لون واحد، يمكنك تقليل ترميز القطعة إلى 3 بت، ثم 2 بتات لمدة 4 قطع وهلم جرا.

التحسين الرئيسي على الرغم من التعداد فقط التحركات الممكنة في كل نقطة في اللعبة. افترض أننا تخزن تحركات البيدق كما {00, 01, 10, 11} لمدة 1 خطوة إلى الأمام، 2 خطوات إلى الأمام، والخروج الأيسر والقطري الحق على التوالي. إذا لم تكن بعض التحركات غير ممكنة، فيمكننا إزالتها من الترميز لهذا المنعطف.

نحن نعرف حالة اللعبة في كل مرحلة (من اتباع جميع التحركات)، لذلك بعد قراءة القطعة التي ستتحرك، يمكننا دائما تحديد عدد البتات التي نحتاج إلى قراءتها. إذا أدركنا التحركات الوحيدة للبيد البيدق في هذه المرحلة، فهي تلتقط في الحق في القطرية أو المضي قدما، ونحن نعرف فقط قراءة 1 بت فقط.

باختصار، تخزن البت المذكورة أعلاه لكل قطعة أقصى فقط. كل خطوة تقريبا سيكون لها خيارات أقل وغالبا ما يكون عدد أقل من البتات.

في كل موقف على عدد من التحركات المحتملة.

الخطوة التالية هي إنشاء

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

بصورة مبرهنة أفضل كفاءة الفضاء لتخزين بشكل عشوائي اللعبة و تحتاج تقريبا 5 قطع/نقل في المتوسط منذ 30-40 ممكن من التحركات.تجميع وتخزين هو مجرد توليد ن في ترتيب عكسي.

تخزين الموقف الصعب الكراك ، التكرار.(يمكن أن يكون هناك ما يصل إلى 9 كوينز على متن موقع واحد ولكن في هذه الحالة لا توجد بيادق ، الأساقفة إذا كان على المجلس هي على العكس المربعات الملونة) ولكن عموما هو مثل تخزين مزيج من نفس القطع على المربعات المتبقية.)

تحرير:

نقطة في إنقاذ التحركات هو فقط لتخزين مؤشر الخطوة.بدلا من تخزين Kc1-c2 و محاولة للحد من هذه المعلومات يجب أن نضيف فقط مؤشر حركة ولدت من القطعية movegenerator(موقف)

في كل خطوة نقوم بإضافة معلومات من حجم

num_of_moves = get_number_of_possible_moves(postion) ;

في تجمع هذا العدد لا يمكن تخفيض

توليد المعلومات تجمع

n=n*num_of_moves+ index_current_move

إضافية

إذا كان هناك خطوة واحدة فقط متوفرة في الموقف النهائي ، حفظ باسم عدد من فعلت سابقا القسري التحركات.على سبيل المثال:إن نقطة الانطلاق 1 القسري التحركات لكل جانب (2 التحركات) ونحن نريد أن حفظ هذا بمثابة خطوة واحدة لعبة, تخزين 1 في بركة n.

مثال على تخزين معلومات بركة

دعونا نفترض أن لدينا معروفة بدءا المواقف ونحن نفعل 3 التحركات.

في الخطوة الأولى هناك 5 التحركات المتاحة ، تحرك مؤشر 4.في الخطوة الثانية هناك 6 التحركات المتاحة ونحن نأخذ موقف المؤشر 3 وفي 3th التحرك هناك 7 التحركات المتاحة عن هذا الجانب و اختار أن اختيار هذه الخطوة مؤشر 2.

ناقلات شكل من الأشكال ؛ index=[4,3,2] n_moves=[5,6,7]

نحن ترميز هذه المعلومات إلى الوراء ، حتى ن= 4+5*(3+6*(2))=79 (لا ضرب من قبل 7 الحاجة)

كيفية unloop هذا ؟ علينا أولا الموقف نجد أن هناك 5 التحركات المتاحة.لذلك

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

نأخذ تحرك مؤشر 4 ودراسة الموقف مرة أخرى و من هذه النقطة نجد أن هناك 6 التحركات المحتملة.

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

ونحن نأخذ تحرك مؤشر 3 الذي يحصل لنا موقف مع 7 ممكن من التحركات.

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

ونحن نفعل الخطوة الأخيرة مؤشر 2 و نصل إلى موقف نهائي.

كما ترون تعقيد الوقت O(n) ansd الفضاء تعقيد O(n).تحرير:تعقيد الوقت هو في الواقع O(n^2) لأن الرقم الذي multipy من قبل يزيد ، ولكن ينبغي أن يكون هناك أي مشكلة في تخزين الألعاب يصل إلى 10 ، 000 التحركات.

إنقاذ الموقف

يمكن أن يتم قريبة من المثلى.

عندما نكتشف عن المعلومات وتخزين المعلومات اسمحوا لي أن أتحدث أكثر حول هذا الموضوع.الفكرة العامة هي أن انخفاض التكرار (سوف نتحدث عن ذلك لاحقا).دعونا نفترض أن هناك لا ترقيات ولا أخذ إذن هناك 8 بيادق, 2 الغربان ، 2 الفرسان ، 2 الأساقفة 1 الملك و 1 سرير لكل جانب.

ماذا علينا أن ننقذ:1.موقف كل السلام 2.تخل من الإجهاض 3.إمكانيات ar-بسنت 4.أن تتحرك قارئي

دعونا نفترض أن كل قطعة يمكن أن يقف في أي مكان ولكن لا 2 قطعة في نفس المكان.عدد من الطرق 8 بيادق من نفس اللون يمكن أن تكون مرتبة على متن ج(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 واحد ممكن ar-بسنت (en passant البيدق يمكن أن يكون في واحدة من 8 الأماكن), 16 (4 بت) للحصول على الإجهاض القيود بت واحد من أجل أن تتحرك.نحن في نهاية المطاف مع 142+3+4+1=150bits

ولكن الآن دعونا نذهب على البحث عن التكرار في المجلس مع 32 قطعة و لا الأخذ.

كل أبيض و أسود بيادق على نفس العمود في مواجهة بعضهما البعض.كل بيدق يواجه رهينة أخرى وهذا يعني أن البيدق الأبيض يمكن أن تكون على الأكثر في المركز الـ 6.هذا يجلب لنا 8*ج(6/2) بدلا من C(64/8)*ج(48/8) التي تقلل المعلومات عن 56 بت.
إمكانية الإجهاض هو أيضا زائدة عن الحاجة.إذا الغربان ليس على مكان انطلاق هناك إمكانية الإجهاض مثقال ذرة أن الغراب.حتى نتمكن من imaginaly إضافة 4 مربعات على المجلس للحصول على معلومات إضافية إذا كان الإجهاض مثقال ذرة هذا الغراب من الممكن إزالة 4 الإجهاض بت.وذلك بدلا من C(56/2)*ج(40/2)*16 علينا ج(58/2)*ج(42/2) و فقدنا 3.76 بت (تقريبا كل 4 بت)
ar-بسنت:عندما نقوم بتخزين واحدة من 8 عابرة سارعت نعرف موقف البيدق الأسود وتقليل إعلامية redindancy (إذا كان أبيض تتحرك و قد 3th بيدق ar-بسنت يعني هذا البيدق الأسود على c5 والأبيض البيدق هو إما c2,c3 أو c4) لذا بدلا من C(6/2) لدينا 3 و فقدنا 2.3 بت.نحن نقصان بعض التكرار إذا كنا متجر مثقال ذرة ar-بسنت العدد أيضا الجانب الذي يمكن القيام به (3 احتمالات-> يسار ، يمين ، على حد سواء) ونحن نعرف possiton من بيدق التي يمكن أن تتخذ عابرة.(على سبيل المثال من prevous عابرة سبيل المثال مثقال ذرة سوداء على c5 ما يمكن أن يكون في اليسار واليمين أو كليهما.إذا كان في موقع واحد لدينا 2*3 (3 لتخزين psissibilites و 2 ممكن التحركات البيدق الأسود على 7 أو 6 رتبة) بدلا من C(6/2) ونحن تخفيض بنسبة 1.3 بت إذا كان يملك على الجانبين نعمل على تخفيض بنسبة 4.2 بت.بهذه الطريقة يمكننا خفض بنسبة 2.3+1.3=3.6 بت لكل عابرة.
الأساقفة:bisops يمكن أن يكون على opostite الساحات إلا هذا الحد من التكرار من 1 بت لكل موقع.

إذا أردنا تلخيص نحن بحاجة 150-56-4-3.6-2=85bits لتخزين الشطرنج إذا لم تكن هناك الاستيلاء

وربما ليس أكثر من ذلك بكثير إذا كان هناك الاستيلاء والترقيات تؤخذ في الاعتبار (ولكن سأكتب عن ذلك في وقت لاحق إذا كان شخص ما سوف تجد هذه المدة وظيفة مفيدة)

معظم الناس قد تم ترميز مجلس الدولة ، ولكن فيما يتعلق الحركات نفسها..هنا قليلا-ترميز الوصف.

بت لكل قطعة:

قطعة-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 (ماكس).

هل المشكلة لإعطاء ترميز أكثر كفاءة لألعاب الشطرنج النموذجية، أو واحدة لديها أقصر أسوأ ترميز حالة؟

بالنسبة لهذا الأخير، فإن الطريقة الأكثر كفاءة هي أيضا الأكثر شفاءة: إنشاء تعداد لجميع الأزواج الممكنة (اللوحة الأولية، التسلسل القانوني للحركات)، والتي، مع موقف السحب المتكرر على الترحيب وغير أكثر - التحركات الخاصة بها منذ القواعد الأخيرة من البيدق أو التقاط القبض، هي العودية. ثم يعطي مؤشر الوظيفة في هذا التسلسل المحدود أقصر ترميز الأسوأ، ولكن أيضا ترميز طويل على قدم المساواة للحالات النموذجية، وأتوقع، مكلفة للغاية للحساب. من المفترض أن تكون هناك أطول لعبة شطرنج محتملة تزيد عن 5000 خطوة، حيث تكون هناك 20-30 تحركات متوفرة في كل موقف لكل لاعب (على الرغم من أن عدد قليل عندما تكون هناك عدد قليل من القطع اليسار) - وهذا يعطي شيئا مثل 40000 بت مطلوب لهذا الترميز.

يمكن تطبيق فكرة التعداد لإعطاء حل أكثر قابلة للقطاع، كما هو موضح في اقتراح هينك هولترمان لتحركات الترميز أعلاه. اقتراحي: ليس الحد الأدنى، ولكن أقصر من الأمثلة المذكورة أعلاه نظرت إليه، وسحق معقول:

64 بت تمثيل المربعات التي تحتل بها المربعات (مصفوفة الإشغال)، بالإضافة إلى قائمة القطع التي في كل ساحة مشغولة (يمكن أن تحتوي على 3 بت من البتات، و 4 بتات للأجزاء الأخرى): هذا يعطي 190 بت من أجل وضع البداية. نظرا لأنه لا يمكن أن يكون هناك أكثر من 32 قطعة على متنها، فإن ترميز مصفوفة الإشغال زائدة عن زائدة عن الحاجة، وهكذا يمكن تشفير شيء مثل مواقع اللوحات الشائعة، كما يقول 33 مجموعة BITS بالإضافة إلى مؤشر اللوحة من قائمة المجالس المشتركة.
1 بت القول الذي يجعل الخطوة الأولى
تحركات الكود حسب اقتراح هينك: عادة 10 بت لكل زوج من الخطوة البيضاء / السوداء، على الرغم من أن بعض التحركات ستتناول 0 بت، عندما لا يحتوي اللاعب على تحركات بديلة.

هذا يشير إلى 490 بت لرمز لعبة 30 خطوة نموذجية، وستكون تمثيلا فعال بشكل معقول للألعاب النموذجية.

تقوم ABOUTH بترميز الموضع المتكرر للمشروع وغير متكررة وغير أكثر من خمسين خطوات منذ القواعد الأخيرة البيدق أو التقاط التقاط: إذا قمت بتشفير Thepast يتحرك مرة أخرى إلى آخر تحرك البيدق أو التقاطها، فأنت لديهم معلومات كافية لتحديد ما إذا كانت هذه القواعد تنطبق: لا حاجة لتاريخ اللعبة بأكملها.

يمكن تعريف الموقف الموجود على لوحة في 7 بت (0-63، وقيمة واحدة تحددها ليست على اللوحة بعد الآن). لذلك لتحديد كل قطعة على اللوحة حيث يقع.

32 قطعة * 7 بت = 224 بت

تحرير: كما أشار كابليان إلى ... لدينا أيضا "البيدق المعزز إلى حالة الملكة. أقترح أن نضيف بتات إضافية في النهاية للإشارة إلى البيدق الذي تم ترقيته.

لذلك لكل بيدق تم الترويج لأننا نتبع 224 بت مع 5 بتات تشير إلى مؤشر البيدق الذي تم الترويج له، و 11111 إذا كانت نهاية القائمة.

لذلك الحد الأدنى من القضية (لا توجد عروض) هي 224 بت + 5 (بدون عروض ترويجية). لكل بيدق ترقية 5 بت.

تحرير: كما يشير الضفدع أشعث، نحن بحاجة إلى بعض الشيء آخر في النهاية للإشارة إلى دورها؛ ^)

كنت أستخدم ترميز طول التشغيل. بعض القطع فريدة (أو موجودة فقط مرتين)، لذلك يمكنني حذف الطول بعدها. مثل كليتوس، أحتاج إلى 13 دولة فريدة من نوعها، حتى أتمكن من استخدام nibble (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 مع nibble ولكن منذ "فارغة، 0" لا معنى له، يمكنني علاج "0" باسم "16".

إذا كان اللوحة فارغا ولكن بالنسبة للبيدق واحد في الزاوية اليسرى العليا، أحصل على "البيدق، 1، فارغ، 16، فارغة، 16، فارغة 16، فارغة، فارغة، 15" = 10 قضم = 40 بت.

أسوأ الحالات هي عندما يكون لدي مربع فارغ بين كل قطعة. ولكن بالنسبة لترميز القطعة، أحتاج فقط إلى 13 من أصل 16 قيما، لذلك ربما يمكنني استخدام واحدة أخرى لأقول "فارغ 1". ثم، أحتاج 64 قضم == 128bits.

بالنسبة للحركات، أحتاج إلى 3 بتات للقطعة (يتم تقديم اللون من خلال حقيقة أن الأبيض دائما يتحرك أولا) بالإضافة إلى 5 بت (0..63) للموقف الجديد = بايت واحد لكل حركة. معظم الوقت، لا أحتاج إلى الموضع القديم لأن قطعة واحدة فقط ستكون ضمن النطاق. بالنسبة للحالة الغريبة، يجب أن أستخدم التعليمات البرمجية الوحيدة غير المستخدمة (أحتاج فقط إلى 7 رموز لترميز القطعة) ثم 5 بتات مقابل البتات القديمة و 5 مقابل الموقف الجديد.

هذا يتيح لي أن ترميز الصدع في 13 لدغات (يمكنني نقل الملك نحو الغراب الذي يكفي أن أقول ما أنوي).

تحرير] إذا سمحت برمز ذكي، فأنا بحاجة إلى 0 بت من أجل الإعداد الأولي (لأنه لا يجب ترميزه بأي طريقة: إنه ثابت) بالإضافة إلى بايت واحد لكل خطوة.

edit2] مما يترك تحويل البيدق. إذا وصلت البيدق إلى الصف الأخير، يمكنني نقله في مكانه ليقول "يحول" ثم قم بإضافة البتات الثلاثة الخاصة بالقطعة التي يتم استبدالها (ليس لديك لاستخدام ملكة؛ يمكنك استبدال البيدق بأي شيء لكن الملك).

مثل ترميز الألعاب على الكتب والأوراق:كل قطعة لها رمز ؛ منذ انها "القانونية" لعبة, أبيض يتحرك أولا - لا تحتاج إلى ترميز الأبيض أو الأسود separetely فقط الاعتماد على عدد من التحركات لتحديد الذين انتقلوا.أيضا ، في كل خطوة هو ترميز (قطعة انهاء الموقف) حيث 'انهاء الموقف' ينخفض إلى أقل قدر من الرموز التي تسمح أن نستشف الغموض (يمكن أن تكون صفر).طول اللعبة يحدد عدد من التحركات.يمكن للمرء أيضا ترميز الوقت في دقائق (منذ الخطوة الأخيرة) في كل خطوة.

ترميز قطعة يمكن أن يتم ذلك إما عن طريق تعيين رمز لكل (32 المجموع) أو عن طريق تعيين رمز إلى فئة ، واستخدام انهاء الموقف لفهم أي قطعة تم نقله.على سبيل المثال ، بيدق 6 ممكن تنتهي الوظائف ؛ ولكن في المتوسط سوى بضع تتوفر في كل منعطف.لذا إحصائيا ، ترميز قبل انهاء الموقف قد يكون أفضل لهذا السيناريو.

مماثلة ترميزات تستخدم ارتفاع القطارات الحسابية في علم الأعصاب (AER).

السلبيات:تحتاج إلى إعادة تشغيل اللعبة كلها للحصول على الوضع الحالي و إنشاء مجموعة فرعية, مثل الكثير من عبور قائمة مرتبطة.

هناك 64 ممكن مناصب في مجالس الإدارة ، لذلك تحتاج 6 بت لكل موقف.هناك 32 الأولي قطعة ، لذلك علينا 192 بت المجموع حتى الآن ، حيث كل 6 بت يشير إلى الموقف من قطعة معينة.ونحن يمكن مسبقا تحديد ترتيب القطع تظهر في, لذلك نحن لم يكن لديك إلى القول الذي هو فيه.

ما إذا كانت قطعة خارج المجلس ؟ حسنا, نحن يمكن أن تضع قطعة في نفس مكان آخر قطعة للإشارة إلى أنه هو خارج المجلس ، لأن ذلك سيكون غير قانوني على خلاف ذلك.ولكن لا نعرف أيضا ما إذا كانت القطعة الأولى سوف يكون في المجلس أو لا.لذلك نضيف 5 بت تشير إلى أي قطعة هو أول واحد (32 إمكانيات = 5 بت لتمثيل القطعة الأولى).ثم يمكننا استخدام تلك البقعة عن القطع اللاحقة التي هي خارج المجلس.هذا يقودنا إلى 197 بت المجموع.يجب أن يكون هناك على الأقل قطعة واحدة على متن الطائرة ، بحيث سوف تعمل.

ثم نحن في حاجة واحدة بت الذي بدوره هو - يجلب لنا 198 بت.

ماذا عن بيدق الترقية ؟ يمكننا أن نفعل ذلك بطريقة سيئة من خلال إضافة 3 بت لكل البيدق ، مضيفا على 42 بت.ولكن بعد ذلك يمكن أن نلاحظ أن معظم الوقت ، بيادق لا ترقية.

لذلك كل بيدق على المجلس ، بت '0' تشير إلى أنها لا تشجع.إذا كان بيدق على المجلس ثم نحن لا نحتاج قليلا على الإطلاق.ثم يمكننا استخدام متغير طول بت السلاسل التي الترويج لديه.في معظم الأحيان أنها سوف تكون ملكة ، لذلك "10" يمكن أن تعني الملكة.ثم "110" يعني الغراب ، "1110" يعني الأسقف ، و "1111" يعني فارس.

الحالة الأولية سوف تأخذ 198 + 16 = 214 بت, لأن كل 16 بيادق على المجلس unpromoted.نهاية اللعبة مع اثنين من ترقية البيدق-كوينز قد تأخذ شيئا مثل 198 + 4 + 4 بمعنى 4 رهائن على قيد الحياة و لا رقي و 2 الملكة بيادق ، 206 بت مجموع.يبدو قوية جدا!

===

ترميز هوفمان ، كما أشار آخرون ، ستكون الخطوة التالية.إذا لاحظت بضعة ملايين ألعاب, ستلاحظ كل قطعة هو أكثر بكثير من المرجح أن يكون في بعض الساحات.على سبيل المثال ، أكثر من مرة ، بيادق البقاء في خط مستقيم ، أو واحد إلى اليسار / واحد إلى اليمين.الملك عادة عصا في جميع أنحاء المنزل القاعدة.

ولذلك وضع نظام ترميز هوفمان لكل فصل الموقف.بيادق من المرجح أن تأخذ فقط في المتوسط 3-4 بت بدلا من 6.الملك يجب أن تأخذ بعض القطع أيضا.

أيضا في هذا المخطط ، وتشمل "اتخذت" ممكن الموقف.هذا يمكن جدا بقوة التعامل مع الإجهاض وكذلك كل الغراب و الملك إضافية "الموقف الأصلي ، انتقلت" الدولة.يمكنك أيضا تشفير عابرة في عساكر من هذا الطريق - "الموقف الأصلي ، عابرة".

مع ما يكفي من البيانات هذا النهج ينبغي أن تسفر عن نتائج جيدة حقا.

سأحاول استخدام هوفمان ترميز. وبعد النظرية وراء هذا هي - في كل لعبة الشطرنج ستكون هناك بعض القطع التي ستنتقلها كثيرا، وبعضها لا يتحرك الكثير أو الحصول على القضاء المبكر. إذا كان موضع البداية يحتوي على بعض القطع التي تمت إزالتها بالفعل - كل ذلك أفضل. نفس الشيء ينطبق على المربعات - تحصل بعض المربعات على رؤية كل الإجراءات، في حين أن البعض لا تطرق كثيرا.

وبالتالي، لدي طاولان Huffman - واحد للقطع وغيرها من المربعات. سيتم إنشاؤها من خلال النظر في اللعبة الفعلية. يمكن أن يكون لدي طاولة كبيرة واحدة لكل زوج مربع، لكنني أعتقد أنه سيكون غير فعال للغاية لأنه لا توجد حالات كثيرة من نفس القطعة تتحرك على نفس المربع مرة أخرى.

كل قطعة لديها معرف معين. نظرا لأن هناك 32 قطعة مختلفة، فسأحتاج إلى 5 بت فقط لمعرف القطعة. لا تتغير معرفات القطعة من اللعبة إلى اللعبة. الشيء نفسه ينطبق على معرفات مربعة، والتي أحتاجها 6 بت.

سيتم ترميز أشجار Huffman عن طريق كتابة كل عقدة حيث يتم اجتيازها في Interorder (أي، أولا، إخراج العقدة، ثم أطفالها من اليسار إلى اليمين). بالنسبة لكل عقدة، سيكون هناك خصوصي بعض الشيء سواء كانت عقدة ورقة أو عقدة فرعية. إذا كانت عقدة ورقة، فسيتم تليها البتات التي تعطي المعرف.

سيتم وضع موقف البداية ببساطة بواسطة سلسلة من أزواج الموقع. بعد ذلك سيكون هناك زوج موقع واحد لموقع لكل خطوة. يمكنك العثور على نهاية واصف موضع البداية (وبدء واصف التحركات) ببساطة عن طريق العثور على القطعة الأولى المذكورة مرتين. في حالة ترويج البيدق، سيكون هناك 2 بت إضافية تحدد ما يصبحه، لكن معرف القطعة لن يتغير.

لحساب احتمال ترويج البيدق في بداية اللعبة، سيكون هناك أيضا جدول "الترويج" بين أشجار Huffman والبيانات. في البداية سيكون هناك 4 بت يحدد عدد البيدون التي يتم ترقيتها. ثم لكل بيدق سيكون هناك هوية هوفمان المشفرة و 2 بت تحديد ما أصبح.

سيتم إنشاء أشجار Huffman من خلال الأخذ في الاعتبار جميع البيانات (كل من موضع البداية والحركات) وطاولة الترويج. على الرغم من أنه عادة يكون جدول الترويج فارغا أو يحتوي على عدد قليل من الإدخالات.

لتلخيصه في المصطلحات الرسومية:

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

وأضاف: هذا لا يزال من الممكن تحسينه. كل قطعة لديها فقط بعض التحركات القانونية. بدلا من مجرد ترميز المربع المستهدف يمكن للمرء إعطاء معرفات قائمة على التحركات المحتملة لكل قطعة. لن يتم إعادة استخدام نفس المعايير لكل قطعة، لذلك في المجموع لن تكون هناك أكثر من 21 معرفات مختلفة (يمكن أن تحتوي الملكة على أكثر من 21 خيارات خطوة محتملة في 21). ضع هذا في جدول Huffman بدلا من الحقول.

ومع ذلك، فإن هذا قد يقدم صعوبة في تمثيل الحالة الأصلية. قد ينشئ المرء سلسلة من التحركات لوضع كل قطعة في مكانها. في هذه الحالة، سيكون من الضروري وضع علامة بطريقة أو بأخرى نهاية الحالة الأولية وبدء التحركات.

بدلا من ذلك، يمكن وضعها باستخدام معرفات مربعة 6 بت غير مضغوطة.

ما إذا كان هذا سيقدم انخفاضا عاما في الحجم - لا أعرف. ربما، ولكن يجب أن تجرب قليلا.

وأضاف 2: حالة واحدة أكثر خاصة. إذا لم يكن لدى ولاية اللعبة، يصبح من المهم التمييز الذي يتحرك بعد ذلك. أضف واحدا آخر في النهاية لذلك. :)

تم تحريره بعد قراءة السؤال بشكل صحيح] إذا افترضت أن كل موقف قانوني يمكن الوصول إليه من الموضع الأولي (وهو تعريف محتمل "قانوني")، فيمكن التعبير عن أي موقف على أنه تسلسل التحركات من البداية. يمكن التعبير عن مقتطف من اللعب بدءا من موقف غير قياسي كسلسلة من التحركات اللازمة للوصول إلى البداية، مفتاح التبديل لإيقاف تشغيل الكاميرا، متبوعا بالتحركات اللاحقة.

لذلك دعونا نسمي الدولة المجلس الأولية الدولة قليلا "0".

يمكن تعداد التحركات من أي موقف عن طريق ترقيم المربعات وتطلب التحركات عن طريق (البدء والنهاية)، مع القفز التقليدي المربع الذي يشير إلى الصدع. ليست هناك حاجة لترميز التحركات غير القانونية، لأن موقف مجلس الإدارة والقواعد معروفة بالفعل بالفعل. يمكن التعبير عن العلم لإيقاف تشغيل الكاميرا كحركة خاصة داخل النطاق، أو أكثر معقولين كرقم خطوة خارج النطاق.

هناك 24 خطوة فتح لأي من الجانبين، والتي يمكن أن يصلح في 5 بت لكل منهما. قد تتطلب التحركات اللاحقة بت أكثر من أجزاء أكثر أو أقل، ولكن التحركات القانونية غير قابلة لها دائما، لذلك يمكن أن ينمو عرض كل خطوة لحسن الحظ أو التوسع. لم أتحسب، لكنني أتصور مواقف 7 بت سيكون نادرا.

باستخدام هذا النظام، يمكن ترميز لعبة 100 خطوة في حوالي 500 بت. ومع ذلك، قد يكون من الحكمة استخدام كتاب الافتتاح. لنفترض أنه يحتوي على مليون سلسلة. دعونا إذن، تشير 0 إلى بداية من اللوحة القياسية، وتشير إلى رقم واحد متبوعا برقم 20 بت من أحدث نسخة منه. قد يتم تقصير الألعاب ذات الفتحات التقليدية إلى حد ما من خلال تقول 20 خطوة أو 100 بت.

هذا ليس أعظم ضغط ممكن، ولكن (بدون كتاب الافتتاح) سيكون من السهل جدا التنفيذ إذا كان لديك بالفعل نموذج الشطرنج، والذي يفترض السؤال.

لمزيد من ضغط، كنت ترغب في طلب التحركات وفقا لاحظية بدلا من ترتيب تعسفي، وترميز التسلسلات المحتملة في عدد أقل من البتات (باستخدام رموز Huffman مثل الأشخاص المذكورين كما ذكر الناس).

إذا لم يكن الوقت الحاسبي مشكلة، فيمكنك استخدام مولد موضعي محتملا محتملا لتعيين معرفات فريدة إلى موضع معين.

من موقف معين يولد أول عدد من المواقف الممكنة في مانور حتمية، على سبيل المثال يبدأ أسفل اليسار إلى أعلى اليمين. يحدد ذلك عدد البتات التي ستحتاج إليها للنقل التالي، وبعض المواقف يمكن أن تكون أقل من ذلك. ثم عندما يتم تخزين هذه الخطوة بالتخزين فقط المعرف الفريد لهذه الخطوة.

تعتبر الترويج والقواعد الأخرى ببساطة تحركات صالحة طالما يتم التعامل معها بطريقة حتمية، على سبيل المثال إلى الملكة، إلى الأسقف، إلى الأسقف كل عدد خطوة منفصلة.

الموضع الأولي هو أصعب ويمكن أن تولد حوالي 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 Movers فقط "فقط" نقل التحركات الصالحة التي تغير موقف التحقق.

معظم الإجابات تجاهلت 3 أضعاف التكرار. لسوء الحظ لمدة 3 أضعاف التكرار، عليك تخزين جميع المناصب التي تم تشغيلها حتى الآن ...

يتطلب الأمر سؤالا أن تخزنه بطريقة فعالة بالفضاء حتى لا نحتاج إلى تخزين الموضع طالما يمكننا إنشاءه من قائمة التحركات (شريطة أن لدينا موقف بداية قياسي). يمكننا تحسين PGN وهذه التي نواجهها. رفع الصوت عاليا هو مخطط بسيط.

هناك 64 مربعات على اللوحة، 64 = 2 ^ 6. إذا قمت بتخزين فقط المربع الأول والأخير في كل خطوة ستأخذ 12 بت (سيتم التعامل مع الترويج لاحقا). لاحظ أن هذا المخطط يغطي بالفعل اللاعبين للتحرك، والقبر، والقطعة التي تم التقاطها، والضبط الخ؛ اعتبارا من هذه يمكن أن تبني من مجرد إعادة تشغيل قائمة النقل.

للحصول على الترويج يمكننا الاحتفاظ بمجموعة منفصلة من المتجهات التي ستقول "عند التحرك N ترويج لقطعة XYZ". يمكننا أن نبقي متجه (int، بايت).

من المغري تحسين (إلى، من) ناقلات أيضا، لأن العديد من هذه المخلفات (إلى، من) ليست ملاءمة في الشطرنج. على سبيل المثال لن تكون هناك انتقال من E1 إلى D8 إلخ. لكنني لم أستطع التوصل إلى أي مخطط. أرحب بأي أفكار أخرى.

لقد فكرت في ذلك لفترة طويلة (+ - 2 ساعة). وليس هناك إجابات واضحة.

على افتراض:

تجاهل الحالة الزمنية (لم يستخدم لاعب أن يكون هناك حد زمني قد يؤدي إلى إجبار التعادل من خلال عدم اللعب)
متى كانت اللعبة لعبت؟!؟ من المهم أن القواعد قد تغيرت مع مرور الوقت (لذلك سوف تتحمل لعبة حديثة في النقطة اللاحقة لعبة حديثة ...) يرجى الرجوع إلى قاعدة البيدق القتلى على سبيل المثال (Wikipedia لديه مشكلة مشهورة للغاية تعرضها)، وإذا كنت تريد للعودة في الوقت المناسب إلى حظ سعيد الأسقف المستخدمة فقط تتحرك ببطء والزهر تستخدم لاستخدامها. الضحك بصوت مرتفع.

... حتى الآن القواعد الحديثة هو. أولا بغض النظر عن التكرار ونقل الحدود التبرعة.

-C 25 بايت مدورة (64B + 32 * 4B + 5B = 325B)

= 64 بت (شيء / لا شيء) + 32 * 4 بتات [1bit = color {black / withe} + 3bit = نوع القطعة {king، queen، bishop، knight، rook، البيدق، movedpawn} nb: moved bawn ... على سبيل المثال، إذا كان آخر مرة نقلت البيدق في الدور السابق مما يدل على أن "EN Passant" ممكن. ] + 5bit للحالة الفعلية (بدوره، en passant، إمكانية التجول أم لا على كل جوانب)

حتى الان جيدة جدا. ربما يمكن تعزيزها ولكن بعد ذلك سيكون هناك طول متغير والترقية لاتخاذ في الاعتبار!؟

الآن، لا تنطبق القواعد التالية فقط عندما يكون اللاعب Apllies لسحب، فهو غير تلقائي! لذلك فكر في هذه التحركات 90 دون التقاط أو نقل البيدق AA أمر ممكن إذا لم يدعو اللاعب إلى رسم! وهذا يعني أن جميع التحركات تحتاج إلى تسجيل ... وتتوفر.

-. العداد ضروري ... ومع ذلك.

فكيف تتعامل مع ذلك؟ ... حسنا حقا لا توجد طريقة. لأنه لا يرغب أي لاعب في رسم، أو أدرك أنه قد حدث. الآن في حالة وجود عداد قد يكفي ... ولكن هنا الحيلة وحتى قراءة قواعد Fide (http://www.fide.com/component/handbook/؟id=124&view=article) لا يمكنني العثور على الإجابة ... ماذا عن فقدان القدرة على التجول. هل هذا تكرار؟ لا أعتقد ذلك ولكن بعد ذلك هو موضوع غير واضح غير موجه، لم يتم توضيحه.

إذن هنا قواعدين هما معقدان أو غير محدد حتى في محاولة لتشفير ... هتافات.

وبالتالي فإن الطريقة الوحيدة لتشفير اللعبة حقا هي تسجيل الكل من البداية ... التي تعارض بعد ذلك (أم لا؟) بسؤال "حالة اللوحة".

نأمل أن هذه المساعدة ... ليس الكثير من الرياضيات :-) فقط لإظهار أن بعض الأسئلة ليست سهلة، مفتوحة جدا للتفسير أو المعرفة المسبقة أن تكون صحيحة وفعالة. لا أحد أعتبره مقابل إجراء مقابلات مع فتح الكثير من علبة الدودة.

التحسين المحتمل على وضع البداية في حل Yacoby

لا يوجد موقف قانوني لديه أكثر من 16 قطعة من كل لون. عدد الطرق لوضع ما يصل إلى 16 قطعة من الأسود و 16 قطعة بيضاء على 64 مربع حوالي 3.63E27. log2 (3.63e27) = 91.55. هذا يعني أنه يمكنك تشفير موضع ولون جميع القطع في 92 بت. هذا أقل من 64 بت من أجل الوظيفة + ما يصل إلى 32 بت من اللون الذي يتطلبه حل Yacoby. يمكنك حفظ 4 بت في أسوأ الحالات على حساب تعقيد كبير في الترميز.

من ناحية أخرى، فإنه يزيد من حجم المواقف مع 5 قطع أو أكثر مفقودة. تمثل هذه المواقف فقط <4٪ من جميع الوظائف، لكنها ربما تكون غالبية الحالات التي تريد تسجيلها بموقف البداية يختلف عن وضع inital.

هذا يؤدي إلى الحل الكامل

تشفير موضع ولون قطع وفقا للطريقة أعلاه. 92 بت.
لتحديد نوع كل قطعة، استخدم رمز Huffman: البيدق: '0'، ROOK: "100"، فارس: "101"، الأسقف: '110'، الملكة: '1110'، الملك: '1111'. يتطلب هذا (16 * 1 + 12 * 3 + 4 * 4) = 68 بت لمجموعة كاملة من القطع. يمكن تشفير موقف اللوحة الكاملة في 92 + 68 = 160 بت كحد أقصى.
تمت إضافة لعبة SHOUD إضافية: Turn: 1 بت، أي القبض ممكن: 4 بتات، "en passant" ممكن: ما يصل إلى 4 بتات (1 بت يخبرها هو الحال و 3 بت يخبر أي واحد). يتم تشفير موضع البداية في = 160 + 9 = 169 بت
للحصول على قائمة التحركات، قم بتعداد جميع التحركات الممكنة لموضع معين وتخزين موضع التحرك في القائمة. تتضمن قائمة التحركات جميع الحالات الخاصة (Castling، en passant، واستقالة). استخدم فقط العديد من البتات حسب الضرورة لتخزين أعلى موضع. في المتوسط، يجب ألا تتجاوز 7 بت لكل خطوة (16 قطعة محتملة و 8 خطوات قانونية لكل قطعة في المتوسط). في بعض الحالات، عندما يتم إجبار هذه الخطوة، فإنها تتطلب فقط 1 بت (نقل أو استقالة).

هناك 32 قطعة على اللوحة. كل قطعة لديها موقف (واحد في 64 مربعات). لذلك تحتاج فقط 32 أعداد صحيحة إيجابية.

أعرف أن 64 وظيفة عقد في 6 بت ولكن لن أفعل ذلك. سأبقي البتات الأخيرة لبضع أعلام (قطعة مسقط، كوينز بيدق)

كليتوسالإجابة جيدة، لكن نسامح أيضا أن ترميز أيضا دورها. إنه جزء من الحالة الحالية، وهو أمر ضروري إذا كنت تستخدم تلك الحالة لقيادة خوارزمية البحث (مثل مشتق ألفا بيتا).

أنا لست مشغل الشطرنج، لكنني أعتقد أن هناك أيضا حالة زاوية أخرى: كم عدد التحركات التي تكررت. بمجرد أن يصنع كل لاعب نفس الخطوة ثلاث مرات، فإن اللعبة هي رسم أو لا؟ إذا كان الأمر كذلك، فأنت بحاجة إلى حفظ هذه المعلومات في الدولة لأنه بعد التكرار الثالث، فإن الحالة هي الآن محطة.

نظرا لأن العديد من الأشخاص الآخرين قد ذكروا أنك يمكن أن تخزين كل من 32 قطعة مربعا، فهناك مربع، وإذا كانوا على اللوحة أم لا، فإن هذا يعطي 32 * (log2 (64) + 1) = 224 بت.

ومع ذلك، لا يمكن للأساقفة أن يشغلوا المربعات السوداء أو البيضاء فقط حتى تحتاج فقط إلى البتات Log2 (32) لهذا الموضع، والتي تعطي 28 * 7 + 4 * 6 = 220 بت.

وبما أن البيادق لا تبدأ في الظهر ويمكن أن تتحرك فقط للمضي قدما، فيمكن أن يكون فقط في 56، ويجب أن يكون من الممكن استخدام هذا القيد للحد من عدد البتات اللازمة للبيدات.

يحتوي مجلس الإدارة على 64 مربعا، ويمكن تمثيله بمقدار 64 بت عرض إذا كان مربعا فارغا أم لا. نحن نحتاج فقط إلى معلومات قطعة إذا كان المربع لديه قطعة. نظرا لأن اللاعب + قطعة تأخذ 4 بت (كما هو موضح سابقا) يمكننا الحصول على الدولة الحالية في 64 + 4 * 32 = 192 بت. رمي في الدور الحالي ولديك 193 بت.

ومع ذلك، نحتاج أيضا إلى تشفير التحركات القانونية لكل قطعة. أولا، نحسب عدد التحركات القانونية لكل قطعة، وإلحاق أن العديد من البتات بعد معرف قطعة مربع كامل. احسبت على النحو التالي:

البيدق: إلى الأمام، الدور الأول إلى الأمام، EN Passant * 2، الترويج = 7 بت. يمكنك الجمع بين الدور الأول للمضي قدما والترويج في بت واحد نظرا لأنها لا يمكن أن تحدث من نفس الموقف، لذلك لديك 6. Rook: 7 مربعات عمودي، 7 مربعات أفقية = 14 بت نايت: 8 مربعات = 8 Bits Bithop: 2 Diagonals * 7 = 14 Bits Queen: 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 بت (× النقالة، ذ موايات).

تتطلب المواقف الأولية بحد أقصى 320 بت (32 قطعة، 4 + 6 بت)

يمكن تمثيل كل خطوة لاحقة بمقدار 16 بت (من موقف، إلى موقف، قطعة).

سيتطلب الصدع 16 بت إضافية، لأنها خطوة مزدوجة.

يمكن تمثيل البيدون اللوزة من قبل واحدة من 4 القيم الغريبة من 4 بت.

بدون القيام الرياضيات بالتفصيل، يبدأ هذا في توفير مساحة بعد التحرك الأول مقارنة بتخزين 32 * 7 بت (صفيف محددة مسبقا من القطع) أو 64 * 4 بت (تعيين المربعات المحددة مسبقا)

بعد 10 خطوات على كلا الجانبين، والحد الأقصى المساحة المطلوبة هو 640 بت

... ولكن بعد ذلك مرة أخرى، إذا حددنا كل قطعة فريدة (5 بت) وإضافة بتسا سادسا للبيديون ملطخة، فإننا نحتاج فقط إلى معرف قطعة + إلى موقف لكل خطوة. هذا يغير الحساب إلى ...

الوظائف الأولية = ماكس 384 بت (32 قطعة، 6 + 6 بت) كل خطوة = 12 بت (إلى وضع، معرف قطعة)

ثم بعد 10 يتحرك على كل جانب، فإن الحد الأقصى للمساحة المطلوبة هو 624 بت

مثل روبرت G, كنت تميل إلى استخدام بى جى لأنه معيار يمكن استخدامها من قبل مجموعة واسعة من الأدوات.

ولكن ، إذا أنا ألعب الشطرنج منظمة العفو الدولية أن هناك في الفضاء البعيد التحقيق ، وبالتالي كل شيء ثمين ، هذا هو ما أريد القيام به من أجل التحركات.سآتي بوك إلى ترميز الحالة الأولية في وقت لاحق.

التحركات لا تحتاج إلى سجل الدولة ؛ فك يمكن أن تأخذ تتبع الدولة وكذلك ما التحركات القانونية في أي وقت.كل التحركات تحتاج إلى السجل الذي من مختلف البدائل القانونية هو المختار.منذ اللاعبين بالتناوب ، وهي الخطوة لا تحتاج إلى تسجيل لاعب اللون.حيث لاعب يمكن أن تتحرك إلا اللون الخاصة بهم قطع الخيار الأول هو الذي قطعة لاعب يتحرك (سأعود إلى البديل الذي يستخدم خيار آخر في وقت لاحق).في معظم 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 بت

منذ عدد من الخيارات ليست دائما قوة اثنين المذكورة أعلاه لا تزال النفايات بت.افترض عدد من الخيارات ج و خيار معين يتم ترقيم ج, ، n = سقف(lg(ج)) (عدد البتات المطلوبة لترميز الاختيار).علينا الاستفادة من هذه المهدرة القيم من خلال دراسة أكثر من خيار المقبل.إذا كان 0 ، لا تفعل شيئا.إذا كان 1 ، ج+ج < 2ⁿ, ثم يضاف ج إلى ج.فك عددا عكس هذا:إذا حصل ج >= ج, طرح ج وتعيين أول بت على الرقم التالي إلى 1.إذا ج < 2ⁿ-ج, ثم تعيين أول بت على الرقم التالي إلى 0.إذا 2ⁿ-ج <= ج < ج, ثم لا تفعل شيئا.استدعاء هذا المخطط "التشبع".

آخر محتمل هو نوع من الخيار الذي قد تقصر الترميز هو اختيار المعارضين قطعة لالتقاط.وهذا يزيد من عدد من الخيارات في الجزء الأول من هذه الخطوة ، اختيار قطعة في معظم إضافية بت (العدد الدقيق يعتمد على كيفية العديد من القطع الحالية لاعب يمكن ان تتحرك).هذا الاختيار تليها خيار التقاط قطعة ، والتي ربما تكون أصغر بكثير من عدد من التحركات لأي من إعطاء اللاعبين القطع.قطعة يمكن أن يكون إلا لهجوم من قطعة واحدة من أي الكاردينال اتجاه بالإضافة إلى فرسان مجموعه على الأكثر 10 مهاجمة قطع.هذا يعطي مجموع الحد الأقصى من 9 بت القبض على التحرك ، على الرغم من أنني أتوقع 7 بت في المتوسط.هذا سيكون من المفيد بشكل خاص على يلتقط من قبل الملكة ، لأنه غالبا ما يكون قليل القانونية الوجهات.

مع التشبع التقاط ترميز ربما لا تحمل ميزة.نحن يمكن أن تسمح لكل الخيارات في تحديد الحالة الأولية التي تستخدم.إذا تشبع لا يستخدم, لعبة الترميز يمكن أيضا استخدام غير المستخدمة اختيار أرقام (ج <= ج < 2ⁿ) لتغيير الخيارات خلال المباراة.في أي وقت ج هو قوة اثنين لم نستطع تغيير الخيارات.

توماس له النهج الصحيح لترميز المجلس. ومع ذلك، يجب دمج هذا مع نهج رالو لتخزين التحركات. قم بإجراء قائمة بجميع التحركات الممكنة، وكتاب عدد البتات اللازمة للتعبير عن هذا الرقم. نظرا لأن فك التشفير يقوم بنفس الحساب الذي يعرفه عدد ممكن ويمكن أن يعرف عدد البتات التي يجب قراءتها، لا حاجة إلى رموز طولها.

وبالتالي نحصل على 164 بت من القطع، 4 بت من معلومات الصدع (على افتراض أننا نقوم بتخزين جزء من اللعبة، وإلا فإنه يمكن إعادة بناءه)، 3 بت من معلومات الأهلية EN - ببساطة تخزين العمود التي حدثت فيها هذه الخطوة ( إذا لم يكن Passant غير ممكن تخزين عمود حيثما غير ممكن - يجب أن تكون هذه الأعمدة موجودة) و 1 من هو التحرك.

عادة ما تأخذ التحركات 5 أو 6 بت ولكن يمكن أن تختلف من 1 إلى 8.

واحد اختصار إضافي - إذا بدأ الترميز ب 12 1 بت (موقف غير صالح - لن يكون هناك جزء حتى ملوكا على جانب واحد) يمكنك إحباط الشفافة، ومسح اللوحة وإعداد لعبة جديدة. سيكون بت القادمة قليلا.

يجب أن تعداد الخوارزمية تعداد جميع الوجهات المحتملة في كل خطوة. عدد الوجهات:

2 أساقفة، 13 وجهة لكل منهما = 26
2 Rooks، 14 وجهة لكل منهما = 28
2 فرسان، 8 وجهات لكل = 16
الملكة، 27 وجهات
الملك، 8 وجهات

8 أقدام يمكن أن تصبح كل كوينز في أسوأ (حالة التعداد)، مما يجعل أكبر عدد من الوجهات المحتملة 9 * 27 + 26 + 28 + 16 + 8 = 321. وبالتالي، يمكن تعداد جميع الوجهات لأي خطوة برقم 9 بت.

الحد الأقصى لعدد التحركات لكل من الطرفين هو 100 (إذا لم أكن مخطئا، وليس لاعب شطرنج). وبالتالي يمكن تسجيل أي لعبة في 900 بت. بالإضافة إلى الموضع الأولي يمكن تسجيل كل قطعة باستخدام أرقام 6 بت، والتي بلغت إجمالتها إلى 32 * 6 = 192 بت. بالإضافة إلى بت واحد ل "من يتحرك أولا" سجل. وبالتالي، يمكن تسجيل أي لعبة باستخدام 900 + 192 + 1 = 1093 بت.

تخزين ولاية مجلس الإدارة

أبسط الطريقة التي فكرت بها هي لأول مرة أيضا لها صفيف من 8 * 8 بت تمثل موقع كل قطعة (حتى 1 إذا كانت هناك قطعة شطرنج هناك و 0 إذا لم يكن هناك). لأن هذا هو طول ثابت لا نحتاج إلى أي المنهي.

تمثل التالي كل قطعة شطرنج حسب موقعها. باستخدام 4 بت لكل قطعة، يستغرق هذا 32 * 4 بت (128 في المجموع). وهو حقا مهدر حقا.

باستخدام شجرة ثنائية، يمكننا أن نمثل بيدق في بايت واحد، فارس وغرور والأسقف في 3 وملك وملكة في 4. كما نحتاج أيضا إلى تخزين لون القطعة، والتي تأخذ بايت إضافية تنتهي كما (سامحني إذا كان هذا خطأ، لم أنظر أبدا هوفمان الترميز بأي تفصيل من قبل):

البيدق: 2.
الروك: 4.
نايت: 4.
الأسقف: 4.
الملك: 5.
الملكة: 5.

بالنظر إلى المجاميع:

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

الذي يدق باستخدام مجموعة حجم ثابت من البتات بنسبة 28 بت.

لذلك أفضل طريقة وجدتها هي تخزينها في 8² + 100 بت صفيف

8*8 + 100 = 164

تخزين التحركات
أول شيء نحتاج إليه هو أن تنتقل قطعة إلى أين. بالنظر إلى أن هناك بحد أقصى 32 قطعة على اللوحة، ونحن نعرف ما هي كل قطعة، بدلا من عدد صحيح يمثل المربع، يمكننا أن يكون لدينا عدد صحيح يمثل تعويض القطعة، مما يعني أننا يتعين علينا فقط أن تناسب 32 قيما محتملة لتمثيل قطعة.

لسوء الحظ، هناك العديد من القواعد الخاصة، مثل الصدع أو الإطاحة بالملك وتشكيل جمهورية (مرجع بر بريشت)، لذلك قبل تخزين القطعة للتحرك، نحتاج إلى بعض الشيء مما يدل على ما إذا كانت خطوة خاصة أم لا.

لذلك لكل خطوة طبيعية لدينا اللازمة 1 + 5 = 6 بت. (نوع 1 بت، 5 بت قطعة)

بعد فك شفرة رقم القطعة، فإننا نعرف بعد ذلك نوع القطعة، وكل قطعة يجب أن تمثل حركتها بطريقة الأكثر كفاءة. على سبيل المثال (إذا كانت قواعد الشطرنج هي ما يصل إلى خدش)، فإن البيدق يحتوي على ما مجموعه 4 تحركات ممكنة (تأخذ اليسار، واتخاذ الحق، ونقل واحدة إلى الأمام، وانتقل اثنين إلى الأمام).
لذلك لتمثيل خطوة البيدق نحتاج إلى أجزاء "6 + 2 = 8". (6 بت لرأس الخطوة الأولية، 2 بت من أجل التحرك)

إن التحرك للملكة سيكون أكثر تعقيدا، حيث سيكون من الأفضل الحصول على اتجاه (8 اتجاهات ممكنة، لذلك 3 بت) وما مجموعه 8 مربعات محتملة للانتقال إلى كل اتجاه (حتى 3 بت آخر). لتمثيل تحريك ملكة سيتطلب 6 + 3 + 3 = 12 بت.

آخر شيء تكرار لي هو أننا نحتاج إلى تخزين اللاعبين الذين يحولونها. يجب أن يكون هذا قليلا (أبيض أو أسود للتحرك بعد ذلك)

تنسيق ناتج
لذلك سوف ينظر تنسيق الملف شيئا مثل هذا

64 بت] مواقع القطعة الأولية
100 بت كحد أقصى] قطع أولية [1 بت
N بت] يتحرك

حيث تتحرك
1 بت] نقل نوع (خاص أو طبيعي)
n بت] حرك التفاصيل

إذا كانت هذه الخطوة خطوة طبيعية، فإن تفاصيل الخطوة تبدو مثل
5 بت] قطعة
N بت] خطوة قطعة محددة (عادة في حدود 2 إلى 6 بت

إذا كانت خطوة خاصة
يجب أن يكون لها نوع عدد صحيح ثم أي معلومات إضافية (مثل إذا كان الصدع). لا أستطيع أن أتذكر عدد التحركات الخاصة، لذلك قد يكون موافقا فقط للإشارة إلى أنها خطوة خاصة (إذا كان هناك واحد فقط)

في حالة قاعدة الأولية المجلس بالإضافة إلى التحركات اللاحقة ، والنظر في ما يلي.

استخدام برنامج شطرنج تعيين الاحتمالات أن كل التحركات الممكنة.على سبيل المثال ، 40 ٪ e2 e4 20% d2-d4, وهلم جرا.إذا كان بعض التحركات القانونية ولكن لا يعتبر هذا البرنامج ، ومنحهم بعض احتمال ضعيف.استخدام الترميز الحسابي لإنقاذ التي كان الخيار اتخاذها ، والتي سوف يكون عدد بين 0 و 0.4 لأول التحرك 0.4 و 0.6 الثانية وهكذا.

تفعل الشيء نفسه على الجانب الآخر.على سبيل المثال, إذا كان هناك فرصة 50 ٪ من e7-e5 الاستجابة e2 e4 ثم ترميز عدد بين 0 و 0.2.كرر حتى يتم اللعبة.النتيجة المحتملة في نطاق صغير جدا.العثور على كسر ثنائية مع أصغر القاعدة التي تناسبها في هذا النطاق.هذا الترميز الحسابي.

هذا هو أفضل من هوفمان لأنه يمكن اعتبار كسور بت ترميز (بالإضافة إلى بعض في نهاية اللعبة لجمع كل بت).

يجب أن تكون النتيجة أكثر إحكاما من هوفمان, و لا توجد حالات خاصة من أجل تعزيز عابرة ، 50 قاعدة التحرك ، وغيرها من التفاصيل لأن يتم التعامل معها من قبل الشطرنج تقييم البرنامج.

إلى إعادتها مرة أخرى استخدام الشطرنج برنامج لتقييم المجلس تعيين كل الاحتمالات في كل خطوة.استخدام الحساب ترميز قيمة لتحديد الخطوة لعبت في الواقع.كرر حتى يتم ذلك.

إذا الشطرنج الخاص بك البرنامج هو جيد بما فيه الكفاية, يمكنك الحصول على أفضل ضغط مع الدولتين التشفير حيث احتمالات محددة على أساس حركات كل من الأبيض والأسود.في الحالة الأكثر تطرفا من بعض 200+ ، بترميز مجموعة كاملة من ألعاب الشطرنج ، وبالتالي ليس ممكنا.

هذا هو الى حد كبير طريقة مختلفة تقول ما داريوس بالفعل كتب فقط مع قليل من الأمثلة على كيفية الترميز الحسابي قد عمل ، مثال حقيقي من استخدام القائمة الشطرنج برنامج للمساعدة في تقييم احتمال الخطوة التالية(s).

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow