streamalism.org

1. Bemutatkozás

A közelmúltban megnéztünk egy algoritmust a 2048-as játék megoldására. Ezt elméleti szempontból vitattuk meg, nem pedig valódi kóddal a mögött.

Itt meg fogjuk írni ennek megvalósítását Java-ban. Ez mind az emberi, mind a számítógépes játékosként fog játszani, megmutatva, hogy egy optimálisabb játék milyen jól játszható.

2. Kezdeti beállítás

Az első dolog, amire szükségünk van, egy beállítás, amelyben játszhatunk a játékkal, és láthatjuk, hogyan halad a fejlődés.

Ez megadja mindazokat a konstrukciókat, amelyekre szükségünk van a játékhoz, és teljes mértékben megvalósítjuk a számítógépes lejátszót - amely egyébként csak véletlenszerű lapokat helyez el. Ez lehetővé teszi számunkra, hogy egy „emberi” játékost bevezessünk a játékba.

2.1. Játék tábla

Minden más előtt szükségünk van egy játéktáblára. Ez egy cellarács, amelybe számok helyezhetők.

Ahhoz, hogy néhány dolgot egy kicsit könnyebb legyen dolgozni, kezdjük a cella helyének egyszerű ábrázolásával. Ez szó szerint csak egy burkoló egy pár koordináta körül:

public class Cell {private final int x; magán döntő int y; // konstruktor, getters és toString}

Most írhatunk egy osztályt, hogy képviselje magát a táblát. Ez az értékeket egy egyszerű kétdimenziós tömbben fogja tárolni, de lehetővé teszi számunkra, hogy a fentieken keresztül hozzáférjünk hozzájuk Sejt osztály:

nyilvános osztálytábla {private final int [] [] tábla; privát végső int pontszám; public Board (int méret) {this.board = new int [size] []; ez.pontszám = 0; for (int x = 0; x <méret; ++ x) {this.board [x] = new int [size]; mert (int y = 0; y <méret; ++ y) {tábla [x] [y] = 0; }}} public int getSize () {return board.length; } public int getScore () {return score; } public int getCell (Cell cell) {return board [cell.getX ()] [cell.getY ()]; } public boolean isEmpty (Cell cell) {return getCell (cell) == 0; } public List üres cellák () {List lista = new ArrayList (); for (int x = 0; x <tábla.hossz; ++ x) {for (int y = 0; y <tábla [x] .hossz; ++ y) {Sejtcella = új Cell (x, y); if (isEmpty (cella)) {eredmény.add (cella); }}} visszatérési eredmény; }}

Ez egy megváltoztathatatlan osztály, amely egy táblát képvisel, és lehetővé teszi számunkra, hogy kihallgassuk, hogy megtudjuk az aktuális állapotot. Ugyancsak nyomon követi az aktuális pontszámot, amire később még eljutunk.

2.2. Számítógépes lejátszó és csempék elhelyezése

Most, hogy van egy játéktáblánk, szeretnénk tudni vele játszani. Az első dolog, amire vágyunk, a számítógépes lejátszó, mert ez egy tisztán véletlenszerű lejátszó, és a későbbiekben pontosan az lesz, amire szükség van.

A számítógépes lejátszó nem tesz mást, mint egy lapkát helyez egy cellába, ezért valamilyen módon meg kell valósítanunk ezt a táblánkon. Szeretnénk ezt változhatatlannak tartani, ezért egy csempe elhelyezése vadonatúj táblát hoz létre az új állapotban.

Első, olyan konstruktort akarunk, amely a tényleges tábla állapotot veszi fel, szemben az előzővel, amely csak egy üres táblát épített:

privát tanács (int [] [] tábla, int pontszám) {this.score = score; this.board = új int [tábla.hossz] []; for (int x = 0; x <tábla.hossz; ++ x) {this.board [x] = tömbök.copyOf (tábla [x], tábla [x] .hossz); }}

Ez magán hogy valaha csak ugyanazon osztályon belül más módszerekkel lehessen használni. Ez segít a tábla beágyazásában.

Ezután hozzáadunk egy módszert egy csempe elhelyezéséhez. Ez egy vadonatúj táblát ad vissza, amely megegyezik a jelenlegivel, azzal a különbséggel, hogy az adott cellában meg van adva a megadott szám:

public Board placeTile (Cella cella, int szám) {if (! isEmpty (cella)) {dobjon új IllegalArgumentException ("Ez a cella nem üres"); } Board eredmény = new Board (this.board, this.score); eredmény.tábla [cella.getX ()] [cella.getY ()] = szám; visszatérési eredmény; }

Végül, írunk egy új osztályt, amely egy számítógépes lejátszót képvisel. Ennek egyetlen módszere lesz, amely átveszi az aktuális táblát és visszaadja az újat:

public class Computer {private final SecureRandom rng = new SecureRandom (); public Board makeMove (Board bemenet) {List üres cellák = input.emptyCells (); dupla számToPlace = rng.nextDouble (); int indexToPlace = rng.nextInt (emptyCells.size ()); Cell cellToPlace = emptyCells.get (indexToPlace); return input.placeTile (cellToPlace, numberToPlace> = 0,9? 4: 2); }}

Ez megkapja a tábla minden üres cellájának listáját, kiválaszt egy véletlenszerűt, majd betesz egy számot. Véletlenszerűen úgy döntünk, hogy az idő 10% -ában egy "4" -et teszünk a cellába, a másik pedig 90% -ot.

2.2. „Emberi” játékos és váltólapok

A következő dologra szükségünk van egy „emberi” játékosra. Ez nem a végcél lesz, hanem egy tisztán véletlenszerű játékos, aki véletlenszerű irányt választ, hogy minden mozdulatnál eltolja a lapkákat. Ez akkor olyan helyként fog működni, amelyre építve optimális játékossá válhatunk.

Először meg kell határoznunk a lehetséges mozgások felsorolását:

public enum {FEL, LE, BALRA, JOBBRA}

Ezután bővítenünk kell a Tábla osztály támogatja a mozdulatokat azáltal, hogy a lapkákat ezen irányok egyikébe tolja. A bonyolultság csökkentése érdekében a táblát úgy akarjuk elforgatni, hogy a lapkákat mindig ugyanabba az irányba toljuk el.

Ez azt jelenti, hogy eszközre van szükségünk a tábla átültetéséhez és visszafordításához:

privát statikus int [] [] transzponálja (int [] [] bemenet) {int [] [] eredmény = új int [bemenet.hossz] []; for (int x = 0; x <bemenet.hossz; ++ x) {eredmény [x] = új int [bemenet [0] .hossz]; for (int y = 0; y <bemenet [0] .hossz; ++ y) {eredmény [x] [y] = bemenet [y] [x]; }} visszatérési eredmény; } privát statikus int [] [] fordított (int [] [] bemenet) {int [] [] eredmény = új int [bemenet.hossz] []; for (int x = 0; x <bemenet.hossz; ++ x) {eredmény [x] = új int [bemenet [0] .hossz]; for (int y = 0; y <bemenet [0] .hossz; ++ y) {eredmény [x] [y] = bemenet [x] [bemenet.hossz - y - 1]; }} visszatérési eredmény; }

A tábla átültetésekor az összes sor és oszlop felcserélődik úgy, hogy a felső él bal bal él legyen. A tábla megfordítása egyszerűen tükrözi, úgy, hogy a bal széle a jobb széle lesz.

Ezután hozzáadunk egy metódust a Tábla adott irányba haladni és újat adni vissza Tábla az új állapotban.

Először a tábla állapotának másolatát készítjük, amellyel aztán együtt dolgozhatunk:

nyilvános testületi lépés (áthelyezés) {int newScore = 0; // A tábla klónozása int [] [] csempe = new int [this.board.length] []; for (int x = 0; x <ez a tábla.hossz; ++ x) {csempe [x] = tömbök. }

Ezután úgy manipuláljuk a másolatot, hogy mindig felfelé mozdítsuk a lapokat:

if (move == Move.LEFT || move == Move.RIGHT) {csempe = átültet (csempe); } if (mozgás == Mozgás.DOWN || mozgás == Mozgatás.JOBB) {csempe = fordított (csempe); }

Szükségünk van még egy csempére - ezúttal arra, amelybe beépítjük a végeredményt - és egy nyomkövetőt az e lépéshez elért új pontszámhoz:

int [] [] eredmény = új int [csempe.hossz] []; int newScore = 0;

Most, hogy készen állunk a cserepek váltására, és manipuláltuk a dolgokat, hogy mindig ugyanabba az irányba dolgozzunk, elkezdhetjük.

Minden oszlopot eltolhatunk a többitől függetlenül. Csak meg kell ismételnünk az oszlopokat, és meg kell ismételnünk, kezdve az átmozgatott lapok egy újabb példányának felépítésével.

Ezúttal a LinkedList mert szeretnénk tudni, hogy az értékek könnyen kibocsáthassanak belőle. Csak azokat a tényleges csempéket adjuk hozzá, amelyek számmal rendelkeznek, és átugorjuk az üres lapokat.

Ezzel elérjük a mozdulatainkat, de még nem érjük el a lapok egyesítését:

for (int x = 0; x <csempe.hossz; ++ x) {LinkedList thisRow = új LinkedList (); for (int y = 0; y 0) {thisRow.add (csempék [x] [y]); }}

Ezután egyesítenünk kell a csempéket. Ezt a fentiektől elkülönítve kell elvégeznünk; különben azt kockáztatjuk, hogy ugyanazt a lapkát többször összevonjuk.

Ezt egy másik építésével érjük el LinkedList a fentiekből származó csempék közül, de ezúttal összeolvadva haladunk:

LinkedList newRow = új LinkedList (); while (thisRow.size ()> = 2) {int először = thisRow.pop (); int második = thisRow.peek (); if (másodperc == első) {int újNumber = első * 2; newRow.add (newNumber); newScore + = newNumber; thisRow.pop (); } else {newRow.add (első); }} newRow.addAll (thisRow);

Itt is kiszámoljuk ennek a lépésnek az új pontszámát. Ez az összevonások eredményeként létrehozott lapok összege.

Ezt most beépíthetjük az eredménytömbbe. Miután elfogyott a listánkból származó csempék, a többit „0” értékkel töltjük fel, jelezve, hogy üresek:

 eredmény [x] = új int [csempe [0] .hossz]; mert (int y = 0; y <csempe [0] .hossz; ++ y) {if (newRow.isEmpty ()) {eredmény [x] [y] = 0; } else {eredmény [x] [y] = newRow.pop (); }}}

Miután befejeztük a cserepek eltolását, újra manipulálnunk kell őket a helyes forgatásig. Ez pont az ellenkezője, amit korábban tettünk:

if (mozgás == Mozgás.DOWN || mozgás == Mozgatás.JOBB) {eredmény = fordított (eredmény); } if (move == Move.LEFT || move == Move.RIGHT) {eredmény = átültet (eredmény); }

És végül új táblát építhetünk és adhatunk vissza ezzel az új burkolólappal és az újonnan kiszámított pontszámmal:

 új tábla visszaküldése (eredmény, ez a pontszám + új pontszám); }

Most olyan helyzetben vagyunk, hogy megírhatjuk a véletlenszerű „emberi” játékosunkat. Ez nem más, mint egy véletlenszerű lépés létrehozása, és a fenti módszer meghívása az adott lépés lejátszásához:

public class Human {private SecureRandom rng = new SecureRandom (); public Board makeMove (Board bemenet) {Move move = Move.values ​​() [rng.nextInt (4)]; return input.move (move); }}

2.3. Játék

Van elég komponensünk a játékhoz, igaz, nem túl sikeresen. Azonban hamarosan javítani fogjuk a Emberi osztályos játékokat, és ez lehetővé teszi számunkra, hogy könnyen láthassuk a különbségeket.

Először is szükségünk van egy módra a játéktábla kinyomtatására.

Ennél a példánál csak a konzolra fogunk nyomtatni, tehát System.out.print elég jó. Egy igazi játékhoz jobb grafikákat szeretnénk készíteni:

privát statikus void printBoard (Board board) {StringBuilder topLines = new StringBuilder (); StringBuilder midLines = új StringBuilder (); for (int x = 0; x <board.getSize (); ++ x) "); topLines.append (" + "); midLines.append (" | "); for (int y = 0; y <board .getSize (); ++ y) {System.out.println (topLines); System.out.println (midLines); for (int x = 0; x <board.getSize (); ++ x) {Cellasejt = new Cell (x, y); System.out.print ("|"); if (board.isEmpty (cell)) {System.out.print ("");} else {StringBuilder output = new StringBuilder (Integer .toString (board.getCell (cell))); while (output.length () <8) {output.append (""); if (output.length () <8) {output.insert (0, "" );}} System.out.print (output);}} System.out.println ("|"); System.out.println (midLines);} System.out.println (topLines); System.out.println ("Pontszám:" + board.getScore ());}

Majdnem készen állunk az indulásra. Csak be kell állítanunk a dolgokat.

Ez azt jelenti, hogy létre kell hozni a táblát, a két játékost, és a számítógépnek két kezdeti lépést kell végrehajtania - vagyis két véletlenszerű számot kell elhelyezni a táblán:

Board board = új Board (4); Számítógépes számítógép = new Computer (); Emberi ember = új Ember (); for (int i = 0; i <2; ++ i) {tábla = számítógép.makeMove (tábla); }

És most megvan a tényleges játékhurok. Ez az emberi és a számítógépes játékosok ismétlése lesz, felváltva, és csak akkor áll meg, ha nem marad üres cellák:

nyomtatott tábla (tábla); do {System.out.println ("Emberi lépés"); System.out.println ("=========="); tábla = ember.makeMove (tábla); nyomtatott tábla (tábla); System.out.println ("Számítógép mozgatása"); System.out.println ("============="); tábla = számítógép.makeMove (tábla); nyomtatott tábla (tábla); } while (! board.emptyCells (). isEmpty ()); System.out.println ("Végső pontszám:" + board.getScore ());

Ezen a ponton, ha futtatnánk a programot, látnánk egy 2048-as véletlenszerű játékot.

3. A 2048 Player megvalósítása

Ha van egy bázisunk, ahonnan a játékot játszhatjuk, elkezdhetjük az „emberi” játékos megvalósítását, és jobb játékot játszhatunk, mint csak véletlenszerű irányt választani.

3.1. Mozgások szimulálása

Az itt megvalósított algoritmus az Expectimax algoritmuson alapszik. Mint olyan, az algoritmus lényege, hogy minden lehetséges mozdulatot szimuláljon, mindegyikhez hozzárendeljen egy pontszámot, és kiválassza a legjobban teljesítőt.

Később a későbbiekben ismertetett okokból nagy mértékben felhasználjuk a Java 8 Streameket a kód strukturálásához.

Kezdjük azzal, hogy újraírjuk a makeMove () módszer belülről Emberi osztály:

public Board makeMove (Board input) {return Arrays.stream (Move.values ​​()) .map (input :: move) .max (Comparator.comparingInt (tábla -> generálScore (tábla, 0))) .vagyElse (bemenet) ; }

Minden lehetséges irányba, ahol be tudunk lépni, létrehozzuk az új táblát, majd elindítjuk a pontozási algoritmust - ezen a táblán való áthaladás és 0 mélység. Ezután kiválasztjuk a legjobb ponttal rendelkező mozdulatot.

A mi generatorScore () Ezután a módszer minden lehetséges számítógépes lépést szimulál - vagyis „2” vagy „4” betűt helyez minden üres cellába -, majd meglátja, mi történhet ezután:

private int generatorScore (Board board, int depth) {if (mélység> = 3) {return aprēķFinalScore (tábla); } return board.emptyCells (). stream () .flatMap (cella -> Stream.of (új pár (cella, 2), új pár (cella, 4))) .mapToInt (mozgás -> {Board newBoard = tábla. placeTile (move.getFirst (), move.getSecond ()); int boardScore = calcScore (newBoard, mélység + 1); return (int) (boardScore * (move.getSecond () == 2? 0,9: 0,1)); }) .sum (); }

Ha elértük a mélységi határunkat, akkor azonnal megállunk, és kiszámoljuk a végeredményt, hogy ez a tábla milyen jó; különben folytatjuk a szimulációnkat.

A mi calcScore () A módszer ekkor a szimulációnk folytatása, futtatva az egyenlet emberi mozgás oldalát.

Ez nagyon hasonlít a makeMove () módszerrel, de a tényleges tábla helyett a folyamatban lévő pontszámot adjuk vissza:

privát int calcScore (Board board, int mélység) {return Arrays.stream (Move.values ​​()) .map (board :: move) .mapToInt (newBoard -> generátorScore (newBoard, mélység)) .max () vagyElse ( 0); }

3.2. A döntőtáblák pontozása

Most olyan helyzetben vagyunk, hogy szimulálhatjuk az emberi és a számítógépes játékosok oda-vissza mozgását, és megállunk, amikor elegendő mennyiséget szimuláltunk belőlük. Minden szimulációs ágban tudnunk kell pontszámot generálni az utolsó táblához, hogy lássuk, melyik ágat akarjuk folytatni.

Pontozásunk olyan tényezők kombinációja, amelyek mindegyikét a tábla minden sorára és oszlopára alkalmazzuk. Ezeket összesítik, és az összeget visszaadják.

Mint ilyen, létre kell hoznunk a sorok és oszlopok listáját, amelyek alapján pontszámokat lehet elérni:

Lista rowsToScore = new ArrayList (); for (int i = 0; i <board.getSize (); ++ i) {Lista sor = new ArrayList (); Lista col = new ArrayList (); mert (int j = 0; j <board.getSize (); ++ j) {row.add (board.getCell (új Cell (i, j))); col.add (board.getCell (új Cell (j, i))); } rowsToScore.add (sor); rowsToScore.add (oszlop); }

Ezután vesszük az elkészített listát, pontozzuk mindegyiket, és összesítsük a pontszámokat. Ez egy helyőrző, amelyet ki fogunk tölteni:

return rowsToScore.stream () .mapToInt (sor -> {int pontszám = 0; visszatérési pontszám;}) .sum ();

Végül pedig valóban létre kell hoznunk a pontszámainkat. Ez a fenti lambda belsejében található, és több különböző tényező, amelyek mind hozzájárulnak:

• Minden sorhoz rögzített pontszám
• A sor minden számának összege
• Minden egyesítés lehetséges a sorban
• A sor minden üres cellája
• A sor monotonitása. Ez azt az összeget jelenti, amelyet a sor növekvő numerikus sorrendben rendezett.

Mielőtt kiszámíthatnánk a pontszámokat, fel kell építenünk néhány extra adatot.

Először egy üres cellákkal rendelkező számok listáját szeretnénk eltávolítani:

Sorolja fel az preMerged = row.stream () .filter (érték -> érték! = 0) .collect (Collectors.toList ());

Ezután néhány számlálást készíthetünk ebből az új listából, megadva az azonos számú szomszédos cellák számát, szigorúan növekvő és szigorúan csökkenő számokkal:

int numMerges = 0; int monotonitásBal = 0; int monotonitásJobb = 0; mert (int i = 0; i másodperc) {monotonicitásBal + = első - másodperc; } else {monotonicitásJobb + = második - első; }}

Most kiszámíthatjuk ennek a sornak a pontszámát:

int pontszám = 1000; pontszám + = 250 * sor.folyam (). szűrő (érték -> érték == 0) .szám (); pontszám + = 750 * numMerges; pontszám - = 10 * sor.folyam (). mapToInt (érték -> érték) .összeg (); pontszám - = 50 * Math.min (monotonicitásBal, monotonicitásJobb); visszatérési pontszám;

Az itt kiválasztott számok viszonylag önkényesek. A különböző számok hatással lesznek a játék sikerességére, a különböző tényezőket előtérbe helyezve a játék módjában.

4. Az algoritmus fejlesztése

Az eddigiek működnek, és láthatjuk, hogy jó játékot játszik, de lassú. Körülbelül 1 perc kell emberi mozdulatokra. Jobban tehetünk ennél.

4.1. Párhuzamos feldolgozás

A kézenfekvő dolog az, hogy párhuzamosan végezzünk munkát. Ez óriási előnye a Java Streamekkel való együttműködésnek - ezt a munkát párhuzamosan végezhetjük el, ha minden egyes adatfolyamhoz csak egyetlen utasítást adunk.

Önmagában ez a változás mozdulatonként körülbelül 20 másodpercig vezet minket.

4.2. Lejátszhatatlan ágak metszése

A következő dolog, amit tehetünk, hogy kivágjuk az összes le nem játszható ágat. Vagyis bármikor, amikor egy emberi lépés változatlan táblát eredményez. Ezek szinte biztosan olyan ágak, amelyek rosszabb eredményeket fognak eredményezni - gyakorlatilag szabad mozgást adnak a számítógépnek -, de ezek feldolgozásához időbe kerülünk.

Ehhez egy egyenlő módszert kell megvalósítanunk a mi rendszerünkön Tábla hogy összehasonlíthassuk őket:

@Orride public boolean egyenlő (Object o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } Board board1 = (Board) o; visszatérés Arrays.deepEquals (tábla, tábla1. tábla); }

Ezután hozzáadhatunk néhány szűrőt a folyamvezetékeinkhez, hogy leállítsuk a változatlanok feldolgozását.

return Arrays.stream (Move.values ​​()) .parallel () .map (tábla :: mozgás) .szűrő (mozgatva ->! mozgatva.egyenlő (tábla)) ........

Ennek minimális hatása van a játék korai szakaszaira - amikor nagyon kevés a kitöltött cella, nagyon kevés a mozgás, amelyet meg lehet vágni. Később azonban ez sokkal nagyobb hatást vált ki, és csak néhány másodpercre csökkenti a mozgási időket.

5. Összefoglalás

Itt felépítettünk egy keretet a 2048-as játék játékához. Ezután írtunk egy megoldót ebbe, hogy jobb játékot tudjunk játszani. Az itt látható összes példa megtalálható a GitHub oldalon.

Miért ne próbálja meg megváltoztatni a szabályokat, hogy lássa, milyen hatással vannak a játékmenetre.