Readme.md

Tetris

In my quest to building a Tetris game, where you can challenge an AI, I have created and trained an AI that plays Tetris all by himself. Github link I think the easiest way to run it, is by cloning the Git and running tkinter_tetris_ai.py from the Tetris2.0/AI/ folder. See my 1 Player Tetris Question for it's mostly similar in the the Game Logic.

How it works

We have 7 characteristic values(genes):

• rows_complete
• weighted_height
• cumulative_heights
• relative_height
• holes
• roughness
• fitness

For each piece, we choose the best position (rotation and offset) by scoring the genes + the next piece's max score against the current choice.

For each 10th (or based on population_size value in AIPlayer) update, AI will evolve.

How evolve works

We keep the first half, best performance(judged by the game score it geted) genes. We generate another half (of population size) genes by these first half genes. Child gene get random characteristic from parents and with mutation possible.

Rules:

• This tetris board has a dimension of 14 * 25
• We measure the algorithm or performance of gene by the score it gets in the game
• If "game over", there will be minus extra score
• Cleaning multiple lines at once, will give extra score

Attempted Learning Enhancements

To improve the learning, we tried to train it by "holes" in the pieces and learn it the last rule - "Clean multiple lines at once, will get extra score". The piece limit was lowered, to 1000 pieces.

In this training way, the AI learned much faster. We can compare the data start from the 1000th game, it seems to abide the clean rule much better, it can clean "2 lines" at once or even "3 lines", and there are fewer holes. The weight of "weighted_height" becomes larger, that means, AI prefers to put pieces on a single column, and the peeks get much higher.

From the 250th train to 300th train, the score never changed, it seems get a "max_score", which is still not good enough from the board result

Code

tkinter_tetris_ai.py

#!/usr/bin/python3 from tkinter import Canvas, Label, Tk, StringVar, Button, LEFT from genetic_game import GeneticGame from time import sleep class Tetris(): def __init__(self): model_path = "model/genetic" self.game = GeneticGame(model_path) self.box_size = 20 self.game_width = self.game.board.max_width * self.box_size self.game_height = self.game.board.max_height * self.box_size self.root = Tk() self.root.geometry("500x550") self.root.title('Tetris') self._game_canvas() self._score_label() self._next_piece_canvas() def start_ai(self): while 1: completed_lines = self.game.play() self.render_game_canvas() self.render_score_label() self.render_next_piece() if completed_lines < 0: break sleep(0.5) self.root.mainloop() def render_game_canvas(self): self.canvas.delete("all") width = self.game.board.max_width height = self.game.board.max_height coords = [(j, i) for j in range(width) for i in range(height) if self.game.board.board[i][j] == 1] self._create_boxes(self.canvas, coords, (0,0)) def render_score_label(self): self.status_var.set(f"Score: {self.game.score}") self.status.update() def render_next_piece(self): self.next_canvas.delete("all") width = self.game.next_piece.width height = self.game.next_piece.height coords = [(j, i) for j in range(width) for i in range(height) if self.game.next_piece.piece[i][j] == 1] self._create_boxes(self.next_canvas, coords, (20,20)) def _create_boxes(self, canvas, coords, start_point): off_x, off_y = start_point for coord in coords: x, y = coord canvas.create_rectangle(x * self.box_size + off_x, y * self.box_size + off_y, (x + 1) * self.box_size + off_x, (y + 1) * self.box_size + off_y, fill="blue") def _game_canvas(self): self.canvas = Canvas(self.root, width = self.game_width, height = self.game_height) self.canvas.pack(padx=5 , pady=10, side=LEFT) def _score_label(self): self.status_var = StringVar() self.status = Label(self.root, textvariable=self.status_var, font=("Helvetica", 10, "bold")) self.status.pack() def _next_piece_canvas(self): self.next_canvas = Canvas(self.root, width = 100, height = 100) self.next_canvas.pack(padx=5 , pady=10) if __name__ == "__main__": tetris = Tetris() tetris.start_ai() 

genetic_game.py

from genetic import GeneticAI import matplotlib.pyplot as plt from tetris_game import Piece, Board class GeneticGame: def __init__(self, model_path = "model/genetic"): self.board = Board() self.score = 0 self.next_piece = Piece() self.ai_player = GeneticAI(model_path) def play(self): self.current_piece = Piece(self.next_piece.piece) self.next_piece = Piece() self.ai_player.current_board = self.board.board self.ai_player.current_shape = self.current_piece.piece self.ai_player.next_shape = self.next_piece.piece next_move = self.ai_player.next_move() rotate = next_move['rotate'] offx = next_move['offx'] self.current_piece.rotate(times = rotate) game_over = self.board.place_piece(self.current_piece, offx) if game_over: return -1 else: completed_lines = self.board.clean_line() self.score += self.get_scores(completed_lines) return completed_lines def havefun(self): while 1: completed_lines = self.play() print(self.board) print(self.score) if completed_lines < 0: return def get_scores(self, completed_lines): if completed_lines == 0: return 1 elif completed_lines == 1: return 400 elif completed_lines == 2: return 4000 elif completed_lines == 3: return 40000 elif completed_lines == 4: return 400000 if __name__ == "__main__": game = GeneticGame() game.havefun() 

genetic.py

from random import uniform, choice from math import floor, pow import pickle import os class Gene(): def __init__(self, rows_complete = uniform(-0.5, 0.5), weighted_height = uniform(-0.5, 0.5), cumulative_heights = uniform(-0.5, 0.5), relative_height = uniform(-0.5, 0.5), holes = uniform(0, 0.5), roughness = uniform(-0.5, 0.5), fitness = -1): self.rows_complete = rows_complete self.weighted_height = weighted_height self.cumulative_heights = cumulative_heights self.relative_height = relative_height self.holes = holes self.roughness = roughness self.fitness = fitness class GeneticAI(): def __init__(self, model_path): self.mutation_rate = 0.2 self.mutation_step = 0.2 self.archive = [] self.genes = [] self.population_size = 10 self.current_gene = -1 self.current_board = None self.current_shape = None self.next_shape = None self.model_path = model_path self.initial_population() def initial_population(self): self.read_dataset() self.evaluate_next_gene() def evaluate_next_gene(self): self.current_gene += 1 if self.current_gene == len(self.genes): self.evolve() def update(self, fail, score): if fail: score -= 5000 self.genes[self.current_gene].fitness = score self.evaluate_next_gene() def evolve(self): self.current_gene = 0 self.genes = sorted(self.genes, key = lambda x: -x.fitness) self.archive += [self.genes[0].fitness] while len(self.genes) > self.population_size // 2: self.genes.pop() total_fitness = sum(gen.fitness for gen in self.genes) def random_gene(): return self.genes[self.random_weighted_number(0, len(self.genes) - 1)] children = [self.genes[0]] while len(children) < self.population_size: children += [self.make_child(random_gene(), random_gene())] self.genes = children def make_child(self, mum, dad): child = Gene( rows_complete = choice([mum.rows_complete, dad.rows_complete]), weighted_height = choice([mum.weighted_height, dad.weighted_height]), cumulative_heights = choice([mum.cumulative_heights, dad.cumulative_heights]), relative_height = choice([mum.relative_height, dad.relative_height]), holes = choice([mum.holes, dad.holes]), roughness = choice([mum.roughness, dad.roughness]) ) if uniform(0, 1) < self.mutation_rate: child.rows_complete += uniform(0, 1) * self.mutation_step * 2 - self.mutation_step if uniform(0, 1) < self.mutation_rate: child.weighted_height += uniform(0, 1) * self.mutation_step * 2 - self.mutation_step if uniform(0, 1) < self.mutation_rate: child.cumulative_heights += uniform(0, 1) * self.mutation_step * 2 - self.mutation_step if uniform(0, 1) < self.mutation_rate: child.relative_height += uniform(0, 1) * self.mutation_step * 2 - self.mutation_step if uniform(0, 1) < self.mutation_rate: child.holes += uniform(0, 1) * self.mutation_step * 2 - self.mutation_step if uniform(0, 1) < self.mutation_rate: child.roughness += uniform(0, 1) * self.mutation_step * 2 - self.mutation_step return child def next_move(self, gene_idx = -1): if gene_idx == -1: gene_idx = self.current_gene current_possible_moves = self.all_possible_move(self.current_board, self.current_shape, gene_idx) for move in current_possible_moves: rotation = move['rotate'] shape = self.current_shape for _ in range(rotation): shape = self.rotate(shape) offx = move['offx'] level = self.drop(self.current_board, shape, (offx, 0)) board = self.place_shape(self.current_board, shape, (level,offx)) move['rating'] += max(self.all_possible_move(board, self.next_shape, gene_idx), key = lambda x:x['rating'])['rating'] best_choice = max(current_possible_moves, key=lambda x: x['rating']) return best_choice def all_possible_move(self, board, shape, gene_idx): possible_moves = [] for rotation in range(4): for offx in range(len(board[0]) - len(shape[0]) + 1): level = self.drop(board, shape, (offx, 0)) status = self.board_status(self.place_shape(board, shape, (level, offx))) rate = status['rows_complete'] * self.genes[gene_idx].rows_complete +\ status['weighted_height'] * self.genes[gene_idx].weighted_height +\ status['cumulative_heights'] * self.genes[gene_idx].cumulative_heights +\ status['relative_height'] * self.genes[gene_idx].relative_height +\ status['holes'] * self.genes[gene_idx].holes +\ status['roughness'] * self.genes[gene_idx].roughness possible_moves += [{'rotate':rotation, 'offx':offx, 'rating':rate, 'status':status}] shape = self.rotate(shape) return possible_moves def drop(self, board, shape, offset): off_x, off_y = offset last_level = len(board) - len(shape) + 1 for level in range(off_y, last_level): for i in range(len(shape)): for j in range(len(shape[0])): if board[level+i][off_x+j] == 1 and shape[i][j] == 1: return level - 1 return last_level - 1 def place_shape(self, board, shape, pos): board_ = [row[:] for row in board] level, offx = pos for i in range(len(shape)): for j in range(len(shape[0])): if shape[i][j] == 1: board_[level+i][offx+j] = shape[i][j] return board_ def rotate(self, shape): return [row[::-1] for row in zip(*shape)] def board_status(self, board): status = {'rows_complete' : 0, 'weighted_height':0, 'cumulative_heights':0, 'relative_height':0, 'holes':0, 'roughness':0 } def get_completed_line(): complete_line = 0 for i, line in enumerate(board): if line.count(0) == 0: del board[i] board.insert(0, [0 for _ in range(len(board[0]))]) complete_line += 1 return complete_line def get_holes_and_peaks(): rotate_board = [row for row in zip(*board)] holes = 0 peaks = [0 for _ in range(len(rotate_board))] for idx, row in enumerate(rotate_board): if row.count(1) > 0: holes += len(row) - row.index(1) - sum(row) peaks[idx] = len(row) - row.index(1) return holes, peaks status['rows_complete'] = get_completed_line() holes, peaks = get_holes_and_peaks() status['holes'] = holes status['weighted_height'] = pow(max(peaks), 1.5) status['cumulative_heights'] = sum(peaks) status['relative_height'] = max(peaks) - min(peaks) status['roughness'] = sum(abs(peaks[i] - peaks[i+1]) for i in range(len(peaks) - 1)) return status def random_weighted_number(self, min_, max_): return floor(pow(uniform(0,1), 2) * (max_ - min_ + 1) + min_) def save_dataset(self): with open(self.model_path, 'wb+') as f: pickle.dump((self.genes, self.archive, self.current_gene), f, -1) def read_dataset(self): if not os.path.isfile(self.model_path): self.genes = [Gene() for _ in range(self.population_size)] else: with open(self.model_path, 'rb') as f: self.genes, self.archive, self.current_gene = pickle.load(f) 

tetris_game.py

from random import choice, randint class Piece(): PIECES = [[(0,1,1),(1,1,0)], [(1,1,0),(0,1,1)], [(1,0,0),(1,1,1)], [(0,0,1),(1,1,1)], [(0,1,0),(1,1,1)], [(1,1),(1,1)], [(1,1,1,1)]] def __init__(self, piece = None): if not piece: self.piece = choice(Piece.PIECES) rotate_time = randint(0,3) self.rotate(times = rotate_time) else: self.piece = piece @property def width(self): return len(self.piece[0]) @property def height(self): return len(self.piece) def rotate(self, times=1): for i in range(times % 4): self.piece = [row[::-1] for row in zip(*self.piece)] def __str__(self): return '\n'.join(''.join(map(str,line)) for line in self.piece) class Board(): def __init__(self, width = 14, height = 25): self.max_height = height self.max_width = width self.board = [[0]*width for _ in range(height)] def restart(self): self.board = [[0]*self.max_width for _ in range(self.max_height)] def clean_line(self): completed_lines = 0 for i, line in enumerate(self.board): if line.count(0) == 0: completed_lines += 1 del self.board[i] self.board.insert(0, [0 for _ in range(self.max_width)]) return completed_lines def _drop(self, piece, offset): last_level = self.max_height - piece.height + 1 for level in range(last_level): for i in range(piece.height): for j in range(piece.width): if self.board[level+i][offset+j] == 1 and piece.piece[i][j] == 1: return level - 1 return last_level - 1 @property def state(self): return ''.join(str(self.board[i][j]) for j in range(self.max_width) for i in range(self.max_height)) def place_piece(self, piece, offset): level = self._drop(piece, offset) if level < 0: return True for i in range(piece.height): for j in range(piece.width): if piece.piece[i][j] == 1: self.board[level+i][offset+j] = piece.piece[i][j] return False def __str__(self): return '-' * self.max_width + '\n' + \ '\n'.join(''.join(map(str,line)) for line in self.board) + '\n' + \ '-' * self.max_width 

How to train

You can train your own model by running the genetic_train.py

from genetic import GeneticAI import matplotlib.pyplot as plt from tetris_game import Piece, Board class TetrisTrain: def __init__(self): self.MAX_PIECE = 1000 self.pieces = [Piece() for _ in range(self.MAX_PIECE+1)] self.start() def start(self): self.board = Board() self.current_piece_index = 0 self.score = 0 self.piece_placed = 0 self.current_piece = None self.next_piece = self.pieces[self.current_piece_index] def train_genetic(self, model_path = "model/genetic"): self.ai_player = GeneticAI(model_path) train_times = 0 while 1: completed_lines = self.play(False) if completed_lines < 0: train_times += 1 print("Score:{}\nTrain {} time".format(self.score, train_times)) self.ai_player.update(True, self.score) self.ai_player.save_dataset() if train_times > 0 and train_times % 50 == 0: self.present(self.ai_player.archive) self.start() def train_genetic_with_limit(self, model_path = "model/genetic_limit"): self.ai_player = GeneticAI(model_path) train_times = 0 while 1: train_times += 1 game_over = False max_clean = 0 while self.piece_placed < self.MAX_PIECE: self.piece_placed += 1 self.current_piece_index += 1 completed_lines = self.play() print(self.board) print("{}/{}\nScore:{}\nTrain {} time".format(self.piece_placed, self.MAX_PIECE, self.score, train_times)) if completed_lines < 0: game_over = True break elif completed_lines > max_clean: max_clean = completed_lines #self.MAX_PIECE += 100 self.ai_player.save_dataset() self.ai_player.update(game_over, self.score) # if train_times > 0 and train_times % 50 == 0: # self.present(self.ai_player.archive) self.start() def play(self, next_piece_fixed = True): self.current_piece = Piece(self.next_piece.piece) if next_piece_fixed: self.next_piece = self.pieces[self.current_piece_index % len(self.pieces)] else: self.next_piece = Piece() self.ai_player.current_board = self.board.board self.ai_player.current_shape = self.current_piece.piece self.ai_player.next_shape = self.next_piece.piece next_move = self.ai_player.next_move() rotate = next_move['rotate'] offx = next_move['offx'] self.current_piece.rotate(times = rotate) game_over = self.board.place_piece(self.current_piece, offx) if game_over: return -1 else: completed_lines = self.board.clean_line() self.score += self.get_scores(completed_lines) return completed_lines def test(self): self.start() while 1: completed_lines = self.play(False) print(self.board) print("Score:{}".format(self.score)) if completed_lines < 0: break def present(self, archive): plt.plot(archive) plt.ylabel('scores') plt.show() def get_scores(self, completed_lines): if completed_lines == 0: return 1 elif completed_lines == 1: return 400 elif completed_lines == 2: return 4000 elif completed_lines == 3: return 40000 elif completed_lines == 4: return 400000 if __name__ == "__main__": tetris = TetrisTrain() tetris.train_genetic() 

Questions

• How can I improve the algorithm even further?
• Is my code ok? Can you see any obvious mistakes?