Die Anatomie eines skalierbaren Problems
Als Informatiker betrachte ich die Welt vorzugsweise durch die Linse der Skalierbarkeit. Ein Problem in einem kleinen, isolierten Datenraum zu lösen, ist oft trivial. Die wahre informationstechnische Herausforderung entsteht erst dann, wenn wir die Parameter verändern und die Komplexität ins Unermessliche steigern. Nur so lässt sich prüfen, ob Lösungsansätze und Methoden tatsächlich robust sind.
Um dieses Prinzip greifbar zu machen, habe ich das bekannte Logik-Spiel 2048 als Basis für ein softwaretechnisches Experiment genutzt. In seiner klassischen 4x4-Variante ist 2048 für das menschliche Gehirn bereits eine kognitive Herausforderung, die nur wenige konsistent meistern. Doch was passiert, wenn wir dieses Problem skalieren?
In meinem Programm lässt sich das Spielfeld dynamisch erweitern – von 4x4 Feldern bis hin zu gigantischen 20x20 Matrizen. Mit jedem zusätzlichen Rasterfeld explodiert die kombinatorische Komplexität. Ab einer bestimmten Größe reicht die Lebensspanne eines Menschen schlichtweg nicht mehr aus, um das Spiel durch manuelle Züge bis zu seinem mathematischen Ende zu spielen. Die Anzahl der möglichen Zustände übersteigt die menschliche Handlungskapazität um ein Vielfaches.
Wenn der Mensch scheitert, übernimmt die Maschine
An diesem Punkt greift das Kernprinzip der Informatik: Wir übergeben das unlösbar gewordene Problem an Algorithmen. Ich habe das Programm um automatische Lösungsmechanismen erweitert (Random-Walk und zyklische Heuristiken).
Auf Tastendruck beginnt der Computer, das Spiel selbstständig fortzuführen – exakt so schnell, wie es der Prozessor des jeweiligen Systems erlaubt. Als Beobachter kann man dem System live dabei zusehen, wie es im Bruchteil von Sekunden Tausende von Berechnungen durchführt, sich durch riesige Spielfelder iteriert und Lösungsstrategien gnadenlos ausführt. Es ist eine faszinierende visuelle Demonstration davon, wie rohe algorithmische Rechenleistung Probleme bewältigt, vor denen der menschliche Verstand kapitulieren muss.
Warum PureBasic?
Ich habe dieses Projekt bewusst in PureBasic programmiert. Basic ist in seiner Syntax die wohl einfachste und lesbarste Programmiersprache der Welt. Der Code ist prozedural, extrem performant und kommt ohne überladene Frameworks aus. Zudem kann jeder Interessierte die kostenlose Demo-Version des PureBasic-Compilers nutzen, um diesen Code direkt auf seinem eigenen Rechner zum Laufen zu bringen und die Grenzen der Skalierbarkeit selbst zu testen.
Die Steuerung
Das Programm wird komplett über die Tastatur bedient. Sie können selbst spielen, die Matrix skalieren oder der Maschine die Kontrolle übergeben:
- Pfeiltasten: Manuelle Züge des Spielers.
- [+] / [-]: Spielfeld vergrößern oder verkleinern (von 4x4 bis 20x20).
- Taste [1]: Auto-Modus "Zufall" starten (die Maschine wählt valide Züge).
- Taste [2]: Auto-Modus "Zyklus" starten (strenge Abfolge: Links, Unten, Rechts, Oben).
- Taste [S]: SpeedFreeze aktivieren/deaktivieren. Unterdrückt visuelle Updates und schaltet die Maschine auf maximale Berechnungsgeschwindigkeit.
- Leertaste [Space]: Den Auto-Modus sofort stoppen.
- Taste [ESC]: Das Spiel hart zurücksetzen und neu starten.
Der Quellcode
Hier ist der vollständige PureBasic-Quellcode für das Projekt. Einfach kopieren, im Editor einfügen und kompilieren.
; =====================================================================
; 2048 - PureBasic Edition (MAX als Potenz + WERT als echter Spielwert)
; =====================================================================
EnableExplicit
#MinGrid = 4
#MaxGrid = 20
Global GridSize.i = 4
Global Dim Board(20, 20)
Global Score.l = 0
Global HighScore.l = 0
Global MoveCount.l = 0
Global GameOver.i = #False
; Automatisierungs-Modi: 0 = Aus, 1 = Zufall (Taste 1), 2 = Zyklus (Taste 2)
Global AutoMode.i = 0
Global SpeedFreeze.i = #False
Global LastMoveTime.q = 0
#AutoDelay = 15
; Zustand für den zyklischen Zug (0: Links, 1: Unten, 2: Rechts, 3: Oben)
Global CycleIndex.i = 0
Structure TileColor
BG.i
FG.i
EndStructure
Global Dim Colors.TileColor(25)
Procedure InitColors()
Colors(0)\BG = RGB(205, 193, 180) : Colors(0)\FG = RGB(205, 193, 180)
Colors(1)\BG = RGB(248, 245, 240) : Colors(1)\FG = RGB(119, 110, 101)
Colors(2)\BG = RGB(238, 228, 218) : Colors(2)\FG = RGB(119, 110, 101)
Colors(3)\BG = RGB(242, 205, 172) : Colors(3)\FG = RGB(119, 110, 101)
Colors(4)\BG = RGB(242, 177, 121) : Colors(4)\FG = RGB(255, 255, 255)
Colors(5)\BG = RGB(245, 149, 99) : Colors(5)\FG = RGB(255, 255, 255)
Colors(6)\BG = RGB(246, 124, 95) : Colors(6)\FG = RGB(255, 255, 255)
Colors(7)\BG = RGB(246, 94, 59) : Colors(7)\FG = RGB(255, 255, 255)
Colors(8)\BG = RGB(214, 69, 35) : Colors(8)\FG = RGB(255, 255, 255)
Colors(9)\BG = RGB(184, 50, 20) : Colors(9)\FG = RGB(255, 255, 255)
Colors(10)\BG = RGB(150, 35, 15) : Colors(10)\FG = RGB(255, 255, 255)
Colors(11)\BG = RGB(115, 22, 10) : Colors(11)\FG = RGB(255, 255, 255)
Colors(12)\BG = RGB(85, 15, 8) : Colors(12)\FG = RGB(255, 255, 255)
Colors(13)\BG = RGB(60, 10, 5) : Colors(13)\FG = RGB(255, 255, 255)
Colors(14)\BG = RGB(40, 20, 20) : Colors(14)\FG = RGB(255, 255, 255)
Colors(15)\BG = RGB(25, 25, 25) : Colors(15)\FG = RGB(255, 255, 255)
EndProcedure
Procedure.i GetPower(val.i)
If val <= 0 : ProcedureReturn 0 : EndIf
Protected p = 0
While val > 1
val / 2
p + 1
Wend
ProcedureReturn p
EndProcedure
Procedure.i GetMaxPowerOnBoard()
Protected x, y, maxP = 0, p
For x = 0 To GridSize - 1
For y = 0 To GridSize - 1
p = GetPower(Board(x, y))
If p > maxP
maxP = p
EndIf
Next
Next
ProcedureReturn maxP
EndProcedure
Procedure.q GetMaxRealValueOnBoard()
Protected x, y, maxVal = 0
For x = 0 To GridSize - 1
For y = 0 To GridSize - 1
If Board(x, y) > maxVal
maxVal = Board(x, y)
EndIf
Next
Next
ProcedureReturn maxVal
EndProcedure
Procedure AddRandomTile()
Protected x, y, count = 0
Protected Dim FreeTiles.Point(400)
For x = 0 To GridSize - 1
For y = 0 To GridSize - 1
If Board(x, y) = 0
If count <= 400
FreeTiles(count)\x = x
FreeTiles(count)\y = y
count + 1
EndIf
EndIf
Next
Next
If count > 0
Protected r = Random(count - 1)
Protected val = 2
If Random(9) = 0
val = 4
EndIf
Board(FreeTiles(r)\x, FreeTiles(r)\y) = val
EndIf
EndProcedure
Procedure ResetGame()
Protected x, y
For x = 0 To 20
For y = 0 To 20
Board(x, y) = 0
Next
Next
Score = 0
MoveCount = 0
CycleIndex = 0
AutoMode = 0
SpeedFreeze = #False
GameOver = #False
AddRandomTile()
AddRandomTile()
EndProcedure
Procedure.i CheckMovesAvailable()
Protected x, y
For x = 0 To GridSize - 1
For y = 0 To GridSize - 1
If Board(x, y) = 0
ProcedureReturn #True
EndIf
If x < GridSize - 1 And Board(x, y) = Board(x + 1, y)
ProcedureReturn #True
EndIf
If y < GridSize - 1 And Board(x, y) = Board(x, y + 1)
ProcedureReturn #True
EndIf
Next
Next
ProcedureReturn #False
EndProcedure
Procedure.i ShiftLineLeft(*Line.Integer, *ScoreInc.Integer, size.i)
Protected i
Protected Dim Original(25)
Protected Dim Row(25)
For i = 0 To size - 1
Original(i) = PeekI(*Line + i * SizeOf(Integer))
Row(i) = Original(i)
Next
Protected Dim Temp(25), tCount = 0
For i = 0 To size - 1
If Row(i) > 0
Temp(tCount) = Row(i)
tCount + 1
EndIf
Next
For i = 0 To size - 1 : Row(i) = 0 : Next
For i = 0 To tCount - 1 : Row(i) = Temp(i) : Next
For i = 0 To size - 2
If Row(i) > 0 And Row(i) = Row(i + 1)
Row(i) * 2
*ScoreInc\i = *ScoreInc\i + Row(i)
Row(i + 1) = 0
i + 1
EndIf
Next
For i = 0 To size - 1 : Temp(i) = 0 : Next
tCount = 0
For i = 0 To size - 1
If Row(i) > 0
Temp(tCount) = Row(i)
tCount + 1
EndIf
Next
For i = 0 To size - 1 : Row(i) = 0 : Next
For i = 0 To tCount - 1 : Row(i) = Temp(i) : Next
Protected changed = #False
For i = 0 To size - 1
If Original(i) <> Row(i)
changed = #True
EndIf
PokeI(*Line + i * SizeOf(Integer), Row(i))
Next
ProcedureReturn changed
EndProcedure
Procedure.i ProcessGameMove(Direction.i, SimulateOnly.i, *ScoreOutput.Integer)
Protected x, y, moved = #False
Protected Dim SimBoard(20, 20)
For x = 0 To GridSize - 1
For y = 0 To GridSize - 1
SimBoard(x, y) = Board(x, y)
Next
Next
Protected totalInc = 0
Select Direction
Case 1 ; Links
For y = 0 To GridSize - 1
Protected Dim ColL(25)
For x = 0 To GridSize - 1 : ColL(x) = SimBoard(x, y) : Next
If ShiftLineLeft(@ColL(0), @totalInc, GridSize) : moved = #True : EndIf
For x = 0 To GridSize - 1 : SimBoard(x, y) = ColL(x) : Next
Next
Case 2 ; Rechts
For y = 0 To GridSize - 1
Protected Dim ColR(25)
For x = 0 To GridSize - 1 : ColR(x) = SimBoard(GridSize - 1 - x, y) : Next
If ShiftLineLeft(@ColR(0), @totalInc, GridSize) : moved = #True : EndIf
For x = 0 To GridSize - 1 : SimBoard(GridSize - 1 - x, y) = ColR(x) : Next
Next
Case 3 ; Oben
For x = 0 To GridSize - 1
Protected Dim ColU(25)
For y = 0 To GridSize - 1 : ColU(y) = SimBoard(x, y) : Next
If ShiftLineLeft(@ColU(0), @totalInc, GridSize) : moved = #True : EndIf
For y = 0 To GridSize - 1 : SimBoard(x, y) = ColU(y) : Next
Next
Case 4 ; Unten
For x = 0 To GridSize - 1
Protected Dim ColD(25)
For y = 0 To GridSize - 1 : ColD(y) = SimBoard(x, GridSize - 1 - y) : Next
If ShiftLineLeft(@ColD(0), @totalInc, GridSize) : moved = #True : EndIf
For y = 0 To GridSize - 1 : SimBoard(x, GridSize - 1 - y) = ColD(y) : Next
Next
EndSelect
*ScoreOutput\i = totalInc
If Not SimulateOnly And moved
For x = 0 To 20
For y = 0 To 20
Board(x, y) = SimBoard(x, y)
Next
Next
EndIf
ProcedureReturn moved
EndProcedure
Procedure.l GetPreviewPoints(Direction.i)
Protected dummyScore = 0
ProcessGameMove(Direction, #True, @dummyScore)
ProcedureReturn dummyScore
EndProcedure
Procedure.i ExecuteMove(dir.i)
Protected s = 0, m = ProcessGameMove(dir, #False, @s)
If m
Score + s
MoveCount + 1
If Score > HighScore
HighScore = Score
EndIf
EndIf
ProcedureReturn m
EndProcedure
Procedure.i MoveLeft() : ProcedureReturn ExecuteMove(1) : EndProcedure
Procedure.i MoveRight() : ProcedureReturn ExecuteMove(2) : EndProcedure
Procedure.i MoveUp() : ProcedureReturn ExecuteMove(3) : EndProcedure
Procedure.i MoveDown() : ProcedureReturn ExecuteMove(4) : EndProcedure
Procedure.i MakeCycleMove()
Protected Dim Dirs.i(4)
Dirs(0) = 1
Dirs(1) = 4
Dirs(2) = 2
Dirs(3) = 3
Protected i, checkDir, dummyScore = 0, moved = #False
For i = 0 To 3
Protected idx = (CycleIndex + i) % 4
checkDir = Dirs(idx)
If ProcessGameMove(checkDir, #True, @dummyScore)
Select checkDir
Case 1 : moved = MoveLeft()
Case 4 : moved = MoveDown()
Case 2 : moved = MoveRight()
Case 3 : moved = MoveUp()
EndSelect
CycleIndex = (idx + 1) % 4
Break
EndIf
Next
ProcedureReturn moved
EndProcedure
Procedure.i MakeRandomValidMove()
Protected Dim ValidDirs.i(5)
Protected count = 0, d
Protected dummyScore = 0
For d = 1 To 4
If ProcessGameMove(d, #True, @dummyScore)
If count < 5
ValidDirs(count) = d
count + 1
EndIf
EndIf
Next
If count > 0
Protected chosenDir = ValidDirs(Random(count - 1))
Select chosenDir
Case 1 : ProcedureReturn MoveLeft()
Case 2 : ProcedureReturn MoveRight()
Case 3 : ProcedureReturn MoveUp()
Case 4 : ProcedureReturn MoveDown()
EndSelect
EndIf
ProcedureReturn #False
EndProcedure
Procedure DrawSidebarOnly()
Protected winW = GadgetWidth(0)
Protected winH = GadgetHeight(0)
Protected boardSize = winH
If StartDrawing(CanvasOutput(0))
Protected sidebarX = boardSize + 10
Protected sidebarW = winW - sidebarX
If sidebarW > 50
DrawingMode(#PB_2DDrawing_AllChannels)
Box(sidebarX, 0, sidebarW, winH, RGB(250, 248, 239))
DrawingMode(#PB_2DDrawing_Transparent)
DrawingFont(FontID(0))
Protected textX = sidebarX + 15
Protected curY = 25
Protected lineH = 22
DrawText(textX, curY, "GRID: " + Str(GridSize) + " x " + Str(GridSize), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "SCORE: " + Str(Score), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "BEST: " + Str(HighScore), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "MOVES: " + Str(MoveCount), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "MAX: " + Str(GetMaxPowerOnBoard()), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "WERT: " + Str(GetMaxRealValueOnBoard()), RGB(0, 0, 0)) : curY + lineH + 12
DrawText(textX, curY, "--- VORSCHAU ---", RGB(0, 0, 0)) : curY + lineH
Protected pUp = GetPreviewPoints(3)
Protected pDown = GetPreviewPoints(4)
Protected pLeft = GetPreviewPoints(1)
Protected pRight = GetPreviewPoints(2)
DrawText(textX, curY, "↑ Oben: +" + Str(pUp), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "↓ Unten: +" + Str(pDown), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "← Links: +" + Str(pLeft), RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "→ Rechts: +" + Str(pRight), RGB(0, 0, 0)) : curY + lineH + 12
DrawText(textX, curY, "--- STEUERUNG ---", RGB(0, 0, 0)) : curY + lineH
If AutoMode = 1
DrawText(textX, curY, "1: Auto-Zufall [RUN]", RGB(0, 0, 0)) : curY + lineH
Else
DrawText(textX, curY, "1: Auto-Zufall", RGB(0, 0, 0)) : curY + lineH
EndIf
If AutoMode = 2
DrawText(textX, curY, "2: Auto-Zyklus [RUN]", RGB(0, 0, 0)) : curY + lineH
Else
DrawText(textX, curY, "2: Auto-Zyklus", RGB(0, 0, 0)) : curY + lineH
EndIf
If SpeedFreeze
DrawText(textX, curY, "S(peed): ON", RGB(0, 0, 0)) : curY + lineH
Else
DrawText(textX, curY, "S(peed): OFF", RGB(0, 0, 0)) : curY + lineH
EndIf
DrawText(textX, curY, "Space: Auto Stoppen", RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "ESC: Neustart", RGB(0, 0, 0)) : curY + lineH
DrawText(textX, curY, "+/-: Grid Ändern", RGB(0, 0, 0))
EndIf
StopDrawing()
EndIf
EndProcedure
Procedure DrawBoard()
Protected winW = GadgetWidth(0)
Protected winH = GadgetHeight(0)
If StartDrawing(CanvasOutput(0))
Box(0, 0, winW, winH, RGB(250, 248, 239))
Protected boardSize = winH
Protected boardX = 0
Protected boardY = 0
DrawingMode(#PB_2DDrawing_AllChannels)
Box(boardX, boardY, boardSize, boardSize, RGB(187, 173, 160))
Protected x, y, px, py, val, pow
Protected spacing = 2
Protected tileSize = (boardSize - (spacing * (GridSize + 1))) / GridSize
For y = 0 To GridSize - 1
For x = 0 To GridSize - 1
px = boardX + spacing + x * (tileSize + spacing)
py = boardY + spacing + y * (tileSize + spacing)
val = Board(x, y)
pow = GetPower(val)
Protected bgCol, fgCol
If pow > 15
bgCol = RGB(15, 15, 15)
fgCol = RGB(255, 255, 255)
Else
bgCol = Colors(pow)\BG
fgCol = Colors(pow)\FG
EndIf
DrawingMode(#PB_2DDrawing_AllChannels)
Box(px, py, tileSize, tileSize, bgCol)
If val > 0
DrawingMode(#PB_2DDrawing_Transparent)
Protected text$ = Str(pow)
Protected fontIdx = 3
If GridSize >= 12
fontIdx = 0
ElseIf GridSize >= 7
fontIdx = 2
EndIf
DrawingFont(FontID(fontIdx))
Protected textW = TextWidth(text$)
Protected textH = TextHeight(text$)
DrawText(px + (tileSize - textW) / 2, py + (tileSize - textH) / 2, text$, fgCol)
EndIf
Next
Next
StopDrawing()
EndIf
DrawSidebarOnly()
EndProcedure
If OpenWindow(0, 100, 100, 800, 600, "2048 - PureBasic Edition", #PB_Window_SystemMenu | #PB_Window_MinimizeGadget | #PB_Window_SizeGadget)
LoadFont(0, "Arial", 10, #PB_Font_Bold)
LoadFont(1, "Arial", 22, #PB_Font_Bold)
LoadFont(2, "Arial", 11, #PB_Font_Bold)
LoadFont(3, "Arial", 14, #PB_Font_Bold)
InitColors()
CanvasGadget(0, 0, 0, 800, 600, #PB_Canvas_Keyboard)
AddKeyboardShortcut(0, #PB_Shortcut_Left, 101)
AddKeyboardShortcut(0, #PB_Shortcut_Right, 102)
AddKeyboardShortcut(0, #PB_Shortcut_Up, 103)
AddKeyboardShortcut(0, #PB_Shortcut_Down, 104)
AddKeyboardShortcut(0, #PB_Shortcut_Escape, 105)
AddKeyboardShortcut(0, #PB_Shortcut_Space, 114)
AddKeyboardShortcut(0, #PB_Shortcut_1, 110)
AddKeyboardShortcut(0, #PB_Shortcut_Pad1, 111)
AddKeyboardShortcut(0, #PB_Shortcut_2, 112)
AddKeyboardShortcut(0, #PB_Shortcut_Pad2, 113)
AddKeyboardShortcut(0, #PB_Shortcut_S, 115)
AddKeyboardShortcut(0, #PB_Shortcut_Add, 106)
AddKeyboardShortcut(0, #PB_Shortcut_Subtract, 107)
AddKeyboardShortcut(0, $BB, 108)
AddKeyboardShortcut(0, $BD, 109)
ResetGame()
DrawBoard()
Define event, moved.i
Repeat
If AutoMode > 0 And Not GameOver
If ElapsedMilliseconds() - LastMoveTime >= #AutoDelay
moved = #False
If AutoMode = 1
moved = MakeRandomValidMove()
ElseIf AutoMode = 2
moved = MakeCycleMove()
EndIf
If moved
AddRandomTile()
If Not CheckMovesAvailable()
GameOver = #True
AutoMode = 0
SpeedFreeze = #False
DrawBoard()
Else
If SpeedFreeze
DrawSidebarOnly()
Else
DrawBoard()
EndIf
EndIf
Else
AutoMode = 0
SpeedFreeze = #False
DrawBoard()
EndIf
LastMoveTime = ElapsedMilliseconds()
EndIf
EndIf
event = WindowEvent()
If event = 0
Delay(5)
Continue
EndIf
Select event
Case #PB_Event_SizeWindow
ResizeGadget(0, 0, 0, WindowWidth(0), WindowHeight(0))
DrawBoard()
Case #PB_Event_Menu
Select EventMenu()
Case 101
If Not GameOver
AutoMode = 0
SpeedFreeze = #False
If MoveLeft()
AddRandomTile()
If Not CheckMovesAvailable() : GameOver = #True : DrawBoard() : EndIf
EndIf
EndIf
Case 102
If Not GameOver
AutoMode = 0
SpeedFreeze = #False
If MoveRight()
AddRandomTile()
If Not CheckMovesAvailable() : GameOver = #True : DrawBoard() : EndIf
EndIf
EndIf
Case 103
If Not GameOver
AutoMode = 0
SpeedFreeze = #False
If MoveUp()
AddRandomTile()
If Not CheckMovesAvailable() : GameOver = #True : DrawBoard() : EndIf
EndIf
EndIf
Case 104
If Not GameOver
AutoMode = 0
SpeedFreeze = #False
If MoveDown()
AddRandomTile()
If Not CheckMovesAvailable() : GameOver = #True : DrawBoard() : EndIf
EndIf
EndIf
Case 105
ResetGame()
Case 114
AutoMode = 0
SpeedFreeze = #False
DrawBoard()
Case 115
If AutoMode > 0
If SpeedFreeze
SpeedFreeze = #False
Else
SpeedFreeze = #True
EndIf
DrawBoard()
EndIf
Case 110, 111
If Not GameOver
AutoMode = 1
LastMoveTime = ElapsedMilliseconds()
DrawBoard()
EndIf
Case 112, 113
If Not GameOver
AutoMode = 2
LastMoveTime = ElapsedMilliseconds()
DrawBoard()
EndIf
Case 106, 108
If GridSize < #MaxGrid
GridSize + 1
ResetGame()
EndIf
Case 107, 109
If GridSize > #MinGrid
GridSize - 1
ResetGame()
EndIf
EndSelect
DrawBoard()
Case #PB_Event_CloseWindow
Break
EndSelect
ForEver
EndIf