2048 per Bruteforce knacken?

Übersicht Sonstiges Smalltalk

Neue Antwort erstellen

Thunder

Betreff: 2048 per Bruteforce knacken?

 BeitragDi, Mai 13, 2014 17:38
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Leute,

ich spiele jetzt schon einige Zeit hin und wieder das Spiel 2048, das es als Browsergame und auch für Android, iOS und Windows Phone gibt. Hier der Link zum Browsergame, falls es jemand nicht kennt: http://gabrielecirulli.github.io/2048/

Ich habe natürlich schon ein paar taktische Sachen darüber gehört, aber ich hatte vor kurzem die Idee, ein Programm zu schreiben, das eine unaufgeräumte Partie in diesem Spiel vielleicht retten könnte. Von Anfang an ein Spiel durchzusimulieren wäre natürlich sicher zu rechenaufwendig, aber ich dachte, wenn schon die meisten Felder (vielfältig) belegt sind, dann könnte man quasi per Bruteforce die beste Lösung ermitteln weiterzumachen.
Habe auch fix ein Programm dazu geschrieben, nur ist es sehr langsam. Also 3-5 Züge kann ich im Voraus berechnen, ohne dass mir der Geduldsfaden reißt...

Also im Moment bin ich dabei das Programm zu optimieren (ohne von Bruteforce abzuweichen). Also hab ich Mal ein paar Routinen in Assembler geschrieben, aber was wirklich langsam ist, sind glaub ich meine Funktinonen, die die Zahlen nach links/rechts/oben/unten schieben.
Also wollte ich Mal fragen, ob jemand Tipps diesbezüglich hat. Darf aber gerne auch alles andere betreffen Smile

Code ist hier. Ihr braucht keine externen Ressourcen. Der Einfachheit halber, habe ich meine Assemblerroutinen ausgeklammert und noch die alten BlitzMax-Funktionen eingeschaltet.
BlitzMax: [AUSKLAPPEN] 
Strict
Framework brl.blitz
Import brl.max2d
Import brl.d3d7max2d
Import brl.Graphics
Import brl.timer

Rem

Import "2048solve.asm"

Extern

	Function copygrid:Int Ptr(grid:Int Ptr)
	Function cmp(grid1:Int Ptr, grid2:Int Ptr)
	Function min2048(grid:Int Ptr)

EndExtern

EndRem

Const GW = 640, GH = 400
Const SIZE = 4
Const GRID_W = 80
Const GRID_WA = GRID_W + 7
Const GRID_SY = (GH-GRID_WA*SIZE)/2, GRID_SX = GRID_SY, GRID_SXW = GRID_SX+GRID_WA*SIZE+5

Global gridmem:Int Ptr, gridmemend:Int Ptr, gridmemlen = SIZE*SIZE*4*1024
Global turnmax = 10
Global timer:TTimer = CreateTimer(20)
Global grid:Int Ptr
Global mxs, mys, mzs
Global vals:Int[4]

Graphics GW, GH

SetClsColor $FF, $C9, $73

gridmem = Int Ptr MemAlloc(gridmemlen)
gridmemend = gridmem + gridmemlen
grid = gridmem
Repeat

	Cls

	mxs = MouseXSpeed()
	mys = MouseYSpeed()
	mzs = MouseZSpeed()

	drawgrid

	If KeyHit(KEY_SPACE) Then analyze
	If KeyHit(KEY_DELETE) Or KeyHit(KEY_BACKSPACE) Then MemClear grid, SIZE*SIZE*4
	
	
	SetColor $A6, $65, $00
	
	DrawText "Left:", GRID_SXW, GRID_SY
	DrawText vals[0], GRID_SXW, GRID_SY+20
	
	DrawText "Right:", GRID_SXW, GRID_SY+50
	DrawText vals[1], GRID_SXW, GRID_SY+70
	
	DrawText "Up:", GRID_SXW, GRID_SY+100
	DrawText vals[2], GRID_SXW, GRID_SY+120
	
	DrawText "Down:", GRID_SXW, GRID_SY+150
	DrawText vals[3], GRID_SXW, GRID_SY+170
	
	DrawText turnmax + " Turns ahead", GRID_SX, 5
	
	updategrid


	If mzs Then
		turnmax :+ mzs
		If turnmax < 1 Then turnmax = 1
	EndIf
	
	Flip 0
	WaitTimer timer

Until AppTerminate()
MemFree gridmem
End


'Rem

Function copygrid:Int Ptr(grid:Int Ptr)
	Local p:Int Ptr = grid + SIZE*SIZE
	If p >= gridmemend Then
		
		gridmem = Int Ptr MemExtend(gridmem, gridmemlen, gridmemlen*2)
		gridmemlen :* 2
		gridmemend = Int Ptr((Byte Ptr gridmem) + gridmemlen)
	
	EndIf
	MemCopy p, grid, SIZE*SIZE*4
	Return p
EndFunction


Function cmp(grid1:Int Ptr, grid2:Int Ptr)
	Local i
	For i = 0 Until SIZE*SIZE
		If grid1[i] <> grid2[i] Then Return False
	Next
	Return True
EndFunction

Function min2048(grid:Int Ptr)
	Local i
	For i = 0 Until SIZE*SIZE
		If grid[i] = 2048 Then Return True
	Next
	Return False
EndFunction

'EndRem

Function drawprogbar(x)

	SetColor 0,0,0
	DrawRect 10, GH-20, GW-20, 1
	DrawRect 10, GH-20, 1, 10
	DrawRect 10, GH-10, GW-20, 1
	DrawRect GW-10, GH-20, 1, 10

	DrawRect 12, GH-18, (GW-24)*x/100, 7

EndFunction



Function schachmatt(grid:Int Ptr)
	Local i
	For i = 0 Until SIZE*SIZE
		If grid[i] = 0 Then Return False
		If i>0 And grid[i-1] = grid[i] Then Return False
		If i>=SIZE And grid[i-SIZE] = grid[i] Then Return False
	Next
	Return True
EndFunction


Function check_rand:Int(grid:Int Ptr, turn = 0)
	Local i, ret:Int, tmp:Int Ptr
	
	
	For i = 0 Until SIZE*SIZE
		If grid[i] = 0 Then
		
			grid[i] = 2
			tmp = copygrid(grid)
			ret = check(tmp, turn)

		
			grid[i] = 4
			tmp = copygrid(grid)
			ret :+ check(tmp, turn)

		
			grid[i] = 0
		EndIf
	Next
	Return ret
EndFunction

Function check:Int(grid:Int Ptr, turn)
	Local ret:Int = 0, tmp:Int Ptr

	turn :+ 1
	If turn > turnmax Then Return 2


	If min2048(grid) Then Return 100000
	If schachmatt(grid) Then
		If turn < 3 Then Return -10000 ..
		Else Return -10
	EndIf
	
	tmp = gridleft(copygrid(grid))
	If Not cmp(grid, tmp) Then ret :+ check_rand(tmp, turn)

	tmp = gridright(copygrid(grid))
	If Not cmp(grid, tmp) Then ret :+ check_rand(tmp, turn)

	tmp = gridup(copygrid(grid))
	If Not cmp(grid, tmp) Then ret :+ check_rand(tmp, turn)

	tmp = griddown(copygrid(grid))
	If Not cmp(grid, tmp) Then ret :+ check_rand(tmp, turn)
	
	Return ret
EndFunction


Function analyze()
	Local g:Int Ptr
	
	
	drawprogbar 5
	Flip 0
	g = copygrid(grid)
	gridleft	g
	If cmp(grid, g) Then vals[0] = 0 Else vals[0] = check_rand(g)
	
	drawprogbar 25
	Flip 0
	g = copygrid(grid)
	gridright	g
	If cmp(grid, g) Then vals[1] = 0 Else vals[1] = check_rand(g)
	
	drawprogbar 50
	Flip 0
	g = copygrid(grid)
	gridup		g
	If cmp(grid, g) Then vals[2] = 0 Else vals[2] = check_rand(g)
	
	drawprogbar 75
	Flip 0
	g = copygrid(grid)
	griddown	g
	If cmp(grid, g) Then vals[3] = 0 Else vals[3] = check_rand(g)

	drawprogbar 100
	Flip 0
	
EndFunction


Function drawgrid()
	Local x, y
	For y = 0 Until SIZE
		For x = 0 Until SIZE
			
			SetColor $00, $00, $00
			DrawRect GRID_SX+x*GRID_WA-1, GRID_SY+y*GRID_WA-1, GRID_W+2, GRID_W+2
			
			SetColor $FF, $B5, $40
			DrawRect GRID_SX+x*GRID_WA, GRID_SY+y*GRID_WA, GRID_W, GRID_W
			
			If grid[x+y*SIZE] Then
				SetColor $A6, $65, $00
				DrawText grid[x+y*SIZE], GRID_SX+15+x*GRID_WA, GRID_SY+15+y*GRID_WA
			EndIf
		Next
	Next
EndFunction

Function updategrid()

	Local mx = MouseX(), my = MouseY()
	Local mh = MouseHit(MOUSE_LEFT) + MouseHit(MOUSE_RIGHT) Shl 1
	
	
	If mh Then
	
		mx = (mx - GRID_SX)/GRID_WA
		my = (my - GRID_SY)/GRID_WA
	
		If mx < SIZE And my < SIZE Then
			
			If mh = 1 Then
				If grid[mx+my*SIZE] = 0 Then grid[mx+my*SIZE] = 2 Else grid[mx+my*SIZE] :Shl 1
			ElseIf mh = 2 Then
				If grid[mx+my*SIZE] = 2 Then grid[mx+my*SIZE] = 0 Else grid[mx+my*SIZE] :Shr 1
			EndIf
			
		EndIf
	
	EndIf
	
	If KeyHit(KEY_LEFT) Then
	
		gridleft grid
	
	ElseIf KeyHit(KEY_RIGHT) Then
		
		gridright grid
	
	ElseIf KeyHit(KEY_UP) Then
		
		gridup grid
		
	ElseIf KeyHit(KEY_DOWN) Then
	
		griddown grid
		
	EndIf
EndFunction




Function gridup:Int Ptr(grid:Int Ptr)
	Local x, y, lx
	For x = 0 Until SIZE
		lx = 0
		For y = 0 Until SIZE
			If grid[x+y*SIZE] Then
				If lx <> y Then
					grid[x+lx*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx + 1
			EndIf
		Next
		For y = 0 Until SIZE-1
			If grid[x+y*SIZE] = grid[x+(y+1)*SIZE] Then
				grid[x+y*SIZE] :Shl 1
				grid[x+(y+1)*SIZE] = 0
			EndIf
		Next
		lx = 0
		For y = 0 Until SIZE
			If grid[x+y*SIZE] Then
				If lx <> y Then
					grid[x+lx*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx + 1
			EndIf
		Next
	Next
	Return grid

EndFunction

Function gridleft:Int Ptr(grid:Int Ptr)
	Local x, y, lx
	For y = 0 Until SIZE
		lx = 0
		For x = 0 Until SIZE
			If grid[x+y*SIZE] Then
				If lx <> x Then
					grid[lx+y*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx + 1
			EndIf
		Next
		For x = 0 Until SIZE-1
			If grid[x+y*SIZE] = grid[x+1+y*SIZE] Then
				grid[x+y*SIZE] :Shl 1
				grid[x+1+y*SIZE] = 0
			EndIf
		Next
		lx = 0
		For x = 0 Until SIZE
			If grid[x+y*SIZE] Then
				If lx <> x Then
					grid[lx+y*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx + 1
			EndIf
		Next
	Next
	Return grid

EndFunction


Function griddown:Int Ptr(grid:Int Ptr)
	Local x, y, lx
	For x = 0 Until SIZE
		lx = SIZE-1
		For y = SIZE-1 To 0 Step -1
			If grid[x+y*SIZE] Then
				If lx <> y Then
					grid[x+lx*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx - 1
			EndIf
		Next
		For y = SIZE-1 To 1 Step -1
			If grid[x+y*SIZE] = grid[x+(y-1)*SIZE] Then
				grid[x+y*SIZE] :Shl 1
				grid[x+(y-1)*SIZE] = 0
			EndIf
		Next
		lx = SIZE-1
		For y = SIZE-1 To 0 Step -1
			If grid[x+y*SIZE] Then
				If lx <> y Then
					grid[x+lx*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx - 1
			EndIf
		Next
	Next
	Return grid
EndFunction


Function gridright:Int Ptr(grid:Int Ptr)
	Local x, y, lx
	For y = 0 Until SIZE
		lx = SIZE-1
		For x = SIZE-1 To 0 Step -1
			If grid[x+y*SIZE] Then
				If lx <> x Then
					grid[lx+y*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx - 1
			EndIf
		Next
		For x = SIZE-1 To 1 Step -1
			If grid[x+y*SIZE] = grid[x-1+y*SIZE] Then
				grid[x+y*SIZE] :Shl 1
				grid[x-1+y*SIZE] = 0
			EndIf
		Next
		lx = SIZE-1
		For x = SIZE-1 To 0 Step -1
			If grid[x+y*SIZE] Then
				If lx <> x Then
					grid[lx+y*SIZE] = grid[x+y*SIZE]
					grid[x+y*SIZE] = 0
				EndIf
				lx = lx - 1
			EndIf
		Next
	Next
	Return grid
EndFunction




Kleine Erklärung zur Handhabe:
Ein Feld gibt man ein, indem man mit der linken Maustaste log2-Mal so oft auf ein Feld klickt, wie der Wert darin ist. Also wenn ich 32 eingeben will, bedenke ich, dass 32 = 2^5 und klicke fünfmal mit der linken Maustaste auf das Feld. Wenn ich zu oft geklickt habe, kann ich mit der rechten Maustaste den Wert wieder senken.
Mit Leertaste starte ich die Berechnung der Werte auf der rechten Seite, die angeben sollen, wie "sinnvoll" jede Richtung ist.
Mit Backspace oder Entfernen kann ich das ganze Feld löschen.
Mit den Pfeiltasten kann ich eine Verschiebung wie im Spiel vornehmen.
Mit dem Mausrad stelle ich die Anzahl der Züge ein, die vorausberechnet werden sollen. Links oben in der Ecke ist die aktuelle Einstellung.

Kleine Erklärung zum Code:
Die globale Variable grid ist ein Zeiger auf einen Speicherbereich, der ziemlich groß ist. Die ersten 4*4 Int werden verwendet, um das eingegebene Feld zu speichern. Der Speicherbereich dahinter wird für die rekursiven Funktionen check und check_rand verwendet, die das Array, das sie gerade ansehen kopieren und eine Änderung vornehmen.
Ich verwalte den Speicher selber und daher ist das Array eindimensional anzusprechen über die Formel x+y*SIZE (wobei SIZE = 4).

check_rand sucht ein freies Feld und erstellt nacheinander alle möglichen Kombinationen, des Feldes, das es bekommt, mit einer zusätzlichen zufälligen Zahl (so wie sie im Spiel jede Runde dazu kommt). Das ist immer entweder eine 2 oder eine 4.

check bewegt das Feld, das es bekommt einmal nach links/rechts/oben/unten und ruft jeweils danach immer check_rand auf, um den nächsten Zug zu berechnen.

Bewertungssystem: Wurde in irgendeiner Runde 2048 erzeugt, gibt check 100000 zurück. Ist eine Runde nicht mehr weiter spielbar (habe ich einfach mal schachmatt genannt), dann gibt die Funktion -10000 zurück, wenn es innerhalb der nächsten 3 Runden passiert oder -10, wenn mehr Runden nötig sind.
Ansonsten gibt eine bis zur maximalen Rekursionstiefe durchgespielte Runde 2 zurück.
So ergeben sich die Werte rechts. Ist nicht besonders ausgefeilt, aber ich muss sowieso erst an Performance arbeiten Very Happy

Ich würde mich wie gesagt sehr über Vorschläge freuen! Besonders gridup/griddown/gridleft/gridright sind nicht besonders gelungen Confused

PS: Und sorry, dass der Code nicht so aufgeräumt ist. Ich dachte eigentlich, das wird ein 20-zeiler oder so Surprised

ZEVS

 BeitragDi, Mai 13, 2014 18:56
Antworten mit Zitat
Benutzer-Profile anzeigen
Mir fällt auf, dass der Rückgabewert von check_rand anscheinend nur vom letzten untersuchten Feld abhängt. Außerdem wird grid kopiert, bevor check aufgerufen wird. Soweit ich das überblicke, verändert check aber das übergebene Feld nicht. Diese (und andere) temporäre Felder verbleiben dazu im Speicher. Das macht das Programm nicht gerade speicherschonend, was bei genügend RAM aber kein Performanceproblem sein sollte.

Die von dir angesprochenen grid**-Methoden sehen in der Tat nicht optimal aus. In den Funktionen gridleft und gridright lässt sich y*SIZE definitiv einmal pro Schleifendurchlauf berechnen, besser ist es, wenn du gleich einen Pointer auf grid[y*SIZE] erstellst, den du dann immer benutzt. In der äußeren Schleife hast du drei innere, die sich m.E. auf eine reduzieren lassen, in der du schaust, ob du das aktuelle Feld in die gewünschte Richtung schieben kannst und dabei gleich noch überprüfst, ob du die Felder vereinen kannst. Wenn du dabei auch gleich lx richtig anpasst, sparst du dir die dritte Schleife. Dabei solltest du in einer weiteren lokalen Variable zwischenspeichern, ob das letzte Feld bereits durch solche Zusammensetzung entstanden ist, damit nicht zu viele Felder verschmolzen werden. Wenn in einer Reihe die Zahlen 4 4 8 stehen und du dann nach links schiebst, soll ja 8 8 und nicht 16 herauskommen.
Meine Idee für gridleft in BlitzMax: [AUSKLAPPEN] 
Function gridleft:Int Ptr(grid:Int Ptr)
	Local x, y, lx, composite, lastValue, p:Int Ptr
	p = grid
	For y = 0 Until SIZE
		lx = 0
		composite = False
		lastValue = 0
		For x = 0 Until SIZE
			If p[x] Then
				If lx <> x Then
					If lx > 0 And Not composite And p[x] = lastValue Then
						p[lx-1] :Shl 1
						p[x] = 0
						composite = True
					Else
						p[lx] = p[x]
						p[x] = 0
						composite = False
					EndIf
				EndIf
				lastValue = p[x]
				lx = lx + Not composite
			EndIf
		Next
		p :+ SIZE
	Next
	Return grid

EndFunction

(ungetestet)

Schließlich würde ich diese Funktionen in C schreiben, da jede Schleife nur vielmal ausgeführt wird und der gcc (soweit ich weiß) dann die ganze Schleife wegoptimieren kann (im Zweifelsfall gcc selbst mit höchster Optimierungsstufe aufrufen und dann zusammenlinken).

Die Funktion check scheint mir auch noch nicht ideal. Wenn man eine Möglichkeit hat zu gewinnen (durch einen richtigen Zug) und zehn zu verlieren (durch die drei anderen, falschen Möglichkeiten und die sich dann ergebenden Situationen), ist das Ergebnis 0.

Wahrscheinlich aufwändiger, aber besser wäre eine Alpha-Beta-Suche. Du betrachtest das Spiel dabei als ein Spiel zwischen dem Spieler (der die vier Spielzüge oben, rechts, unten und links hat) und dem Computer (der auf jeder freie Feld eine 2 oder 4 setzen könnte).

ZEVS

DAK

 BeitragMi, Mai 14, 2014 9:15
Antworten mit Zitat
Benutzer-Profile anzeigen
Mal nur teilweise dazugehörend gibt es auf Stackoverflow eine Frage, wo die bislang besten Lösungsalgos zusammengefasst sind: klick

Da du dich ja hauptsächlich für die Geschwindigkeit und weniger für den Algo interessierst hier noch ein paar Tipps:

Solltest du die Möglichkeit haben, nach 64-bit zu kompilieren, dann würde es sich anbieten, den gesamten Spielstand in einem 64-bit int zu kodieren. Dazu wird das ganze Ding in 16 4-Bit Teile aufzuteilen, wobei jedes dieser Teile ein Feld repräsentiert. Die Spielsteine werden dabei nicht mit ihren eigentlichen Zahlen angeschrieben, sondern so:

0 = 0
2 = 1
4 = 2
8 = 3
...

(Wobei hald der linke Wert die Zahl ist, die der Spieler sieht, und der rechte Wert die Zahl ist, die im Speicher steht)

Auf diese Weise passt dein ganzes Spielfeld in ein einziges Register.

Kannst du nur nach 32-bit kompilieren, dann bringt diese Darstellung immer noch was, passt ja immerhin das ganze Spielfeld in zwei Register, was acht mal besser ist als im Moment.

Wenn du es dann noch schaffst, das Verschieben usw. hin zu kriegen, ohne Branches (if usw) zu verwenden, dann wird das Ganze auch noch deutlich schneller, da du die Pipeline richtig ausnützt. Musst dazu hald schauen, dass du die Moves als logische Funktionen hinkriegst.

Als Beispiel:
Code: [AUSKLAPPEN]
row = eine Zeile am Spielfeld (Nicht das ganze Spielfeld!), 16-bit

unsigned short row = 0x1FF0;

#Schlecht
if ((row && 0xF000)==0x0000) {
     row = row << 4
}

#Besser
row = (((row & 0xF000)!=0)-1)&(row<<4) | (((row & 0xF000)==0)-1)&(row);


Dabei werden zwar hier aus 3 Operationen 10 Operationen, dafür wird die Pipeline nicht geflusht, was ordentlich was an Geschwindigkeit rausholen kann. Ist aber hald etwas mehr Arbeit.

Echte Schleifen (die fix x mal durchlaufen) sind hier weniger ein Problem als ein if, da diese die Pipeline kaum belasten.
Gewinner der 6. und der 68. BlitzCodeCompo

Thunder

 BeitragMi, Mai 14, 2014 22:15
Antworten mit Zitat
Benutzer-Profile anzeigen
Wow vielen Dank, ZEVS, für dein gutes Auge! Also der Fehler in check_rand wäre mir nicht aufgefallen...
Deine Funktion hat zwar nicht auf Anhieb funktioniert, aber ich konnte dann eine ähnliche programmieren, das war ein guter Tipp Wink Und mit gcc hattest du recht, der optimiert das sehr gut (wie ich es sehe).

DAK: Danke auch für den Link zu Stackoverflow! Im zweiten Beitrag oder so hat ein Typ erwähnt, dass er das das ganze Feld in einem 64 bit Register speichert und die Verschieboperationen zeilen-/spaltenweise per Lookup-Tabelle realisiert. Also im Voraus alle möglichen Kombinationen und zugehörige Endprodukte von Verschiebungen berechnet und abspeichert, sodass er dann nur Ersetzungen hat, was mir wahrscheinlich etwas Performance bringen wird.

Nach 64bit kompilieren werde ich nicht (weil ich ja BlitzMax als Framework will), aber ich nehme einfach per Assemblerroutinen MMX zuhilfe und die BlitzMax-Funktionen verwenden Short-Zeiger (ein Short = eine Zeile).

Ich werde auch versuchen, das ganze etwas von Bruteforce wegzubringen, wenn möglich. Habe schon begonnen über minimax- und Alpha-Beta-Suche zu lesen, aber da muss ich mich erst hineinarbeiten.
Das Programm arbeite ich gerade um, sodass es mit diesen "gepackten" 64bit Feldern zurechtkommt.

Sollte das Programm mal praktisch einsetzbar sein, liefere ich den Code noch nach Very Happy

Neue Antwort erstellen


Übersicht Sonstiges Smalltalk

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group