8
\$\begingroup\$

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

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(**{
        trait.name: (choice([mum.traits[trait], dad.traits[trait]])
                     + (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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.