Ilmuwan Komputer yang Menemukan Pelajaran Hidup dalam Game

Untuk Shang Hua Teng, ilmu komputer teoretis tidak pernah murni teoretis. Sekarang berusia 58 tahun, Teng adalah seorang profesor ilmu komputer di University of Southern California dan pemenang dua kali Gödel Prize, sebuah penghargaan tahunan yang mengakui karya teoretis yang inovatif. Tapi dia sering berusaha menghubungkan teori abstrak itu dengan kehidupan sehari-hari dengan cara yang praktis dan menyenangkan.

Lahir di Beijing pada malam Revolusi Kebudayaan China, Teng datang ke Amerika Serikat untuk perencanaan sekolah pascasarjana untuk mempelajari arsitektur komputer, tetapi dia segera mengubah arah untuk fokus pada teori matematika yang lebih abstrak. Dia menerima gelar doktor di Universitas Carnegie Mellon pada tahun 1991 untuk membuktikan teorema tentang cara terbaik untuk mempartisi grafik — jaringan titik, atau simpul, dihubungkan dengan garis, atau tepi.

Meskipun teoretis, karya tersebut memiliki aplikasi praktis - dan seringkali, menurutnya, aplikasi praktis mengarah pada wawasan teoretis baru. Selama persekutuan musim panas NASA tahun 1993, Teng bergabung dengan tim yang mensimulasikan dinamika fluida menggunakan metode "elemen hingga", yang memodelkan struktur kompleks sebagai kumpulan dari banyak potongan kecil. Kumpulan ini dapat diperlakukan sebagai grafik, dan tugas Teng adalah mengadaptasi metode partisi dari penelitian pascasarjana ke pengaturan baru ini. Namun dia menjadi penasaran dengan teknik partisi yang digunakan tim NASA sebelumnya, dan mulai menyelidiki struktur matematis yang mendasarinya bersama dengan sesama ilmuwan komputer. Daniel Spielman, sekarang menjadi profesor ilmu komputer di Universitas Yale. Proyek penelitian bersama itu memulai kolaborasi selama puluhan tahun yang memenangkan dua Penghargaan Gödel.

Itu bukan satu-satunya saat dia melihat hubungan yang dalam antara teori dan praktik. “Setiap kali, hal-hal yang tampaknya sangat praktis ini memiliki matematika yang indah di belakang mereka,” kata Teng.

Baru-baru ini, Teng mengalihkan perhatiannya ke matematika indah di balik permainan seperti tic-tac-toe, catur, dan Go. Dalam permainan "kombinatorial" seperti itu, tidak ada unsur kebetulan, dan kedua pemain selalu tahu segalanya tentang keadaan papan. Namun permainan kombinatorial tetap menantang karena banyaknya cara permainan bisa dimainkan mungkin sangat banyak.

Peneliti teori permainan suka menggeneralisasi permainan semacam itu ke papan yang lebih besar — ​​meningkatkan tic-tac-toe dari kotak 3 kali 3 menjadi n-oleh-n, misalnya — dan hitung kesulitan dalam menentukan pemain mana yang akan menang dengan kondisi papan awal tertentu. Kemungkinan jawaban yang berbeda mengurutkan permainan menjadi “kelas kompleksitas” yang muncul di seluruh ilmu komputer teoretis.

Satu kelas kompleksitas terkenal menggunakan nama biasa P, untuk "waktu polinomial", dan berisi jenis masalah yang dapat diselesaikan dalam jumlah waktu yang masuk akal, secara kasar. Masalah di kelas NP yang sama-sama terkenal mungkin membutuhkan waktu yang tidak masuk akal untuk diselesaikan, tetapi solusinya mudah diperiksa. Untuk masalah di kelas kompleksitas lain, yang dijuluki PSPACE, bahkan verifikasi yang efisien seperti itu tidak dijamin. Ketika peneliti mempertimbangkan "logika mendalam" dari game dua pemain - "jika Anda melakukan X, dan kemudian jika saya melakukan Y, dan kemudian jika Anda melakukan Z," dan seterusnya - mereka sering membicarakan tentang PSPACE. Tapi seperti Teng telah membantu membuktikan, matematika permainan kombinatorial tidak selalu mudah.

Quanta berbicara dengan Teng baru-baru ini untuk membahas jalannya ke ilmu komputer, matematika yang mendasari permainan papan, dan pengaruh ayahnya. Wawancara telah diringkas dan diedit untuk kejelasan.

Bagaimana rasanya mengenyam pendidikan di Tiongkok?

Saya lahir sedikit sebelum Revolusi Kebudayaan, dan ayah saya adalah ketua jurusan teknik sipil di universitas. Ketika revolusi terjadi, dia ditawan di kampus. Kemudian seluruh kampus dikirim jauh ke pedesaan.

Saya dulu mengumpulkan sampah untuk dijual sampai saya hampir menyelesaikan SMP, dan kemudian tiba-tiba China berubah. Jika Anda belajar, Anda bisa masuk perguruan tinggi, dan kami tidak memiliki prospek lain untuk memiliki pekerjaan tetap. Saya bangun, dan saya berkata, "Saya perlu belajar."

Bagaimana Anda memilih ilmu komputer?

Saya ingin belajar biologi setelah SMA. Saya tidak tahu mengapa, tetapi ayah saya tidak terlalu senang dengan itu. Saya baik-baik saja dalam matematika, dan dia bertanya apakah saya ingin mengerjakan matematika. Aku berkata tidak. [Tertawa.] Dan kemudian dia berkata, "Anda tahu, ada disiplin baru yang disebut ilmu komputer, dan itu sangat bagus." Entah bagaimana, dia mendorong saya untuk mengambil jurusan ilmu komputer.

Pendidikan pada saat itu sangat mendasar. Kami tidak terpapar pada banyak hal, dan ilmu komputer bahkan bukan sebuah departemen; itu jurusan teknik elektro. Tetapi dengan keberuntungan yang benar-benar acak, kami dilatih sebagai siswa matematika dalam kalkulus, dan saya belajar beberapa hal yang pada akhirnya berguna untuk menjadi seorang ahli teori. Tanpa itu saya mungkin tidak akan memiliki kesempatan untuk lulus. Hari-hari ini anak-anak jauh lebih berbakat: Sejak sekolah menengah, mereka adalah ahli matematika yang lebih berbakat daripada saya ketika saya datang ke negara ini.

Bagaimana kesenjangan dalam pengetahuan Anda memengaruhi pengalaman Anda di sekolah pascasarjana?

Suatu hari [penasihat saya, Gary Miller,] menemukan bahwa saya belum pernah mendengar tentang NP. Itu dalam sebuah diskusi. Dia berkata, "Masalah ini terlihat sulit bagi NP." Saya berkata, "Uh-huh." Dia berkata, "Kamu tidak percaya padaku?" Dan kemudian dia mulai membuktikannya, dan di tengah jalan dia dengan tajam menoleh ke arah saya, karena saya hanya duduk di sana, dan dia berkata, "Tahukah kamu apa itu NP-hard?" Aku berkata tidak.

Saya pikir itu adalah hari terakhir saya bekerja dengannya, tetapi dia melanjutkan dan memberi tahu saya definisinya. Beliau berkata, “Jika kamu tidak tahu, tidak apa-apa, asalkan kamu mampu berpikir.” Dia memiliki pengaruh yang luar biasa pada saya.

Anda pada dasarnya adalah seorang ahli teori, tetapi sepanjang karier Anda, Anda telah terjun ke industri. Bagaimana kerja praktek ini terhubung dengan penelitian teoretis Anda?

Dalam tesis saya, saya mengembangkan beberapa metode geometris untuk mempartisi grafik. Saya dapat menunjukkan bahwa rangkaian metode geometris ini terbukti memberikan potongan yang bagus untuk grafik elemen hingga.

Atas rekomendasi mentor saya, saya mulai memberikan ceramah di NASA dan Boeing Aerospace. Di Boeing, saya ingat model 3D dari salah satu sayap sudah memiliki hampir satu juta elemen — mereka bahkan tidak dapat memuatnya ke dalam satu mesin. Jadi mereka ingin memotong grafik ini menjadi komponen yang berbeda, meletakkannya di mesin yang berbeda dengan beban komputasi yang serupa, dan meminimalkan komunikasi. Itu sebabnya secara matematis rumusnya adalah potongan grafik.

Dalam ilmu komputer teoretis, seringkali prinsip-prinsip matematika yang mendasarinya tidak berubah bahkan ketika tampilan masalah berubah secara drastis, dari pengoptimalan menjadi teori permainan. Saat Anda melakukan penelitian, rasanya tidak ada perubahan drastis.

Berbicara tentang teori permainan, saya melihat Anda membantu merancang permainan papan. Bagaimana itu bisa terjadi?

Oh, saya suka permainan papan! Ada hubungan yang indah dengan teori kompleksitas. Tetapi kebanyakan saya adalah murid dari murid-murid saya.

Saya sedang memberikan ceramah di Universitas Boston tentang teorema diskrit yang indah yang disebut lemma Sperner. Ini sangat sederhana dalam satu dimensi. Anda memiliki segmen garis di mana salah satu ujungnya berwarna merah dan salah satu ujungnya berwarna biru. Anda membaginya menjadi subsegmen [dengan simpul di kedua ujungnya] dan mewarnai setiap simpul baru dengan warna merah atau biru. Kemudian [tidak peduli bagaimana Anda mewarnainya] kami tahu pasti ada segmen yang memiliki kedua warna tersebut.

Dalam dua dimensi, itu sangat mempesona. Anda memiliki segitiga, dan sekarang Anda memiliki tiga warna: Satu sudut berwarna merah, satu berwarna biru dan satu berwarna hijau. Anda membagi segitiga ini menjadi segitiga yang lebih kecil, sehingga ujung-ujungnya dipecah menjadi beberapa bagian. Setiap tepi luar mengikuti aturan satu dimensi: Node hanya dapat menggunakan warna dari kedua ujungnya. Di dalam segitiga, Anda dapat melakukan ketiga warna sesuka Anda. Lemma Sperner mengatakan bahwa dengan cara apa pun Anda membaginya, jika Anda melakukan pewarnaan ini, pasti ada segitiga yang memiliki ketiga warna tersebut.

Kyle Burke adalah murid saya, mengerjakan analisis numerik pada saat itu. Dia datang ke kantor saya dan berkata mungkin ada permainan papan yang indah dari lemma Sperner: Dua pemain mewarnai papan secara berulang, dan siapa pun yang membuat segitiga tiga warna akan kalah dalam permainan. Permainan papan terbaik memiliki pemenang daripada seri, dan di sini, jelas seseorang akan menang. Mengapa? Karena lemma Sperner!

Saya menelepon teman saya David Eppstein dari Irvine untuk membicarakan tentang cara membuat permainan papan yang bagus. Dia berkata, "Game yang bagus memiliki aturan sederhana dan papan yang indah, dan itu harus keras untuk PSPACE." Karena jika Anda dapat menyelesaikannya dalam waktu polinomial, komputer akan selalu mengalahkan Anda.

Jadi kami melewati kriteria itu. Kyle berkata, "Apakah game ini sederhana?" Saya berkata, "Ya, itu satu kalimat!" Dia berkata, "Apakah game ini penuh warna?" Saya berkata, "Dengan desain!" Lalu dia berkata, "Jika saya membuktikan bahwa ini sulit untuk PSPACE, dapatkah saya mendapatkan gelar Ph.D.?" Saya menjawab ya, dan dia melakukannya. Ada banyak segi yang berbeda dari teoremanya. Ini mengungkapkan hal-hal tertentu tentang titik tetap, yang merupakan konsep yang sangat indah dalam matematika.

Bisakah saya bermain game di mana saja?

Ini tersedia, dengan beberapa penyesuaian, secara online.

Game apa yang kamu suka mainkan?

Saya seorang ahli teori permainan. [Tertawa.] Saya bermain sedikit dengan putri saya, tetapi saya tidak tumbuh dewasa memainkannya. Tidak seperti siswa saya, yang telah bermain game sepanjang hidup mereka.

Apa pekerjaan lain yang telah Anda lakukan pada matematika permainan papan?

Kita mempunyai kertas baru-baru ini tentang pertanyaan terbuka: Jika Anda menyatukan dua game yang dapat dipecahkan waktu polinomial, berdampingan, apakah itu akan membuat mereka sulit untuk PSPACE? Di setiap gerakan, Anda hanya dapat memainkan salah satunya. Ini disebut penjumlahan permainan.

Apa artinya menyatukan dua game?

Di game kuno Go, saat Anda meletakkan cukup banyak batu, Anda mendapatkan banyak arena terpisah, jadi dalam beberapa hal Anda memainkan sejumlah game. Anda harus khawatir tentang sudut ini dan sudut itu. Anda ingin memenangkan semuanya, tetapi itu tidak berarti Anda harus memenangkan setiap bagian.

Secara filosofis menarik, bukan? Ini seperti Anda berperang, dan ada banyak pertempuran, tetapi perhatian Anda terbatas. Setiap saat Anda hanya dapat membuat satu keputusan di salah satu medan perang, dan lawan Anda dapat merespons atau menggandakan di beberapa medan perang lainnya. Saya mencoba menjelaskan hal ini kepada ayah saya. Saat Anda memainkan sejumlah permainan, itu benar-benar berarti: Bagaimana Anda kalah secara strategis?

Kami membuktikannya untuk dua game, tetapi Anda dapat menggabungkan tiga game dan teoremanya masih benar: Tiga game waktu polinomial yang digabungkan dapat menjadi sulit untuk PSPACE.

Sejak dia mendorong Anda ke ilmu komputer, bagaimana tanggapan ayah Anda terhadap berbagai pekerjaan yang telah Anda lakukan selama bertahun-tahun?

Dia sering bertanya kepada saya, "Mengapa kamu melakukan ini?" Bekerja dalam teori, seringkali Anda tidak mendapatkan hasil selama bertahun-tahun, dan dia memahaminya secara bertahap. Sejak awal saya dapat berbicara tentang metode elemen hingga - mereka juga mengajarkannya di teknik sipil. Tapi saya tidak tahu bagaimana membicarakan matematika rekreasi ini.

Kemudian saya berpikir tentang sebuah idiom yang berasal dari novel China terkenal berjudul Kisah Tiga Negara. Salah satu karakternya, Zhuge Liang, hampir merupakan ahli strategi yang sempurna, dan idiomnya berbunyi, "Tiga tukang memperbaiki sepatu lebih baik daripada Zhuge Liang." Ini digunakan dengan cara yang ringan untuk mengatakan bahwa tiga orang biasa bisa menjadi sempurna ketika mereka menggabungkan kepala mereka. Tetapi ketika Anda melihat sejarah idiom ini, banyak hal diucapkan secara berbeda di berbagai daerah, dan "tukang sepatu" memiliki bunyi yang sama dengan "jenderal lapangan". Jadi dikatakan, "Tiga jenderal lapangan bersama-sama lebih baik daripada ahli strategi yang sempurna ini."

Saya berkata kepada ayah saya bahwa itulah teorema yang kami buktikan dengan penjumlahan permainan. Jenderal lapangan mewakili [algoritma untuk memecahkan] permainan waktu polinomial: Di setiap medan perang, mereka tahu cara menang. Tetapi bagian yang sulit adalah mengetahui kapan harus kalah, bukan bagaimana memenangkan setiap permainan komponen. Jika seseorang dapat memainkan permainan sulit itu, mereka benar-benar ahli strategi terbaik. Jenderal lapangan tidak membuat keputusan logika yang mendalam ini, tetapi entah bagaimana jika Anda menggabungkannya dengan baik, mereka tidak lebih buruk dari ahli strategi yang sempurna ini.

Saya memberi tahu ayah saya, "Akhirnya saya menyadari teorema matematika ini yang setara dengan salah satu idiom terkenal kami!" Dia berusia 94 tahun saat itu, sangat tajam, dan dia berkata, "Itu usaha yang bagus." Saya tidak cukup meyakinkan dia. Itu adalah percakapan teknis terakhir saya dengannya; beberapa bulan kemudian dia lulus. Setiap kali saya berpikir untuk menjelaskan pekerjaan saya, ini adalah sorotan saya.