Oyun yapay zekasının kökeni ve evrimi
Bu makale Microsoft Research AI Headlines (MSRAsia) , AI Teknolojisi İncelemesi Yeniden yazdırmaya yetkili, yeniden yazdırmanız gerekirse lütfen Microsoft Research AI başlığına başvurun.
Bilgisayar bilimcileri, satranç becerilerini geliştirmek istedikleri için değil, yapay zeka algoritmalarını ve süreçteki karmaşık sorunlarla başa çıkma becerilerini sürekli olarak iyileştirmeyi umdukları için AI oyununa her zaman hevesli olmuşlardır. Aslında, AI oyununun tarihi neredeyse yapay zekanın tarihi kadar uzundur.Yapay zeka üzerine yapılan birçok araştırma, oyunları tamamlayabilecek bir ajanın nasıl inşa edileceğine dair araştırmalardan kaynaklanmaktadır. Oyun AI'sının evrimine her zaman AI araştırmasının ilerlemesi eşlik etti.
Yapay zeka araştırmalarının satranç ve kart oyunlarını tavla, dama, satranç, poker ve Go gibi deneysel nesneler olarak seçmesinin nedeni, temelde aşağıdaki özelliklere sahip olmalarıdır:
1) Hepsi, sonucun ve eylem kriterlerinin belirlenmesi için açık koşullara sahip basit ve açık bir kurala sahiptir;
2) Halkın algısında, bu satranç ve kart oyunlarında ustalaşmak ve ustalaşmak çoğu zaman insan zekasının bir dereceye kadar tezahürüdür.
1956'da taslaklar başladı Takviye öğrenme algoritmalarını kullanın
Aslında, Alan Turing'in yapay zekanın ana hatlarını belirlemesinden çok önce, bilgisayar bilimcileri "akıllı" programlarını oyunlarda test etmeye çoktan başladılar.
1928'de John Vonn Neuman, Minimax (Minimax) algoritmasını yayınladı ve 1949'da Claude Shannon algoritmayı yeniden düzenleyerek satranç problemlerini çözmek için kullandı. 1956'da Dartmouth Konferansı düzenlendi ve bir disiplin olarak yapay zeka kuruldu. Aynı yıl Arthur Samuel, kendi kendine öğrenme yoluyla Dama oyununu fethedebilecek bir algoritma icat etti.Şimdi algoritmanın adı Takviye Öğrenme.
daha fazla okuma
Oyun Ağacı Bir oyunda çeşitli sonraki olasılıkları ifade etmek için bir ağaç kullanılır.Tam bir oyun ağacında, oyundaki belirli bir durumu temsil eden bir başlangıç düğümü olacaktır; bir sonraki seviyenin alt düğümleri, üst seviyenin ana düğümleridir. Bir sonraki adım için çeşitli olasılıklar, oyunun sonuna kadar bu kurala göre genişletilir. Oyun ağacındaki yaprak düğümler, oyunun bittiği olası durumları temsil eder.
Minimax algoritması (Minimax) Claude Shannon tarafından tanımlanan satrancı çözmek için bir algoritmadır ve algoritma ilk olarak 1927'de John Vonn Neuman tarafından icat edilmiştir. Algoritma şu şekilde özetlenebilir: İki oyunculu bir yüzleşme oyunu için, herhangi bir oyuncunun kararı diğer oyuncunun önceki kararına bağlı olacaktır ve diğer oyuncu her zaman kazanmak için elinden gelenin en iyisini yapar. Bu nedenle, bir taraf tüm seçenekler arasından en fazla avantaja sahip olanı seçerken, diğer taraf rakipten en az avantaja sahip olanı seçecektir. Algoritma, farklı oyuncular arasındaki stratejileri ayrıntılı bir şekilde sıralayarak bir arama ağacı oluşturabilir ve farklı olasılıkları ayrıntılı bir şekilde sıralayarak en iyi sonucu alabilecek yolu seçebilir. Pratikte, farklı oyunlar farklı durum uzayı karmaşıklığı içerebileceğinden, algoritmanın hesaplama karmaşıklığı katlanarak artacaktır, bu nedenle aramanın karmaşıklığını basitleştirmek için, örneğin durumu tahmin etmek için budama stratejileri kullanmak genellikle gereklidir. (Sonuç) değerlendirme işlevi (Değerlendirme İşlevi).
Alfa-Beta budama Minimax algoritmasında değerlendirilecek düğüm sayısını azaltmak için kullanılan bir arama budama algoritmasıdır. Algoritma, arama işlemi sırasında her zaman iki değeri korur: alfa, bulunan en iyi değeri tanımlamak için kullanılır, daha küçük bir değere sahip herhangi bir düğümün aramaya devam etmesi gerekmez ve beta, rakibin nasıl olduğunu açıklamak için kullanılır. En kötü değerden bahsetmişken, seçeneklerden herhangi biri beta değerinden büyükse, bu rakibin mevcut duruma gitmeyi seçmeyeceği anlamına gelir, böylece arama da durdurulabilir.
Şekil 1: Basit bir Minimax arama ağacı (solda); Alfa-Beta budama stratejisine sahip Minimax arama ağacı (sağda) ( adresinden)
199 2 yılda tavla atılımı bir kilometre taşı oldu
Tavla'nın akıllı programının atılımı, yapay zeka araştırmaları tarihinde bir kilometre taşı olarak kabul ediliyor. 1970 civarında, Alman satranç oyuncusu Hans Berliner, akıllı tavla programı BKG 9.8'i yazdı.
Şekil 2: Tavla (solda); TD-Gammon'un model yapısı (sağda)
Geldi 199 Gerald Tesauro, 2 yıl içinde TD-Gammon'u yazdı. Yapay sinir ağları Model olarak ve benimsendi TD-lambda Algoritma eğitildi. Birçok kendi kendine oyun sayesinde, TD-Gammon en üst düzey insan seviyesine ulaştı ve TD-Gammon'un satranç oyununu insan oyunculardan farklı kılan, insan oyuncular olmadan bu eğitim yöntemidir. TD-Gammon'un önemi sadece Takviye öğrenme Eğitim, özellik mühendisliğine ihtiyaç duyulmadığını kanıtlıyor.Sadece satranç taşının konumunu sinir ağının girdisi olarak kullanmak, en iyi insan oyuncular seviyesine ulaşan bir aracı eğitebilir.
Tavla bölümü kazanır veya kaybeder
Başlangıçta akıllı tavla programı BKG 9.8, yeni başlayanlarla satranç oynarken sıklıkla kaybeder. Ancak daha sonra Berliner, programı sürekli iyileştirmek için bulanık mantık ilkesini kullandı ve sonunda 19 79 Temmuz 2007'de, o zamanki dünya tavla şampiyonu İtalyan Luigi Villa'yı 7: 1 yendi. Ancak Berliner, bunun çoğunlukla şans eseri olduğunu ve zar atışlarının bilgisayar için daha faydalı olduğuna da dikkat çekti.
1990'lar, Dama ve satranç yapay zekası insanları geride bıraktı
Bilgisayar hesaplama gücündeki önemli artış ve yapay zeka algoritmalarının kademeli olgunluğuyla, Arthur Samuel'in dama çözmek için ilk algoritmayı yazmasından 38 yıl sonra, Albert Üniversitesi'nden Profesör Jonathan Schaeffer 199 Ekibin 4 yıl içinde Chinook'u yazmasına öncülük eden programın çekirdeği hala kullanıyor Arama ağacı Algoritma, arama ağacının hesaplama karmaşıklığını azaltmak ve tahmin fonksiyonunun doğruluğunu iyileştirmek için taslak ustalarının açılış yöntemlerini ve oyunsonunun sonucunu içeren bir veri tabanı oluşturdu ve bir manuel özellik tabanlı Alfa-Beta ağaç araması algoritması.
199 4 yıl içinde Chinook ile dünya şampiyonu Marion Tinsley arasında oynanan dama finalinde Marion Tinsley rahatsızdı ve arka arkaya 6 kez Chinook ile berabere kaldıktan sonra oyundan vazgeçti, bu yüzden Chinook bir insan oyuncuya karşı ilk kazanan oldu. Taslaklar dünya şampiyonu için akıllı program. Profesör Jonathon Schaeffer, 2007 yılında dama sorununun yapay zeka ile çözüldüğünü kanıtlayan bir makale yayınladı.
Şekil 3: Marion Tinsley - Chinook (solda); Garry Kasparov - Deep Blue (sağda)
Öte yandan, satranç AI, Xu Fengxiong liderliğindeki Derin Düşünce ekibi tarafından da fethedildi. Derin düşünme, arama hızlandırma için özel bir donanım tasarımı kullanır ve bu temelde, tek adımlı bir uzantı (tekil uzantılar) algoritması sunar. Temel fikri şudur: katman katman bir strateji araması gerçekleştirirseniz, belirli bir adımın sonucunun bundan önemli ölçüde daha iyi olduğunu görürsünüz. Diğer hamleler için, tuzak olmadığını doğrulamak için bu hamle arayışı daha da derinleştirilecektir.
Bundan sonra, Deep Blue ekibi IBM tarafından işe alındı ve Big Blue ana bilgisayarına (daha sonra Deep Blue olarak değiştirildi) başvurdu. 199 Dünya satranç şampiyonu Garry Kasparov'u 7 yılda 3,5: 2,5 yendi. Kasparov'a karşı oynanan oyunda Deep Blue, saniyede 200 milyon hareket hesaplayabilen ve sonraki 12 hamleyi arama ve tahmin edebilen özel olarak tasarlanmış bir ana bilgisayarın güçlü hesaplama gücünden yararlandı (tek adımlı genişletme durumunda aranabilir 40 hareket). Sonunda, Deep Blue Bilgisayar, insan dünya satranç şampiyonunu standart zaman sınırı içinde yenen ilk bilgisayar sistemi oldu.
Go AI, evrimini tamamlar ve başlangıçta tarihsel misyonunu gerçekleştirir
Buna karşılık, Go durumu yukarıda belirtilen tahta oyunlarından çok daha karmaşıktır (her hareket için seçenek aralığı 19 * 19'dur) ve satranç stratejisi oyunun değerlendirilmesine çok bağlıdır.Bu nedenle Go her zaman bir karşılaştırma olarak görülmüştür. Satranç gibi daha zor tahta oyunları.
1968'de Albert Zobrist, yalnızca genç oyuncuları yenebilecek ilk Go programını yazdı. 199 3 yıl içinde Bernd Brügmann, tahmin fonksiyonu yerine Monte Carlo algoritmasını kullanarak Monte Carlo Go programını yazdı.Program artık göreve göre sonuç için tahmin fonksiyonunu dikkatlice tasarlamıyor, ancak Çoklu örnekleme (kullanıma sunma) -Oyunun sonuna kadar kendi kendine oyunun ortalama değeri tahmini sonucun yerini alır. Bu algoritma aynı zamanda AlphaGo'nun başarısı için temel algoritma olarak kabul edilir.
2006 yılında, Fransız Ulusal Bilgi ve Otomasyon Enstitüsü'nde (INRIA) araştırmacı olan Sylvain Gelly, Monte Carlo Go temelinde UCT algoritmasını tanıttı ve MoGo programını oluşturdu. 2008 yılında, program, serbest bırakılma durumunda profesyonel 8'i yendi. Sahne oyuncusu Kim Myung Wan. MoGo'nun başarısı, Go problemini çözmede MCTS (UCT) algoritmasının önemini tam olarak kanıtlamaktadır.
DeepMind ekibi 2015 yılında bir Derin takviye öğrenme AlphaGo programı, Avrupa Go şampiyonu Fan Hui'yi başarıyla yendi ve profesyonel bir Go oyuncusunu 19 yönlü bir satranç tahtasında hiçbir hamle yapmadan yenebilen ilk bilgisayar Go programı oldu.
daha fazla okuma
Monte Carlo Ağaç Arama (MCTS) Monte Carlo algoritmasını oyun ağacı aramasına uygulayan, 2006 yılında Rémi Coulom tarafından icat edilen bir algoritmadır. Algoritmanın temel fikri, tahmin fonksiyonuna göre tahmin edilen sonucu simülasyon ortamından elde edilen sonuçla değiştirmektir. Aynı yıl, L. Kocsis ve C. Szepesvari, UCB'yi Monte Carlo aramasıyla birleştirerek arama stratejileri için keşif ve kullanımı dengelemek için bir yol sağlayan UCT algoritmasını icat etti. Halihazırda uygulanan MCTS, genellikle UCT uygulamasını benimser.
CFR (Karşı-olgusal Pişmanlık Minimizasyonu) Bu, Martin Zinkevich tarafından 2007'de önerilen bir algoritmadır. Algoritma, oyun bittikten sonra pişmanlık değerini en aza indirme yöntemi ile rastgele bir strateji ile başlar, daha sonra optimal oyun stratejisini ve Nash dengesini bulmak için en iyi seçeneği arar. Algoritmanın oyunun olası tüm durumlarını geçmesi gerekir, bu nedenle hesaplama miktarını azaltmak için budama, tahmin ağı ve durum sıkıştırma gibi yöntemleri de benimsemesi gerekir.
Kusursuz bilgi oyunu AI daha karmaşıktır, Tarih sahnesinde başladı
Yukarıda belirtilen satrançla karşılaştırıldığında, poker, briç ve mahjong gibi kart oyunları başka bir oyun türü olarak kabul edilir.Bu oyunlarda, oyuncuların bilgileri genellikle asimetriktir. Bu tür oyunlara Kusurlu bilgi oyunu (Kusurlu bilgi oyunu).
Bilgi asimetrisi nedeniyle, Texas Hold'em gibi oyunlarda oyuncular, blöf yaparak rakiplerini yanıltabilirler.Genellikle, en iyi insan oyuncuların bu tekniği (sanat) çoktan öğrendiklerine inanılmaktadır. Albert Üniversitesi'ndeki araştırmacılar Texas Hold'em yapay zekasının geliştirilmesini teşvik ediyor, 198 4 yıllık profesyonel poker oyuncusu Mike Caro, Alberta Üniversitesi araştırmacısı Jonathon Schaeffer'in Orac programını yazdı. 199 Loki, 7 yıl içinde Texas Hold'em oyuncularının blöf yapma davranışını simüle etmek için yazılmıştır. 2001 yılında, program PsOpti olarak yeniden adlandırılmış ve oyun teorisine dayalı bir yöntem sunmuştur. 2015 yılında Cepheus piyasaya sürülmüştür. Program bir önceki temelde tanıtılmıştır. Gmp CFR + Algoritma, iki kişilik sınırlı bahis Texas Hold'em'i çözüyor ve bilgisayarın sınırlı bahis durumunda insanları tamamen yenebileceğini kanıtlıyor. 2017 yılında, Carnegie Mellon Üniversitesi ve Albert Üniversitesi, iki kişilik sınırsız Texas Hold'em'de dünyanın en iyi insan oyuncularını başarıyla yenen Libratus ve DeepStack'i arka arkaya yayınladı. 2019'da Carnegie Mellon University ve Facebook AI, altı kişilik limitsiz pokerde profesyonel poker oyuncularını başarıyla mağlup eden Libratus, Pluribus'un halef sürümünü yayınladı.
Öte yandan, bu eksik bilgi durumu, oyun stratejisini daha karmaşık hale getirir ve bu da oyunu temel alan Ağaç arama ile CFR Algoritma sisteminin hesaplama karmaşıklığı daha büyüktür. Oyunun nispeten karmaşık kuralları nedeniyle (teklif verme aşaması ve oyun aşaması dahil), briç yavaş yavaş yapay zekanın nesnesi haline geldi. 1980'lerin başında, bir zamanlar ABD Donanması Columbia Bölge Laboratuvarı'nda çalışan Tom Throop, Bridge Baron programını yazmaya başladı. On yıldan fazla güncellemelerden sonra, 199 7 yılda ilk Dünya Bilgisayar Köprüsü Yarışması'nı kazandı. İkinci yılda, yarışmanın şampiyonu Oregon Üniversitesi'nden Matthew Ginsberg tarafından geliştirilen GIB programı ile kazanıldı. Aynı yıl, program Dünya Briç Şampiyonalarına katılmaya davet edildi ve nihayet 35 katılımcı arasında 12'nci oldu. Takip eden on yıl içinde, Monte Carlo yöntemine dayanan Jack ve Wbridge5 rekabeti sırayla kazandı. Mahjong için, Tokyo Üniversitesi'nden Naoki Mizukami, 2015'te Baku Da adlı bir AI programı geliştirdi ve Japon Dwango da 2018'de bir derin öğrenme modeline dayalı NAGA025'i geliştirdi. Ancak genel olarak, bu yapay zeka programlarının en iyi insan oyuncularla hala bazı boşlukları var.
Satranç ve go gibi "mükemmel bilgi" içeren tahta oyunları ve Texas Hold'em, briç ve mahjong gibi "kusurlu bilgiler" içeren kart oyunları ile karşılaştırıldığında, sadece "kusurlu bilgilere" sahip olmakla kalmayıp aynı zamanda daha fazla gizli bilgiye sahip oldukları için daha zordur. Uzay. Bu doğa, onları insanın gerçek yaşamındaki karar verme sürecine daha da yaklaştırır. Oyun yapay zekasındaki bu tür atılımlar, oyun yapay zekası araştırmalarında bir sonraki dönüm noktası olabilir.
Şekil 4: Oyun AI gelişiminin geçmişi
Referans malzemeleri:
http: // www .bridgeguys .com /CGlossary/Computer/CBProgrammers.pdf
http: // www .andreykurenkov .com / yazma / ai / a-kısa-oyun-geçmişi-ai /
