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?
