عالم الكمبيوتر الذي يجد دروس الحياة في الألعاب

في حالة شانغ هوا تنغ، علم الكمبيوتر النظري لم يكن أبدًا نظريًا بحتًا. الآن 58 ، Teng هو أستاذ علوم الكمبيوتر في جامعة جنوب كاليفورنيا والفائز مرتين بجائزة Gödel ، وهي جائزة سنوية تعترف بالعمل النظري الرائد. لكنه غالبًا ما يسعى إلى ربط تلك النظرية المجردة بالحياة اليومية بطرق عملية ومرحة.

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

على الرغم من أن العمل نظري ، إلا أنه كان له تطبيقات عملية - وفي كثير من الأحيان ، وجد أن التطبيقات العملية تؤدي إلى رؤى نظرية جديدة. خلال زمالة ناسا الصيفية عام 1993 ، انضم تنغ إلى فريق يحاكي ديناميكيات الموائع باستخدام طرق "العناصر المحدودة" ، التي تصمم الهياكل المعقدة كتجمعات من العديد من القطع الصغيرة. يمكن التعامل مع هذه المجموعات على أنها رسوم بيانية ، وكانت مهمة Teng هي تكييف طريقة التقسيم من بحث الخريجين إلى هذا الإعداد الجديد. لكنه أصبح فضوليًا بشأن تقنية التقسيم التي استخدمها فريق ناسا سابقًا ، وبدأ في التحقيق في هيكلها الرياضي الأساسي مع عالم كمبيوتر زميل دانيال سبيلمان، الآن أستاذ علوم الكمبيوتر في جامعة ييل. بدأ مشروع البحث المشترك هذا تعاونًا دام عقودًا وفاز بجائزتي Gödel.

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

في الآونة الأخيرة ، حوّل Teng انتباهه إلى الرياضيات الجميلة وراء ألعاب مثل tic-tac-toe و chess و Go. في مثل هذه الألعاب "الاندماجية" ، ليس هناك عنصر حظ ، وكلا اللاعبين يعرف دائمًا كل شيء عن حالة اللوحة. ومع ذلك ، لا تزال الألعاب الاندماجية تمثل تحديًا لأن عدد الطرق التي يمكن أن تلعب بها اللعبة قد يكون كبيرًا بشكل مذهل.

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

إحدى فئات التعقيد الشهيرة تُطلق عليها الاسم النثرى P ، بمعنى "وقت متعدد الحدود" ، وتحتوي على نوع المشاكل التي يمكن حلها في فترة زمنية معقولة ، تقريبًا. قد تستغرق المشكلات في فئة NP المشهورة أيضًا وقتًا غير معقول لحلها ، ولكن من السهل التحقق من حلولها. بالنسبة للمشكلات في فئة التعقيد الأخرى ، التي يطلق عليها اسم PSPACE ، فحتى هذا التحقق الفعال غير مضمون. عندما يفكر الباحثون في "المنطق العميق" للألعاب ثنائية اللاعبين - "إذا فعلت X ، ثم إذا فعلت Y ، ثم إذا فعلت Z ،" وما إلى ذلك - غالبًا ما يجدون أنفسهم يتحدثون عن PSPACE. ولكن كما أثبت Teng ، فإن رياضيات الألعاب الاندماجية ليست دائمًا واضحة.

كوانتا تحدث مع Teng مؤخرًا لمناقشة طريقه إلى علوم الكمبيوتر ، والرياضيات الكامنة وراء ألعاب الطاولة ، وتأثير والده. تم اختصار المقابلة وتحريرها من أجل الوضوح.

كيف كان الأمر مثل الحصول على التعليم في الصين؟

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

اعتدت أن أجمع القمامة لبيعها حتى أنتهيت عمليًا من الإعدادية ، ثم تغيرت الصين فجأة. إذا درست يمكنك الالتحاق بالجامعة ، ولم يكن لدينا أي احتمال آخر بالحصول على وظيفة منتظمة. استيقظت وقلت ، "أنا بحاجة للدراسة."

كيف اخترت علوم الكمبيوتر؟

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

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

كيف أثرت هذه الثغرات في معرفتك على تجربتك مع الدراسات العليا؟

ذات يوم اكتشف [مستشاري ، غاري ميلر] أنني لم أسمع من قبل عن NP. كان في مناقشة. قال ، "هذه المشكلة تبدو صعبة NP." قلت ، "آه". قال ، "أنت لا تصدقني؟" ثم بدأ في إثبات ذلك ، وفي منتصف الطريق التفت إلي بحدة ، لأنني كنت جالسًا هناك ، وقال ، "هل تعرف ما هو NP-hard؟" قلت لا.

اعتقدت أن هذا كان آخر يوم لي في العمل معه ، لكنه استمر وأخبرني بالتعريف. قال ، "إذا كنت لا تعرف ، فلا يهم ، طالما أنك قادر على التفكير." كان له تأثير هائل علي.

أنت في الأساس مُنظِّر ، لكن طوال حياتك المهنية قمت بغزوات في الصناعة. كيف ربط هذا العمل العملي بأبحاثك النظرية؟

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

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

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

بالحديث عن نظرية الألعاب ، رأيت أنك ساعدت في تصميم لعبة لوحية. كيف حدث هذا؟

أوه ، أنا أحب ألعاب الطاولة! هناك روابط جميلة مع نظرية التعقيد. لكن في الغالب أنا طالب طلابي.

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

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

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

اتصلت بصديقي David Eppstein من Irvine للتحدث عما يجعل لعبة الطاولة جيدة. قال ، "اللعبة الجيدة لها قواعد بسيطة ولوحة جميلة ، ويجب أن تكون صعبة على PSPACE." لأنه إذا تمكنت من حلها في وقت متعدد الحدود ، فإن الكمبيوتر سيهزمك طوال الوقت.

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

هل يمكنني لعب اللعبة في أي مكان؟

إنه متاح ، مع بعض التعديلات ، online.

ما هي الألعاب التي تحب أن تلعبها؟

أنا منظّر للألعاب. [يضحك.] ألعب قليلاً مع ابنتي ، لكني لم أكبر وأنا ألعبها. على عكس طلابي ، الذين لعبوا الألعاب طوال حياتهم.

ما الأعمال الأخرى التي قمت بها في رياضيات ألعاب الطاولة؟

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

ماذا يعني وضع لعبتين معًا؟

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

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

لقد أثبتنا ذلك في لعبتين ، ولكن يمكنك وضع ثلاث ألعاب معًا ولا تزال النظرية صحيحة: ثلاث ألعاب متعددة الحدود معًا يمكن أن تصبح صعبة PSPACE.

منذ أن دفعك نحو علوم الكمبيوتر ، كيف استجاب والدك للعمل المختلف الذي قمت به على مر السنين؟

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

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

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

أخبرت والدي ، "لقد أدركت أخيرًا أن نظرية الرياضيات هذه تعادل إحدى مصطلحاتنا الاصطلاحية الشهيرة!" كان عمره 94 عامًا في ذلك الوقت ، وكان حادًا جدًا ، وقال ، "هذه محاولة جيدة." لم أقنعه تمامًا. كانت تلك آخر محادثة تقنية لي معه ؛ بعد بضعة أشهر وافته المنية. كلما فكرت في شرح عملي ، هذا هو أبرز ما لدي.