Oyunlarda yapay zeka ile ilgili ilginç materyallere rastladım. Yapay zeka ile ilgili temel şeylerin basit örnekler kullanılarak açıklandığı bu kitapta, yapay zekanın uygun şekilde geliştirilmesi ve tasarlanması için birçok faydalı araç ve yöntem bulunmaktadır. Bunların nasıl, nerede ve ne zaman kullanılacağı da oradadır.
Örneklerin çoğu sözde kodla yazılmıştır, dolayısıyla ileri düzey programlama bilgisine gerek yoktur. Kesimin altında resim ve gif'lerin bulunduğu 35 sayfalık metin var, o yüzden hazır olun.
GÜNCELLEME. Özür dilerim ama Habré'deki bu makalenin kendi çevirisini zaten yaptım. . Onun versiyonunu okuyabilirsiniz , ancak bazı nedenlerden dolayı makale beni geçmedi (aramayı kullandım ancak bir şeyler ters gitti). Ve oyun geliştirmeye adanmış bir blogda yazdığım için, çevirinin kendi versiyonunu abonelere bırakmaya karar verdim (bazı noktalar farklı biçimlendirilmiş, bazıları geliştiricilerin tavsiyesi üzerine kasıtlı olarak çıkarılmıştır).
AI nedir?
Game AI, bir nesnenin bulunduğu koşullara bağlı olarak hangi eylemleri gerçekleştirmesi gerektiğine odaklanır. Bu genellikle "akıllı temsilci" yönetimi olarak adlandırılır; burada bir temsilci bir oyuncu karakteri, bir araç, bir bot veya bazen daha soyut bir şey olabilir: bütün bir varlık grubu, hatta bir medeniyet. Her durumda çevresini görmesi, ona göre karar vermesi ve ona göre hareket etmesi gereken bir şeydir. Buna Duyu/Düşün/Eylem döngüsü denir:
- Duyu: Aracı, çevresinde davranışını etkileyebilecek şeyler (yakındaki tehditler, toplanacak öğeler, keşfedilecek ilginç yerler) hakkında bilgi bulur veya alır.
- Düşünün: Temsilci nasıl tepki vereceğine karar verir (eşyaları toplamanın yeterince güvenli olup olmadığını veya önce savaşması/saklanması gerekip gerekmediğini değerlendirir).
- Harekete Geçme: Temsilci önceki kararı uygulamak için eylemler gerçekleştirir (düşmana veya nesneye doğru hareket etmeye başlar).
- ...artık karakterlerin eylemleri nedeniyle durum değişti, dolayısıyla döngü yeni verilerle tekrarlanıyor.
Yapay zeka döngünün Sense kısmına odaklanma eğilimindedir. Örneğin otonom arabalar yolun fotoğraflarını çekiyor, bunları radar ve lidar verileriyle birleştirip yorumluyor. Bu genellikle, gelen verileri işleyen ve ona anlam veren, "20 metre önünüzde başka bir araba var" gibi anlamsal bilgileri çıkaran makine öğrenimi tarafından yapılır. Bunlar sözde sınıflandırma problemleridir.
Verilerin çoğu zaten onun ayrılmaz bir parçası olduğundan, oyunların bilgi elde etmek için karmaşık bir sisteme ihtiyacı yoktur. İleride bir düşman olup olmadığını belirlemek için görüntü tanıma algoritmaları çalıştırmaya gerek yok; oyun zaten biliyor ve bilgiyi doğrudan karar verme sürecine aktarıyor. Bu nedenle döngünün Duyu kısmı genellikle Düşün ve Harekete Geç kısmından çok daha basittir.
Oyun Yapay Zekasının Sınırlamaları
Yapay zekanın uyulması gereken bir takım sınırlamaları vardır:
- Yapay zekanın sanki bir makine öğrenimi algoritmasıymış gibi önceden eğitilmesine gerek yoktur. On binlerce oyuncuyu izlemek ve onlara karşı oynamanın en iyi yolunu öğrenmek için geliştirme sırasında bir sinir ağı yazmanın hiçbir anlamı yok. Neden? Çünkü oyun henüz çıkmadı ve oyuncu yok.
- Oyun eğlenceli ve zorlu olmalı, bu nedenle ajanlar insanlara karşı en iyi yaklaşımı bulmamalıdır.
- Oyuncuların gerçek insanlara karşı oynuyormuş gibi hissetmeleri için temsilcilerin gerçekçi görünmesi gerekir. AlphaGo programı insanlardan daha iyi performans gösterdi ancak seçilen adımlar oyunun geleneksel anlayışından çok uzaktı. Eğer oyun bir insan rakibi simüle ediyorsa bu duygunun olmaması gerekir. Algoritmanın ideal kararlar yerine makul kararlar vermesi için değiştirilmesi gerekiyor.
- Yapay zeka gerçek zamanlı olarak çalışmalıdır. Bu, algoritmanın karar vermek için CPU kullanımını uzun süre tekeline alamayacağı anlamına gelir. 10 milisaniye bile çok uzun çünkü çoğu oyunda tüm işlemleri gerçekleştirmek ve bir sonraki grafik karesine geçmek için yalnızca 16 ila 33 milisaniye gerekir.
- İdeal olarak sistemin en azından bir kısmının veriye dayalı olması gerekir, böylece kodlayıcı olmayanlar değişiklik yapabilir ve ayarlamalar daha hızlı yapılabilir.
Tüm Duyma/Düşünme/Eylem Etme döngüsünü kapsayan yapay zeka yaklaşımlarına bakalım.
Temel Kararlar Vermek
En basit oyun olan Pong ile başlayalım. Amaç: Raketi, topun yanından uçmak yerine üzerinden sekecek şekilde hareket ettirin. Bu, topa vurmazsanız kaybettiğiniz tenis gibidir. Burada yapay zekanın nispeten kolay bir görevi var; platformu hangi yöne hareket ettireceğine karar vermek.
Koşullu ifadeler
Pong'daki yapay zeka için en bariz çözüm, platformu her zaman topun altına yerleştirmeye çalışmaktır.
Bunun için sözde kodla yazılmış basit bir algoritma:
oyun çalışırken her kare/güncelleme:
eğer top raketin solundaysa:
küreği sola hareket ettir
Aksi takdirde top raketin sağındaysa:
küreği sağa hareket ettir
Platform top hızında hareket ediyorsa bu, Pong'daki yapay zeka için ideal algoritmadır. Temsilci için çok fazla veri ve olası eylemler yoksa hiçbir şeyi karmaşıklaştırmaya gerek yoktur.
Bu yaklaşım o kadar basittir ki Duyu/Düşün/Eylem döngüsünün tamamı zar zor fark edilir. Ama orada:
- Sense kısmı iki if ifadesinden oluşur. Oyun topun nerede olduğunu ve platformun nerede olduğunu biliyor, dolayısıyla yapay zeka bu bilgi için ona bakıyor.
- Think kısmı aynı zamanda iki if ifadesinin içinde yer alır. Bu durumda birbirini dışlayan iki çözümü içerirler. Sonuç olarak, üç eylemden biri seçilir: platformu sola hareket ettirin, sağa hareket ettirin veya zaten doğru konumlandırılmışsa hiçbir şey yapmayın.
- Act kısmı, Raketi Sola Taşı ve Raketi Sağa Taşı ifadelerinde bulunur. Oyun tasarımına bağlı olarak platformu anında veya belirli bir hızda hareket ettirebilirler.
Bu tür yaklaşımlara reaktif denir - dünyanın mevcut durumuna tepki veren ve harekete geçen basit bir kurallar dizisi (bu durumda kodda ifadeler varsa) vardır.
Karar ağacı
Pong örneği aslında karar ağacı adı verilen resmi bir yapay zeka kavramına eşdeğerdir. Algoritma bir "yaprağa", yani hangi eylemin gerçekleştirileceğine ilişkin bir karara ulaşmak için bu sürecin içinden geçer.
Platformumuzun algoritması için karar ağacının blok diyagramını yapalım:
Ağacın her bir parçasına düğüm denir; yapay zeka, bu tür yapıları tanımlamak için grafik teorisini kullanır. İki tür düğüm vardır:
- Karar düğümleri: Her bir alternatifin ayrı bir düğüm olarak temsil edildiği, bazı koşulların test edilmesine dayalı olarak iki alternatif arasında seçim yapılması.
- Son düğümler: Nihai kararı temsil eden gerçekleştirilecek eylem.
Algoritma ilk düğümden (ağacın “kökü”) başlar. Ya hangi alt düğüme gideceğine karar verir ya da düğümde saklanan eylemi yürütür ve çıkar.
Önceki bölümde anlatılan if ifadeleriyle aynı işi yapan bir karar ağacına sahip olmanın faydası nedir? Burada her kararın tek koşulu ve iki olası sonucu olan genel bir sistem var. Bu, geliştiricinin, bir ağaçtaki kararları temsil eden verilerden, sabit kodlamaya gerek kalmadan yapay zeka oluşturmasına olanak tanır. Tablo halinde sunalım:
Kod tarafında dizeleri okumak için bir sistem alacaksınız. Her biri için bir düğüm oluşturun, karar mantığını ikinci sütuna, alt düğümleri ise üçüncü ve dördüncü sütunlara göre bağlayın. Hala koşulları ve eylemleri programlamanız gerekiyor, ancak artık oyunun yapısı daha karmaşık olacak. Burada ek kararlar ve eylemler ekleyebilir ve ardından ağaç tanımı metin dosyasını düzenleyerek yapay zekanın tamamını özelleştirebilirsiniz. Daha sonra dosyayı, oyunu yeniden derlemeden veya kodu değiştirmeden davranışı değiştirebilecek olan oyun tasarımcısına aktarırsınız.
Karar ağaçları, geniş bir örnek kümesinden (örneğin, ID3 algoritması kullanılarak) otomatik olarak oluşturulduklarında çok faydalıdır. Bu onları, elde edilen verilere dayalı olarak durumları sınıflandırmak için etkili ve yüksek performanslı bir araç haline getirir. Ancak temsilcilerin eylemleri seçebileceği basit bir sistemin ötesine geçiyoruz.
senaryolar
Önceden oluşturulmuş koşulları ve eylemleri kullanan bir karar ağacı sistemini analiz ettik. Yapay zekayı tasarlayan kişi ağacı istediği gibi düzenleyebilir ancak yine de her şeyi programlayan kodlayıcıya güvenmek zorundadır. Peki ya tasarımcıya kendi koşullarını veya eylemlerini yaratması için gerekli araçları verebilseydik?
Programcının Top Raketin Solunda mı ve Top Raketin Sağında mı koşulları için kod yazmasına gerek kalmaması için, tasarımcının bu değerleri kontrol etmek için koşulları yazacağı bir sistem oluşturabilir. Daha sonra karar ağacı verileri şöyle görünecektir:
Bu aslında ilk tablodakiyle aynıdır, ancak çözümlerin kendi içlerinde kendi kodları vardır, biraz if ifadesinin koşullu kısmına benzer. Kod tarafında, bu, karar düğümleri için ikinci sütunda okunur, ancak yürütülecek belirli bir koşulu aramak yerine (Top Raketin Solunda mı), koşullu ifadeyi değerlendirir ve buna göre doğru veya yanlış değerini döndürür. Bu, Lua veya Angelscript kodlama dili kullanılarak yapılır. Geliştirici bunları kullanarak oyunundaki nesneleri (top ve raket) alabilir ve komut dosyasında (ball.position) mevcut olacak değişkenler oluşturabilir. Ayrıca kodlama dili C++'dan daha basittir. Tam bir derleme aşaması gerektirmez, bu nedenle oyun mantığını hızlı bir şekilde ayarlamak için idealdir ve "kodlayıcı olmayanların" gerekli işlevleri kendilerinin oluşturmasına olanak tanır.
Yukarıdaki örnekte kodlama dili yalnızca koşullu ifadeyi değerlendirmek için kullanılmıştır ancak eylemler için de kullanılabilir. Örneğin, Move Paddle Right verileri bir komut dosyası ifadesi haline gelebilir (ball.position.x += 10). Böylece, Move Paddle Right'ı programlamaya gerek kalmadan eylem komut dosyasında da tanımlanır.
Daha da ileri giderek karar ağacının tamamını bir kodlama dilinde yazabilirsiniz. Bu, sabit kodlanmış koşullu ifadeler biçiminde bir kod olacaktır, ancak bunlar harici komut dosyalarında bulunacaktır, yani programın tamamı yeniden derlenmeden değiştirilebilirler. Farklı AI tepkilerini hızlı bir şekilde test etmek için oyun sırasında komut dosyasını sıklıkla düzenleyebilirsiniz.
Olay Yanıtı
Yukarıdaki örnekler Pong için mükemmeldir. Sürekli olarak Hisset/Düşün/Eylem Et döngüsünü çalıştırırlar ve dünyanın en son durumuna göre hareket ederler. Ancak daha karmaşık oyunlarda bireysel olaylara tepki vermeniz ve her şeyi bir anda değerlendirmemeniz gerekir. Bu durumda Pong zaten kötü bir örnek. Başka birini seçelim.
Düşmanların oyuncuyu tespit edene kadar hareketsiz kaldığı, ardından "uzmanlıklarına" göre hareket ettikleri bir tetikçi hayal edin: Birisi "acele etmek" için koşacak, birisi uzaktan saldıracak. Bu hala temel bir reaktif sistemdir - "bir oyuncu tespit edilirse bir şeyler yapın" - ancak mantıksal olarak Oyuncunun Gördüğü etkinliğine ve Tepkiye (bir yanıt seçin ve onu yürütün) bölünebilir.
Bu bizi Duyu/Düşün/Eylem döngüsüne geri getirir. Yapay zekanın oynatıcıyı görüp görmediğini her karede kontrol edecek bir Sense kısmını kodlayabiliriz. Değilse hiçbir şey olmaz, ancak görürse Oyuncu Görüldü olayı oluşturulur. Kodda "Oyuncu Görüldü olayı oluştuğunda yapın" yazan ayrı bir bölüm bulunacaktır; burada Düşün ve Harekete Geç bölümlerine yanıt vermeniz gerekir. Böylece, Oyuncu Görüldü etkinliğine tepkiler ayarlayacaksınız: "acele eden" karakter için - ChargeAndAttack ve keskin nişancı için - HideAndSnipe. Bu ilişkiler, yeniden derlemeye gerek kalmadan hızlı düzenleme için veri dosyasında oluşturulabilir. Burada da script dili kullanılabilir.
Zor kararlar vermek
Basit reaksiyon sistemleri çok güçlü olmasına rağmen yeterli olmadıkları birçok durum vardır. Bazen temsilcinin o anda ne yaptığına bağlı olarak farklı kararlar vermeniz gerekebilir, ancak bunu bir koşul olarak hayal etmek zordur. Bazen bunları bir karar ağacında veya senaryoda etkili bir şekilde temsil etmek için çok fazla koşul vardır. Bazen bir sonraki adıma karar vermeden önce durumun nasıl değişeceğini önceden değerlendirmeniz gerekir. Bu sorunları çözmek için daha karmaşık yaklaşımlara ihtiyaç vardır.
Sonlu durum makinesi
Sonlu durum makinesi veya FSM (sonlu durum makinesi), aracımızın şu anda birkaç olası durumdan birinde olduğunu ve bir durumdan diğerine geçebileceğini söylemenin bir yoludur. Bu tür belirli sayıda durum vardır; adı da buradan gelir. Hayattan en güzel örnek trafik ışığıdır. Farklı yerlerde farklı ışık dizileri vardır, ancak prensip aynıdır; her durum bir şeyi temsil eder (durma, yürüme vb.). Bir trafik ışığı herhangi bir zamanda yalnızca tek bir durumdadır ve basit kurallara göre bir durumdan diğerine hareket eder.
Oyunlardaki NPC'lerde de benzer bir hikaye var. Örneğin aşağıdaki durumlara sahip bir guard'ı ele alalım:
- Devriye geziyorum.
- Saldırıyor.
- Kaçmak.
Ve durumunu değiştirmek için bu koşullar:
- Muhafız düşmanı görürse saldırır.
- Muhafız saldırır ancak düşmanı artık göremezse devriye görevine geri döner.
- Bir gardiyan saldırır ama ağır yaralanırsa kaçar.
Ayrıca koruyucu durum değişkeni ve çeşitli kontroller içeren if ifadeleri de yazabilirsiniz: yakınlarda bir düşman var mı, NPC'nin sağlık seviyesi nedir, vb. Birkaç durum daha ekleyelim:
- Tembellik - devriyeler arasında.
- Arama - fark edilen düşman ortadan kaybolduğunda.
- Yardım Bulma: Bir düşman tespit edildiğinde ancak tek başına savaşamayacak kadar güçlü olduğunda.
Her birinin seçeneği sınırlıdır - örneğin, gardiyan, sağlığı düşükse gizli bir düşmanı aramayacaktır.
Sonuçta kocaman bir "eğer" listesi var , O "çok hantal hale gelebilir, bu nedenle durumları ve durumlar arasındaki geçişleri akılda tutmamıza izin veren bir yöntemi resmileştirmemiz gerekiyor. Bunu yapmak için, tüm durumları dikkate alıyoruz ve her durumun altında, diğer durumlara tüm geçişleri, onlar için gerekli koşullarla birlikte bir listeye yazıyoruz.
Bu bir durum geçiş tablosudur; FSM'yi temsil etmenin kapsamlı bir yoludur. Bir diyagram çizelim ve NPC davranışının nasıl değiştiğine dair tam bir genel bakış elde edelim.
Diyagram, mevcut duruma göre bu temsilci için karar vermenin özünü yansıtmaktadır. Üstelik her ok, yanındaki koşulun doğru olması durumunda durumlar arasındaki geçişi gösterir.
Her güncellemede aracının mevcut durumunu kontrol ediyoruz, geçiş listesine bakıyoruz ve geçiş koşulları karşılanıyorsa yeni durumu kabul ediyoruz. Örneğin, her kare 10 saniyelik zamanlayıcının süresinin dolup dolmadığını kontrol eder ve eğer öyleyse, güvenlik görevlisi Bekleme durumundan Devriyeye geçer. Aynı şekilde, Saldıran durum, ajanın sağlığını kontrol eder; eğer düşükse, Kaçan durumuna geçer.
Bu, durumlar arasındaki geçişleri ele alıyor, peki ya durumların kendileriyle ilişkili davranışlar? Belirli bir durum için gerçek davranışın uygulanması açısından, FSM'ye eylemler atadığımız tipik olarak iki tür "kanca" vardır:
- Mevcut durum için periyodik olarak gerçekleştirdiğimiz eylemler.
- Bir durumdan diğerine geçerken yaptığımız eylemler.
Birinci tipe örnekler. Devriye durumu, aracıyı her karede devriye rotası boyunca hareket ettirecektir. Saldırı durumu, her karede veya bunun mümkün olduğu bir duruma geçişte bir saldırı başlatmaya çalışacaktır.
İkinci tür için, "düşman görünürse ve düşman çok güçlüyse, Yardım Bulma durumuna gidin" geçişini düşünün. Temsilcinin yardım için nereye gideceğini seçmesi ve Yardım Bulma durumunun nereye gideceğini bilmesi için bu bilgiyi saklaması gerekir. Yardım bulunduğunda, temsilci Saldırı durumuna geri döner. Bu noktada müttefikine tehdidi anlatmak isteyecektir, böylece Arkadaşına Bildir eylemi gerçekleşebilir.
Bir kez daha bu sisteme Duyu/Düşün/Eylem döngüsünün merceğinden bakabiliriz. Anlam, geçiş mantığı tarafından kullanılan verilerde somutlaşır. Düşün - her durumda geçişler mevcuttur. Hareket ise bir devlet içinde veya devletler arası geçişlerde periyodik olarak gerçekleştirilen eylemlerle gerçekleştirilir.
Bazen sürekli oylama geçiş koşulları maliyetli olabilir. Örneğin, her bir ajan, düşmanları görüp göremediğini belirlemek ve Devriyeden Saldırı durumuna geçip geçemeyeceğini anlamak için her karede karmaşık hesaplamalar yaparsa, bu çok fazla CPU zamanı alacaktır.
Dünyanın durumundaki önemli değişiklikler, meydana geldikçe işlenecek olaylar olarak düşünülebilir. FSM'nin her karede "temsilcim oynatıcıyı görebilir mi?" geçiş durumunu kontrol etmesi yerine, daha az sıklıkta (örneğin saniyede 5 kez) kontrol yapacak şekilde ayrı bir sistem yapılandırılabilir. Sonuç olarak, kontrol başarılı olduğunda Oyuncu Görüldü mesajı verilir.
Bu, FSM'ye iletilir ve artık Oyuncu Görüldü olayının alınması koşuluna gitmeli ve buna göre yanıt vermelidir. Ortaya çıkan davranış, yanıt vermeden önce neredeyse algılanamayan bir gecikme dışında aynıdır. Ancak Sense bölümünün programın ayrı bir bölümüne ayrılması sonucunda performans arttı.
Hiyerarşik sonlu durum makinesi
Ancak büyük FSM'lerle çalışmak her zaman uygun değildir. Saldırı durumunu MeleeAttacking ve RangedAttacking'i ayıracak şekilde genişletmek istiyorsak, Saldırı durumuna yol açan diğer tüm durumlardan geçişleri (mevcut ve gelecek) değiştirmemiz gerekecek.
Örneğimizde çok sayıda yinelenen geçiş olduğunu muhtemelen fark etmişsinizdir. Rölanti durumundaki çoğu geçiş, Devriye durumundaki geçişlerle aynıdır. Özellikle daha fazla benzer durum eklersek kendimizi tekrarlamamak güzel olur. Savaş durumlarına geçişlerin yalnızca tek bir ortak kümesinin olduğu Boşta Çalışma ve Devriyeyi "savaş dışı" genel etiketi altında gruplandırmak mantıklıdır. Bu etiketi bir durum olarak düşünürsek, Rölanti ve Devriyelik alt eyaletler haline gelir. Yeni bir savaş dışı alt durum için ayrı bir geçiş tablosu kullanma örneği:
Ana durumlar:
Savaş dışı durumu:
Ve diyagram biçiminde:
Bu aynı sistemdir ancak Rölanti ve Devriyeyi içeren yeni bir savaş dışı durumu içerir. Her durumun alt durumları olan bir FSM içermesiyle (ve bu alt durumların da kendi FSM'lerini içermesi - ve ihtiyaç duyduğunuz sürece böyle devam etmesi), bir Hiyerarşik Sonlu Durum Makinesi veya HFSM (hiyerarşik sonlu durum makinesi) elde ederiz. Savaş dışı durumu gruplandırarak bir dizi gereksiz geçişi kestik. Aynısını ortak geçişlerin olduğu yeni durumlar için de yapabiliriz. Örneğin, gelecekte Saldırı durumunu Yakın Dövüş ve Füze Saldırı durumlarına genişletirsek, bunlar düşmana olan mesafeye ve cephane mevcudiyetine bağlı olarak birbirleri arasında geçiş yapan alt eyaletler olacak. Sonuç olarak, karmaşık davranışlar ve alt davranışlar minimum sayıda tekrarlanan geçişlerle temsil edilebilir.
Davranış ağacı
HFSM ile karmaşık davranış kombinasyonları basit bir şekilde oluşturulur. Ancak geçiş kuralları şeklinde karar almanın mevcut durumla yakından ilgili olması konusunda ufak bir zorluk var. Ve birçok oyunda bu tam olarak ihtiyaç duyulan şeydir. Durum hiyerarşisinin dikkatli kullanımı geçiş tekrarlarının sayısını azaltabilir. Ancak bazen hangi eyalette olursanız olun işe yarayan veya neredeyse her eyalette geçerli olan kurallara ihtiyaç duyarsınız. Örneğin, eğer bir ajanın sağlığı %25'e düşerse, ister savaşta, ister boşta olsun, ister konuşuyor olsun, onun kaçmasını istersiniz; bu koşulu her duruma eklemeniz gerekir. Tasarımcınız daha sonra düşük sağlık eşiğini %25'ten %10'a değiştirmek isterse, bunun yeniden yapılması gerekecektir.
İdeal olarak bu durum, değişikliklerin yalnızca tek bir yerde yapılabilmesi ve geçiş koşullarının etkilenmemesi için “hangi durumda olunacağına” ilişkin kararların eyaletlerin dışında olduğu bir sistemi gerektirmektedir. Davranış ağaçları burada görünür.
Bunları uygulamanın birkaç yolu vardır, ancak özü hepsi için kabaca aynıdır ve karar ağacına benzer: Algoritma bir "kök" düğümle başlar ve ağaç, kararları veya eylemleri temsil eden düğümleri içerir. Yine de birkaç önemli fark var:
- Düğümler artık üç değerden birini döndürüyor: Başarılı (iş tamamlandıysa), Başarısız (başlatılamazsa) veya Çalışıyor (hala çalışıyorsa ve nihai sonuç yoksa).
- İki alternatif arasında seçim yapılabilecek artık karar düğümleri yoktur. Bunun yerine, bunlar bir alt düğüme sahip Dekoratör düğümlerdir. Başarılı olurlarsa tek alt düğümlerini çalıştırırlar.
- Eylemleri gerçekleştiren düğümler, gerçekleştirilen eylemleri temsil etmek için bir Çalıştırma değeri döndürür.
Bu küçük düğüm kümesi, çok sayıda karmaşık davranış oluşturmak için birleştirilebilir. Önceki örnekteki HFSM korumasını bir davranış ağacı olarak düşünelim:
Bu yapıyla, Boşta/Devriye durumundan Saldırı durumuna veya başka herhangi bir duruma belirgin bir geçiş olmamalıdır. Bir düşman görünür durumdaysa ve karakterin sağlığı düşükse, daha önce hangi düğümü çalıştırdığına bakılmaksızın (Devriye, Rölanti, Saldırı veya başka herhangi bir) yürütme Kaçan düğümde durdurulacaktır.
Davranış ağaçları karmaşıktır; bunları oluşturmanın birçok yolu vardır ve dekoratörler ile bileşik düğümlerin doğru kombinasyonunu bulmak zor olabilir. Ağacın ne sıklıkta kontrol edileceğine dair sorular da var; her parçasını mı gözden geçirmek istiyoruz, yoksa yalnızca koşullardan biri değiştiğinde mi? Düğümlere ilişkin durumu nasıl saklarız - 10 saniye boyunca Boşta kaldığımızı nasıl bileceğiz veya sırayı doğru şekilde işleyebilmemiz için en son hangi düğümlerin çalıştığını nasıl bileceğiz?
Bu nedenle birçok uygulama var. Örneğin, bazı sistemler dekoratör düğümlerini satır içi dekoratörlerle değiştirmiştir. Dekoratör koşulları değiştiğinde ağacı yeniden değerlendirir, düğümlerin birleştirilmesine yardımcı olur ve periyodik güncellemeler sağlar.
Yardımcı program tabanlı sistem
Bazı oyunların birçok farklı mekaniği vardır. Basit ve genel geçiş kurallarının tüm faydalarından yararlanmaları arzu edilir, ancak bu tam bir davranış ağacı şeklinde olması gerekmez. Açık bir seçimler dizisine veya olası eylemler ağacına sahip olmak yerine, tüm eylemleri incelemek ve o anda en uygun olanı seçmek daha kolaydır.
Yardımcı Program tabanlı sistem tam da bu konuda yardımcı olacaktır. Bu, aracının çeşitli eylemlere sahip olduğu ve her birinin göreceli faydasına göre hangisini gerçekleştireceğini seçtiği bir sistemdir. Faydanın, aracının bu eylemi gerçekleştirmesinin ne kadar önemli veya arzu edilir olduğunun keyfi bir ölçüsü olduğu durumlarda.
Bir eylemin mevcut durumuna ve ortamına dayalı olarak hesaplanan faydası, aracı herhangi bir zamanda en uygun diğer durumu kontrol edebilir ve seçebilir. Bu, geçişlerin mevcut durum da dahil olmak üzere her bir potansiyel durum için bir tahminle belirlenmesi haricinde FSM'ye benzer. Devam etmek için en yararlı eylemi seçtiğimizi (veya zaten tamamladıysak kalmayı) lütfen unutmayın. Daha fazla çeşitlilik için bu, küçük bir listeden dengeli ancak rastgele bir seçim olabilir.
Sistem, örneğin 0'dan (tamamen istenmeyen) 100'e (tamamen arzu edilen) kadar isteğe bağlı bir fayda değeri aralığı atar. Her eylemin bu değerin hesaplanmasını etkileyen bir dizi parametresi vardır. Koruyucu örneğimize dönecek olursak:
Eylemler arasındaki geçişler belirsizdir; herhangi bir durum diğerini takip edebilir. Eylem öncelikleri, döndürülen fayda değerlerinde bulunur. Bir düşman görünürse ve bu düşman güçlüyse ve karakterin sağlığı düşükse, hem Fleeing hem de FindingHelp sıfırdan farklı yüksek değerler döndürecektir. Bu durumda FindingHelp her zaman daha yüksek olacaktır. Benzer şekilde, savaş dışı faaliyetler hiçbir zaman 50'den fazla sonuç vermez, dolayısıyla bunlar her zaman savaş faaliyetlerinden daha düşük olacaktır. Eylemleri oluştururken ve bunların faydalarını hesaplarken bunu dikkate almanız gerekir.
Örneğimizde, eylemler ya sabit bir sabit değer ya da iki sabit değerden birini döndürür. Daha gerçekçi bir sistem, sürekli bir değer aralığından bir tahmin döndürecektir. Örneğin, eğer ajanın sağlığı düşükse Kaçma eylemi daha yüksek fayda değerleri döndürür ve Düşman çok güçlüyse Saldırı eylemi daha düşük fayda değerleri döndürür. Bu nedenle, ajanın düşmanı yenmek için yeterli sağlığına sahip olmadığını hissettiği herhangi bir durumda Kaçma eylemi, Saldırı eylemine göre önceliklidir. Bu, eylemlerin herhangi bir sayıda kritere göre önceliklendirilmesine olanak tanır ve bu yaklaşımı bir davranış ağacından veya FSM'den daha esnek ve değişken hale getirir.
Her eylemin program hesaplaması için birçok koşulu vardır. Komut dosyası dilinde veya bir dizi matematiksel formül olarak yazılabilirler. Bir karakterin günlük rutinini simüle eden Sims, ek bir hesaplama katmanı ekler; temsilci, fayda derecelendirmelerini etkileyen bir dizi "motivasyon" alır. Bir karakter açsa, zamanla daha da acıkacak ve EatFood eyleminin fayda değeri, karakter bunu gerçekleştirene kadar artacak, açlık seviyesi azalacak ve EatFood değeri sıfıra dönecektir.
Bir derecelendirme sistemine dayalı olarak eylemleri seçme fikri oldukça basittir, bu nedenle Yardımcı Program tabanlı bir sistem, yapay zeka karar verme süreçlerinin tamamen yerine geçmek yerine, bunların bir parçası olarak kullanılabilir. Karar ağacı iki alt düğümün fayda derecesini isteyebilir ve yüksek olanı seçebilir. Benzer şekilde, bir davranış ağacı, hangi alt öğenin yürütüleceğine karar vermek amacıyla eylemlerin faydasını değerlendirmek için bileşik bir Yardımcı Program düğümüne sahip olabilir.
Hareket ve navigasyon
Önceki örneklerde sağa veya sola hareket ettirdiğimiz bir platformumuz, devriye gezen veya saldıran bir korumamız vardı. Peki belirli bir süre boyunca temsilci hareketini tam olarak nasıl ele alacağız? Hızı nasıl ayarlayacağız, engellerden nasıl kaçınacağız ve bir hedefe ulaşmanın düz bir çizgide ilerlemekten daha zor olduğu durumlarda nasıl rota planlayacağız? Şuna bir bakalım.
Управление
İlk aşamada, her ajanın ne kadar hızlı ve hangi yönde hareket ettiğini içeren bir hız değerine sahip olduğunu varsayacağız. Saniyede metre, saatte kilometre, saniyede piksel vb. cinsinden ölçülebilir. Duyu/Düşün/Eylem döngüsünü hatırlayacak olursak, Düşünme kısmının bir hız seçtiğini ve Hareket Etme kısmının bu hızı aracıya uyguladığını hayal edebiliriz. Tipik olarak oyunlarda bu görevi sizin için yapan, her nesnenin hız değerini öğrenen ve ayarlayan bir fizik sistemi bulunur. Bu nedenle, AI'ya tek bir görev bırakabilirsiniz - aracının hangi hıza sahip olması gerektiğine karar vermek. Temsilcinin nerede olması gerektiğini biliyorsanız, onu belirli bir hızda doğru yönde hareket ettirmeniz gerekir. Çok önemsiz bir denklem:
istenen_travel = hedef_konum – aracı_konum
2 boyutlu bir dünya hayal edin. Aracı (-2,-2) noktasındadır, hedef kuzeydoğuda bir yerde (30, 20) ve aracının oraya ulaşması için gerekli yol (32, 22)'dir. Diyelim ki bu konumlar metre cinsinden ölçülüyor - eğer aracının hızını saniyede 5 metre olarak alırsak, o zaman yer değiştirme vektörümüzü ölçeklendireceğiz ve yaklaşık olarak (4.12, 2.83) bir hız elde edeceğiz. Bu parametrelerle temsilci hedefine yaklaşık 8 saniyede ulaşacaktır.
Değerleri istediğiniz zaman yeniden hesaplayabilirsiniz. Ajan hedefin yarısında olsaydı hareket uzunluğu yarısı kadar olurdu ama ajanın maksimum hızı 5 m/s olduğundan (buna yukarıda karar verdik) hızı aynı olacaktır. Bu aynı zamanda hareketli hedefler için de işe yarar ve ajanın hareket ettikçe küçük değişiklikler yapmasına olanak tanır.
Ancak daha fazla çeşitlilik istiyoruz; örneğin, bir karakterin ayakta durma pozisyonundan koşma pozisyonuna geçmesini simüle etmek için hızı yavaş yavaş artırmak. Aynı şey durmadan önce de yapılabilir. Bu özellikler, yönlendirme davranışları olarak bilinir ve her birinin belirli adları vardır: Ara, Kaç, Varış vb. Buradaki fikir, aracının konumunu ve mevcut hızını hedef ile karşılaştırmaya dayalı olarak, aracının hızına hızlandırma kuvvetlerinin uygulanabilmesidir. Amaca ulaşmak için farklı yöntemler kullanmak.
Her davranışın biraz farklı bir amacı vardır. Arama ve Varış, bir aracıyı bir hedefe taşımanın yollarıdır. Engellerden Kaçınma ve Ayırma, hedefe giden yolda engellerden kaçınmak için temsilcinin hareketini ayarlar. Hizalama ve Uyum, temsilcilerin birlikte hareket etmesini sağlar. Tüm faktörleri dikkate alan tek bir yol vektörü oluşturmak için herhangi bir sayıda farklı yönlendirme davranışı toplanabilir. Duvarlardan ve diğer etmenlerden uzak durmak için Varış, Ayrılma ve Engellerden Kaçınma davranışlarını kullanan bir etmen. Bu yaklaşım, gereksiz ayrıntılar olmadan açık yerlerde iyi çalışır.
Daha zor koşullarda, farklı davranışların eklenmesi daha kötü sonuç verir; örneğin, bir temsilci, Varış ve Engellerden Kaçınma arasındaki çatışma nedeniyle bir duvara sıkışıp kalabilir. Bu nedenle, tüm değerlerin eklenmesinden daha karmaşık olan seçenekleri göz önünde bulundurmanız gerekir. Bunun yolu şudur: Her davranışın sonuçlarını toplamak yerine, hareketi farklı yönlerde değerlendirebilir ve en iyi seçeneği seçebilirsiniz.
Ancak çıkmaz sokakların ve hangi yöne gideceğimize dair seçimlerin olduğu karmaşık bir ortamda, daha gelişmiş bir şeye ihtiyacımız olacak.
bir yol bulmak
Direksiyon davranışları, A noktasından B noktasına ulaşmanın engellerin etrafından yalnızca küçük sapmalarla düz bir yol olduğu açık bir alanda (futbol sahası veya arena) basit hareketler için mükemmeldir. Karmaşık rotalar için, dünyayı keşfetmenin ve onun içinde bir rotaya karar vermenin bir yolu olan yol bulmaya ihtiyacımız var.
En basiti, temsilcinin yanındaki her kareye bir ızgara uygulamak ve hangisinin hareket etmesine izin verildiğini değerlendirmektir. Bunlardan biri hedef ise, başlangıca ulaşana kadar her kareden bir öncekine giden rotayı takip edin. Bu rota. Aksi takdirde, hedefinizi bulana veya kareleriniz bitene kadar (olası bir rota olmadığı anlamına gelir) yakındaki diğer karelerle işlemi tekrarlayın. Bu, resmi olarak Genişlik Öncelikli Arama veya BFS (genişlik öncelikli arama algoritması) olarak bilinen şeydir. Her adımda her yöne bakar (dolayısıyla genişlik, "genişlik"). Arama alanı, istenen konuma ulaşana kadar hareket eden bir dalga cephesi gibidir; arama alanı, bitiş noktası dahil edilene kadar her adımda genişler ve ardından başlangıca kadar izlenebilmektedir.
Sonuç olarak, istediğiniz rotanın derlendiği karelerin bir listesini alacaksınız. Bu yol (dolayısıyla yol bulma) - aracının hedefi takip ederken ziyaret edeceği yerlerin listesi.
Dünyadaki her karenin konumunu bildiğimiz göz önüne alındığında, yol boyunca ilerlemek için yönlendirme davranışlarını kullanabiliriz - düğüm 1'den düğüm 2'ye, sonra düğüm 2'den düğüm 3'e vb. En basit seçenek, bir sonraki karenin merkezine doğru ilerlemektir, ancak daha da iyi bir seçenek, mevcut kare ile bir sonraki kare arasındaki kenarın ortasında durmaktır. Bu nedenle temsilci keskin dönüşlerde köşeleri kesebilecektir.
BFS algoritmasının dezavantajları da vardır; "doğru" yöndeki kareler kadar "yanlış" yöndeki kareleri de araştırır. A* (A yıldız) adı verilen daha karmaşık bir algoritmanın devreye girdiği yer burasıdır. Aynı şekilde çalışır, ancak komşu kareleri (sonra komşuların komşuları, sonra komşuların komşularının komşuları vb.) körü körüne incelemek yerine, düğümleri bir liste halinde toplar ve incelenen bir sonraki düğüm her zaman en iyi düğüm olacak şekilde sıralar. en kısa yola giden yol. Düğümler, iki şeyi hesaba katan bir buluşsal yönteme göre sıralanır: arzu edilen kareye giden varsayımsal bir rotanın "maliyeti" (her türlü seyahat maliyeti dahil) ve bu meydanın varış noktasından ne kadar uzakta olduğuna ilişkin bir tahmin (aramada aramayı saptırır). doğru yön).
Bu örnek, temsilcinin her seferinde bir kareyi araştırdığını ve her seferinde en umut verici olan bitişik kareyi seçtiğini göstermektedir. Ortaya çıkan yol BFS ile aynıdır ancak süreçte daha az kare dikkate alınmıştır; bu da oyun performansı üzerinde büyük bir etkiye sahiptir.
Izgarasız hareket
Ancak çoğu oyun bir ızgara üzerine yerleştirilmemiştir ve gerçekçilikten ödün vermeden bunu yapmak genellikle imkansızdır. Uzlaşmalara ihtiyaç var. Kareler ne büyüklükte olmalı? Çok büyük olduklarında küçük koridorları veya dönüşleri doğru bir şekilde temsil edemeyecekler, çok küçük olduklarında aranacak çok fazla kare olacak ve bu da sonuçta çok zaman alacak.
Anlaşılması gereken ilk şey, bir ağın bize bağlı düğümlerin bir grafiğini vermesidir. A* ve BFS algoritmaları aslında grafikler üzerinde çalışır ve ağımızı hiç umursamaz. Düğümleri oyun dünyasında herhangi bir yere koyabiliriz: Bağlantılı herhangi iki düğüm arasında, ayrıca başlangıç ve bitiş noktaları ile düğümlerden en az biri arasında bağlantı olduğu sürece, algoritma eskisi gibi çalışacaktır. Her düğüm dünyada herhangi bir sayıda varsayımsal yolun parçası olabilecek önemli bir konumu temsil ettiğinden, buna genellikle ara nokta sistemi denir.
Örnek 1: Her karede bir düğüm. Arama, aracının bulunduğu düğümden başlar ve istenilen karenin düğümünde sona erer.
Örnek 2: Daha küçük bir düğüm kümesi (yol noktaları). Arama, aracının karesinde başlar, gerekli sayıda düğümden geçer ve ardından hedefe doğru devam eder.
Bu tamamen esnek ve güçlü bir sistemdir. Ancak bir geçiş noktasının nereye ve nasıl yerleştirileceğine karar verirken biraz dikkatli olmak gerekir, aksi takdirde aracılar en yakın noktayı göremeyebilir ve yolu başlatamayabilir. Dünyanın geometrisine göre ara noktaları otomatik olarak yerleştirebilseydik daha kolay olurdu.
Gezinme ağının veya navmesh'in (gezinme ağı) göründüğü yer burasıdır. Bu genellikle, temsilcinin yürümesine izin verilen her yerde, dünyanın geometrisi üzerine yerleştirilmiş 2 boyutlu bir üçgen ağıdır. Ağdaki üçgenlerin her biri, grafikte bir düğüm haline gelir ve grafikte bitişik düğümler haline gelen en fazla üç bitişik üçgene sahiptir.
Bu resim Unity motorundan bir örnektir; dünyadaki geometriyi analiz etti ve bir navmesh oluşturdu (ekran görüntüsünde açık mavi). Bir navmesh'teki her çokgen, bir aracının durabileceği veya bir çokgenden diğer çokgene geçebileceği bir alandır. Bu örnekte çokgenler, bulundukları katlardan daha küçüktür; bu, aracının nominal konumunun ötesine uzanacak boyutunu hesaba katmak için yapılır.
Yine A* algoritmasını kullanarak bu ağ üzerinden bir rota arayabiliriz. Bu bize, tüm geometriyi hesaba katan ve gereksiz düğümler ve yol noktaları oluşturulmasını gerektirmeyen, dünyadaki neredeyse mükemmel bir rotayı verecektir.
Yol bulma, bir makalenin bir bölümünün yeterli olmayacağı kadar geniş bir konudur. Daha ayrıntılı incelemek istiyorsanız, bu yardımcı olacaktır .
planlama
Yol bulmayla bazen sadece bir yön seçip hareket etmenin yeterli olmadığını, bir rota seçip istediğimiz hedefe ulaşmak için birkaç dönüş yapmamız gerektiğini öğrendik. Bu fikri genelleyebiliriz: Bir hedefe ulaşmak sadece bir sonraki adım değildir, bazen ilkinin ne olması gerektiğini bulmak için birkaç adım ileriye bakmanız gereken bütün bir dizidir. Buna planlama denir. Yol bulma, planlamanın çeşitli uzantılarından biri olarak düşünülebilir. Duyu/Düşün/Eylem döngüsü açısından, burası Düşünme bölümünün gelecek için birden fazla Eylem bölümünü planladığı yerdir.
Magic: The Gathering masa oyunu örneğine bakalım. İlk olarak elimizde aşağıdaki kart seti ile gidiyoruz:
- Bataklık - 1 siyah mana (kara kartı) verir.
- Orman - 1 yeşil mana (arazi kartı) verir.
- Kaçak Sihirbazı - Çağırmak için 1 mavi mana gerektirir.
- Elf Mistik - Çağırmak için 1 yeşil mana gerektirir.
Kolaylık sağlamak için kalan üç kartı görmezden geliyoruz. Kurallara göre, bir oyuncunun tur başına 1 arazi kartı oynamasına izin verilir, bu karta "dokunarak" mana çıkarabilir ve ardından mana miktarına göre büyü yapabilir (bir yaratık çağırmak dahil). Bu durumda, insan oyuncu Orman oynamayı, 1 yeşil manaya dokunmayı ve ardından Elf Mistik'i çağırmayı bilir. Peki oyunun yapay zekası bunu nasıl anlayabilir?
Kolay planlama
Önemsiz yaklaşım, uygun eylem kalmayana kadar her eylemi sırayla denemektir. Yapay zeka, kartlara bakarak Swamp'ın neler oynayabileceğini görüyor. Ve onu oynuyor. Bu turda başka eylem kaldı mı? Elf Mistik veya Kaçak Sihirbazı'nı çağıramaz çünkü onları çağırmak için sırasıyla yeşil ve mavi manaya ihtiyaç duyarlar, Swamp ise yalnızca siyah mana sağlar. Ve artık Forest'ı oynayamayacak çünkü zaten Swamp'ı oynamıştı. Bu nedenle, oyun yapay zekası kurallara uydu ancak bunu kötü bir şekilde yaptı. Geliştirilebilir.
Planlama, oyunu istenen duruma getirecek eylemlerin bir listesini bulabilir. Bir yol üzerindeki her karenin komşuları olduğu gibi (yol bulmada), bir plandaki her eylemin de komşuları veya ardılları vardır. İstenilen duruma ulaşana kadar bu eylemleri ve sonraki eylemleri arayabiliriz.
Örneğimizde istenen sonuç “mümkünse bir yaratığı çağırmak”tır. Turun başında oyunun kurallarının izin verdiği yalnızca iki olası eylemi görüyoruz:
1. Swamp oynayın (sonuç: Swamp oyunda)
2. Orman oynayın (sonuç: Oyunda Orman)
Yapılan her eylem, yine oyunun kurallarına bağlı olarak başka eylemlere yol açabilir ve diğerlerini kapatabilir. Swamp oynadığımızı hayal edin - bu, bir sonraki adım olarak Swamp'ı kaldıracak (zaten oynadık) ve bu aynı zamanda Forest'ı da kaldıracak (çünkü kurallara göre tur başına bir arazi kartı oynayabilirsiniz). Bundan sonra yapay zeka bir sonraki adım olarak 1 siyah mana almayı ekliyor çünkü başka seçenek yok. Devam ederse ve Bataklığa Tap'ı seçerse 1 birim siyah mana alacak ve bununla hiçbir şey yapamayacak.
1. Swamp oynayın (sonuç: Swamp oyunda)
1.1 "Dokunma" Bataklığı (sonuç: Bataklığa "dokunuldu", +1 birim siyah mana)
Kullanılabilir işlem yok - END
2. Orman oynayın (sonuç: Oyunda Orman)
Eylem listesi kısaydı, çıkmaza girdik. Bir sonraki adım için işlemi tekrarlıyoruz. Orman oynuyoruz, "1 yeşil mana al" eylemini açıyoruz, bu da üçüncü eylemi açacak - Elf Mistik'i çağır.
1. Swamp oynayın (sonuç: Swamp oyunda)
1.1 "Dokunma" Bataklığı (sonuç: Bataklığa "dokunuldu", +1 birim siyah mana)
Kullanılabilir işlem yok - END
2. Orman oynayın (sonuç: Oyunda Orman)
2.1 Ormana "Dokun" (sonuç: Ormana "dokunulur", +1 birim yeşil mana)
2.1.1 Elf Mistik Çağır (sonuç: Elf Mistik oyunda, -1 yeşil mana)
Kullanılabilir işlem yok - END
Sonunda olası tüm eylemleri araştırdık ve bir yaratığı çağıran bir plan bulduk.
Bu çok basitleştirilmiş bir örnek. Bazı kriterleri karşılayan herhangi bir plan yerine mümkün olan en iyi planı seçmeniz tavsiye edilir. Potansiyel planları, bunların uygulanmasının sonucuna veya genel faydasına göre değerlendirmek genellikle mümkündür. Kara kartı oynadığınızda kendinize 1 puan, yaratık çağırdığınızda ise 3 puan kazanabilirsiniz. Swamp oynamak 1 puanlık bir plan olacaktır. Ve Orman oynamak → Ormana dokunun → Elf Mistikini çağırmak anında 4 puan verecektir.
Magic: The Gathering'de planlama bu şekilde çalışır, ancak aynı mantık diğer durumlarda da geçerlidir. Örneğin satrançta filin hareket etmesine yer açmak için piyonu hareket ettirmek. Veya XCOM'da bu şekilde güvenli bir şekilde çekim yapmak için bir duvarın arkasına saklanın. Genel olarak fikri anladınız.
Geliştirilmiş planlama
Bazen her olası seçeneğin dikkate alınmasını gerektirmeyecek kadar çok potansiyel eylem vardır. Magic: The Gathering ile örneğe dönecek olursak: Diyelim ki oyunda ve elinizde birkaç kara ve yaratık kartı var - olası hamle kombinasyonlarının sayısı düzinelerce olabilir. Sorunun birkaç çözümü var.
İlk yöntem geriye doğru zincirlemedir. Tüm kombinasyonları denemek yerine nihai sonuçla başlayıp doğrudan bir rota bulmaya çalışmak daha iyidir. Ağacın kökünden belirli bir yaprağa gitmek yerine, ters yönde, yapraktan köke doğru hareket ederiz. Bu yöntem daha kolay ve hızlıdır.
Düşmanın 1 sağlığı varsa "1 veya daha fazla hasar ver" planını bulabilirsiniz. Bunu başarmak için bir dizi koşulun karşılanması gerekir:
1. Hasar bir büyüden kaynaklanabilir - elinizde olmalıdır.
2. Büyü yapmak için manaya ihtiyacınız vardır.
3. Mana kazanmak için arazi kartı oynamanız gerekir.
4. Arazi kartını oynamak için elinizde olması gerekir.
Başka bir yol da en iyi öncelikli aramadır. Tüm yolları denemek yerine en uygun olanı seçiyoruz. Çoğu zaman bu yöntem, gereksiz arama maliyetleri olmadan en uygun planı verir. A*, en iyi ilk arama biçimidir; en umut verici rotaları baştan inceleyerek, diğer seçenekleri kontrol etmeye gerek kalmadan zaten en iyi yolu bulabilir.
İlginç ve giderek daha popüler hale gelen en iyi ilk arama seçeneği Monte Carlo Ağaç Aramadır. Algoritma, sonraki her eylemi seçerken hangi planların diğerlerinden daha iyi olduğunu tahmin etmek yerine, sona ulaşana kadar (plan zafer veya yenilgiyle sonuçlandığında) her adımda rastgele ardılları seçer. Nihai sonuç daha sonra önceki seçeneklerin ağırlığını artırmak veya azaltmak için kullanılır. Bu işlemi art arda birkaç kez tekrarlayan algoritma, durum değişse bile (düşman oyuncuya müdahale etmek için harekete geçse bile) bir sonraki en iyi hamlenin ne olduğuna dair iyi bir tahmin verir.
Oyunlarda planlamaya ilişkin hiçbir hikaye, Hedef Odaklı Eylem Planlaması veya GOAP (hedef odaklı eylem planlaması) olmadan tamamlanmış sayılmaz. Bu yaygın olarak kullanılan ve tartışılan bir yöntemdir ancak birkaç ayırt edici detay dışında aslında daha önce bahsettiğimiz geriye doğru zincirleme yöntemidir. Amaç "oyuncuyu yok etmek" olsaydı ve oyuncu siperin arkasındaysa, plan şu şekilde olabilir: bir el bombasıyla yok et → onu al → fırlat.
Genellikle her birinin kendi önceliği olan birkaç hedef vardır. En yüksek öncelikli hedef tamamlanamıyorsa (oyuncu görünür olmadığı için hiçbir eylem kombinasyonu "oyuncuyu öldürme" planı oluşturmaz), yapay zeka daha düşük öncelikli hedeflere geri döner.
Eğitim ve adaptasyon
Oyun yapay zekasının genellikle makine öğrenimini kullanmadığını çünkü aracıları gerçek zamanlı olarak yönetmeye uygun olmadığını söylemiştik. Ancak bu, bu bölgeden bir şey ödünç alamayacağınız anlamına gelmez. Bir şutörde kendisinden bir şeyler öğrenebileceğimiz bir rakip istiyoruz. Örneğin, haritadaki en iyi konumları öğrenin. Veya bir dövüş oyununda oyuncunun sık kullandığı kombo hareketlerini bloke ederek onu başkalarını kullanmaya motive eden bir rakip. Dolayısıyla makine öğrenimi bu gibi durumlarda oldukça faydalı olabilir.
İstatistik ve Olasılıklar
Karmaşık örneklere girmeden önce, birkaç basit ölçüm alıp bunları karar vermek için kullanarak ne kadar ileri gidebileceğimizi görelim. Örneğin, gerçek zamanlı strateji; bir oyuncunun oyunun ilk birkaç dakikasında saldırı başlatıp başlatamayacağını ve buna karşı nasıl bir savunma hazırlayacağımızı nasıl belirleriz? Gelecekteki tepkilerin ne olabileceğini anlamak için bir oyuncunun geçmiş deneyimlerini inceleyebiliriz. Başlangıç olarak, elimizde bu kadar ham veri yok ama toplayabiliriz; yapay zeka bir insana karşı oynadığı her seferde, ilk saldırının zamanını kaydedebilir. Birkaç seanstan sonra oyuncunun gelecekte atak yapması için gereken sürenin ortalamasını alacağız.
Ortalama değerlerde de bir sorun var: Eğer bir oyuncu 20 kez aceleye geldiyse ve 20 kez yavaş oynadıysa, o zaman gerekli değerler ortada bir yerde olacak ve bu bize yararlı bir şey vermeyecek. Çözümlerden biri giriş verilerini sınırlamaktır; son 20 parça dikkate alınabilir.
Benzer bir yaklaşım, oyuncunun geçmiş tercihlerinin gelecekte de aynı olacağını varsayarak belirli eylemlerin olasılığını tahmin ederken kullanılır. Bir oyuncu bize beş kez ateş topuyla, iki kez yıldırımla, bir kez de yakın dövüşle saldırıyorsa, onun ateş topunu tercih ettiği açıktır. Tahmin yürütelim ve farklı silahlar kullanma olasılığını görelim: ateş topu=%62,5, yıldırım=%25 ve yakın dövüş=%12,5. Oyun yapay zekamızın kendisini ateşten korumaya hazırlanması gerekiyor.
Bir başka ilginç yöntem de, büyük miktarlardaki girdi verilerini incelemek ve yapay zekanın istenen şekilde tepki vermesini sağlayacak şekilde durumu sınıflandırmak için Naive Bayes Sınıflandırıcısını kullanmaktır. Bayes sınıflandırıcıları en çok e-posta spam filtrelerindeki kullanımlarıyla tanınır. Burada kelimeleri inceliyorlar, bu kelimelerin daha önce göründükleri yerlerle (spam olsun ya da olmasın) karşılaştırıyorlar ve gelen e-postalar hakkında sonuçlar çıkarıyorlar. Aynı şeyi daha az girdiyle bile yapabiliriz. Yapay zekanın gördüğü tüm yararlı bilgilere (hangi düşman birimlerinin oluşturulduğu, hangi büyüleri kullandıkları veya hangi teknolojileri araştırdıkları gibi) ve nihai sonuca (savaş veya barış, acele veya savunma vb.) dayalı olarak. - İstenilen AI davranışını seçeceğiz.
Tüm bu eğitim yöntemleri yeterlidir ancak test verilerine göre kullanılması tavsiye edilir. Yapay zeka, oyun testçilerinizin kullandığı farklı stratejilere uyum sağlamayı öğrenecek. Yayınlandıktan sonra oyuncuya uyum sağlayan yapay zeka çok öngörülebilir hale gelebilir veya yenilmesi çok zor olabilir.
Değer bazlı adaptasyon
Oyun dünyamızın içeriği ve kuralları göz önüne alındığında, yalnızca girdi verilerini kullanmak yerine karar almayı etkileyen değerler kümesini değiştirebiliriz. Biz bunu yaparız:
- Yapay zekanın dünyanın durumu ve oyun sırasındaki önemli olaylar (yukarıdaki gibi) hakkında veri toplamasına izin verin.
- Bu verilere dayanarak birkaç önemli değeri değiştirelim.
- Kararlarımızı bu değerleri işlemeye veya değerlendirmeye dayalı olarak hayata geçiririz.
Örneğin, bir temsilcinin birinci şahıs nişancı haritasında seçebileceği birkaç oda vardır. Her odanın, ziyaretin ne kadar arzu edilir olduğunu belirleyen kendi değeri vardır. Yapay zeka, değere göre hangi odaya gidileceğini rastgele seçer. Ajan daha sonra hangi odada öldürüldüğünü hatırlar ve değerini azaltır (oraya dönme olasılığı). Bunun tersi durumda da benzer şekilde, eğer temsilci çok sayıda rakibi yok ederse odanın değeri artar.
Markov modeli
Toplanan verileri tahminlerde bulunmak için kullansaydık ne olurdu? Belirli bir süre boyunca oyuncuyu gördüğümüz her odayı hatırlarsak oyuncunun hangi odaya gidebileceğini tahmin etmiş oluruz. Oyuncunun odalar arasındaki hareketlerini (değerleri) takip edip kaydederek bunları tahmin edebiliriz.
Üç oda alalım: kırmızı, yeşil ve mavi. Ayrıca maç oturumunu izlerken kaydettiğimiz gözlemler:
Her odadaki gözlem sayısı neredeyse eşit; pusu kurmak için nerede iyi bir yer oluşturacağımızı hâlâ bilmiyoruz. İstatistik toplamak, harita boyunca eşit şekilde görünen oyuncuların yeniden doğması nedeniyle de karmaşıklaşıyor. Ancak haritada göründükten sonra girdikleri bir sonraki odaya ilişkin veriler zaten faydalıdır.
Yeşil odanın oyunculara uygun olduğu görülüyor - çoğu insan kırmızı odadan oraya taşınıyor ve bunların% 50'si orada kalıyor. Mavi oda ise tam tersine pek popüler değil; oraya neredeyse hiç kimse gitmiyor ve eğer giderlerse de uzun süre kalmıyorlar.
Ancak veriler bize daha önemli bir şey söylüyor; bir oyuncu mavi bir odadayken, onu gördüğümüz bir sonraki oda yeşil değil kırmızı olacak. Yeşil oda kırmızı odaya göre daha popüler olsa da oyuncunun mavi odada olması durumunda durum değişiyor. Bir sonraki durum (yani oyuncunun gideceği oda) önceki duruma (yani oyuncunun o anda bulunduğu odaya) bağlıdır. Bağımlılıkları araştırdığımız için, gözlemleri bağımsız olarak saymaktan daha doğru tahminlerde bulunacağız.
Geçmiş bir durumdan elde edilen verilere dayanarak gelecekteki bir durumu tahmin etmeye Markov modeli denir ve bu tür örneklere (odalarla birlikte) Markov zincirleri denir. Desenler ardışık durumlar arasındaki değişiklik olasılığını temsil ettiğinden, her geçişin etrafındaki olasılığa sahip FSM'ler olarak görsel olarak görüntülenirler. Daha önce, bir aracının içinde bulunduğu davranışsal durumu temsil etmek için FSM'yi kullanıyorduk ancak bu kavram, aracıyla ilişkili olsun ya da olmasın her durumu kapsar. Bu durumda eyaletler, aracının işgal ettiği odayı temsil eder:
Bu, durum değişikliklerinin göreceli olasılığını temsil etmenin basit bir yoludur ve yapay zekaya bir sonraki durumu tahmin etme yeteneği kazandırır. Birkaç adım sonrasını tahmin edebilirsiniz.
Eğer bir oyuncu yeşil odadaysa, bir dahaki gözlemlendiğinde orada kalma şansı %50'dir. Ama sonrasında bile hâlâ orada olma şansı nedir? Oyuncunun sadece iki gözlemden sonra yeşil odada kalma şansı değil, aynı zamanda ayrılıp geri dönme şansı da var. İşte yeni verileri dikkate alan yeni tablo:
Oyuncuyu iki gözlem sonrasında yeşil odada görme şansının %51 - %21 arasında kırmızı odadan olacağını, %5'inin aradaki mavi odayı ziyaret edeceğini ve %25'inin yeşil odada olduğunu gösterir. Oyuncunun %XNUMX'i yeşil odadan çıkmayacak.
Tablo yalnızca görsel bir araçtır; prosedür yalnızca her adımda olasılıkların çarpılmasını gerektirir. Bu, tek bir uyarıyla geleceğe bakabileceğiniz anlamına gelir: Bir odaya girme şansının tamamen mevcut odaya bağlı olduğunu varsayıyoruz. Buna Markov Özelliği denir; gelecekteki durum yalnızca şu ana bağlıdır. Ancak bu yüzde yüz doğru değil. Oyuncular kararlarını diğer faktörlere bağlı olarak değiştirebilirler: sağlık seviyesi veya cephane miktarı. Bu değerleri kaydetmediğimiz için tahminlerimizin doğruluğu daha az olacaktır.
N-Gram
Bir dövüş oyunu örneğine ve oyuncunun kombo hareketlerini tahmin etmeye ne dersiniz? Aynısı! Ancak tek bir durum veya olay yerine kombo saldırıyı oluşturan tüm dizileri inceleyeceğiz.
Bunu yapmanın bir yolu, her girişi (Kick, Punch veya Block gibi) bir arabellekte depolamak ve arabelleğin tamamını bir olay olarak yazmaktır. Yani oyuncu SuperDeathFist saldırısını kullanmak için tekrar tekrar Kick, Kick, Punch tuşlarına basıyor, AI sistemi tüm girdileri bir arabellekte saklıyor ve her adımda kullanılan son üçünü hatırlıyor.
(Kalın çizgiler, oyuncunun SuperDeathFist saldırısını başlattığı zamandır.)
Yapay zeka, oyuncu Kick'i ve ardından başka bir Kick'i seçtiğinde tüm seçenekleri görecek ve ardından bir sonraki girişin her zaman Punch olduğunu fark edecektir. Bu, temsilcinin SuperDeathFist'in kombo hareketini tahmin etmesine ve mümkünse engellemesine olanak tanıyacaktır.
Bu olay dizilerine N-gram adı verilir; burada N, depolanan öğelerin sayısıdır. Önceki örnekte bu 3 gramlık (trigram) bir değerdi; bunun anlamı şudur: ilk iki giriş üçüncüyü tahmin etmek için kullanılır. Buna göre 5 gramda ilk dört girdi beşinciyi tahmin eder ve bu şekilde devam eder.
Tasarımcının N gramın boyutunu dikkatli seçmesi gerekiyor. Daha küçük bir N daha az bellek gerektirir ancak aynı zamanda daha az geçmiş depolar. Örneğin, 2 gramlık (bigram) Kick, Kick veya Kick, Punch'ı kaydedecek ancak Kick, Kick, Punch'ı depolayamayacak, dolayısıyla yapay zeka SuperDeathFist kombinasyonuna yanıt vermeyecektir.
Öte yandan, daha büyük sayılar daha fazla bellek gerektirir ve çok daha fazla olası seçenek olacağından yapay zekanın eğitilmesi daha zor olacaktır. Tekme, Yumruk veya Blok şeklinde üç olası girişiniz olsaydı ve biz 10 gramlık bir giriş kullansaydık, bu yaklaşık 60 bin farklı seçenek olurdu.
Bigram modeli basit bir Markov zinciridir; her geçmiş durum/mevcut durum çifti bir bigramdır ve ilkine dayanarak ikinci durumu tahmin edebilirsiniz. 3 gram ve daha büyük N gramları aynı zamanda Markov zincirleri olarak da düşünülebilir; burada tüm öğeler (N gramındaki sonuncusu hariç) birlikte birinci durumu ve son öğe ikinci durumu oluşturur. Dövüş oyunu örneği, Tekme ve Tekme durumundan Tekme ve Yumruk durumuna geçiş şansını göstermektedir. Çoklu giriş geçmişi girişlerini tek bir birim olarak ele alarak, aslında giriş sırasını tüm durumun bir parçasına dönüştürüyoruz. Bu bize bir sonraki girdiyi tahmin etmek ve bir sonraki kombo hamlenin ne olacağını tahmin etmek için Markov zincirlerini kullanmamıza olanak tanıyan Markov özelliğini verir.
Sonuç
Yapay zekanın geliştirilmesinde en yaygın araç ve yaklaşımlardan bahsettik. Ayrıca kullanılmaları gereken ve özellikle yararlı oldukları durumlara da baktık.
Bu, oyun yapay zekasının temellerini anlamak için yeterli olmalıdır. Ancak elbette bunların hepsi yöntem değil. Daha az popüler olan ancak daha az etkili olmayanlar şunlardır:
- tepe tırmanma, gradyan iniş ve genetik algoritmaları içeren optimizasyon algoritmaları
- çekişmeli arama/zamanlama algoritmaları (minimax ve alfa-beta budama)
- sınıflandırma yöntemleri (algılayıcılar, sinir ağları ve destek vektör makineleri)
- Ajanların algısını ve hafızasını işlemeye yönelik sistemler
- Yapay zekaya mimari yaklaşımlar (hibrit sistemler, alt küme mimarileri ve yapay zeka sistemlerini üst üste yerleştirmenin diğer yolları)
- animasyon araçları (planlama ve hareket koordinasyonu)
- performans faktörleri (ayrıntı düzeyi, her zaman ve zaman dilimleme algoritmaları)
Alakalı kaynaklar:
1. GameDev.net'te Ve .
2. oyun yapay zekası geliştirmeyle ilgili çok çeşitli konularda birçok sunum ve makale içerir.
3. çoğu ücretsiz olarak sunulan GDC Yapay Zeka Zirvesi konularını içerir.
4. Web sitesinde de faydalı materyaller bulunabilir .
5. Yapay Zeka araştırmacısı ve oyun geliştiricisi Tommy Thompson, YouTube'da videolar hazırlıyor ticari oyunlarda yapay zekanın bir açıklaması ve çalışması ile.
Konuyla ilgili kitaplar:
1. Game AI Pro kitap serisi, belirli özelliklerin nasıl uygulanacağını veya belirli sorunların nasıl çözüleceğini açıklayan kısa makalelerden oluşan bir koleksiyondur.
2. AI Game Programming Wisdom serisi, Game AI Pro serisinin öncüsüdür. Daha eski yöntemleri içerir, ancak neredeyse tamamı bugün bile geçerlidir.
3. yapay zekanın genel alanını anlamak isteyen herkesin temel metinlerinden biridir. Bu, oyun geliştirmeyle ilgili bir kitap değil; yapay zekanın temellerini öğretiyor.
Kaynak: habr.com
