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 25, 2017

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

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