Ο επιστήμονας υπολογιστών που βρίσκει μαθήματα ζωής στα παιχνίδια

Για Σανγκ-Χουά Τενγκ, η θεωρητική επιστήμη των υπολογιστών δεν ήταν ποτέ καθαρά θεωρητική. Τώρα, 58 ετών, ο Teng είναι καθηγητής επιστήμης υπολογιστών στο Πανεπιστήμιο της Νότιας Καλιφόρνια και δύο φορές νικητής του βραβείου Gödel, ενός ετήσιου βραβείου που αναγνωρίζει το πρωτοποριακό θεωρητικό έργο. Αλλά συχνά προσπαθεί να συνδέσει αυτή την αφηρημένη θεωρία με την καθημερινή ζωή με τρόπους τόσο πρακτικούς όσο και παιχνιδιάρικους.

Γεννημένος στο Πεκίνο την παραμονή της Κινεζικής Πολιτιστικής Επανάστασης, ο Τενγκ ήρθε στις Ηνωμένες Πολιτείες για μεταπτυχιακό σχεδιασμό για να σπουδάσει αρχιτεκτονική υπολογιστών, αλλά σύντομα άλλαξε κατεύθυνση για να επικεντρωθεί σε πιο αφηρημένη μαθηματική θεωρία. Έλαβε το διδακτορικό του στο Πανεπιστήμιο Carnegie Mellon το 1991 για την απόδειξη ενός θεωρήματος σχετικά με τον καλύτερο τρόπο διαχωρισμού γραφημάτων - ιστών σημείων ή κόμβων, συνδεδεμένων με γραμμές ή ακμές.

Αν και θεωρητική, η εργασία είχε πρακτικές εφαρμογές - και συχνά, όπως διαπίστωσε, οι πρακτικές εφαρμογές οδηγούσαν σε νέες θεωρητικές ιδέες. Κατά τη διάρκεια μιας καλοκαιρινής υποτροφίας της NASA το 1993, ο Teng εντάχθηκε σε μια ομάδα που προσομοιώνει τη δυναμική των ρευστών χρησιμοποιώντας μεθόδους «πεπερασμένων στοιχείων», οι οποίες μοντελοποιούν πολύπλοκες δομές ως συγκροτήματα πολλών μικροσκοπικών κομματιών. Αυτά τα συγκροτήματα μπορούν να αντιμετωπιστούν ως γραφήματα και το καθήκον του Teng ήταν να προσαρμόσει τη μέθοδο διαχωρισμού από την μεταπτυχιακή του έρευνα σε αυτό το νέο περιβάλλον. Αλλά άρχισε να περιεργάζεται την τεχνική διαχωρισμού που είχε χρησιμοποιήσει προηγουμένως η ομάδα της NASA και άρχισε να ερευνά την υποκείμενη μαθηματική δομή της μαζί με έναν άλλο επιστήμονα υπολογιστών Ντάνιελ Σπίλμαν, τώρα καθηγητής πληροφορικής στο Πανεπιστήμιο Yale. Αυτό το κοινό ερευνητικό πρόγραμμα ξεκίνησε μια συνεργασία δεκαετιών που τους κέρδισε τα δύο βραβεία Gödel.

Δεν ήταν η μόνη φορά που είδε μια βαθιά σχέση μεταξύ θεωρίας και πράξης. «Κάθε φορά, αυτά τα φαινομενικά εντελώς πρακτικά πράγματα είχαν αυτά τα όμορφα μαθηματικά πίσω τους», είπε ο Teng.

Πιο πρόσφατα, ο Teng έχει στρέψει την προσοχή του στα όμορφα μαθηματικά πίσω από παιχνίδια όπως το tic-tac-toe, το σκάκι και το Go. Σε τέτοια «συνδυαστικά» παιχνίδια, δεν υπάρχει στοιχείο της τύχης, και οι δύο παίκτες γνωρίζουν πάντα τα πάντα για την κατάσταση του ταμπλό. Ωστόσο, τα συνδυαστικά παιχνίδια παραμένουν προκλητικά επειδή ο αριθμός των τρόπων που μπορεί να παίξει ένα παιχνίδι μπορεί να είναι ιλιγγιωδώς μεγάλος.

Οι ερευνητές της θεωρίας παιγνίων επιθυμούν να γενικεύουν τέτοια παιχνίδια σε όλο και μεγαλύτερους πίνακες — κλιμακώνοντας το tic-tac-toe από τετράγωνα 3 επί 3 σε n-με-n, για παράδειγμα — και ποσοτικοποιήστε τη δυσκολία να προσδιορίσετε ποιος παίκτης θα κερδίσει δεδομένης κάποιας αρχικής κατάστασης του ταμπλό. Οι διαφορετικές πιθανές απαντήσεις ταξινομούν τα παιχνίδια στο ίδιο "τάξεις πολυπλοκότητας" που εμφανίζονται σε όλη τη θεωρητική επιστήμη των υπολογιστών.

Μια διάσημη τάξη πολυπλοκότητας ακούει στο πεζό όνομα P, για τον «πολυωνυμικό χρόνο», και περιέχει το είδος των προβλημάτων που μπορούν να λυθούν σε εύλογο χρονικό διάστημα, χονδρικά μιλώντας. Τα προβλήματα στην εξίσου διάσημη κλάση NP μπορεί να απαιτούν υπερβολικό χρόνο για να λυθούν, αλλά οι λύσεις τους είναι εύκολο να ελεγχθούν. Για προβλήματα σε μια άλλη κατηγορία πολυπλοκότητας, που ονομάζεται PSPACE, ακόμη και μια τέτοια αποτελεσματική επαλήθευση δεν είναι εγγυημένη. Όταν οι ερευνητές εξετάζουν τη «βαθιά λογική» των παιχνιδιών δύο παικτών - «αν κάνεις X, και μετά αν κάνω Y, και μετά αν κάνεις το Z», και ούτω καθεξής - συχνά βρίσκονται να μιλούν για το PSPACE. Αλλά όπως έχει βοηθήσει ο Teng να αποδειχθεί, τα μαθηματικά των συνδυαστικών παιχνιδιών δεν είναι πάντα απλά.

Quanta μίλησε πρόσφατα με τον Teng για να συζητήσει την πορεία του προς την επιστήμη των υπολογιστών, τα μαθηματικά που κρύβουν τα επιτραπέζια παιχνίδια και την επιρροή του πατέρα του. Η συνέντευξη έχει συμπυκνωθεί και επεξεργαστεί για λόγους σαφήνειας.

Πώς ήταν να πάρεις εκπαίδευση στην Κίνα;

Γεννήθηκα λίγο πριν από την Πολιτιστική Επανάσταση και ο πατέρας μου ήταν πρόεδρος στο τμήμα του πανεπιστημίου στον τομέα του πολιτικού μηχανικού. Όταν έγινε η επανάσταση, ήταν αιχμάλωτος στην πανεπιστημιούπολη. Τότε ολόκληρη η πανεπιστημιούπολη στάλθηκε βαθιά στην ύπαιθρο.

Συνήθιζα να μάζευα σκουπίδια για να πουλήσω μέχρι να τελειώσω ουσιαστικά το γυμνάσιο και μετά ξαφνικά η Κίνα άλλαξε. Αν σπούδαζες θα μπορούσες να μπεις στο κολέγιο και δεν είχαμε άλλη προοπτική να έχουμε κάποια κανονική δουλειά. Ξύπνησα και είπα: «Πρέπει να μελετήσω».

Πώς επιλέξατε την επιστήμη των υπολογιστών;

Ήθελα να σπουδάσω βιολογία μετά το λύκειο. Δεν ξέρω γιατί, αλλά ο πατέρας μου δεν ήταν πολύ ευχαριστημένος με αυτό. Τα πήγαινα καλά στα μαθηματικά και με ρώτησε αν ήθελα να κάνω μαθηματικά. Είπα όχι. [Γέλια.] Και μετά είπε, «Ξέρετε, υπάρχει ένας νέος κλάδος που ονομάζεται επιστήμη των υπολογιστών και είναι πραγματικά καλός». Κάπως, με ώθησε να ασχοληθώ με την επιστήμη των υπολογιστών.

Η εκπαίδευση εκείνη την εποχή ήταν πολύ βασική. Δεν ήμασταν εκτεθειμένοι στα περισσότερα πράγματα, και η επιστήμη των υπολογιστών δεν ήταν καν τμήμα. ήταν μια μεγάλη κατηγορία ηλεκτρολόγων μηχανικών. Αλλά από εντελώς τυχαία τύχη εκπαιδευτήκαμε ως μαθητές μαθηματικών στον λογισμό και έμαθα μερικά πράγματα που τελικά ήταν χρήσιμα για να γίνω θεωρητικός. Χωρίς αυτό μάλλον θα είχα μηδενικές πιθανότητες να περάσω. Αυτές τις μέρες τα παιδιά είναι πολύ πιο ταλαντούχα: Από το γυμνάσιο και μετά είναι πιο ταλαντούχοι μαθηματικοί από ό,τι ήμουν εγώ όταν ήρθα σε αυτή τη χώρα.

Πώς επηρέασαν αυτά τα κενά στις γνώσεις σας την εμπειρία σας στο μεταπτυχιακό;

Μια μέρα [ο σύμβουλός μου, Gary Miller,] ανακάλυψε ότι δεν είχα ακούσει ποτέ για τον NP. Ήταν σε μια συζήτηση. Είπε, «Αυτό το πρόβλημα φαίνεται NP-σκληρό». Είπα, «Ε-χα». Είπε: «Δεν με πιστεύεις;» Και μετά άρχισε να το αποδεικνύει, και στα μισά του δρόμου γύρισε απότομα προς το μέρος μου, επειδή ακριβώς καθόμουν εκεί, και είπε, «Ξέρεις τι είναι το NP-hard;» Είπα όχι.

Νόμιζα ότι ήταν η τελευταία μου μέρα που δούλευα μαζί του, αλλά συνέχισε και μου είπε τον ορισμό. Είπε, «Αν δεν ξέρεις, δεν πειράζει, αρκεί να είσαι σε θέση να σκεφτείς». Είχε τρομερό αντίκτυπο πάνω μου.

Είστε κατά κύριο λόγο θεωρητικός, αλλά σε όλη τη διάρκεια της καριέρας σας έχετε κάνει επιδρομές στη βιομηχανία. Πώς συνδέθηκε αυτή η πρακτική εργασία με τη θεωρητική σας έρευνα;

Στη διατριβή μου ανέπτυξα μερικές γεωμετρικές μεθόδους για την κατάτμηση γραφημάτων. Κατάφερα να δείξω ότι αυτή η οικογένεια γεωμετρικών μεθόδων έδωσε αποδεδειγμένα καλές περικοπές για γραφήματα πεπερασμένων στοιχείων.

Μετά από σύσταση του μέντορά μου, άρχισα να δίνω ομιλίες στη NASA και την Boeing Aerospace. Στη Boeing, θυμάμαι ότι το τρισδιάστατο μοντέλο ενός από τα φτερά είχε ήδη σχεδόν ένα εκατομμύριο στοιχεία — δεν μπορούσαν καν να το φορτώσουν σε ένα μηχάνημα. Ήθελαν λοιπόν να κόψουν αυτό το γράφημα σε διαφορετικά στοιχεία, να τα τοποθετήσουν σε διαφορετικά μηχανήματα με παρόμοια υπολογιστικά φορτία και να ελαχιστοποιήσουν την επικοινωνία. Γι' αυτό μαθηματικά ο τύπος είναι μια κοπή γραφήματος.

Στη θεωρητική επιστήμη των υπολογιστών, συχνά οι υποκείμενες μαθηματικές αρχές παραμένουν αμετάβλητες ακόμα και όταν η εμφάνιση του προβλήματος αλλάζει δραστικά, από τη βελτιστοποίηση στη θεωρία παιγνίων. Όταν κάνετε την έρευνα, δεν φαίνεται σαν μια δραστική αλλαγή.

Μιλώντας για τη θεωρία παιγνίων, είδα ότι βοήθησες στο σχεδιασμό ενός επιτραπέζιου παιχνιδιού. Πως έγινε αυτό?

Ω, μου αρέσουν τα επιτραπέζια παιχνίδια! Υπάρχουν όμορφες συνδέσεις με τη θεωρία πολυπλοκότητας. Αλλά κυρίως είμαι μαθητής των μαθητών μου.

Έδινα μια ομιλία στο Πανεπιστήμιο της Βοστώνης για ένα όμορφο διακριτό θεώρημα που ονομάζεται λήμμα του Sperner. Είναι πολύ απλό σε μια διάσταση. Έχετε ένα τμήμα γραμμής όπου το ένα άκρο είναι κόκκινο και το ένα άκρο είναι μπλε. Το χωρίζετε σε υποτμήματα [με κόμβους στα δύο άκρα] και χρωματίζετε κάθε νέο κόμβο είτε κόκκινο είτε μπλε. Τότε [ανεξάρτητα από το πώς τα χρωματίζετε] ξέρουμε ότι πρέπει να υπάρχει ένα τμήμα που να έχει και τα δύο χρώματα.

Σε δύο διαστάσεις, είναι πολύ συναρπαστικό. Έχετε ένα τρίγωνο και τώρα έχετε τρία χρώματα: Μια γωνία είναι κόκκινη, μια είναι μπλε και μια είναι πράσινη. Διαιρείτε αυτό το τρίγωνο σε μικρότερα τρίγωνα, έτσι οι άκρες χωρίζονται σε τμήματα. Κάθε εξωτερικό άκρο ακολουθεί τον μονοδιάστατο κανόνα: Οι κόμβοι μπορούν να χρησιμοποιήσουν μόνο τα χρώματα των δύο άκρων. Μέσα στο τρίγωνο, μπορείτε να κάνετε και τα τρία χρώματα με όποιον τρόπο θέλετε. Το λήμμα του Sperner λέει ότι με όποιον τρόπο το διαιρέσεις, αν κάνεις αυτόν τον χρωματισμό, πρέπει να υπάρχει ένα τρίγωνο που να έχει και τα τρία χρώματα.

Ο Κάιλ Μπερκ ήταν μαθητής μου και δούλευε την αριθμητική ανάλυση εκείνη την εποχή. Ήρθε στο γραφείο μου και είπε ότι θα μπορούσε να υπάρξει ένα όμορφο επιτραπέζιο παιχνίδι με το λήμμα του Sperner: Δύο παίκτες χρωματίζουν επαναληπτικά έναν πίνακα και όποιος προκαλεί ένα τρίγωνο τριών χρωμάτων θα χάσει το παιχνίδι. Τα καλύτερα επιτραπέζια παιχνίδια έχουν νικητές και όχι ισοπαλία, και εδώ, σαφώς κάποιος θα κερδίσει. Γιατί; Γιατί το λήμμα του Σπέρνερ!

Κάλεσα τον φίλο μου David Eppstein από το Irvine για να μιλήσω για το τι κάνει ένα καλό επιτραπέζιο παιχνίδι. Είπε, «Ένα καλό παιχνίδι έχει απλούς κανόνες και όμορφο ταμπλό και πρέπει να είναι σκληρό στο PSPACE». Γιατί αν μπορείτε να το λύσετε σε πολυωνυμικό χρόνο, ένας υπολογιστής θα σας κέρδιζε όλη την ώρα.

Οπότε περάσαμε από αυτά τα κριτήρια. Ο Κάιλ είπε: «Είναι απλό αυτό το παιχνίδι;» Είπα, «Ναι, είναι μια πρόταση!» Είπε, "Είναι πολύχρωμο αυτό το παιχνίδι;" Είπα, «Σε σχέδιο!» Στη συνέχεια είπε, "Αν αποδείξω ότι είναι δύσκολο για το PSPACE, μπορώ να πάρω διδακτορικό;" Είπα ναι, και το έκανε. Υπάρχουν πολλές διαφορετικές πτυχές του θεωρήματός του. Αποκαλύπτει ορισμένα πράγματα για σταθερά σημεία, που είναι μια πολύ όμορφη έννοια στα μαθηματικά.

Μπορώ να παίξω το παιχνίδι οπουδήποτε;

Είναι διαθέσιμο, με κάποιες τροποποιήσεις, διαδικτυακά (online).

Ποια παιχνίδια σας αρέσει να παίζετε;

Είμαι θεωρητικός παιχνιδιών. [Γέλια.] Παίζω λίγο με την κόρη μου, αλλά δεν μεγάλωσα παίζοντας τους. Σε αντίθεση με τους μαθητές μου, που έπαιξαν παιχνίδια σε όλη τους τη ζωή.

Τι άλλη δουλειά έχετε κάνει στα μαθηματικά των επιτραπέζιων παιχνιδιών;

Είχαμε ένα χαρτί πρόσφατα σχετικά με μια ανοιχτή ερώτηση: Εάν βάλετε δύο παιχνίδια με δυνατότητα επίλυσης πολυωνύμων μαζί, το ένα δίπλα στο άλλο, θα τα καθιστούσε σκληρά στο PSPACE; Σε κάθε κίνηση μπορείτε να παίξετε μόνο ένα από αυτά. Αυτό ονομάζεται άθροιση παιχνιδιών.

Τι σημαίνει να βάζεις δύο παιχνίδια μαζί;

Στο αρχαίο παιχνίδι Go, όταν βάζετε αρκετές πέτρες, έχετε πολλές ξεχωριστές αρένες, οπότε κατά κάποιο τρόπο παίζετε ένα άθροισμα παιχνιδιών. Πρέπει να ανησυχείς για αυτή τη γωνία και εκείνη τη γωνία. Θέλετε να κερδίσετε το σύνολο, αλλά αυτό δεν σημαίνει ότι πρέπει να κερδίσετε κάθε κομμάτι.

Είναι φιλοσοφικά ενδιαφέρον, σωστά; Είναι σαν να έχεις πόλεμο, και έχει πολλές μάχες, αλλά η προσοχή σου είναι πεπερασμένη. Ανά πάσα στιγμή μπορείτε να πάρετε μόνο μία απόφαση σε ένα από τα πεδία μάχης και ο αντίπαλός σας μπορεί είτε να απαντήσει είτε να διπλασιαστεί σε κάποιο άλλο πεδίο μάχης. Αυτό προσπαθούσα να το εξηγήσω στον πατέρα μου. Όταν παίζετε ένα άθροισμα παιχνιδιών, σημαίνει πραγματικά: Πώς χάνετε στρατηγικά;

Το αποδείξαμε για δύο παιχνίδια, αλλά μπορείτε να συνδυάσετε τρία παιχνίδια και το θεώρημα εξακολουθεί να ισχύει: Τρία παιχνίδια πολυωνυμικού χρόνου μαζί μπορούν να γίνουν σκληρά για το PSPACE.

Από τότε που σας ώθησε προς την επιστήμη των υπολογιστών, πώς ανταποκρίθηκε ο πατέρας σας στη διαφορετική δουλειά που έχετε κάνει όλα αυτά τα χρόνια;

Με ρωτούσε συχνά, «Γιατί το κάνεις αυτό;» Δουλεύοντας θεωρητικά, συχνά δεν έχεις αποτέλεσμα εδώ και χρόνια και το κατάλαβε σταδιακά. Από νωρίς θα μπορούσα να μιλήσω για τη μέθοδο των πεπερασμένων στοιχείων — το διδάσκουν και στον πολιτικό μηχανικό. Αλλά δεν μπορούσα να καταλάβω πώς να μιλήσω για αυτά τα ψυχαγωγικά μαθηματικά.

Μετά σκέφτηκα ένα ιδίωμα που προέρχεται από αυτό το διάσημο κινέζικο μυθιστόρημα που ονομάζεται Ειδύλλιο των Τριών Βασιλείων. Ένας από τους χαρακτήρες, ο Zhuge Liang, ήταν σχεδόν ένας τέλειος στρατηγός, και το ιδίωμα λέει, "Τρεις μοντέρνες παπουτσιών είναι καλύτεροι από τον Zhuge Liang". Χρησιμοποιείται με αυτόν τον ήπιο τρόπο για να πει ότι τρεις μέσοι άνθρωποι μπορούν να είναι τέλειοι όταν ενώνουν τα κεφάλια τους. Αλλά όταν κοιτάξετε την ιστορία αυτού του ιδιώματος, τα πράγματα προφέρονταν διαφορετικά σε διαφορετικές περιοχές και το "shoe fixer" είχε τον ίδιο ήχο με το "field general". Λέει λοιπόν, «Τρεις στρατηγοί πεδίου μαζί είναι καλύτεροι από αυτόν τον τέλειο στρατηγό».

Είπα στον πατέρα μου αυτό ακριβώς το θεώρημα αποδείξαμε με την άθροιση των παιχνιδιών. Οι στρατηγοί πεδίου αντιπροσωπεύουν [αλγόριθμους επίλυσης] παιχνίδια πολυωνυμικού χρόνου: Σε κάθε πεδίο μάχης, ξέρουν πώς να κερδίζουν. Αλλά το δύσκολο μέρος είναι να ξέρεις πότε να χάσεις, όχι πώς να κερδίσεις κάθε ένα από τα συστατικά παιχνίδια. Αν κάποιος μπορεί να παίξει αυτό το δύσκολο παιχνίδι, είναι πραγματικά ο καλύτερος στρατηγός. Οι στρατηγοί δεν παίρνουν αυτές τις βαθιές λογικές αποφάσεις, αλλά με κάποιο τρόπο, αν τις συνδυάσεις καλά, δεν είναι χειρότεροι από αυτόν τον τέλειο στρατηγό.

Είπα στον μπαμπά μου: «Επιτέλους συνειδητοποίησα αυτό το θεώρημα των μαθηματικών που ισοδυναμεί με ένα από τα διάσημα ιδιώματα μας!» Ήταν 94 ετών εκείνη την εποχή, πολύ ευκρινής και είπε, «Αυτή είναι μια καλή προσπάθεια». Δεν τον έπεισα καθόλου. Αυτή ήταν η τελευταία τεχνική συνομιλία μου μαζί του. λίγους μήνες αργότερα πέρασε. Κάθε φορά που σκέφτομαι να εξηγήσω τη δουλειά μου, αυτό είναι το αποκορύφωμά μου.