جدول التبديل

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

تُنفَّذ جداول التبديل عادةً كجداول تجزئة ، حيث يُشفِّر فهرس التجزئة موضع اللوحة الحالي. عدد المواضع المحتملة في شجرة اللعبة دالة أسية لعمق البحث، وقد يتراوح بين الآلاف والملايين أو حتى أكبر بكثير. لذا، قد تستهلك جداول التبديل معظم ذاكرة النظام المتاحة، وعادةً ما تُشكِّل الجزء الأكبر من مساحة الذاكرة التي تشغلها برامج تشغيل الألعاب.

تعمل برامج محاكاة الألعاب بتحليل ملايين الوضعيات المحتملة في النقلات القليلة القادمة. عادةً، تستخدم هذه البرامج استراتيجيات مشابهة للبحث العميق ، ما يعني أنها لا تحتفظ بسجل لجميع الوضعيات التي تم تحليلها حتى الآن. في العديد من الألعاب، يمكن الوصول إلى وضعية معينة بأكثر من طريقة، وتُسمى هذه الوضعيات بالتبديلات . ^{[ 1 ]} في الشطرنج ، على سبيل المثال، سلسلة النقلات 1. d4 Nf6 2. c4 g6 (انظر تدوين الشطرنج الجبري ) لها 4 تبديلات ممكنة، حيث يمكن لأي من اللاعبين تبديل ترتيب نقلاته. بشكل عام، بعد n نقلة، يكون الحد الأقصى للتبديلات الممكنة هو ( n !) ^² . على الرغم من أن العديد من هذه التبديلات غير قانونية، فمن المرجح أن يقوم البرنامج بتحليل الوضعية نفسها عدة مرات.

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

غالبًا ما يتجاوز عدد المواضع التي يبحث فيها الحاسوب قيود الذاكرة الخاصة بالنظام الذي يعمل عليه؛ لذا لا يمكن تخزين جميع المواضع. وعندما يمتلئ الجدول، تُزال المواضع الأقل استخدامًا لإفساح المجال لمواضع جديدة؛ وهذا ما يجعل جدول التبديل بمثابة ذاكرة تخزين مؤقتة .

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

يمكن استخدام جدول التجزئة الذي يُنفذ جدول النقل لأغراض أخرى غير إيجاد عمليات النقل. في تقليم ألفا-بيتا ، يكون البحث أسرع (بل مثاليًا) عندما يُؤخذ في الاعتبار دائمًا أولًا الابن للعقدة التي تُمثل أفضل نقلة. بالطبع، لا توجد طريقة لمعرفة أفضل نقلة مسبقًا، ولكن عند استخدام التعميق التكراري ، تُعتبر النقلة التي وُجد أنها الأفضل في بحث سطحي تقريبًا جيدًا. لذلك، تُجرَّب هذه النقلة أولًا. ولتخزين أفضل ابن لعقدة ما، يُستخدم المدخل المُقابل لتلك العقدة في جدول النقل.

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

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

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

على الرغم من أن نسبة العقد التي ستكون عبارة عن تبديلات ضئيلة، إلا أن شجرة اللعبة ذات بنية أسية، لذا فإن تخزين عدد قليل جدًا من هذه العقد مؤقتًا يمكن أن يُحدث فرقًا كبيرًا. في الشطرنج، تم الإبلاغ عن انخفاض في وقت البحث بنسبة 0-50% في وضعيات منتصف اللعبة المعقدة، وما يصل إلى خمسة أضعاف في نهاية اللعبة. ^{[ 2 ]}

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

• خوارزمية مينيمكس
• تقليم ألفا-بيتا
• تجزئة زوبريست

• جداول النقل Sigmachess.com
• معلومات فنية: جدول النقل الرئيسي (معلومات حول بنية البيانات والتنفيذ)
• تشريح برامج الشطرنج، إعداد: تي إيه مارسيلاند، جامعة ألبرتا
• جدول التبديلات - ويكي برمجة الشطرنج