Skip to content

Instantly share code, notes, and snippets.

@bgnori
Last active October 25, 2017 09:01
Show Gist options
  • Save bgnori/3ecd42a22afcc6e1fa2eaa58d5d7d617 to your computer and use it in GitHub Desktop.
Save bgnori/3ecd42a22afcc6e1fa2eaa58d5d7d617 to your computer and use it in GitHub Desktop.
import collections
m = [[-1,1,1,-1,-1,1,1,-1,-1,1],[1,"S",1,"L",-1,-1,-1,-1,-1,-1],[-1,-1,-1,1,1,-1,1,-1,1,1],[1,"L",-1,-1,1,-1,1,-1,1,-1],[-1,1,1,-1,-1,-1,-1,"L",1,-1],[1,-1,1,-1,-1,1,-1,1,-1,1],[-1,"L",-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,"G",1],[-1,-1,1,1,-1,-1,-1,1,-1,-1]]
print(m)
class Position(collections.namedtuple("Position", ['x', 'y'])):
__slots__ = ()
def up(self):
return self._replace(y=self.y-1)
def down(self):
return self._replace(y=self.y+1)
def left(self):
return self._replace(x=self.x-1)
def right(self):
return self._replace(x=self.x+1)
class Player(collections.namedtuple("Player", ['position', 'goal', 'hp', 'target', 'hp_max', 'history', 'visited'])):
__slots__ = ()
def move(self, direction):
if direction == 'u':
pos = self.position.up()
elif direction == 'd':
pos = self.position.down()
elif direction == 'l':
pos = self.position.left()
elif direction == 'r':
pos = self.position.right()
else:
assert False, "got %s"%(direction,)
pass
return self._replace(position=pos, history=self.history + (direction,))
def visit(self):
if self.position not in self.visited:
return True, self._replace(visited=self.visited.union(frozenset((self.position,))))
return False, self
def check(self, game):
if self.position == self.goal:
if game.current_best[0] < self.hp:
game.current_best = (self.hp, self.history)
return False
if self.hp < self.hp_max - 5:
return False
return True
greed_dict = {'G': 0, 1:1, -1:2, 'L':3, 'S': 4}
class Game:
def __init__(self, mss):
self.count = 0
self.knownmax = 0
self.current_best = (-100, None)
xss = []
boundary = tuple("L" for x in range(len(mss[0])+2))
xss.append(boundary[:])
for ms in mss:
xss.append(tuple(["L"] + ms[:] + ["L"]))
xss.append(boundary[:])
self.map = tuple(xss)
for yi, ms in enumerate(self.map):
for xi, m in enumerate(ms):
if m == "S":
self.start = Position(xi, yi)
if m == "G":
self.goal = Position(xi, yi)
def setup_pc(self, hp, target):
return Player(
position = self.start,
goal= self.goal,
hp = hp,
target = target,
hp_max = 0,
history = tuple(),
visited = frozenset([self.start]))
def get_sq(self, pos):
assert(isinstance(pos, Position))
return self.map[pos.y][pos.x]
def update(self, player):
m = self.get_sq(player.position)
if isinstance(m, int):
if player.hp + m > player.hp_max:
return player._replace(hp=player.hp+m, hp_max=player.hp+m)
else:
return player._replace(hp=player.hp+m)
elif isinstance(m, str):
if m == "L":
return player._replace(hp=0)
elif m == "G":
return player._replace(hp=player.hp - player.target)
else:
pass
else:
pass
return player
def search(self, p):
self.knownmax = max(self.knownmax, p.hp_max)
self.count += 1
if self.count > 100000:
print(self.knownmax)
print(self.current_best)
self.count = 0
greedy = [(d, self.get_sq(p.move(d).position))for d in 'udlr']
greedy.sort(key=lambda x: greed_dict[x[1]])
for d, _ in greedy:
ok, q = p.move(d).visit()
if ok:
r = self.update(q)
if r.check(self):
self.search(r)
g = Game(m)
print(g.map)
p = g.setup_pc(36, 49)
print(p)
print("search!")
g.search(p)
print("done. maybe not found.")
@bgnori
Copy link
Author

bgnori commented Oct 24, 2017

序盤で見つかる経路例。
(-4, ('u', 'l', 'd', 'd', 'r', 'r', 'd', 'd', 'r', 'u', 'u', 'r', 'u', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'r', 'u', 'r', 'u', 'u', 'u', 'r', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'l', 'd', 'l', 'd', 'l', 'l', 'u', 'l', 'l', 'l', 'u', 'l', 'l', 'd', 'd', 'd', 'd', 'r', 'r', 'u', 'r', 'r', 'd', 'r', 'r', 'r', 'r', 'u')

@bgnori
Copy link
Author

bgnori commented Oct 24, 2017

なおったと思いたい
(-4, ('u', 'r', 'd', 'd', 'r', 'r', 'd', 'd', 'd', 'r', 'd', 'd', 'd', 'r', 'u', 'u', 'u', 'r', 'r', 'u', 'u', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'd', 'l'))

@bgnori
Copy link
Author

bgnori commented Oct 24, 2017

'u', 'r', 'd', 'd', 'r', 'r', 'd', 'd', 'd', 'r', 'd', 'd', 'l', 'l', 'u', 'u', 'l', 'u', 'l', 'd', 'l', 'd', 'd', 'r', 'd', 'd', 'r', 'r', 'u', 'r', 'r', 'r', 'u', 'u', 'u', 'r', 'r', 'u', 'u', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'd', 'l'

@bgnori
Copy link
Author

bgnori commented Oct 25, 2017

BDD/ZDDを使う。Simpathとか実装しないと駄目だろう

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment