streamalism.org

1. Uvod

Nedavno smo pogledali algoritam za rješavanje igre 2048. O tome smo razgovarali s teoretskog gledišta, a ne sa stvarnim kodom koji stoji iza toga.

Ovdje ćemo napisati implementaciju ovoga u Javi. Ovo će igrati i kao ljudski i kao računarski igrač, pokazujući kako se može igrati optimalnija igra.

2. Početno postavljanje

Prvo što nam treba je postavka u kojoj možemo igrati igru ​​i vidjeti kako napreduje.

To će nam pružiti sve konstrukcije potrebne za igranje igre i u potpunosti implementirati računalni player - koji ionako postavlja samo slučajne pločice. To nam onda daje opseg da implementiramo "ljudskog" igrača za igranje igre.

2.1. Ploča za igru

Prije svega, trebamo ploču za igru. Ovo je mreža stanica u koje se mogu smjestiti brojevi.

Da bi s nekim stvarima bilo malo lakše raditi, započnimo s jednostavnim prikazom mjesta stanice. Ovo je doslovno samo omot oko par koordinata:

javna klasa Cell {private final int x; privatni konačni int y; // konstruktor, getteri i toString}

Sada možemo napisati razred koji će predstavljati sam odbor. Ovo će pohraniti vrijednosti u jednostavan dvodimenzionalni niz, ali omogućiti nam pristup njima putem gore navedenog Ćelija razred:

javna klasa Board {private final int [] [] ploča; privatni konačni int rezultat; javna ploča (int veličina) {this.board = nova int [veličina] []; this.score = 0; za (int x = 0; x <size; ++ x) {this.board [x] = new int [size]; za (int y = 0; y <veličina; ++ y) {ploča [x] [y] = 0; }}} public int getSize () {return board.length; } javni int getScore () {povratni rezultat; } public int getCell (ćelijska ćelija) {povratna ploča [cell.getX ()] [cell.getY ()]; } javna logička vrijednost isEmpty (ćelija ćelije) {return getCell (ćelija) == 0; } javni popis emptyCells () {Rezultat popisa = novi 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 (ćelija)) {result.add (ćelija); }}} vrati rezultat; }}

Ovo je nepromjenjiva klasa koja predstavlja ploču i omogućuje nam da je ispitujemo kako bismo saznali trenutno stanje. Također bilježi trenutni rezultat, do kojeg ćemo doći kasnije.

2.2. Računalni player i postavljanje pločica

Sad kad imamo ploču za igru, želimo se moći igrati s njom. Prvo što želimo je računalni uređaj, jer je riječ o potpuno slučajnom uređaju i kasnije će biti točno onakav kakav je potreban.

Računalni uređaj ne radi ništa više nego postavlja pločicu u ćeliju, tako da trebamo neki način da to postignemo na našoj ploči. Želimo da ovo ostane nepromjenjivo, pa će postavljanje pločice generirati potpuno novu ploču u novom stanju.

Prvi, želimo konstruktor koji će uzeti stvarno stanje ploče, za razliku od naše prethodne koja je upravo napravila praznu ploču:

privatna ploča (int [] [] ploča, int rezultat) {this.score = score; this.board = novi int [board.length] []; for (int x = 0; x <board.length; ++ x) {this.board [x] = Arrays.copyOf (board [x], board [x] .length); }}

Ovo je privatni tako da se ikad može koristiti samo drugim metodama unutar iste klase. To pomaže u našem kapsuliranju ploče.

Zatim ćemo dodati metodu za postavljanje pločice. Ovo vraća potpuno novu ploču koja je identična trenutnoj, osim što ima zadani broj u datoj ćeliji:

javna ploča placeTile (ćelijska ćelija, int broj) {if (! isEmpty (cell)) {throw new IllegalArgumentException ("Ta ćelija nije prazna"); } Rezultat ploče = nova ploča (this.board, this.score); result.board [cell.getX ()] [cell.getY ()] = broj; povratni rezultat; }

Konačno, napisat ćemo novu klasu koja predstavlja računalni uređaj. Ovo će imati jednu metodu koja će uzeti trenutnu ploču i vratiti novu:

javna klasa Računalo {private final SecureRandom rng = new SecureRandom (); javni Board makeMove (ulaz na ploči) {List emptyCells = input.emptyCells (); dvostruki numberToPlace = rng.nextDouble (); int indexToPlace = rng.nextInt (emptyCells.size ()); Cell cellToPlace = emptyCells.get (indexToPlace); vrati input.placeTile (cellToPlace, numberToPlace> = 0,9? 4: 2); }}

Ovo dobiva popis svih praznih ćelija s ploče, bira slučajnu i zatim u nju stavlja broj. Slučajno ćemo odlučiti staviti "4" u ćeliju 10% vremena, a "2" ostalih 90%.

2.2. "Ljudski" igrač i pločice koje se mijenjaju

Sljedeće što nam treba je "ljudski" igrač. Ovo neće biti krajnji cilj, već čisto slučajni igrač koji odabire slučajni smjer za pomicanje pločica svaki put kad napravi potez. To će tada djelovati kao mjesto na kojem se možemo nadograditi kako bismo stvorili našeg optimalnog igrača.

Prvo, moramo definirati nabrajanje mogućih poteza koji se mogu povući:

javni popis Premjesti {GORE, DOLJE, LIJEVO, DESNO}

Dalje, moramo povećati Odbor klase za potporu u pokretanju pomicanjem pločica u jednom od ovih smjerova. Da bismo ovdje smanjili složenost, želimo ploču zakrenuti tako da pločice uvijek pomičemo u istom smjeru.

To znači da su nam potrebna sredstva i za transponiranje i za okretanje ploče:

privatni statički int [] [] transpose (int [] [] input) {int [] [] rezultat = novi int [input.length] []; za (int x = 0; x <input.length; ++ x) {rezultat [x] = novi int [input [0] .length]; for (int y = 0; y <input [0] .length; ++ y) {result [x] [y] = input [y] [x]; }} vratiti rezultat; } privatni statički int [] [] obrnuti (int [] [] ulaz) {int [] [] rezultat = novi int [input.length] []; za (int x = 0; x <input.length; ++ x) {rezultat [x] = novi int [input [0] .length]; for (int y = 0; y <input [0] .length; ++ y) {result [x] [y] = input [x] [input.length - y - 1]; }} vratiti rezultat; }

Transponiranjem ploče zamijenit će se svi redovi i stupci okolo, tako da gornji rub postane lijevi rub. Obrnutim dijelom ploče jednostavno se zrcali tako da lijevi rub postane desni.

Dalje, dodamo metodu u Odbor povući potez u zadanom smjeru i vratiti novi Odbor u novoj državi.

Počinjemo s izradom kopije ploče na kojoj možemo zatim raditi:

potez javne ploče (Premjesti potez) {int newScore = 0; // Kloniranje ploče int [] [] pločice = novi int [this.board.length] []; for (int x = 0; x <this.board.length; ++ x) {pločice [x] = Nizovi.copyOf (this.board [x], this.board [x] .length); }

Dalje, manipuliramo našom kopijom tako da ćemo uvijek pomicati pločice prema gore:

if (move == Move.LEFT || move == Move.RIGHT) {pločice = transponirati (pločice); } if (move == Move.DOWN || move == Move.RIGHT) {pločice = obrnuto (pločice); }

Treba nam još jedan niz pločica - ovaj put onaj u koji ćemo ugraditi konačni rezultat - i tragač za novim rezultatom postignutim za ovaj potez:

int [] [] rezultat = novi int [pločice.dužina] []; int newScore = 0;

Sad kad smo spremni započeti s pomicanjem pločica i izmanipulirali smo stvari tako da uvijek radimo u istom smjeru, možemo početi.

Možemo pomicati svaki stupac neovisno od ostalih. Samo trebamo preći preko stupaca i ponoviti, počevši od izrade još jedne kopije pločica koje premještamo.

Ovaj put ih ugrađujemo u LinkedList jer ćemo htjeti moći iz toga lako izbaciti vrijednosti. Također dodajemo samo stvarne pločice koje imaju brojeve i preskaču prazne pločice.

Ovo postiže naše pomicanje, ali još uvijek ne spajanje pločica:

za (int x = 0; x <pločice.duljina; ++ x) {LinkedList thisRow = novi LinkedList (); for (int y = 0; y 0) {thisRow.add (pločice [x] [y]); }}

Dalje, moramo spojiti pločice. To moramo učiniti odvojeno od gore navedenog; u suprotnom riskiramo spajanje iste pločice više puta.

To se postiže izgradnjom drugog LinkedList pločica iz gore navedenog, ali ovaj put se spaja u hodu:

LinkedList newRow = novi LinkedList (); while (thisRow.size ()> = 2) {int first = thisRow.pop (); int drugo = thisRow.peek (); if (drugo == prvo) {int newNumber = prvo * 2; newRow.add (noviBroj); newScore + = newNumber; thisRow.pop (); } else {newRow.add (prvi); }} newRow.addAll (thisRow);

Ovdje također izračunavamo novi rezultat za ovaj potez. Ovo je zbroj pločica stvorenih kao rezultat spajanja.

Sada to možemo ugraditi u polje rezultata. Nakon što nam ponestane pločica s popisa, ostatak se popunjava vrijednošću "0" da bi se naznačilo da su prazne:

 rezultat [x] = novi int [pločice [0] .dužina]; za (int y = 0; y <pločice [0] .dužina; ++ y) {if (newRow.isEmpty ()) {rezultat [x] [y] = 0; } else {rezultat [x] [y] = newRow.pop (); }}}

Kad završimo s pomicanjem pločica, trebamo ih ponovno manipulirati natrag u ispravnu rotaciju. To je upravo suprotno što smo učinili ranije:

if (move == Move.DOWN || move == Move.RIGHT) {rezultat = obrnuto (rezultat); } if (move == Move.LEFT || move == Move.RIGHT) {rezultat = transponiranje (rezultat); }

I konačno, možemo izgraditi i vratiti novu ploču s ovim novim setom pločica i novo izračunati rezultat:

 vratiti novu ploču (rezultat, this.score + newScore); }

Sad smo u poziciji da možemo napisati svog slučajnog "ljudskog" igrača. To ne čini ništa drugo nego generiranje slučajnog poteza i pozivanje gornje metode za reprodukciju tog poteza:

javna klasa Human {private SecureRandom rng = new SecureRandom (); javna zajednica makeMove (unos ploče) {Premjesti potez = Premjesti.value () [rng.nextInt (4)]; povratak input.move (pomicanje); }}

2.3. Igranje igre

Imamo dovoljno komponenata za igranje igre, iako ne baš uspješno. Međutim, uskoro ćemo poboljšati način na koji Ljudski razredne igre, a to će nam omogućiti da lako uočimo razlike.

Prvo, trebamo način ispisa ploče za igru.

U ovom ćemo primjeru samo ispisati na konzolu System.out.print je dovoljno dobro. Za pravu igru ​​željeli bismo napraviti bolju grafiku:

privatna statička praznina printBoard (ploča ploče) {StringBuilder topLines = novi StringBuilder (); StringBuilder midLines = novi StringBuilder (); for (int x = 0; x <board.getSize (); ++ x) "); topLines.append (" + "); midLines.append (" | "); for (int y = 0; y <ploča .getSize (); ++ y) {System.out.println (topLines); System.out.println (midLines); for (int x = 0; x <board.getSize (); ++ x) {Cell cell = nova ćelija (x, y); System.out.print ("|"); if (board.isEmpty (cell)) {System.out.print ("");} else {StringBuilder output = new StringBuilder (Integer .toString (board.getCell (ćelija))); 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 ("Ocjena:" + board.getScore ());}

Skoro smo spremni za polazak. Moramo samo postaviti stvari.

To znači stvaranje ploče, dva igrača i navođenje računala na dva početna poteza - to jest postavljanje dva slučajna broja na ploču:

Ploča ploče = nova ploča (4); Računalno računalo = novo Računalo (); Ljudski čovjek = novi Čovjek (); za (int i = 0; i <2; ++ i) {ploča = računalo.makeMove (ploča); }

I sada imamo stvarnu petlju igre. Ovo će biti ponavljanje ljudskih i računalnih igrača koji se izmjenjuju i zaustavljaju samo kada ne ostanu prazne stanice:

printBoard (ploča); do {System.out.println ("Ljudski potez"); System.out.println ("=========="); ploča = human.makeMove (ploča); printBoard (ploča); System.out.println ("Premještanje računala"); System.out.println ("============="); ploča = računalo.makeMove (ploča); printBoard (ploča); } while (! board.emptyCells (). isEmpty ()); System.out.println ("Konačna ocjena:" + board.getScore ());

U ovom trenutku, ako bismo pokrenuli program, vidjeli bismo da se igra slučajna igra 2048. godine.

3. Implementacija programa 2048 Player

Jednom kada imamo bazu iz koje ćemo igrati igru, možemo početi implementirati "ljudskog" igrača i igrati bolju igru ​​od pukog odabira slučajnog smjera.

3.1. Simulacija poteza

Algoritam koji ovdje implementiramo temelji se na algoritmu Expectimax. Kao takav, srž algoritma je simulirati svaki mogući potez, dodijeliti rezultat svakom i odabrati onaj koji najbolje prolazi.

Iskoristit ćemo Java 8 Streams za pomoć u strukturiranju ovog koda iz razloga koje ćemo vidjeti kasnije.

Počet ćemo s ponovnim pisanjem makeMove () metoda iznutra naše Ljudski razred:

javna ploča makeMove (ulaz ploče) {return Arrays.stream (Move.values ​​()) .map (input :: move) .max (Comparator.comparingInt (ploča -> generirajScore (ploča, 0))). orElse (ulaz) ; }

Za svaki mogući smjer u kojem se možemo kretati, generiramo novu ploču, a zatim započinjemo algoritam bodovanja - dodavanje u ovu ploču i dubina 0. Zatim odabiremo potez koji ima najbolji rezultat.

Naše generiratiScore () metoda zatim simulira svaki mogući potez računala - to jest stavljanje "2" ili "4" u svaku praznu ćeliju - i zatim vidi što bi se moglo dogoditi sljedeće:

privatni int generiratiScore (ploča ploče, dubina int) {if (dubina> = 3) {povratak izračunatiFinalScore (ploča); } return board.emptyCells (). stream () .flatMap (cell -> Stream.of (new Pair (cell, 2), new Pair (cell, 4))) .mapToInt (move -> {Board newBoard = board. placeTile (move.getFirst (), move.getSecond ()); int boardScore = izračunajScore (nova ploča, dubina + 1); vrati se (int) (boardScore * (move.getSecond () == 2? 0,9: 0,1)); }) .sum (); }

Ako smo dosegli ograničenje dubine, odmah ćemo se zaustaviti i izračunati konačni rezultat koliko je dobra ova ploča; u suprotnom nastavljamo s našom simulacijom.

Naše izračunaj rezultat () metoda je tada nastavak naše simulacije, pokrećući jednadžbu na strani čovjeka.

Ovo je vrlo slično makeMove () gornju metodu, ali vraćamo tekući rezultat umjesto stvarne ploče:

private int izračunatiScore (ploča ploče, dubina int) {return Arrays.stream (Move.values ​​()) .map (board :: move) .mapToInt (newBoard -> generirajScore (newBoard, dubina)) .max () .orElse ( 0); }

3.2. Bodovanje konačnih ploča

Sad smo u situaciji kada možemo simulirati pokrete i nazad ljudi i računala, zaustavljajući se kad smo ih simulirali. Moramo biti sposobni generirati rezultat za konačnu ploču u svakoj grani simulacije, kako bismo mogli vidjeti koja je grana ona koju želimo nastaviti.

Naše bodovanje kombinacija je čimbenika, od kojih ćemo svaki primijeniti na svaki redak i svaki stupac na ploči. Sve se zbrajaju i vraća se zbroj.

Kao takvi, moramo generirati popis redaka i stupaca za ocjenu:

Popis redoviToScore = novi ArrayList (); for (int i = 0; i <board.getSize (); ++ i) {Redak popisa = novi ArrayList (); Popis col = novi ArrayList (); for (int j = 0; j <board.getSize (); ++ j) {row.add (board.getCell (nova ćelija (i, j))); col.add (board.getCell (nova Ćelija (j, i))); } redoviToScore.add (redak); redoviToScore.add (col); }

Zatim uzmemo popis koji smo napravili, ocjenjujemo svakog od njih i zajedno zbrajamo bodove. Ovo je rezervirano mjesto koje ćemo popuniti:

vratiti redoveToScore.stream () .mapToInt (redak -> {int rezultat = 0; povrat rezultat;}) .sum ();

Konačno, zapravo moramo generirati svoje rezultate. To se nalazi unutar gornje lambde i nekoliko je različitih čimbenika koji svi doprinose:

• Fiksni rezultat za svaki red
• Zbroj svakog broja u redu
• Svako spajanje moguće u nizu
• Svaka prazna ćelija u redu
• Monotonost reda. To predstavlja iznos koji je red organiziran u rastućem numeričkom redoslijedu.

Prije nego što možemo izračunati rezultate, moramo stvoriti neke dodatne podatke.

Prvo, želimo popis brojeva s uklonjenim praznim ćelijama:

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

Tada možemo izvršiti neke brojeve s ovog novog popisa, dajući broj susjednih ćelija s istim brojem, sa strogo rastućim brojevima i strogo silaznim brojevima:

int numMerges = 0; int monotonostLeft = 0; int monotonostRight = 0; for (int i = 0; i second) {monotonicityLeft + = first - second; } else {monotoničnostRight + = second - first; }}

Sada možemo izračunati naš rezultat za ovaj redak:

int rezultat = 1000; ocjena + = 250 * row.stream (). filter (vrijednost -> vrijednost == 0) .count (); ocjena + = 750 * numMerges; rezultat - = 10 * row.stream (). mapToInt (vrijednost -> vrijednost) .sum (); rezultat - = 50 * Math.min (monotonicityLeft, monotonicityRight); povratni rezultat;

Brojevi ovdje odabrani su relativno proizvoljni. Različiti brojevi utjecati će na to koliko dobro igra igra, dajući prednost različitim čimbenicima u našem igranju.

4. Poboljšanja algoritma

Ovo što imamo do sada djeluje i možemo vidjeti da igra dobru utakmicu, ali sporo. Potrebno je oko 1 minute po ljudskom potezu. Možemo i bolje od ovoga.

4.1. Paralelna obrada

Očito što možemo učiniti je raditi paralelno. Ovo je velika prednost rada s Java Streamsom - to možemo raditi paralelno dodavanjem samo jedne izjave u svaki tok.

Sama ova promjena smanjuje nas na oko 20 sekundi po potezu.

4.2. Rezidba grana koje se ne mogu igrati

Sljedeće što možemo učiniti je orezati sve grane koje se ne mogu igrati. Odnosno, svaki put kad ljudski potez rezultira nepromijenjenom pločom. To su gotovo sigurno grane koje će rezultirati lošijim ishodima - oni zapravo daju računalu slobodan potez, ali koštaju nas vremena za obradu da bismo ih slijedili.

Da bismo to učinili, moramo primijeniti metodu jednakih na našoj Odbor kako bismo ih mogli usporediti:

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

Zatim možemo dodati neke filtre u naše protočne cjevovode kako bismo zaustavili obradu svega što se nije promijenilo.

return Arrays.stream (Move.values ​​()). paralelno () .map (board :: move) .filter (preseljeno ->! preseljeno.equals (ploča)) ........

To ima minimalan utjecaj na rane dijelove sviranja - kad je vrlo malo ispunjenih stanica, vrlo je malo poteza koji se mogu obrezati. Međutim, kasnije to počinje imati mnogo veći utjecaj, smanjujući vrijeme premještanja na samo nekoliko sekundi.

5. Sažetak

Ovdje smo izgradili okvir za igranje igre 2048. Zatim smo u to napisali rješivač kako bismo mogli igrati bolju igru. Svi ovdje prikazani primjeri mogu se naći na GitHubu.

Zašto ne pokušati mijenjati pravila da biste vidjeli kako utječu na igranje.