2048 AI Python Highest Possible Score
Introduction:
This was a project undergone in a group of people which were me and a person called Edwin. While I was responsible for the Highest Score code, Edwin was responsible for the Monte Carlo code and since they are both distinct, I believed that they both deserved their own article. Both have their advantages and disadvantages and in the application of a real AI, the Monte Carlo method would be the only viable option because the Highest Score has a cheaty nature in that it can decide the best board out of an option of many boards. Nonetheless, it is still very satisfying seeing the code get a winning board(2048 tile) in under a second using the code.
To see the results of the codes, I am attaching a graph of the results of the code so you can gauge its performance for yourself. Note, our scoring system is slightly different to the real scoring system of 2048 where the score is decided by the sum of all the tiles on the grid.
If you run for very high DEPTHS eg. depth 10, I ran it for 2 hours and it hit max score of a 65,536 tile! You can see the final grid of depth 8 on the right of the grid on the pycharm terminal.
import random
import numpy as np
import sys
import time
from itertools import product
import matplotlib.pyplot as plt
ROW_LENGTH = 4
STARTING_NUMBERS = 2
CHANCE_OF_TWO = 90
PLAYER_SCORE = 0
TOTAL_MOVES = 0
NUMBER_OF_RUNS = 7
POSSIBLE_MOVES = ["up", "right", "down", "left"]
DEPTH = 2
POSSIBLE_ARRANGEMENTS = product(POSSIBLE_MOVES, repeat=DEPTH)
TEMPLATE = [[0.135, 0.121, 0.102, 0.0999],
[0.0997, 0.088, 0.076, 0.0724],
[0.0606, 0.0562, 0.0371, 0.0161],
[0.0125, 0.0099, 0.0057, 0.0033]]
BEST_DIRECTION = ""
BEST_SCORE = 0
BEST_GRID = None
PLT_SCORE = [[],[],[],[]]
def generateTile():
RANDOM_NUM = random.randint(1, 100)
if RANDOM_NUM < CHANCE_OF_TWO:
number = 2
else:
number = 4
return number
def createGrid(dimensions):
grid = [[0 for i in range(dimensions)] for j in range(dimensions)]
for i in range(STARTING_NUMBERS):
number = generateTile()
grid[random.randint(0, ROW_LENGTH - 1)][random.randint(0, ROW_LENGTH - 1)] = number
displayGrid(grid)
return grid
def displayGrid(*grids):
for grid in grids:
print(np.array(grid))
def evalgrid(grid):
return np.sum(np.array(grid) * TEMPLATE)
def move(direction, grid, score):
if direction == "left" or direction == "right":
for i in range(ROW_LENGTH):
if direction == "right": grid[i] = grid[i][::-1]
for j in range(grid[i].count(0)):
grid[i].append(grid[i].pop(grid[i].index(0)))
for element in range(0, ROW_LENGTH - 1):
if grid[i][element] == grid[i][element + 1]:
score += grid[i][element] * 2
grid[i][element] = grid[i][element] * 2
grid[i].remove(grid[i][element + 1])
grid[i].append(0)
if direction == "right": grid[i] = grid[i][::-1]
return grid, score
else:
collection = [grid[j][i] for i in range(0, ROW_LENGTH) for j in range(0, ROW_LENGTH)]
vGrid = [collection[i * ROW_LENGTH:((i + 1) * ROW_LENGTH)] for i in range(ROW_LENGTH)]
for i in range(ROW_LENGTH):
if direction == "down": vGrid[i] = vGrid[i][::-1]
for j in range(vGrid[i].count(0)):
vGrid[i].append(vGrid[i].pop(vGrid[i].index(0)))
for element in range(0, ROW_LENGTH - 1):
if vGrid[i][element] == vGrid[i][element + 1]:
score += grid[i][element] * 2
vGrid[i][element] = vGrid[i][element] * 2
vGrid[i].remove(vGrid[i][element + 1])
vGrid[i].append(0)
if direction == "down": vGrid[i] = vGrid[i][::-1]
for row in range(ROW_LENGTH):
for column in range(ROW_LENGTH):
grid[row][column] = vGrid[column][row]
return grid, score
def check(grid):
gridArr = []
for direction in POSSIBLE_MOVES:
temp = [x[:] for x in grid]
gridArr.append(move(direction, temp, PLAYER_SCORE))
for potentialGrid in gridArr:
if grid != potentialGrid[0]:
return False
return True
def updateGrid(grid, state):
count = 0
for i in range(ROW_LENGTH):
count += grid[i].count(0)
if not count:
if check(grid):
return grid, True
if state == True:
while True:
row = random.randint(0, ROW_LENGTH - 1)
column = random.randint(0, ROW_LENGTH - 1)
if grid[row][column] == 0:
grid[row][column] = generateTile()
return grid, False
return grid, False
def bestmove(grid, CURR_DEPTH, SET_OF_MOVES, currentscore):
CURR_DEPTH += 1
placeholder = [x[:] for x in grid]
if CURR_DEPTH != DEPTH:
for DIRECTION in POSSIBLE_MOVES:
grid = move(DIRECTION, grid, currentscore)[0]
SET_OF_MOVES.append(DIRECTION)
# print(f"Depth {CURR_DEPTH}")
# displayGrid(grid)
if grid != placeholder:
grid = updateGrid(grid, True)[0]
bestmove(grid, CURR_DEPTH, SET_OF_MOVES, currentscore)
SET_OF_MOVES.pop()
grid = [x[:] for x in placeholder]
return
else:
global BEST_SCORE
global BEST_DIRECTION
global BEST_GRID
SCORE = evalgrid(grid)
if BEST_SCORE < SCORE:
BEST_SCORE = SCORE
BEST_DIRECTION = SET_OF_MOVES[0]
BEST_GRID = grid
return
return
def main():
board = createGrid(ROW_LENGTH)
TOTAL_MOVES = 0
PLAYER_SCORE = 0
while board:
# PLAYER_CURRENT_MOVE= input(f"Enter your move, your current score is {PLAYER_SCORE}")
# PLAYER_CURRENT_MOVE=random.choice(POSSIBLE_MOVES)
BEST_SCORE = 0
BEST_DIRECTION = ""
bestmove(board, 0, [], PLAYER_SCORE)
# sys.exit()
placeholder = [x[:] for x in board]
board = BEST_GRID
if placeholder == board:
ended = True
else:
board, ended = updateGrid(board, True)
TOTAL_MOVES += 1
if TOTAL_MOVES%1000==0:
displayGrid(board)
if ended:
displayGrid(board)
print("DONE")
PLAYER_SCORE = sum(map(sum,board))
return TOTAL_MOVES, PLAYER_SCORE
for i in range(NUMBER_OF_RUNS):
start = time.time()
moves, score = main()
PLT_SCORE[0].append(DEPTH)
PLT_SCORE[1].append(score)
PLT_SCORE[2].append(moves)
PLT_SCORE[3].append(time.time()-start)
DEPTH += 1
print(i)
figure, axis = plt.subplots(1,3)
axis[0].plot(PLT_SCORE[0], PLT_SCORE[1])
axis[0].set_title("Depth VS. Score")
axis[1].plot(PLT_SCORE[0], PLT_SCORE[2])
axis[1].set_title("Depth VS. Moves")
axis[2].plot(PLT_SCORE[0], PLT_SCORE[3])
axis[2].set_title("Depth VS. Time")
plt.show()
sys.exit()
Cheatiness:
Edwin and I had a debate about the inherent cheatiness of this code because of the way it operates, what I do here is by using recursion, I am building a game tree of the possibilities of future grids.
This is an example of a game tree and what my code does is it generates a game tree of a certain depth which we state and then from the resultant grids that are generated, I choose the grid which has the greatest evaluation which means its the most optimal grid. We do this using a heuristic function which is a combination of the sum of all the numbers on the grid but also a matrix which we copied from someone else on the internet who has create a far superior AI to our own.
The majority of the code is built to get the functional game of 2048 working and right now it is all printing onto the terminal but we hope that with some time we may be able to visualise it so it looks more aesthetically pleasing. We had to make our move functions as efficient as possible because without it, we would be wasting a lot of computation time having the code generate the next grid and because of this we created the move function as follows:
def move(direction, grid, score):
if direction == "left" or direction == "right":
for i in range(ROW_LENGTH):
if direction == "right": grid[i] = grid[i][::-1]
for j in range(grid[i].count(0)):
grid[i].append(grid[i].pop(grid[i].index(0)))
for element in range(0, ROW_LENGTH - 1):
if grid[i][element] == grid[i][element + 1]:
score += grid[i][element] * 2
grid[i][element] = grid[i][element] * 2
grid[i].remove(grid[i][element + 1])
grid[i].append(0)
if direction == "right": grid[i] = grid[i][::-1]
return grid, score
else:
collection = [grid[j][i] for i in range(0, ROW_LENGTH) for j in range(0, ROW_LENGTH)]
vGrid = [collection[i * ROW_LENGTH:((i + 1) * ROW_LENGTH)] for i in range(ROW_LENGTH)]
for i in range(ROW_LENGTH):
if direction == "down": vGrid[i] = vGrid[i][::-1]
for j in range(vGrid[i].count(0)):
vGrid[i].append(vGrid[i].pop(vGrid[i].index(0)))
for element in range(0, ROW_LENGTH - 1):
if vGrid[i][element] == vGrid[i][element + 1]:
score += grid[i][element] * 2
vGrid[i][element] = vGrid[i][element] * 2
vGrid[i].remove(vGrid[i][element + 1])
vGrid[i].append(0)
if direction == "down": vGrid[i] = vGrid[i][::-1]
for row in range(ROW_LENGTH):
for column in range(ROW_LENGTH):
grid[row][column] = vGrid[column][row]
return grid, scoreWhat this effectively does it iterate through the array and whenever it encounters a 0, it will pop it and insert it to the end of the list. In the reverse direction, we can flip the list, when move the zeros and then flip the list again and this has the same effect. This means we only need one loop and is the most effective method we could find for doing the code.
def bestmove(grid, CURR_DEPTH, SET_OF_MOVES, currentscore):
CURR_DEPTH += 1
placeholder = [x[:] for x in grid]
if CURR_DEPTH != DEPTH:
for DIRECTION in POSSIBLE_MOVES:
grid = move(DIRECTION, grid, currentscore)[0]
SET_OF_MOVES.append(DIRECTION)
# print(f"Depth {CURR_DEPTH}")
# displayGrid(grid)
if grid != placeholder:
grid = updateGrid(grid, True)[0]
bestmove(grid, CURR_DEPTH, SET_OF_MOVES, currentscore)
SET_OF_MOVES.pop()
grid = [x[:] for x in placeholder]
return
else:
global BEST_SCORE
global BEST_DIRECTION
global BEST_GRID
SCORE = evalgrid(grid)
if BEST_SCORE < SCORE:
BEST_SCORE = SCORE
BEST_DIRECTION = SET_OF_MOVES[0]
BEST_GRID = grid
return
returnThe best move function is the key to this code and all it does it recursively iterate through the game tree until it reaches its desires depth and then evaluates the grid based on a heuristic we have chosen and if its score if greater than the current greatest score, then we update a variable that holds the best grid with the current grid and then we use this grid for the next iteration of best move.
Heuristic:
def evalgrid(grid):
return np.sum(np.array(grid) * TEMPLATE)TEMPLATE = [[0.135, 0.121, 0.102, 0.0999],
[0.0997, 0.088, 0.076, 0.0724],
[0.0606, 0.0562, 0.0371, 0.0161],
[0.0125, 0.0099, 0.0057, 0.0033]]
I would like to credit Randy Olson for the template we used as this template is the key for evaluating a good position. What it does is maximise the score for a distinct set of tiles by having the greatest tile in the corner while the other tiles are positioned in such a way that they are easy to combine. e.g. the second and third highest tile is the 2nd and 3rd tile on the top row and by doing so, this means it is very easy to combine 2 of the same tile since they will be adjacent to each other. Note that this is evalgrid will be maximised whenever all the tile ordered from largest to smallest are placed on the grid in positions going from largest to smallest.
And that is how we built our AI!
