streamalism.org

1. Inleiding

Onlangs hebben we gekeken naar een algoritme om het spel 2048 op te lossen. We bespraken dit vanuit een theoretisch oogpunt, en niet met een echte code erachter.

Hier gaan we een implementatie hiervan in Java schrijven. Dit zal spelen als zowel de menselijke als de computerspeler, en laat zien hoe goed een meer optimaal spel kan worden gespeeld.

2. Eerste installatie

Het eerste dat we nodig hebben, is een opstelling waarin we het spel kunnen spelen en kunnen zien hoe de voortgang gaat.

Dit geeft ons alle constructies die we nodig hebben om het spel te spelen, en de computerspeler volledig te implementeren - die sowieso alleen willekeurige tegels plaatst. Dit geeft ons dan de ruimte om een ​​“menselijke” speler te implementeren om het spel te spelen.

2.1. Spelbord

Voor alles hebben we een speelbord nodig. Dit is een rooster van cellen waarin getallen kunnen worden geplaatst.

Om sommige dingen een beetje gemakkelijker te maken om mee te werken, laten we beginnen met een eenvoudige weergave van een cellocatie. Dit is letterlijk slechts een wrapper rond een paar coördinaten:

openbare klasse Cell {private final int x; privé laatste int y; // constructor, getters en toString}

We kunnen nu een klas schrijven om het bord zelf te vertegenwoordigen. Dit gaat de waarden opslaan in een eenvoudige tweedimensionale array, maar geeft ons toegang tot ze via het bovenstaande Cel klasse:

openbare klasse Board {private final int [] [] board; privé eindscore int; openbaar bord (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 () {return score; } openbare int getCell (celcel) {retourbord [cell.getX ()] [cell.getY ()]; } openbare boolean isEmpty (celcel) {return getCell (cel) == 0; } openbare lijst emptyCells () {Lijstresultaat = nieuwe 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 (cel)) {resultaat.add (cel); }}} resultaat retourneren; }}

Dit is een onveranderlijke klasse die een bord vertegenwoordigt en waarmee we het kunnen ondervragen om de huidige status te achterhalen. Het houdt ook een actuele score bij, waar we later op terugkomen.

2.2. Een computerspeler en het plaatsen van tegels

Nu we een speelbord hebben, willen we ermee kunnen spelen. Het eerste dat we willen is de computerspeler, omdat dit een puur willekeurige speler is en later precies zo zal zijn als nodig is.

De computerspeler doet niets anders dan een tegel in een cel plaatsen, dus we hebben een manier nodig om dat op ons bord te bereiken. We willen dit onveranderlijk houden, dus het plaatsen van een tegel genereert een gloednieuw bord in de nieuwe staat.

Eerste, we willen een constructor die de werkelijke boardstatus aanneemt, in tegenstelling tot onze eerdere die zojuist een leeg bord heeft gemaakt:

privébord (int [] [] bord, int score) {this.score = score; this.board = nieuwe int [board.length] []; voor (int x = 0; x <board.length; ++ x) {this.board [x] = Arrays.copyOf (board [x], board [x] .length); }}

Dit is privaat zodat het alleen kan worden gebruikt door andere methoden binnen dezelfde klasse. Dit helpt bij onze inkapseling van het bord.

Vervolgens voegen we een methode toe om een ​​tegel te plaatsen. Dit retourneert een gloednieuw bord dat identiek is aan het huidige, behalve dat het het opgegeven nummer in de gegeven cel heeft:

public Board placeTile (Cell cell, int number) {if (! isEmpty (cell)) {throw new IllegalArgumentException ("Die cel is niet leeg"); } Bordresultaat = nieuw bord (this.board, this.score); result.board [cell.getX ()] [cell.getY ()] = nummer; resultaat teruggeven; }

Tenslotte, we zullen een nieuwe klas schrijven die een computerspeler vertegenwoordigt. Dit heeft een enkele methode die het huidige bord neemt en het nieuwe retourneert:

openbare klasse Computer {privé definitief SecureRandom rng = nieuwe SecureRandom (); public Board makeMove (Board input) {List emptyCells = input.emptyCells (); dubbel numberToPlace = rng.nextDouble (); int indexToPlace = rng.nextInt (emptyCells.size ()); Cel cellToPlace = emptyCells.get (indexToPlace); return input.placeTile (cellToPlace, numberToPlace> = 0.9? 4: 2); }}

Dit haalt de lijst van elke lege cel van het bord, kiest een willekeurige cel en plaatst er vervolgens een nummer in. We besluiten willekeurig om 10% van de tijd een "4" in de cel te plaatsen en de andere 90% een "2".

2.2. Een "menselijke" speler en wisselende tegels

Het volgende dat we nodig hebben, is een 'menselijke' speler. Dit wordt niet het einddoel, maar een puur willekeurige speler die een willekeurige richting kiest om de tegels elke keer dat hij een zet doet, te verschuiven. Dit zal dan fungeren als een plek waarop we kunnen voortbouwen om onze optimale speler te maken.

Ten eerste moeten we een opsomming definiëren van de mogelijke zetten die kunnen worden gemaakt:

openbare opsomming Beweeg {UP, DOWN, LEFT, RIGHT}

Vervolgens moeten we de Bord klasse om het maken van zetten te ondersteunen door tegels in een van deze richtingen te verschuiven. Om de complexiteit hier te verminderen, willen we het bord zo draaien dat we tegels altijd in dezelfde richting verschuiven.

Dit betekent dat we een middel nodig hebben om het bord te transponeren en om te keren:

private static int [] [] transpose (int [] [] input) {int [] [] resultaat = nieuwe int [input.length] []; for (int x = 0; x <input.length; ++ x) {resultaat [x] = nieuwe int [input [0] .lengte]; voor (int y = 0; y <invoer [0] .lengte; ++ y) {resultaat [x] [y] = invoer [y] [x]; }} resultaat retourneren; } private static int [] [] reverse (int [] [] input) {int [] [] resultaat = nieuwe int [input.length] []; for (int x = 0; x <input.length; ++ x) {resultaat [x] = nieuwe int [input [0] .length]; voor (int y = 0; y <invoer [0] .lengte; ++ y) {resultaat [x] [y] = invoer [x] [invoer.lengte - y - 1]; }} resultaat retourneren; }

Als u het bord transponeert, worden alle rijen en kolommen omgewisseld, zodat de bovenrand de linkerrand wordt. Door het bord om te keren, wordt het eenvoudig gespiegeld, zodat de linkerrand de rechterrand wordt.

Vervolgens voegen we een methode toe aan het Bord om een ​​beweging in een bepaalde richting te maken en een nieuwe terug te geven Bord in de nieuwe staat.

We beginnen met het maken van een kopie van de bordstaat waarmee we kunnen werken:

openbaar bord verplaatsen (verplaats verplaatsen) {int newScore = 0; // Kloon het bord int [] [] tegels = nieuwe int [this.board.length] []; voor (int x = 0; x <this.board.length; ++ x) {tiles [x] = Arrays.copyOf (this.board [x], this.board [x] .length); }

Vervolgens manipuleren we onze kopie zodat we altijd tegels naar boven gaan verschuiven:

if (move == Move.LEFT || move == Move.RIGHT) {tegels = transponeren (tegels); } if (move == Move.DOWN || move == Move.RIGHT) {tiles = reverse (tiles); }

We hebben nog een andere reeks tegels nodig - deze keer degene waarin we het eindresultaat zullen bouwen - en een tracker voor de nieuwe score die voor deze zet is behaald:

int [] [] resultaat = nieuwe int [tegels.lengte] []; int newScore = 0;

Nu we klaar zijn om tegels te verschuiven, en we dingen hebben gemanipuleerd zodat we altijd in dezelfde richting werken, kunnen we beginnen.

We kunnen elke kolom onafhankelijk van de andere verschuiven. We hoeven alleen maar de kolommen te herhalen en te herhalen, te beginnen met het bouwen van nog een kopie van de tegels die we verschuiven.

Deze keer bouwen we ze in tot een LinkedList omdat we er gemakkelijk waarden uit willen halen. We voegen ook alleen de daadwerkelijke tegels met nummers toe en slaan lege tegels over.

Dit bereikt onze verschuiving, maar nog niet het samenvoegen van tegels:

for (int x = 0; x <tiles.length; ++ x) {LinkedList thisRow = nieuwe LinkedList (); voor (int y = 0; y 0) {thisRow.add (tegels [x] [y]); }}

Vervolgens moeten we tegels samenvoegen. We moeten dit los van het bovenstaande doen; anders lopen we het risico dezelfde tegel meerdere keren samen te voegen.

Dit wordt bereikt door een ander te bouwen LinkedList van de tegels uit het bovenstaande, maar deze keer samenvoegen we:

LinkedList newRow = nieuwe LinkedList (); while (thisRow.size ()> = 2) {int first = thisRow.pop (); int tweede = thisRow.peek (); if (second == first) {int newNumber = first * 2; newRow.add (newNumber); newScore + = newNumber; thisRow.pop (); } else {newRow.add (eerste); }} newRow.addAll (thisRow);

Hier berekenen we ook de nieuwe score voor deze zet. Dit is de som van de tegels die zijn gemaakt als gevolg van samenvoegingen.

We kunnen dit nu in de resultaatmatrix inbouwen. Zodra we geen tegels meer uit onze lijst hebben, wordt de rest gevuld met de waarde "0" om aan te geven dat ze leeg zijn:

 resultaat [x] = nieuwe int [tegels [0] .lengte]; for (int y = 0; y <tegels [0] .lengte; ++ y) {if (newRow.isEmpty ()) {resultaat [x] [y] = 0; } anders {resultaat [x] [y] = newRow.pop (); }}}

Zodra we klaar zijn met het verplaatsen van tegels, moeten we ze weer manipuleren naar de juiste rotatie. Dit is precies het tegenovergestelde dat we eerder deden:

if (move == Move.DOWN || move == Move.RIGHT) {resultaat = omgekeerd (resultaat); } if (move == Move.LEFT || move == Move.RIGHT) {resultaat = transponeren (resultaat); }

En tot slot kunnen we een nieuw bord bouwen en terugbrengen met deze nieuwe set tegels en de nieuw berekende score:

 retourneer nieuw bord (resultaat, this.score + newScore); }

We zijn nu in een positie waarin we onze willekeurige "menselijke" speler kunnen schrijven. Dit doet niets anders dan een willekeurige zet genereren en de bovenstaande methode aanroepen om die zet te spelen:

openbare klasse Human {privé SecureRandom rng = nieuwe SecureRandom (); openbaar bord makeMove (bordinvoer) {Move move = Move.values ​​() [rng.nextInt (4)]; return input.move (verplaatsen); }}

2.3. Het spel aan het spelen

We hebben genoeg componenten om het spel te spelen, zij het niet erg succesvol. Binnenkort zullen we echter de manier verbeteren waarop de Mens class plays, en dit zal ons in staat stellen om de verschillen gemakkelijk te zien.

Ten eerste hebben we een manier nodig om het speelbord af te drukken.

Voor dit voorbeeld gaan we gewoon afdrukken naar de console, dus System.out.print is goed genoeg. Voor een echt spel zouden we betere graphics willen maken:

privé statisch ongeldig printBoard (Board board) {StringBuilder topLines = nieuwe StringBuilder (); StringBuilder midLines = nieuwe 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) {Celcel = nieuwe cel (x, y); System.out.print ("|"); if (board.isEmpty (cel)) {System.out.print ("");} else {StringBuilder-uitvoer = nieuwe StringBuilder (geheel getal .toString (board.getCell (cel))); 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 ());}

We zijn bijna klaar om te vertrekken. We hoeven alleen maar dingen op te zetten.

Dit betekent dat je het bord, de twee spelers moet maken en de computer twee eerste zetten moet laten doen - dat wil zeggen, twee willekeurige getallen op het bord plaatsen:

Bordbord = nieuw bord (4); Computer computer = nieuwe computer (); Mens mens = nieuwe mens (); voor (int i = 0; i <2; ++ i) {board = computer.makeMove (board); }

En nu hebben we de eigenlijke spellus. Dit wordt een herhaling van de menselijke en computerspelers die om de beurt spelen en alleen stoppen als er geen lege cellen meer zijn:

printBoard (bord); do {System.out.println ("Menselijke beweging"); System.out.println ("=========="); board = human.makeMove (board); printBoard (bord); System.out.println ("Computer verplaatsen"); System.out.println ("============="); board = computer.makeMove (board); printBoard (bord); } while (! board.emptyCells (). isEmpty ()); System.out.println ("Eindscore:" + board.getScore ());

Als we op dit punt het programma zouden draaien, zouden we een willekeurig spel van 2048 zien spelen.

3. Implementatie van de 2048 Player

Zodra we een basis hebben van waaruit we het spel kunnen spelen, kunnen we beginnen met het implementeren van de "menselijke" speler en een beter spel spelen dan alleen een willekeurige richting kiezen.

3.1. Moves simuleren

Het algoritme dat we hier implementeren, is gebaseerd op het Expectimax-algoritme. Als zodanig, de kern van het algoritme is om elke mogelijke zet te simuleren, een score toe te kennen aan elke zet en degene te selecteren die het het beste doet.

We zullen veel gebruik maken van Java 8 Streams om deze code te structureren, om redenen die we later zullen zien.

We beginnen met het herschrijven van het makeMove () methode van binnenuit onze Mens klasse:

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

Voor elke mogelijke richting waarin we kunnen bewegen, genereren we het nieuwe bord en starten we het scoringsalgoritme - passen op dit bord en een diepte van 0. Vervolgens selecteren we de zet met de beste score.

Onze Genereer Score () De methode simuleert vervolgens elke mogelijke computerbeweging - dat wil zeggen, het plaatsen van een "2" of een "4" in elke lege cel - en kijkt dan wat er daarna zou kunnen gebeuren:

private int createScore (Board board, int depth) {if (depth> = 3) {return berekenFinalScore (board); } return board.emptyCells (). stream () .flatMap (cel -> Stream.of (nieuw paar (cel, 2), nieuw paar (cel, 4))) .mapToInt (verplaats -> {Board newBoard = board. placeTile (move.getFirst (), move.getSecond ()); int boardScore = berekenScore (newBoard, diepte + 1); return (int) (boardScore * (move.getSecond () == 2? 0.9: 0.1)); }) .sum (); }

Als we onze dieptelimiet hebben bereikt, stoppen we onmiddellijk en berekenen we een eindscore voor hoe goed dit bord is; anders gaan we verder met onze simulatie.

Onze berekenScore () methode is dan de voortzetting van onze simulatie, waarbij de menselijke verplaatsingskant van de vergelijking wordt uitgevoerd.

Dit lijkt erg op de makeMove () methode hierboven, maar we retourneren de lopende score in plaats van het daadwerkelijke bord:

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

3.2. Het scoren van eindborden

We bevinden ons nu in een situatie waarin we bewegingen heen en weer kunnen simuleren door de menselijke en computerspelers, en stoppen wanneer we er genoeg van hebben gesimuleerd. We moeten in elke simulatietak een score kunnen genereren voor het uiteindelijke bord, zodat we kunnen zien welke tak de tak is die we willen nastreven.

Onze score is een combinatie van factoren, die we allemaal gaan toepassen op elke rij en elke kolom op het bord. Deze worden allemaal bij elkaar opgeteld en het totaal wordt geretourneerd.

Daarom moeten we een lijst met rijen en kolommen genereren om te scoren tegen:

Lijst rijenToScore = nieuwe ArrayList (); for (int i = 0; i <board.getSize (); ++ i) {List row = new ArrayList (); Lijst col = new ArrayList (); voor (int j = 0; j <board.getSize (); ++ j) {row.add (board.getCell (nieuwe cel (i, j))); col.add (board.getCell (nieuwe cel (j, i))); } rijenToScore.add (rij); rijenToScore.add (col); }

Vervolgens nemen we de lijst die we hebben gemaakt, scoren we ze allemaal en tellen we de scores bij elkaar op. Dit is een tijdelijke aanduiding die we gaan invullen:

retourneer rijenToScore.stream () .mapToInt (rij -> {int score = 0; retourneer score;}) .sum ();

Ten slotte moeten we onze scores daadwerkelijk genereren. Dit gaat binnen de bovenstaande lambda, en zijn verschillende factoren die allemaal bijdragen:

• Voor elke rij een vaste score
• De som van elk getal in de rij
• Elke samenvoeging mogelijk in de rij
• Elke lege cel in de rij
• De eentonigheid van de rij. Dit vertegenwoordigt het bedrag dat de rij in oplopende numerieke volgorde is georganiseerd.

Voordat we de scores kunnen berekenen, moeten we wat extra gegevens opbouwen.

Ten eerste willen we een lijst met de nummers waarvan de lege cellen zijn verwijderd:

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

We kunnen dan enkele tellingen maken van deze nieuwe lijst, waarbij we het aantal aangrenzende cellen met hetzelfde nummer geven, met strikt oplopende nummers en strikt aflopende nummers:

int numMerges = 0; int monotonicityLeft = 0; int monotonicityRight = 0; for (int i = 0; i second) {monotonicityLeft + = eerste - tweede; } anders {monotonicityRight + = second - first; }}

Nu kunnen we onze score voor deze rij berekenen:

int score = 1000; score + = 250 * row.stream (). filter (waarde -> waarde == 0) .count (); score + = 750 * aantalMerges; score - = 10 * row.stream (). mapToInt (waarde -> waarde) .sum (); score - = 50 * Math.min (monotonicityLeft, monotonicityRight); score teruggeven;

De hier geselecteerde nummers zijn relatief willekeurig. Verschillende nummers hebben invloed op hoe goed het spel speelt, waarbij verschillende factoren voorrang krijgen bij hoe we spelen.

4. Verbeteringen aan het algoritme

Wat we tot nu toe hebben werkt, en we kunnen zien dat het een goed spel speelt, maar het is traag. Het duurt ongeveer 1 minuut per menselijke beweging. We kunnen het beter doen dan dit.

4.1. Parallelle verwerking

Het voor de hand liggende dat we kunnen doen, is parallel werken. Dit is een enorm voordeel van het werken met Java Streams - we kunnen dit parallel laten werken door slechts een enkele instructie aan elke stream toe te voegen.

Alleen al deze verandering brengt ons terug tot ongeveer 20 seconden per zet.

4.2. Onspeelbare takken snoeien

Het volgende dat we kunnen doen, is takken wegsnoeien die niet kunnen worden afgespeeld. Dat wil zeggen, elke keer dat een menselijke beweging resulteert in een ongewijzigd bord. Dit zijn vrijwel zeker branches die tot slechtere resultaten zullen leiden - ze geven de computer in feite de vrije hand - maar ze kosten ons verwerkingstijd om ze na te streven.

Om dit te doen, moeten we een gelijken-methode implementeren op onze Bord zodat we ze kunnen vergelijken:

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

We kunnen dan enkele filters toevoegen aan onze streampijplijnen om te stoppen met het verwerken van iets dat niet is gewijzigd.

return Arrays.stream (Move.values ​​()) .parallel () .map (bord :: verplaats) .filter (verplaatst ->! verplaatst.equals (bord)) ........

Dit heeft een minimale impact op de vroege delen van het spel - als er maar heel weinig gevulde cellen zijn, zijn er maar heel weinig zetten die kunnen worden bijgesneden. Later begint dit echter een veel grotere impact te hebben, waardoor de bewegingstijden worden teruggebracht tot slechts enkele seconden.

5. Samenvatting

Hier hebben we een raamwerk gebouwd voor het spelen van het spel 2048. Vervolgens hebben we hier een oplosser in geschreven zodat we een beter spel kunnen spelen. Alle voorbeelden die hier te zien zijn, zijn te vinden op GitHub.

Waarom probeer je de regels niet te variëren om te zien hoe ze de gameplay beïnvloeden.