Celem gry jest dotarcie 1152
udało mi się to zrobić! Oto przykładowe wyniki wyszukiwania.W pierwszym wierszu trzy liczby to: wynik stanu, głębokość wykresu i maksymalny element z macierzy. Na kolejnych trzech jest macierzą sama:
...
-577 246 576
36 288 9
1 1 576
144 36 72
-577 245 576
36 288 18
18 1 576
144 9 72
-577 249 576
1 288 9
1 288 576
1 1 1
-577 245 576
36 288 1
18 18 576
144 9 72
-577 250 576
1 1 9
1 576 576
1 1 1
-1153 251 1152
1 1 9
1 1 1152
1 1 1
-1153 251 1152
1 1 9
1 1152 1
1 1 1
-577 250 576
1 576 9
1 1 576
1 1 1
-1153 251 1152
1 1 9
1 1 1152
1 1 1
-1153 251 1152
1 1152 9
1 1 1
1 1 1
...
Jak widać, aby uzyskać wynik trzeba zbadać dość głęboko. Weź również pod uwagę, że współczynnik rozgałęzienia jest bardzo duży i możesz zauważyć, że problem stanowi wyzwanie. Musisz wykonać ~ ruchów, aby uzyskać wynik . Zakładając, że zabierze Ci to sekund na ruch, będziesz grać w grę dla 40min !!!
To, co zrobiłem, przypisałem wynik dla każdego węzła/stanu, a podczas eksploracji utrzymywałem tylko najwyższe stany/stany: . Zapewni to, że będziemy eksplorować tylko odpowiednie węzły. Pozostało więc zaprojektowanie funkcji score/heurystyki. Oto co wynik funkcje Próbowałem:
- maksymalna elementu z macierzy
- głębokość węzła
- suma elementów macierzy
- score który opowiada o ile elementy podzielna przez 9 IS sąsiednim elementem jest podzielna przez 9
- liczby odrębnych elementów w macierzy
- liczby odrębnych elementów w macierzy powyżej 9
- liczba różnych elementów w macierzy poniżej 2
- wynik, który mówi o ile elementy podzielna przez 9 jest sąsiedni element, który jest również podzielna przez 9, a jej dwa razy mniejszej
Za pomocą prostych heurystyk mogli budować bardziej złożony. W rezultacie otrzymałem heurystykę, która jest sumą tylko pierwszego i ostatniego z wyżej wymienionej listy. Zbieranie bardziej restrykcyjnych heurystyk utrudnia wyszukiwanie. Oto kod (Python 3):
import random
from queue import PriorityQueue
dx = [0, 0, -1, -1, -1, 1, 1, 1]
dy = [-1, 1, -1, 0, 1, -1, 0, 1]
class State:
def __init__(self, a, depth):
self.depth = depth
if len(a) == 9:
self.a = (tuple(a[:3]), tuple(a[3:6]), tuple(a[6:]))
if len(a) == 3:
self.a = tuple(map(tuple, a))
@staticmethod
def check(i):
return 0 <= i < 3
def get_9_moves(self):
ans = []
for i in range(3):
for j in range(3):
if self.a[i][j] % 9 == 0:
for k in range(len(dx)):
ni, nj = i + dx[k], j + dy[k]
if State.check(ni) and State.check(nj):
if self.a[ni][nj] % 9 == 0 and \
self.a[i][j] == self.a[ni][nj]:
ans.append(((i, j), (ni, nj)))
return ans
def get_sum_moves_rec(self, i, j, cur_sum, cur_cells, ans):
if cur_sum > 9:
return
if cur_sum == 9 and len(cur_cells) > 1:
ans.append(tuple(cur_cells))
for k in range(len(dx)):
ni, nj = i + dx[k], j + dy[k]
pair = (ni, nj)
if self.check(ni) and self.check(nj) and pair not in cur_cells:
cur_cells.append(pair)
self.get_sum_moves_rec(ni, nj, cur_sum + self.a[ni][nj], cur_cells, ans)
cur_cells.pop()
def get_sum_moves(self):
ans = []
for i in range(3):
for j in range(3):
self.get_sum_moves_rec(i, j, self.a[i][j], [(i, j)], ans)
return ans
def get_neighbours(self):
neighbours = []
moves = self.get_sum_moves()
for move in moves:
a = list(map(list, self.a))
for i in range(len(move)):
x, y = move[i]
if i == len(move)-1:
a[x][y] = 9
else:
a[x][y] += 1
neighbours.append(State(a, self.depth+1))
moves = self.get_9_moves()
for move in moves:
a = list(map(list, self.a))
a[move[0][0]][move[0][1]] = 1
a[move[1][0]][move[1][1]] *= 2
neighbours.append(State(a, self.depth+1))
return neighbours
def get_value(self):
return max(map(max, self.a))
# 576
def get_score0(self):
return -self.get_value()
def get_score1(self):
ans = 0
for i in range(3):
for j in range(3):
if self.a[i][j] % 9 == 0:
ans += 1
return ans
# 36
def get_score2(self):
ans = 0
for i in range(3):
for j in range(3):
if self.a[i][j] < 9:
ans += 1
return ans
# achieves 1152 but rather slow
def get_score3(self):
return -self.depth
# 36
def get_score4(self):
ans = 0
for i in range(3):
for j in range(3):
if self.a[i][j] == 1:
ans += 1
return ans
# 288
def get_score5(self):
return -sum(map(sum, self.a))
def get_score6(self):
t = []
for i in range(3):
for j in range(3):
if self.a[i][j] % 9 == 0:
t.append((self.a[i][j], (i, j)))
t.sort(reverse=True)
ans = 0
for i in range(len(t) - 1):
pairi = t[i][1]
pairj = t[i+1][1]
if abs(pairi[0]-pairj[0]) <= 1 and abs(pairi[1]-pairj[1]) <= 1:
ans += 1
break
return -ans
def get_score7(self):
t = []
for i in range(3):
for j in range(3):
if self.a[i][j] % 9 == 0:
t.append(self.a[i][j])
t.sort(reverse=True)
ans = 0
for i in range(len(t) - 1):
if t[i] // t[i+1] == 2:
ans += 1
break
return -ans
def get_score8(self):
t = []
for e in self.a:
t.extend(e)
return len(list(filter(lambda x: x >= 9,t)))
def get_score9(self):
t = []
for e in self.a:
t.extend(e)
return len(list(filter(lambda x: x <= 2,t)))
def get_score10(self):
t = []
for e in self.a:
t.extend(e)
return len(set(filter(lambda x: x >= 9,t)))
def get_score_mix(self):
# achieves 1152
return self.get_score0() + self.get_score6()
def __repr__(self):
ans = ''
for i in range(3):
for j in range(3):
ans += '{0:4d} '.format(self.a[i][j])
ans += '\n'
return ans
def __hash__(self):
return hash(self.a)
def __lt__(self, other):
# hash(self) < hash(other)
pass
class Solver:
@staticmethod
def strategy1(s):
visited = set()
while True:
# print(s)
neighbours = s.get_neighbours()
if len(neighbours) == 0:
break
ns = None
for i in range(30):
ns = random.choice(neighbours)
if not ns in visited:
s = ns
break
if ns is None:
break
print(s.get_value())
@staticmethod
def strategy2(s):
visited = set()
max_depth = 6
max_value = 0
calls = 0
def dfs(state, depth):
# print(state)
nonlocal max_value, calls
calls += 1
if depth > max_depth:
return
if state in visited:
return
visited.add(state)
max_value = max(max_value, s.get_value())
for new_state in state.get_neighbours():
dfs(new_state, depth + 1)
dfs(s, 0)
print(max_value)
print(calls)
@staticmethod
def strategy3(s):
visited = set()
pq = PriorityQueue(maxsize=1000)
pq.put((0, s))
visited.add(s)
max_value = 0
while not pq.empty():
score, state = pq.get()
# print(' score0 score1 score2 score3 score4 score5 score6 score7 score8 score9 score10')
# print('{0:7d} {1:7d} {2:7d} {3:7d} {4:7d} {5:7d} {6:7d} {7:7d} {8:7d} {9:7d} {10:7d}'.format(state.get_score0(), state.get_score1(), state.get_score2(),
# state.get_score3(), state.get_score4(), state.get_score5(),
# state.get_score6(), state.get_score7(), state.get_score8(),
# state.get_score9(), state.get_score10()))
print(score, state.depth, state.get_value())
print(state)
max_value = max(max_value, state.get_value())
for new_state in state.get_neighbours():
# print(random.randint(0, 10))
if new_state not in visited:
visited.add(new_state)
pq._put((new_state.get_score_mix(), new_state))
print(max_value)
start = list(range(1, 10))
random.shuffle(start)
s = State(start, 0)
Solver.strategy3(s)
# s = State([1, 1, 18, 18, 18, 36, 18 , 18, 2 ], 0)
# print(s)
#
# for n in s.get_neighbours():
# print(n)
Co dalej?
Ponieważ procedura nie jest bardzo wydajna (znalezienie odpowiedzi zajmuje około 1 minuty), można spróbować znaleźć lepszą heurystykę, która byłaby przydatna do wyszukiwania. Wygląda na to, że powinny być bardzo luźne, próbując wymodelować wymóg, w przeciwnym razie zepsułoby to wyszukiwanie.
"łączysz sąsiednie numery". jak definiujesz "sąsiednie"? czy masz to, gdy mają wspólną krawędź lub bok? – svs
'Łączysz te same wielokrotności 9'. czy dozwolone są tylko sąsiednie elementy? – svs
możesz prześledzić ścieżkę i numery muszą być jakoś połączone (powyżej, poniżej, po lewej, prawej, po przekątnej) i te same wielokrotności 9 muszą być w sąsiedztwie również – Bruha