Введение:
Это был проект группы людей, в которую входили я и человек по имени Эдвин. В то время как я отвечал за код наивысшего балла, Эдвин отвечал за код Монте-Карло, и, поскольку они оба различны, я полагал, что они оба заслуживают отдельной статьи. У обоих есть свои преимущества и недостатки, и при применении реального ИИ метод Монте-Карло был бы единственным жизнеспособным вариантом, потому что наивысший результат имеет обманный характер, поскольку он может выбрать лучшую доску из вариантов многих досок. Тем не менее, по-прежнему очень приятно видеть, как код получает выигрышную доску (2048 плиток) менее чем за секунду, используя код.
Чтобы увидеть результаты кодов, я прилагаю график результатов кода, чтобы вы могли сами оценить его производительность. Обратите внимание: наша система подсчета очков немного отличается от реальной системы подсчета очков 2048 года, где счет определяется суммой всех плиток на сетке.
Если вы бежите на очень большие ГЛУБИНЫ, например. глубина 10, я запускал его в течение 2 часов, и он набрал максимальное количество очков в 65 536 плиток! Вы можете увидеть окончательную сетку глубины 8 справа от сетки на терминале pycharm.
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()
Обман:
Мы с Эдвином поспорили о присущей этому коду обманчивости из-за того, как он работает. Здесь я использую рекурсию, я строю игровое дерево возможностей будущих сеток.
Это пример дерева игры, и мой код генерирует дерево игры определенной глубины, которую мы указываем, а затем из сгенерированных результирующих сеток я выбираю сетку с наибольшей оценкой, что означает ее наибольшую оптимальная сетка. Мы делаем это с помощью эвристической функции, которая представляет собой комбинацию суммы всех чисел в сетке, а также матрицы, которую мы скопировали у кого-то в Интернете, который создал ИИ, намного превосходящий наш собственный.
Большая часть кода создана для того, чтобы заставить работать функциональную игру 2048 года, и прямо сейчас все это печатается на терминале, но мы надеемся, что через некоторое время мы сможем визуализировать его, чтобы он выглядел более эстетично. Мы должны были сделать наши функции перемещения максимально эффективными, потому что без этого мы бы тратили много времени на вычисления, пока код генерирует следующую сетку, и поэтому мы создали функцию перемещения следующим образом:
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
Что это эффективно делает, он выполняет итерацию по массиву, и всякий раз, когда он встречает 0, он извлекает его и вставляет в конец списка. В обратном направлении мы можем перевернуть список, переместив нули, а затем снова перевернув список, и это даст тот же эффект. Это означает, что нам нужен только один цикл, и это самый эффективный метод, который мы могли бы найти для выполнения кода.
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 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]]
Я хотел бы поблагодарить Рэнди Олсона за шаблон, который мы использовали, поскольку этот шаблон является ключом к оценке хорошей позиции. Что он делает, так это максимизирует счет для отдельного набора плиток, располагая самую большую плитку в углу, в то время как другие плитки расположены таким образом, чтобы их было легко комбинировать. например вторая и третья по высоте плитка - это 2-я и 3-я плитка в верхнем ряду, и, таким образом, это означает, что очень легко объединить 2 одинаковых плитки, поскольку они будут смежными друг с другом. Обратите внимание, что это evagrid будет максимизироваться всякий раз, когда все плитки, упорядоченные от наибольшего к наименьшему, будут размещены в сетке в позициях, идущих от наибольшего к наименьшему.
Именно так мы построили наш ИИ!
