Зума вдохновил игровую эвристику и ее преемников ⇐ Python

[Anonymous]

У меня есть университетское задание разработать допустимую эвристику и сократить количество последователей игры, вдохновленной Зумой. В игре есть линия цветных шариков (цвета: 1, 2, 3, 4) и немного боеприпасов. Если подряд подряд выпадают три шара одного цвета, они удаляются с линии. Такое удаление может вызвать каскадные эффекты. Задача требует, чтобы эвристика была допустимой.
Вы можете пропустить шарик из боеприпасов и каждый ход можете использовать только первый шарик из него.
на данный момент это мой код:

Код: Выделить всё

def successor(self, state):
"""Generates optimized successor states for the given state."""
line, ammo = state
successors = []

if not ammo:
return []

balls_count = [0, 0, 0, 0]
ammo_count = [0, 0, 0, 0]

for ball in ammo:
ammo_count[ball - 1] += 1
for ball in line:
balls_count[ball - 1] += 1

# Validate that at least 3 of any color are available
for i in range(4):
if balls_count[i] > 0 and balls_count[i] + ammo_count[i] < 3:
return []

line_len = len(line)
first_ball = ammo[0]

new_ammo = ammo[1:]
# Insert the first ball at each position in the line
for i in range(line_len + 1):
# Skip consecutive balls
if i <  line_len - 1 and line[i] == first_ball:
if line[i + 1] == first_ball:
i = i + 2
continue
i = i + 1
continue

new_line = line[:i] + (first_ball,) + line[i:]
reduced_line = self.check_line_sequences(new_line, i, line_len + 1)

new_state = (reduced_line, new_ammo)

if self.is_redundant(new_state):
continue

action = [i, first_ball]
successors.append((action, new_state))

# Add the skip option
skipped_state = (line, new_ammo)

if not self.is_redundant(skipped_state):
action = ["skip", first_ball]
successors.append((action, skipped_state))

return successors

не удалось найти допустимую эвристику, поэтому я ставлю 1, если это не конец игры, и 0, если это конец.

Код: Выделить всё

problem1 = ((1, 1), (1,))  # 1, t: 0
problem2 = ((1, 2, 2, 1, 1), (2, 1))  # 1, t: 0
problem3 = ((1, 2, 3, 3, 2, 2, 1, 1), (3,))  # 1, t: 0
problem4 = ((2, 2, 3, 2), (3, 3))  # 2, t: 0
problem5 = ((2, 2, 3, 2), (3, 3, 2, 1, 2, 2, 4))  # 2, t: 0
problem6 = ((2, 2, 3, 3, 2), (1, 3))  # 2, t: 0
problem7 = ((3, 3, 4, 4, 3, 3), (3, 4))  # 2, t: 0
problem8 = ((1, 1, 2, 2, 1, 1, 3, 3, 4, 4, 3, 1, 1), (2, 4, 3, 3, 3, 1))  # 2, t: 0
problem9 = ((2, 3, 3, 2), (1, 2, 3))  # 3, t: 0
problem10 = ((4, 1, 2, 3, 3, 2, 2, 1, 1), (4, 3, 4))  # 3, t: 0
problem11 = ((1, 1, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 2, 4, 1, 1, 4, 3, 3, 2, 2, 3, 3, 1, 1), (3, 4, 1, 2, 3, 4))  # 3, t: 0
problem12 = ((2, 2, 3, 3, 1), (1, 1, 2, 3))  # 4, t: 0
problem13 = ((4, 2, 2, 3, 3, 2), (1, 3, 4, 4))  # 4, t: 0
problem14 = ((1, 1, 2, 2, 3, 3, 4, 4, 3, 3, 2, 2, 1, 1), (1, 2, 3, 4))  # 4, t: 0
problem15 = ((1, 1, 2, 2, 3, 3, 4, 4, 3, 3, 2, 2, 1, 1), (1, 2, 3, 4, 1, 2, 3, 4))  # 4, t: 0
problem16 = ((1, 1, 2, 2, 3, 3, 4, 4, 3, 3, 2, 2, 1, 1, 2, 2), (1, 2, 3, 4, 1, 2))  # 4, t: 0.05, 0
problem17 = ((1, 1, 3, 3, 2, 2, 3, 3, 4, 4, 3, 3, 2, 2, 3, 3, 1, 1), (1, 2, 3, 4, 1, 2, 3, 4))  # 4, t: 0.1, 0
problem18 = ((2, 2, 3, 3, 1), (4, 1, 1, 2, 3))  # 5, t: 0
problem18_1 = ((1, 2, 2, 1, 1, 3, 3, 1), (4, 2, 3, 4, 4, 2, 1))  # 5, t: 0
problem19 = ((1, 2, 2, 1, 1, 3, 3, 1), (4, 2, 3, 4, 4, 3, 2, 3, 2, 2, 3, 1, 1))  # 5, t: 0
problem20 = ((1, 1, 2, 4, 1, 1, 4, 3, 3, 2, 2, 3, 3, 1, 1), (3, 4, 1, 2, 3, 4))  # 5, t: 0.25, 0.1
problem21 = ((1, 1, 3, 3, 4, 4, 3, 3, 2, 2, 1, 1, 2, 2), (1, 2, 3, 4, 2, 3, 4))  # 5, t: 0.21, 0.05
problem22 = ((1, 1, 3, 3, 4, 4, 3, 3, 2, 2, 1, 1, 2, 2), (1, 2, 3, 4, 1, 3))  # 5, t: 0.17, 0.03
problem22_1 = ((1, 1, 3, 3, 2, 2, 3, 1, 2, 3, 3, 2, 2, 3, 3, 1, 1), (3, 1, 2, 4, 3, 4, 3, 1))  # 5, t: 0.08, 0.03
problem22_2 = ((1, 1, 3, 3, 2, 2, 3, 1, 4, 2, 3, 3, 2, 2, 3, 3, 1, 1), (3, 4, 1, 2, 4, 3, 4, 3, 1))  # 6, t: 9.6, 2
problem23 = ((3, 3, 4, 4, 3, 3), (3, 1, 2, 3, 2, 1, 4))  # 7, t: 0
problem24 = ((1, 3, 3, 2, 1, 2, 2), (1, 3, 2, 4, 2, 3, 2))  # 7, t: 0
problem25 = ((3, 3, 1, 4, 2, 4, 4, 1, 2, 4, 3), (2, 2, 2, 2, 4, 4, 1, 3))  # 7, t: 0.06
problem25_1 = ((1, 1, 2, 2, 1, 1, 3, 3, 4, 4, 3, 1, 1), (3, 3, 3, 3, 3, 2, 4, 3, 3, 3, 1))  # 7, t: 0.23, 0.06
problem25_2 = ((3, 3, 1, 1, 4, 3, 2, 4, 3, 3, 2, 4, 4, 1, 3), (4, 4, 2, 2, 3, 3, 3, 1, 3))  # 7, t: 9.6, 7.2
problem26 = ((1, 3, 3, 2, 1, 2, 2), (1, 3, 2, 4, 2, 3, 4, 2))  # 8, t: 0.03, 0.01
problem27 = ((1, 2, 1, 2), (1, 2, 4, 1, 2, 2, 4, 1, 3, 2, 1, 2))  # 10, t: 0
problem28 = ((2, 2, 3, 2), (3, 1))  # no, t: 0
problem29 = ((4, 2, 2, 3, 3, 2), (1, 3))  # no, t: 0
problem30 = ((2, 2, 3, 3, 2, 4), (2, 2, 3, 2))  # no, t: 0
problem31 = ((4, 2, 2, 3, 3, 2), (1, 3, 4))  # no, t: 0
problem32 = ((4, 2, 2, 3, 3, 1), (1, 1, 2, 3))  # no, t: 0
problem50 = ((1, 1, 3, 1, 4, 4, 1), (2, 3, 3, 4, 2, 2))

У меня есть эти тесты для проверки, и мне нужно, чтобы они решили их как можно быстрее с наименьшим количеством шаров.

Подробнее здесь: https://stackoverflow.com/questions/792 ... successors