2048 Oyununu (JAVA kodu) çözmek için Yapay Zekayı Kullanma

• 7 Nisan 2014
• Vasilis Vryniotis
• . 6 Yorumlar

Şimdiye kadar çoğunuz 2048 oyunu Gabriele Cirulli tarafından. 2048 sayısına ulaşmak için hücrelerin sayılarını birleştirmenizi gerektiren basit ama oldukça bağımlılık yapan bir tahta oyunudur. Beklendiği gibi, daha fazla hücre yüksek değerlerle dolduğunda oyunun zorluğu da artar. Şahsen, oyunu oynayarak oldukça fazla zaman geçirmeme rağmen, hiçbir zaman 2048'e ulaşamadım. Yani yapılacak doğal şey, 2048 oyununu yenmek için JAVA'da bir AI çözücü geliştirmeye çalışmaktır. 🙂

Bu yazıda, Game 2048'in Yapay Zeka Çözücüsünü oluşturma yaklaşımımı kısaca tartışacağım, kullandığım sezgisel yöntemleri açıklayacağım ve JAVA'da yazılan kodun tamamını sağlayacağım. Kod, GPL v3 lisansı altında açık kaynaklıdır ve şu adresten indirebilirsiniz: Github.

JAVA'da 2048 Oyunu Geliştirmek

Orijinal oyun JavaScript ile yazılmış, bu yüzden onu JAVA ile sıfırdan yeniden yazmak zorunda kaldım. Oyunun ana fikri, tümü 4'nin katları olan Tamsayı değerlerine sahip 4 × 2 bir ızgaraya sahip olmanızdır. Sıfır değerli hücreler boş kabul edilir. Oyun sırasında her noktada değerleri 4 yöne Yukarı, Aşağı, Sağa veya Sola doğru hareket ettirebilirsiniz. Bir hareket yaptığınızda, ızgaranın tüm değerleri o yöne doğru hareket eder ve ızgaranın sınırlarına ulaştıklarında veya sıfır olmayan başka bir hücreye ulaştıklarında dururlar. Önceki hücre aynı değere sahipse, iki hücre çift değerli tek bir hücre olarak birleştirilir. Her hareketin sonunda boş hücrelerden birine tahtaya rastgele bir değer eklenir ve değeri 2 olasılıkla 0.9 veya 4 olasılıkla 0.1'tür. Oyun, oyuncu 2048 (kazan) değerine sahip bir hücre oluşturmayı başardığında veya yapacak başka hamle olmadığında (kaybedecek) sona erer.

Oyunun orijinal uygulamasında, hareket-birleştirme algoritması biraz karmaşıktır çünkü tüm yönleri hesaba katar. Taşları birleştirebileceğimiz yönü sabitlersek ve hareketi gerçekleştirmek için tahtayı buna göre döndürürsek, algoritmanın güzel bir basitleştirmesi yapılabilir. Maurits van der Schee geçenlerde incelemeye değer olduğuna inandığım bir makale yazdı.

Tüm sınıflar Javadoc yorumlarıyla belgelenmiştir. Aşağıda, uygulama mimarisinin üst düzey bir tanımını sunuyoruz:

1. Yönetim Kurulu Sınıfı

Tahta sınıfı, taşları hareket ettirmekten, skoru hesaplamaktan, oyunun sonlandırılıp sonlandırılmadığını doğrulamaktan sorumlu olan oyunun ana kodunu içerir.

2. ActionStatus ve Direction Enum

ActionStatus ve Direction, bir hareketin sonucunu ve buna göre yönünü depolayan 2 temel numaralandırmadır.

3. ConsoleGame Sınıfı

ConsoleGame, oyunu oynamamıza ve AI Çözücünün doğruluğunu test etmemize izin veren ana sınıftır.

4. AIsolver Sınıfı

AIsolver, belirli bir Kurul verilen bir sonraki en iyi hareketi değerlendirmekten sorumlu olan Yapay Zeka modülünün birincil sınıfıdır.

Yapay Zeka Teknikleri: Minimax vs Alpha-beta budama

Bu oyunu otomatik olarak çözmek için çeşitli yaklaşımlar yayınlanmıştır. En dikkate değer olanı, Matt Overlan. Sorunu çözmek için Minimax algoritması ve Alpha-beta budama kullanarak iki farklı yaklaşım denedim.

Minimax Algoritması

The Minimax iki oyunculu sıfır toplamlı oyunları çözmek için kullanılabilen özyinelemeli bir algoritmadır. Oyunun her durumunda bir değeri ilişkilendiririz. Minimax algoritması, belirli bir önceden tanımlanmış derinliğe ulaşana kadar genişleyen bir ağaç oluşturarak olası oyun durumlarının uzayında arama yapar. Bu yaprak durumlarına ulaşıldığında, değerleri ara düğümlerden olanları tahmin etmek için kullanılır.

Bu algoritmanın ilginç fikri, her seviyenin iki oyuncudan birinin sırasını temsil etmesidir. Kazanmak için her oyuncunun rakibin maksimum getirisini en aza indiren hamleyi seçmesi gerekir. İşte minimax algoritmasının güzel bir video sunumu:

[Gömülü içerik]

Aşağıda Minimax Algoritmasının sözde kodunu görebilirsiniz:

işlev minimax (düğüm, derinlik, maksimize etmePlayer)
    if derinlik = 0 or düğüm bir terminal düğümüdür
        dönüş düğümün sezgisel değeri
    if maximizingPlayer bestValue: = -∞
        her biri için düğümün alt öğesi: = minimax (çocuk, derinlik - 1, YANLIŞ)) bestValue: = max (bestValue, val);
        dönüş En iyi değeri
    başka
        bestValue: = + ∞
        her biri için düğümün alt öğesi: = minimax (çocuk, derinlik - 1, DOĞRU)) bestValue: = min (bestValue, val);
        dönüş En iyi değeri
(* Oyuncuyu büyütmek için ilk çağrı *)
minimax (başlangıç, derinlik, DOĞRU)

Alfa beta budama

The Alfa-beta budama algoritması değerlendirmemiz / genişletmemiz gereken düğüm sayısını büyük ölçüde azaltan (eriten) bir minimax genişlemesidir. Bunu başarmak için, algoritma alfa ve beta olmak üzere iki değeri tahmin eder. Belirli bir düğümde beta, alfadan küçükse, alt ağaçların geri kalanı budanabilir. Alfabea algoritmasının güzel bir video sunumu:

[Gömülü içerik]

Aşağıda Alfa-beta budama Algoritmasının sözde kodunu görebilirsiniz:

işlev alfabea (düğüm, derinlik, α, β, maximizingPlayer)
    if derinlik = 0 or düğüm bir terminal düğümüdür
        dönüş düğümün sezgisel değeri
    if maksimize etmeOyuncu
        her biri için düğümün çocuğu α: = max (α, alphabeta (çocuk, derinlik - 1, α, β, YANLIŞ))
            if β ≤ α
                kırılma (* β kesme *)
        dönüş α
    başka
        her biri için düğümün çocuğu β: = min (β, alphabeta (çocuk, derinlik - 1, α, β, DOĞRU))
            if β ≤ α
                kırılma (* α kesme *)
        dönüş β
(* İlk çağrı *)
alfabea (başlangıç, derinlik, -∞, + ∞, DOĞRU)

Oyun 2048'i çözmek için AI nasıl kullanılır?

Yukarıdaki algoritmaları kullanmak için önce iki oyuncuyu tanımlamalıyız. İlk oyuncu oyunu oynayan kişidir. İkinci oyuncu, tahta hücrelerine rastgele değerler ekleyen bilgisayardır. Açıkçası, ilk oyuncu puanını en üst düzeye çıkarmaya ve 2048 birleşimini elde etmeye çalışıyor. Öte yandan, orijinal oyundaki bilgisayar, kullanıcı için olası en kötü hamleyi seçerek engelleyecek şekilde özel olarak programlanmamıştır, bunun yerine boş hücrelere rastgele değerler ekler.

Öyleyse neden sıfır toplamlı oyunları çözen ve özellikle her iki oyuncunun da onlar için mümkün olan en iyi hamleyi seçtiğini varsayan AI tekniklerini kullanıyoruz? Cevap basit; Skorunu en üst düzeye çıkarmaya çalışan sadece ilk oyuncu olmasına rağmen, bilgisayarın seçimleri ilerlemeyi engelleyebilir ve kullanıcının oyunu tamamlamasını durdurabilir. Bilgisayarın davranışını ortolojik rastgele olmayan bir oyuncu olarak modelleyerek, seçimimizin bilgisayarın oynadığından bağımsız olarak sağlam olmasını sağlıyoruz.

İkinci önemli kısım, oyunun durumlarına değerler atamaktır. Bu problem nispeten basit çünkü oyunun kendisi bize bir puan veriyor. Ne yazık ki puanı tek başına maksimize etmeye çalışmak iyi bir yaklaşım değil. Bunun bir nedeni, değerlerin konumu ve boş değerli hücrelerin sayısının oyunu kazanmak için çok önemli olmasıdır. Örneğin, büyük değerleri uzak hücrelere dağıtırsak, onları birleştirmemiz gerçekten zor olur. Ayrıca boş hücremiz yoksa, oyunu her an kaybetme riskimiz vardır.

Yukarıdaki tüm nedenlerden dolayı, birkaç buluşsal yöntem önerildi Monoticity, tahtadaki pürüzsüzlük ve Free Tiles gibi. Ana fikir, puanı tek başına her bir oyun durumunu değerlendirmek için kullanmak değil, bunun yerine yukarıda belirtilen puanları içeren sezgisel bir bileşik puan oluşturmaktır.

Son olarak, Minimax algoritmasının bir uygulamasını geliştirmiş olmama rağmen, çok sayıda olası durumun algoritmayı çok yavaşlattığını ve bu nedenle budamanın gerekli olduğunu not etmeliyiz. JAVA uygulamasının bir sonucu olarak, Alpha-beta budama algoritmasının genişlemesini kullanıyorum. Ek olarak, diğer uygulamalardan farklı olarak, keyfi kurallar kullanarak bilgisayarın seçimlerini agresif bir şekilde budamıyorum, bunun yerine oyuncunun mümkün olan en iyi hamlesini bulmak için hepsini hesaba katıyorum.

Sezgisel bir puan işlevi geliştirme

Oyunu yenmek için birkaç farklı sezgisel işlev denedim. En yararlı bulduğum şey şudur:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

Yukarıdaki işlev, panonun gerçek puanını, boş hücre / parçaların sayısını ve daha sonra tartışacağımız kümeleme puanı adı verilen bir ölçüyü birleştirir. Her bileşeni daha ayrıntılı olarak görelim:

1. Gerçek Puan: Açık nedenlerden dolayı, bir panonun değerini hesaplarken puanını hesaba katmalıyız. Daha yüksek puana sahip panolar, genellikle daha düşük puanlı panolara göre tercih edilir.
2. Boş Hücre Sayısı: Daha önce de bahsettiğimiz gibi, sonraki hamlelerde oyunu kaybetmememiz için birkaç boş hücre tutmak önemlidir. Daha fazla boş hücreye sahip pano durumları, genellikle daha az hücreye sahip olanlara göre tercih edilir. Bu boş hücrelere nasıl değer veririz diye bir soru ortaya çıkıyor? Çözümümde, onları gerçek puanın logaritmasına göre ağırlıklandırıyorum. Bu, aşağıdaki etkiye sahiptir: Puan ne kadar düşükse, çok sayıda boş hücreye sahip olmak o kadar az önemlidir (Bunun nedeni, oyunun başında hücreleri birleştirmenin oldukça kolay olmasıdır). Skor ne kadar yüksekse, oyunumuzda boş hücrelerimizin olmasını sağlamak o kadar önemlidir (Bunun nedeni, oyunun sonunda boş hücre eksikliğinden dolayı kaybetme olasılığının daha yüksek olmasıdır.
3. Kümeleme Puanı: Kurulumuzun değerlerinin ne kadar dağınık olduğunu ölçen kümeleme skorunu kullanıyoruz. Benzer değerlere sahip hücreler birbirine yakın olduğunda, birleştirmeleri daha kolaydır, yani oyunu kaybetmek daha zordur. Bu durumda kümeleme puanı düşük bir değere sahiptir. Tahtanın değerleri dağınıksa bu puan çok büyük bir değer alır. Bu puan, önceki iki puandan çıkarılır ve kümelenmiş tahtaların tercih edilmesini sağlayan bir ceza görevi görür.

Fonksiyonun son satırında puanın negatif olmamasını sağlıyoruz. Skor, yönetim kurulunun puanı pozitifse kesinlikle pozitif ve yalnızca puanın panosu sıfır olduğunda sıfır olmalıdır. Max ve min fonksiyonları, bu etkiyi elde etmemiz için oluşturulmuştur.

Son olarak, oyuncu bir terminal oyun durumuna ulaştığında ve daha fazla hamle yapılmasına izin verilmediğinde, durumun değerini tahmin etmek için yukarıdaki puanı kullanmadığımızı not etmeliyiz. Oyun kazanılırsa, mümkün olan en yüksek tamsayı değerini atarken, oyun kaybedilirse en düşük negatif olmayan değeri (önceki paragrafta olduğu gibi benzer mantıkla 0 veya 1) atarız.

Kümeleme Puanı hakkında daha fazla bilgi

Daha önce de söylediğimiz gibi, kümeleme puanı, panonun değerlerinin ne kadar dağınık olduğunu ölçer ve bir ceza gibi davranır. Bu skoru, oyunda "ustalaşan" kullanıcıların ipuçlarını / kurallarını içerecek şekilde oluşturdum. Önerilen ilk kural, benzer değerlere sahip hücreleri daha kolay birleştirmek için yakın tutmaya çalışmanızdır. İkinci kural, yüksek değerli hücrelerin birbirine yakın olması ve tahtanın ortasında değil, yanlarda veya köşelerde görünmesidir.

Kümeleme puanının nasıl tahmin edildiğini görelim. Kurulun her hücresi için komşularından (boş hücreler hariç) mutlak farklılıkların toplamını tahmin ediyoruz ve ortalama farkı alıyoruz. Ortalamaları almamızın nedeni, iki komşu hücrenin etkisini birden fazla kez saymaktan kaçınmaktır. Toplam kümeleme puanı, tüm bu ortalamaların toplamıdır.

Kümeleme Puanı aşağıdaki özelliklere sahiptir:

1. Pano değerleri dağıldığında yüksek, benzer değerlere sahip hücreler birbirine yakın olduğunda düşük değer alır.
2. İki komşu hücrenin etkisine ağır basmaz.
3. Kenar boşluklarındaki veya köşelerdeki hücrelerin daha az komşusu vardır ve bu nedenle daha düşük puanlar vardır. Sonuç olarak, yüksek değerler kenar boşluklarına veya köşelere yakın yerleştirildiğinde puanları daha düşüktür ve dolayısıyla ceza daha küçüktür.

Algoritmanın doğruluğu

Beklendiği gibi, algoritmanın doğruluğu (diğer bir deyişle kazanılan oyunların yüzdesi), kullandığımız arama derinliğine büyük ölçüde bağlıdır. Aramanın derinliği ne kadar yüksekse, doğruluk o kadar yüksek ve çalışması için o kadar çok zaman gerekir. Testlerimde, derinliği 3 olan bir arama 0.05 saniyeden az sürer ancak% 20 kazanma şansı verir, 5 derinliği yaklaşık 1 saniye sürer ancak% 40 kazanma şansı verir ve son olarak 7 derinliği 27-28 saniye sürer ve yaklaşık% 70-80 kazanma şansı verir.

Gelecekteki açılımlar

Kodu iyileştirmekle ilgilenenler için burada inceleyebileceğiniz birkaç şey var:

1. Hızı Artırın: Algoritmanın hızını artırmak, daha büyük derinlik kullanmanıza ve böylece daha iyi doğruluk elde etmenize olanak tanır.
2. Grafik Oluşturun: Gabriele Cirulli'nin uygulamasının bu kadar ünlü olmasının iyi bir nedeni var. Güzel görünüyor! Bir GUI geliştirmeyi zahmet etmedim, ancak sonuçları konsola yazdırmayı tercih ediyorum, bu da oyunun takip edilmesini ve oynanmasını zorlaştırıyor. Güzel bir GUI oluşturmak bir zorunluluktur.
3. Sezgisel Ayarlama: Daha önce bahsettiğim gibi, birkaç kullanıcı farklı sezgisel yöntemler önerdi. Puanların hesaplanma şekli, ağırlıkları ve dikkate alınan tahta özellikleri ile deneyler yapılabilir. Küme puanını ölçme yaklaşımımın Monotonluk ve Düzgünlük gibi diğer önerileri birleştirmesi gerekiyor, ancak yine de iyileştirme için yer var.
4. Derinliği Ayarlama: Oyun durumuna bağlı olarak arama derinliğini de ayarlamaya / ayarlamaya çalışabilirsiniz. Ayrıca şunu da kullanabilirsiniz: Yinelemeli derinleşme derinlik arama alfa-beta budama algoritmasını geliştirdiği bilinen algoritma.

JAVA kodunu şuradan indirmeyi unutmayın: Github ve deney. Umarım bu gönderiyi beğenmişsinizdir! Yaptıysanız, lütfen makaleyi Facebook ve Twitter'da paylaşmak için bir dakikanızı ayırın. 🙂