ROLLING STONE
Sokoban oyununu çözmek amacıyla yazılmış bir program olan Rolling Stone, 90 test oyununda denenmiş ve 12'sinde çözüme ulaşabilmiştir. Kuralları çok basit olan bu "tek-ajan" (single-agent) oyun, türdeşlerinden bir çok yönden farklıdır. Bu programın denenmesi sonucunda varılan kanı, oyunun bazı bölümlerinin sadece tek-ajan oyun taktikleriyle çözülmesinin imkansız olduğudur.
Amaç, taşları hedefe götürürken en az sayıda hareket yapmaktır. Ancak bu da taşların ve adamın en az sayıda hareketi diye ikiye ayrılır. Rolling Stone, taşların en az sayıda hareket etmesi esasına göre yazılmıştır.
Taşların yerleri koordinatlarla belirlenir. Bu arada adamın yerinin koordinatları da başka bir yerde tutulur. Çünkü oyunda sadece taşların yeri değil, adamın yeri de önemlidir.
ALT SINIR
Bir tahmin fonksiyonuyla alt sınır belirleyen bu program, henüz yeterince iyi olmadığı için bazı bölümlerde, en kısa çözümden çok daha büyük sayılar vermektedir. (Mesela bir bölümde tahmin fonksiyonu 96 veriyorken, en iyi insan çözümü 374'tür.)
Tek-Ajan oyunlarda genelde bütün durumlardan çözüme gidilebilir. Fakat bu oyunda durum farklıdır. Bazı durumlarda taş(lar) kilitlenir ve hareket edemez duruma gelir. Eğer kilitlenme olursa, oyun bu durumdan çözüme ulaşamaz. Hem bu durumu engellemek için, hem de arama ağacımızı küçültmek için bu gibi kilitlenme pozisyonları program tarafından ihtimal dışı bırakılmıştır.
Bazen de program insan çözümünü tahmin ettiği halde, hareketlerin hepsini çıkaramamaktadır.
TAHMİN FONKSİYONU (HEURISTIC)
Tahmin fonksiyonu (alt sınır) hesabında şunlar dikkate alınır:
- Sadece hedefe olan mesafe hesaplanır,
- Birbirinin yolunu tıkayan taşlar olduğunda, yapılması gereken fazla hareketler hesaplanır,
- Taşı odadan çıkarıp geri odaya sokmak gerektiğinde, bunun için fazladan gerekli hareket sayısı da hesaplanır.
Üst sınırlar ise insanların rekorlarıyla belirlenir.
POZİSYON TABLOSU
Daha önceki pozisyonlar bu tablo aracılığıyla hafızada tutulur, böylece daha sonra o pozisyonlara bir daha gelinmesi engellenir. Unutmamamız gereken şey, hafızada tutulanın sadece taşların koordinatları olduğudur. Bu yüzden kontrol yapılırken adamın yeri de ayrıca kontrol edilmektedir.
KİLİTLENME
Bu programda, her hareketten önce kilitlenme olup olmayacağı kontrol edilir, böylece yanlış bir hamle yapılarak oyunun kilitlenmesi engellenmiş olur.
Kontrol, hareketin olduğu yerde (5x4)'lük bir alan içinde yapılır. Daha önceden; 5x4 lük bir karede, taşlar, duvarlar ve adamın dahil olduğu BÜTÜN kilitlenme pozisyonları belirlenerek bir dosyaya konmuştur (Bu dosya yaklaşık 4.6 MB'tır). Her hareketten önce bu dosya baştan sona taranarak kilitlenme engellenmiş olur.
5x4 yetersiz, küçük bir alan gibi gözükebilir. Fakat bütün oyun alanını kapsayan tabloların tutulması çok büyük hafıza isteyecek, ayrıca çok zaman alacaktır. Kilitlenmelerin de hep hareketin yapıldığı civarda olduğunu da düşünürsek, 5x4 yeterli bir alandır.
Bu konuda çok önemli bir nokta ise hedef bölgelerle ilgilidir (taşların götürülmesinin istendiği yerler). Program kilitlenme kontrolünü hedef bölgelerde yapmaz. Çünkü hedef bölgeye getirilen bir taşın bir daha oynatılmaya ihtiyacı olmayabilir. Bu bölgede yapılacak kilitlenme kontrolü gereksiz olmakla kalmayıp oyunun sonuca gitmesini de engelleyebilir.
HAREKET SIRASI
Bazı bölümlerde çözüm kolay ve çok sayıdadır. Bu durumda en az sayıda hareket edilen çözümü seçmek gerekir. Bu amaçla Rolling Stone programı şu tekniği kullanmaktadır: "Eğer mümkünse, hareketi bir önceki hareketle aynı yönde yap."
Bu şekilde adamın hareket sayısının azaltılması amaçlanmıştır.
MAKROLAR
Program iki tane makro kullanmaktadır: Tünel ve Hedef makroları.
Tünel Makrosu: Sadece tek taşın geçebileceği tek yönlü tünellerde uygulanır. Taş tünele bir kere girmişse, çıkana kadar başka hareketlere bakılmaz. Böylece gereksiz hesaplamalardan kurtulunmuş olur.
Hedef Makrosu: Hedef alanına yaklaşıldığında çalıştırılır. Bu makro, hedef yerlerinin öncelik sırasına göre oluşturulmuştur. Önceliklerin belirlenmesi ve taşın direk olarak istenilen yere konması; bir taşın hedefe yerleştirilirken başka bir hedef noktasını tıkamasını engeller.
Ayrıca bu iki makro bazı bölümlerde birleştirilmiş ve tek hareket haline getirilmiştir. Böylece makroya başlayan taş, başka hiçbir hareket hesaplanmaksızın hedef noktalarından birine yerleştirilir.
HEDEF İÇİN DÜZENLEMELER
Program, hedeflerin aynı odada olduğunu varsayarak bir öncelik sırası oluşturmaktadır. Böylece hedef bölgesindeki kilitlenmeler de engellenmiş olur.
DENEYLERİN SONUÇLARI
- Makrolar büyük bir kolaylık sağlamaktadır. Bazı bölümlerde makrolar sayesinde, arama ağacımızın uzunluğu çözümden daha kısa olmaktadır. Çünkü ağaçtaki bazı dallar birden çok hareketi temsil etmektedir (Bir bölümde 355 hareketlik bir çözüm, makrolar sayesinde sadece 185. derinlikte bulunmuştur).
- Daha önceki pozisyonların hafızada tutulması Sokoban'a diğer oyunlara nazaran daha çok faydalı olmaktadır. Mesela bir problemde pozisyon tablosunun tutulmaması arama ağacını 5650 kat arttırmaktadır !
PROGRAMDA GELİŞTİRİLMESİ DÜŞÜNÜLEN YÖNLER
- Kilitlenmeler: Şu anda kullanılan ve 5x4 lük bir alanda çalışan kontrol sistemi yeterli olmakla beraber, eğer işlem gücü de yeterliyse 5x5 lik bir alanda da hesaplama yapılabilir. Daha fazlası gereksiz olur. Çünkü bu alan içerisinde bütün kilitlenme ihtimalleri bulunmaktadır.
- Sokoban'da odalar rastgele oluşturulmaz, belli bir stratejiyle kurulurlar. Daha büyük kilitlenmeleri tespit edebilmek için, kilitlenme tablolarını her oda için ayrı olacak şekilde yapabiliriz. Bu, kilitlenme problemini tam olarak çözemese de programın şu anda bulamadığı bazı kilitlenmeleri bulacağı düşünülüyor.
- Hedef Makroları: Programdaki hedef makroları, hedeflerin aynı odada bulunduğunu ve bu odaya tek giriş olduğunu varsaydığı için bazı bölümlerde işe yaramamaktadır. Bunun içinse yeni bir yöntem düşünülmüş. Hedef makroları belli bir yarıçapta çalıştırılacak, yani taşlar hedeflerin etki alanına girdiklerinde makroya uyacaklar. Bu arada hedef yerlerinin öncelikleri çok dikkatli belirlenmelidir. Programın yazarları, hedef önceliklerini doğru belirleyecek bir hedef makrosu yazılması halinde şu anda çözebildikleri bölüm sayısının, 2 katından daha fazlasına çıkabileceğine inanıyorlar. Bazı bölümlerde ise hedef makroları çözüme gitmeyi engellemektedir. Bu yüzden bu makroların daha güzel düzenlenmesi gerekmektedir.
- Uygulanması düşünülen bir fikir de, oyundaki kahramanımızın önce bir odayı düzenlemesi daha sonra diğer bölgelere/odalara geçmesidir. Böylece yerel tarama yapılacağı için arama ağacı küçülecektir.
- "Bölümlenmiş Arama" (partition search) tekniği de programa faydalı olabilir. Hafızada kilitlenme pozisyonunun tutulması için bütün taşların yerine değil de, sadece kilitlenmenin olduğu bölgedeki taşların yerlerine bakılır.
- Bir taşın yolunun başka bir taş tarafından tıkanması durumunda, taşlardan biri hareket etmeden diğeri de edemeyeceğinden bu taş, yolu açılana kadar arama ağacına katılmaz.
- Tahminler iyi bir planlamanın, 90 bölümün hepsini çözmeye yeteceğini göstermektedir. Her ne kadar program (şu anki haliyle) 50. bölümü "kaba-kuvvet" (brute-force) arama yöntemiyle çözse de, hedefe ulaşmaya çalışan planlı bir arama yönteminin gerekliliği kesindir.
- Araştırılan bir konu da programın canlı olarak makro öğrenmesidir. Taşların hedefe giden yollarının aynı olması durumunda programın bu yolu bir makro olarak belirlemesi ve her taş için arama masrafından kurtulunmuş olması gibi... İstenen, programın bunu oyun sırasında kendi öğrenmesidir.
- Probleme bir başka açıyla bakılacak olursa; oyun bütün taşlar hedeflerinde olarak başlar ve biz bu sefer taşları sadece ÇEKEREK olmaları gereken yere getirmeye çalışırız. Böylece kilitlenme pozisyonlarının çoğu da ihtimal dışı kalmaktadır. Bu da programa eklenilmesi düşünülen diğer bir yöntem.
DİĞER PROGRAMLAR
Sokoban'ı çözme amaçlı programlardan bir tanesi de Andrew Myers'ın programıdır. 90 problemden 9 tanesini çözebilmiştir (Rolling Stone’dan sonra en iyi sonuç veren program). Programda “genişlik öncelikli (breadth-first) A*” arama tekniği kullanılmıştır.Program hem adamın hem de taşların hereket sayısını en aza indirmeye çalışmaktadır.
Hedef noktalarının aynı odada olması durumunda işe yarayan şu yöntem kullanılmıştır:
- Taşın en yakın hedef noktasına olan uzaklığı hesaplanıyor.
- En yakın (hedef olmayan) yerden bütün hedeflere gidilmesi için gereken (adamın ve taşın) hareket sayıları hesaplanıyor.
Tahmin mekanizması bu iki değere göre bir çözüm hesaplıyor ve hangi taşın itilmesi gerektiğine karar veriyor. Bu daha önceden hazırlanan 700 KB'lık bir dosya sayesinde çabucak yapılabiliyor.
Program taşların aynı çizgide dizilerek birbirlerinin yolunu tıkaması durumunu göz önüne almamış. Arama fonksiyonu kesin bir arama yöntemi kullanmamış çünkü bu bazen çözümün gözden kaçmasına yol açıyor.
Kilitlenme tabloları 3x3lük alanlar için otomatik olarak oluşturuluyor. Hedef bölgelerdeki kilitlenmeler de ayrıca bir yerde tutuluyor. Elle yazılan tablolar sayesinde bu problem kolayca çözülmekte, fakat program bu tabloları kendi kendine oluşturamıyor.
SONUÇ
Sokoban, diğer tek-ajan oyunlarından oldukça farklıdır. Bu yüzden sadece tek-ajan çözüm arama teknileri yetersiz kalmaktadır. Fakat programın yapımcıları diğer tekniklere geçmeden önce bu tekniği gidebileceği yere kadar götürmek istedikleri için, şimdilik başka teknikler kullanmamaya kararlılar.
Kaynak
KILITLENME(DEADLOCK) DURUMLARINDA SINGLE AGENT SEARCH(A*)
Cogu uygulama "Eger cozumu olan bir durumdan basladiysan, hic bir zaman cozumu olmayan bir duruma girme". Ozelligine sahip olmak icin A* tekniklerini kullanmaya calisir.Cozumsuz yollarin (mesela Sokoban oyununda oldugu gibi) programin basarisiz veya basariliysa bile verimsiz olmasinda onemli bir payi vardir. Bu kagitta programin calismasiyla birlikte ogrenen (realtime’da ogrenen) patern arama (pattern search) anlatilacak.Patern arama cozumsuz yollara cikmanin minumum kurallarini arastirarak soyler ve boylece bu bilgiler problemin gercek cozumunu ararken cozumu olmayan bir yol uzerinden aramaya devam etmememizi ve dolayisiyla gereksiz yere zaman harcamimizi bastan onler .Bu teknik sayesinde Sokoban oyununun verimliligi 15 kat artirilabilmistir.
A* 'in verimliligi artirmasi genel olarak sahip olduklari su ozelliklerden kaynaklanir:
- Verimli ve ucuz taban katsayisi hesaplayicisi
- Arama agacina patern aramadan dolayi eklenen dallanma payinin kucuk olmasi
- Azaltilmis ve cok daha mantikli cozum uzunluklari.
Bu kagitta Sokoban oyunu uzerinde A* ‘in nasil cozumu olmayan yollara girmeyi engellemeyi basardigini inceleyecegiz.Sokoban kurallari bsit olan,unlu bir oyundur.Kisaca odalar, yollar,taslar ve bu taslarin tasinmasi gereken hedef bolgeden olusur.Taslari hedef bolgeye, sadece itme yetenegine sahip olan bir hamal tasir. Bir tasi eski yerine cekerek getiremiyecegimizden, bir hareket problemimizi cozumu olan bir durumdan, cozumsuz bir duruma sokabilir.
Sokoban oyununu patern arama olmadan cozmeye calisan teknikler yetersiz kalmistir.Bu tekniklerle 90 test datasindan sadece 20’si cozulebilmistir. Patern aramanin onemi, bu cozulemeyen 70 test datasinda basarisizligin onemli bir nedeninin cozumsuz yollar (deadlock) olmasindan gelmektedir.Eger bu kilitlenme noktalarini arastirsak cok buyuk bir verimlilik elde edebiliriz.
Bunun icin cozumu aramak icin harcadigimiz eforun bir kismini, cozumun kilitlenme noktalarini bulmak icin, programla es zamanli olarak ogrenen bir algoritmayi calistirmak icin kullanabiliriz. Bu arama agaciyla, edinilen bilgi arasinda bir pazarliktir. Ama bu pazarlik Sokoban oyununda bizim lehimizedir.Basarisiz bir patern arama ortalama agaca 50 dal eklerken, basarili bir patern arama ise ortalama 1000 dallik bir azaltma meydana getirir.Yani bu riskinin yaninda cok rahatlikla oynanmasi gereken bir kumardir.
PATERN ARAMA
Taslarin durumun cozumsuz yol olmadigini bulmak ve kanitlamk icin patern arama algoritmasinin Sokobanin labirenti uzerine asil programdan ayri olarak arama yapmasi gerekir.bir patern aramanin sonucu ,eger cozumsuz bir yola cikan patern bulmayi basardiysa, minimal boyuta getirilerek, daha sonra asil arama isleminde kullanilmak uzere kaydedilir.Program kilit noktalarina girmeyi, kaydedilen bu bilgileri kullanarak oneler.
Tanim olarak oyunun kilitlenmesi butun taslarin hedef bolgeye ulasamadigi konfigurasyondur.Eger bir tasi A'dan B'ye hareket ettirince oyun cozumsuz duruma geciyorsa,B'deki tas bu kilitlenen paternin bir parcasi demektir.Bu patern arama algoritmasinin ilk verisidir ve bu tasi kullanarak minumum bir patern bulmasi gerekir. Bunu bulmak icin asil labirentten farkli olarak, bu labirentin aynisi olan bir test labirenti olusturur ve bu labirentte taslarin alt kumesinden olusan taslarla calisir.
Test labirentine ilk once aradigimiz paternin parcasi oldugu kesin olan B’deki tasi yerine koyarak baslariz. Bu tek tastan olusan test labirentini IDA*'in patern arama icin daha verimli olmasi icin ozellestirilmis hali olan PIDA* ile cozmeye calisiriz. PIDA* bize ya bir cozumu doner ya da cozum olmadigini. PIDA* eger bir cozum donmusse, cozumde kullanilan taslarin ve hamalin tasi hedef bolgeye tasimak icin kullandigi yolun uzerindeki taslarla ilgileniriz.Hamalin yolu ve taslarin yolu bize orjinal labirentten hangi tasi test labiretine koyacagimiz soyler.Orjinal labirentte olan ve PIDA* 'in bize dondugu cozumle cakisan taslar, bu cozumu gecersiz kilar.Bu yuzden tas yolu uzerinde olan ve B'ye en yakin olan tasi test labirentine ekleriz ve PIDA* 'in bu yeni test labirenti icin bir cozum bulmasi icin tekrar cagiririz.Eger boyle bir tas yoksa bu sefer hamalin yolu uzerinde olan ve A'ya en yakin olan tasi test labiretine ekleyip islemi tekraralariz.Eger boyle bir tas da yoksa PIDA* A'dan B'ye olan bu tas harekitinin cozumu olan bir yol oldgunu ispatlamis olur (Bu cozumun gercek cozum olmadigini sadece hareket ettirdigimiz taslarla ilgili bir arastirmanin sonucu oldugunu hatirlatirim).
Eger PIDA* herhangibir cozum bulamamissa, A’dan B’ye hareket cozumu olmayan bir hareket demektir ve bu patern uzerinde (daha sonra kullanirken maksimum verimi elde edebilmek icin) inceleme yapmamiz gerekir.Ilk once varligi ve yoklugu, hareketin cozulebilirligi uzerinde hic bir etksi olmayan taslar ayiklanir.Cozumsuz konfigurasyon uzerinde ne kadar az tas bulunursa, o kadar cok pozisyonla eslestirebilecegimizi unutmayalim.Minumum konfigurasyonu bulmak icin soyle bir ozelligin saglanmasini saglamamiz gerekiyor: "Minumum konfigurasyon, cikarildiginda da cozumsuzlugun devam ettigi taslardan olusmaz". Yani minumum konfigurasyonun icindeki herhangibir tasi cikarirsak kesinlikle cozumu olan bir patern bulmus oluruz.
Minimize etme islemi icin N tane tastan olusan patern alinir ve olasi butun N-1 taneden olusan paternleri inceleyerek, yukaridaki ozelligin var olup olmadigini arastirir,Gereken taslar paternden cikarilarak isleme devam edilir.
Kaynak
SOKOBAN: COZULEMEZ DURUMDA STANDARD TEK-AJANLI ARAMA TEKNIKLERINI DEGERLENDIRME
OZET
Tek ajanli arama ,cesitli uygulamalari cozumlemede kullanilan guclu bir aracdir. Akademik calismalarin cogu baslanabilir bir durumdan baslayarak baslanamaz durumlara ulasilamayan tek ajanli arama tekniklerini arastirmistir. Bu raporda cozumsuz durumlar iceren aramalar uzerinde durulmustur.
GIRIS
Gecmiste tek ajanli arama teknigi(A*) cok kullanilmistir. A* iceren akademik calismalarin cogu(Rubik kubu ve kayan tas bulmacasi) su acilardan kolaydi: basit ve etkili alt sinir tahmin edicileri,az dallanma ve kontrol edilir derinlik. Bu oyunlarda cozulebilir bir durumdan basladiginiz zaman bu ozelligi surekli koruyabilirsiniz. Boylece gercek zamanli bir algoritma kurularak cozum garanti edilebilir. Arama uygulamalarinda geri donulebilirlik ve dolayisi ile cozumsuz bir duruma ulasmayi engelleme onemli bir unsurdur. Kucuk bir hamle buyuk bir soruna yol acabilir. Bununla nasil basa cikilacagi zor bir sorundur. Sokoban taslari ittirerek hedeflere goturmeye amaclayan populer tek kisilik bir oyundur. Geri cekme hamlesi olmadigi icin cozumsuz bir duruma ulasilabilir ve bir durumun cozumsuz oldugunu yuzlerce derinlikte bir arama ile ancak cozebilecegimiz bir tahta kolayca yapilabilir. Bu yuzden cozumsuz durumlari saptamasi cok zordur. Sokoban bir cok nedenden dolayi zor bir arama uygulamasidir:
- cok kompleks alt sinir tahmincisi,
- dallanma cok genis ve degisken,
- cozum arama agacinda cok derinde olabilir,
- cozumsuz durumlara ulasilabilir.
Cozumsuz durumlar nedeni ile sokoban icin verimli cozumler uretmek cok zordur. Sokoban problemlerini cozmek icin IDA* tabanli bir program olusturduk. Standart A*'a ek olarak iyi bir alt sinir tahmin edici,cozumsuz durum tablolari,duragan bir heuristic ve verimliligi saglayan macrolar yaptik. Buna ragmen 90 unlu problemin 16sini cozduk. Tekniklerimiz gelistirilebilir oldugunu dusunuyoruz,boylece daha fazla soru cozulebilir. Ayrica standart A* kullanarak cozumlenemeyecek sokoban problemleri oldugunu dusunuyoruz.
SOKOBAN
Sokoban populer tek kisilik bir oyundur. Japonya'da dogmustur.Amac, 20*20 veya daha az bir alanda taslari cekerek, engelleri asarak hedefe ulastirmaktir. Bunu en az hamlede yapmak daha zordur. Bir hamle yalnizca adamin tasi ittirebilecegi bir yer oldugu zaman gecerlidir. Sokobanin en verimli cozumunu iki sekilde tanimlayabiliriz:adamin hamle sayisi,tasin hamle sayisi. Burada tas hamle sayisi incelenmistir. Sokoban NP-hard katagorisindedir. [DZ95] oyunun hareket planlama oyunu oldugunu gostermis ve tarihteki benzer oyunlari incelemistir. Sokobani, maddeleri yerinden alip,engelleri asarak hedefe goturmesi gereken bir robot gibi dusunebiliriz. Bu oyun bu yuzden cok iyi bir yapay zeka uygulamasidir.
SOKOBAN NEDEN ILGINCTIR?
Sokoban siradan bir A* arama teknigi cozumlu soru degildir. Onu zor yapan ozellikleri ise:
Alt Sinir:
Sokobanin cozumu icin isabetli bir alt sinir uretmek zordur.Sinir ne kadar isabetli ise cozum o kadar verimlidir.
Cozumsuz durum:
Sokobanda diger A* uygulamalarindakinin aksine geri donulemez hamleler vardir. Dolayisi ile tek bir hamle alt siniri sonsuz yapabilir.Eger alt sinir fonksiyonu bunu incelemezse cozumu olmayan alt dallari incelemek gereksiz yere caba harcatir.Cok basit bir ornek bir tasin koseye girmesi. Gereksiz incelemeleri engellemek icin bu durumlari saptamamiz lazim.
Arama
Uzayinin Genisligi: Sokobanda cok dallanmadan dolayi arama uzayi cok genistir. 6dan 34e kadar tasli standart sokoban problemlerinde cozum derinligi 100 ile 650 arasinda degismektedir.Problem 48de derinlik hesaplayan programimiz 200 hamlede cozum oldugunu bulmus fakat arama uzayinin genisligi nedeni ile cozumu bulamamistir.SOKOBANI COZMEYE DOGRU
Standart arama tekniklerinin 90 soruyu cozmede yetersiz oldugunu dusundugumuz halde IDA* teknolojisini ilerletmeyi dusunduk.
Alt Sinir:
Butun taslari hedefe goturmek icin gereken minumum hamlelerin toplamini aldik. Bir tas birden cok yere gidebilecegine gore bunlardan en kisa olanini aliyoruz. n dal ve m kose oldugunu dusunursek kompleksitesi O(n^3*log n/log(2+n/4)). Bunu her hamlede hesaplamamiz gerekli fakat her hamlede yalniz bir tasi hedefinden bir birim yer degistirdigimize gore, her hamle icin negatif deger deviri belirleyerek bu yukden kurtulabiliriz. Alt sinir belirlemenin bir avantaji cozum uzunlugunun tek mi cift mi oldugunu dogru verir. Boylece artirmalarimizi ikiser yapariz. Ayrica alt sinir belirlemede yardimci faktorler de vardir. Birbirlerin hedef yolu uzerinde bitisik iki tas varsa her seferinde alt siniri iki artirmamiz gerekir cunku bir tasi ittirip geri cekmeliyiz. Ikinci durum, bazen bir tasin odanin disina itilip tekrar cekilmesi gerekebilir. Bu durum adamin tasa gore konumunu degistirmesi gerektiginde ortaya cikar,mesela sagindayken soluna gecmesi gerekiyorsa. Alt sinir bu uc faktorun toplami alinarak belirlenmistir.
Yer Degistirme Tablosu:
Ayni yerlere tekrar gitmemek icin buyuk bir yer degistirme tablosu tutarak gidilen kareler bu tabloya islenir. Asil onemli olan taslarin pozisyonu olduguna gore, adamin taslar sabitken gidebilecegi her yer esit olarak algilanmali ve bu dallar da incelenmemelidir.
Cozumsuz Durum Tablosu:
Bir veri tabaninda sinirli bir alanda olasi cozumsuz durumlar agac seklinde tutulmaktadir.Bizim deneyimlerimizle 5*4 luk dikdortgensel alanlar icin cozumsuz durum tablolari olusturduk(yaklasik olarak 22milyon girdiden olusuyor).Cozumsuz durumlar bu alanin disinda kalan durumlar icin gecerli oldu fakat daha buyuk tablolar olusturmak cok pratik degil. Hedef bolgesinde cozumsuz durumlar incelenmemeli cunku,hedef karelerinde girdigi yerde kalabilir.
Makro Hareketler:
Tunel Makro: Bir tas eger tunelin girisinde ise ve adam bunu yalnizca o taraftan ittirebiliyorsa o zaman tunelin sonuna kadar tasi ittirmesi gerekir ve bunu tek bir makro hareket gibi algilayabiliriz. Hedef Makro: Eger tas hedef odasina girmisse direk olarak onceligi en fazla olan bos hedef karesine ittirilir. Yani bu durumu hedef makro hareketi ile halledebiliriz.
Hamle Sirasi:
Hamle sirasi cok onemlidir. Kac hamlede bitecegini bilsen bile,bu hamleleri dogru sirada yapmak gereklidir. Duragan dedigimiz bir sema kullandik. Buna gore, eger bir tasin surekli ayni yonde hareket etmesi bir onceki hamlenin duraganligini(inertia) koruyorsa gidebildigin kadar git.
DENEYSEL SONUCLAR
20 milyon dal taramasi sonucunda programimiz 16 tane soruyu cozebilmistir. Bu sokobanin ne kadar zor bir oyun oldugunu gosterir. Makro hareketler nedeni ile arama agacinin derinligi cozum uzunlugundan daha kisa olabiliyor. Yer degistirme tablosu arama agacini 2000 kat kadar azaltabiliyor. Alt sinir tahmincisi arama agacini yaklasik 84000 kat azaltabiliyor.
SU ANKI PROGRAMI GELISTIRME
- Daha buyuk cozumsuz durumlar bulmak
- Tahtanin tamaminda degil de bolgesel olarak hamleleri inceleme
- On arama analizleri yapma
- Tekrarlanan seyleri dinamik ogrenme ve bunlara makro gibi davranma
- Tasi geri dogru cekme
SONUC
Sokoban hem insanlar hem makinalar icin zor bir oyun. Geleneksel A* arama teknikleri yetersiz. Cozumsuz durumlar kompleksiteyi cok artiriyor.
Kaynak
Kaynak
SOKOBAN: İLGİLİ KESİTLERLE ARAMAYI GELİŞTİRME
GENEL
İnsanlar ilgili hareketle ilgisiz hareketi birbirinden ayırabildikleri için büyük bir arama yüzeyinde çok kompleks problemleri çözerek ilerleyebiliyorlar. Bu makalede, hareket etkisine dayalı dallanma tekniği ile single-agent aramayı sunacağız. Etki ölçümü, güncel durumdaki hareket sırasına bağlı olarak yerel (ilgili) ve yerel olmayan (ilgisiz) hareketler arasındaki farklılığı kullanan kaba ilişki formudur. Bizim dallanma tekniğimiz hareketin ilgili mi yoksa ilgisiz mi olduğuna karar vermek için güncel durumdan m tane önceki hareketi kullanır, eğer ilgisiz hareketse aramayı o noktada keser. Bu teknik Sokoban problemlerini çözmede kullandığımız arama çabasını/gayretini azaltır.
Anahtar Kelimeler: Single-agent arama, heuristic arama, Sokoban J, yerel arama, IDA*.
GİRİŞ ve MOTİVASYON
İnsanlar başarılı bir şekilde geniş bir arama yüzeyinde meta-seviyesindeki karar verme yetenekleri sayesinde hareket edebilmektedirler. Bu süreçte bir plan oluştururken ilgili farklı hareketler hesaba katılır, ilgisiz hareketler bulunduğu an aramaya son verilir ve plana dahil edilmez. Her hareket küçük hedefleri tamamlamak için bir dizi mantık sırasını izler.
Küçük arama yüzeylerini tararken, bilgisayar meta-seviyesindeki karar verme yeteneğinin getirdiği üstünlüğe erişmeden temel seviyede kalarak arama yüzeyinin büyük bir oranını birer birer sayarak etkin bir şekilde işin üstesinden gelir. Lakin, muhakeme yaparak bir insan tarafından kolayca çözülebilecek bir problem bilgisayar tarafından standart arama algoritmaları kullanarak büyük bir güç harcanarak çözülebiliyor. Eğer bilgisayarlarında daha geniş arama yüzeylerini başarılı bir şekilde aramalarını istiyorsak meta-seviyesinde muhakeme yapabilmeleri için bilgisayar algoritmaları geliştirmemiz gerekir. Boş hareket aramaları ve kullanışsız yerlerde kesme yöntemleri gibi meta-seviyesinde muhakeme yapabilen algoritmaların geliştirildiği (iki oyuncu arama) bilgisayar oyunları var. Single-agent arama için makro hareketler örnektir. Bu makalede, ilgili kesitleri, single-agent arama için geliştirilmiş meta-düzeyi muhakemeyi tanıtacağız. Bu arama kendisinden sonraki hareketi seçmede kısıtlandırılıyor. Sınırlandırılmış istisnalar olmak kaydıyla sadece kendisinden önceki hareketlerle ilgili hareketlere izin veriliyor. İlgili hareketin tam tanımı uygulmaya bağlıdır.
Doğa resmi çizen bir sanatçıyı düşünün. Resmi çizmenin bir yolu önce ayıyı çizmek sonra gölü daha sonra dağı ve son olarak bitki örtüsünü çizmektir. Alternatif bir yolda, önce ayının bir kısmını çizmek, sonra dağı çizmek sonra ayıya dönmek daha sonra biraz bitki çizmek ve dağa devam etmek vb... İlk yöntem insanın resim çizişine uygundur: tanımlanabilir elemanan konsantre olmak ve istenilen tamlık yakalanana kadar onun üstünde çalışmak. Diğeri tipik bilgisayar yöntemidir: istenilen sonuca ulaşıldığı sürece hangi çizginin çizileceği önemli değildir.
Ne yazıkki çoğu arama algoritması insan örneğindekini izlemez. Aramadaki her bir nodta, algoritma önceki hamleyle ilgisine bakmak sızın her hamleyi hesaba katar. Örneğin, satrançta "a" piyonu ilerletme ve "h" piyonu ilerletmeyi düşünün. İnsan hareket sırasında "a" piyonu vezirin önüne koymayı analiz edecek. Bilgisayar kararsız ama legal sınırları "a" piyonu koymak sonra "h" piyonu koymak sonra "a" piyonu koymak... Açık olarak görülüyorki buna benzer alternatifleri düşünme etkili bir değerlendirme değildir.
Yukarıdaki örnekte eksik olan ilgi nosyonudur. Satranç örneğinde, piyonu “a” ya sürdükten sonra ve sonra “h” ye gitmeyi düşündükten sonra tekrar geri dönüp “a” piyonu düşünmek akıl karı gözükmüyor. İstisnalar kaideyi bozmayacak şekilde böyle geri çekilme hamleleri bir anlam ifade etmeyebilir.
Diğer bir iyi çalışılmış single-agent arama alanı/konusunda da, örneğin N-yap-boz ve Rubik’s küp, ilgi nosyonu önemli değildir. Her iki problemde de hamlelerin hareket alanı sınırlıdır, örneğin bir durumdaki tüm legal hareketler bir sonrakine “kapalı” (yerel) dır. Gerçek hayatta karşılaştığımız önemli problemlerde yerel veya yerel olmayan hareketlere izin veren geniş hareket alanları olabilir.
Bu makale ilgili kesitleri sunar ve Sokoban yap-boz’unun tek oyunculu labiren çözümündeki etkilerini gösterir. Sokoban için labirentin yapısını yansıtan yenibir ilgi metriği kullanırız. Hareket sadece m hareket önceki hareketler tarafından etkileniyorsa ilgili olarak hesaba katılır. Arama ilgili hareketleri yaparken önceki hareketleri hesaba katar ve sınırlı sayıda istisnaya göre ayarlanır. Bu sınırlamalar içinde arama alanının engellendiği rastgele hareketler süresince arama yerel olarak çaba harcamaya zorlanır. Meta seviyesinde düşünme kapasitesinde, programı yerel hareketleri düşünmesi için zorlama ona önceden hazırlanmış bir planı benimsetir; istisnalar planı değiştirmek için karar vermede kullanılır.
Arama ağacı boyutu, ve böylece problemi çözmede harcanan arama çabası, arama ağacının derinliğine ve etkin dallanma faktörüne bağlıdır. İlgili kesitleri amacı dallanma faktörünü azaltmaktır. Bizim Sokoban programı Rolling Stone için ilgili kesitler arama alanında geniş bir küçülmeyle sonuçlanır. İlgili kesitleri kullanarak Rolling Stone programı verilen 90 test probleminde 40 çözümden 44 çözüme çıkmayı başarmıştır. Problem zorluğunun üstel “exponential” artığı göz önünde bulundurulursa problemin çözüm sayısındaki göreceli küçük artışlar arama etkinliğindeki geniş artışlara sebep olur.
SOKOBAN
Sokoban tek oyunculu popüler bir bilgisayar oyunudur. Bu oyunun çekiciliği oyunun sade (basit) kurallarından ve aldatıcı kolay problemlerin meydan okuyan zekasından kaynaklanır. http://xsokoban.lcs.mit.edu/xsokoban.html adresinde Sokoban problemleri yer alır.
Oyun alanı 20x20’lik veya daha az bir dikdörtgen alan içindeki odalardan ve geçitlerden oluşur. Yerleştirilen kayaları hedef alana taşımakla görevli bir hamal Sokoban vardır. Hamal bir kerede bir kayayı arkadan itmek suretiyle hareket ettirebilir. Bir karede duvar, kaya veya hamaldan sadece biri olabilir. Tüm kayaları hedef bölgeye taşımak yeterince zor olmasına ramen en az kaya itme veya en az hamal hareketi kısıtlamaları getirilerekte oyun zorlaştırılabilir.
Kareleri yatay olarak “A”dan “T” ye ve dikey olarak “a”dan “t”ye etiketleyerek 20x20 lik bir koordinat sistemi oluşturulur. Bir hareket kayayı bir kareden diğer kareye itmekten oluşur. Hareket hamalın kayayı arkadan iterek hareket ettirmesini sağlayacak geçerli bir yolun varlığı söz konusu olduğu sürece yasaldır.
Kaya hareketinin sayısı veya hamal hareketinin sayısı diye iki metrik vardır. Genelde tek bir çözüm ikisinide en aza indirgeyemeyebilir. Çalışmamızda kayanın hareketlerini en aza indirmeye çalışacağız.
Kimin hangi problemi ne kadar etkin bir şekilde çözdüğünü saklayan ayrıntılı skor dosyası http://xsokoban.lcs.mit.edu/xsokoban.html adresindedir. Problemi çözme belirli bir ölçüde memnuniyet verir, çözümünüzü geliştirme bi o kadar önemlidir. En uygun/yüksek/iyi çözüm uzunluklarındaki mükemmel üst sınırları bu insan çözümleri sunar.
SOKOBANİIN HESAPLANMIŞ ZORLUĞU
Literatürde single-agent arama (A* ) yaygın bir biçimde araştırılmıştır. Sonuçta zor uygulamaları çözmede harcanan arama gayretinde etkileyici bir azalma sağlanmıştır. Lakin, uygulamalar aşağıdaki özelliklerin (tümüne veya) bir kısmına sahip olmada eskiden gelişmiş single-agent arama yeterliliği gösterirken şimdi basittirler.
- etkin ve hesaplı alt limit tahmincileri
- arama ağacında küçük dallanma faktörü
- uygun (kabul edilebilir) çözüm uzunlukları
- hareketlerinin tümü geri alınabilir olma.
Bilgisayarlar için Sokoban zor bir problem alanıdır ve aşağıdaki sebeplerden dolayı önceki çalışılmış alanlardan daha uğraştırıcıdır.
- Sokoban karmaşık alt limit tahmincisine sahiptir. Verilen N hedef için O(N^3)
- Sokoban için dallanma faktörü geniş ve çeşitlidir. (Potansiyeli 100’ün üstündedir.)
- Sokoban probleminin çözümü çok uzun olabilir. (Bazı problemlerde 600 hamleyi geçiyor)
- 20x20’lik bir alanla sınırlandırılmış problemler için Sokoban’ın arama alanının karmaşıklığı O(10^98) dir.
- Sokoban problemleri sıralı çözümler gerktirir. Alt hedeflerin çoğunun bir biriyle iletişim içinde olması problemi bağımsız alt hedeflere bölmeyi zorlaştırır.
- 15lik yap-boz ve Rubik’in kübünde tüm hareketlerer geri alınabilir ama Sokobanda bazı hamleler geri alınamaz.
Sokoban probleminin temelini oluşturan grafik direktir “directed”. Ek olarak, Grafikte çözümü içermeyen yollar vardır. Bu iki özelliğin bulunması çıkmazlar “deadlocks” gerekli ve yeterlidir. Boşuna yapılan aramaları engellemek için çıkmazları tanımlamak önemlidir.
İLGİLİ ÇALIŞMALAR
Sokoban PSPACE-complete olarak gösterilir. (Wilfong’un çalışması ve ambardaki robotla karşılaştırılabilir). Sokoban yapay zeka araştırmalarının akıcılığı için deneysel test-yeri “test-bed” olarak kullanılan oyunun mükemmel bir örneğidir.
ROLLING STONE
Rolling stone programını kullanarak farklı teknikler ve arama yeterliliği üzerindeki etkilerini karşılaştırdık. Aşağıda programımızın temel parçalarının listesi vardır:
IDA*: Rolling stone programı tekrarlamalı derinlik A* arama algoritması kullanır. A* ve IDA* herhangi bir durumdan hedef durumuna kadarki uzaklıkta makul bir alt limit kullanır. IDA* kısmi bir uzunlukta çözüm arayarak tekrar eder. Eğer çözüm bulunursa arama o noktada sona erer. Alt limit tahmin edici gerekli sayıda hamlede çözümün bulunmadığını garanti ederek büyük bir oransda arama ağacını elimine eder.
- Alt Limit: Pozisyon ile hedef arasındaki mesafeyi
makul bir şekilde tahmin etmede Mükemmel İki Parçalı Eşleştirme
algoritması kullanılır. Eşleştirme her kayayı hedefiyle eşleştiri
ve tüm kayaların hedefleriyle toplam (minimum) uzaklığını döndürür.
- Yerdeğiştirme Tablosu: Sokoban’ın arama yüzeyi ağaç
yerine tekrar eden noktaları ve döngüleri mümkün kılan grafiktir.
Yerdeğiştirme tablosu kesin kaya yerleri ve adama erişmeyi hesaba
katarak eş adam yerilerini kullanarak bir pozisyon haritası oluşturur.
- Hareket Sırası: Program, dallanma noktalarının alt dallarını
çözüme ulaşma ihtimaline (çözüm eğilimine) dayalı olarak sıralar.
Hareket sırası arama ağacını sadece son tekrarlamada küçültür.
- Çıkmaz Tablosu: 4x5lik parseller halinde çıkmaz
noktaların saklandığı tablodur. IDA* araması sırasında güncel
durumun çıkmaz ile sonuçlanıp sonuçlanmayacağını çıkmaz
tablosunu kullanarak saptarız. Yerel çıkmazlarla sonuçlanacak
hareketleri eleyerek etkin dallanma faktörünü azaltmada çıkmaz
tabloları kullanılır.
- Tünel Makroları: Sokoban labirenti sıkça tünel içerir.
Bir kere kaya tünelin içine itildimi sonuna kadar tüm yol boyunca
itilmelidir.Bunu keşvetmek için tekrar tekrar arama yerine bu
hareket sırası tek bir makroda saklanabilir. Bu yolla arama ağacını
küçültebiliriz. Tünel makroları ön süreç veya ön işlem olarak tanımlanır.
- Hedef Makroları: Aramaya başlamadan önce hedef alanın
nasıl doldurulacağı ile ilgili bir ön arama yapılır. Çıkmazlara
yol açabilecek hamlelerden kaçınmak için özel bir arama yapılır.
Hedef alanla ilgli bu bilgiler çıkmazlara meydan vermeden kayaların
hedef karelere yerleştirilmesi için kullanılacak hedef makroyu
oluşturmada kullnılır.
- Hedef Kesitler: Bir kayanın hedef bölgesinin girişine
getirildiği anda herhengi bir makro düşünülmeyebilir. Bu kesitlerin
arkasındaki fikir biri eğer makrolara güvenmiyorsa alternatif
dallanmalarla kayayı itebilmesidir. Yani makro yerine aramaya
devam ederek farklı yollar bulunmasıdır.
- Şablon Arama “Pattern Search”: Şablon arama alt limitlerin etkinsizliğinin bulunmasında etkin bir yoldur.küçük, yerel bağdaşmayan aramalar alt limitin yeterince büyük olduğu (çıkmazlar için sonsuz) kayaların şablonlarını kapsamaz. Bu şablonlar arama süresince aramayı geliştirmede kullanılır. Şablonlar değişmez zayıf alt limitlerle sonuçlanacak veya düzeltilmiş ölçümleri olan penaltılar oluşturacak aktif kaya etkileşimleri hakkında bilgi sunar.
SONUÇLAR
Şablon aramalar en pahalı ama en kazançlı elemanlardır. Arama ağaçları hala çok derin ve etkin dallanma faktörü haddinden yüksektir.
İLGİLİ KESİTLER
Makul bir “ilgi” yaklaşımı “etki”dir. Eğer iki hareket birbirlerini etkilemiyorsa, bu iki hareketin birbiriyle ilgili olmadığı sonucuna varabiliriz.
Bir hareketin ilgili olduğunu düşünmek için o hareketten önceki m tane hareketin onu etkilemesi gerekir. Aramaya sadece önceki hamleler dikkate alınarak ilgili hareket yapması için izin verilir ve sadece bir iki küçük istisnaya izin verilir. Meta seviyesinde düşünme kapasitesinde, programı yerel hareketleri düşünmesi için zorlama ona önceden hazırlanmış bir planı benimsetir; istisnalar planı değiştirmek için karar vermede kullanılır.
ETKİ
İki hamle arasındaki etkiyi bulmak için iki hamlenin kareleri arasındaki etkileşimi kullanırız. İki kare arasındaki etkileşim kareler arasındaki “en etkili yol” nosyonu ile saptanır. Bu en az masraflı yol olarak düşünülebilinir ama etki maliyet metriği olarak kullanılır.
Labirentin yapısını hesaba katma etki ile orantılı olmayan basit bir coğrafik uzaklık ile sonuçlanır.
Aşağıdaki özellikleri etkiyi ölçmede kullnırız.
- Alternatifler: İki kare arasında ne kadar fazla
alternatif varsa kareler birbirlerini o kadar az etkilerler.
- Hedef Eğrisi: Verilen bir kare için hedefe ulaşmada
kullanılacak yol üzerinde olan kareler yol üzerinde olmayan
karelerden daha fazla etkilidir.
- Bağlantılar: İki komşu kare aralarından bir kaya
hareket edecek şekilde birleşmişlerse birbirlerini sadece
aralarından adamın geçebileceği durumdakinden daha fazla etkilerler.
- Tünel: Tünelin içinde tünelin uzunluğu farketmeksizin etkileşim hep aynısdır.
Bizim ilgili kesit uygulamamızda küçük “off-line” aramalar labirentteki diğer her kareye, her bir kare için etki değerlerini saklayan (20x20)x(20x20)lik bir tabloyu önceden hesaplamak için kullanılır. Her kare çifti arasında en geniş etkiyi içeren yolu bulmak için breadth-first arama kullanılır. Etki sayısı ne kadar küçükse iki karenin birbirlerini etkilemesi o kadar fazladır.
Etkileşim simetrik değildir.
Bizim uygulamamız herhangi bir çift kare arasındaki en geniş etkiyi bulan en kısa yol bulma algoritmasını çalıştırır. İlk kareye başlangıç karesi ve ikinci kareye gidileçek/varılacak kare diyoruz. Başlangıç ve gidilecek kare arasındaki yolda bulunan tüm kareler ne kadar etkileşim içinde olduklarına bağlı olarak katkıda bulunurlar. Bir çift kareye ne kadar fazla puan veriliyorsa o iki kare birbiri ile o kadar az etkileşim içindedir.
- Alternatifler: Yol üstündeki s karesi yol üstünde olmayan
iki komşu kareye sahip olsun. Herbir komşu kare, n için takip
eden puanlar eklenir. 2 puan eğer s’den n’ye kaya itilebiliyorsa;
1 puan eğer s’den n’ye sadece adam hareket edebiliyorsa ve 0
puan eğer n duvarsa.
- Hedef Eğrisi: Eğer labirentte s başlangıç noktası ve gidilecek
nokta arasındaki optimum yol üzerindeyse alternatif puanlar
ikiye bölünür.
- Bağlantı: Eğer kaya gidilecek noktaya doğru ittiriliyorsa
1 puan eklenir. Eğer sadece adam iki kare arasındaki bağlantıdan
(gidilecek kareye doğru) geçebiliyorsa o zaman 2 puan eklenir.
- Tünel: Eğer önceki kare tüneldeyse, üstteki özelliklere bakılmadan 0 puan eklenir.
İLGİLİ KESİT KURALLARI
m1 ve m2 verilen iki hamle olsun. Eğer hamle kareleri biribirlerini etkilemezlerse m2 hamlesine m1’e göre uzak denilir. Daha doğrusu, iki hamle eğer etki tablosu [m1’den m’den] <=etki eşiği –Eşitsizlikteki etki eşiği, etki eşiğinin eşikle uyumlu olduğu yerlerdedir- ise birbirlerini etkilerler.
İlgili kesitler önceden oynan hamlelerden uzak olan hamleleri elerler ve böylece bu hamleler aramayla ilgili olarak düşünülmezler. Hamlelerin kesilmesinde/elenmesinde iki yol vardır.
- Eğer son m hamlede k uzak hamle yapılmışsa. Bu kesilme labirentin ilgisiz alanlarında arama yapılmasını engeller.
- Hamle önceki hamleye göre uzak ama eski hamlelere göre yakınsa. Bu önceden çalışılmış alana dönmemesine yardımcı oluyor.
Bizim deneylerimizde k=1 dir. Bu yolla ilk kesme kriteri ikincisini zorlayacak.
Labirentteki farklılıkları yansıtmak için etki eşiğindeki parametreler ve m aramanın başında saptanır.
- Etki Tablosu[x,y] de y’nin, x’ten herhangi bir hedefe giden optimum yolun üzerinde olmasını sağlayan tüm girdiler için ortalama değer hesapla.
- Ortalama haddinden yüksektir. İkiye bölerek dengele.
- Kesilmelerin çok fazla agresiv olmamasını sağlamak için etki eşiğinin 6’dan düşük olmasına izin verilmez.
Kullanılan hikaye (oynanmış hamle) uzunluğu, m, aşağıdaki gibi hesaplanır.
- Etki Tablosu[x,y] de y karesindeki kayanın hedefe itilebileceğini sağlayan tüm girdiler için ortalama değer hesapla.
- Kesilmelerin çok fazla agresiv olmamasını sağlamak için m’in 10’dan büyük olmasına izin verilmez.
ÖRNEK
Şekil insanların bu problemi çözmenin iki ayrı alt probleme ayırmadan geçtiğini anında tanımladıkları bir örneği gösterir. En uygun çözüm 82 hamledir; Rolling Stone alt limit tahmin edicisi 70 değerini döndürüyor. Standart IDA* 7 tekrarlamada çözümü buluyor. Hareket sırasına bakılmaksızın IDA* ilk 6 tekrarlamada problemin çözümünün olmadığını (en az 70+2*i hamlede) garanti ediyor. Alt limit 6 olmasına rağmen problem ikiye ayrılınca 4 tekrarlamada sonuca ulaşılıyor. Bu şekilde büyük bir arama yükü azaltılıyor.
Bizim uygulamamız sağdaki hamlelerden uzak soldaki tüm hamleleri düşünüyor (veya tam tersi). Böylece aramada sadece belirli bir sayıda sıçramaya “switch” izin veriliyor. Parametre ayarlarımız 9 hareketten sadece bir yerel olmayan harekete izin veriyor. İlgili kesitler hala en uygun çözümü verirken 32.803 nod sayısını 24.748’e düşürüyor. Kaydetmeler (%25) görecelik olarak küçülmüş gözüküyor çünkü yerdeğiştirme tablosu tekrar eden pozisyonları yakalıyor ve aramadan eleniyor. İlgili kesitlerin arama için gereken çabayı azaltmayı sağlamasının sevindirici olmasına rağmen Mümkün kaydetmelerin tümüne ulaşılmasında sadece küçük bir adımdır. Açıkça daha sofistike (karmaşık) yöntemler gerekiyor.
TARIŞMA
Bizim güncel uygulamamız için en az ilgili kesitlerin tepesi önemsizdir. İki hamlenin etkisi basit bir arama tablosuna yerleştirilmiştir. Bu tepenin çoğu problem için arama maliyetinde hakim olduğu şablon aramalarımızla yalın bir farklılıktır.
İLGİLİ KESİTLERE YAKIN BİR BAKIŞ
İlgili kesitlerin amacı arama ağacının boyutunu küçültmektir. Aramadan yasal (legal) hamleleri eleyerek buna ulaşabiliyoruz ve böylece ağacın etkin dallanma faktörünü küçültüyoruz. İlgi için iyi bir heuristic, sonuçları eleme ve ağacı küçültme arasındaki doğru dengeyi bulmada anahtar rol üstlenir.
TEORİK OLARAK İLGİLİ KESİTLER
Korf’un teorisini bizim algoritmamiza uygulayarak ilgili kesitler uygulamasını daha iyi anlayacağız.
IDA* aramadaki nod sayısını aşağıdaki formulle buluruz:
- n: toplam nod sayısı
- d: optimum çözümün uzunluğu
- h(kök): kök nodun heuristik değeri (<=d)
- b: etkin dallanma faktörü
- e: ağaçtaki iç nodların ortalama değeri
- sd: (optimum) d uzunluğuyla çözüm sayısı
Formülün ilk bölümü çözümü olmayan tüm tekrarların boyutunun toplamını gösteriyor. İkinci bölümde son tekrarlamanın boyu. Çözümün nodların dalında homojen dağıldığı kabul ediliyor. Eğer sadece tek çözüm yolu varsa, aramanın son tekrarı üzerindeki yolun yarısıdır.
İlgili kesitler denklemi iki yoldan genişletiyor. Birincisi çözümsüz tekrarlar boyut olarak küçültülüyor. Buna dallanma faktörünü küçültme etkisinde bulunan hareketlerin elenmesi yoluyla ulaşıyoruz. İkincisi, eğer ilk çözüm ilgili kesitler tarafından elendiyse ek bir arama yapılması olasılığının olmasıdır.
İki yollada ilgili kesitlerin aramaya etkisini yansıtmak için birinci denklem genişletilmiştir.
- x: kesitlerin girişkenliği
- r(x): girişkenlik fonksiyonunun olarak, ortalama dallanma faktörü küçültülmesi
- p(x): Olasılıkların birbirinden bağımsız olduğu kabul edilirse çözümün aramadan kesilme olasılığı
- a(x): beklenen ek tekrarlama sayısı
- sd+a(x): d+a(x) seviyesindeki çözüm sayısı
Performans uyum çabası kaydetmeler (arama ağacı boyutunu küçültme) ve maliyet (gerekenden daha fazla arama yapılması) arasındaki doğru dengenin bulunması yönünde yönlendirilmelidir.
RASTLANTISAL İLGİLİ KESİTLER
Neden-sonuç yaklaşımına göre aynı kurallar aynı durumlarda geçerlidir; ama manevraların olduğu durumlar aramadan ilgisiz aranlar oldukları düşünülerek atılabilirler. Böyle durumlarda bir mekanizmanın çalışması ve hatayı ayırtetmesi gerekir.
Çözüm ilgili kesite karar vermede rastlantıya yer verilmesidir. Eğer bir dallanma ilgili kesitle budanmışsa, rastgele bir sayı üretilir ve daha ileri gidilmelimi yoksa kesilmelimi ona karar verilir. Rastlantı ilgili kesitlere güvenmemizi yansıtır. Bu iki uç nokta arasında bir yer arama ağacı boyutundaki (çözüm bulunduğundaki ertelemelerle) küçülmeleri dengeleyen kesilme oranıdır.
DENEYSEL SONUÇLAR
Rolling Stone programı 25.000.000 nodluk arama limiti kullanılarak 90 problemlik bir test kullanılarak testedilmiştir. (Rastlantısal ilgili kesitler olmadan) ilgili kesitler yöntemiyle 40 çözümden (eskiden 40 tane çözülüyordu) 44 çözüme ulaşılmıştır.
Deneyde 9., 11., 21., 46., 49. ve 51. problemlerde optimum olmayan çözümler üretilmiştir. Bu ilgili kesitlerin güvenli olmayan doğasını göstermiştir.
Çözülen yeni 4 problem içinde 49. ilginç olanıdır. 100 milyon nodu 3 milyona indirmiştir. Bu problemi bir insan 11. tekrarlamada bulabilirken Rolling Stone ilgili kesitleri kullanarak optimum olmayan bir sonuç elde etmiştir, yani 13. tekrarlamada çözümü bulmuştur.
Bu deneye göre ilgili kesitler arama becerisini 5 kat arttırmıştır. Eğer 49. problemi hesaba katmazsak, bu kabaca 3.5 kat olarak görülebilir.
Problemler içindeki en iyi örnek 19 numaralı örnektir. Nod sayısı kabaca 10 kat azaltılmıştır.
RASTLANTISAL İLGİLİ KESİTLER
Program önceden her yerel kesilmeyi dikkate alırken şimdi sadece %80’ini dikkate alıp %20’sini geri çeviriyor. Bazı problemlerde gelişme olması beklenmiyor. Örneğin 1. problem zaten 270 hamlede çözülüyor, bunun daha ilerisi yok.
Şekil kabaca arama ağacının %80’inin ilgili kesitlerle elendiğini gösteriyor. Birinin aramayı %70 azaltmak için sadece %40 kesilmeleri kullanması gerekir. Böylece, küçük bir kesilme bile büyük kaydetmelere neden oluyor. Herbir kesilmeyle çözüm yollarınında azaldığı görülebilir, yani her kesilmede bir çözüm yolunu elemiş olabiliriz.
Bizim çalışmamızda 44 problemin sadec 6 tanesi optimum olmayan çözüm buldu. Kabaca problemlerin %13’ü optimum değil. Unutmayalımki bizim amacımız çözüm kalitesi değil problemin zorluk derecesini arttırark çözmekti, yani her bulunan çözüm bizimiçin sevindiricidir.
TEORİK OLARAK İLGİLİ KESİTLERE TEKRAR BAKIŞ
3. denklemimize dönersek ( b - r ) d - e teriminin hesaba hakim olduğunu görürüz. Biz d (optimum çözüm uzunluğu) nu biliyoruz ve b, r, ve e yi ölçüyoruz. Rolling Stone bu değerleri ölçmek için geliştirilen bir araçtır.
Dallanma faktörünün küçültülmesi probleme bağlı olarak değişkendir.
e değerinin ölçümü ilgili kesitler olduğunda veya olmadığında sadece küçük bir farklılık gösterir.
4. denkleme discharging d, e, b ve r yi ekleme tahmin edilen ve gözlenen ağaç boyutu arasında geniş bir farklılıkyaratır. Korf’un formülü dolaylı kabullenmeler içerir, örneğin, dallanma faktörü ağaç boyunca göreceli olarak tek düzedir. Sokoban problemlerinde dallanma faktörü hareketten harekete çılgınca atlama gösterebilir. Ek olarak, bizim çalışmalarımızda dallanma faktörünün ağacın köklerine yakın yerlerinde küçülme eğilşimi gösterdiğini saptamıştır ve problem basitleştikçe dallanma faktörünün oyunun sonunda bir kaç kaya kalıncaya kadar arttığı saptanmıştır. İlaveten, Veriler ilgili kesitlerin aramadan sonra değilde önce olma eğiliminde olduğunu gösteriyor.
3. denklemin diğer elemanı ilk çözüm ilgili kesitler tarafından kaçırıldığında ek arama çabası gereğidir. Bazı problemeler göreceli olarak yüksek hata oranına sahiptir; bu sonuçlar toplam kesilme sayısının küçük ve tek hatanın oranı çarpıtacağı yerlerdeki küçük aramalara sahip problemlerden gelir.
Son olarak, bizim çalışmalarımız ilgili kesitlerin %0.2 lik çözümü elediğini gösteriyor. Eklemeli dizi “articulation sequence” denilen bir terim var. Çözüm alternatif yollar içerebilir ama öyle bir nokta olabilirki çözüm output sırayı takip etmeden bitmez. Yani problemin çözümünde alternatif yolların hepsinin kapsadığı ve alternatifi olmayan bir yol vardır. Bu yola eklemeli dizi diyoruz. Bu yol eğer ilgili kesitler tarafından elenirse çözüme ulaşılamaz. Bizim bulduğumuz %0.2 lik hata oranı bu yol için haddinden fazladır. Biz bu menavraları (eklemeli diziyi oluşturan yolu) elememek için yeni yöntemler geliştirmeliyiz.
ÖZET
İlgili kesitlerin Sokoban problemlerinin çözümünde büyük bir arama gayretini indirgediği deneylerle gösteriliyor. Soruların zorluğu birazcık artsa bile çözüm için yapılan aramanın üstel olarak artması bizim ilgili kesitler yardımıyla çözdüğümüz 4 problemin gerçekten ne kadar önemli olduğunu gösteriyor.
SONUÇ ve GELECEKTEKİ ÇALIŞMALAR
Kaba bir yaklaşımla, ilgili kesitler geniş çaplı hamlelerden yerel hamlelere destek vermek için aramayı zorlamasından dolayı insan benzeri problem çözme yöntemlerini sağlar. Bu yöntem çözümü kaybetme pahasına bile olsa arama ağacının boyutunu küçültmede büyük bir olanak sağlar. Verilen Sokoban arama ağaçlarının genişliği ve derinliğiyle optimum çözüm bulmak ikinci düşüncedir; herhangi bir çözüm bulmak yeterince uğraştırıcıdır. Bizim ilgili kesitleri geliştirmek için bir çok düşüncemiz var. Bunlardan bir kaçı:
- Kalabalığa baplı farklı uzaklıklar kullanmak. Dinamik etki ölçümleri statikten daha iyidir.
- İlgili kesitlerde bir çok parametre vardır. Bunların üstünde çalışmak olağanüstü başarılar getirebilir.
- Giriş kısmında anlattığımız insanın resim çizişi gibi olmasada yakın elemanları bir bütün gibi çizecek bir algoritma geliştirilebilir.
İlgli kesitler hala Sokoban arama ağaçlarını dallandırmada önemli bir yol değildir. Yeni fikirlerle sadece 4 problemi daha çözdük. Eğer 90 problemin hepsini başarılı bir şekilde çözmek istiyorsak daha fazla çalışmalıyız.
Kaynak
KONU
Bu paper da search space problemlerinde kullanilan performans gelistirme yontemleri tartisiliyor. Bu gelistirmeler taranacak olan bolgeyi onemli olcude kucultuyorlar.
GİRİŞ
Genel olarak yapay zeka çalışmaları konudan bağımsız (domain independent) çözümler üzerine yoğunlaşmış fakat daha sonra gorulmus ki özel bir konu üzerinde yapılan çalışmalar daha verimli sonuçlar veriyor. Domain-independent cözümler konu hakkında arastırma gerektirmedikleri gibi aynı zamanda fazla programlama uğraşısıda gerektirmezler fakat tarama alanları çok büyüktür ve bütün kaynakları tüketirler.
Standart tarama tekniklerinin sokoban problemleri için yetersiz olduklari anlasildiktan sonra (90 problemin sadece 10 tanesi çözülebiliyordu) yeni algoritmalar geliştirilmeye başlandi ve bugun çözülebilen problem sayisi 52 ye yükseltilebildi. Bu başarının temel nedeni, kouya ozel bilgi ve gelistirmelerin eklenmesiydi. Bu da bize konuya-bagımlı yöntemlerin bize kazandirdiklarini açıkça gösteriyor.
Genellikle literatürde single-agent tarama yöntemlerinin birkaç satır program koduyla yapilabileceği anlatılır ama bunlara eklenebilecek olan gelistirmelerden pek bahsedilmez. Aslinda daha iyi bir performans için çeşitli geliştirmeler kullanilabilir.
KONUDAN BAĞIMSIZ YÖNTEMLER
Daha çok çözüm kümesi küçük problemlerde kullanilabilecek bir yöntemdir. Yapilan denemelerde blackbox isimli bir programla Sokoban problemleri çözülmeye çalışılmış ve görülmüş ki ilk problem birkaç saniyede çözülebilmesine rağmen ikinci problem için bir saatten fazla zaman gerekmiş.
KONUYA BAĞIMLI YÖNTEMLER
Bu yöntemler kullanilarak yapilan Sokoban çalışmalarında algoritma 1 milyar “node” ile sınırlanmış ve eklenen her geliştirmeden sonra program 90 problemle tekrar denenmiştir.
Kullanilan yöntemler ve çözülebilen problem sayisi şöyle:
| Yöntem | Çözülebilen Problem Sayisi |
| Lower Bound | 0 |
| Transposition Table | 6 |
| Move Ordering | 6 |
| Deadlock Table | 8 |
| Tunnel Macros | 10 |
| Goal Macros | 23 |
| Goal Cuts | 26 |
| Pattern Search | 46 |
| Relevance Cuts | 47 |
| Overestimation | 52 |
Kısaca bu yontemleri açıklamamız gerekirse;
- Lower Bound: Bu yontemde herhangi bir durumda hedef duruma olan uzaklik belirlenir ve yapilmasi gereken hamle sayisi (minimum) hesaplanir. Bu yontem tek basina hiç problem çözememektedir.
- Transposition Table: Bu tablo tekrarlanan durumların önlenmesi amacıyla olusturulur ve onceden gelinen veya devamli kendini tekrarlayan durumların engellenmesini sağlar. Arama ağacını büyük ölçülerde düşürebilen bir yöntemdir.
- Move Ordering: Burada amaç ağaç içindeki dallanmalardan çözüme en yakın olanını seçmektir. Bu yöntemle ek olarak çözülebilen herhangi bir program olmamasina rağmen arama uğraşını düşürür.
- Deadlock Table: Belli durumlarda meydana gelebilecek olasi kitlenmeleri tespit için kullanılan bir yöntemdir. Bunun için 4 x 5 lik bir alanda oluşabilecek bütün durumlar bir dosyaya kaydedilir ve arama sırasında bu dosyadan mevcut durum kontrol edilir ve bu sayede oluşabilecek kitlenmelerin önüne geçilmiş olunur.
- Tunnel Macros: Harita üzerinnde bulunan tüneller ön bir incelemeyle bulunur ve buralardan geçirilecek olan taşlar arama yapilarak değil tek makro hareketiyle tünelden geçirilirler. Buda ağacın boyutunu küçülttüğünden bizim için yararlı olur.
- Goal Macros: Bu yöntemde hedef bölge üzerinde taşların nasıl yerleştirilmesi gerektiği önceden belirlenir ve hedef bölgeye yaklaşan taşlar tek bir makro hareketiyle bu yerlere sırayla yerleştirilir. Her bir makro hareketi tek hamle sayıldığından arama bölgesini önemli ölçüde küçültür ve verimi artırır.
- Goal Cuts: Eger bir taş hedef bölge sınırına gelmişse hedef makrosunun çalıştırılmasını sağlar ve böylelikle diğer hareketler gözardı edilmiş olunur.
- Pattern Searches: Çalışma sırasında duruma özel olarak çalışırlar ve minimum hamle sayısını kesinleştirmede kullanılırlar. Bu yöntem cok büyük ölçülerde katkıda bulunur ve 20 ek problemin çözülebilmesini sağlar.
- Relevance Cuts: Yapacağımız hamlelerin daha önce yaptıklarımızla olan ilişkisini ve alakasını hesaplamaya yarar. Olası çözüm yollarını eleme ihtimali olduğundan çok güvenilir olmasada ağaç büyüklüğünü düşürdüğünden yararlı bir yöntemdir.
- Overestimation: Sonuca olan uzaklığımız hakkında yaptığımız tahmini geliştirmek üzere kullanılan bir yöntemdir.
Programın bu geliştirmeler eklenmeden ve eklendikten sonraki performansi arasinda dikkate deger bir fark vardir. Ancak bunlardan en ilgi çekeni Lower Bound fonksiyonudur. Bu fonksiyon tek basina hiç problem çözemesede bu fonksiyon olmadanda sistem hiç problem çözemeyecektir. Diğer önemli geliştirmelerde; Goal Macros (35 problem daha çözülebilmesini sağliyor), Transposition Table (23 problem kazandiriyor), ve Pattern Search (16 problem kazandiriyor). Diger geliştirmelerin programdan çıkarilmasi pek fazla bir kayıp yaratmazken yukarıdaki 3 fonksiyon oldukça büyük bir performans kaybına neden oluyor.
KONTROL FONKSİYONLARI
Konuya bağımlı yöntemlerde kullanilan diger bir geliştirme yöntemide kontrol fonksiyonlaridir. Bu fonksiyonlar diğer fonksiyonlarin ne zaman kullanılacaklarını denetlerler. Bu sayede program performansına önemli ölçüde katkıda bulunurlar. Örnek olarak bir problem içinde eger bir fonksiyonun çalişmasi çok zaman kaybına neden oluyorsa ve sadece bazı durumlarda kullanılması gerekiyorsa, kontrol yapilari bu fonksiyonun sadece gerekli olduğu zamanlarda kullanılmasını sağlar. Kontrol fonksiyonlarına örnek olarak Transposition Table (Tekrar eden durumlerı engeller), Goal Macros (Hedef bolgeye ulaşıldığında tek hareketle taşı hedefe yerleştirir) ve Pattern Searches (Geriye kalan hamle sayısını belirlemede yardımcı olurlar) yontemlerini denetleyen fonksiyonlar sayılabilir.
Herhangi bir gelistirmeyi programlamak sadece kısa bir zamana malolurken bunun kontrol fonksiyonlarının yazılması cok daha fazla zamana ihtiyaç duyar ve programimizin genel performansını da buyuk olcude etkiler.
SONUÇ
Bu yazida genel olan bahsedilen konu Domain-dependent yöntemlerin geliştirilmesine yönelik çalişmalar anlatilmiş ve bunlardan çıkarılacak en temel sonuç ta domain-independent yöntemlerin domain-dependent yöntemlerle karşılaştırıldığında çok hızlı bir programlamayla hazırlanabildiği fakat domain-independent yöntemlerin çok daha verimsiz çalıştığıdır.
Kaynak
Bu paper AI'in karisik search problemlerini cozmek icin kullandigi methodlardan bahsediyor. Bu methodlarin kullanilma amaclarinin search tree'lerinin size'ini dusurmek olduguna dikkat cekiyor.
GİRİŞ
AI'nin problemleri cozmek icin cok genis search teknikleri kullandigindan bahsedilmis. Porblemleri cozmek icin alandan bagimsiz ( Domain-independent ) arastirma teknikleri kullanilmaya baslanmis. Bu teknikler fazla caba gerektirmemesine ragmen, cok basit problemlerde dahi problemi cozen kisinin performansini sinirliyormus.Bu yuzden arastirma alanina bagli ( domain-dependent ) teknikleri kullanilmaya baslanmıs. Bu tekniklerin search tree'lerinin size'ini onemli olcude dusurdugu gorulmus. Bu domain-dependent tekniklerin Sokoban gibi cozulmesi zor problemleri ( NP-hard, PSPACE-complete ) cozmek icin kullanildigi soylenmis. Ilk onceleri sadece 90 problemden 10 tanesi cozulebilmis.Sonradan teknikler uzerinde cesitli gelistirmeler yapilarak bu sayi 50'ye kadar cikartilmis. Bu gelistirmeler soyle siniflandirilmis: generality, computational model, comleteness and admissibility.
SOKOBAN
Sokoban probleminde amac bir adamin labirentin icindeki butun kayalari sadece iterek ( cekmek yasak ) onceden belirlenmis yerlerine yerlestirmesini iceriyor. Bu isi yaparken adama her seferinde sadece bir tane kayayi itmesi gerektigi gibi cesitli sinirlamalar getiriliyor. Sokoban probleminde bazen cozulemeyen problemlerle ( deadlock ) karsilasilabiliyor ( kosede bir kayanin olmasi gibi ). Bu paperda cesitli sokoban problemlerini cozmeye calisacagimiz soyleniyor. Bu problemlerin ozellikleri su sekilde siralanmis.
- Sokoban'in yapisi bazen bir directed graph gibi olabiliyor, yani bazi harekelerin tersi olamiyor. Bu da deadlock'lara neden olabiliyor.
- Cesitli uzun cozumlerin birlesimi ve bazi tree'lerdeki buyuk dallanmalar okoban problemlerinin cozumunu zorlastiriyor. 20x20'lik bir labirentin search space'sinin size'i 1098 olarak hesaplanmis.
- Sokoban problemleri sirali bir sekilde ilerliyor. Yani bazi kucuk parcalar dgistirelemiyor. Bu yuzden problemi kucuk parcalara bolmek etkili olmuyor.Ornegin bir problemden bir tane kayanin cikartilmasi problemi degistirdigi icin bu tip parcalamalar yapilamiyor.
- Sokoban problemlerinin cozumunde basit ve etkili bir lower-bound elde etmek cok zor. En iyi lower-bound estimator'lari pahalilar ve cogu zamanda etkisiz oluyorlar.
Sokoban problemlerinde cok fazla sayida zor search-space ozellikleri var. Bilimsel arastirma methodlarinin traditional domainleri - NxN-puzzles ve Rubik's Cube gibi - en az bir search-space ozelliklerine gore daha kolaylar. Asagida cesitli problemlerin karsilastirilmasi verilmis.
| Propety | Specifies | 24-Puzzle | Rubik's Cube | Sokoban |
| Branching Factor | Average | 2.37 | 14 | 12 |
| Range | 1-4 | 18 | 0-136 | |
| Solution Length | Average | 100+ | 18 | 260 |
| Range | 1-80 | 1-20 | 97-674 | |
| Search-Space size | Upper Bound | 1025 | 1019 | 1098 |
| Calculation of Lower Bound | Full | O(n) | O(n) | O(n3) |
| Incremental | O(1) | O(1) | O(n2) | |
| Underlying Graph | Undirected | Undirected | Directed |
UYGULAMA-BAĞIMSIZ TEKNİKLER ( Application-Independent Techniques )
Genellikle kucuk domain'li problemlarin cozumunde kullaniliyor. Sokoban problemlerini cozmek icin Blackbox isminde bir program yapilmis. Bu program ilk problemi ( icinde sadece bir tane tas bulunan ) birkac saniyede cozebimis fakat ikinci problemin cozumu ( icinde iki tane tas bulunan ) 90 saniye surmus. Domain-independent problemlerle cozum yapan kisiler otomatik olarak buyuk search-space'lerini etkili bir bicimde traverse bilgisini belilemede yetersiz kaliyorlarmis. Bu yuzden, baska secenegimiz olmadigi icin, sokoban problemlerini cozmekde domain-dependent search tekniklerini kullaniyoruz.
UYGULAMA BAĞIMLI TEKNİKLER ( Application-Dependent Techniques )
Sokoban implementation'larinin tabanini iteraive deepening A* (IDA*) olusuruyor.Butun uygulamalarda kullanilacak olan algoritma 20 node milyon iceriyor. IDA* algoritmasinin uzerinde 3 yili askin bir suredir gelistirmeler yapiliyor.Bu gelistirmelerden sonra Rolling Stone adli programla 90-problem uzerinde denemneler yapildi ve kac tane problem cozulebildigine bakilmis. Basit IDA* ve simple lower-bound estimastor'la baslayarak programin her versiyonu R0'dan R10'na kadar kronik olarak siralanmis.
Simple Lower-Bound ( 0 problems solved )
Tek basina bir problem cozumeyecegi biliniyormus. Ilk lower bound her kayanin en yakinindaki hedefe ulastirilmasiymis.Fakat lower-bound degerleriyle gercek cozumler arasinda cok buyuk farklar varmis.Bu yuzden etkisiz kalmis.Iyi bir performans elde etmek icin iyi bir lower bound bulmak sart oldugu icin application-dependent knowledge'e ihtiyac duyulmus.
Minimum Matching Lower-Bound (R0, 0 problems solved )
Daha admissible bir lower bound elde etmek icin olusturulmus. Her kaya bir hedefe assign ediliyor ve butun kayalarin hedeflerine olan toplam minimum uzakligi aliniyor.Minimum cost O(n3)'mus. Bu yuzden gelistirilmek zorunda kalmis.En son haliyle search tree'nin size'I 1015 azalmis. Fakat bu minimum matching lower bound da 20 milyon node sinirinda tek basina hicbir problem cozememis. Bu yuzden sinir 1 milyar node'a cikartilmis fakat yine hicbir problem cozulememis.
Transposition Table (R1, 5 problems solved )
Search space'ler genellikle graph yapisinda olduklari halde bunlar uzerinde tree'misler gibi islemler yapiliyormus. Tree'ler dallanadikca cok buyudukleri icin ve bazi durumlarda bos yere ayni dallari kontrol edebilecegimiz olasiligina karsilik bir tablo tutmayi uygun bulmuslar ve her seferinde bu tablolalara baktiktan sonra dallar uzerinde islemler yapilmaya baslanmis. Tablolar eklendikten sonra 20 milyon node limitinde 5 tane problem cozulmus.
Move Ordering (R2, 4 problems solved )
Her dala rastgele gitmek yerine, dogru olma olasiligi yuksek olan dallara ilk once gitmeyi hedef almislar. Bu best-first search'lerde kullanilmiyormus.Fakat depth-first ebreadth-first search'lerde efficiency kazandiriyormus. IDA* search'lerde ise hicbir kar veya zarar saglamiyor. Bu yontem kullanilarak bir problem kisa bir sure icinde 20 milyon node sinirinda cozulebilmis ve iki tanesinin cozumu de daha fazla node gerektirmis.
Deadlock Table (R3, 5 problems solved )
Bu yontemde de search space'inin icinde daha kucuk bir dikdortgen seciliyor ve o alandaki deadlock'lara bakiliyor ve o deadlock'lar bir tabloda tutuluyor.Hareket yapilmadan once deadlock tablosuna bakiliyor. Eger tablo'da varsa hareket yapilmiyor.Deadlock tablolari search tree'lerinin dallanma size'lerini %20 azaltiyormus. Search'un exponential oldugu dusunulurse cok buyuk bir azaltma oldugu farkedilecektir. Bu yontemle de 5 tane problem cozulebilmis.
Tunnel Macros (R4, 6 problems solved )
Eger labirentin icinde tunel varsa ve bu tunelden her seferinde sadece bir tane kayanin gecebilecegi genislikteyse, kayalar bu tunelden tek tek gecirilmeliler.Yani tunelin icinde kaya birakilmamali.Bu yuzden tuneli gecinceye kadar yapilan movelar birbirinin aynisi olacaktir. Bu tuneldeki hareketler macro olarak tanimlaniyor ve her tunele giriste move'un yerini bu macro aliyor. Bu yontem search space'lerini onemli olcude azaltiyorlarmis. Bu yontemle fazladan bir problem daha cozulmus.
Goal Macros (17 Çözüm)
Çoğu Sokoban problemlerinde hedef alanlar belli odalara toplanmistır. Bu tip problemlerde problem iki parçaya bölünmüş:
- Taşlar nasil hedef alanlarının bulunduğu odalara sokulacak ve
- Bu taşlar nasıl hedef alanlarına konulacak.
Bu problemlerde genelde bu tip alt problemler birbirinden bağımsız çözülmüş. Eğer bir taş, hedef alanlarının olduğu odaya girerse direk hedef alanına koyulmuş. Bu konma işlemi hedef makroları tarafından yapılmış. Bir taş için birden fazla hedef makrosu olabilirmiş. Kaya hedefe ulaşınca başka bir şey düşünülmüyormus. Bu da geri kalan problemin karmaşıklığını azaltıyor. Hedef makrosunun tünel makrosundan farkı, hedef makrolarında alternatif yollar araştırılıyor. Hedef makrosu yapılırken diğer hareketlerin ortadan kaldırılması aranacak ağacın boyutunu tünel makrosundan daha çok etkiliyor.
Bu yöntem kullanılarak 6 yerine 17 problem çözülmüş. Bazı bireysel problemlerde arama "node" larının sayısı oldukça azalmış. Aramalar ortalama 20 kat azalmış. Bu ortalama tutucuymuş çünkü başarısız aramalar 20 milyon "node" da durdurulmuş.
Goal Cuts (24 Çözüm)
Hedef makrolarının tahmin fonksiyonları, hedef makrosu çalıştırılırken pek çok hareketi eliyormuş. Bunun nedeni eğer bir taş hedef alana itiliyorsa, bu diğer hareketlerden etkilenmeyeceği için diğer hareketler ihmal ediliyormuş. Aynı şeyler diğer hedef makroları içinde geçerliymiş. Goal cut lar arama alanını küçültüyormuş. Eğer bir taş diğer taşları etkilemeden hedef makrosu ile hedefe ulaştırılıyorsa o taşı itmek için yapılabilecek alternatif hareketlerin hepsi hareket listesinden siliniyormuş. Bu yöntemle 24 problem çözülmüş. Problem 65 "goal cut" sız çözülemiyormuş. Çözülmüş problemler için ortalama arama alanı 6 kat azmış.
Desen Araması (Pattern Search - 47 - 48 çözüm)
Taşların yaptığı hareketlerin alt sinirlarına (lower bound) sayı vermişler ve kitlenme ye neden olanlarada ¥ sayısı vermişler. Bu alt sınır en az 2 en fazla ¥ olabiliyor (kitlenme durumu). Eğer yanlış bir hareket gözlenirse bu o pozisyon için olan alt sınır ölçümüne ekleniyor. Bu sayede alt sınır fonksiyonu oldukça iyi tahminde bulunuyor. İki çeşit haritadan (maze) den bahsediliyor.
Orjinal harita: veri yapılarının kullanıldığı (IDA* araması tarafından)
Test haritası: Desen araması için kullanılan
Desen aramaları test haritasındaki taşların sayısıyla ilgilenir ve kitlenme olup olmadığını kontrol eder. Eğer bir hareketten önce kitlenme yoksa o hareket desen içinde sayılır. PIDA* (IDA nın bir versiyonu) bu tip en iyi haritaları çözüyormuş. Ya bir sonuç buluyor yada başarısız (fail) oluyormuş. Eğer bir sonuç bulursa ve eğer bu sonuç bizim alt sınırımızla çelişirse alt sınır fonksiyonu hatalı ve düzeltilmeli demek oluyor.
Bu tahminin çalışma yöntemi şöyle:
Bir hareket yapılıyor ve sonra sadece bu hareketin yapıldığı yerdeki taş esas alınıp arama yapılıyor ve kitlenme araştırılıyor sonra labirentteki taşlarla çelişen bir taş haritaya (maze) eklenip yeniden çözüm aranıyor, her seferinde yeni bir taş ekleniyor ve kitlenme araştırılıyor. Eğer kitlenme olursa hareket yapılmıyor, olmazsa yapılıyor. Hareketin yapıldığı yeri etkilemeyen taşlar gözardı ediliyor. Bu yöntemle yukardan aşağı kanıt (top-down proof) yapılıyor. Bunun method of Anologies ten farkı onun bottom-up tahmin yaklaşımını kullanıyor olması.
Minimal Penalty Pattern, sadece kitlenmeyi yapan taşları haritaya koyup kaydediyor ve tektaş ekleyip yeni haritaya geçiyor. İlk bakışta N harf kaydedilmişse bir tane ekleyip N+1 taşı kontrol ediyor. Bu da pattern in minimum olmasini sağlıyor. IDA* arama sırasında her "node" da normal en az alt sınır hesaplanıyor. Bu değer cutoff için yetersizse penalty pattern ile çalışıyor demektir ve en yüksek penalty hesaplanıp alt sınır a ekleniyor. Eğer birkaç pattern overlap olursa maksimum non-overlapping olan alt küme ele alınıyor. Çok fazla pattern eşleşmesini engellemek için, pattern sayısı sınırlanmış ve en son yapılan pattern ler gerektiğinde silinebilir. Bu yöntemle 48 problem çözülmüş.
Desen aramalarının maliyeti IDA* a göre daha az. Kitlenme tabloları ve desen veritabanları desen bilgilerini tutmanın farklı yolları. Bu veritabanındaki desenler küçük, bunları heasaplamak çok fazla kaynak istiyor ve ayrıca bunlar bir yerde tutulmak zorunda. - Desen araması bizi bunlardan kurtarıyor çünkü bunlar istenildiğinde oluşturuluyor.
Relevance Cuts (48 - 50 çözüm)
Bu yöntem birbirleriyle ilişkisi olmayan taşları birbirinden ayırıyor ve ayrı ayrı çözüyor. Eğer iyi bir ayrım yapabilirse bu çok büyük bir gelişme sağlar. Bu yöntem ilgisiz hareketler serisini ortadan kaldırıyor. Sadece birbiriyle ilgili hareketler yapılıyor. Birkaç istisnai durum dışında eğer bir hareket daha önceki hareketlerden etkilenmiyorsa yapılmıyor. Buda bize iyi bir çözüm sağlıyor.
Bir etkileme metriği farklı alanlarda farklı değerler veriyor. Algoritma en kısa yol algoritmasına benzer bir yolla bulunuyor, sadece burda en yakın uzaklık yerine birbirlerini etkilemeleri ele alınıyor ve "etki tablosu" (influence table) adında bir tabloda tutuluyor.
Figür 7 de birbirleriyle ilgileri olmayan iki odadaki taşlar çözülmüş. En iyi çözüm 82 imiş ve Rolling Stone un alt sınır hesaplayıcısı 70 değerini vermiş Standart IDA* sonuç bulmak için 7 iterasyona gerek duymuş. Bu problemde sadece bir parçayı çözmek (sol yada sağ) 4 iterasyon gerektiriyormuş fakat alt sınır olarak 6 değeri dönmüş. Bu problemleri iki ayrı problem olarak dönmek problemlerin arama karmaşıklığında büyük azalmalara neden olmuş.bu yöntemin transposition tabloları %25 oranında tekrarlanan pozisyonlardan kurtuluyor. Bu yöntem büyük azaltmalara neden olduğu halde bazı duzenlemelere ihtiyaç duymaktadir. Relevance cut sadece birbirini etkileyen taşlara baktığı için fazla yer kaplamıyor. Bu yöntemin eklenmesi çözülen problem sayısını 50 ye çıkarmış. Fakat bu yöntem sadece büyük aramalar için kullanilmış. Bunun nedeni yöntemin yetersiz oluşu değil diğer problemlerin çok yeterli çözümlerinin varolmasıdır.
Overestimation (54 çözüm)
A* tabanlı algoritmalarda çözüm için admissible bir tahmin gerekli. Bu tahmin de bilgi gerektiriyor. Sokoban problemlerinde tahmin her taşın hedefe olan uzaklığıydı. Bu gerçek yol ile çeliştiği için bir alt sınır fonksiyonuna ihtiyaç duyulmuş. Bu fonksiyon ne kadar iyi ise arama o kadar daha verimli oluyor.
Diğer bölümlerde çeşitli yöntemler kullanılarak (relevance cut, goal macros) kısa çözümler bulunmaya çalışıldı. Burada amaç tahmin fonksiyonunun çok yakın bir tahminde bulunması.
Overestimation tekniği bütün desen aramalarındaki desenlerin penaltılarını birleştiriyor. Ayrıntılı bilgi Appendix A10 da.
Bu yöntemle 3 fazla problem çözülmüş. Overestimation ile hemen hemen bütün problemler çözülmüş ve bazılarıda 20 milyon "node" un çok altına düşmüş. (123000 node gibi). Ortalama IDA* ve total "node" lar yarı yarıya azalmış.
Rapid Random Restart (57 çözüm)
Bazı problemler heavy tail özelliği gösterdikleri için sınıflandırılmışlar. Heavy tail özelliğinde problemin bazı algoritmalar kullanılarak çözülmesi çok zor oluyor, bunun için rastgele parametreler kullanılıyor. RRR (Rapid Random Restart) çözüm algoritmasındaki parametreleri çoğaltıp değiştirerek çözüm zamanını oldukça azaltıyor. Sadece tek parametre kullanmak yerine RRR sürekli yeni (rastgele) parametrelerle arama yapıyor. Bu yöntem kullanılarakta 90 problemin 57 tanesi çözülmüş.
SINGLE-AGENT SEARCH ENHANCEMENTS
Rolling Stone'un ilk ve son versiyonlari arasindaki performans farki sekil 8'de acik gorulmektedir. Eger transposition tablolu Rolling Stone'u en cok cozdugu program kadar program (57) cozebilmesi icin genisletiseydi 1050'lik bir ugras gerekecekti!
Bundan sonraki tartismada ilk Rolling Stone'a eklenen bu iyilestirme yontemlerinin (enhancement) hangi sirayla yapilmasi gerektigi ele alinacak.
Su ana kadarki yapilan calismalarin zamana gore grafigi sekil 9'da verilmistir. Buna gore her cozulen sorunla (bug), cozulebilen problem sayisi artmis ama bu artis giderek azalmis. Sekil 8'deki gosterim yanlis yonlendirmeler yapabilir, her iyilestirme metodu bir digerinin ustune kuruldugu icin birbirlerinden bagimsiz dusunulemezler. Nasil lower-bound metodu hicbir problemi cozemediyse, lower-bound icermeyen cozum yontemlerinin hicbiri de hicbir problemi cozemez. Ayni sekilde goal macros kaldirildiginda cozulebilir problem sayisi 33'e, pattern searchler de 22'ye, transposition tablolar da 19'a dusuyor. Yani bu yontemlerin herbiri cok degerli.
BİLGİ TAKSONOMİSİ
Domain-specific bilgi kullanimi yerine degisik bilgi siniflandirma yontemleri de kullanilabilir.
Generality: Bilginin genelligine gore siniflandirma, domain, instance ve subtree bazinda.
Computation: Bilginin elde edilme yontemine gore static(duragan) bir bilirkisiden tavsiye ya da dinamik bir arastirma sonucu elde edilen.
Admissiblity / Completeness: Bilgi tutarli yani en iyi cozumu garanti eden ya da tutarli olmayan oabilir. Tutarli olmayan bilgi algoritmanin butunlugunu saglayabilir ya da tam tersi. Ama tutarli bilgi her zaman icin tamdir.
Sekil 10'da cesitli arastirma yontemleri gosteriliyor. Bosluklar literaturden doldurulabilir. Bazi arastirma yontemleri uygulamaya gore yer degistirebilir. Ornegin overestimation static ya da dinamik; goal macros tutarli ya da tutarli olmayan; pattern databases, domain based ya da instance based olabilir.
KONTROL FONKSİYONLARI
Konrol fonksiyonlari hangi arastirma yonteminin kullanilip kullanilmayacagini ve eger kullanilacaksa na zaman kullanilacagini belirliyor. Bu nedenle cok onemlidirler.
Tranposition Table
Yeni bilginin, eski bilgiyi degistirmeye deger olup olmadigina bakiyor. Sadece tabloya bakarak degistirme maliyetiyle degistirlidiginde elde edilecek faydalari kiyasliyor.
Goal Macros
Eger bir alan cok az goal karesine sahipse ya da bircok girisi varsa, bu konudaki bir arastirmaya (goal macro kullanmaya) cok da gerek yoktur.
Pattern Searches
Sadece non-trivial heuristic fonsiyonumuz, bir ceza durumunun olabilecegini soyluyorsa kullanilir. Aslinda cok fazla islem gerektirmez. Ama cozumden uzak oldugu ve maliyetin fazla oldugu goruldugunde kontrol fonsiyonunu durduruyor.
Bazi durumlarda kontrol fonsiyonlarini uygulamak zaman alici ama kritik olabilir. Aslinda %90 kodlama eforu arastirma yontemlerine, %10'u kontrol fonsiyonlarina gidiyor.
SINGLE-AGENT SEARCH FRAMEWORK
Single agent arastirma yontemleri (genellikle IDA*'la) birkac satir kod gerektirir. Bunun yaninda dogrudan gorulemeyen single agent arastirma yontemi gerektiren problemler, cok daha fazla arastirma ve efor gerektirir.
Sekil 11'de temel IDA* yontemi ve bu arastirma raporunda bahsedilen gelistirme yontemleri veriliyor. Bu kodda aslinda sadece 3 arastirma yontemi bulunuyor:
- Alt siniri degistirmek: iki sekilde yapilabilir; alt siniri optimal olarak artirarak (pattern kullanarak) ki bu arastirilan uzakligi azaltiyor, ya da overestimation yaparak.
- Katkida bulunma olasiligi az olan dallari yok etmek. Bu, arama agacinda buyuk azaltmalarla sonuclanabilirse de butunlugu bozar.
- Agac boyutunu azaltmak, bir dizi hareketi tek bir hareket olarak (macrolarla) degistirmek.
Bazi arastirma yontemleri, sekil 12'de gosterlidigi gibi domain ve instance basamaklarinda oncul arastirma yapar.
Alpha-beta algoritmasinin tanimlanmasi sadece birkac satir alsa da Deep Blue satranc programinin cok cesitli ve arama agacinin boyutunu kuculten arastirma yontemleri vardir.
Sekil 13'te de problem cozum ve bu cozum icin kullanilan bilgilerin hierarsisi gosteriliyor.
Kaynak
SOKOBAN'DA HARİTA ÜRETME
Benim okudugum yazi Sokoban'da harita ureten ve bu haritayı sınıflndıran bir pogramdan bahsediyor. Program üc asamada calısıyor. Pogramın calısma asamalarıına gecmeden once bazı terimleri acıklıga kavusturalım.
- Passway: iki kareyi birbirine baglayan yer,
- Goal_Avoid: Hamalın sandıkları tasıyamayacagı yerler
- Dead_end_area (Add_Avoid): Hamalın sandıgı kımıldatamayacagı yerler,orn:koseler,
- Corner_Goal: Sandıkların bitme durumunun koselerde olması,
- Goal_range: bir tane sandıgın herbir bıtıs durumundan gidebileegi yerler.
- Haritayı Uretme: n*n lik bir hartaya oncelikle duvarlar yeni olusan bolumlerin baglantısın kesmeyecek sekılde, sekilde rasgele yerlestiriliyor.Daha sonra bitme durumlari "goal_avaoid"lerin usutunde olmayacak sekilde belirleniyor.Son olarak da sandıklar, "goal_range"in icinde olacak sekilde ama "dead end_arealar"ı kapsamayacak sekilde yerlestiriliyor.Her sandık yerlestirildikten sonra "goal_avoid" "goal_range" ve "dead_end_arealar" tekrar hesaplanıyor
- Kontrol: Uretilen haritaların cozulebilirliginin kontrol edildigi asama. Program bunu "breadth_first_search" ile gerceklestiriyor, boylelikle cozumu fazla uzun olmayan haritaları kolayca kontrol edebiliyor ama cozumu uzun olanlar icin sonuca ulasamıyor.Kontrol asamasından sonra uretilen haritalrın yaklasik yarısı cozumleri olmadıgı icin eleniyor.
- Sınıflandırma: Bu asamada program onceden belirlenmis bazı
kriterlere gore cozumu olan haritalari sınıflandırıyor.Bu kriterler
- Cozumu yedi hamleden daha az olan haritalar kolay olarak adlandırılıyor ve program tarafından eleniyor.
- Eger sandıklar tasınırken dort yonde de ilerletilerek cozume ulasılmazsa,yine cozum kolay olarak nitelendiriliyor ve eleniyor.
- Belli bir harita icin sadece tek bir cozum varsa bu harita da kolay olarak nitelendiriliyor.
Sınıflandırma asamasını gecen haritalar program tarafından "zor haritalar" kategorisine konuyor, bu haritaların da yaklasık dortte biri bu oyunun ustaları tarafından "zor" olarak nitelendiriliyor.
Deneysel Veriler:
| Uretilen harita sayısı | 500 |
| Uretırken elenen harita sayısı | 7 |
| Cozumu olmayan harıta sayısı | 245 |
| Program tarafından kolay diye adlandırılan | 204 |
| Program tarafından iyi diye adlandırılan | 44 |
| Oyunun ustalarının begendıgı harita sayısı | 14 |