2048 ai
2024-11-21
I recently competed with Shell We Hack? in BlockCTF 2024. I began late and only had the time to solve two challenges, one being this challenge, 2048 ai.
To begin, we're given the challenge description
Can you speedrun 2048?When connecting to the server using netcat as indicated the following response is provided:
nc 54.85.45.101 8006
micah@micahs_laptop ~ % nc 54.85.45.101 8006
2 0 0 0
0 0 0 2
0 0 0 0
0 0 0 0
Enter command(s) (w/a/s/d for movement, q to quit):
Entering one of w, a, s, or d (w, in this case) returns the next iteration:
Enter command(s) (w/a/s/d for movement, q to quit): w
2 0 0 2
0 0 2 0
0 0 0 0
0 0 0 0
Enter command(s) (w/a/s/d for movement, q to quit):When seeing this we can infer, given the name of the challenge, that what we're interacting with is a text-based version of the popular game 2048: https://play2048.co/. With this in mind we can safely assume that in order to get the flag, we must win the game and achieve a tile with the value of 2048.
A quick google search reveals that the average move count to win 2048 is 938.8[1], which is too large to attempt manually or by brute-force.
After fumbling around for a while with trying to modify pre-existing, old algorithms, I decided to search the challenge name, 2048 ai, on github and found this repo: https://github.com/nneonneo/2048-ai, for which the README.md contained the following instructions for manual use:
Enter board one row at a time, with entries separated by spaces
Row 1: 16 128 256 1024
Row 2: 16 8 2 0
Row 3: 8 2 0 0
Row 4: 0 4 0 0
Current board:
16 128 256 1024
16 8 2 0
8 2 0 0
0 4 0 0
Enter updates in the form r,c,n (1-indexed row/column), separated by spaces:
16 128 256 1024
16 8 2 0
8 2 0 0
0 4 0 0
005.030340: Score 0, Move 1: up
EXECUTE MOVE: up
Current board:
32 128 256 1024
8 8 2 0
0 2 0 0
0 4 0 0
Enter updates in the form r,c,n (1-indexed row/column), separated by spaces: 3,1,4
32 128 256 1024
8 8 2 0
4 2 0 0
0 4 0 0
035.648508: Score 0, Move 2: left
EXECUTE MOVE: left
Current board:
32 128 256 1024
16 2 0 0
4 2 0 0
4 0 0 0
Enter updates in the form r,c,n (1-indexed row/column), separated by spaces: 4,3,2
32 128 256 1024
16 2 0 0
4 2 0 0
4 0 2 0
058.927319: Score 0, Move 3: left
EXECUTE MOVE: leftThe challenge author was likely referencing this specific repository when creating the challenge. The solution path then becomes clear[2]:
- Clone the repo and follow the install instructions
- Set up a listener for the solver ai
- Write a script to connect the two, passing the game-board from the remote server to the solver script, and vice-versa
- flag
A bit later in the morning I completed the following spaghetti-code python script:
from pwn import *
game = remote('54.85.45.101', 8006)
solver = remote('127.0.0.1', 1337)
#Receiving and setting up the initial board from the game
game_response = game.recvuntil(b'quit):')
current_board = []
for row in game_response.decode().splitlines():
current_board.append([x for x in row.split()])
current_board.pop(0)
current_board.pop(-1)
current_board.pop(-1)
current_board = [[int(j) for j in i] for i in current_board]
def printboard(name, b):
print()
print(name+ ":")
for i in range(4):
current_row = " ".join(str(x) for x in b[i])
print(current_row, end="\n")
print()
printboard("Gameboard from gameserver", current_board)
#Sending the initial board off to the solver
print("Sending to solver...:")
for i in range(4):
canary = b'Row ' + str(i + 1).encode() + b':'
solver.recvuntil(canary)
current_row = " ".join(str(x) for x in current_board[i]).encode()
print(current_row)
solver.send(current_row + b'\n')
solver_reponse = solver.recvuntil(b'spaces:')
print(solver_reponse.decode())
solver.send(b'\n')
print("\\n")
while True:
solver_reponse = solver.recvuntil(b'spaces:')
print(solver_reponse.decode())
solver_response_array = []
for row in solver_reponse.decode().splitlines():
solver_response_array.append([x for x in row.split()])
for i in range(5):
solver_response_array.pop(0)
solver_response_array.pop(1)
solver_response_array.pop(-1)
solver_move_choice, solver_new_board = solver_response_array[0][2], solver_response_array[1:]
printboard("Solve board after move" ,solver_new_board)
printboard("Game board before move: ", current_board)
#Makes the move the AI decided in the actual game, and output the delta with the new squares in r,c,n format
match solver_move_choice:
case "left":
solver_move_choice = b'a'
case "right":
solver_move_choice = b'd'
case "up":
solver_move_choice = b'w'
case "down":
solver_move_choice = b's'
game.send(solver_move_choice + b'\n')
try:
game_response = game.recvuntil(b'quit):')
except:
game.interactive() #FOUND THE FLAG!
current_board = []
for row in game_response.decode().splitlines():
current_board.append([x for x in row.split()])
current_board.pop(0)
current_board.pop(-1)
current_board.pop(-1)
current_board = [[int(j) for j in i] for i in current_board]
printboard("Game board after move", current_board)
#calcluating the r,c,n by checking the delta:
deltas = []
for i in range(4):
for j in range(4):
if int(solver_new_board[i][j]) != current_board[i][j]:
deltas.append(str(i + 1) + "," + str(j + 1) + "," + str(current_board[i][j]))
#send off deltas, repeat entire process until 2048 is achieved
solver.send(" ".join(deltas).encode() + b'\n')
print(" ".join(deltas))Running the script hammers the terminal with several dozen moves per second, however after 940 moves we are greeted with the beautiful 2048 tile and the following output:
Game board before move:
2 0 0 4
0 0 0 2
2 2 8 4
1024 1024 32 2
[*] Switching to interactive mode
2 4 2 0
2 0 0 0
4 8 4 0
2048 32 2 0
Congratulations! You reached 2048 and won the game!
flag{f4st3r_th4n_hum4nly_p0ssibl3}
[*] Got EOF while reading in interactiveThis solves the challenge and outputs the flag: flag{f4st3r_th4n_hum4nly_p0ssibl3}
-
https://jdlm.info/articles/2017/08/05/markov-chain-2048.html ⮐
-
Of course there is an easier way to achieve the same result, which is to manually change the functions within the solver library, but I thought passing the board data back and forth between connections was abstractly much more pleasing and decided to continue down that route ⮐