#! /usr/bin/env python # Encoding: UTF-8 import sys import argparse import itertools import heapq from collections import defaultdict, namedtuple from weakref import WeakKeyDictionary from sqlalchemy.orm import aliased from sqlalchemy.orm.exc import NoResultFound from sqlalchemy.sql.expression import not_, and_, or_ from pokedex.db import connect, tables, util ### ### Illegal Moveset exceptions ### class IllegalMoveCombination(ValueError): pass class TooManyMoves(IllegalMoveCombination): pass class NoMoves(IllegalMoveCombination): pass class MovesNotLearnable(IllegalMoveCombination): pass class NoParent(IllegalMoveCombination): pass class TargetExcluded(IllegalMoveCombination): pass class DuplicateMoves(IllegalMoveCombination): pass ### ### Generic helpers ### def powerset(iterable): # recipe from: http://docs.python.org/library/itertools.html "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1)) ### ### Search information object ### class MovesetSearch(object): _cache = WeakKeyDictionary() def __init__(self, session, pokemon, version, moves, level=100, costs=None, pomeg_glitch=False, exclude_versions=(), exclude_pokemon=(), debug_level=0): self.session = session self.debug_level = debug_level try: # Cache all the common stuff. # Not that it takes a lot of time to load, but it can add up # if repeated. self.__dict__ = MovesetSearch._cache[session] except KeyError: self.generator = None self.sketch = util.get(session, tables.Move, identifier=u'sketch').id self.unsketchable = set([ util.get(session, tables.Move, identifier=u'struggle').id, util.get(session, tables.Move, identifier=u'chatter').id, ]) self.no_eggs_group = util.get(session, tables.EggGroup, identifier=u'no-eggs').id self.ditto_group = util.get(session, tables.EggGroup, identifier=u'ditto').id self.load_pokemon() self.load_moves() MovesetSearch._cache[session] = self.__dict__ self.debug_level = debug_level self.pomeg_glitch = pomeg_glitch if not moves: raise NoMoves('No moves specified.') elif len(moves) > 4: raise NoMoves('Too many moves specified.') if costs is None: self.costs = default_costs else: self.costs = costs self.excluded_families = frozenset(p.species.evolution_chain_id for p in exclude_pokemon) if debug_level > 1: print 'Specified moves:', [move.id for move in moves] self.goal_pokemon = pokemon.id self.goal_moves = frozenset(move.id for move in moves) self.goal_version_group = version.version_group_id self.goal_level = level if len(self.goal_moves) < len(moves): raise DuplicateMoves('Cannot learn duplicate moves') if pokemon: self.goal_evolution_chain = pokemon.species.evolution_chain_id if self.goal_evolution_chain in self.excluded_families: raise TargetExcluded('The target pokemon was excluded.') else: self.goal_evolution_chain = None # Fill self.generation_id_by_version_group self.load_version_groups(version.version_group_id, [v.version_group_id for v in exclude_versions]) self.pokemon_moves = defaultdict( # key: pokemon lambda: defaultdict( # key: version_group lambda: defaultdict( # key: move lambda: defaultdict( # key: method list)))) # ordered list of (level, cost) self.movepools = defaultdict(dict) # evo chain -> move -> best cost self.learnpools = defaultdict(set) # evo chain -> move, w/o egg moves easy_moves, non_egg_moves = self.load_pokemon_moves( self.goal_evolution_chain, 'family') # Hard moves: ones we have to breed for or do somehing even costlier # (we might also have to breed for the easy moves, but only within # the family) self.hard_moves = self.goal_moves - easy_moves self.egg_moves = self.goal_moves - non_egg_moves if self.hard_moves: # Have to breed! self.load_pokemon_moves(self.goal_evolution_chain, 'others') self.construct_breed_graph() self.find_duplicate_versions() self.output_objects = dict() kwargs = dict() if debug_level: self._astar_debug_notify_counter = 0 kwargs['notify'] = self.astar_debug_notify kwargs['estimate_error_callback'] = self.astar_estimate_error self.generator = InitialNode(self).find_all_paths(**kwargs) def load_version_groups(self, version, excluded): """Load generation_id_by_version_group & trade_costs """ query = self.session.query(tables.VersionGroup.id, tables.VersionGroup.generation_id) query = query.join(tables.Version.version_group) if excluded: query = query.filter(not_(tables.VersionGroup.id.in_(excluded))) self.generation_id_by_version_group = dict(query) def expand(v2): for v1 in self.generation_id_by_version_group: if self.get_trade_cost(v1, v2): yield 0, None, v1 def is_goal(v): return True goal = self.goal_version_group filtered_map = {goal: self.generation_id_by_version_group[goal]} for result in a_star(self.goal_version_group, expand, is_goal): for cost, transition, version in result: filtered_map[version] = ( self.generation_id_by_version_group[version]) self.generation_id_by_version_group = filtered_map self.trade_costs = defaultdict(dict) for g1 in self.generation_id_by_version_group: for g2 in self.generation_id_by_version_group: cost = self.get_trade_cost(g1, g2) if cost: self.trade_costs[g1][g2] = cost if self.debug_level > 1: print 'Excluded version groups:', excluded print 'Trade cost table:' print '%03s' % '', for g1 in sorted(self.generation_id_by_version_group): print '%03s' % g1, print for g1 in sorted(self.generation_id_by_version_group): print '%03s' % g1, for g2 in sorted(self.generation_id_by_version_group): print '%03s' % self.trade_costs[g1].get(g2, '---'), print def get_trade_cost(self, version_group_from, version_group_to): """Return cost of trading between versions, None if impossibble The generation of traded moves/items should also be checked, if trading to gen. 1. """ # XXX: this ignores HM transfer restrictions if version_group_from == version_group_to: # No reason to trade return None gen_from = self.generation_id_by_version_group[version_group_from] gen_to = self.generation_id_by_version_group[version_group_to] if gen_from == gen_to: return self.costs['trade'] elif gen_from in (1, 2): if gen_to in (1, 2): return self.costs['trade'] else: return None elif gen_to in (1, 2): return None elif gen_from > gen_to: return None elif gen_from < gen_to - 1: return None else: return self.costs['trade'] + self.costs['transfer'] def load_pokemon_moves(self, evolution_chain, selection): """Load pokemon_moves, movepools, learnpools, smeargle_families `selection`: 'family' for loading only pokemon in evolution_chain 'others' for loading only pokemon NOT in evolution_chain Returns: (easy_moves, non_egg_moves) If `selection` == 'family': easy_moves is a set of moves that are easier to obtain than by breeding non_egg_moves is a set of moves that don't require breeding Otherwise, these are empty sets. """ if self.debug_level > 1: print 'Loading pokemon moves, %s %s' % (evolution_chain, selection) query = self.session.query( tables.PokemonMove.pokemon_id, tables.PokemonMove.move_id, tables.PokemonMove.version_group_id, tables.PokemonMoveMethod.identifier, tables.PokemonMove.level, tables.PokemonSpecies.evolution_chain_id, ) query = query.join(tables.PokemonMove.pokemon) query = query.join(tables.Pokemon.species) query = query.filter(tables.PokemonMoveMethod.id == tables.PokemonMove.pokemon_move_method_id) query = query.filter(tables.PokemonMove.version_group_id.in_( set(self.generation_id_by_version_group))) query = query.filter(or_( tables.PokemonMove.level > 100, # XXX: Chaff? tables.PokemonMove.move_id.in_(self.goal_moves), tables.PokemonMove.move_id == self.sketch, tables.PokemonMove.move_id.in_( self.evolution_moves.values()), )) if self.excluded_families: query = query.filter(not_(tables.PokemonSpecies.evolution_chain_id.in_( self.excluded_families))) if evolution_chain: if selection == 'family': query = query.filter(tables.PokemonSpecies.evolution_chain_id == ( evolution_chain)) elif selection == 'others': query = query.filter(tables.PokemonSpecies.evolution_chain_id != ( evolution_chain)) query = query.order_by(tables.PokemonMove.level) easy_moves = set() non_egg_moves = set() self.smeargle_families = set() costs = self.costs movepools = self.movepools learnpools = self.learnpools sketch_cost = costs['sketch'] breed_cost = costs['breed'] for pokemon, move, vg, method, level, chain in query: if move in self.goal_moves: if method == 'level-up': cost = costs['level-up'] else: gen = self.generation_id_by_version_group[vg] if method == 'machine' and gen < 5: cost = costs['machine-once'] elif method == 'tutor' and gen == 3: cost = costs['tutor-once'] elif method == 'egg': cost = costs['breed'] else: cost = costs[method] movepools[chain][move] = min( movepools[chain].get(move, cost), cost) if method != 'egg': learnpools[chain].add(move) non_egg_moves.add(move) if cost < breed_cost: easy_moves.add(move) elif move == self.sketch: cost = sketch_cost self.smeargle_families.add(self.evolution_chains[pokemon]) else: # An evolution move. We need to use it anyway if we need # the evolution, so the cost can be an arbitrary positive # number. But, do check if this family actually needs the move. evolution_chain = self.evolution_chains[pokemon] if move != self.evolution_moves.get(evolution_chain): continue cost = 1 self.pokemon_moves[pokemon][vg][move][method].append((level, cost)) if self.debug_level > 1 and selection == 'family': print 'Easy moves:', sorted(easy_moves) print 'Non-egg moves:', sorted(non_egg_moves) if self.debug_level > 1: print 'Smeargle families:', sorted(self.smeargle_families) return easy_moves, non_egg_moves def load_pokemon(self): """Load pokemon breed groups and evolutions self.egg_groups: maps evolution chains to their sorted egg groups (wil contain empty tuple for no-eggs or ditto) self.evolution_chains: maps pokemon to their evolution chains self.pokemon_by_evolution_chain: maps evolution chains to their pokemon self.unbreedable: set of unbreedable pokemon self.evolution_parents[pokemon] = the pre-evolved form self.evolutions[pokemon] = list of (trigger, move, level, child) self.evolution_moves[evolution_chain] = move required for evolution self.babies[egg_group_id] = set of baby pokemon self.hatch_counters[pokemon] = hatch counter self.gender_rates[evolution_chain] = gender rate self.switchable_form_pokemon[pokemon] = set of pokemon for switchable forms """ eg1 = tables.PokemonEggGroup eg2 = aliased(tables.PokemonEggGroup) # Gotta do little species dance to get the evolution parent pokemon parent_species = aliased(tables.PokemonSpecies) parent_pokemon = aliased(tables.Pokemon) query = self.session.query( tables.Pokemon.id, tables.PokemonSpecies.evolution_chain_id, tables.PokemonSpecies.id, tables.PokemonSpecies.forms_switchable, parent_pokemon.id, eg1.egg_group_id, eg2.egg_group_id, tables.EvolutionChain.baby_trigger_item_id, tables.PokemonSpecies.hatch_counter, tables.PokemonSpecies.gender_rate, ) query = query.join(tables.Pokemon.species) query = query.join(tables.PokemonSpecies.evolution_chain) query = query.outerjoin((parent_species, tables.PokemonSpecies.parent_species)) query = query.outerjoin((parent_pokemon, parent_species.pokemon)) query = query.join((eg1, eg1.species_id == tables.PokemonSpecies.id)) query = query.outerjoin((eg2, and_( eg2.species_id == tables.PokemonSpecies.id, eg1.egg_group_id < eg2.egg_group_id, ))) bad_groups = (self.no_eggs_group, self.ditto_group) unbreedable = dict() # pokemon->evolution chain self.evolution_parents = dict() self.egg_groups = defaultdict(tuple) self.evolution_chains = dict() self.pokemon_by_evolution_chain = defaultdict(set) self.babies = defaultdict(set) self.hatch_counters = dict() self.gender_rates = dict() self.switchable_form_pokemon = dict() switchable_pokemon_by_species = defaultdict(set) item_baby_chains = set() # evolution chains with baby-trigger items for (pokemon, evolution_chain, species, forms_switchable, parent, g1, g2, baby_item, hatch_counter, gender_rate) in query: self.hatch_counters[pokemon] = hatch_counter self.gender_rates[evolution_chain] = gender_rate if g1 in bad_groups: unbreedable[pokemon] = evolution_chain else: groups = (g1, g2) if g2 else (g1, ) if len(self.egg_groups.get(evolution_chain, ())) <= len(groups): self.egg_groups[evolution_chain] = groups if not parent: for group in groups: self.babies[group].add(pokemon) self.evolution_chains[pokemon] = evolution_chain self.pokemon_by_evolution_chain[evolution_chain].add(pokemon) if parent: self.evolution_parents[pokemon] = parent if baby_item: item_baby_chains.add(evolution_chain) if forms_switchable: # Each form-swithable species shares a set of the switchable # pokemon. When adding a pokémon we assign the set to it, # and add the pokémon to it (mutating the shared copy). # So in the end, each of the pokémon ends up with the complete # set for its species. switchable = switchable_pokemon_by_species[species] self.switchable_form_pokemon[pokemon] = switchable switchable.add(pokemon) self.unbreedable = frozenset(unbreedable) self.evolutions = defaultdict(set) self.evolution_moves = dict() query = self.session.query( tables.Pokemon.id, tables.EvolutionTrigger.identifier, tables.PokemonEvolution.known_move_id, tables.PokemonEvolution.minimum_level, ) query = query.join(tables.PokemonEvolution.trigger) query = query.join(tables.PokemonEvolution.evolved_species) query = query.join(tables.PokemonSpecies.pokemon) for child, trigger, move, level in query: self.evolutions[self.evolution_parents[child]].add( (trigger, move, level, child)) if move: self.evolution_moves[self.evolution_chains[child]] = move if self.debug_level > 1: print 'Loaded %s pokemon: %s evo; %s families: %s breedable' % ( len(self.evolution_chains), len(self.pokemon_by_evolution_chain), len(self.egg_groups), len(self.evolutions), ) print 'Evolution moves: %s' % self.evolution_moves # Chains with unbreedable babies for baby, evolution_chain in unbreedable.items(): if baby not in self.evolution_parents: groups = self.egg_groups[evolution_chain] for group in groups: self.babies[group].add(baby) # Chains with item-triggered alternate babies for item_baby_chain in item_baby_chains: for item_baby in self.pokemon_by_evolution_chain[item_baby_chain]: if item_baby not in self.evolution_parents: for regular_baby in self.evolutions[item_baby]: for group in self.egg_groups[item_baby_chain]: self.babies[group].add(pokemon) def load_moves(self): """Load move_generations""" query = self.session.query( tables.Move.id, tables.Move.generation_id, ) self.move_generations = dict(query) if self.debug_level > 1: print 'Loaded %s moves' % len(self.move_generations) def construct_breed_graph(self): """Fills breeds_required breeds_required[egg_group][moveset] = minimum number of breeds needed from a pokemon in this group with this moveset to the goal pokemon with the goal moveset. The score cannot get lower by learning new moves, only by breeding. If missing, breeding or raising the pokemon won't do any good. Exceptions: For pokemon in the target family, breeds_required doesn't apply. For the empty moveset just check if any moveset is worthwhile (i.e. bool(breeds_required[egg_group])). """ # Part I. Determining what moves can be passed/learned # eg1_movepools[egg_group_id] = set of moves passable by pkmn in that group eg1_movepools = defaultdict(set) # eg2_movepools[b_g_id1, b_g_id2] = ditto for pkmn in *both* groups eg2_movepools = defaultdict(set) # non_egg_pools = as eg1_movepools but for *learnable* moves learn_pools = defaultdict(set) goal_egg_groups = self.egg_groups[self.goal_evolution_chain] all_groups = set() for family, groups in self.egg_groups.iteritems(): if not groups: continue if family == self.goal_evolution_chain: continue elif family in self.smeargle_families: pool = self.goal_moves else: pool = self.movepools[family] pool = set(pool) & self.goal_moves learnpool = self.learnpools[family] & pool for group in groups: eg1_movepools[group].update(pool) learn_pools[group].update(learnpool) all_groups.add(group) if len(groups) >= 2: eg2_movepools[groups].update(pool) if self.debug_level > 1: print 'Egg group summary:' for group in sorted(all_groups): print "%2s can pass: %s" % (group, sorted(eg1_movepools[group])) if learn_pools[group] != eg1_movepools[group]: print " but learn: %s" % sorted(learn_pools[group]) for g2 in sorted(all_groups): for g1 in sorted(all_groups): if eg2_movepools[g1, g2]: print " %2s/%2s pass: %s" % (g1, g2, sorted(eg2_movepools[g1, g2])) print 'Goal groups:', goal_egg_groups # Part II. Determining which moves are worthwhile to pass # We want *all* paths, not just shortest ones, so use DFS. breeds_required = defaultdict(dict) def handle(group, moves, path): """ group: the group of the parent moves: moves the parent should pass down path: previously visited groups - to prevent cycles """ if not moves: # No more moves needed to pass down: success! return True if breeds_required[group].get(moves, 999) <= len(path): # Already done return True success = False # Breed some more path = path + (group, ) for new_group in all_groups.difference(path): new_groups = tuple(sorted([group, new_group])) # Can we pass down all the requested moves? if moves.issubset(eg1_movepools[new_group]): # Learn some of the moves: they don't have to be passed to us for learned in powerset(moves & learn_pools[new_group]): new_moves = moves.difference(learned) local_success = handle(new_group, new_moves, path) # If this chain eventually ended up being successful, # it means that it is useful to pass this moveset # to this group. if local_success: breeds_required[group][moves] = min(breeds_required[group].get(moves, 999), len(path) - 1) success = True return success for group in goal_egg_groups: handle(group, self.hard_moves, ()) for moves in powerset(self.goal_moves): if moves: breeds_required[group][frozenset(moves)] = 1 self.breeds_required = breeds_required if self.debug_level > 1: for group, movesetlist in breeds_required.items(): print 'From egg group', group for moveset, cost in movesetlist.items(): print " %s breeds with %s" % (cost, sorted(moveset)) def find_duplicate_versions(self): """Fill `duplicate_versions` duplicate_versions[pokemon][version_group] = set of version groups that are identical as far as the pokemon learning those moves is concerned, and are in the same generation. Thus, trading between them is unnecessary. """ self.duplicate_versions = dict() counter = 0 for pokemon, vg_moves in self.pokemon_moves.items(): dupes = self.duplicate_versions[pokemon] = dict() last = None last_moves = None last_gen = None for version_group, moves in vg_moves.items(): gen = self.generation_id_by_version_group[version_group] if gen == last_gen and moves == last_moves: last.add(version_group) dupes[version_group] = last counter += 1 else: last = set([version_group]) dupes[version_group] = last last_moves = moves last_gen = gen if self.debug_level > 1: print 'Deduplicated %s version groups' % counter def astar_debug_notify(self, cost, node, setsize, heapsize): counter = self._astar_debug_notify_counter if counter % 100 == 0: print 'A* iteration %s, cost %s; remaining: %s (%s) \r' % ( counter, cost, setsize, heapsize), sys.stdout.flush() self._astar_debug_notify_counter += 1 def astar_estimate_error(self, result): print '**warning: bad A* estimate**' print_result(result) def __iter__(self): return self.generator def get_by_id(self, table, id): key = table, 'id', id try: return self.output_objects[key] except KeyError: o = self.output_objects[key] = util.get(self.session, table, id=id) return o def get_by_identifier(self, table, ident): key = table, 'identifier', ident try: return self.output_objects[key] except KeyError: o = self.output_objects[key] = util.get(self.session, table, identifier=ident) return o def get_list(self, table, ids): key = table, 'list', ids try: return self.output_objects[key] except KeyError: o = self.output_objects[key] = sorted( (util.get(self.session, table, id=id) for id in ids), key=lambda x: x.identifier) return o ### ### Costs ### default_costs = { # Costs for learning a move in various ways 'level-up': 20, # The normal way 'machine': 40, # Machines are slightly inconvenient. 'machine-once': 2000, # before gen. 5, TMs only work once. Avoid. 'tutor': 60, # Tutors are slightly more inconvenient than TMs – can't carry them around 'tutor-once': 2100, # gen III: tutors only work once (well except Emerald frontier ones) # For technical reasons, 'sketch' is also used for learning Sketch and # by normal means, if it isn't included in the target moveset. # So the actual cost of a sketched move will be double this number. 'sketch': 1, # Cheap. Exclude Smeargle if you think it's too cheap. # Gimmick moves – we need to use this method to learn the move anyway, # so make a big-ish dent in the score if missing 'stadium-surfing-pikachu': 100, 'light-ball-egg': 100, # … # Ugh... I don't know? 'colosseum-purification': 100, 'xd-shadow': 100, 'xd-purification': 100, 'form-change': 100, # Other actions. # Breeding should cost more than 3 times a lv-up/machine/tutor move. 'evolution': 100, # We have to do this anyway, usually. 'evolution-delayed': 50, # *in addition* to evolution. Who wants to mash B on every level. 'breed': 400, # Breeding's a pain. 'trade': 200, # Trading's a pain, but not as much as breeding. 'transfer': 150, # *in addition* to trade. Keep it below 'trade'. 'forget': 300, # Deleting a move. (Not needed unless deleting an evolution move.) 'relearn': 150, # Also a pain, though not as big as breeding. 'per-level': 1, # Prefer less grinding. This is for all lv-ups but the final “grow” 'form-switch': 5, # Not a big deal # Breeding for moves the target pokemon leans easily is kind of stupid. # (Though not *very* stupid, and since the program considers evolution # chains as a group, the penalty should be much smaller than normal move cost.) 'egg': 3, # General cost of breeding a move 'per-hatch-counter': 1, # penalty for 1 initial hatch counter point (these range from 5 to 120) # Penalty for *not* breeding a required egg move; this makes parents # with more required moves gain a big advantage over the competition 'breed-penalty': 100, } ### ### A* ### class Node(object): """Node for the A* search algorithm. To get started, implement `expand` & `is_goal` and call `find_path`. N.B. Node objects must be hashable. """ def expand(self): """Return a list of (costs, transition, next_node) for next states "Next states" are those reachable from this node. May return any finite iterable. """ raise NotImplementedError def is_goal(self): """Return true iff this is a goal node. """ raise NotImplementedError def estimate(self): """Return an *optimistic* estimate of the cost to the given goal node. If there are multiple goal states, return the lowest estimate among all of them. """ return 0 def find_path(self, goal=None, **kwargs): """Return the best path to the goal Returns an iterator of (cost, transition, node) triples, in reverse order (i.e. the first element will have the total cost and goal node). If `goal` will be passed to the `estimate` and `is_goal` methods. See a_star for the advanced keyword arguments, `notify` and `estimate_error_callback`. """ paths = self.find_all_paths(**kwargs) try: return paths.next() except StopIteration: return None def find_all_paths(self, **kwargs): """Yield the best path to each goal Returns an iterator of paths. See the `search` method for how paths look. Giving the `goal` argument will cause it to search for that goal, instead of consulting the `is_goal` method. This means that if you wish to find more than one path, you must not pass a `goal` to this method, and instead reimplament `is_goal`. See a_star for the advanced keyword arguments, `notify` and `estimate_error_callback`. """ return a_star( initial=self, expand=lambda s: s.expand(), estimate=lambda s: s.estimate(), is_goal=lambda s: s.is_goal(), **kwargs) def a_star(initial, expand, is_goal, estimate=lambda x: 0, notify=None, estimate_error_callback=None): """A* search algorithm for a consistent heuristic General background: http://en.wikipedia.org/wiki/A*_search_algorithm This algorithm will work in large or infinite search spaces. This version of the algorithm is modified for multiple possible goals: it does not end when it reaches a goal. Rather, it yields the best path for each goal. (Exhausting the iterator is of course not recommended for large search spaces.) Returns an iterable of paths, where each path is an iterable of (cummulative cost, transition, node) triples representing the path to the goal. The transition is the one leading to the corresponding node. The path is in reverse order, thus its first element will contain the total cost and the goal node. The initial node is not included in the returned path. Arguments: `initial`: the initial node `expand`: function yielding a (cost of transition, transition, next node) triple for each node reachable from its argument. The `transition` element is application data; it is not touched, only returned as part of the best path. `estimate`: function(x) returning optimistic estimate of cost from node x to a goal. If not given, 0 will be used for estimates. `is_goal`: function(x) returning true iff x is a goal node `notify`: If given, if is called at each step with three arguments: - current cost (with estimate). The cost to the next goal will not be smaller than this. - current node - open set cardinality: roughly, an estimate of the size of the boundary between "explored" and "unexplored" parts of node space - debug: stats that be useful for debugging or tuning (in this implementation, this is the open heap size) The number of calls to notify or the current cost can be useful as stopping criteria; the other values may help in tuning estimators. `estimate_error_callback`: function handling cases where an estimate was detected not to be consistent. The function is given a path (as would be returned by a_star, except it does not lead to a goal node). By default, nothing is done (as an estimate that's not even optimistic can still be useful). """ # g: best cummulative cost (from initial node) found so far # h: optimistic estimate of cost to goal # f: g + h closed = set() # nodes we don't want to visit again est = estimate(initial) # estimate total cost opened = _HeapDict() # node -> (f, g, h) opened[initial] = (est, 0, est) came_from = {initial: None} # node -> (prev_node, came_from[prev_node]) while True: # _HeapDict will raise StopIteration for us try: x, (f, g, h) = opened.pop() except IndexError: raise StopIteration closed.add(x) if notify is not None: notify(f, x, len(opened.dict), len(opened.heap)) if is_goal(x): yield _trace_path(came_from[x]) for cost, transition, y in expand(x): if y in closed: continue tentative_g = g + cost old_f, old_g, h = opened.get(y, (None, None, None)) if old_f is None: h = estimate(y) elif tentative_g > old_g: continue came_from[y] = ((tentative_g, transition, y), came_from[x]) new_f = tentative_g + h opened[y] = new_f, tentative_g, h if estimate_error_callback is not None and new_f < f: estimate_error_callback(_trace_path(came_from[y])) def _trace_path(cdr): """Backtrace an A* result""" # Convert a lispy list to a pythony iterator while cdr: car, cdr = cdr yield car class _HeapDict(object): """A custom parallel heap/dict structure -- the best of both worlds. This is NOT a general-purpose class; it only supports what a_star needs. """ # The dict has the definitive contents # The heap has (value, key) pairs. It may have some extra elements. def __init__(self): self.dict = {} self.heap = [] def __setitem__(self, key, value): self.dict[key] = value heapq.heappush(self.heap, (value, key)) def __delitem__(self, key): del self.dict[key] def get(self, key, default): """Return value for key, or default if not found """ return self.dict.get(key, default) def pop(self): """Return (key, value) with the smallest value. Raises IndexError if empty """ while True: value, key = heapq.heappop(self.heap) # raises IndexError for us if key in self.dict: del self.dict[key] return key, value ### ### Result objects ### class Facade(object): """Facade for optput objects The main algorithm uses integers (and tiny strings, and sets, dicts, tuples you get the picture...). The rest of the world uses ORM objects. So, all objects that are returned in results have "object ID" attributes ending in an underscore (e.g. pokemon_), and this base class adds underscore-less properties that get the underlying object. """ @property def pokemon(self): return self.search.session.query(tables.Pokemon).filter_by(id=self.pokemon_).one() @property def version_group(self): return self.search.get_by_id(tables.VersionGroup, self.version_group_) @property def versions(self): return self.version_group.versions @property def move(self): return self.search.get_by_id(tables.Move, self.move_) @property def moves(self): return self.search.get_list(tables.Move, self.moves_) @property def move_method(self): return self.search.get_by_identifier(tables.PokemonMoveMethod, self.move_method_) @property def evolution_trigger(self): return self.search.get_by_identifier(tables.EvolutionTrigger, self.evolution_trigger_) ### ### Search space transitions ### class Action(Facade): pass class StartAction(Action, namedtuple('StartAcion', 'search pokemon_ version_group_')): def __unicode__(self): vers = ' or '.join(v.name for v in self.versions) return u"Start with {0.pokemon.name} in {1}".format(self, vers) class LearnAction(Action, namedtuple('LearnAction', 'search move_ move_method_')): def __unicode__(self): return u"Learn {0.move.name} by {0.move_method.name}".format(self) class RelearnAction(Action, namedtuple('RelearnAction', 'search move_')): def __unicode__(self): return u"Relearn {0.move.name}".format(self) class ForgetAction(Action, namedtuple('ForgetAction', 'search move_')): def __unicode__(self): return u"Forget {0.move.name}".format(self) class TradeAction(Action, namedtuple('TradeAction', 'search version_group_')): def __unicode__(self): vers = ' or '.join(v.name for v in self.versions) return u"Trade to {1}".format(self, vers) class EvolutionAction(Action, namedtuple('EvolutionAction', 'search pokemon_ evolution_trigger_ moves_')): def __unicode__(self): return u"Evolve to {0.pokemon.name} by {0.evolution_trigger.name}".format(self) class ShedEvolutionAction(EvolutionAction, namedtuple('EvolutionAction', 'search pokemon_ evolution_trigger_ moves_')): def __unicode__(self): mvs = ', '.join(m.name for m in self.moves) return u"Co-evolve to {0.pokemon.name}, learning {1}".format(self, mvs) class FormSwitchAction(Action, namedtuple('EvolutionAction', 'search pokemon_')): def __unicode__(self): return u"Switch to {0.pokemon.name}".format(self) class GrowAction(Action, namedtuple('GrowAction', 'search level')): def __unicode__(self): return u"Grow to level {0.level}".format(self) class SketchAction(Action, namedtuple('SketchAction', 'search move_')): def __unicode__(self): return u"Sketch {0.move.name}".format(self) class BreedAction(Action, namedtuple('BreedAction', 'search pokemon_ moves_')): def __unicode__(self): mvs = ', '.join(m.name for m in self.moves) return u"Breed {0.pokemon.name} with {1}".format(self, mvs) ### ### Search space nodes ### class InitialNode(Node, namedtuple('InitialNode', 'search')): def expand(self): search = self.search pokemon_vgs = [] for pokemon, version_groups in search.pokemon_moves.items(): egg_groups = search.egg_groups[search.evolution_chains[pokemon]] if any(search.breeds_required[group] for group in egg_groups): for version_group in version_groups: pokemon_vgs.append((pokemon, version_group)) for pokemon in search.pokemon_by_evolution_chain[search.goal_evolution_chain]: # We treat Shedinja as learning Ninjask moves by evolution itself. # Nincada doesn't learn the moves and therefore may not be in # pokemon_moves, but is required for getting them. So we have to # include Nincada among the initial nodes explicitly. # (For everybody else, three duplicate nodes aren't a problem) for version_group in search.generation_id_by_version_group: pokemon_vgs.append((pokemon, version_group)) # And for the Pomeg glitch, it we may need to start by breeding # an empty moveset if search.pomeg_glitch: for version_group in search.generation_id_by_version_group: cost = search.costs['breed'] yield cost, None, GoalBreedNode(search=search, dummy='g', version_group_=version_group, moves_=frozenset()) for pokemon, version_group in pokemon_vgs: action = StartAction(search, pokemon, version_group) node = PokemonNode( search=search, pokemon_=pokemon, level=0, version_group_=version_group, moves_=frozenset(), new_level=True, ) yield 0, action, node def is_goal(self): return False class PokemonNode(Node, Facade, namedtuple('PokemonNode', 'search pokemon_ level version_group_ new_level moves_')): def __str__(self): return "lv.{level:3}{s} {species:<10.10}{form:3.3} in {version_group_:3} with {moves}".format( s='*' if self.new_level else ' ', moves=','.join(sorted(move.identifier for move in self.moves)) or '---', self=self, species=self.pokemon.species.identifier, form=self.pokemon.default_form.form_identifier or '', **self._asdict()) def expand(self): search = self.search evo_chain = search.evolution_chains[self.pokemon_] if not self.moves_: # Learn something first # (other expand_* than listed here may rely on there being a move) return itertools.chain( self.expand_learn(), # Shedinja actually learns stuff by evolution self.expand_evolutions(), ) elif self.moves_.difference(self.search.goal_moves): # Learned too much! # Moves that aren't in the goal set are either Sketch or evolution # moves. # For the former, use the sketch; for the latter, evolve and # forget the move. return itertools.chain( self.expand_sketch(), self.expand_forget(), self.expand_evolutions(), ) elif evo_chain != search.goal_evolution_chain: if not any(self.moves_ in search.breeds_required[group] for group in search.egg_groups[evo_chain]): # It doesn't make sense to train this any more, since there's # no way to pass the moves to the goal pokemon. return () gender_rate = search.gender_rates[evo_chain] if gender_rate == 8 or gender_rate < 0: # Female-only and genderless pokémon can not pass moves down at # all. return () if len(self.moves_) == 4: learns = () else: learns = self.expand_learn() return itertools.chain( learns, self.expand_trade(), self.expand_grow(), self.expand_evolutions(), self.expand_form_change(), self.expand_breed(), ) def expand_learn(self): search = self.search moves = search.pokemon_moves[self.pokemon_][self.version_group_] for move, methods in moves.items(): if move in self.moves_: continue for method, levels_costs in methods.items(): if method == 'level-up': for level, cost in levels_costs: level_difference = level - self.level if level_difference > 0 or ( level_difference == 0 and self.new_level): cost += level - self.level * search.costs['per-level'] yield self._learn(move, method, cost, level=level, new_level=True) elif search.generation_id_by_version_group[ self.version_group_] > 1: yield self._learn(move, 'relearn', search.costs['relearn'], action=RelearnAction(self.search, move), new_level=False) elif method in 'machine tutor'.split(): for level, cost in levels_costs: yield self._learn(move, method, cost, new_level=False) elif method == 'egg': # ignored here pass elif method == 'light-ball-egg': if self.level == 0 and self.new_level: for level, cost in levels_costs: yield self._learn(move, method, cost) elif method == 'stadium-surfing-pikachu': for level, cost in levels_costs: yield self._learn(move, method, cost, new_level=False) elif method == 'form-change': for level, cost in levels_costs: # Learn this at goal level, but only if the current # level is strictly lower. # That'll prevent the pokémon to learn more than one # of these without us having to keep track of the other # forms and their moves. if self.level < search.goal_level: yield self._learn(move, method, cost, level=search.goal_level, new_level=True) else: raise ValueError('Unknown move method %s' % method) def _learn(self, move, method, cost, action=None, **kwargs): kwargs['moves_'] = self.moves_.union([move]) if action is None: action = LearnAction(self.search, move, method) return cost, action, self._replace( **kwargs) def expand_forget(self): cost = self.search.costs['forget'] for move in self.moves_.difference(self.search.goal_moves): yield cost, ForgetAction(self.search, move), self._replace( moves_=self.moves_.difference([move]), new_level=False) def expand_trade(self): search = self.search target_vgs = search.trade_costs[self.version_group_] if not target_vgs: return gen_from = search.generation_id_by_version_group[self.version_group_] if gen_from == 2: max_gen = max(search.move_generations[m] for m in self.moves_) for version_group, cost in target_vgs.items(): if (gen_from == 2 and max_gen == 2 and search.generation_id_by_version_group[version_group] == 1): continue yield cost, TradeAction(search, version_group), self._replace( version_group_=version_group, new_level=False) def expand_grow(self): search = self.search if (self.pokemon_ == search.goal_pokemon and self.version_group_ == search.goal_version_group and self.moves_ == search.goal_moves and self.level <= search.goal_level): kwargs = self._asdict() kwargs['level'] = search.goal_level kwargs['new_level'] = 'G' yield 0, GrowAction(search, search.goal_level), GoalNode(**kwargs) def expand_evolutions(self): search = self.search for trigger, move, level, child in search.evolutions[self.pokemon_]: kwargs = dict(pokemon_=child) cost = search.costs['evolution'] if move and move not in self.moves_: continue if trigger == 'shed': # Shedinja uses Ninjask's minimum level for trigger2, move2, level2, child2 in search.evolutions[self.pokemon_]: if child2 == child: continue level = level2 if level: if level > self.level: kwargs['level'] = level cost += search.costs['per-level'] * (level - self.level) kwargs['new_level'] = True elif level == self.level: if self.new_level: # We just grew here pass else: # Have to gain a level kwargs['level'] = level + 1 kwargs['new_level'] = True cost += search.costs['evolution-delayed'] else: cost += search.costs['evolution-delayed'] elif trigger == 'level-up': # Have to gain a level kwargs['level'] = self.level + 1 kwargs['new_level'] = True if trigger in 'level-up use-item'.split(): pass elif trigger == 'trade': kwargs['new_level'] = False elif trigger == 'shed': # Find the Ninjask for trigger2, move2, level2, child2 in search.evolutions[self.pokemon_]: if child2 == child: continue additional_moves = defaultdict(set) # level -> moves # Get all of Ninjask's moves nicely sorted for move, levels_costs in search.pokemon_moves[child2][self.version_group_].items(): for level, cost in levels_costs.get('level-up', []): additional_moves[level].add(move) # Figure out at which level we're *really* evolving here for new_level, moves in additional_moves.items(): if level >= level2: shed_kwargs = dict(kwargs) shed_kwargs['level'] = new_level for shed_moves in powerset(moves): if not shed_moves: continue shed_kwargs['moves_'] = new_moves = self.moves_.union(shed_moves) yield cost, ShedEvolutionAction(search, child, trigger, new_moves), self._replace( **shed_kwargs) else: raise ValueError('Unknown evolution trigger %s' % trigger) # N.B. The Shedinja evolution relies on kwargs being final. # Don't add anything between 'shed' and this! yield cost, EvolutionAction(search, child, trigger, self.moves_), self._replace( **kwargs) def expand_form_change(self): search = self.search for pokemon in search.switchable_form_pokemon.get(self.pokemon_, ()): if pokemon != self.pokemon_: yield search.costs['form-switch'], FormSwitchAction( search, pokemon), self._replace(pokemon_=pokemon, new_level=False) def expand_breed(self): search = self.search if self.pokemon_ in search.unbreedable: return if search.generation_id_by_version_group[self.version_group_] == 1: return evo_chain = search.evolution_chains[self.pokemon_] gender_rate = search.gender_rates[evo_chain] if gender_rate == 8 or gender_rate < 0: # Female-only and genderless pokémon can not pass moves down at # all. return egg_groups = search.egg_groups[evo_chain] breeds_required = search.breeds_required moves = self.moves_ cost = search.costs['breed'] cost += search.costs['egg'] * len(moves) cost += search.costs['breed-penalty'] * len(search.egg_moves - moves) goal_family = search.goal_evolution_chain goal_groups = search.egg_groups[goal_family] goal_compatible = set(goal_groups).intersection(egg_groups) for group in egg_groups: if moves in breeds_required[group]: yield cost, None, BreedNode(search=self.search, dummy='b', group_=group, version_group_=self.version_group_, moves_=self.moves_) # Since the target family is not included in our breed graph, we # breed with it explicitly. There must be a female to breed with, # unless this is already the target family so we can breed w/ Ditto. if goal_compatible and (goal_family == evo_chain or 0 <= search.gender_rates[search.goal_evolution_chain] < 8): yield cost, None, GoalBreedNode(search=self.search, dummy='g', version_group_=self.version_group_, moves_=self.moves_) def expand_sketch(self): sketch = self.search.sketch if sketch in self.moves_: for sketched in sorted(self.search.goal_moves): if sketched in self.search.unsketchable: continue if sketched not in self.moves_: moves = set(self.moves_) moves.remove(sketch) moves.add(sketched) action = SketchAction(self.search, sketched) cost = self.search.costs['sketch'] yield cost, action, self._replace( new_level=False, moves_=frozenset(moves)) def estimate(self): # Given good estimates, A* finds solutions much faster. # However, here it seems we either have easy movesets, which # get found pretty easily by themselves, or hard ones, where # heuristics don't help too much, or impossible ones where they # don't matter at all. # So, keep the computations here to a minimum. search = self.search if self.version_group_ == search.goal_version_group: trade_cost = 0 else: trade_cost = search.trade_costs[self.version_group_].get( search.goal_version_group, search.costs['trade'] * 2) return trade_cost def is_goal(self): return False class BaseBreedNode(Node): """Breed node This serves to prevent duplicate breeds, by storing only the needed info in the namedtuple. Also, the base breed cost was already paid, so the breeding tends to happen later in the algorithm. """ def expand(self): search = self.search vg = self.version_group_ gen = search.generation_id_by_version_group[vg] hatch_level = 5 if (gen < 4) else 1 for baby in self.babies(): bred_moves = self.moves_ moves = search.pokemon_moves[baby][vg] if not bred_moves.issubset(moves): continue learns = True for move in bred_moves: learns = False for method, levels_costs in moves[move].items(): if method in ('egg', 'machine'): learns = True break if not learns: break if not learns: continue extra_moves = set() if len(bred_moves) < 4: for move, methods in moves.items(): for method, levels_costs in moves[move].items(): if method == 'light-ball-egg': extra_moves.add(move) elif method == 'level-up': # The bred pokémon starts out with "starting" # level-up moves # XXX: these may get overwritten. This doesn't # affect moveset legality because games with # breeding have move relearners, but the # instructions won't be right. if (search.pomeg_glitch and gen == 3) or any( level <= hatch_level for level, cost in levels_costs): extra_moves.add(move) cost = search.costs['per-hatch-counter'] * search.hatch_counters[baby] for extra in powerset(extra_moves): all_bred_moves = bred_moves.union(extra) if len(all_bred_moves) <= 4: action = BreedAction(self.search, baby, all_bred_moves) node = PokemonNode(search=self.search, pokemon_=baby, level=hatch_level, version_group_=vg, moves_=all_bred_moves, new_level=False) yield 0, action, node def is_goal(self): return False class BreedNode(BaseBreedNode, namedtuple('BreedNode', 'search dummy group_ version_group_ moves_')): def babies(self): search = self.search for baby in search.babies[self.group_]: baby_chain = search.evolution_chains[baby] if self.moves_.issubset(search.movepools[baby_chain]) and ( search.gender_rates[baby_chain] > 0): yield baby class GoalBreedNode(BaseBreedNode, namedtuple('GoalBreedNode', 'search dummy version_group_ moves_')): def babies(self): search = self.search goal_family = search.goal_evolution_chain group = search.egg_groups[goal_family][0] for baby in search.pokemon_by_evolution_chain[goal_family]: if baby in search.babies[group]: yield baby class GoalNode(PokemonNode): def expand(self): return () def is_goal(self): return True ### ### Interface ### def verify_moveset(session, pokemon, version, moves, level=100, **kwargs): """Verify the given moveset. Returns a result with a hint on how to obtain the moveset, if it is valid. Otherwise, returns a false value. """ try: search = MovesetSearch(session, pokemon, version, moves, level, **kwargs) except IllegalMoveCombination, e: return False else: for result in search: return result def print_result(result, moves=()): template = u"{cost:4} {est:4} {action:45.45}{long:1} {pokemon:10}{level:>3}{nl:1}{versions:2} {moves}" print template.format(cost='Cost', est='Est.', action='Action', pokemon='Pokemon', long='', level='Lv.', nl='V', versions='er', moves=''.join(m.name[0].lower() for m in moves)) for cost, action, node in reversed(list(result)): if action: print template.format( cost=cost, action=action, long='>' if (len(unicode(action)) > 45) else '', est=node.estimate(), pokemon=node.pokemon.name, nl='.' if node.new_level else ' ', level=node.level, versions=''.join(v.name[0] for v in node.versions), moves=''.join('.' if m in node.moves else ' ' for m in moves) + ''.join(m.name[0].lower() for m in node.moves if m not in moves), ) def main(argv, session=None): parser = argparse.ArgumentParser(description= 'Find out if the specified moveset is valid, and provide a suggestion ' 'on how to obtain it.') parser.add_argument('pokemon', metavar='POKEMON', type=unicode, help='Pokemon to check the moveset for') parser.add_argument('move', metavar='MOVE', type=unicode, nargs='*', help='Moves in the moveset') parser.add_argument('-l', '--level', metavar='LV', type=int, default=100, help='Level of the pokemon') parser.add_argument('-v', '--version', metavar='VER', type=unicode, default='x', help='Version to search in.') parser.add_argument('-q', '--quiet', action='store_true', default=False, help="Don't print out the result, only indicate it by the return " "value.") parser.add_argument('-V', '--exclude-version', metavar='VER', type=unicode, action='append', default=[], help='Versions to exclude (along with their ' 'counterparts, if any, e.g. `black` will also exclude White).') parser.add_argument('-P', '--exclude-pokemon', metavar='PKM', type=unicode, action='append', default=[], help='Pokemon to exclude (along with their families, e.g. `pichu` ' 'will also exclude Pikachu and Raichu).') parser.add_argument('-p', '--pomeg-glitch', action='store_true', default=False, help='Allow the Pomeg glitch, i.e. levelling up eggs in the 3rd ' "generation. (Note that the printouts won't mention the glitch " 'explicitly.)') parser.add_argument('-d', '--debug', action='append_const', const=1, default=[], help='Output timing and debugging information. Can be specified more ' 'than once for even more verbosity.') args = parser.parse_args(argv) args.debug = len(args.debug) if args.debug: print 'Connecting' if session is None: session = connect(engine_args={'echo': args.debug > 2}) if args.debug: print 'Parsing arguments' class BadArgs(ValueError): pass def _get_list(table, idents, name, query=None): if not idents: return [] result = [] if not query: query = session.query(table.identifier, table) query = query.filter(table.identifier.in_(idents)) query = query.order_by(table.id.desc()) ident_map = dict(query) for ident in idents: try: result.append(ident_map[ident]) except KeyError: print>>sys.stderr, ('%s %s not found. Please use ' 'the identifier.' % (name, ident)) raise BadArgs return result try: pokemon_query = session.query(tables.PokemonSpecies.identifier, tables.Pokemon) pokemon_query = pokemon_query.filter( tables.PokemonSpecies.id == tables.Pokemon.species_id) all_pokemon = _get_list(tables.PokemonSpecies, [args.pokemon] + args.exclude_pokemon, 'Pokemon', query=pokemon_query) all_versions = _get_list(tables.Version, [args.version] + args.exclude_version, 'Version') pokemon = all_pokemon[0] moves = _get_list(tables.Move, args.move, 'Move') version = all_versions[0] excl_versions = all_versions[1:] excl_pokemon = all_pokemon[1:] except BadArgs: return False if args.debug: print 'Starting search' result = verify_moveset(session, pokemon, version, moves, args.level, exclude_versions=excl_versions, exclude_pokemon=excl_pokemon, pomeg_glitch=args.pomeg_glitch, debug_level=args.debug) # XXX: Support more than one result if result: if args.debug: print '-' * 79 if not args.quiet: print_result(result, moves=moves) else: if args.debug: print ' ' * 79 if not args.quiet: print 'Illegal move combination.' return result if __name__ == '__main__': sys.exit(not main(sys.argv[1:]))