streamalism.org

1. Introduksjon

Nylig så vi på en algoritme for å løse spillet 2048. Vi diskuterte dette fra et teoretisk synspunkt, og ikke med noen reell kode bak.

Her skal vi skrive en implementering av dette på Java. Dette vil spille som både menneskelige og dataspillere, og viser hvor godt et mer optimalt spill kan spilles.

2. Første oppsett

Det første vi trenger er et oppsett der vi kan spille spillet og se hvordan fremgangen går.

Dette vil gi oss alle konstruksjonene vi trenger for å spille spillet, og implementere dataspilleren - som bare plasserer tilfeldige fliser uansett. Dette gir oss muligheten til å implementere en “menneskelig” spiller for å spille spillet.

2.1. Brettspill

Før noe annet trenger vi et spillbrett. Dette er et rutenett av celler som tall kan plasseres i.

For å gjøre noen ting litt lettere å jobbe med, la oss begynne med en enkel fremstilling av en celleplassering. Dette er bokstavelig talt bare en innpakning rundt et par koordinater:

offentlig klasse Cell {privat finale int x; privat finalen; // konstruktør, getters og toString}

Vi kan nå skrive en klasse for å representere styret selv. Dette kommer til å lagre verdiene i en enkel todimensjonal matrise, men la oss få tilgang til dem via ovennevnte Celle klasse:

public class Board {private final int [] [] board; privat endelig int score; public Board (int size) {this.board = new int [size] []; this.score = 0; for (int x = 0; x <størrelse; ++ x) {this.board [x] = ny int [størrelse]; for (int y = 0; y <størrelse; ++ y) {bord [x] [y] = 0; }}} public int getSize () {return board.length; } public int getScore () {retur score; } public int getCell (Cell cell) {return board [cell.getX ()] [cell.getY ()]; } offentlig boolsk isEmpty (Cellecelle) {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); }}} returner resultat; }}

Dette er en uforanderlig klasse som representerer et brett og lar oss forhøre det for å finne ut den nåværende tilstanden. Det holder også oversikt over en nåværende poengsum, som vi kommer til senere.

2.2. En datamaskinspiller og plassering av fliser

Nå som vi har fått et spillbrett, vil vi kunne spille med det. Det første vi vil ha er dataspilleren, fordi dette er en rent tilfeldig spiller og vil være nøyaktig etter behov senere.

Dataspilleren gjør ikke annet enn å plassere en flis i en celle, så vi trenger noen måte å oppnå det på brettet vårt. Vi vil beholde dette som uforanderlig, så plassering av fliser vil generere et helt nytt brett i den nye staten.

Først, vi vil ha en konstruktør som tar den faktiske styretilstanden, i motsetning til vår tidligere som nettopp konstruerte et tomt brett:

private Board (int [] [] board, int score) {this.score = score; this.board = new int [board.length] []; for (int x = 0; x <board.length; ++ x) {this.board [x] = Arrays.copyOf (board [x], board [x] .length); }}

Dette er privat slik at den bare kan brukes av andre metoder innen samme klasse. Dette hjelper med innkapslingen av tavlen.

Deretter legger vi til en metode for å plassere en flis. Dette returnerer et helt nytt brett som er identisk med det nåværende, bortsett fra at det har gitt nummer i den gitte cellen:

public Board placeTile (Cellecelle, int-nummer) {if (! isEmpty (cell)) {throw new IllegalArgumentException ("At cellen er ikke tom"); } Board result = new Board (this.board, this.score); result.board [cell.getX ()] [cell.getY ()] = tall; returresultat; }

Endelig, vi skriver en ny klasse som representerer en dataspiller. Dette vil ha en enkelt metode som tar det nåværende styret og returnerer det nye:

offentlig klasse Datamaskin {privat finale SecureRandom rng = ny SecureRandom (); public Board makeMove (Board input) {List emptyCells = input.emptyCells (); dobbel numberToPlace = rng.nextDouble (); int indexToPlace = rng.nextInt (emptyCells.size ()); Cell cellToPlace = emptyCells.get (indexToPlace); return input.placeTile (cellToPlace, numberToPlace> = 0,9? 4: 2); }}

Dette får listen over hver tomme celle fra tavlen, plukker en tilfeldig og legger deretter et tall i den. Vi vil tilfeldig bestemme oss for å sette en "4" i cellen 10% av tiden, og en "2" den andre 90%.

2.2. En “menneskelig” spiller og skiftende fliser

Det neste vi trenger er en “menneskelig” spiller. Dette kommer ikke til å bli sluttmålet, men en rent tilfeldig spiller som velger en tilfeldig retning for å skifte flisene hver gang det gjør et trekk. Dette vil da fungere som et sted vi kan bygge videre på for å gjøre vår optimale spiller.

For det første må vi definere en oppregning av mulige trekk som kan gjøres:

offentlig enum Flytt {OPP, NED, VENSTRE, HØYRE}

Deretter må vi utvide Borde klasse for å støtte trekk ved å flytte fliser i en av disse retningene. For å redusere kompleksiteten her, vil vi rotere brettet slik at vi alltid skifter fliser i samme retning.

Dette betyr at vi trenger et middel både for å transponere og reversere brettet:

privat statisk int [] [] transponere (int [] [] inngang) {int [] [] resultat = ny 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 [y] [x]; }} returner resultat; } privat statisk int [] [] omvendt (int [] [] inngang) {int [] [] resultat = ny 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]; }} returner resultat; }

Transponering av brettet bytter alle rader og kolonner rundt, slik at den øverste kanten blir venstre kant. Å snu brettet speiler ganske enkelt det slik at venstre kant blir høyre kant.

Deretter legger vi til en metode for Borde å gjøre et trekk i en gitt retning, og returnere en ny Borde i den nye staten.

Vi begynner med å lage en kopi av tavlestaten som vi deretter kan jobbe med:

public Board move (Move move) {int newScore = 0; // Klone brettet int [] [] tile = new int [this.board.length] []; for (int x = 0; x <this.board.length; ++ x) {tile [x] = Arrays.copyOf (this.board [x], this.board [x] .length); }

Deretter manipulerer vi kopien vår slik at vi alltid skal flytte fliser opp:

if (move == Move.LEFT || move == Move.RIGHT) {fliser = transponere (fliser); } if (move == Move.DOWN || move == Move.RIGHT) {tile = reverse (tile); }

Vi trenger enda et utvalg av fliser - denne gangen det vi vil bygge det endelige resultatet i - og en tracker for den nye poengsummen som er oppnådd for dette trekket:

int [] [] resultat = ny int [tile.length] []; int newScore = 0;

Nå som vi er klare til å begynne å skifte fliser, og vi har manipulert ting slik at vi alltid jobber i samme retning, kan vi begynne.

Vi kan skifte hver kolonne uavhengig av de andre. Vi trenger bare å gjenta kolonnene og gjenta, og begynne med å bygge enda en kopi av flisene vi skifter.

Denne gangen bygger vi dem inn i en LinkedList fordi vi ønsker å være i stand til å slå verdier av det enkelt. Vi legger også bare til de faktiske flisene som har tall og hopper over tomme fliser.

Dette oppnår vår skifting, men ennå ikke sammenslåing av fliser:

for (int x = 0; x <tile.length; ++ x) {LinkedList thisRow = new LinkedList (); for (int y = 0; y 0) {thisRow.add (fliser [x] [y]); }}

Deretter må vi slå sammen fliser. Vi må gjøre dette separat fra det ovennevnte; Ellers risikerer vi å slå sammen den samme flisen flere ganger.

Dette oppnås ved å bygge en annen LinkedList av flisene fra ovenstående, men denne gangen smelter vi sammen mens vi går:

LinkedList newRow = ny LinkedList (); mens (thisRow.size ()> = 2) {int først = thisRow.pop (); int sekund = thisRow.peek (); hvis (andre == først) {int newNumber = første * 2; newRow.add (newNumber); newScore + = newNumber; thisRow.pop (); } annet {newRow.add (første); }} newRow.addAll (thisRow);

Her beregner vi også den nye poengsummen for dette trekket. Dette er summen av flisene som er opprettet som et resultat av sammenslåinger.

Vi kan nå bygge dette inn i resultatoppstillingen. Når vi har gått tom for fliser fra listen vår, blir resten fylt med verdien "0" for å indikere at de er tomme:

 resultat [x] = ny int [fliser [0] .lengde]; for (int y = 0; y <tile [0] .length; ++ y) {if (newRow.isEmpty ()) {result [x] [y] = 0; } annet {resultat [x] [y] = newRow.pop (); }}}

Når vi er ferdig med å skifte fliser, må vi manipulere dem igjen til riktig rotasjon. Dette er det stikk motsatte som vi gjorde tidligere:

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

Og til slutt kan vi bygge og returnere et nytt brett med dette nye settet med fliser og den nylig beregnede poengsummen:

 returner nytt styre (resultat, this.score + newScore); }

Vi er nå i en posisjon der vi kan skrive vår tilfeldige "menneskelige" spiller. Dette gjør ingenting mer enn å generere et tilfeldig trekk og kalle metoden ovenfor for å spille det trekket:

offentlig klasse Human {private SecureRandom rng = ny SecureRandom (); public Board makeMove (Board input) {Move move = Move.values ​​() [rng.nextInt (4)]; returinngang. flytt (flytt); }}

2.3. Spille spillet

Vi har nok komponenter til å spille spillet, om enn ikke veldig vellykket. Imidlertid vil vi snart forbedre måten Menneskelig klassespill, og dette vil tillate oss å se forskjellene enkelt.

Først trenger vi en måte å skrive ut spillbrettet på.

For dette eksemplet skal vi bare skrive ut til konsollen, så System.out.print er god nok. For et ekte spill vil vi lage bedre grafikk:

privat statisk ugyldig printBoard (Board board) {StringBuilder topLines = new StringBuilder (); StringBuilder midLines = nye 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) {Cellecelle = 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 ("Score:" + board.getScore ());}

Vi er nesten klare. Vi trenger bare å sette opp ting.

Dette betyr at du oppretter brettet, de to spillerne og får datamaskinen til å gjøre to innledende trekk - det vil si å plassere to tilfeldige tall på brettet:

Styrestyret = nytt styre (4); Datamaskin = ny datamaskin (); Menneske menneske = nytt menneske (); for (int i = 0; i <2; ++ i) {board = computer.makeMove (board); }

Og nå har vi selve spillløkken. Dette kommer til å være en repetisjon av menneskelige og dataspillere som svinger, og stopper bare når det ikke er tomme celler igjen:

printBoard (bord); gjør {System.out.println ("Human move"); System.out.println ("==========="); brett = human.makeMove (brett); printBoard (bord); System.out.println ("Computer move"); System.out.println ("=============="); brett = computer.makeMove (brett); printBoard (bord); } mens (! board.emptyCells (). erEmpty ()); System.out.println ("Final Score:" + board.getScore ());

På dette punktet, hvis vi skulle kjøre programmet, ville vi se et tilfeldig spill på 2048 som ble spilt.

3. Implementering av 2048 Player

Når vi har en base for å spille spillet fra, kan vi begynne å implementere den "menneskelige" spilleren og spille et bedre spill enn bare å velge en tilfeldig retning.

3.1. Simulering av bevegelser

Algoritmen vi implementerer her er basert på Expectimax-algoritmen. Som sådan, kjernen i algoritmen er å simulere alle mulige trekk, tildele en poengsum til hver enkelt og velge den som gjør det best.

Vi bruker tungt Java 8 Streams for å hjelpe til med å strukturere denne koden, av grunner vi ser senere.

Vi starter med å skrive om makeMove () metode fra innsiden av vår Menneskelig klasse:

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

For hver mulige retning vi kan bevege oss i, genererer vi det nye tavlen og starter deretter scoringsalgoritmen - passering i dette brettet og en dybde på 0. Vi velger deretter det trekket som har best poengsum.

Våre generereScore () metoden simulerer deretter alle mulige datamaskinflyttinger - det vil si å plassere enten en "2" eller en "4" i hver tomme celle - og så se hva som kan skje videre:

private int generereScore (Board board, int depth) {if (depth> = 3) {return calcinalFinalScore (board); } 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 = calculateScore (newBoard, depth + 1); return (int) (boardScore * (move.getSecond () == 2? 0.9: 0.1)); }) .sum (); }

Hvis vi har nådd dybdegrensen, stopper vi umiddelbart og beregner en endelig poengsum for hvor bra dette brettet er. Ellers fortsetter vi med simuleringen.

Våre beregne score () metoden er deretter fortsettelsen av simuleringen vår, og kjører den menneskelige bevegelsessiden av ligningen.

Dette ligner veldig på makeMove () metoden ovenfor, men vi returnerer den pågående poengsummen i stedet for selve brettet:

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

3.2. Scorer siste brett

Vi er nå i en situasjon der vi kan simulere bevegelser frem og tilbake av menneskelige spillere og dataspillere, og stopper når vi har simulert nok av dem. Vi må være i stand til å generere en poengsum for det endelige brettet i hver simuleringsgren, slik at vi kan se hvilken gren som er den vi vil forfølge.

Vår poengsum er en kombinasjon av faktorer, som vi skal bruke på hver rad og hver kolonne på brettet. Disse blir alle oppsummert, og totalen returneres.

Som sådan må vi generere en liste over rader og kolonner for å score mot:

Liste rowsToScore = ny ArrayList (); for (int i = 0; i <board.getSize (); ++ i) {List row = new ArrayList (); Liste col = ny ArrayList (); for (int j = 0; j <board.getSize (); ++ j) {row.add (board.getCell (new Cell (i, j))); col.add (board.getCell (ny celle (j, i))); } rowsToScore.add (rad); rowsToScore.add (kol); }

Så tar vi listen vi har laget, scorer hver av dem og summerer poengsummen sammen. Dette er en plassholder som vi skal fylle ut:

return rowsToScore.stream () .mapToInt (row -> {int score = 0; return score;}) .sum ();

Til slutt må vi faktisk generere poengene våre. Dette går inn i ovennevnte lambda, og er flere forskjellige faktorer som alle bidrar:

• En fast score for hver rad
• Summen av hvert tall i raden
• Hver fusjon mulig på rad
• Hver tomme celle i raden
• Monotonisiteten i rekken. Dette representerer beløpet raden er organisert i stigende numerisk rekkefølge.

Før vi kan beregne poengene, må vi bygge litt ekstra data.

Først vil vi ha en liste over tallene med tomme celler fjernet:

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

Vi kan da gjøre noen tellinger fra denne nye listen, og gi antall tilstøtende celler med samme nummer, med strengt stigende tall og strengt synkende tall:

int antall Fusjoner = 0; int monotonisitet Venstre = 0; int monotonisitetRett = 0; for (int i = 0; i sekund) {monotonisitet Venstre + = første - sekund; } annet {monotonicityRight + = sekund - først; }}

Nå kan vi beregne poengsummen vår for denne raden:

int score = 1000; score + = 250 * rad.strøm (). filter (verdi -> verdi == 0). antall (); score + = 750 * antallMerges; score - = 10 * rad.strøm (). mapToInt (verdi -> verdi). sum (); score - = 50 * Math.min (monotonisitet Venstre, monotonisitet Rett); retur score;

Tallene som er valgt her er relativt vilkårlige. Ulike tall vil ha innvirkning på hvor godt spillet spiller, og prioritere forskjellige faktorer i hvordan vi spiller.

4. Forbedringer av algoritmen

Det vi har så langt fungerer, og vi kan se at det spiller et bra spill, men det er tregt. Det tar rundt 1 minutt per menneskelig bevegelse. Vi kan gjøre det bedre enn dette.

4.1. Parallell behandling

Det åpenbare vi kan gjøre er å gjøre arbeid parallelt. Dette er en stor fordel ved å jobbe med Java Streams - vi kan få dette til å fungere parallelt ved å bare legge til en enkelt uttalelse til hver strøm.

Denne endringen alene får oss ned på rundt 20 sekunder per trekk.

4.2. Beskjæring av avspillbare grener

Den neste tingen vi kan gjøre er å beskjære grener som ikke kan spilles. Det vil si når som helst et menneskelig trekk resulterer i et uendret styre. Dette er nesten helt sikkert grener som kommer til å gi dårligere resultater - de gir datamaskinen et gratis trekk - men de koster oss behandlingstid for å forfølge dem.

For å gjøre dette må vi implementere en lik metode på vår Borde slik at vi kan sammenligne dem:

@ Override offentlig boolsk er lik (Objekt o) {hvis (dette == o) {returner sant; } hvis (o == null || getClass ()! = o.getClass ()) {return false; } Board board1 = (Board) o; retur Arrays.deepEquals (bord, bord1. bord); }

Vi kan deretter legge til noen filtre i strømrørledningene våre for å stoppe behandlingen av alt som ikke har endret seg.

return Arrays.stream (Move.values ​​()) .parallel () .map (board :: move). filter (flyttet ->! moved.equals (board)) ........

Dette har minimal innvirkning på de tidlige delene av spillet - når det er veldig få fylte celler, er det veldig få trekk som kan trimmes. Men senere begynner dette å få en mye større innvirkning, og reduserer flyttetider ned til bare noen få sekunder.

5. Sammendrag

Her bygde vi et rammeverk for å spille spillet 2048. Deretter skrev vi en løser inn i dette slik at vi kan spille et bedre spill. Alle eksemplene som vises her kan du finne på GitHub.

Hvorfor ikke prøve å variere reglene for å se hvordan de påvirker spillet.