Custom tetris block placement algorithm

Question

Well it's not entirely a generic problem, but that's why we're here after all.

A bit of background

My task is to create a tetris like simulation with an AI playing it. The lines do not disappear when they are completed. The end result should be a matrix filled with the neatly placed blocks, with very few or no gaps.

What I chose to do, was a genetic approach, with constant weights and methods for evaluation. The AI would try to place the blocks in all possible places, rotations, evaluate the temporary matrices, and go with the best one.

The problem

In tetris, you can move to the left or right even when the block is on the ground. This allows to solve many positions that would otherwise be impossible. The real problem however, that these holes can even occur mid-air, something like this:

falling J shape, with optimal choice occurring mid-air

The only solution I see here, would be trying all positions, rotations, and all possible combinations of mid-air moves, which I assume is "not an optimal solution" to say it formally.

My question

Is if someone has an idea or another approach, to find these possibilities for placement with realistic amounts of computing power

Answer 1

A single piece can be positioned in a maximum of 10x20x4 = 800 positions on a single board. These will be the nodes of your graph. Where you can move from one node to another in a single move, there is an edge. You can then prune nodes that are illegal (e.g. overlap with existing obstacles on the board). You can also mark nodes as "final" - there, the tile has an obstacle directly under at least one part of it (but they can still have nodes connected to them).

You can then check which final nodes are reachable from the initial node, which is a standard problem.

You could optimize this further by ignoring nodes where the piece is above the current height of the board.

Example code:

import copy
import time
from os import system, name
from random import randint
from wrapt import synchronized
from asciimatics.screen import Screen
import asciimatics
from asciimatics.effects import Cycle, Stars
from asciimatics.renderers import FigletText
from asciimatics.scene import Scene
from asciimatics.screen import Screen

class Tile:
  shapes = \
  [
    [
     [0, 0, 2],
     [2, 2, 2]
    ],
    [
     [3, 3, 0],
     [0, 3, 3]
    ],
    [
     [0, 4, 4],
     [4, 4, 0]
    ],
    [
     [5, 0, 0],
     [5, 5, 5]
    ],
    [
     [6, 6],
     [6, 6]
    ],
    [
     [0, 0, 0, 0],
     [7, 7, 7, 7],
     [0, 0, 0, 0]
    ],
    [
     [0, 8, 0],
     [8, 8, 8]
    ]
  ]

  def __init__(self, id=-1):
    if id >= 0:
        self.id = id
    else:
        self.id = randint(0, len(self.shapes)-1)
    self.shape = self.shapes[id]

  x = 8
  y = 0

  id = 0

  def rotate(self):
    self.shape = list(zip(*self.shape[::-1]))

class Model:
  _height = 25
  _width = 20

  _score = 0

  def __init__(self):
    self._view = None
    self._field = [[0] * self._width for i in range(self._height)]
    for i in range(5):
      for j in range(self._height):
        self._field[j][i] = 1
        self._field[j][-i-1] = 1

    for i in range(5):
      for j in range(self._width):
        self._field[-i-1][j] = 1

    self._tile = Tile()
    self._nexttile = Tile()

  def set_view(self, view):
    self._view = view

  def get_height(self):
    i = 0
    for r in self._field[:-5]:
      full_line = True
      if sum(r[5:-5]) > 0:
        return i
      i += 1
    return i

  def _merge(self, field, tile):
    field_copy = copy.deepcopy(field)
    for i in range(len(tile.shape)):
      for j in range(len(tile.shape[0])):
        field_copy[tile.y + i][tile.x + j] += tile.shape[i][j]
    return field_copy

  @synchronized
  def _is_valid(self, field, tile):
    for i in range(len(tile.shape)):
      for j in range(len(tile.shape[0])):
        if tile.shape[i][j] > 0:
          if (field[tile.y + i][tile.x + j] > 0):
            return False
    return True

  def get_board(self):
    return self._merge(self._field, self._tile)

  def rotate(self):
    self._tile.rotate()
    if not self._is_valid(self._field, self._tile):
      self._tile.rotate()
      self._tile.rotate()
      self._tile.rotate()
    if self._view is not None:
      self._view.show()

  def _which_lines_completed(self):
    lines = []
    i = 0
    for r in self._field[:-5]:
      full_line = True
      for c in r:
        if c == 0:
          full_line = False
      if full_line:
        lines.append(i)
      i += 1
    return lines

  def _remove_lines(self, lines):
    for l in lines:
      for i in list(range(1, l+1))[::-1]:
        self._field[i] = self._field[i-1].copy()
    if len(lines) == 4: 
      self._score += 5000
    elif len(lines) == 3:
      self._score += 1000
    elif len(lines) == 2:
      self._score += 500
    elif len(lines) == 1:
      self._score += 100  

  @synchronized
  def move_down(self):
    self._tile.y += 1
    if not self._is_valid(self._field, self._tile):
      self._tile.y -= 1
      self._field = self._merge(self._field, self._tile)
      self._tile = self._nexttile
      self._nexttile = Tile()

      # Check if any lines need to be removed
      lines = self._which_lines_completed()
      # If lines need to be removed, notify the view
      if len(lines) > 0:
        self._view.remove_lines(lines)
        # Remove the lines
        self._remove_lines(lines)
    if self._view is not None:
      self._view.show()

  @synchronized
  def move_left(self):
    self._tile.x -= 1
    if not self._is_valid(self._field, self._tile):
      self._tile.x += 1
    else:
      if self._view is not None:
        self._view.show()

  @synchronized
  def move_right(self):
    self._tile.x += 1
    if not self._is_valid(self._field, self._tile):
      self._tile.x -= 1
    if self._view is not None:
        self._view.show()

class AsciimaticView:
  def __init__(self, model):
    self.screen = Screen.open()
    self.model = model

  def _show_board(self, board):
    #self.screen.clear()
    b = board
    x = 0
    y = 0
    for r in b[:-4]:
      x = 0
      for c in r[4:-4]:
        if c == 1:
          self.screen.print_at(u'██', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
        elif c == 2:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
        elif c == 3:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
        elif c == 4:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
        elif c == 5:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
        elif c == 6:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_CYAN, Screen.A_BOLD)
        elif c == 7:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_YELLOW, Screen.A_BOLD)
        elif c == 8:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_MAGENTA, Screen.A_BOLD)  
        else:
          self.screen.print_at(u'  ', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
        x += 2
      y += 1

    self.screen.print_at(u'                             ', 0, y, Screen.COLOUR_RED, Screen.A_BOLD)
    self.screen.print_at(u'                             ', 0, y+1, Screen.COLOUR_RED, Screen.A_BOLD)
    self.screen.print_at(u'                             ', 0, y+2, Screen.COLOUR_RED, Screen.A_BOLD)
    self.screen.print_at(u'                             ', 0, y+3, Screen.COLOUR_RED, Screen.A_BOLD)
    for i in range(len(self.model._nexttile.shape)):
      x = 0
      if (i == 1):
        self.screen.print_at(u'Next: ', x, y, Screen.COLOUR_WHITE, Screen.A_BOLD)
      x = x + 6
      for j in range(len(self.model._nexttile.shape[0])):
        c = self.model._nexttile.shape[i][j]
        if c == 1:
          self.screen.print_at(u'██', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
        elif c == 2:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
        elif c == 3:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
        elif c == 4:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
        elif c == 5:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
        elif c == 6:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_CYAN, Screen.A_BOLD)
        elif c == 7:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_YELLOW, Screen.A_BOLD)
        elif c == 8:
          self.screen.print_at(u'[]', x, y, Screen.COLOUR_MAGENTA, Screen.A_BOLD)  
        else:
          self.screen.print_at(u'  ', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
        x = x + 2
      y = y + 1
    x = 0
    y = 24
    self.screen.print_at(u'Score: ' + str(self.model._score), x, y, Screen.COLOUR_WHITE, Screen.A_BOLD)
    self.screen.refresh()

  def show(self):
    self._show_board(self.model.get_board())

  def remove_lines(self, lines):
    b = self.model.get_board()
    for i in range(5):
      for l in lines:
        b[l][5:-5] = [1-el for el in b[l][5:-5]]
      self._show_board(b)
      time.sleep(0.1)

class Node:
  x = 0
  y = 0
  rot = 0
  final = False
  edges = []

  def __eq__(self, other):
    """Overrides the default implementation"""
    if isinstance(other, Node):
      return (self.x == other.x) and (self.y == other.y) and (self.rot == other.rot)
    return False

  def is_neighbour(self, other):
    if (abs(self.x - other.x) + abs(self.y - other.y) + abs(self.rot - other.rot) == 1) and (other.y >= self.y):
      return True
    return False

  def __hash__(self):
    return hash((self.x, self.y, self.rot))

def get_possible_moves(model, tile):
  start_node = Node()
  start_node.x = model._tile.x
  start_node.y = model.get_height() - len(tile.shape)-1

  frontier = [start_node]
  visited = {start_node: True}
  final_nodes = []
  while len(frontier) > 0:
    n = frontier.pop()
    for dx, dy, rot in [(-1, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)][::-1]:
      nn = Node()
      nn.x = n.x + dx
      nn.y = n.y + dy
      nn.rot = (n.rot + rot) % 4
      if nn not in visited:
        visited[nn] = True
        t = Tile(tile.id)
        t.x = nn.x
        t.y = nn.y
        for r in range(nn.rot):
          t.rotate()
        if model._is_valid(model._field, t):
          frontier.append(nn)
          # check if node is final
          for i in range(len(t.shape)):
            for j in range(len(t.shape[0])):
              if (t.shape[i][j] > 0) and (model._field[nn.y + i + 1][nn.x + j] > 0):
                nn.final = True
                final_nodes.append(nn)
                break
            if (nn.final):
              break

  print(len(visited))
  print(len(final_nodes))
  return final_nodes

m = Model()
m._field = [
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 0, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]

m._tile = Tile(3)

import threading
import keyboard

# define a thread which takes input
class InputThread(threading.Thread):
  def run(self):
    #self.daemon = True
    self.last_user_input = None
    while True:
        try:
          if keyboard.is_pressed('left'):#if key 'q' is pressed
            self.last_user_input = 'a'
            m.move_left()
          elif keyboard.is_pressed('right'):#if key 'q' is pressed
            self.last_user_input = 'a'
            m.move_right()
          elif keyboard.is_pressed('z'):
            print('z')
            self.last_user_input = 'z'
            m.rotate()
          elif keyboard.is_pressed('down'):
            m.move_down()
          elif keyboard.is_pressed('q'):
            break
          else:
            pass
          # do something based on the user input here
          # alternatively, let main do something with
          # self.last_user_input
        except:
          pass
        time.sleep(0.1)

# main
#it = InputThread()
#it.start()

fn = get_possible_moves(m, m._tile)
time.sleep(2)
v = AsciimaticView(m)
m.set_view(v)
v.show()
time.sleep(2)
for n in fn:
  m._tile = Tile(m._tile.id)
  m._tile.x = n.x
  m._tile.y = n.y
  for r in range(n.rot):
    m._tile.rotate()
  v.show()
  time.sleep(1)

time.sleep(500)