حل معضلة الشطرنج الرياضية هذه واحصل على مليون دولار؟
يعرض العلماء جائزة قدرها مليون دولار لأي شخص يتمكّن من حلّ عقدة شيطانية مستعصية في مسألة شطرنج كلاسيكية تدعى: لغز الملكة (الوزير).
الجميل في التحدي أنه ليس عليك حتى الإلمام بقواعد الشطرنج للمشاركة فيه، في نفس الوقت، لا يعني ذلك أنه سيكون سهلًا. في الحقيقة، يقول الباحثون أن الحلّ معقّد رياضيًا جدًا لدرجة أن الوصول إليه قد يستغرق آلاف السنوات.
لوضع الأمور في نصابها، دعنا نعود للبداية.
لغز الوزير (أو كما يطلق عليه أيضًا: لغز الوزراء الثمانية)، نشر أولًا في عام 1848، ويطلب منك وضع ثمانية وزراء على رقعة شطرنج مكونة من ثمانية مربعات على كل جانب، بحيث لا يكون أيّ منها في موقع يهدد آخر.
إذا كنت على دراية بقوانين الشطرنج، فأنت تعلم أن الوزير هو أقوى قطعة على الرقعة، لأنه يستطيع التحرك في ثمانية اتجاهات -أعلى وأسفل وإلى الجانبين وقطريًا- بالإضافة إلى استطاعته الحركة لمسافة غير محدودة في كل هذه الاتجاهات.
هذه الحرية الفريدة في الحركة هي السبب في أن لغز الوزير يمثّل تحدّيًا جذابًا للاعبي الشطرنج وعلماء الرياضيات، رغم أنه ليس صعبًا في الحل.
في الحقيقة، هناك 92 طريقة مختلفة، من بين 4.5 بليون احتمالية لتسكين الوزراء الثمانية على الرقعة، الأمر الذي دفع علماء الرياضيات للبحث عن طريقة لجعل اللغز أشدّ إثارة.
ماذا لو فرضنا أنه بدلًا من التقيّد برقعة 8 x 8والتي تحتوي 64 مربعًا، توسّعنا في المسألة لتشمل نظريًا أي عدد من الوزراء؟
في هذه الحالة سيكون عليك أن تضع عشرين وزيرًا فوق رقعة أبعادها 20 x 20، أو مئة وزير فوق رقعة أبعادها 100 x 100، وهكذا، بحيث لا يقع أي منهم في نفس الصف أو العمود أو القطر الذي يحتله الآخر.
حين نتوسع في هذا اللغز (المسمى بلغز النون وزيرًا، حيث يحتوي عدد «ن» من الصفوف ومن الأعمدة ومن الوزراء) ليشمل أعدادًا كبيرة (مثل ن = 100)، تصبح الحسبة شديدة التعقيد حتى على أجهزة الكومبيوتر كبيرة القدرة، مع الكم الهائل من الاحتمالات الذي تحتويه.
تزداد صعوبة التحدي لدرجة لا معقولة إذا أضفنا عقدة جديدة: مجموعة من الوزراء لا يمكن تحريكهم، ومكانهم ثابت بالفعل على الرقعة.
عالم الكومبيوتر إيان جينت (Ian Gent) من جامعة سانت أندروز University of St Andrews بالمملكة المتحدة، يشرح الأمر قائلًا: «يختص البحث الجديد بمسألة إكمال النون وزيرًا n-Queens Completion Problem، حيث لا يقتصر الأمر على مجرد رقعة أكبر، لكنه يتجاوز ذلك إلى وجود عدد من الوزراء ثابتين بالفعل».
ويتابع: «للتوضيح، إذا كان بعض الوزراء في أماكنهم بالفعل في الرقعة التي أبعادها ن x ن، هل يمكنك أن تجد حلًا للغز الوزراء النون بدون تحريك أي من هؤلاء الوزراء الثابتين؟».
المسألة قد تكون سهلة الاستيعاب، لكن العثور على طرق فعالة لحلها لأي قيمة لنون، يعدّ في الواقع واحدًا من أصعب العمليات في مجال التعقيدات الحاسوبية (Computational Complexity).
لهذا السبب يعتقد جنت وباحثوه المساعدين أن برنامج الكومبيوتر الذي سيتمكن من حل هذا النوع المعقّد من مسألة الوزراء بسرعة (أي لا يستغرق آلاف السنين للحل عند القيم الكبيرة لنون) سيكون قادرًا بما يكفي على حل كل أنواع المسائل الأخرى ذات الأعداد الكبيرة من المتغيّرات، والتي تعاني أجهزة اليوم في حلها.
يقول جنت: «إذا كان بإمكانك كتابة برنامج كومبيوتر قادر على حل المسألة بسرعة فعلًا، فسيكون بإمكانك أن تعدّله لحل الكثير من أهم المسائل التي تؤثر علينا يوميًا».
ويتابع: «يشمل ذلك المسائل العادية، مثل معرفة أكبر مجموعة مكوّنة من أصدقائك على فيسبوك الذين لا يعرفون بعضهم البعض، أو التحديات الهامة مثل فكّ الشفرة التي تبقي جميع التداولات المالية على الانترنت آمنة».
لهذا السبب عرض معهد كلاي للرياضيات (Clay Mathematics Institute) جائزة قدرها مليون دولار لكل من يتمكن من حل التحدي، كجزء من مسائل جوائز الألفية Millennium Prize Problems خاصتهم، بعدما أثبت فريق جنت في ورقة بحثية جديدة أن مسألة إكمال الوزراء النون هي مثال لما يسمى بمسائل P vs NP (كثيرة حدود وكثيرة حدود غير القطعية).
يشرح جنت الأمر قائلًا: «المساهمة التقنية المقدمة في الورقة كانت أن مسألة إكمال الوزراء النون تقع في تصنيف NP-الكاملة أو كثيرة الحدود غير القطعية الكاملة» ويتابع: «إذا كان هذا صحيحًا، فهو يعني أنه إذا كانت خوارزمية ما قادرة على حل مسألة إكمال الوزراء النون، فإنه يمكن استخدامها بشكل غير مباشر لحل أي مسألة أخرى في تصنيف NP.»
ووفقًا لكلام جنت، فالجائزة مستحقة لمن يثبت أنه لا توجد خوارزمية قادرة على حل اللغز في وقت معقول، أو لمن يطوّر خوارزمية قادرة على حله بسرعة – أو، في لغة الرياضيات، خلال ما يسمى بالوقت كثير الحدود Polynomial Time.
إذا كنت تبحث عن نصائح للحل، فقد صرح جنت لموقع (Digital Trends) أن المتسابقين يجب أن يكونوا عباقرة، ومحظوظين جدًا، وحاصلين على الدكتوراه في التعقيدات الحاسوبية، ليكون لديهم فرصة في الفوز بالجائزة. وحتى حينها لن تكون الاحتمالات في صالحهم.
أحد أفراد الفريق بيتر نايتنجيل (Peter Nightingale) يشرح قائلًا: «الأمر كله نظري»، ويتابع: «في الواقع، لم يتمكن أحد من الاقتراب من كتابة برنامج قادر على حل المسألة بسرعة، لذا فإن ما كشف عنه بحثنا هو أنه، لكل الأغراض العملية، لا يمكن فعل ذلك».
هكذا طرح التحدي، فهل من شخص قادر على إثبات خطئهم؟
نشرت النتائج في نشرة أبحاث الذكاء الاصطناعي ( Journal of Artificial Intelligence Research).
المصدر
يعرض العلماء جائزة قدرها مليون دولار لأي شخص يتمكّن من حلّ عقدة شيطانية مستعصية في مسألة شطرنج كلاسيكية تدعى: لغز الملكة (الوزير).
الجميل في التحدي أنه ليس عليك حتى الإلمام بقواعد الشطرنج للمشاركة فيه، في نفس الوقت، لا يعني ذلك أنه سيكون سهلًا. في الحقيقة، يقول الباحثون أن الحلّ معقّد رياضيًا جدًا لدرجة أن الوصول إليه قد يستغرق آلاف السنوات.
لوضع الأمور في نصابها، دعنا نعود للبداية.
لغز الوزير (أو كما يطلق عليه أيضًا: لغز الوزراء الثمانية)، نشر أولًا في عام 1848، ويطلب منك وضع ثمانية وزراء على رقعة شطرنج مكونة من ثمانية مربعات على كل جانب، بحيث لا يكون أيّ منها في موقع يهدد آخر.
إذا كنت على دراية بقوانين الشطرنج، فأنت تعلم أن الوزير هو أقوى قطعة على الرقعة، لأنه يستطيع التحرك في ثمانية اتجاهات -أعلى وأسفل وإلى الجانبين وقطريًا- بالإضافة إلى استطاعته الحركة لمسافة غير محدودة في كل هذه الاتجاهات.
هذه الحرية الفريدة في الحركة هي السبب في أن لغز الوزير يمثّل تحدّيًا جذابًا للاعبي الشطرنج وعلماء الرياضيات، رغم أنه ليس صعبًا في الحل.
في الحقيقة، هناك 92 طريقة مختلفة، من بين 4.5 بليون احتمالية لتسكين الوزراء الثمانية على الرقعة، الأمر الذي دفع علماء الرياضيات للبحث عن طريقة لجعل اللغز أشدّ إثارة.
ماذا لو فرضنا أنه بدلًا من التقيّد برقعة 8 x 8والتي تحتوي 64 مربعًا، توسّعنا في المسألة لتشمل نظريًا أي عدد من الوزراء؟
في هذه الحالة سيكون عليك أن تضع عشرين وزيرًا فوق رقعة أبعادها 20 x 20، أو مئة وزير فوق رقعة أبعادها 100 x 100، وهكذا، بحيث لا يقع أي منهم في نفس الصف أو العمود أو القطر الذي يحتله الآخر.
حين نتوسع في هذا اللغز (المسمى بلغز النون وزيرًا، حيث يحتوي عدد «ن» من الصفوف ومن الأعمدة ومن الوزراء) ليشمل أعدادًا كبيرة (مثل ن = 100)، تصبح الحسبة شديدة التعقيد حتى على أجهزة الكومبيوتر كبيرة القدرة، مع الكم الهائل من الاحتمالات الذي تحتويه.
تزداد صعوبة التحدي لدرجة لا معقولة إذا أضفنا عقدة جديدة: مجموعة من الوزراء لا يمكن تحريكهم، ومكانهم ثابت بالفعل على الرقعة.
عالم الكومبيوتر إيان جينت (Ian Gent) من جامعة سانت أندروز University of St Andrews بالمملكة المتحدة، يشرح الأمر قائلًا: «يختص البحث الجديد بمسألة إكمال النون وزيرًا n-Queens Completion Problem، حيث لا يقتصر الأمر على مجرد رقعة أكبر، لكنه يتجاوز ذلك إلى وجود عدد من الوزراء ثابتين بالفعل».
ويتابع: «للتوضيح، إذا كان بعض الوزراء في أماكنهم بالفعل في الرقعة التي أبعادها ن x ن، هل يمكنك أن تجد حلًا للغز الوزراء النون بدون تحريك أي من هؤلاء الوزراء الثابتين؟».
المسألة قد تكون سهلة الاستيعاب، لكن العثور على طرق فعالة لحلها لأي قيمة لنون، يعدّ في الواقع واحدًا من أصعب العمليات في مجال التعقيدات الحاسوبية (Computational Complexity).
لهذا السبب يعتقد جنت وباحثوه المساعدين أن برنامج الكومبيوتر الذي سيتمكن من حل هذا النوع المعقّد من مسألة الوزراء بسرعة (أي لا يستغرق آلاف السنين للحل عند القيم الكبيرة لنون) سيكون قادرًا بما يكفي على حل كل أنواع المسائل الأخرى ذات الأعداد الكبيرة من المتغيّرات، والتي تعاني أجهزة اليوم في حلها.
يقول جنت: «إذا كان بإمكانك كتابة برنامج كومبيوتر قادر على حل المسألة بسرعة فعلًا، فسيكون بإمكانك أن تعدّله لحل الكثير من أهم المسائل التي تؤثر علينا يوميًا».
ويتابع: «يشمل ذلك المسائل العادية، مثل معرفة أكبر مجموعة مكوّنة من أصدقائك على فيسبوك الذين لا يعرفون بعضهم البعض، أو التحديات الهامة مثل فكّ الشفرة التي تبقي جميع التداولات المالية على الانترنت آمنة».
لهذا السبب عرض معهد كلاي للرياضيات (Clay Mathematics Institute) جائزة قدرها مليون دولار لكل من يتمكن من حل التحدي، كجزء من مسائل جوائز الألفية Millennium Prize Problems خاصتهم، بعدما أثبت فريق جنت في ورقة بحثية جديدة أن مسألة إكمال الوزراء النون هي مثال لما يسمى بمسائل P vs NP (كثيرة حدود وكثيرة حدود غير القطعية).
يشرح جنت الأمر قائلًا: «المساهمة التقنية المقدمة في الورقة كانت أن مسألة إكمال الوزراء النون تقع في تصنيف NP-الكاملة أو كثيرة الحدود غير القطعية الكاملة» ويتابع: «إذا كان هذا صحيحًا، فهو يعني أنه إذا كانت خوارزمية ما قادرة على حل مسألة إكمال الوزراء النون، فإنه يمكن استخدامها بشكل غير مباشر لحل أي مسألة أخرى في تصنيف NP.»
ووفقًا لكلام جنت، فالجائزة مستحقة لمن يثبت أنه لا توجد خوارزمية قادرة على حل اللغز في وقت معقول، أو لمن يطوّر خوارزمية قادرة على حله بسرعة – أو، في لغة الرياضيات، خلال ما يسمى بالوقت كثير الحدود Polynomial Time.
إذا كنت تبحث عن نصائح للحل، فقد صرح جنت لموقع (Digital Trends) أن المتسابقين يجب أن يكونوا عباقرة، ومحظوظين جدًا، وحاصلين على الدكتوراه في التعقيدات الحاسوبية، ليكون لديهم فرصة في الفوز بالجائزة. وحتى حينها لن تكون الاحتمالات في صالحهم.
أحد أفراد الفريق بيتر نايتنجيل (Peter Nightingale) يشرح قائلًا: «الأمر كله نظري»، ويتابع: «في الواقع، لم يتمكن أحد من الاقتراب من كتابة برنامج قادر على حل المسألة بسرعة، لذا فإن ما كشف عنه بحثنا هو أنه، لكل الأغراض العملية، لا يمكن فعل ذلك».
هكذا طرح التحدي، فهل من شخص قادر على إثبات خطئهم؟
نشرت النتائج في نشرة أبحاث الذكاء الاصطناعي ( Journal of Artificial Intelligence Research).
المصدر