Yenilmez Genetik Algoritma

The source-page: http://www.tropicalcoder.com/GeneticAlgorithm.htm

DNA molecule
Paul Thiessen‘in izniyle DNA görüntüsü (Görüntüyü değiştirdim – orijinaller çok güzel. Bir göz atın!)

Genetik algoritmalarla oynamayı – onların büyümesini ve gelişmesini izlemekten zevk alıyorum. Her zaman engelleri aşarken ekranımın etrafında dolaşıp yiyecek arayan organizmaları gerektiren deneylerimde, büyük medeniyetlerin büyüyüp çürümesine hayran kaldım. Biyologların muhtemelen onlarca yıldır bildiği pek çok temel ilkeyi ve belki de olmayan birkaçını yeniden keşfettim.

Bir gün basit bir oyunda ustalaşmak için bir genetik algoritmanın gelişip gelişmeyeceği konusunda spekülasyon yaptım. Belki TicTacToe oyununun başlamak için iyi bir deney olabileceğini düşündüm. Yıllar önce denediğim bir analizden bunun basit bir iş olmayabileceğini biliyordum. Hiç oturup oyunu analiz etmeye çalıştınız mı? Oyun tahtasının küçük diyagramlarını çizmeye başlıyorsunuz, bunlar çok geçmeden oyunun tüm olası permütasyonlarına rağmen çalıştıkça üssel olarak büyüyen ağaçlara dönüşüyor. Masanız artık takip edemeyeceğiniz küçük diyagramlarla dolduğu için muhtemelen kısa sürede pes edeceksiniz. Yaptım. Hayat çok kısa!

Oyunu analiz etme görevini otomatikleştirmenin bir yolu olması gerektiği aklıma geldi. Rastgele hamleler yaparak birbirimizle oyun oynamak için küçük algoritmalar yazdım. Buradaki fikir, milyonlarca oyun oynadıklarında, sonunda oyunun olası her permütasyonunu oynayacaklardı. Oluşturulan her pano pozisyonunu yakalamam, geliştirme tablosunda zaten bir kopyası olup olmadığını görmek için bakmam, yoksa tabloya eklemem gerekiyor. Sonunda, olası her durumu temsil eden bir masam olacaktı. Ancak başlamadan önce, karmaşıklığı daraltmak için birkaç basit kuralı düşündüm.

Her hamlede, bir ‘filtre’nin mevcut oyuncunun bakış açısından tahtayı analiz etmesine ve onun için bariz bir galibiyet modelini tamamlamasına veya rakibinin bariz bir kazanma girişimini engellemesine karar verdim. Böylesine önemsiz bir görevin organizmanın bir parçası olmayacağına karar verdim; bunun yerine öğrenmesi çok daha zor bir beceriye sahip olacaktı – strateji. Masaları ikiye böldüm. X oyuncusunu her zaman ilk hareket eden kişi olarak atadım ve ilk hamlesini bekleyen boş bir tahta ile başlayarak, kendisine sunulabilecek her olası tahtadan oluşan bir masaya sahip olacaktı. Aynı şeyi, üzerinde tek bir X bulunan bir tahtadan başlayarak karşılaşabileceği her pozisyonun bir veritabanını geliştirecek olan O için de yaptım.

Son olarak, olası panoların sayısını daraltmak için, aynı kartın uzayda döndürülmesinden kaynaklanan kopyaları ortadan kaldırmak için her bir karşılaştırma sırasında gerektiği gibi her kartı döndürmek ve/veya ‘yansıtmak’ için kod geliştirdim.

Artık görevi yönetilebilir bir boyuta indirdiğime göre, gerekirse binlerce tahtayı tutacak masalar ayırdım ve oyunların başlamasına izin verdim. Bu ‘kaba kuvvet’ algoritmasını bir milyon oyun için çalıştırdım ve sonunda, yukarıda belirtilen kurallar altında, X’in yanıt verebilmesi gereken yalnızca 57 olası ‘pano’ olduğunu keşfetmeye şaşırdım ve O’nun karşılaşacağı sadece 38 olası pano. Bu hayal ettiğimden çok daha basitti!

Yinelemeleri ortadan kaldırmak için kartı gerektiği gibi döndürür ve/veya yansıtırsanız, X’in ilk hareket için yalnızca 3 benzersiz seçeneği vardır. Bir köşe hamlesi, bir yan hamle oynayabilir veya merkezi alabilir. 2. hamlede 7 seçeneği, 3. hamlede 5, 4. hamlede 3 seçeneği ve 5. hamlede sadece bir seçeneği olduğunu keşfettim. O zaman 3 * 7 * 5 * 3 * 1 = 315 olası oyun için bir üst limit belirleyebiliriz, ancak gerçekte bu olası yolların sadece küçük bir kısmı birkaç hareketin ötesine geçebilir. Birçok yol oyunun erken sonlandırılmasına yol açar ve diğerleri, döndürüldüğünde veya uzaya yansıtıldığında aynı konumlara götürür. Tüm bariz kazançları veya engellemeye yönelik bariz ihtiyaçları filtrelemek, veritabanındaki diğer birçok konumu ortadan kaldırır. Sonunda, son derece gelişmiş bir organizmanın karşılaşabileceği her durumu yalnızca 17 pano kadar az kapladığını buldum.

9 kareden oluşan oyun tahtasının kendisi, 9 öğeli basit tek boyutlu bir diziye atandı. Bu karelerin gerçek dünyada nasıl yerleştirildiği algoritma için önemli değildi. Yalnızca kendisine verilen belirli bir modele uygun bir yanıt geliştirebilmesi önemliydi, bu, sunulan modele yanıt olarak hareketini temsil eden 0’dan 8’e kadar bir sayıdır.

Artık oyunu oynamak için genetik algoritmalar oluşturmak mümkündü. X oyuncusu 57 “gen” e, gerçekte her biri 0’dan 8’e kadar bir değer alabilen 57 öğeden oluşan basit tek boyutlu bir diziye, herhangi bir oyunda karşılaşabileceği 57 olası durumdan oluşan veri tablosu ile birlikte sahip olacaktır.

Bir algoritma, tablosundaki mevcut tahta konumuna bakacaktır. Bulunduğunda, tahta masasındaki konumunun indeksi, cevabına bakmak için gen tablosunun indeksi olur. Benzer şekilde, O oyuncu algoritması, bir oyunda karşılaşabileceği 38 olası durumun bir tablosuna ve 38 genlik bir diziye sahip olacaktır. -İşte- bir örnek. Artık nihayet tic tac toe oyuncuları medeniyetini geliştirmeye başlayabiliriz.

O zaman başlamak için bin oyuncudan oluşan bir dizim vardı. Bu 1000 oyuncunun her birine, her gen için rastgele (yasal) bir değer atandı, tahtadaki boş karelerden birine geçme seçimi. X oyuncuları veya O oyuncuları ayrı ayrı geliştirdim. Hangi oyuncu olursa olsun, rastgele sayı üretecine karşı oynadı.

1000 organizmanın her biri 1000 oyun oynar ve bir puan toplar. Gelecek neslin babaları olmak için sadece en iyi 10 oyuncu seçildi. Bu en iyi 10 oyuncunun her birinin 99 çocuğu var. Bu yavruların her biri, genlerinden birine karşı tek bir rastgele mutasyona uğrar (yine de deneyimlerime göre, az sayıda birden fazla mutasyon vermenin işe yaradığını öğrendim). Şimdi, ilk 10 kazanan ve tüm mutant yavrularından oluşan yepyeni bir nesli test ediyoruz. Bu yeni neslin her biri bin oyun oynuyor, ardından bir kez daha en iyi 10 oyuncu sonraki neslin babaları oluyor.

Seyretmek ne harikaydı! 6 ila 10 nesil içinde zirveye ulaştılar ve her galibiyet, beraberlik veya mağlubiyet için verilen puanları denemeye başladım. Bir galibiyet için 1 puan, beraberlik için 0 puan ve mağlubiyet için -1 puan alırlarsa, şaşırtıcı bir oranda kazanmayı artırmak için geliştiklerini keşfettim. İki oyuncu arasındaki rastgele hamleler yapan oyunlarda, X (her zaman önce gitmesi için atadığım) her zaman O’ya karşı 2’ye 1 kazanır. Açıkçası ilk hamleyi yapmak güçlü bir avantajdır. Bununla birlikte, organizmalarım birkaç nesil evrimleştiğinde, O, X’i 12’ye 1 oranında yeniyordu (X, engellemediğinde veya basit kazançlar almadığında rastgele hareketler yapıyor)

Bu ilk başarının ardından, asla kaybetmeyen organizmaları evrimleştirip geliştiremeyeceğimi merak ettim. Bu çabayı, her mağlubiyet için 100 puan düşürmek gibi, büyük ölçüde kaybetmenin cezasını artırarak başardım. Birkaç nesil sonra artık kimse bir oyun kaybetmedi. Ancak galibiyet sayısı da önemli ölçüde düştü.

Organizmalarımdan mümkün olan en iyi performansı elde etmek için doğru ödül ve ceza oranını keşfettim: onları her galibiyet için 1 puan ve her kayıp için yaklaşık negatif 6 veya 7 puan ödüllendirmek.

Sonuçlardan çok memnun kaldım. Sadece şampiyon oyunculardan oluşan bir ırk geliştirmekle kalmadım, oynamayı öğrendikleri şey stratejiydi. Unutmayın, tüm basit kazançlar veya bloklar, organizmalara ulaşmadan önce filtrelendi ve rakiplerine ayrıca rastgele bir hamle oluşturmadan önce basit bir galibiyeti hatasız bir şekilde engelleme veya kendi basit galibiyetlerini oynama yeteneği verildi.

Genetik organizmaların, rakiplerinin korkulu ‘iki yönlü bölünme’ gibi bir tuzak kurmasını engelleyebilmek için birden fazla ileriyi ‘tahmin etme’ kapasitesine sahip olması gerektiği söylenebilir. onları. Elbette kendi tuzaklarını kuracak kadar ileriyi ‘düşünebilmeliler’, yoksa asla kazanamazlardı. Rakiplerine her zaman basit bir galibiyeti bloke etme yeteneği verildiğinden, bir oyunu kazanmanın tek yolu, en az bir hamle önceden stratejik bir oyun oluşturmaktı.

Artık yenilmez bir organizmam vardı, şampiyonların şampiyonu. Onunla ne yapabilirim? Belki de, gagalamak için 9 kollu bir Skinner kutusuna bir güvercin koyabiliriz. Sunulan tahta desenine yanıt olarak doğru kolu gagalarsa, bir mısır tanesi ile ödüllendirilecek ve sonunda TicTacToe oynamayı öğrenecekti. Ya da eğitmek için kullanabilirim -TicTacToe oynayan bir Sinir Ağı-!