The goal of the game is to reach 1152
I've managed to do it! Here is a sample output of the search. On the first row the three numbers are: score of the state, the depth of the graph, and the maximum element from the matrix. On the next three is the matrix itself:
...
-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
...
As you can see in order to get score 1152 you have to explore pretty deep. Take also into account that the branching factor is very big and you could see that the problem is challenging. You have to do ~250 moves in order to get the score 1152. Assuming that it takes you 10 seconds per move you'll be playing the game for 40min!!!
What I did was I associated a score for each node/state and during the exploration I only kept the top 1000 nodes/states. This ensures that we explore only relevant nodes.
So what was left was engineering the score functions/heuristics. Here what score functions I've tried:
- maximal element from the matrix
- depth of the node
- sum of the elements in the matrix
- score which tells for how many elements divisible by 9 the is neighboring element which is also divisible by 9
- number of distinct elements in the matrix
- number of distinct elements in the matrix above 9
- number of distinct elements in the matrix below 2
- score which tells for how many elements divisible by 9 the is neighboring element which is also divisible by 9 and its twice smaller
Using simple heuristics you could build up more complex. What I ended up with is the heuristics which is a sum of only the first and the last in the above-mentioned list. Picking more restrictive heuristics messes up the search. Here's the code (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)
What's next?
Since the procedure is not very performant ( it takes ~ 1 min to find the answer) one could try to find better heuristics which would be useful for the search. It seems that they should be very loose trying to model the requirement otherwise they would mess up the search.
