Hayat Derslerini Oyunlarda Bulan Bilgisayar Bilimcisi

İçin Shang Hua TengTeorik bilgisayar bilimi hiçbir zaman tamamen teorik olmadı. Şu anda 58 yaşında olan Teng, Güney Kaliforniya Üniversitesi'nde bilgisayar bilimi profesörü ve çığır açan teorik çalışmaları ödüllendiren yıllık bir ödül olan Gödel Ödülü'nü iki kez kazandı. Ancak çoğu zaman bu soyut teoriyi hem pratik hem de eğlenceli bir şekilde günlük hayata bağlamaya çalışıyor.

Çin Kültür Devrimi'nin arifesinde Pekin'de doğan Teng, bilgisayar mimarisi üzerine eğitim almayı planlayan yüksek lisans eğitimi için Amerika Birleşik Devletleri'ne geldi, ancak kısa süre sonra yönünü değiştirerek daha soyut matematik teorisine odaklandı. Doktorasını 1991 yılında Carnegie Mellon Üniversitesi'nde, grafiklerin (doğrular veya kenarlarla birbirine bağlanan nokta ağları veya düğümlerden oluşan ağlar) en iyi şekilde nasıl bölünebileceğine dair bir teoremi kanıtladığı için aldı.

Teorik olmasına rağmen, çalışmanın pratik uygulamaları vardı ve pratik uygulamaların sıklıkla yeni teorik anlayışlara yol açtığını gördü. 1993 NASA yaz bursu sırasında Teng, karmaşık yapıları birçok küçük parçanın birleşimi olarak modelleyen "sonlu elemanlar" yöntemlerini kullanarak akışkanlar dinamiğini simüle eden bir ekibe katıldı. Bu topluluklar grafik olarak ele alınabilir ve Teng'in görevi, lisansüstü araştırmasındaki bölümleme yöntemini bu yeni ortama uyarlamaktı. Ancak NASA ekibinin daha önce kullandığı bölümleme tekniğini merak etti ve diğer bilgisayar bilimcileriyle birlikte bu tekniğin temel matematiksel yapısını araştırmaya başladı. Daniel Spielman, şu anda Yale Üniversitesi'nde bilgisayar bilimi profesörü. Bu ortak araştırma projesi, onlara iki Gödel Ödülü kazandıran onlarca yıllık bir işbirliğini başlattı.

Teori ile pratik arasında derin bir bağlantı gördüğü tek zaman bu değildi. Teng, "Her seferinde, görünüşte tamamen pratik olan bu şeylerin arkasında güzel bir matematik vardı" dedi.

Son zamanlarda Teng dikkatini tic-tac-toe, satranç ve Go gibi oyunların ardındaki güzel matematiğe çevirdi. Bu tür "kombinatoryal" oyunlarda şans unsuru yoktur ve her iki oyuncu da her zaman tahtanın durumu hakkında her şeyi bilir. Yine de kombinatoryal oyunlar zorlu olmaya devam ediyor çünkü bir oyunun oynanabileceği yolların sayısı baş döndürücü derecede fazla olabilir.

Oyun teorisi araştırmacıları, bu tür oyunları daha büyük tahtalara genelleştirmeyi seviyorlar; tic-tac-toe'yu 3'e 3'lük karelerden n-By-nörneğin - ve başlangıçtaki tahta durumu göz önüne alındığında hangi oyuncunun kazanacağını belirlemenin zorluğunu ölçün. Farklı olası cevaplar, oyunları aynı şekilde sıralar "karmaşıklık sınıfları” teorik bilgisayar bilimi boyunca ortaya çıkan bir şey.

Ünlü bir karmaşıklık sınıfı, "polinom zaman" anlamına gelen sıradan P adını alır ve kabaca konuşursak, makul bir sürede çözülebilecek türden problemleri içerir. Aynı derecede ünlü NP sınıfındaki problemlerin çözülmesi mantıksız miktarda zaman alabilir, ancak çözümlerinin kontrol edilmesi kolaydır. PSPACE adı verilen başka bir karmaşıklık sınıfındaki sorunlar için bu kadar etkili bir doğrulama bile garanti edilmez. Araştırmacılar iki oyunculu oyunların "derin mantığını" - "sen X yaparsan, sonra ben Y yaparsam, sonra sen Z yaparsan" vb. - ele aldıklarında genellikle kendilerini PSPACE hakkında konuşurken bulurlar. Ancak Teng'in de kanıtladığı gibi kombinatoryal oyunların matematiği her zaman basit değildir.

Kuantum Bilgisayar bilimine giden yolu, masa oyunlarının altında yatan matematiği ve babasının etkisini tartışmak için yakın zamanda Teng'le konuştu. Röportaj, netlik sağlamak amacıyla kısaltıldı ve düzenlendi.

Çin'de eğitim almak nasıldı?

Kültür Devrimi'nden biraz önce doğdum ve babam üniversitede inşaat mühendisliği bölüm başkanıydı. Devrim gerçekleştiğinde kampüste esaret altındaydı. Daha sonra tüm kampüs kırsalın derinliklerine gönderildi.

Ortaokulu neredeyse bitirene kadar satmak için çöp topluyordum ve sonra Çin aniden değişti. Okursan üniversiteye girebilirdin ve düzenli bir işte çalışmaktan başka şansımız yoktu. Uyandım ve "Çalışmam lazım" dedim.

Bilgisayar bilimlerini nasıl seçtiniz?

Liseden sonra biyoloji okumak istiyordum. Nedenini bilmiyorum ama babam bundan pek memnun değildi. Matematikte iyiydim ve bana matematik yapmak isteyip istemediğimi sordu. Hayır dedim. [Gülüyor.] Sonra şöyle dedi: "Biliyorsunuz, bilgisayar bilimi adında yeni bir disiplin var ve bu gerçekten çok iyi." Bir şekilde beni bilgisayar bilimi alanında uzmanlaşmaya teşvik etti.

O dönemde eğitim çok temel düzeydeydi. Çoğu şeye maruz kalmıyorduk ve bilgisayar bilimi bir bölüm bile değildi; elektrik mühendisliğinde önemli bir konuydu. Ancak tamamen şans eseri, matematik öğrencileri olarak matematik alanında eğitildik ve sonunda bir teorisyen olmak için yararlı olacak birkaç şey öğrendim. O olmasaydı muhtemelen geçme şansım sıfır olurdu. Bugünlerde çocuklar çok daha yetenekli: Liseden itibaren benim bu ülkeye geldiğimden daha yetenekli matematikçiler oldular.

Bilginizdeki bu boşluklar lisansüstü eğitim deneyiminizi nasıl etkiledi?

Bir gün [danışmanım Gary Miller] NP'yi hiç duymadığımı keşfetti. Bir tartışmadaydı. "Bu problem NP-zor görünüyor" dedi. "Hı-hı" dedim. "Bana inanmıyor musun?" dedi. Ve sonra bunu kanıtlamaya başladı ve yarı yolda bana sert bir şekilde döndü çünkü ben orada öylece oturuyordum ve dedi ki, "NP-zorun ne olduğunu biliyor musun?" Hayır dedim.

Bunun onunla çalıştığım son gün olduğunu sanıyordum ama o devam etti ve bana tanımı anlattı. "Bilmiyorsanız, düşünebildiğiniz sürece hiçbir önemi yoktur" dedi. Onun benim üzerimde muazzam bir etkisi vardı.

Öncelikle bir teorisyensiniz ancak kariyeriniz boyunca endüstriye atılımlarda bulundunuz. Bu pratik çalışmanın teorik araştırmanızla bağlantısı nasıldı?

Tezimde grafikleri bölümlemek için bazı geometrik yöntemler geliştirdim. Bu geometrik yöntem ailesinin sonlu eleman grafikleri için kanıtlanabilir derecede iyi kesimler sağladığını göstermeyi başardım.

Akıl hocamın tavsiyesi üzerine NASA ve Boeing Aerospace'de konuşmalar yapmaya başladım. Boeing'de kanatlardan birinin 3 boyutlu modelinin halihazırda bir milyona yakın öğeye sahip olduğunu hatırlıyorum; bunu tek bir makineye bile yükleyemediler. Bu grafiği farklı bileşenlere bölüp benzer hesaplama yüklerine sahip farklı makinelere yerleştirmek ve iletişimi en aza indirmek istediler. Bu yüzden matematiksel olarak formül bir grafik kesimidir.

Teorik bilgisayar bilimlerinde, problemin görünümü optimizasyondan oyun teorisine kadar büyük ölçüde değiştiğinde bile temel matematiksel prensipler genellikle değişmez. Araştırmayı yaparken çok büyük bir değişiklikmiş gibi hissetmiyorsunuz.

Oyun teorisinden bahsetmişken, bir masa oyunu tasarlamaya yardım ettiğinizi gördüm. Bu nasıl oldu?

Ah, masa oyunlarını seviyorum! Karmaşıklık teorisiyle güzel bağlantılar var. Ama çoğunlukla öğrencilerimin öğrencisiyim.

Boston Üniversitesi'nde Sperner lemması adı verilen güzel bir ayrık teorem hakkında bir konuşma yapıyordum. Tek boyutta çok basittir. Bir ucunun kırmızı, bir ucunun mavi olduğu bir çizgi parçanız var. Bunu alt bölümlere (her iki ucunda da düğümler olacak şekilde) bölersiniz ve her yeni düğümü kırmızı veya mavi olarak renklendirirsiniz. O zaman [onları nasıl renklendirirseniz renklendirin] her iki rengi de içeren bir segment olması gerektiğini biliyoruz.

İki boyutlu olarak çok büyüleyici. Bir üçgeniniz var ve artık üç renginiz var: Bir köşesi kırmızı, bir köşesi mavi ve bir köşesi yeşil. Bu üçgeni daha küçük üçgenlere bölersiniz, böylece kenarlar parçalara ayrılır. Her dış kenar tek boyutlu kurala uyar: Düğümler yalnızca iki ucun renklerini kullanabilir. Üçgenin içinde üç rengi de istediğiniz şekilde yapabilirsiniz. Sperner'ın lemması şunu söylüyor: Hangi şekilde bölerseniz bölün, eğer bu renklendirmeyi yaparsanız, üç rengi de içeren bir üçgen olması gerekir.

Kyle Burke o zamanlar sayısal analiz üzerinde çalışan benim öğrencimdi. Ofisime geldi ve Sperner'in lemmasının güzel bir masa oyunu olabileceğini söyledi: İki oyuncu bir tahtayı tekrar tekrar boyar ve kim üç renkli bir üçgen oluşturursa oyunu kaybedecektir. En iyi masa oyunlarında beraberlik yerine kazananlar vardır ve burada açıkça birisinin kazanacağı açıktır. Neden? Çünkü Sperner'ın lemması!

İyi bir masa oyununun nelerden oluştuğunu konuşmak için Irvine'den arkadaşım David Eppstein'ı aradım. "İyi bir oyunun basit kuralları ve güzel bir tahtası vardır ve PSPACE açısından zor olmalıdır" dedi. Çünkü bunu polinom zamanda çözebilirseniz bilgisayar sizi her zaman yener.

Biz de bu kriterlerin üzerinden geçtik. Kyle, "Bu oyun basit mi?" dedi. “Evet, tek cümle!” dedim. “Bu oyun renkli mi?” dedi. "Tasarım gereği!" dedim. Sonra, "PSPACE'in zor olduğunu kanıtlarsam doktora derecesi alabilir miyim?" dedi. Ben evet dedim ve o da yaptı. Teoreminin birçok farklı yönü vardır. Matematikte çok güzel bir kavram olan sabit noktalarla ilgili bazı şeyleri ortaya çıkarıyor.

Oyunu her yerde oynayabilir miyim?

Bazı ince ayarlarla kullanılabilir, Online.

Hangi oyunları oynamayı seversin?

Ben bir oyun teorisyeniyim. [Gülüyor.] Kızımla biraz oynuyorum ama onlarla oynayarak büyümedim. Hayatları boyunca oyun oynayan öğrencilerimin aksine.

Masa oyunlarının matematiği üzerine başka hangi çalışmaları yaptınız?

Biz vardı kâğıt Geçenlerde açık bir soru hakkında: Polinom zamanla çözülebilen iki oyunu yan yana koyarsanız, bu onları PSPACE açısından zor yapar mı? Her hamlede bunlardan yalnızca birini oynayabilirsiniz. Buna oyunların toplamı denir.

İki oyunu bir araya getirmek ne anlama geliyor?

Antik Go oyununda, yeterince taş koyduğunuzda birçok ayrı arenaya sahip olursunuz, yani bir anlamda oyunların toplamını oynuyorsunuz. Şu köşe ve şu köşe için endişelenmelisin. Tamamını kazanmak istiyorsunuz ama bu her kısmı kazanmanız gerektiği anlamına gelmiyor.

Felsefi açıdan ilginç, değil mi? Sanki bir savaşınız var ve birçok savaş var ama dikkatiniz sınırlı. Herhangi bir anda savaş alanlarından yalnızca birinde tek bir karar verebilirsiniz ve rakibiniz ya karşılık verebilir ya da başka bir savaş alanında ikiye katlanabilir. Bunu babama anlatmaya çalışıyordum. Bir dizi oyun oynadığınızda bu aslında şu anlama gelir: Stratejik olarak nasıl kaybedersiniz?

Bunu iki oyun için kanıtladık, ancak üç oyunu bir araya getirebilirsiniz ve teorem hala doğrudur: Üç polinom zamanlı oyun bir araya getirildiğinde PSPACE açısından zor olabilir.

Baban seni bilgisayar bilimine yönlendirdiğinden beri, yıllar içinde yaptığın farklı çalışmalara nasıl tepki verdi?

Bana sık sık "Bunu neden yapıyorsun?" diye sorardı. Teorik olarak çalışarak, çoğu zaman yıllarca hiçbir sonuç elde edemezsiniz ve o, bunu yavaş yavaş anladı. Başlangıçta sonlu elemanlar yöntemi hakkında konuşabiliyordum; bunu inşaat mühendisliğinde de öğretiyorlar. Ama bu eğlence amaçlı matematik hakkında nasıl konuşacağımı bulamadım.

Sonra şu ünlü Çin romanından türetilmiş bir deyim aklıma geldi: Üç krallığın hikâyesi. Karakterlerden biri olan Zhuge Liang neredeyse mükemmel bir stratejistti ve deyim şöyle: "Üç ayakkabı tamircisi Zhuge Liang'dan daha iyidir." Bu, üç ortalama insanın kafa kafaya verdiklerinde mükemmel olabileceğini söylemek için bu kadar neşeli bir şekilde kullanılıyor. Ancak bu deyimin geçmişine baktığınızda farklı bölgelerde bazı şeylerin farklı telaffuz edildiğini ve “ayakkabı tamircisi” ile “saha generali”nin aynı sese sahip olduğunu görürsünüz. Yani diyor ki, "Üç saha generali birlikte bu mükemmel stratejistten daha iyidir."

Babama oyunların toplamıyla kanıtladığımız teoremin tam olarak bu olduğunu söyledim. Saha generalleri polinom zamanlı oyunları [çözmek için algoritmaları] temsil eder: Her savaş alanında nasıl kazanılacağını bilirler. Ancak işin zor kısmı, bileşen oyunlarının her birinin nasıl kazanılacağını değil, ne zaman kaybedeceğinizi bilmektir. Birisi bu zor oyunu oynayabiliyorsa, o gerçekten en iyi stratejisttir. Saha generalleri bu derin mantıksal kararları vermezler, ancak bunları bir şekilde güzel bir şekilde bir araya getirirseniz, bu mükemmel stratejistten daha kötü değiller.

Babama, "En sonunda ünlü deyimlerimizden birine eşdeğer olan bu matematik teoremini fark ettim!" dedim. O zamanlar 94 yaşındaydı, çok zekiydi ve "Bu iyi bir deneme" dedi. Onu pek ikna edemedim. Bu onunla yaptığım son teknik konuşmaydı; birkaç ay sonra vefat etti. Ne zaman çalışmamı açıklamayı düşünsem, bu benim en önemli noktamdır.