Kas yra optimalus 2048 m. Žaidimo algoritmas?

Neseniai suklupau 2048 m . Jūs derinate šias plyteles perkeliant jas į bet kurią iš keturių krypčių, kad padarytumėte „dideles“ plyteles. Po kiekvieno judėjimo atsitiktinėje tuščioje erdvėje atsiranda naujas fragmentas, kurio vertė yra 2 arba 4 . Žaidimas baigiasi, kai visi laukai yra užpildyti ir nėra jokių judesių, galinčių derinti plyteles, arba sukuriate 2048 .

Pirma, turiu vadovautis aiškiai apibrėžta tikslo pasiekimo strategija. Taigi, aš galvojau apie tai, kaip parašyti jai programą.

Mano dabartinis algoritmas yra:

 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 } 

Ką aš darau, tam tikru momentu bandysiu sujungti plyteles su 2 ir 4 reikšmėmis, ty stengiuosi kuo mažiau 2 ir 4 plytelių. Jei tai bandysiu, visos kitos plytelės automatiškai sujungiamos, o strategija atrodo gera.

Bet kai aš iš tikrųjų naudoju šį algoritmą, iki žaidimo pabaigos gaunu iki 4000 taškų. Maksimalūs AFAIK taškai yra šiek tiek daugiau nei 20 000 taškų, o tai yra daug daugiau nei mano dabartinis balas. Ar yra geresnis algoritmas nei didesnis?

1815 m
12 марта '14 в 8:37 2014-03-12 08:37 „nitish712“ yra nustatytas kovo 12 d. 14, 8:37 2014-03-12 08:37
@ 14 atsakymų

Aš sukūriau 2048 AI, naudojant optimizavimo optimizavimą, o ne miniax paiešką, kurią naudojo @ lover algoritmas. AI paprasčiausiai atlieka visų galimų judesių maksimalų padidinimą, po to laukia visų galimų plokštelių pasirodymų (svertinės plytelės, t. Y. 10% 4 ir 90% 2). Kiek aš žinau, neįmanoma optimizuoti lūkesčių optimizavimo (išskyrus tai, kad šakos, kurios yra labai mažai tikėtinos, yra pašalintos), todėl naudojamas algoritmas yra kruopščiai optimizuota brutalios jėgos paieška.

Našumas

Pagal numatytąją konfigūraciją (maksimalus paieškos gylis 8) AI trunka nuo 10 ms iki 200 ms, kad užbaigtų judėjimą, priklausomai nuo valdybos padėties sudėtingumo. Atliekant bandymus, per visą žaidimą AI pasiekia vidutinį 5-10 judėjimo greitį per sekundę. Jei paieškos gylis ribojamas iki 6 judesių, AI gali lengvai atlikti 20+ judesius per sekundę.

Norėdami įvertinti AI efektyvumą, aš pradėjau AI 100 kartų (prijungtas prie žaidimo naršyklės naudojant nuotolinio valdymo pultą). Kiekvienai plytelei nurodoma, kiek žaidimų, kuriose ši plytelė buvo pasiekta bent kartą, yra:

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

Minimalus balas visoms kelionėms buvo 124024; didžiausias rezultatas buvo 794076. Vidutinis balas buvo 387222. AI niekada negavo 2048 plytelių (todėl jis niekada neprarado žaidimo net kartą per 100 žaidimų); iš tiesų, tai bent 8192 plytelės pasiekė bent vieną kartą kiekviename bėgime!

Čia yra geriausio veikimo ekrano kopija:

2019

1183
19 марта '14 в 10:22 2014-03-19 10:22 atsakymas pateikiamas nneonneo kovo 19 d. 14 val. 10:22 2014-03-19 10:22

Aš esu AI programos autorius, kurį kiti minėjo šioje temoje. Galite peržiūrėti AI veiksmą arba skaityti šaltinį .

Šiuo metu programa pasiekia apie 90 proc. Laimėtojo „JavaScript“ spartos naršyklėje mano nešiojamojo kompiuterio naršyklėje, suteikdama apie 100 milisekundžių mąstymo laiko per vieną ruožą, taigi, nors ji nėra tobula (dabar!), Ji veikia labai gerai.

Kadangi žaidimas yra diskrečios valstybės erdvės, puikios informacijos, žingsnio po žingsnio žaidimas, pvz., Šachmatai ir šaškės, naudoju tuos pačius metodus, kurie buvo įrodyti, kad jie veikia šiuose žaidimuose, būtent minimx paieška su alfa-beta derliaus . Kadangi šiame algoritme jau yra daug informacijos, kalbėsiu tik apie dvi pagrindines heuristikas, kurias naudoju statinėje vertinimo funkcijoje ir kurios įformina daugelį intuicijų, kurias čia išreiškė kiti žmonės.

monotonija

Ši heuristika stengiasi užtikrinti, kad plytelių vertės padidėtų arba sumažėtų abiem kryptimis kairėje / dešinėje ir aukštyn / žemyn. Tik ši heuristika atspindi intuiciją, kurią daugelis kitų sakė, kad vertingesnės plytelės turėtų būti sugrupuotos į kampą. Paprastai tai užkerta kelią mažesnę vertę turintiems našlaičiams vertybiniams popieriams ir išlaikys valdybą labai organizuotai, o mažos plytelės bus pakopuotos ir užpildytos didesnėmis plokštelėmis.

Čia yra visiškai monotoniško tinklo ekranas. Tai gavau, pradėdamas algoritmą su eval funkcija, kuri ignoravo kitas heuristikas ir apsvarstė tik monotoniškumą.

2019

1233
13 марта '14 в 23:04 2014-03-13 23:04 atsakymas pateikiamas 13 m. kovo 13 d., 23:04, 2014-03-13 23:04

Mane domina AI idėja šiam žaidimui, kuriame nėra sunkiai koduotų žvalgybos (ty, heuristikos, taškų ir kt.). AI turi „žinoti“ tik žaidimo taisykles ir „suprasti“ žaidimą. Tai prieštarauja daugumai AI (pvz., Šioje temoje), kurioje žaidimas iš esmės yra brutali jėga, kontroliuojama taškų skaičiavimo funkcija, atspindinčia žmogaus žaidimo supratimą.

AI algoritmas

Radau paprastą, bet stebėtinai gerą žaidimo algoritmą: norint nustatyti kitą tam tikros lentos judėjimą, AI žaidime į atmintį žaidžia atsitiktiniais judesiais, kol baigsis žaidimas. Tai daroma kelis kartus, stebint rezultatą žaidimo pabaigoje. Tada apskaičiuojamas vidutinis galutinis pradinio posūkio taškas. Kitas žingsnis yra pradinis judėjimas su didžiausiu vidutiniu rezultatu.

Su 100 judėjimų (t.y. žaidimuose su atmintimi), AI judėjimui, jis pasiekia 2048 plyteles 80% atvejų ir 4096 plytelių 50% atvejų. Naudojant 10 000 važiavimų, 2048 m. Gauna 100%, 70% - 4096, o apie 1% - 8192.

Žr

Čia rodomas geriausias pasiektas rezultatas:

2019

125
25 мая '14 в 12:25 2014-05-25 12:25 atsakymas į Ronenzą pateiktas gegužės 25 d. 14 val. 12:25 2014-05-25 12:25

EDIT :. Tai naivus algoritmas, imituojantis žmogaus sąmoningo mąstymo procesą, ir jis gauna labai silpnus rezultatus, lyginant su AI, kurie ieško visų galimybių, nes jis tik žiūri į vieną plokštę į priekį. Ji buvo pateikta ankstyvajame atsako etape.

Aš paaiškinau algoritmą ir nugalėjau žaidimą! Tai gali nepavykti dėl paprasto nesėkmės arti pabaigos (jūs esate priversti judėti žemyn, kurį niekada neturėtumėte daryti, ir plytelė rodoma ten, kur ji turėtų būti didžiausia. Tiesiog pabandykite išlaikyti viršutinę eilutę pilnai, taigi judant į kairę, nesilaikoma šablonas), bet iš esmės jūs turite fiksuotą dalį ir mobilų žaidimo dalį. Tai jūsų tikslas:

Šį modelį pasirinkau pagal nutylėjimą.

 1024 512 256 128 8 16 32 64 4 2 xx xxxx 

Pasirinktas kampas yra savavališkas, iš esmės niekada nespaudžiate vieno klavišo (draudžiamas judėjimas), o jei tai padarysite, dar kartą paspaudžiate priešingą ir pabandykite ją ištaisyti. Būsimose plytelėse modelis visada tikisi, kad kita atsitiktinė plytelė bus 2 ir bus rodoma priešingoje dabartinio modelio pusėje (o pirmoji eilutė yra neišsami, apatiniame dešiniajame kampe, kai tik baigiama pirmoji eilutė, apačioje kairėje yra kampas).

Čia yra algoritmas. Apie 80% laimėjimų (atrodo, jūs visada galite laimėti daugiau „profesionalių“ AI metodų, nesu tikras.)

 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) } 

Keletas nuorodų į trūkstamus veiksmus. Čia:

Modelis pasikeitė dėl sėkmės, kad būtų artimesnis laukiamam modeliui. Modelis, kurį AI bando pasiekti, yra

  512 256 128 x XX xx XX xx xxxx 

Ir grandinė, kur galima pasiekti, tapo:

  512 256 64 O 8 16 32 O 4 xxx xxxx 

O yra draudžiamos erdvės ...