2048-ml

git clone git://git.codymlewis.com/2048-ml.git
Log | Files | Refs | README | LICENSE

commit 952caa48219793cd3c4d9cbe50c62140dc723e8c
Author: Cody Lewis <cody@codymlewis.com>
Date:   Mon, 17 Feb 2020 21:19:20 +1100

Initial commit

Diffstat:
AAutoplay.py | 57+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ABoard.py | 214+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AEvolve.py | 82+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ANeuralNet.py | 49+++++++++++++++++++++++++++++++++++++++++++++++++
AREADME.md | 31+++++++++++++++++++++++++++++++
ATile.py | 25+++++++++++++++++++++++++
Agame.py | 27+++++++++++++++++++++++++++
Arequirements.txt | 3+++
8 files changed, 488 insertions(+), 0 deletions(-)

diff --git a/Autoplay.py b/Autoplay.py @@ -0,0 +1,57 @@ +import itertools +import numpy as np + +import Board + + +''' +Functions that play 2048 without user input +''' + + +def convert_and_play(moves): + '''Convert the list of moves and play the game with it''' + return np.mean([play(str().join(moves)) for _ in range(10)]) + + +def play(move_str, verbose=False): + '''Play the game by cycling the moves specified''' + board = Board.Board(4, 4) + movement = { + "u": board.up, + "d": board.down, + "l": board.left, + "r": board.right + } + counter = 0 + if verbose: + print(board) + for a in itertools.cycle(move_str): + if board.game_over() or counter == len(move_str): + break + if movement[a](): + board.spawn_tile() + counter = 0 + if verbose: + print() + print(board) + else: + counter += 1 + return board.get_score() + + +def model_play(model): + board = Board.Board(4, 4) + movement = { + "u": board.up, + "d": board.down, + "l": board.left, + "r": board.right + } + print(board) + while not board.game_over()and \ + movement[model.predict([board.get_game_state()])[0]](): + board.spawn_tile() + print(board) + print("Game over!") + print(f"The model scored {board.get_score()}!") diff --git a/Board.py b/Board.py @@ -0,0 +1,214 @@ +import math +import random + +import Tile + + +''' +Object for the 2048 Board +''' + + +class Board: + ''' + A 2048 board class + ''' + + def __init__(self, width, height): + self.__width = width + self.__height = height + self.__score = 0 + self.__tiles = [[None for _ in range(width)] for _ in range(height)] + self.__max_num_len = 1 + self.__available_tiles = [i for i in range(width * height)] + for _ in range(1 if random.randint(1, 100) < 95 else 2): + self.spawn_tile() + + def get_game_state(self): + '''Return a flattened list of the current game state''' + return [int(t) if t else 0 for r in self.__tiles for t in r] + + def get_score(self): + '''Get the current score of the game''' + return self.__score + + def spawn_tile(self): + '''Spawn a random new Tile on the board''' + coord = random.sample(self.__available_tiles, 1)[0] + i = coord % self.__width + j = math.floor(coord / self.__width) + self.__tiles[i][j] = Tile.Tile( + 2 if random.randint(1, 100) < 95 else 4, + self.__max_num_len + ) + self.take_space(i, j) + + def take_space(self, col, row): + '''Mark a space in the board as taken''' + self.__available_tiles.remove(row * self.__width + col) + + def give_space(self, col, row): + '''Unmark a space in the board as taken''' + self.__available_tiles.append(row * self.__width + col) + + def combine_tiles(self, i, j, k, l): + '''Combine 2 tiles on the board''' + self.__tiles[k][l] += self.__tiles[i][j] + self.__tiles[i][j] = None + self.give_space(i, j) + self.__score += int(self.__tiles[k][l]) + if self.__tiles[k][l].max_num_len > self.__max_num_len: + self.update_mnl(self.__tiles[k][l].max_num_len) + else: + self.__tiles[k][l].max_num_len = self.__max_num_len + + def update_mnl(self, new_len): + '''Update the maximum number length''' + self.__max_num_len = new_len + for i in range(self.__height): + for j in range(self.__width): + if self.__tiles[i][j]: + self.__tiles[i][j].max_num_len = new_len + + def move_tile(self, i, j, k, l): + '''Move a tile across the board''' + if i != k or j != l: + self.__tiles[k][l] = self.__tiles[i][j] + self.take_space(k, l) + self.__tiles[i][j] = None + self.give_space(i, j) + + def game_over(self): + '''Check when the game is over''' + return len(self.__available_tiles) == 0 and self.no_adjacents() + + def no_adjacents(self): + '''Check that there are no equal adjecent tiles''' + for i in range(self.__height): + for j in range(self.__width): + p = j < self.__width - 1 and self.__tiles[i][j + 1] == self.__tiles[i][j] + q = i < self.__height - 1 and self.__tiles[i + 1][j] == self.__tiles[i][j] + if p or q: + return False + return True + + def left(self): + '''Slide the tiles to the left''' + if not self.can_left(): + return False + for i in range(self.__height): + pivot = 0 + for j in range(1, self.__width): + if self.__tiles[i][j]: + if self.__tiles[i][j] == self.__tiles[i][pivot]: + self.combine_tiles(i, j, i, pivot) + else: + if self.__tiles[i][pivot]: + pivot += 1 + self.move_tile(i, j, i, pivot) + return True + + def can_left(self): + '''Check if anything can move left''' + for i in range(self.__height): + for j in range(1, self.__width): + p = self.__tiles[i][j] + q = not self.__tiles[i][j - 1] or \ + self.__tiles[i][j] == self.__tiles[i][j - 1] + if p and q: + return True + return False + + def right(self): + '''Slide the tiles to the right''' + if not self.can_right(): + return False + for i in range(self.__height - 1, -1, -1): + pivot = self.__width - 1 + for j in range(self.__width - 2, -1, -1): + if self.__tiles[i][j]: + if self.__tiles[i][j] == self.__tiles[i][pivot]: + self.combine_tiles(i, j, i, pivot) + else: + if self.__tiles[i][pivot]: + pivot -= 1 + self.move_tile(i, j, i, pivot) + return True + + def can_right(self): + '''Check if anything can move right''' + for i in range(self.__height - 1, -1, -1): + for j in range(self.__width - 2, -1, -1): + p = self.__tiles[i][j] + q = not self.__tiles[i][j + 1] or \ + self.__tiles[i][j] == self.__tiles[i][j + 1] + if p and q: + return True + return False + + def up(self): + '''Slide the tiles up''' + if not self.can_up(): + return False + for j in range(self.__width): + pivot = 0 + for i in range(1, self.__height): + if self.__tiles[i][j]: + if self.__tiles[i][j] == self.__tiles[pivot][j]: + self.combine_tiles(i, j, pivot, j) + else: + if self.__tiles[pivot][j]: + pivot += 1 + self.move_tile(i, j, pivot, j) + return True + + def can_up(self): + '''Check if anything can move up''' + for j in range(self.__width): + for i in range(1, self.__height): + p = self.__tiles[i][j] + q = not self.__tiles[i - 1][j] or \ + self.__tiles[i][j] == self.__tiles[i - 1][j] + if p and q: + return True + return False + + def down(self): + '''Slide the tiles down''' + if not self.can_down(): + return False + for j in range(self.__width - 1, -1, -1): + pivot = self.__width - 1 + for i in range(self.__height - 2, -1, -1): + if self.__tiles[i][j]: + if self.__tiles[i][j] == self.__tiles[pivot][j]: + self.combine_tiles(i, j, pivot, j) + else: + if self.__tiles[pivot][j]: + pivot -= 1 + self.move_tile(i, j, pivot, j) + return True + + def can_down(self): + '''Check if anything can move down''' + for j in range(self.__width - 1, -1, -1): + for i in range(self.__height - 2, -1, -1): + p = self.__tiles[i][j] + q = not self.__tiles[i + 1][j] or \ + self.__tiles[i][j] == self.__tiles[i + 1][j] + if p and q: + return True + return False + + def __str__(self): + result = f"Score: {self.__score}\n" + for i in range(self.__height): + result += ("_" if i == 0 else "=") * \ + (self.__width * (self.__max_num_len + 2)) + "\n" + for j in range(self.__width): + result += "|" + \ + (str(self.__tiles[i][j]) if self.__tiles[i][j] + else " " * self.__max_num_len) + "|" + result += "\n" + result += "-" * (self.__width * (self.__max_num_len + 2)) + "\n" + return result diff --git a/Evolve.py b/Evolve.py @@ -0,0 +1,82 @@ +#!/usr/bin/env python3 + +import random +import numpy as np +import sys + +import Autoplay + + +''' +Functions to perform evolutionary learning of 2048 +''' + + +BASES = ["u", "d", "l", "r"] + + +def pool_play(genomes): + '''Get the population of genomes to play the game''' + return [Autoplay.convert_and_play(g) for g in genomes] + + +def crossover(a, b): + '''Crossover two genomes''' + min_len = min(len(a), len(b)) + result = a[:min_len] + for i, gene in enumerate(b[:min_len]): + if random.randint(1, 100) <= 50: + result[i] = gene + return result + + +def mutate(genome): + '''Mutate a genome''' + for i, gene in enumerate(genome): + if random.randint(1, 100) < 30: + genome[i] = random.choice(BASES) + if random.randint(1, 100) < 25: + genome.extend(random.choices(BASES, k=random.randint(1, 5))) + return genome + + +def evolve(epochs, verbose=True): + '''Perform an evolutionary algorithm''' + population = [ + random.choices(BASES, k=random.randint(4, 20)) for _ in range(100) + ] + the_best = str() + for epoch in range(epochs): + fitnesses = pool_play(population) + med = np.median(fitnesses) + new_pop = [] + for i, fitness in enumerate(fitnesses): + if fitness >= med: + new_pop.append(population[i]) + for _ in range(50): + new_pop.append( + mutate( + crossover(random.choice(new_pop), random.choice(new_pop)) + ) + ) + max_index = np.argmax(fitnesses) + the_best = str().join(population[max_index]) + if verbose: + sys.stdout.write("\033[K") + print( + f"Epoch {epoch + 1}: " + + f"genome {the_best} " + + f"scored {fitnesses[max_index]}", + end="\r" + ) + population = new_pop + return the_best + + +if __name__ == "__main__": + NUM_EPOCHS = 100 + print("Evolving a strategy for 2048...") + RESULT = evolve(NUM_EPOCHS) + SCORE = Autoplay.play(RESULT, verbose=True) + print(f"The best strategy found was {RESULT}") + print(f"It scored {SCORE}") diff --git a/NeuralNet.py b/NeuralNet.py @@ -0,0 +1,49 @@ +#!/usr/bin/env python3 + +from sklearn import neural_network +import random +import sys + +import Autoplay +import Board + + +def learn(epochs, verbose=False): + model = neural_network.MLPClassifier() + board = Board.Board(4, 4) + classes = ["u", "d", "l", "r"] + model.partial_fit( + [board.get_game_state()], + ["u"], + classes=classes + ) + for epoch in range(epochs): + board = Board.Board(4, 4) + movement = { + "u": board.up, + "d": board.down, + "l": board.left, + "r": board.right + } + score = board.get_score() + while not board.game_over(): + prev_state = board.get_game_state() + prediction = model.predict([prev_state])[0] + while not movement[prediction](): + prediction = random.choice(classes) + if board.get_score() > score: + model.partial_fit([prev_state], [prediction]) + score = board.get_score() + board.spawn_tile() + sys.stdout.write("\033[K") + if verbose: + print(f"Epoch {epoch + 1}, score: {board.get_score()}", end="\r") + if verbose: + print() + return model + + +if __name__ == "__main__": + print("Learning to play 2048...") + MODEL = learn(10_000, verbose=True) + Autoplay.model_play(MODEL) diff --git a/README.md b/README.md @@ -0,0 +1,31 @@ +# 2048 ML + +Machine learning algorithms attempting to solve 2048 + +## Requirements + +- python3.8+ + +## Installation + +``` +pip install -r requirements.txt +``` + +## Running + +To play the game: +``` +./game.py +``` + +To run the evolutionary algorithm: +``` +./Evolve.py +``` + + +To run the neural network: +``` +./NeuralNet.py +``` diff --git a/Tile.py b/Tile.py @@ -0,0 +1,25 @@ +''' +Object for the 2048 tile +''' + + +class Tile: + ''' + 2048 Tile class + ''' + + def __init__(self, value, max_num_len=1): + self.__value = value + self.max_num_len = max(max_num_len, len(str(value))) + + def __add__(self, other): + return Tile(self.__value + int(other)) + + def __eq__(self, other): + return isinstance(other, Tile) and self.__value == int(other) + + def __str__(self): + return f"{self.__value:{self.max_num_len}d}" + + def __int__(self): + return self.__value diff --git a/game.py b/game.py @@ -0,0 +1,27 @@ +#!/usr/bin/env python3 + +from getkey import getkey, keys + +import Board + +if __name__ == "__main__": + board = Board.Board(4, 4) + movement = { + keys.UP: board.up, + keys.DOWN: board.down, + keys.LEFT: board.left, + keys.RIGHT: board.right + } + print(board) + while not board.game_over(): + print("Your move: ") + key = getkey() + moved = False + if key in movement.keys(): + moved = movement[key]() + if moved: + board.spawn_tile() + print() + print(board) + print("Game over!") + print(f"Final score: {board.get_score()}") diff --git a/requirements.txt b/requirements.txt @@ -0,0 +1,3 @@ +numpy +scikit-learn +getkey