Implementering af en 2048-løsning i Java

1. Introduktion

For nylig så vi på en algoritme til løsning af spillet 2048. Vi diskuterede dette fra et teoretisk synspunkt og ikke med nogen reel kode bag det.

Her skal vi skrive en implementering af dette i Java. Dette vil spille som både de menneskelige og computerafspillere, hvilket viser, hvor godt et mere optimalt spil kan spilles.

2. Første opsætning

Den første ting, vi har brug for, er en opsætning, hvor vi kan spille spillet og se, hvordan fremskridtene går.

Dette giver os alle de konstruktioner, som vi har brug for for at spille spillet, og implementerer fuldstændigt computerafspilleren - som alligevel kun placerer tilfældige fliser. Dette giver os derefter muligheden for at implementere en "menneskelig" spiller til at spille spillet.

2.1. Spilbræt

Før noget andet har vi brug for et spillebræt. Dette er et gitter af celler, hvor tal kan placeres.

For at gøre nogle ting lettere at arbejde med, lad os begynde med en simpel gengivelse af en celleplacering. Dette er bogstaveligt talt bare en indpakning omkring et par koordinater:

offentlig klasse Cell {privat afsluttende int x; privat endelig int y; // konstruktør, getters og toString}

Vi kan nu skrive en klasse, der repræsenterer selve tavlen. Dette gemmer værdierne i et simpelt todimensionelt array, men giver os adgang til dem via ovenstående Celle klasse:

public class Board {private final int [] [] board; privat endelig int score; public Board (int størrelse) {this.board = new int [størrelse] []; 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) {board [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 ()]; } offentlig boolsk isEmpty (Cellecelle) {return getCell (cell) == 0; } offentlig Liste tommeCeller () {Listeresultat = ny ArrayList (); for (int x = 0; x <board.length; ++ x) {for (int y = 0; y <board [x] .length; ++ y) {Cell cell = new Cell (x, y); hvis (isEmpty (celle)) {result.add (celle); }}} returner resultat; }}

Dette er en uforanderlig klasse, der repræsenterer en tavle og lader os forhøre den for at finde ud af den aktuelle tilstand. Det holder også styr på en nuværende score, som vi kommer til senere.

2.2. En computerafspiller og placering af fliser

Nu hvor vi har et spillebræt, vil vi være i stand til at lege med det. Den første ting, vi ønsker, er computerafspilleren, fordi dette er en rent tilfældig spiller og vil være nøjagtigt efter behov senere.

Computeren spiller ikke andet end at placere en flise i en celle, så vi har brug for en eller anden måde at opnå det på vores bord. Vi vil beholde dette som uforanderligt, så placering af en flise genererer et helt nyt bræt i den nye tilstand.

Først, vi vil have en konstruktør, der tager den aktuelle bordtilstandi modsætning til vores tidligere, der netop konstruerede et blankt bræt:

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 så det kun nogensinde kan bruges af andre metoder inden for samme klasse. Dette hjælper med vores indkapsling af tavlen.

Dernæst tilføjer vi en metode til at placere en flise. Dette returnerer et helt nyt kort, der er identisk med det nuværende, bortset fra at det har det givne nummer i den givne celle:

public Board placeTile (Cellecelle, int-nummer) {if (! isEmpty (cell)) {smid nyt IllegalArgumentException ("Denne celle er ikke tom"); } Board result = new Board (this.board, this.score); result.board [cell.getX ()] [cell.getY ()] = antal; returresultat }

Langt om længe, vi skriver en ny klasse, der repræsenterer en computerafspiller. Dette vil have en enkelt metode, der tager det nuværende bord og returnerer det nye:

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

Dette får listen over hver tom celle fra tavlen, vælger en tilfældig og sætter derefter et nummer i den. Vi vil tilfældigt beslutte at sætte en "4" i cellen 10% af tiden, og en "2" den anden 90%.

2.2. En "menneskelig" spiller og skiftende fliser

Den næste ting, vi har brug for, er en "menneskelig" spiller. Dette bliver ikke det endelige mål, men en rent tilfældig spiller, der vælger en tilfældig retning for at skifte fliserne hver gang det bevæger sig. Dette fungerer derefter som et sted, som vi kan bygge videre på for at gøre vores optimale spiller.

For det første skal vi definere en optælling af de mulige bevægelser, der kan foretages:

offentlig enum Flyt {OP, NED, VENSTRE, HØJRE}

Dernæst skal vi udvide Bestyrelse klasse til støtte for at bevæge sig ved at flytte fliser i en af ​​disse retninger. For at reducere kompleksiteten her ønsker vi at dreje brættet, så vi altid skifter fliser i samme retning.

Dette betyder, at vi har brug for et middel både til at transponere og vende ombord:

privat statisk int [] [] transponere (int [] [] input) {int [] [] resultat = ny int [input.længde] []; for (int x = 0; x <input.length; ++ x) {result [x] = new int [input [0] .length]; for (int y = 0; y <input [0]. længde; ++ y) {resultat [x] [y] = input [y] [x]; }} returner resultat; } privat statisk int [] [] omvendt (int [] [] input) {int [] [] resultat = ny int [input.længde] []; for (int x = 0; x <input.length; ++ x) {result [x] = new int [input [0] .length]; for (int y = 0; y <input [0]. længde; ++ y) {resultat [x] [y] = input [x] [input.længde - y - 1]; }} returner resultat; }

Transponering af tavlen bytter alle rækker og kolonner rundt, således at den øverste kant bliver venstre kant. Omvendt bræt spejler det blot sådan, at venstre kant bliver højre kant.

Dernæst tilføjer vi en metode til Bestyrelse at tage et skridt i en given retning og returnere en ny Bestyrelse i den nye stat.

Vi starter med at lave en kopi af bestyrelsen, som vi derefter kan arbejde med:

public Board move (Move move) {int newScore = 0; // Klon tavlen 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); }

Dernæst manipulerer vi vores kopi, så vi altid flytter fliser op:

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

Vi har brug for endnu en række fliser - denne gang den, som vi vil bygge det endelige resultat i - og en tracker til den nye score, der er opnået for dette træk:

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

Nu hvor vi er klar til at begynde at skifte fliser, og vi har manipuleret tingene, så vi altid arbejder i samme retning, kan vi starte.

Vi kan skifte hver kolonne uafhængigt af de andre. Vi skal bare gentage kolonnerne og gentage, begyndende med at bygge endnu en kopi af de fliser, vi skifter.

Denne gang bygger vi dem op i en LinkedList fordi vi vil være i stand til let at sprænge værdier ud af det. Vi tilføjer også kun de faktiske fliser, der har tal og springer over tomme fliser.

Dette opnår vores skift, men endnu ikke sammenfletning af fliser:

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

Dernæst skal vi flette fliser. Vi er nødt til at gøre dette separat fra ovenstående; Ellers risikerer vi at flette den samme flise flere gange.

Dette opnås ved at opbygge en anden LinkedList af fliserne fra ovenstående, men denne gang fusionerer vi, mens vi går:

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

Her beregner vi også den nye score for dette træk. Dette er summen af ​​fliserne, der er oprettet som et resultat af fletninger.

Vi kan nu opbygge dette i resultat array. Når vi først er løbet tør for fliser fra vores liste, bliver resten befolket med værdien "0" for at indikere, at de er tomme:

 resultat [x] = ny int [fliser [0] .længde]; for (int y = 0; y <brikker [0] .længde; ++ y) {hvis (newRow.isEmpty ()) {resultat [x] [y] = 0; } andet {resultat [x] [y] = newRow.pop (); }}}

Når vi er færdige med at skifte fliser, skal vi manipulere dem igen til den korrekte rotation. Dette er det stik modsatte, som vi gjorde tidligere:

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

Og endelig kan vi bygge og returnere et nyt bræt med dette nye sæt fliser og den nyberegnede score:

 returner nyt Board (resultat, this.score + newScore); }

Vi er nu i en position, hvor vi kan skrive vores tilfældige "menneskelige" spiller. Dette gør intet andet end at generere et tilfældigt træk og kalde ovenstående metode for at spille det træk:

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

2.3. At spille spillet

Vi har nok komponenter til at spille spillet, omend ikke meget vellykket. Imidlertid vil vi snart forbedre den måde, som Human klassespil, og dette vil give os mulighed for let at se forskellene.

For det første har vi brug for en måde at udskrive spillebrættet på.

I dette eksempel skal vi bare udskrive til konsollen, så System.out.print er god nok. For et rigtigt spil ønsker vi at lave bedre grafik:

privat statisk ugyldig printBoard (Board board) {StringBuilder topLines = new StringBuilder (); StringBuilder midLines = ny 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 = ny celle (x, y); System.out.print ("|"); hvis (board.isEmpty (celle)) {System.out.print ("");} ellers {StringBuilder output = ny StringBuilder (heltal .toString (board.getCell (celle))); mens (output.length () <8) {output.append (""); hvis (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 næsten klar til at gå. Vi skal bare sætte tingene op.

Dette betyder at oprette brættet, de to spillere og få computeren til at foretage to indledende træk - det vil sige placere to tilfældige tal på tavlen:

Bestyrelse = ny bestyrelse (4); Computer computer = ny Computer (); Menneske menneske = nyt menneske (); for (int i = 0; i <2; ++ i) {board = computer.makeMove (board); }

Og nu har vi den egentlige spilsløjfe. Dette vil være en gentagelse af de menneskelige og computerafspillere, der skiftes, og stopper kun, når der ikke er tomme celler tilbage:

printBoard (bord); gør {System.out.println ("Human move"); System.out.println ("==========="); board = human.makeMove (board); printBoard (bord); System.out.println ("Computer flyt"); System.out.println ("=============="); board = computer.makeMove (kort); printBoard (bord); } mens (! board.emptyCells (). isEmpty ()); System.out.println ("Endelig score:" + board.getScore ());

På dette tidspunkt, hvis vi skulle køre programmet, ville vi se et tilfældigt spil på 2048 blive spillet.

3. Implementering af 2048 Player

Når vi har en base, hvorfra vi kan spille spillet, kan vi begynde at implementere den "menneskelige" spiller og spille et bedre spil end bare at vælge en tilfældig retning.

3.1. Simulering af bevægelser

Algoritmen, vi implementerer her, er baseret på Expectimax-algoritmen. Som sådan, kernen i algoritmen er at simulere alle mulige bevægelser, tildele en score til hver enkelt og vælge den, der klarer sig bedst.

Vi bruger tungt Java 8 Streams til at hjælpe med at strukturere denne kode af grunde, vi ser senere.

Vi starter med at omskrive makeMove () metode indefra vores Human 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 mulig retning, vi kan bevæge os i, genererer vi det nye tavle og starter derefter scoringsalgoritmen - passerer i dette bræt og en dybde på 0. Vi vælger derefter det træk, der har den bedste score.

Vores generereScore () metoden simulerer derefter alle mulige computertræk - det vil sige at placere enten en "2" eller en "4" i hver tom celle - og derefter se, hvad der kunne ske næste:

private int generereScore (Board board, int depth) {if (depth> = 3) {return calcinalFinalScore (board); } returner board.emptyCells (). stream () .flatMap (celle -> Stream.of (nyt par (celle, 2), nyt par (celle, 4))) .mapToInt (flyt -> {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ået vores dybdegrænse, stopper vi straks og beregner en endelig score for, hvor god denne tavle er; Ellers fortsætter vi med vores simulering.

Vores beregne score () metoden er derefter fortsættelsen af ​​vores simulering, der kører den menneskelige bevægelsesside af ligningen.

Dette svarer meget til makeMove () metode ovenfor, men vi returnerer den løbende score i stedet for det faktiske bord:

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 endelige bestyrelser

Vi er nu i en situation, hvor vi kan simulere bevægelser frem og tilbage af de menneskelige og computerafspillere og stopper, når vi har simuleret nok af dem. Vi er nødt til at være i stand til at generere en score for det endelige bord i hver simuleringsgren, så vi kan se, hvilken gren der er den, vi vil forfølge.

Vores scoring er en kombination af faktorer, som vi hver især vil anvende på hver række og hver kolonne på tavlen. Disse opsummeres alle sammen, og summen returneres.

Som sådan er vi nødt til at generere en liste over rækker og kolonner til at score mod:

Liste rowsToScore = ny ArrayList (); for (int i = 0; i <board.getSize (); ++ i) {Liste række = ny ArrayList (); Liste col = ny ArrayList (); for (int j = 0; j <board.getSize (); ++ j) {row.add (board.getCell (ny celle (i, j))); col.add (board.getCell (ny celle (j, i))); } rowsToScore.add (række); rowsToScore.add (col); }

Derefter tager vi listen, som vi har opbygget, scorer hver af dem og summerer score. Dette er en pladsholder, som vi er ved at udfylde:

return rowToScore.stream () .mapToInt (række -> {int score = 0; return score;}) .sum ();

Endelig skal vi faktisk generere vores scores. Dette går inde i ovenstående lambda og er flere forskellige faktorer, som alle bidrager:

  • En fast score for hver række
  • Summen af ​​hvert nummer i rækken
  • Enhver fusion mulig i rækken
  • Hver tom celle i rækken
  • Rækkets monotoni. Dette repræsenterer det beløb, rækken er organiseret i stigende numerisk rækkefølge.

Før vi kan beregne scoringerne, skal vi opbygge nogle ekstra data.

Først vil vi have en liste over numrene med tomme celler fjernet:

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

Vi kan derefter foretage nogle optællinger fra denne nye liste ved at give antallet af tilstødende celler med det samme nummer med strengt stigende tal og strengt faldende tal:

int numMerges = 0; int monotonicitet Venstre = 0; int monotonicitetRet = 0; for (int i = 0; i sekund) {monotonicitet Venstre + = første - sekund; } andet {monotonicitetRight + = sekund - første; }}

Nu kan vi beregne vores score for denne række:

int score = 1000; score + = 250 * række.strøm (). filter (værdi -> værdi == 0). antal (); score + = 750 * numMerges; score - = 10 * række.strøm (). mapToInt (værdi -> værdi). sum (); score - = 50 * Math.min (monotonicitet Venstre, monotonicitet Ret); retur score

De valgte tal er relativt vilkårlige. Forskellige tal vil have indflydelse på, hvor godt spillet spiller, og prioritere forskellige faktorer i, hvordan vi spiller.

4. Forbedringer af algoritmen

Det, vi har hidtil, fungerer, og vi kan se, at det spiller et godt spil, men det er langsomt. Det tager cirka 1 minut pr. Menneskeligt træk. Vi kan gøre det bedre end dette.

4.1. Parallel behandling

Den åbenlyse ting, vi kan gøre, er at arbejde parallelt. Dette er en enorm fordel ved at arbejde med Java Streams - vi kan få dette til at arbejde parallelt ved blot at tilføje en enkelt erklæring til hver stream.

Denne ændring alene får os ned på omkring 20 sekunder pr. Træk.

4.2. Beskæring af uafspillelige grene

Den næste ting vi kan gøre er at beskære eventuelle grene, der ikke kan afspilles. Det vil sige når som helst et menneskeligt træk resulterer i et uændret bord. Dette er næsten helt sikkert grene, der vil resultere i dårligere resultater - de giver computeren effektivt et gratis træk - men de koster os behandlingstid for at forfølge dem.

For at gøre dette skal vi implementere en ligemetode på vores Bestyrelse så vi kan sammenligne dem:

@ Override offentlige boolske er lig med (Objekt o) {hvis (dette == o) {returner sandt; } hvis (o == null || getClass ()! = o.getClass ()) {returner false; } Board board1 = (Board) o; returnere Arrays.deepEquals (bord, board1.board); }

Vi kan derefter tilføje nogle filtre til vores stream-rørledninger for at stoppe behandlingen af ​​noget, der ikke har ændret sig.

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

Dette har minimal indflydelse på de tidlige dele af spillet - når der er meget få fyldte celler, er der meget få træk, der kan trimmes. Senere begynder dette dog at få en meget større indvirkning og reducerer flytider ned til kun få sekunder.

5. Resume

Her byggede vi en ramme for at spille spillet 2048. Derefter skrev vi en løser ind i dette, så vi kan spille et bedre spil. Alle eksemplerne her kan findes på GitHub.

Hvorfor ikke prøve at ændre reglerne for at se, hvordan de påvirker gameplayet.