Parça parça yayınlamakta olduğum Yapay Zeka Oyunları ‘nın 3. makalesini sizlerle paylaşıyorum. Yapay zeka, yapay zeka oyun ve yapay zeka kodları ile ilgili makalelerini uzun olmaları nedeniyle sizlerle parça parça paylaşıyorum.
Yapay Zeka Oyunları Algoritma Seçme
Bu algoritmaların en basitine çayırda ateş denir. Başlangıç noktasının etrafında ardışık daireler inşa ederek çalışmaktadır. Algoritmanın her bir basamağı da daha geniş bir daire oluşturur. Ardışık daireler ve onlara ait elementlere daha büyük ve daha büyük indeksler atanır. Şekil 5’te görüldüğü gibi, indeks 4 olan daire hedef noktamızdan geçer.
Şekil 5. Basit bir yol bulma algoritması
Şimdi, zıt yönde ilerliyoruz ve her adımda, daha küçük bir indeksi olan daire üzerinde bulunan en yakın harita noktasına hareket ettiğimiz kuralına uyarak başlangıç noktasına ulaşıyoruz. Geri döndüğümüzde haritanın unsurları başlangıç noktası ile varış noktası arasındaki en kısa yolu oluşturuyor.
Bu algoritmanın çalışma şekli incelendiğinde, büyük bir avantajın yanı sıra (basitlik) ek olarak ciddi bir dezavantaja da sahip olduğu görülebilir. Örneğimizde şekil 5’te görüldüğü gibi algoritmanın bulduğu yol, en kötü senaryoda haritanın 81 alanının incelenmesine rağmen oyunun sadece beş öğesinden oluşuyor. 256×256 alanlardan oluşan bir haritanın olması durumunda, 65536 harita öğesini incelemek zorunda kalabilirsiniz!
A * algoritmasının birincil avantajı araştırılan alanların küçültülmesi, bilinçli olarak hedefi doğru araştırmaya yönlendirmektir. Kısaca dile getirmek gerekirse, haritadaki bir noktaya ulaşma maliyetini hesaplarken A* algoritması, hedefe ulaşmanın tahmini maliyetini gösteren bazı buluşsal yöntemler ekler. Bu işlev tipik olarak şu anda incelenen noktadan varış noktasına olan mesafedir.
Yapay Zeka Oyunları Algoritmanın Gereklilikleri
Optimum yol bulma sistemlerine birçok gereklilik sunulmaktadır. Optimal, mutlaka kısa anlamına gelmez. Algoritma arazinin türü gibi ek faktörleri hesaba katabilir. (Örneğin, bir RTS oyunundaki bir tank bataklığın etrafından dolaşmaktayken daha hızlı geçebilir), Dönme açısı sınırlamaları, bölgedeki düşmanların sayısı, ve oyuna bağlı olarak diğer birçok unsur bulunur. Algoritma haritanın dağılmaması gereken alanları önlemektedir. Örneğin dost birimlerle iletişim kurarak mesafeyi korur. En önemli şart, algoritmanın, her iki nokta arasında bir yol olduğu sürece her zaman en uygun yolu bulabilmesi gerektiğidir. Aşağıda, A* algoritmasını açıklayan kodlar gösterilmektedir.
PriorityQueue OpenList
List ClosedList
startNode.g = 0;
startNode.h = EstimateCostToEndNode(startNode)
startNode.f = startNode.g + startNode.h
startNode.parent = null
Open.Insert(startNode)
while(OpenList is not empty)
//obtain the topmost element from the priority queue
Node node = Open.GetNode()
if(node == endNode)
return TRUE
for(each neighbour _succ of the node node)
newG = node.g + CalcCostFromNodeToNode(_succ, node);
if(examined _succ is on OpenList or ClosedList
and the new cost is >= than the previous)
analyse another neighbour
else
_succ.parent = node
_succ.g = newG
_succ.h = EstimateCostToEndNode(_succ)
_succ.f = _succ.g + _succ.h
if(_succ is already on ClosedList)
remove _succ from ClosedList
if(_succ isn’t on OpenList yet)
add _succ to OpenList
ClosedList.Insert(node)
return FALSE
Yapay Zeka Oyunları Optimizasyon
Doğrudan uygulanan algoritma, yapılardaki öncelik sırasından kaynaklı olarak (OpenList) ve (CloseList)’ten ne kadar süre alabileceğinin bir sonucu olarak etkisiz hale gelebilir. Bu kusurların etrafında çalışan çoklu programlama yöntemleri mevcuttur. Optimizasyon sorunlarına iki yoldan yaklaşılabilir:
1- Arama algoritmasının kendisini en iyi duruma getirme,
2- Veri yapılarını optimize etme.
Birinci durumda, genelde bütün dünyayı (haritayı) bölgelere bölme ve algoritmayı iki bölüme ayırma yöntemi uygulanır. Önce, hangi bölgelere geçeceğimizi kontrol ederek yolu araştırırız. Daha sonra her bölge için, giriş noktasından çıkışa doğru hareket ederiz. Her bölgede, bulunduğumuz bölge için A * algoritmasını kullanarak en uygun yolu buluyoruz. Bu şekilde, arama alanını önemli ölçüde sınırlıyoruz, böylece hesaplamalar için gerekli olan kaynakların miktarını azaltmış oluyoruz.
Aslında bu yöntem, bir insanın hedefe giden yolu nasıl bulduğuna dayanıyor. Büyük bir şehrin başka bir ucuna giderken, yürüteç tüm rotayı eşit hassasiyetle planlamıyor. Bunun yerine, bilinen iki oryantasyon noktası arasında dolaşır ve her iki nokta arasında yürümeye hazır caddeye kadar yol planlamaktadır
Yapay Zeka Oyunları başka bir optimizasyon faktörü sezgisel fonksiyonların ve parametrelerin uygun bir şekilde seçilmesidir. Çünkü arama bölgesi oyun haritasında ne kadar yayılır karar verir.
Yapay Zeka ve Yapay Zeka Oyunları ile ilgili ilerleyen zamanlarda daha ayrıntılı yazılarımızı sizlerle paylaşmaya devam edeceğim.
Daha önceki Yapay Zeka Oyunları – 2. bölümü için tıklayın.
Yapay Zeka ve Yapay Zeka Oyunları ile ilgili ilerleyen zamanlarda daha ayrıntılı yazılarımızı sizlerle paylaşmaya devam edeceğim.
Daha önceki Yapay Zeka Oyunları – 2. bölümü için tıklayın.
