# Genetic algorithm for playing Tetris

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)

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)

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.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

child = Gene(
)
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)

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:


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?
• Nice code, but where is the question? – FreezePhoenix May 3 '18 at 14:39
• @Phoe Any useful observation about the code is welcome. Do you see any mistakes, or ways to improve the AI? – Ludisposed May 3 '18 at 15:26

The thing that strikes me immediately is the amount of repetition in genetic.py. Suppose that you needed to add a new trait. How many places in the code would have to be updated? Well, you'd need to add:

1. A keyword argument to Gene.__init__:

roughness = uniform(-0.5, 0.5),

2. An attribute assignment in Gene.__init__:

self.roughness          = roughness

3. A keyword parameter in the call to Gene in GeneticAI.make_child:

roughness = choice([mum.roughness, dad.roughness])

4. A mutation step in GeneticAI.make_child:

if uniform(0, 1) < self.mutation_rate:
child.roughness += uniform(0, 1) *  self.mutation_step * 2 - self.mutation_step

5. A rating element in GeneticAI.all_possible_move:

status['roughness'] * self.genes[gene_idx].roughness

6. An initializer in GeneticAI.board_status:

'roughness':0

7. A score computation in GeneticAI.board_status:

status['roughness'] = sum(abs(peaks[i] - peaks[i+1]) for i in range(len(peaks) - 1))


The Don't Repeat Yourself (DRY) principle says that "Every piece of knowledge must have a single, unambiguous, authoritative representation within a system". Applying the principle here means that each trait must have a single representation within the code.

Additionally, points 1 to 6 in the list above are completely boilerplate: the additional code is identical for each trait, and so is exactly the kind of boring detail that we'd prefer to delegate to the computer.

So how should we represent a trait? Well, a trait seems to have four attributes:

1. A name, for example "holes".

2. A minimum initial value, for example 0.

3. A maximum initial value, for example 0.5.

4. Some code in GeneticAI.board_status that calculates the trait's contribution to the score for the board based on the number of completed lines, the number of holes, and the heights of the peaks.

One way to represent a trait would be as an object belonging to a class, like this:

class Trait:
"""A trait under genetic control. Has attributes:

name: str -- name of the trait
initial_min: float -- minimum initial value
initial_max: float -- maximum initial value
score -- function taking (lines, holes, peaks) and returning the
trait's contribution to board score

"""
def __init__(self, name, initial_min, initial_max, score):
self.name = name
self.initial_min = initial_min
self.initial_max = initial_max
self.score = score

@property
def initial(self):
"Return uniformly distributed initial value for the trait."
return uniform(self.initial_min, self.initial_max)


Then you can construct a global list of traits:

TRAITS = [
Trait('lines', -.5, .5, lambda lines, _, _: lines),
Trait('holes', 0, .5, lambda _, holes, _: holes),
Trait('weighted', -.5, .5, lambda _, _, peaks: max(peaks) ** 1.5),
Trait('cumulative', -.5, .5, lambda _, _, peaks: sum(peaks)),
Trait('relative', -.5, .5, lambda _, _, peaks: max(peaks) - min(peaks)),
Trait('roughness', -.5, .5, lambda _, _, peaks:
sum(abs(peaks[i] - peaks[i+1]) for i in range(len(peaks) - 1))),
]


(Note that passing the three arguments lines, holes, and peaks is not necessarily the best way to pass the board information to the trait score functions. I think that it would be better to pass the board and let the trait functions compute the information they need about the board. But this would require some adjustments elsewhere, in particular get_completed_line is destructive so can only be called once per turn. To keep this answer clear I'm looking only at the traits.)

Now that you have a global list of traits, the rest of the code just needs to iterate over the traits and do something appropriate. For example, in Gene.__init__ you'd construct a dictionary mapping the trait to its initial value:

def __init__(self, fitness=-1, **kwargs):
self.fitness = fitness
self.traits = {
trait: kwargs.pop(trait.name, trait.initial)
for trait in TRAITS
}
if kwargs:
raise TypeError("{} got an unexpected keyword argument {!r}",
self.__qualname__, next(iter(kwargs)))


Then in GeneticAI.make_child you can iterate over the traits and construct the child gene:

def make_child(self, mum, dad):
return Gene(**{
+ (uniform(-1, 1) * self.mutation_step
* (uniform(0, 1) < self.mutation_rate)))
for trait in TRAITS
})


Note the simplification in the mutation code. The original code has

uniform(0, 1) *  self.mutation_step * 2 - self.mutation_step


but this can be simplified, first by extracting the common multiplication by self.mutation_step:

(uniform(0, 1) * 2 - 1) * self.mutation_step


and then by changing the bounds of the random number generation.

There are three more places which will have to be changed to use the new data structures, but I will leave those for you to complete.

The effect of this change is that there is no duplicated code manipulating the traits, and if you want to add a new trait, then you only have a single place to update, namely the definition of TRAITS.