streamalism.org

1. Úvod

Nedávno sme sa pozreli na algoritmus riešenia hry 2048. Diskutovali sme o tom z teoretického hľadiska a nie za tým, že by za tým bol nejaký skutočný kód.

Tu napíšeme jeho implementáciu v Jave. Toto bude hrať ako ľudský, tak aj počítačový hráč, čo ukazuje, ako dobre sa dá hrať optimálnejšia hra.

2. Počiatočné nastavenie

Prvá vec, ktorú potrebujeme, je nastavenie, v ktorom môžeme hrať hru a sledovať, ako ide pokrok.

Získate tak všetky konštrukcie, ktoré potrebujeme na hranie hry, a úplnú implementáciu počítačového prehrávača, ktorý aj tak umiestňuje iba náhodné dlaždice. To nám potom dáva priestor na implementáciu „ľudského“ hráča, ktorý bude hrať túto hru.

2.1. Herná doska

Pred všetkým potrebujeme herný plán. Toto je mriežka buniek, do ktorej je možné umiestniť čísla.

S cieľom uľahčiť prácu s niektorými vecami, začnime jednoduchou reprezentáciou umiestnenia bunky. Toto je doslova iba obal okolo dvojice súradníc:

public class Cell {private final int x; súkromný konečný int y; // konštruktor, getri a toString}

Teraz môžeme napísať triedu, ktorá bude predstavovať samotnú tabuľu. Toto uloží hodnoty do jednoduchého dvojrozmerného poľa, ale umožní nám k nim prístup pomocou vyššie uvedeného Bunka trieda:

public class Board {private final int [] [] board; súkromné ​​konečné int skóre; public Board (int size) {this.board = new int [size] []; this.score = 0; for (int x = 0; x <size; ++ x) {this.board [x] = new int [size]; for (int y = 0; y <size; ++ y) {board [x] [y] = 0; }}} public int getSize () {return board.length; } public int getScore () {návrat skóre; } public int getCell (Cell cell) {return board [cell.getX ()] [cell.getY ()]; } public boolean isEmpty (Cell cell) {return getCell (cell) == 0; } public List emptyCells () {List result = new ArrayList (); for (int x = 0; x <board.length; ++ x) {for (int y = 0; y <board [x] .length; ++ y) {Cell cell = new Cell (x, y); if (isEmpty (cell)) {result.add (cell); }}} vrátiť výsledok; }}

Toto je nemenná trieda, ktorá predstavuje dosku a umožňuje ju vypočuť ju, aby sme zistili aktuálny stav. Tiež sleduje aktuálne skóre, ku ktorému prídeme neskôr.

2.2. Počítačový prehrávač a umiestňovanie dlaždíc

Teraz, keď máme herný plán, chceme byť schopní hrať s ním. Prvá vec, ktorú chceme, je počítačový prehrávač, pretože ide o čisto náhodný prehrávač, ktorý bude neskôr presne podľa potreby.

Počítačový hráč neurobí nič iné ako vloženie dlaždice do bunky, takže potrebujeme nejaký spôsob, ako to dosiahnuť na našej doske. Chceme, aby to nebolo nemenné, takže umiestnením dlaždice sa vygeneruje úplne nová doska v novom stave.

Najprv, chceme konštruktor, ktorý prevezme skutočný stav dosky, na rozdiel od našej staršej, ktorá práve skonštruovala prázdnu dosku:

privátna nástenka (int [] [] nástenka, int skóre) {this.score = skóre; this.board = new int [board.length] []; for (int x = 0; x <board.length; ++ x) {this.board [x] = Arrays.copyOf (board [x], board [x] .length); }}

Toto je súkromné takže ho môžu kedykoľvek použiť iba iné metódy v tej istej triede. To pomáha pri našom zapuzdrení dosky.

Ďalej pridáme metódu umiestnenia dlaždice. Týmto sa vráti úplne nová doska, ktorá je identická s aktuálnou, okrem toho, že má dané číslo v danej bunke:

public Board placeTile (Cell cell, int number) {if (! isEmpty (cell)) {throw new IllegalArgumentException ("that cell is not empty"); } Výsledok nástenky = nová nástenka (this.board, this.score); result.board [cell.getX ()] [cell.getY ()] = číslo; návratový výsledok; }

Nakoniec napíšeme novú triedu predstavujúcu počítačového hráča. Bude to mať jedinú metódu, ktorá vezme súčasnú dosku a vráti novú:

public class Computer {private final SecureRandom rng = new SecureRandom (); public Board makeMove (Board input) {List emptyCells = input.emptyCells (); double numberToPlace = rng.nextDouble (); int indexToPlace = rng.nextInt (emptyCells.size ()); Bunka cellToPlace = emptyCells.get (indexToPlace); návrat input.placeTile (cellToPlace, numberToPlace> = 0,9? 4: 2); }}

Týmto sa získa zoznam všetkých prázdnych buniek z hracej plochy, vyberie sa náhodná a potom sa do nej vloží číslo. Náhodne sa rozhodneme vložiť „4“ do bunky 10% času a „2“ ďalších 90%.

2.2. „Ľudský“ hráč a radenie dlaždíc

Ďalšia vec, ktorú potrebujeme, je „ľudský“ hráč. Nebude to konečný cieľ, ale čisto náhodný hráč, ktorý vyberie náhodný smer a posúva dlaždice vždy, keď urobí ťah. To potom bude pôsobiť ako miesto, na ktorom môžeme stavať, aby sme sa stali našim optimálnym hráčom.

Najprv musíme definovať zoznam možných pohybov, ktoré je možné vykonať:

verejné enum Posunúť {HORE, DOLE, DOĽAVA, VPRAVO}

Ďalej musíme rozšíriť Doska triedy na podporu vykonávania pohybov posúvaním dlaždíc v jednom z týchto smerov. Kvôli zjednodušeniu tu chceme otočiť dosku tak, aby sme vždy posúvali dlaždice rovnakým smerom.

To znamená, že potrebujeme prostriedky na transpozíciu a zvrátenie fóra:

private static int [] [] transpose (int [] [] input) {int [] [] result = new int [input.length] []; for (int x = 0; x <input.length; ++ x) {result [x] = new int [input [0] .length]; pre (int y = 0; y <vstup [0] .dlžka; ++ y) {výsledok [x] [y] = vstup [y] [x]; }} vrátiť výsledok; } private static int [] [] reverse (int [] [] input) {int [] [] result = new int [input.length] []; for (int x = 0; x <input.length; ++ x) {result [x] = new int [input [0] .length]; for (int y = 0; y <input [0] .length; ++ y) {result [x] [y] = input [x] [input.length - y - 1]; }} vrátiť výsledok; }

Pri transpozícii dosky sa vymenia všetky riadky a stĺpce tak, aby sa z horného okraja stal ľavý okraj. Reverzná doska to jednoducho zrkadlí tak, že z ľavého okraja sa stane pravý okraj.

Ďalej pridáme metódu do Doska urobiť pohyb v danom smere a vrátiť nový Doska v novom stave.

Začíname vytvorením kópie stavu nástenky, s ktorou potom môžeme pracovať:

presun verejnej rady (presun presunu) {int newScore = 0; // Klonujte dosku int [] [] dlaždice = nový int [this.board.length] []; for (int x = 0; x <this.board.length; ++ x) {dlaždice [x] = Arrays.copyOf (this.board [x], this.board [x] .length); }

Ďalej manipulujeme s našou kópiou tak, aby sme vždy posúvali dlaždice nahor:

if (move == Move.LEFT || move == Move.RIGHT) {dlaždice = transponovať (dlaždice); } if (move == Move.DOWN || move == Move.RIGHT) {dlaždice = reverz (dlaždice); }

Potrebujeme ešte ďalšie pole dlaždíc - tentokrát ten, do ktorého začleníme konečný výsledok - a sledovač nového skóre získaného týmto ťahom:

int [] [] výsledok = nový int [dlaždice.length] []; int newScore = 0;

Teraz, keď sme pripravení začať posúvať dlaždice, a manipulovali sme s vecami tak, aby sme vždy pracovali rovnakým smerom, môžeme začať.

Každý stĺpec môžeme posunúť nezávisle od ostatných. Musíme len iterovať cez stĺpce a opakovať, počnúc budovaním ďalšej kópie dlaždíc, ktoré posúvame.

Tentokrát ich zabudujeme do a LinkedList pretože budeme chcieť, aby sme z neho mohli ľahko vypustiť hodnoty. Tiež pridáme iba skutočné dlaždice, ktoré majú čísla, a preskočíme cez prázdne dlaždice.

Týmto sa dosahuje naše radenie, ale ešte nie zlúčenie dlaždíc:

pre (int x = 0; x <dlaždice.length; ++ x) {LinkedList thisRow = new LinkedList (); pre (int y = 0; y 0) {thisRow.add (dlaždice [x] [y]); }}

Ďalej musíme zlúčiť dlaždice. Musíme to urobiť osobitne od vyššie uvedeného; inak riskujeme, že zlúčime tú istú dlaždicu viackrát.

To sa dosiahne vybudovaním ďalšieho LinkedList z dlaždíc z vyššie uvedeného, ​​ale tentokrát sa postupne zlučujú:

LinkedList newRow = nový LinkedList (); while (thisRow.size ()> = 2) {int first = thisRow.pop (); int second = thisRow.peek (); if (druhý == prvý) {int newNumber = prvý * 2; newRow.add (newNumber); newScore + = newNumber; thisRow.pop (); } else {newRow.add (prvý); }} newRow.addAll (thisRow);

Tu tiež počítame nové skóre pre tento ťah. Toto je súčet dlaždíc vytvorených v dôsledku zlúčenia.

Teraz to môžeme zabudovať do výsledného poľa. Po vyčerpaní dlaždíc z nášho zoznamu sa zvyšok naplní hodnotou „0“, čo znamená, že sú prázdne:

 výsledok [x] = nový int [dlaždice [0] .dĺžka]; pre (int y = 0; y <dlaždice [0]. dĺžka; ++ y) {if (newRow.isEmpty ()) {výsledok [x] [y] = 0; } else {vysledok [x] [y] = newRow.pop (); }}}

Po dokončení posúvania dlaždíc musíme s nimi znova manipulovať späť do správneho otočenia. Toto je presný opak, ktorý sme urobili predtým:

if (move == Move.DOWN || move == Move.RIGHT) {result = reverse (result); } if (move == Move.LEFT || move == Move.RIGHT) {result = transpose (result); }

A nakoniec môžeme zostaviť a vrátiť novú dosku s touto novou sadou dlaždíc a novo vypočítaným skóre:

 vrátiť novú dosku (výsledok, this.score + newScore); }

Teraz sme v pozícii, kedy môžeme napísať nášho náhodného „ľudského“ hráča. Nerobí to nič iné ako vygenerovať náhodný ťah a zavolať vyššie uvedenú metódu na prehranie tohto ťahu:

public class Human {private SecureRandom rng = new SecureRandom (); public Board makeMove (vstup Board) {Move move = Move.values ​​() [rng.nextInt (4)]; návratový vstup.move (presunúť); }}

2.3. Hranie hry

Na hranie hry máme dostatok komponentov, aj keď nie veľmi úspešne. Čoskoro však budeme vylepšovať spôsob, akým Človek triedy, a to nám umožní ľahko vidieť rozdiely.

Najskôr potrebujeme spôsob, ako vytlačiť hernú dosku.

V tomto príklade tlačíme iba na konzolu, takže System.out.print je dosť dobré. Pre skutočnú hru by sme chceli urobiť lepšiu grafiku:

private static void printBoard (Board board) {StringBuilder topLines = new StringBuilder (); StringBuilder midLines = nový StringBuilder (); pre (int x = 0; x <board.getSize (); ++ x) "); topLines.append (" + "); midLines.append (" | "); for (int y = 0; y <doska .getSize (); ++ y) {System.out.println (topLines); System.out.println (midLines); for (int x = 0; x <board.getSize (); ++ x) {Bunka bunky = 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 (výstup);}} System.out.println ("|"); System.out.println (midLines);} System.out.println (topLines); System.out.println („Skóre:“ + board.getScore ());}

Sme takmer pripravení vyraziť. Musíme len zariadiť veci.

To znamená vytvoriť hraciu plochu, dvoch hráčov a nechať počítač vykonať dva počiatočné ťahy - to znamená umiestniť na hraciu plochu dve náhodné čísla:

Dosková doska = nová doska (4); Počítač počítač = nový počítač (); Človek človek = nový Človek (); pre (int i = 0; i <2; ++ i) {board = computer.makeMove (doska); }

A teraz máme skutočnú hernú slučku. Bude to opakovanie striedania ľudských a počítačových hráčov a zastavenie, až keď nezostanú žiadne prázdne bunky:

printBoard (doska); do {System.out.println ("Ľudský pohyb"); System.out.println ("=========="); doska = human.makeMove (doska); printBoard (doska); System.out.println ("Presunutie počítača"); System.out.println ("============="); doska = computer.makeMove (doska); printBoard (doska); } while (! board.emptyCells (). isEmpty ()); System.out.println ("Konečné skóre:" + board.getScore ());

V tomto okamihu, ak by sme mali spustiť program, videli by sme, že sa hrá náhodná hra z roku 2048.

3. Implementácia prehrávača 2048 Player

Keď budeme mať základňu, z ktorej budeme môcť hrať túto hru, môžeme začať implementovať „ľudského“ hráča a hrať lepšiu hru, než len vyberať náhodný smer.

3.1. Simulácia pohybov

Algoritmus, ktorý tu implementujeme, je založený na algoritme Expectimax. Ako taký, jadrom algoritmu je simulovať všetky možné pohyby, každému z nich prideliť skóre a vybrať ten, ktorý funguje najlepšie.

Streamy Java 8 budeme intenzívne využívať na pomoc pri štruktúrovaní tohto kódu, z dôvodov, ktoré uvidíme neskôr.

Začneme opätovným napísaním makeMove () metóda zvnútra našej Človek trieda:

public Board makeMove (Board input) {return Arrays.stream (Move.values ​​()) .map (input :: move) .max (Comparator.comparingInt (board -> generateScore (board, 0))) .orElse (input) ; }

Pre každý možný smer, ktorým sa môžeme pohnúť, vygenerujeme novú dosku a potom spustíme bodovací algoritmus - prihrávka v tejto doske a hĺbka 0. Potom vyberieme ťah, ktorý má najlepšie skóre.

Náš generateScore () metóda potom simuluje každý možný pohyb počítača - to znamená vloženie „2“ alebo „4“ do každej prázdnej bunky - a potom uvidí, čo sa môže stať ďalej:

private int generateScore (Board Board, Int depth) {if (depth> = 3) {return CalculateFinalScore (Board); } návrat board.emptyCells (). stream () .flatMap (bunka -> Stream.of (nový pár (bunka, 2), nový pár (bunka, 4))) .mapToInt (presun -> {doska nová doska = doska. placeTile (move.getFirst (), move.getSecond ()); int boardScore = vypočítať skóre (newBoard, depth + 1); return (int) (boardScore * (move.getSecond () == 2? 0,9: 0,1)); }) .sum (); }

Ak sme dosiahli svoj limit hĺbky, okamžite sa zastavíme a vypočítame konečné skóre toho, aká dobrá je táto doska; inak pokračujeme v našej simulácii.

Náš vypočítať skóre () Metóda je potom pokračovaním našej simulácie, prebiehajúcej po ľudskej strane rovnice.

Toto je veľmi podobné makeMove () vyššie, ale vraciame priebežné skóre namiesto skutočnej tabuľky:

private int countScore (Board board, int depth) {return Arrays.stream (Move.values ​​()) .map (board :: move) .mapToInt (newBoard -> generateScore (newBoard, depth)) .max () .orElse ( 0); }

3.2. Bodovanie finálových tabúľ

Teraz sme v situácii, keď môžeme simulovať pohyby tam a späť hráčmi na človeka a počítač, a zastavíme sa, keď ich už nasimulujeme dosť. Musíme byť schopní vygenerovať skóre pre výsledkovú dosku v každej vetve simulácie, aby sme videli, ktorá vetva je tou, ktorú chceme sledovať.

Naše bodovanie je kombináciou faktorov, z ktorých každý použijeme na každý riadok a každý stĺpec na tabuli. Všetky sa spočítajú a celková suma sa vráti.

Preto musíme vygenerovať zoznam riadkov a stĺpcov, ktoré budú hodnotiť:

Zoznam RowToScore = new ArrayList (); pre (int i = 0; i <board.getSize (); ++ i) {riadok zoznamu = nový ArrayList (); Zoznam col = new ArrayList (); for (int j = 0; j <board.getSize (); ++ j) {row.add (board.getCell (new Cell (i, j)))); col.add (board.getCell (nová bunka (j, i))); } riadkyToScore.add (riadok); RowToScore.add (col); }

Potom vezmeme zoznam, ktorý sme vytvorili, skórujeme každý z nich a sumarizujeme skóre. Toto je zástupný symbol, ktorý sa chystáme vyplniť:

návrat RowToScore.stream () .mapToInt (riadok -> {int skóre = 0; návratové skóre;}) .sum ();

Nakoniec musíme skutočne vygenerovať naše skóre. Toto ide dovnútra vyššie uvedenej lambdy a je to niekoľko rôznych faktorov, ktoré všetky prispievajú:

• Pevné skóre pre každý riadok
• Súčet každého čísla v riadku
• Každé možné zlúčenie v rade
• Každá prázdna bunka v rade
• Monotónnosť radu. Toto predstavuje množstvo, ktoré je riadok usporiadaný vo vzostupnom číselnom poradí.

Predtým, ako budeme môcť vypočítať skóre, musíme zostaviť nejaké ďalšie údaje.

Najprv chceme zoznam čísel s odstránenými prázdnymi bunkami:

Zoznam preMerged = row.stream () .filter (hodnota -> hodnota! = 0) .collect (Collectors.toList ());

Potom môžeme z tohto nového zoznamu urobiť nejaké počty, ktoré dajú počet susedných buniek s rovnakým počtom, s prísne stúpajúcimi číslami a striktne klesajúcimi číslami:

int numMerges = 0; int monotonicita Vľavo = 0; int monotonicitaRight = 0; for (int i = 0; i second) {monotonicityLeft + = first - second; } else {monotonicitaRight + = second - first; }}

Teraz môžeme vypočítať naše skóre pre tento riadok:

int skóre = 1 000; skóre + = 250 * riadok.prúd (). filter (hodnota -> hodnota == 0) .počet (); skóre + = 750 * numMerges; skóre - = 10 * riadok.stream (). mapToInt (hodnota -> hodnota) .sum (); skóre - = 50 * matematický.min (monotónnosť vľavo, monotónnosť vpravo); skóre návratu;

Tu vybrané čísla sú relatívne ľubovoľné. Rôzne čísla budú mať vplyv na to, ako dobre hra hrá, pričom budú uprednostňované rôzne faktory v tom, ako hráme.

4. Vylepšenia algoritmu

To, čo zatiaľ máme, funguje a vidíme, že hrá dobrú hru, ale je to pomalé. Na pohyb človeka to trvá asi 1 minútu. Môžeme urobiť lepšie ako toto.

4.1. Paralelné spracovanie

Je zrejmé, že môžeme urobiť prácu paralelne. To je obrovská výhoda práce s prúdmi Java - túto prácu môžeme dosiahnuť paralelne tak, že do každého streamu pridáme jeden príkaz.

Samotná táto zmena nás zníži na približne 20 sekúnd na pohyb.

4.2. Prerezávanie nehrateľných vetiev

Ďalšia vec, ktorú môžeme urobiť, je orezať všetky vetvy, ktoré sú nehrateľné. Teda kedykoľvek, keď bude mať ľudský pohyb za následok nezmenenú dosku. Toto sú takmer určite odvetvia, ktoré povedú k horším výsledkom - skutočne poskytujú počítaču voľný pohyb - ale stojí ich čas, aby sme ich sledovali.

Aby sme to dosiahli, musíme do našej implementovať metódu rovnosti Doska aby sme ich mohli porovnať:

@Override public boolean equals (Object o) {if (this == o) {return true; } if (o == null || getClass ()! = o.getClass ()) {return false; } Board board1 = (Board) o; return Arrays.deepEquals (board, board1.board); }

Potom môžeme pridať niektoré filtre do našich streamovacích potrubí, aby sme zastavili spracovanie všetkého, čo sa nezmenilo.

návrat Arrays.stream (Move.values ​​()) .parallel () .map (board :: move) .filter (Move ->! Move.equals (Board)) ........

To má minimálny vplyv na prvé časti hry - keď je vyplnených buniek veľmi málo, je len veľmi málo ťahov, ktoré je možné orezať. Neskôr to však začne mať oveľa väčší vplyv, a to tak, že sa časy presunu znížia iba na niekoľko sekúnd.

5. Zhrnutie

Tu sme vytvorili rámec pre hranie hry 2048. Potom sme do toho napísali riešiteľa, aby sme mohli hrať lepšiu hru. Všetky tu zobrazené príklady nájdete na GitHub.

Prečo neskúsiť zmeniť pravidlá a zistiť, aký majú dopad na hrateľnosť.