شطرنج الحاسوب
طرق الحاسوب

تعود بدايات الآلات التي تلعب الشطرنج إلى السنوات الأولى من القرن العشرين حيث كانت هناك بعض الآلات الميكانيكية التي كانت تلعب نهاية لعبة ملك ضد قلعة وبعض الآلات الكهربائية التي كانت تلعب ألعابًا أخرى مثل لعبة هيكس،
سعى العلماء والمنظرون إلى تطوير آلة قادرة على التعلم والتفكير وتطبيق ما تتعلمه مثل البشر، ونظرا لتعقيد لعبة الشطرنج، فقد كان صنع آلة تستطيع أن تلعبها أحد الاهداف الاساسية التي سعى اليها مطورو الذكاء الاصطناعي، بدءا من النصف الأخير من القرن العشرين صممت العديد من المخططات المختلفة للحواسيب لتكون قادرة على لعب الالعاب الذهنية مثل الشطرنج والداما.يمكن للاعب الشطرنج البشري تحديد الحركات الأفضل بشكل واضح والاستراتيجية المناسبة بغض النظر عن عدد الحركات اللازمة، ولكن يجب أن يكون الحاسوب منهجيًا في تحليله بحيث يعرض كل الحركات الممكنة من الوضعية الحالية واختيار أفضل حركة ممكنة.
يتفق معظم اللاعبين على أن توقع ما لا يقل عن خمس حركات للأمام (عشر مرات) عند الضرورة مطلوب للعب بشكل جيد.  تمنح قواعد البطولة العادية كل لاعب ثلاث دقائق في المتوسط لكل نقلة.  في المتوسط، هناك أكثر من 30 حركة قانونية لكل موضع شطرنج، لذلك يجب على الكمبيوتر فحص كوادريليون احتمالية للنظر إلى الأمام لعشر حركات (خمس حركات كاملة)؛  فإذا كان بأمكان الحاسوب فحص مليون إحتمالية في الثانية فإنه سيحتاج إلى أكثر من 30 عامًا.
كانت المحاولات الأولى لصنع حاسوب يلعب الشطرنج سبقت العصر الإلكتروني، لكن كان الكمبيوتر الرقمي للبرنامج المخزن هو ما أعطى مجالًا لحساب معقد إلى هذه الدرجة.  وضع كلود شانون، في عام 1949، مبادئ الذي اعتقد أن بإمكانها حل الشطرنج حسابيا. حيث تُمَثل اللعبة «كشجرة»، أو بنية بيانات رقمية من الخيارات (الفروع) المقابلة للحركات.  كانت عُقد الشجرة عبارة عن المواضع على اللوحة الناتجة عن خيارات النقل. ولكن كان واضحا منذ البداية استحالة تمثيل مباراة شطرنج كاملة في شجرة
يوجد ما معدله 36 حركة لكل موضع في الشطرنج وتستمر اللعبة المتوسطة حوالي 35 حركة حتى تنتهي بالأنسحاب ومن 60-80 حركة إذا انتهت بكش ملك مات أو ردب أو تعادل من نوع آخر.  هناك 400 إحتمالية ممكنة بعد النقلة الأولى لكل لاعب، وحوالي 200000 إحتمالية بعد النقلة الثانية لكل منهما، وحوالي 120 مليون إحتمالية بعد النقلة الثالثة لكل منهما.  لذلك اقترحت نظرة محدودة (بحث) في موضع معين، متبوعًا باستخدام المعرفة الخاصة بالمجال لتقييم المواقف النهائية الناتجة  سينتج عن ذلك وضع متوسط، بالنظر إلى التحركات الجيدة من كلا الجانبين، وسيُعلم تقييمه اللاعب بجودة أو سوء الحركات المختارة.  كانت عمليات البحث والمقارنة على الشجرة مناسبة تمامًا للحواسيب ؛  لم يكن من الممكن تمثيل معرفة الشطرنج الدقيقة في وظيفة التقييم كذلك.  عانت برامج الشطرنج المبكرة في كلا المجالين: البحث في الشجرة الضخمة يتطلب موارد حسابية تفوق بكثير تلك المتاحة، وما هي معرفة الشطرنج المفيدة وكيف سيتم تشفيرها مما اسستغرق عقودًا لاكتشافها.
نموذج تقييم مبكر يسمى تقييم الفا بيتا، وهو نظام يحدد عددا محددا من نتائج الشجرة والبحث عن أفضل خيار بين هذه الخيارات أدى هذا بطبيعة الحال إلى ما يشار إليه باسم «البحث الانتقائي»، وذلك باستخدام معرفة الشطرنج (الاستدلال) لاختيار بعض الحركات التي يفترض أنها جيدة من كل وضعية، وتقليم الآخرين وتجاهل باقي الحركات.ولكن كلما كثر عدد الحركات اللازمة كلما ظهر ضعف هذا النظام وقد لا تحدد جودة أو سوء الحركة للعديد من الحركات في اللعبة، لذلك غالبًا ما يؤدي البحث الانتقائي إلى تقليم أفضل حركة أو حركات.  تم إحراز تقدم ضئيل أو لم يتم إحراز أي تقدم على مدى السنوات الخمس والعشرين التالية التي سيطر عليها نموذج البحث الانتقائي.  كان أفضل برنامج تم إنتاجه خلال هذا الوقت هو ماك هاك بي إل في عام 1967 ؛ حيث كان يلعب الشطرنج على مستوى الهواة (فئة C على وفق تصنيف اتحاد الشطرنج الأمريكي).
في عام 1974، استخدم نموذج بحث آخر لأول مرة في برنامج جامعة نورث وسترن للشطرنج 4.0، وهو البديل الموصوف في ورقة شانون عام 1949، والذي يسمى بنظام (العرض الكامل أو «القوة الغاشمة»).  في هذا النهج، يتم البحث عن جميع الحركات الموجودة في وضعية معينة وتقييمها، لحركة أو حركتين لا أكثر.  اكتشفوا أن الوقت اللازم للبحث في جميع الحركات كان أقل بكثير من الوقت المطلوب لتطبيق الاستدلال المعرفي المكثف لاختيار عدد قليل منها فقط، كما أن فائدة عدم تجاهل الحركات الجيدة قبل الأوان أو عن غير قصد أدت إلى أداء أقوى بشكل كبير.
واجه مطورو برامج الحاسوب القادرة على لعب الشطرنج مشاكل متنوعة مثل:
واجهة المستخدم الرسومية (GUI) - كيف تدخل الحركات عليها من طرف الحاسوب وما هي طريقة إبلاغ المستخدم بها، وكيفية تسجيل النقلة، وكيفية ضبط عناصر التحكم في الوقت، واعتبارات الواجهة الأخرى
تقنيات البحث - كيفية تحديد الحركات الممكنة واختيار الحركات الأفضل من موضع معين ؛
تقييم الورقة - كيفية تقييم قيمة مركز اللوحة، إذا لم يتم إجراء بحث من هذا الموضع.
واجهة المستخدم الرسومية
تدعم برامج الشطرنج الحاسوبية عادة عددًا من المعايير الواقعية الشائعة.  يمكن لجميع برامج اليوم تقريبًا قراءة وكتابة حركات اللعبة على أنها تدوين الألعاب المحمولة (PGN)، ويمكنها قراءة وتدوين الوضعيات المختلفة غالبًا ما تفهم برامج الشطرنج الأقدم تدوينًا جبريًا طويلًا فقط، لكن المستخدمين اليوم يتوقعون أن تفهم برامج الشطرنج تدوين الشطرنج القياسي.
منذ أواخر التسعينيات، بدأ المبرمجون في تطوير محركات منفصلة (بواجهة سطر أوامر تحسب الحركات الأقوى في الموضع) أو واجهة المستخدم الرسومية (GUI) التي تزود اللاعب بلوحة شطرنج يمكنهم رؤيتها وقطعه التي يمكن نقلها بنقرة اصبع.  تنقل المحركات تحركاتها إلى واجهة المستخدم الرسومية باستخدام بروتوكول مثل بروتوكول اتصال محرك الشطرنج (CECP) أو واجهة الشطرنج العالمية (UCI).  من خلال تقسيم برامج الشطرنج إلى هاتين القطعتين، يمكن للمطورين برمجة واجهة الحاسوب لوحدها، أو المحرك لوحده، دون الحاجة إلى برمجة كلا الجزأين معا.
يجب على المطورين أن يقرروا ما إذا كانوا يريدون تزويد المحرك بتعليمات عن الأفتتاحيات أو قواعد نهاية اللعبة أو ترك ذلك لواجهة المستخدم الرسومية.
لوحة التحكم
تعتبر بنية البيانات المستخدمة لتمثيل كل موقع في الشطرنج أداة لفهم الحركة وتقييم الموقع، تتضمن اماكن خزن البيانات القطع المخزنة في («الذاكرة»)، ومواضع القطع المخزنة في قائمة («قائمة القطع»)، ومجموعات مجموعات دراسة حركات القطع («لوحات البت»)، بالأضافة إلى اماكن لتخزين حركات المباراة طويل المدى.
تقنيات البحث
تعتبر برامج الشطرنج الحاسوبية حركات الشطرنج بمثابة تفرعات لشجرة اللعبة الاساسية.  من الناحية النظرية، يجب عليها أن تفحص جميع الحركات، ثم كل الحركات التي يمكن أن يقوم بها الخصم للتصدي لتلك الحركات، ثم كل الحركات التي تصد الحركات التي سيتحركها الخصم، وهكذا، حيث يُطلق على كل حركة فردية يقوم بها لاعب ب «الطية».  يستمر هذا التقييم حتى حد أقصى معين لعمق البحث أو يحدد البرنامج أنه قد وصل إلى موضع نهائي مثل كش مات.  في كل حركة يحدد الحاسوب أفضل نقلة ممكنة للاعب ؛  يحاول كلا اللاعبين جعل الوضعية أفضل بالنسبة له. مما يؤدي إلى التوصل إلى عقدة طرفية معينة يمثل تقييمها القيمة التي تم البحث عنها للموضع.  يتم دعم قيمته إلى الجذر، ويصبح هذا التقييم تقييمًا للموقف على اللوحة.  عملية البحث هذه تسمى «مينيكس».
لا يمكن للتطبيق السالك لهذا النهج إلا البحث في لعدد حركات قليل في فترة زمنية عملية، لذلك تم ابتكار طرق مختلفة لتسريع البحث عن حركات جيدة بشكل كبير.
كانت الورقة الأولى عن هذا الموضوع بقلم كلود شانون عام 1950.  لقد توقعت استراتيجيتي البحث الرئيسيتين المحتمل استخدامهما، والتي أطلق عليها «النوع أ» و «النوع ب»، قبل أن يقوم أي شخص ببرمجة جهاز كمبيوتر للعب الشطرنج.
تستخدم برامج النوع أ نهج «القوة الغاشمة»، حيث تقوم بفحص كل موضع ممكن لعدد ثابت من الحركات باستخدام خوارزمية مينيكس.  اعتقد شانون أن هذا سيكون غير عملي لسببين.
أولاً، مع وجود ما يقرب من ثلاثين حركة ممكنة في وضع نموذجي من الحياة الواقعية، توقع أن يستغرق البحث في المواضع الـ 109 تقريبًا المتضمنة في البحث عن ثلاث حركات للأمام لكلا الجانبين (ستة حركات) حوالي ستة عشر دقيقة، حتى في الحالة «المتفائلة جدًا» بحيث أن حاسوب الشطرنج قادر على تقييم مليون موقع كل ثانية.  (استغرق الأمر حوالي أربعين عامًا لتحقيق هذه السرعة).
ثانيًا، تجاهل مشكلة السكون، محاولًا فقط تقييم مركز يقع في نهاية تبادل القطع أو تسلسل مهم آخر من الحركات («الخطوط»).  فقد توقع أن تكييف النوع أ للتعامل مع هذا سيزيد بشكل كبير من عدد الوظائف التي يجب النظر إليها وسيبطئ البرنامج أكثر.
بدلاً من إهدار قوة المعالجة في فحص التحركات السيئة أو التافهة، اقترح شانون أن برامج «النوع ب» ستستخدم تحسينين:
توظيف بحث هادئ.
انظر فقط إلى عدد قليل من الحركات الجيدة لكل مركز.
سيمكنهم هذا من النظر إلى الأمام («أعمق») في أهم الأحتمالات في وقت معقول.
لقد أثبت اختبار الزمن أن النوع أ هو الأفضل،  تستخدم جميع البرامج الحديثة بحثًا عن السكون الطرفي قبل تقييم الوظائف.  بينما فشل النوع ب (الذي يسمى اليوم بالتقييم الأمامي) لصالح امتدادات البحث.
أجرى أدريان دي جروت مقابلات مع عدد من لاعبي الشطرنج من مستويات متفاوتة، واستنتج أن كلا من الأساتذة والمبتدئين يقيمون حوالي أربعين إلى خمسين حركة مختلفة قبل أن يقرروا أي خطوة يلعبونها.  ما يجعل اللاعبين ذوي الخبرة أفضل بكثير من غيرهم هو أنهم يستخدمون مهاراتاهم للتعرف على الأنماط المبنية على التجربة بناء على الحركات التي اتخذوها أو اتخذها خصومهم في مواقف مشابهة، وهذا يمكّنهم من فحص بعض الأحتمالات بعمق أكبر من غيرها من خلال عدم التفكير ببساطة في الحركات التي يمكنهم افتراض أنها سيئة مقدما.
المزيد من الأدلة على ذلك هو الطريقة التي يجد بها اللاعبون الجيدون أنه من الأسهل تذكر المواقف من مباريات الشطرنج الحقيقية، وتقسيمها إلى عدد صغير من المواضع الفرعية التي يمكن التعرف عليها، بدلاً من الترتيبات العشوائية تمامًا من نفس القطع.  في المقابل، يتمتع اللاعبون متوسطو المستوى بنفس مستوى الاستدعاء لكليهما.
تكمن مشكلة النوع ب في أنه يعتمد على قدرة البرنامج على تحديد الحركات الجيدة بما يكفي لتكون جديرة بالاهتمام (`` معقولة '') في أي موضع معين، وقد ثبت أن تمييز هذه الحركات أصعب بكثير من أن تكون اسرع مت عمليات بحث مع الأجهزة المتفوقة وتقنيات امتداد البحث.
فازت برامج البحث الكامل للعرض («القوة الغاشمة») لسبب بسيط هو أن برامجهم لعبت شطرنج بشكل أفضل.  لم تحاول مثل هذه البرامج تقليد عمليات التفكير البشري، ولكنها اعتمدت على عمليات البحث الكاملة مثل تقييك ألفا بيتا.  تضمنت معظم هذه البرامج (بما في ذلك جميع البرامج الحديثة اليوم) أيضًا جزءًا انتقائيًا محدودًا إلى حد ما من البحث استنادًا إلى عمليات البحث عن الربح، وعادةً ما تكون الامتدادات والتقييمات (خاصة تقييم الحركة الفارغة من التسعينيات وما بعده) والتي تم تشغيلها بناءً على شروط معينة في محاولة للتخلص من الحركات السيئة الواضحة (تحركات التاريخ) أو تقليلها أو للتحقق من النتائج المثيرة للاهتمام (مثل القيام بكش، البيادق المارة في المرتبة السابعة، إلخ)  ومع ذلك، يجب استخدام مشغلات التمديد والتقييم بعناية فائقة.  على المدى الطويل ولا تزال البرامج تهدر الكثير من الوقت في النظر إلى المواقف غير المهمة. ولكن إذا تم تقييم الكثير من الحركات، فهناك خطر استبعاد الحركات المثيرة للاهتمام.  تختلف برامج الشطرنج من حيث طريقو وأنواع وقواعد التقييم والتمديد المدرجة وكذلك في وظيفة التقييم.  يُعتقد أن بعض البرامج أكثر انتقائية من غيرها (على سبيل المثال، كان من المعروف أن ديب بلو أقل انتقائية من معظم البرامج التجارية لأنه كان قادرا على القيام بمزيد من عمليات البحث الكاملة بالعرض الكامل)، ولكن جميعها لديها بحث أساسي كامل العرض كأساس وتحتوي جميعها على بعض المكونات الانتقائية (Q-search، التقليم / الامتدادات).
على الرغم من أن مثل هذه الإضافات تعني أن البرنامج لم يفحص حقًا كل عقدة ضمن عمق البحث الخاص به (لذلك لن تكون قوة غاشمة حقًا بهذا المعنى)، فقد وُجد أن الأخطاء النادرة الناتجة عن عمليات البحث الانتقائية هذه تستحق الوقت الإضافي الذي وفره لأنه يمكنه من البحث بشكل أعمق.  بهذه الطريقة يمكن لبرامج الشطرنج الحصول على أفضل الحركات في وقت اقل.
التحسينات الأخرى
يمكن استخدام العديد من التحسينات الأخرى لجعل برامج الشطرنج أقوى.  على سبيل المثال، تُستخدم جداول الذاكرة لتسجيل الوضعيات التي تم تقييمها مسبقًا، لحفظ إعادة حسابها.  تسجل جداول التفنيد التحركات الرئيسية التي تلغي الحركات التي تبدو أنها جيدة للوهلة الأولى ؛  عادة ما يتم تجربتها أولاً في مواقف مختلفة (حيث من المحتمل أن تدحض الحركة التي تدحض موقفًا آخر).  العيب هو أن جداول الذاكرة في في منتصف اللعب يمكن أن تصبح كبيرة جدًا - عشرات إلى مئات الملايين من الإدخالات.  جدول الذاكرة في الحاسوب ديب بلو لشركة IBM في عام 1996، على سبيل المثال كان يحتوي على 500 مليون إدخال.  يمكن أن تؤدي جداول الذاكرة الصغيرة جدًا إلى قضاء وقت أطول في البحث عن إدخالات غير موجودة مقارنة بالوقت الذي يوفر بواسطة الإدخالات الموجودة.  تستخدم العديد من محركات الشطرنج التأمل والبحث عن مستويات أعمق في وقت الخصم، مثل البشر، لزيادة قوة لعبهم.
تستخدم برامج الشطرنج الحديثة عادةً مجموعة متنوعة من الامتدادات والتخفيضات المستقلة عن المجال، هذا على عكس البحث الانتقائي أو التقييم الأمامي للعصر المبكر: يتم البحث عن جميع الحركات إلى حد ما ؛  يتم تقييم العقد فقط على أساس ما تم العثور عليه، وليس بشكل استباقي من خلال تطبيق معرفة الشطرنج الخاصة بالمجال.
بالطبع، يمكن للأجهزة الأسرع والذاكرة الإضافية تحسين قوة لعب برنامج الشطرنج.  يمكن أن تحسن محركات البحث ذات مؤشرات الترابط العالية الأداء بشكل متواضع إذا كان البرنامج يعمل على محرك بحث واحد أو على عدد صغير من المحركات.  تم تصميم معظم البرامج الحديثة للاستفادة من المحركات المتعددة لإجراء بحث متوازي.  تم تصميم البرامج الأخرى للتشغيل على جهاز حاسوب للأغراض العامة وتخصيص توليد الحركة أو البحث الموازي أو التقييم للمعالجات المخصصة أو المعالجات المشتركة المتخصصة.
سرعة المعالج
في سبعينيات القرن الماضي، كانت معظم برامج الشطرنج تعمل على أجهزة حاسوب عملاقة
مما يشير إلى أنه خلال فترة تطور شطرنج الحاسوب، كانت قوة المعالجة هي العامل المحدد في الأداء.  كافحت معظم برامج الشطرنج للبحث على عمق أكبر من 3 طحركات.  لم تظهر العلاقة بين سرعة المعالج والمعرفة المشفرة في وظيفة التقييم إلا بعد ظهور آلات الشطرنج للأجهزة في الثمانينيات.
تشير التقديرات إلى أن مضاعفة سرعة معالج الحاسوب تكسب ما يقرب من خمسين إلى سبعين نقطة من نقاط Elo في قوة اللعب
التقييم
بالنسبة لمعظم أوضاع الشطرنج، لا يمكن لأجهزة الكمبيوتر الوصول إلى جميع الوضعيات النهائية الممكنة.  بدلاً من ذلك، يجب عليهم النظر إلى الأمام لبضع حركات ومقارنة الوضعيات الناتجة مع بعضها البعض، تسمى الخوارزمية التي تقيم النتائج ب «وظيفة التقييم»، وغالبًا ما تختلف هذه الخوارزميات اختلافًا كبيرًا بين برامج الشطرنج المختلفة.
تقوم وظائف التقييم عادةً بتقييم المواقف في مئات من المواضع المختلفة، والنظر في قيمة الفائدة إلى جانب العوامل الأخرى التي تؤثر على قوة كل جانب.  عند عد قيم القطع لكل جانب، تكون القيم النموذجية للقطع هي نقطة واحدة للبيدق، و 3 نقاط للحصان والفيل، و 5 نقاط للقلعة، و 9 نقاط للملكة.  يُعطى الملك أحيانًا قيمة عالية عشوائية مثل 200 نقطة (ورقة شانون) للتأكد من أن تنفيذ كش مات يفوق كل العوامل الأخرى..
بالإضافة إلى نقاط القطع، تأخذ معظم وظائف التقييم العديد من العوامل في الاعتبار، مثل هيكلة البيادق، وحقيقة أن زوج الفيلة عادةً ما يكون له قيمة أكبر في نهاية اللعبة، والقطع المركزية أكثر قيمة، وما إلى ذلك.  عادة ما يتم النظر في حماية الملوك، وكذلك مرحلة اللعبة الافتتاح أو الوسط أو نهاية اللعبة
ناتج وظيفة التقييم هو عدد قياسي واحد، بناء على عدد بيادق أو وحدات أخرى، وهو مجموع مرجح للعوامل المختلفة الموضحة.  يُفترض أن يمثل التقييم أو يقارب قيمة الشجرة الفرعية أسفل العقدة التي تم تقييمها كما لو كان قد تم البحث عنها حتى النهاية، أي  نهاية اللعبة.  أثناء البحث، تتم مقارنة التقييم مع تقييمات الحركات الأخرى، مما يؤدي إلى استبعاد العقد التي تمثل حركات سيئة أو رديئة لأي من الجانبين، للحصول على عقدة والتي من خلال التقارب، تمثل قيمة الموضع مع أفضل لعب من كلا الجانبين.
لا يوجد إطار تحليلي أو نظري لما يجب أن تحتويه وظيفة التقييم.  كما أنها ليست مخصصة تمامًا.  تتكتل العشرات إلى المئات من العوامل الفردية في شكل ثابت.