air - 自定义俄罗斯方 block 放置算法

Question

这不完全是一个普遍问题，但这就是我们来到这里的原因。

一些背景

我的任务是创建一个类似俄罗斯方 block 的模拟，并让 AI 来玩它。完成后，线条不会消失。最终结果应该是一个矩阵，其中充满了整齐放置的 block ，间隙很少或没有间隙。

我选择做的是一种遗传方法，具有恒定的权重和评估方法。人工智能会尝试将 block 放置在所有可能的位置、旋转、评估临时矩阵，并选择最好的矩阵。

问题

在俄罗斯方 block 中，即使方 block 在地面上，您也可以向左或向右移动。这可以解决许多原本不可能解决的问题。然而，真正的问题是，这些孔甚至可能出现在半空中，如下所示:

falling J shape, with optimal choice occurring mid-air

我在这里看到的唯一解决方案是尝试所有位置、旋转以及所有可能的空中移动组合，正式地说，我认为这“不是最佳解决方案”。

我的问题

如果有人有一个想法或其他方法，找到具有实际计算能力的放置的可能性

Answer 1

单个棋子最多可以放置在单板上 10x20x4 = 800 个位置。这些将是图表的节点。如果您可以通过一次移动从一个节点移动到另一个节点，则存在边缘。然后，您可以修剪非法节点(例如与板上现有障碍物重叠)。您还可以将节点标记为“最终” - 在那里，图 block 的至少一部分正下方有一个障碍物(但它们仍然可以有连接到它们的节点)。

然后您可以检查从初始节点可以到达哪些最终节点，这是一个标准问题。

您可以通过忽略棋子高于棋盘当前高度的节点来进一步优化。

示例代码:

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)