Soru Oyun 2048 için en uygun algoritma nedir?


Son zamanlarda oyuna katıldım 2048. "Daha büyük" fayans yapmak için dört yönden herhangi birine hareket ederek benzer fayansları birleştirirsiniz. Her hareketinden sonra, rastgele boş konumda yeni bir karo ya da 2 veya 4. Oyun tüm kutular doldurulduğunda sona erer ve fayansları birleştirebilecek herhangi bir hamle olmaz ya da bir değere sahip bir karo oluşturursunuz. 2048.

Bir, hedefe ulaşmak için iyi tanımlanmış bir strateji izlemem gerekiyor. Bu yüzden bunun için bir program yazmayı düşündüm.

Mevcut algoritmam:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Yaptığım şey herhangi bir noktada fayansları değerlerle birleştirmeye çalışacağım 2 ve 4yani sahip olmaya çalışıyorum 2 ve 4 fayans, mümkün olduğunca az. Bu şekilde denersem, diğer tüm karolar otomatik olarak birleştirildi ve strateji iyi görünüyor.

Ancak, bu algoritmayı kullandığımda, oyun bitmeden sadece yaklaşık 4000 puan alırım. Maksimum puan AFAIK, şu anki skorumdan çok daha büyük olan 20.000'den biraz daha fazla. Yukarıdakilerden daha iyi bir algoritma var mı?


1755
2018-03-12 05:37


Menşei


Bu yardımcı olabilir! ov3y.github.io/2048-AI - cegprakash
@ nitish712 bu arada, algoritmanız sizin açınızdan beri açgözlüdür choose the move with large number of merges hangi hızla yerel optima yol açar - Khaled.K
@ 500-InternalServerError: Eğer ben alfa-beta oyun ağacı budama ile bir AI uygulamak vardı, yeni bloklar olumsuz olarak yerleştirilmiş varsayılmaktadır. Bu en kötü durum varsayımıdır, ancak yararlı olabilir. - Charles
Yüksek puanı hedeflemek için zamanınız olmadığında eğlenceli bir dikkat dağıtıcı: Mümkün olan en düşük puanı almaya çalışın. Teorik olarak 2s ve 4s değişiyor. - Mark Hurd
Bu sorunun meşruluğu üzerine tartışma meta üzerinde bulunabilir: meta.stackexchange.com/questions/227266/... - Jeroen Vannevel


Cevaplar:


Kullanarak bir 2048 AI geliştirdim expectimax @ ovolve'nin algoritması tarafından kullanılan minimax araması yerine optimizasyon. AI, tüm olası hareketler üzerinde maksimuma çıkar, ardından tüm muhtemel kiremit yumruları üzerinde beklenti (fayansların olasılığına göre ağırlıklandırılır, yani% 10 ve 2 için% 90). Bildiğim kadarıyla, beklenmedik optimizasyonu (son derece olası olmayan dalların çıkarılması hariç) ayarlamak mümkün değildir ve kullanılan algoritma, dikkatle optimize edilmiş bir kaba kuvvet araştırmasıdır.

performans

AI, varsayılan konfigürasyonunda (maksimum 8 arama derinliği), levha konumunun karmaşıklığına bağlı olarak, bir hareketi yürütmek için 10 ms'den 200 ms'ye kadar her yerde alır. Testte, AI tüm oyun boyunca saniyede 5-10 hamle ortalama bir hareket hızı elde eder. Eğer arama derinliği 6 hamle ile sınırlanmışsa, AI saniyede 20+ hamle yapabilir, bu da bazılarını yapar. ilginç izleme.

AI'nın skor performansını değerlendirmek için AI'yı 100 kez çalıştırdım (tarayıcı kontrolüne uzaktan kumanda ile bağlı). Her bir karo için, bu döşemenin en az bir kez elde edildiği oyunların oranları şunlardır:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

Tüm koşularda minimum puan 124024'tü; elde edilen maksimum puan 794076 idi. Ortanca skor 387222'dir. AI 2048 kiremitini elde edemedi (bu yüzden 100 oyunda bir kez bile oyunu kaybetmemişti); Aslında, 8192 her koşuda en az bir kez kiremit!

İşte en iyi koşunun ekran görüntüsü:

32768 tile, score 794076

Bu oyun 968 saniyede 27830 hamle ya da saniyede 4,8 hamle yaptı.

uygulama

Benim yaklaşımım, tüm kartı (16 giriş) tek bir 64-bit tam sayı olarak kodlar (çini çengeller, yani 4-bit parçalar). 64 bitlik bir makinede bu, tüm kartın tek bir makine kaydında geçirilebilmesini sağlar.

Bit kaydırma işlemleri, tek tek satır ve sütunları ayıklamak için kullanılır. Tek bir satır veya sütun 16 bitlik bir miktardır, bu nedenle 65536 boyutundaki bir tablo, tek bir satır veya sütun üzerinde çalışan dönüşümleri kodlayabilir. Örneğin, hareketler, her hareketin tek bir satırı veya sütunu nasıl etkilediğini açıklayan önceden hesaplanmış bir "hareket efekti tablosuna" 4 arama olarak uygulanır (örneğin, "sağa doğru" tablosu, "1122 -> 0023" girişini içerir. satır [2,2,4,4] sağa hareket ettirildiğinde satır [0,0,4,8] olur.

Puanlama da tablo araması kullanılarak yapılır. Tablolar, olası tüm satır / sütunlarda hesaplanan sezgisel puanları içerir ve bir tahta için elde edilen sonuç, her satır ve sütundaki tablo değerlerinin toplamıdır.

Bu pano temsili, hareket ve puanlama için tablo arama yaklaşımı ile birlikte, AI'nın kısa bir süre içinde çok sayıda oyun durumunu (2011 ortalarındaki dizüstü bilgisayarımın bir çekirdeğinde saniyede 10.000.000 oyun durumu) aramasına olanak tanır.

Expectimax araştırmasının kendisi, “beklenti” adımları (tüm muhtemel kiremit yumurtlama konumlarını ve değerlerini test etme ve bunların her bir olasılığa göre optimize edilmiş puanlarını ağırlıklandırma) ve “maksimizasyon” aşamaları (tüm olası hareketleri test etme) arasında değişen bir özyinelemeli arama olarak kodlanır. ve en iyi skoru olanı seçerek). Ağaç araması, daha önce görüldüğü bir pozisyonu gördüğü zaman sona erer ( transpozisyon tablosuÖnceden belirlenmiş bir derinlik sınırına ulaştığında veya yüksek olasılıklı olmayan bir levha durumuna ulaştığında (örneğin, başlangıç ​​pozisyonundan bir sıraya 6 "4" karo elde etmek suretiyle ulaşıldı). Tipik arama derinliği 4-8 hamledir.

Sezgiseller

Optimizasyon algoritmasını uygun pozisyonlara yönlendirmek için birkaç sezgisel yaklaşım kullanılır. Sezgisel kesin seçim algoritmanın performansı üzerinde büyük bir etkiye sahiptir. Çeşitli buluşsallar ağırlıklandırılır ve belirli bir pozisyonun nasıl “iyi” olduğunu belirleyen bir pozisyona birleştirilir. Optimizasyon araştırması daha sonra tüm olası yönetim pozisyonlarının ortalama skorunu maksimize etmeyi amaçlayacaktır. Oyunda gösterildiği gibi gerçek puan, değil Kurul puanını hesaplamak için kullanılır, çünkü karoları birleştirme lehine çok fazla ağırlıklıdır (gecikmiş birleşme büyük bir fayda sağlayabilir).

Öncelikle iki çok basit buluşsal yöntem kullandım, açık kareler için "bonuslar" verdim ve kenarda büyük değerler elde ettim. Bu keşifler oldukça iyi performans gösterdi, sıklıkla 16384'ü başardı ama hiç 32768'e ulaşamadı.

Petr Morávek (@ xificurk) benim AI'mi aldı ve iki yeni buluşsallık ekledi. İlk buluşsallık, monotonik olmayan sıralar ve sütunlar arttıkça artan sütunlar için bir penaltı idi; bu, küçük sayıdaki monotonik olmayan sıraların skoru kuvvetli bir şekilde etkilememesini sağladı, ancak büyük sayıdaki monotonik olmayan satırlar skoru önemli ölçüde kırdı. İkinci keşif, açık alanlara ek olarak potansiyel birleşme sayısını (bitişik değerler) saydı. Bu iki sezgisel algoritma, monotonik levhalara (birleşmesi daha kolay olan) doğru yönelmeye ve çok sayıda birleşmeyle (daha büyük bir etki için mümkün olduğunca birleştirmeleri hizalamaya teşvik ederek) tahta pozisyonlarına doğru ilerlemeye hizmet etti.

Ayrıca, Petr ayrıca bir "meta-optimizasyon" stratejisi kullanarak sezgisel ağırlıklarını optimize etti (bir algoritma kullanarak) CMA-ES), ağırlıklar kendilerini mümkün olan en yüksek ortalama skoru elde etmek için ayarlandı.

Bu değişikliklerin etkisi oldukça önemlidir. Algoritma, zamanın% 90'ından fazlasını elde etmek için zamanın yaklaşık% 13'ünü oluşturan 16384 çini elde etmeye gitti ve algoritma, zamanın 1 / 3'ü boyunca 32768'e ulaşmaya başladı (eski buluşsallık bir zamanlar bir 32768 çini üretmedi). .

Sezgisel keşif için hala bir yer olduğuna inanıyorum. Bu algoritma kesinlikle "optimal" değil, ama oldukça yakınlaşıyor gibi hissediyorum.


AI, oyunlarının üçte birinden 32768 çini elde etmesinin büyük bir kilometre taşı olduğunu; Herhangi bir insan oyuncunun resmi oyunda 32768 elde edip etmediğini (yani, kaydetme veya geri alma gibi araçları kullanmadan) duymak beni şaşırtacaktır. Ben 65536 kiremit ulaşılabilecek olduğunu düşünüyorum!

AI'yi kendiniz deneyebilirsiniz. Kod şu adrestedir https://github.com/nneonneo/2048-ai.


1132
2018-03-19 07:22



@RobL: 2, zamanın% 90'ında görünür; 4'lerin zamanının% 10'u görünüyor. İçinde kaynak kodu: var value = Math.random() < 0.9 ? 2 : 4;. - nneonneo
Şu anda Cuda'ya geçiş yapmak için GPU daha da yüksek hızlar için çalışıyor! - nimsson
@nneonneo Kodunuzu emscripten ile javascript'e taşıdım ve oldukça iyi çalışıyor tarayıcıda Şimdi! Izlemek için serin, derleme ve her şeye ihtiyaç olmadan ... Firefox'ta, performans oldukça iyi ... - reverse_engineer
Bir 4x4 ızgaradaki teorik sınır aslında 131072 değil 65536'dır. Ancak bu, doğru anda 4'lük bir değer elde etmeyi gerektirir (yani, 4'le birlikte 6553636 doldurulan - 15 adet alan doldurulmuştur) ve bu durumda tahta kurulmalıdır. böylece anı birleştirebilirsiniz. - Bodo Thiesen
@nneonneo Oyunların% 60'ında 32k'ye ulaşan AI'mızı daha iyi görmek isteyebilirsiniz: github.com/aszczepanski/2048 - cauchy


Bu konudaki diğerlerinin bahsettiği AI programının yazarıyım. AI'yi görüntüleyebilirsiniz aksiyon ya da oku kaynak.

Şu anda, program, dizüstü bilgisayarımdaki tarayıcıda javascript ile çalışan% 90'lık bir kazanım oranını yaklaşık 100 milisaniye değerinde düşünme süresiyle başardı, bu yüzden mükemmel değil (henüz!).

Oyun ayrı bir devlet alanı, mükemmel bilgi, satranç ve dama gibi sıra tabanlı oyun olduğundan, bu oyunlarda çalıştığı ispatlanmış aynı yöntemleri kullandım. minimaks  arama ile alfa-beta budama. Orada bu algoritma hakkında çok fazla bilgi bulunduğundan, sadece kullandığım iki ana buluşsaldan bahsedeceğim. statik değerlendirme işlevi ve diğer insanların burada ifade ettikleri sezgilerin çoğunu formüle eder.

monotonluk

Bu buluşsal, karoların değerlerinin, hem sol / sağ hem de yukarı / aşağı yönlerinde arttığını veya azaldığını temin etmeye çalışır. Bu buluşsallık, tek başına diğerlerinin bahsettiği sezgiyi, daha yüksek değerli karoların bir köşede kümelenmesi gerektiğini yakalar. Tipik olarak daha küçük değerli karoların yetim kalmasını önleyecek ve daha büyük çini içine giren ve daha küçük çini içine dolduran daha küçük kiremitlerle levhayı çok düzenli tutacak.

İşte mükemmel monotonik bir ızgara bir ekran görüntüsü. Bunu, algoritmayı diğer işlevlerini göz ardı etmek ve sadece monotonluğu göz önünde bulundurmak için eval fonksiyonu ile çalıştırarak elde ettim.

A perfectly monotonic 2048 board

Pürüzsüzlük

Yukarıdaki keşif tek başına, bitişik karoların değer olarak azaldığı, fakat tabii ki birleştirmek için bitişik karoların aynı değerde olması gereken yapılar yaratma eğilimindedir. Bu nedenle, pürüzsüzlük sezgisi, komşu karolar arasındaki değer farkını ölçer ve bu sayımı en aza indirmeye çalışır.

Hacker News hakkında bir yorumcu verdi ilginç bir formalizasyon Bu fikrin grafik teorisi açısından.

İşte mükemmel bir düzgün ızgara, bir nezaket ekran görüntüsü bu mükemmel parodi çatal.

A perfectly smooth 2048 board

Ücretsiz Fayans

Son olarak, oyun tahtası çok sıkışık olduğunda seçenekler hızlı bir şekilde tükenebileceğinden, çok az sayıda ücretsiz fayansa sahip olmanın bir cezası var.

Ve bu kadar! Bu kriterleri optimize ederken oyun alanı boyunca arama yapmak, oldukça iyi bir performans sağlar. Açıkça kodlanmış bir hareket stratejisinden ziyade genelleştirilmiş bir yaklaşımın kullanılmasının bir avantajı, algoritmanın genellikle ilginç ve beklenmedik çözümler bulabilmesidir. Eğer koşmayı izlerseniz, çoğu zaman hangi duvarın ya da köşenin karşı karşıya kaldığını değiştirmesi gibi şaşırtıcı ama etkili hareketler yapar.

Düzenle:

İşte bu yaklaşımın gücünü gösteren bir gösteri. Karo değerlerini kaldırdım (böylece 2048'e ulaştıktan sonra devam etti) ve burada sekiz denemeden sonra en iyi sonuç.

4096

Evet, bu 2048 yanında bir 4096. =) Bu aynı tahtada üç kez zor 2048 kiremit elde ettiği anlamına gelir.


1224
2018-03-13 20:04



Bilgisayarı '2' ve '4' karolarını 'rakip' olarak yerleştirebilirsiniz. - Wei Yen
@WeiYen Elbette, ama bir minmax problemi ile ilgili olarak, oyun mantığına sadık değil çünkü bilgisayar, kasıtlı olarak skoru en aza indirgemek yerine, belli olasılıklarla rasgele bir şekilde fayanslar yerleştiriyor. - koo
AI fayansları rastgele yerleştirse de amaç kaybetmek değildir. Şanssızlık, rakibin sizin için en kötü hamleyi seçmesiyle aynı şeydir. “Min” kısmı, muhafazakâr bir şekilde oynamaya çalıştığınız anlamına gelir, böylece şanssızlık yaratabileceğiniz korkunç hareketler olmaz. - FryGuy
Ben 20s bir çatal oluşturmak için bir fikir vardı, nerede bilgisayar yerine koymak için belirlemek için 2s ve 4s yerine AI rastgele kullanır. Sonuç: berbat imkansızlık. Burada denenebilir: sztupy.github.io/2048-Hard - SztupY
@SztupY Vay, bu şeytan. Bana hatırlatır qntm.org/hatetris Hatetris, durumunuzu en aza indirecek parçayı da yerleştirmeye çalışır. - Patashu


DÜZENLE: Bu, insan bilinçli düşünce sürecini modelleyen ve tüm olasılıkları araştıran AI'ya kıyasla çok zayıf sonuçlar alan saf bir algoritmadır. Cevap zaman çizelgesinde erken sunuldu.

Algoritmayı geliştirdim ve oyunu dövüyorum! Sonuna yakın basit kötü şanstan dolayı başarısız olabilir (aşağıya doğru hareket etmek zorunda kalmazsınız, ki asla yapmamalısınız, ve en yüksek değerde bir karo görünür. Sadece en üstteki satırı doldurmaya çalışın, böylece sola Deseni kırın), ancak temel olarak, sabit bir parçaya ve oynamak için bir mobil parçaya sahip olursunuz. Bu senin amacın:

Ready to finish

Bu varsayılan olarak seçtiğim model.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

Seçilen köşe keyfi, temelde asla tek bir tuşa basmazsınız (yasak hareket) ve eğer yaparsanız, tekrar tersine bastırır ve düzeltmeye çalışırsınız. Gelecek karolar için, model her zaman bir sonraki rasgele kiremitin 2 olmasını ve mevcut modelin karşıt tarafında görünmesini bekler (ilk satır tamamlanmamışken, sağ üst köşede, ilk satır tamamlandıktan sonra, sol altta) köşe).

İşte algoritma gider. % 80 civarında kazanır (her zaman daha "profesyonel" AI teknikleriyle kazanmak mümkündür, bununla ilgili emin değilim.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Eksik adımlarda birkaç işaretçi. İşte: model change

Model, beklenen modele daha yakın olma şansından dolayı değişti. AI'nın elde etmeye çalıştığı model şu:

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

Ve oraya varılacak zincir:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

O Yasak alanları temsil eder ...

Bu yüzden sağa, sonra tekrar sağa, sonra (4'ün oluşturulduğu yere bağlı olarak sağa ya da yukarı), o zamana kadar zinciri tamamlamaya devam edecektir:

Chain completed

Şimdi model ve zincir geri döndü:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

İkinci işaretçi, şansı kötü ve ana noktaya alındı. Başarısız olması muhtemeldir, ancak yine de başarabilir:

Enter image description here

İşte model ve zincir:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

128 seviyesine ulaşmayı başardığında, bir bütün satır tekrar kazanılır:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

119
2018-03-12 16:05



execute move with best score Bir sonraki eyaletlerden en iyi skoru nasıl değerlendirirsiniz? - Khaled.K
buluşsal tanımlanır evaluateResult Temel olarak mümkün olan en iyi senaryoya en yakın olanı elde etmeye çalışırsınız. - Daren
@Daren Ayrıntılarınızı bekliyorum - ashu
@ashu Üzerinde çalışıyorum, beklenmedik şartlar beni bitirmek için zamanımdan ayrıldı. Bu arada algoritmayı geliştirdim ve şimdi zamanın% 75'ini çözüyor. - Daren
Bu strateji hakkında gerçekten çok hoşuma giden şey, oyunu el ile oynarken kullanabildiğim için 37k puanlık bir puan almamı sağladı. - Cephalopod


Bu oyun için bir AI fikriyle ilgilenmeye başladım. kodlanmış zeka yok (yani buluşsal, skorlama fonksiyonları vb.). Yapay zeka "Bilmek" sadece oyun kuralları ve "çözmek" oyun oyna. Bu, oyun oynamanın esasen oyunun insan anlayışını temsil eden bir puanlama fonksiyonu tarafından yönlendirilen kaba kuvvetin olduğu çoğu AI'ya (bu konudakiler gibi) zıttır.

AI Algoritması

Basit ama şaşırtıcı derecede iyi bir oyun algoritması buldum: Belirli bir tahta için bir sonraki hamleyi belirlemek için, AI oyunu kullanarak bellekte oynar. rasgele hareketler Oyun bitene kadar. Bu, son oyun skorunu takip ederken birkaç kez yapılır. Sonra ortalama son skor başlangıç ​​hareket başına hesaplanır. En yüksek ortalama son puana sahip başlangıç ​​hareketi bir sonraki hamle olarak seçilmiştir.

Hareket başına sadece 100 çalışmayla (yani hafıza oyunlarında) AI, 2048 karonun% 80'ini ve 4096 karonunun% 50'sini elde eder. 10000 çalışmasını kullanarak, 2048 karonunu% 100, 4096 döşemesi için% 70 ve 8192 döşemesi için yaklaşık% 1 alır.

Eylemde görün

Elde edilen en iyi skor burada gösterilmiştir:

best score

Bu algoritma hakkında ilginç bir gerçek, rastgele oyunların şaşırtıcı derecede oldukça kötü olmasına rağmen, en iyi (ya da en azından kötü) hamlelerin seçilmesi, çok iyi bir oyuna yol açar: Tipik bir AI oyunu, 70000 puana ve son 3000 hamleye ulaşabilir. Herhangi bir pozisyondan bellek içi rastgele oyun oyunları, ölmeden önce yaklaşık 40 ekstra hareket halinde ortalama 340 ek puan verir. (Bunu AI'yi çalıştırarak ve hata ayıklama konsolunu açarak kendiniz görebilirsiniz.)

Bu grafik şu noktayı göstermektedir: Mavi çizgi, her hareketinden sonra tahta puanını gösterir. Kırmızı çizgi, algoritmanın en iyi Bu pozisyondan rastgele koşan son oyun puanı. Özünde, kırmızı değerler, algoritmanın en iyi tahmininiz olduğu için mavi değerleri yukarı doğru "çekiyor". Kırmızı çizginin her noktanın mavi çizgisinin üstünde olduğunu görmek ilginç, yine de mavi çizgi daha fazla artmaya devam ediyor.

scoring graph

Algoritmanın, onu üreten hamleleri seçmesi için iyi bir oyun oynamasını öngörmesi gerekmediğini hayret verici buluyorum.

Daha sonra arama yaparken bu algoritmanın bir Saf Monte Carlo Ağacı Ara algoritması.

Uygulama ve Linkler

İlk önce olabilecek bir JavaScript sürümü oluşturdum burada görüldü. Bu sürüm, 100'lük koşuları düzgün bir zamanda çalıştırabilir. Ek bilgi için konsolu açın. (kaynak)

Daha sonra, biraz daha fazla oynamak için @nneonneo yüksek düzeyde optimize edilmiş bir altyapı kullandım ve C ++ 'da benim versiyonumu uyguladı. Bu sürüm, sabrınız varsa, hareket başına 100000, hatta 1000000'e kadar izin verir. Sağlanan bina talimatları. Konsolda çalışır ve ayrıca web sürümünü çalmak için uzaktan kumanda vardır. (kaynak)

Sonuçlar

Şaşırtıcı bir şekilde, sayıların sayısını arttırmak oyun oynamayı büyük ölçüde geliştirmez. Bu stratejiye, 4096 fayansı ve daha küçük olanları olan 8192 çini elde etmek için çok yakın olan 80000 noktada bir sınır var gibi görünüyor. 100 ila 100000 arasında çalışma sayısını arttırmak, olasılık Bu sınıra ulaşma sınırı (% 5'den% 40'a) ancak kırılmadı.

10000 koşusu, bu bariyeri en fazla 129892 skor ve 8192 karoya ulaşan zamanın% 1'inden daha az kırmak için yönetilen kritik konumların yakınında 1000000'e geçici bir artışla çalışır.

İyileştirmeler

Bu algoritmayı uyguladıktan sonra, min veya max skorlarını veya min, max ve avg kombinasyonlarını kullanmayı içeren birçok geliştirmeyi denedim. Ayrıca derinlik kullanmayı denedim: Her hareket için K çalışmalarını denemek yerine, hareket başına K hareketlerini denedim liste belirli bir uzunluğun (örneğin "yukarı, yukarı, sol") ve en iyi puanlama hareket listesinin ilk hareketinin seçilmesi.

Daha sonra belirli bir hamle listesinden sonra bir hamle yapabilmenin koşullu olasılığını hesaba katan bir puanlama ağacı uyguladım.

Ancak, bu fikirlerin hiçbiri basit ilk fikirden hiçbir gerçek avantaj göstermedi. C ++ kodunda yorumlanan bu fikirlerin kodunu bıraktım.

Çalışmalardan herhangi birini yanlışlıkla bir sonraki en yüksek kiremiğe ulaşmayı başardığında 1000000'a kadar çalışma sayısını artıran bir "Derin Arama" mekanizması ekledim. Bu bir zaman iyileştirme teklif etti.

Herhangi birinin AI'nin alan bağımsızlığını koruyan başka iyileştirme fikirleri olup olmadığını öğrenmek isterim.

2048 Varyantlar ve Klonlar

Sadece eğlenmek için ben de AI'yi bir yer imi olarak uyguladıOyunun kontrollerine girerek. Bu, AI'nın orijinal oyunla çalışmasına izin verir ve çeşitlerinin çoğu.

Bu, AI'nın alandan bağımsız doğası nedeniyle mümkündür. Bazı değişkenler, Altıgen klon gibi oldukça farklıdır.


114
2018-05-25 09:25



+1. Bir AI öğrencisi olarak bunu gerçekten ilginç buldum. Boş zamanlarında buna daha iyi bakacağız. - Isaac
Bu harika! Beklenti için iyi bir sezgisel işlev için ağırlıkları optimize eden saatler harcadım ve bunu 3 dakika içinde uyguladım ve bu onu tamamen parçalara ayırdı. - Brendan Annable
Monte Carlo simülasyonunun güzel kullanımı. - nneonneo
Bu oyunu izlemek aydınlanmayı gerektiriyor. Bu tüm buluşsalları darbeler ve yine de çalışır. Tebrikler! - Stéphane Gourichon
Bugüne kadar, burada en ilginç çözüm. - shebaw


Burada bir blogumda yayınla


Önerdiğim çözüm çok basit ve uygulanması kolaydır. Bununla birlikte, 131040 puanına ulaşmıştır. Algoritma performanslarının çeşitli kriterleri sunulmuştur.

Score

Algoritma

Sezgisel puanlama algoritması

Algoritmanın temel aldığı varsayım oldukça basittir: Eğer daha yüksek puan almak istiyorsanız, yönetim kurulu mümkün olduğunca düzenli tutulmalıdır. Özellikle, en uygun kurulum, karo değerlerinin doğrusal ve monotonik bir azalan sırasına göre verilir. Bu sezgi size ayrıca bir karo değeri için üst sınır verir: s n, tahtadaki karo sayısıdır.

(Gerektiğinde 2 kiremit yerine 4 kiremit rastgele oluşturulmuşsa 131072 karosuna ulaşma olasılığı vardır)

Tahtayı düzenlemek için iki olası yol aşağıdaki resimlerde gösterilmiştir:

enter image description here

Monotonik bir azalan düzende karoların koordinasyonunu uygulamak için, skor, lineerleştirilmiş değerlerin toplamı olarak hesaplanır ve ortak oran r <1 olan bir geometrik dizinin değerleri ile çarpılır.

s

s

Bir kerede birçok doğrusal yol değerlendirilebilir, final puanı herhangi bir yolun maksimum puanı olacaktır.

Karar kuralı

Uygulanan karar kuralı oldukça akıllı değil, Python'daki kod burada sunuldu:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Minmax veya Expectiminimax'ın bir uygulaması algoritmayı kesinlikle geliştirecektir. Açıkçası bir daha Gelişmiş karar kuralı algoritmayı yavaşlatacak ve uygulanması için biraz zaman gerektirecektir. Yakın gelecekte minimax uygulamasını deneyeceğim. (bizi izlemeye devam edin)

Karşılaştırma

  • T1 - 121 testi - 8 farklı yol - r = 0.125
  • T2 - 122 testi - 8 farklı yol - r = 0.25
  • T3 - 132 testi - 8 farklı yol - r = 0.5
  • T4 - 211 testleri - 2 farklı yollar - r = 0.125
  • T5 - 274 testleri - 2 farklı yollar - r = 0.25
  • T6 - 211 testleri - 2 farklı yollar - r = 0.5

enter image description here enter image description here enter image description here enter image description here

T2 durumunda, on dört test, ortalama skorla 4096 karo üretmektedir. s 42000

kod

Kod aşağıdaki bağlantıdan GiHub'da bulunabilir: https://github.com/Nicola17/term2048-AI Dayanmaktadır term2048 ve Python'da yazılmıştır. C ++ 'da mümkün olan en kısa sürede daha verimli bir versiyon uygulayacağım.


88
2018-03-26 22:13



Fena değil, illüstrasyonlarınız bana birleştirme fikirlerini bir değerlendirmeden geçirdiler. - Khaled.K


Denemem, yukarıdaki gibi diğer çözümler gibi beklemeyi kullanıyor, ancak bitboard'lar olmadan. Nneonneo'nun çözümü, yaklaşık 6 kiremit ile 4'lük bir derinlik ve 4 hareketin mümkün olduğu 10 milyonluk hareketleri kontrol edebilir (2 * 6 * 4)4. Benim durumumda, bu derinliğin keşfedilmesi çok uzun sürüyor, beklemediğim aramaların derinliğini soldaki serbest fayans sayısına göre ayarlıyorum:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

Levhaların skorları, serbest fayans sayısının karesinin ağırlıklı toplamı ve 2D ızgarasının nokta çarpımı ile hesaplanır:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

Hangi sol üst kiremit gelen bir tür yılanda azalan fayans organize etmek için zorlar.

Aşağıdaki kod veya jsbin:

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



Bunun neden daha fazla değere sahip olmadığından emin değil. Bu sadelik için gerçekten etkili. - David Greydanus
Teşekkürler, geç cevap ve gerçekten iyi değil (neredeyse her zaman [1024, 8192]), maliyet / istatistik fonksiyonu daha fazla çalışmaya ihtiyaç duyar - caub
Boş alanlara nasıl ağırlık verdiniz? - David Greydanus
Bu basitçe cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid) ve bu maliyeti maksimize etmeye çalışıyoruz - caub
Bu daha fazla Upvotes ihtiyacı var! Büyük kod! - Smartis


Bence, 10000'den fazla puan elde ettiğimden, oldukça iyi çalışan bir algoritma buldum, 1600'lü yaşlarımın en iyisi. Çözümüm en büyük sayıları bir köşede tutmayı değil, en üst sırada tutmaktı.

Lütfen aşağıdaki kodu inceleyin:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

25
2018-03-12 18:57



Bunu test eden 100.000 oyuna, "yukarı, sağa, yukarı, sola, ..." gibi önemsiz döngüsel stratejiye karşı koştum (ve eğer gerekirse). Döngüsel strateji, "ortalama karo puanını" tamamladı 770.6, bu sadece bir tane var 396.7. Bunun neden olabileceğini tahmin ettiniz mi? Sola veya sağa çok daha fazla birleştiğinde bile çok fazla iniş yaptığını düşünüyorum. - Thomas Ahle
Karolar, çoklu yönlerde kaydırılmamışsa, uyumsuz yollarla istiflenme eğilimindedir. Genel olarak, döngüsel bir strateji kullanmak, merkezdeki daha büyük kiremitlerle sonuçlanacak ve bu da manevra yapmayı daha da zorlaştırıyor. - bcdan


Bu iş parçasında bahsedilen diğer programlardan daha iyi olan 2048 kontrolörünün yazarıyım. Denetleyicinin verimli bir şekilde uygulanması github. İçinde ayrı bir repo Kontrolörün durum değerlendirme fonksiyonunu geliştirmek için kullanılan kod da vardır. Eğitim yöntemi kâğıt.

Kontrolör, bir varyant tarafından sıfırdan (insan 2048 uzmanlığı olmadan) öğrenilen bir durum değerlendirme fonksiyonu ile expectimax araştırmasını kullanır. geçici fark öğrenme (bir takviye öğrenme tekniği). Durum değeri işlevi bir n-tuple ağıTemel olarak, tahtada gözlemlenen modellerin ağırlıklı bir doğrusal işlevidir. Daha fazla 1 milyar ağırlık, toplamda.

performans

1 hamle / s'de: 609104 (100 oyun ortalaması)

10 hamle / s'de: 589355 (300 oyun ortalaması)

3 katlı olarak (yaklaşık 1500 hareket / s): 511759 (1000 oyun ortalaması)

10 hamle / s için karo istatistikleri aşağıdaki gibidir:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(Son satır, verilen döşemeleri aynı zamanda tahtada bulundurmak anlamına gelir).

3 katlı için:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Ancak, 65536 çini elde etmeyi hiç gözlemlemedim.


25
2017-12-21 10:49



Oldukça etkileyici sonuç. Ancak, açıklayacağınız cevabı muhtemelen güncellemeniz mümkün olabilir (kabaca, basit terimlerle ... Eminim ki tüm detaylar burada yayınlamak için çok uzun zaman alacaktır). Öğrenme algoritmasının nasıl çalıştığının kaba bir açıklamasında olduğu gibi? - Cedric Mamo
@CedricMamo: Github'da bir referans var: arxiv.org/abs/1604.05085 - Florian Castellane