From ab82a735cd57dd20236135447b774643faf7e1c1 Mon Sep 17 00:00:00 2001 From: Philip Paquette Date: Tue, 5 Mar 2019 16:01:53 -0500 Subject: Refactored get_all_possible_orders for 2.5x speed improvement - Returning all locations at once - Removed 'loc' argument from method - Map has pre-computed attribute dest_with_coats --- diplomacy/engine/game.py | 348 ++++++++++++++++++++++--------------------- diplomacy/engine/map.py | 14 +- diplomacy/tests/test_game.py | 2 +- diplomacy/utils/export.py | 3 +- 4 files changed, 193 insertions(+), 174 deletions(-) diff --git a/diplomacy/engine/game.py b/diplomacy/engine/game.py index 2c845e6..7bf11a2 100644 --- a/diplomacy/engine/game.py +++ b/diplomacy/engine/game.py @@ -1474,196 +1474,204 @@ class Game(Jsonable): self.rebuild_hash() self.build_caches() - def get_all_possible_orders(self, loc=None): - """ Computes a list of all possible orders for a unit in a given location - :param loc: Optional. The location where to get a list of orders (must include coasts) - If not provided, returns a list of all possible orders for all locations - :return: A list of orders for the unit, if there is a unit at location, or a list of possible - orders for all locations if no locations are provided. + def get_all_possible_orders(self): + """ Computes a list of all possible orders for all locations + :return: A dictionary with locations as keys, and their respective list of possible orders as values """ - # pylint: disable=too-many-branches - # No locations, building a dict with all locations - if not loc: - all_possible_orders = {} - for map_loc in self.map.locs: - map_loc = map_loc.upper() - all_possible_orders[map_loc] = self.get_all_possible_orders(map_loc) - return all_possible_orders - - def remove_duplicates(list_with_dup): - """ Shorthand functions to remove duplicates """ - seen = set() - return [item for item in list_with_dup if not (item in seen or seen.add(item))] - - # Otherwise finding the possible orders at that specific location - possible_orders = [] - is_dislodged = False - unit = None - unit_power = None - - # If there are coasts possible, recursively adding the coasts first, then adding the loc orders - if '/' not in loc: - for loc_with_coast in [coast for coast in self.map.find_coasts(loc) if '/' in coast]: - possible_orders += self.get_all_possible_orders(loc_with_coast) - - # Determining if there is a unit at loc - # Dislodged unit have precedence over regular unit in Retreat phase - for power in self.powers.values(): - dislodged = [u for u in power.retreats if u[2:] == loc.upper()] - regular = [u for u in power.units if u[2:] == loc.upper()] - if dislodged: - is_dislodged = True - unit = dislodged[0] - unit_power = power - break - elif regular and not is_dislodged: - unit = regular[0] - unit_power = power - if self.phase_type != 'R': - break - - # No unit found, checking if location is a home - if unit is None: - if self.phase_type != 'A': - return remove_duplicates(possible_orders) - for power in self.powers.values(): - if loc[:3] in power.homes and 'BUILD_ANY' not in self.rules: - unit_power = power - break - if loc[:3] in power.centers and 'BUILD_ANY' in self.rules: - unit_power = power - break + # pylint: disable=too-many-branches,too-many-nested-blocks + possible_orders = {loc.upper(): set() for loc in self.map.locs} - # Not a home, and no units - if not unit_power: - return remove_duplicates(possible_orders) + # Game is completed + if self.get_current_phase() == 'COMPLETED': + return {loc: list(possible_orders[loc]) for loc in possible_orders} - # Determining if we can build or need to remove units - build_count = 0 if self.phase_type != 'A' else len(unit_power.centers) - len(unit_power.units) + # Building a dict of (unit, is_dislodged, retreat_list, duplicate) for each power + # duplicate is to indicate that the real unit has a coast, and that was added a duplicate unit without the coast + unit_dict = {} + for power in self.powers.values(): - # Determining unit type and unit location - unit_type = unit[0] if unit else '' - unit_loc = unit[2:] if unit else '' + # Regular units + for unit in power.units: + unit_loc = unit[2:] + unit_dict[unit_loc] = (unit, False, [], False) + if '/' in unit_loc: + unit_dict[unit_loc[:3]] = (unit, False, [], True) + + # Dislodged units + for unit, retreat_list in power.retreats.items(): + unit_loc = unit[2:] + unit_dict['*' + unit_loc] = (unit, True, retreat_list, False) + + # Building a list of build counts and build_sites + build_counts = {power_name: len(power.centers) - len(power.units) if self.phase_type == 'A' else 0 + for power_name, power in self.powers.items()} + build_sites = {power_name: self._build_sites(power) if self.phase_type == 'A' else [] + for power_name, power in self.powers.items()} # Movement phase if self.phase_type == 'M': - # Computing coasts for dest - dest_1_hops = [l.upper() for l in self.map.abut_list(unit_loc, incl_no_coast=True)] - dest_with_coasts = [self.map.find_coasts(dest) for dest in dest_1_hops] - dest_with_coasts = {val for sublist in dest_with_coasts for val in sublist} + + # Building a list of units and homes for each power + power_units = {power_name: power.units[:] for power_name, power in self.powers.items()} # Hold - possible_orders += ['{} H'.format(unit)] - - # Move (Regular) and Support (Hold) - for dest in dest_with_coasts: - if self._abuts(unit_type, unit_loc, '-', dest): - possible_orders += ['{} - {}'.format(unit, dest)] - if self._abuts(unit_type, unit_loc, 'S', dest): - if self._unit_owner('A {}'.format(dest)): - possible_orders += ['{} S A {}'.format(unit, dest)] - elif self._unit_owner('F {}'.format(dest)): - possible_orders += ['{} S F {}'.format(unit, dest)] - - # Move Via Convoy - for dest in self._get_convoy_destinations(unit_type, unit_loc): - possible_orders += ['{} - {} VIA'.format(unit, dest)] - - # Support (Move) - for dest in dest_with_coasts: - - # Computing src of move (both from adjacent provinces and possible convoys) - # We can't support a unit that needs us to convoy it to its destination - abut_srcs = self.map.abut_list(dest, incl_no_coast=True) - convoy_srcs = self._get_convoy_destinations('A', dest, exclude_convoy_locs=[unit_loc]) - - # Computing coasts for source - src_with_coasts = [self.map.find_coasts(src) for src in abut_srcs + convoy_srcs] - src_with_coasts = {val for sublist in src_with_coasts for val in sublist} - - for src in src_with_coasts: - - # Checking if there is a unit on the src location - if self._unit_owner('A {}'.format(src)): - src_unit_type = 'A' - elif self._unit_owner('F {}'.format(src)): - src_unit_type = 'F' - else: - continue + for power_name in self.powers: + for unit in power_units[power_name]: + order = unit + ' H' + possible_orders[unit[2:]].add(order) + if '/' in unit: + possible_orders[unit[2:5]].add(order) + + # Move, Support, Convoy + for power_name in self.powers: + for unit in power_units[power_name]: + unit_type, unit_loc = unit[0], unit[2:] + unit_on_coast = '/' in unit_loc + for dest in self.map.dest_with_coasts[unit_loc]: + + # Move (Regular) + if self._abuts(unit_type, unit_loc, '-', dest): + order = unit + ' - ' + dest + possible_orders[unit_loc].add(order) + if unit_on_coast: + possible_orders[unit_loc[:3]].add(order) + + # Support (Hold) + if self._abuts(unit_type, unit_loc, 'S', dest): + if dest in unit_dict: + other_unit, _, _, duplicate = unit_dict[dest] + if not duplicate: + order = unit + ' S ' + other_unit[0] + ' ' + dest + possible_orders[unit_loc].add(order) + if unit_on_coast: + possible_orders[unit_loc[:3]].add(order) + + # Support (Move) + # Computing src of move (both from adjacent provinces and possible convoys) + # We can't support a unit that needs us to convoy it to its destination + abut_srcs = self.map.abut_list(dest, incl_no_coast=True) + convoy_srcs = self._get_convoy_destinations('A', dest, exclude_convoy_locs=[unit_loc]) + + # Computing coasts for source + src_with_coasts = [self.map.find_coasts(src) for src in abut_srcs + convoy_srcs] + src_with_coasts = {val for sublist in src_with_coasts for val in sublist} + + for src in src_with_coasts: + if src not in unit_dict: + continue + src_unit, _, _, duplicate = unit_dict[src] + if duplicate: + continue - # Checking if src unit can move to dest (through adj or convoy), and that we can support it - # Only armies can move through convoy - if src[:3] != unit_loc[:3] \ - and self._abuts(unit_type, unit_loc, 'S', dest) \ - and ((src in convoy_srcs and src_unit_type == 'A') - or self._abuts(src_unit_type, src, '-', dest)): + # Checking if src unit can move to dest (through adj or convoy), and that we can support it + # Only armies can move through convoy + if src[:3] != unit_loc[:3] \ + and self._abuts(unit_type, unit_loc, 'S', dest) \ + and ((src in convoy_srcs and src_unit[0] == 'A') + or self._abuts(src_unit[0], src, '-', dest)): + + # Adding with coast + order = unit + ' S ' + src_unit[0] + ' ' + src + ' - ' + dest + possible_orders[unit_loc].add(order) + if unit_on_coast: + possible_orders[unit_loc[:3]].add(order) + + # Adding without coasts + if '/' in dest: + order = unit + ' S ' + src_unit[0] + ' ' + src + ' - ' + dest[:3] + possible_orders[unit_loc].add(order) + if unit_on_coast: + possible_orders[unit_loc[:3]].add(order) + + # Move Via Convoy + for dest in self._get_convoy_destinations(unit_type, unit_loc): + order = unit + ' - ' + dest + ' VIA' + possible_orders[unit_loc].add(order) + + # Convoy + if unit_type == 'F': + convoy_srcs = self._get_convoy_destinations(unit_type, unit_loc, unit_is_convoyer=True) + for src in convoy_srcs: + + # Making sure there is an army at the source location + if src not in unit_dict: + continue + src_unit, _, _, _ = unit_dict[src] + if src_unit[0] != 'A': + continue - # Adding with coast - possible_orders += ['{} S {} {} - {}'.format(unit, src_unit_type, src, dest)] + # Checking where the src unit can actually go + convoy_dests = self._get_convoy_destinations('A', src, unit_is_convoyer=False) - # Adding without coasts - if '/' in dest: - possible_orders += ['{} S {} {} - {}'.format(unit, src_unit_type, src, dest[:3])] + # Adding them as possible moves + for dest in convoy_dests: + if self._has_convoy_path('A', src, dest, convoying_loc=unit_loc): + order = unit + ' C A ' + src + ' - ' + dest + possible_orders[unit_loc].add(order) - # Convoy - if unit_type == 'F': - convoy_srcs = self._get_convoy_destinations(unit_type, unit_loc, unit_is_convoyer=True) - for src in convoy_srcs: + # Retreat phase + if self.phase_type == 'R': - # Checking if there is a unit on the src location - if unit_type == 'F' and self._unit_owner('A {}'.format(src)): - src_unit_type = 'A' - else: - continue + # Finding all dislodged units + for unit_loc, (unit, is_dislodged, retreat_list, duplicate) in unit_dict.items(): + if not is_dislodged or duplicate: + continue + unit_loc = unit_loc[1:] # Removing the leading * + unit_on_coast = '/' in unit_loc + + # Disband + order = unit + ' D' + possible_orders[unit_loc].add(order) + if unit_on_coast: + possible_orders[unit_loc[:3]].add(order) - # Checking where the src unit can actually go - convoy_dests = self._get_convoy_destinations(src_unit_type, src, unit_is_convoyer=False) + # Retreat + for dest in retreat_list: + if dest[:3] not in unit_dict: + order = unit + ' R ' + dest + possible_orders[unit_loc].add(order) + if unit_on_coast: + possible_orders[unit_loc[:3]].add(order) + + # Adjustment phase + if self.phase_type == 'A': - # Adding them as possible moves - for dest in convoy_dests: - if self._has_convoy_path(src_unit_type, src, dest, convoying_loc=unit_loc): - possible_orders += ['{} C {} {} - {}'.format(unit, src_unit_type, src, dest)] + # Building a list of units for each power + power_units = {power_name: power.units[:] for power_name, power in self.powers.items()} - # Retreat phase - if self.phase_type == 'R': + for power_name in self.powers: + power_build_count = build_counts[power_name] + power_build_sites = build_sites[power_name] - # Disband - if is_dislodged: - possible_orders += ['{} D'.format(unit)] + # Disband + if power_build_count < 0: + for unit in power_units[power_name]: + unit_on_coast = '/' in unit + order = unit + ' D' + possible_orders[unit[2:]].add(order) + if unit_on_coast: + possible_orders[unit[2:5]].add(order) - # Retreat - if is_dislodged: - retreat_locs = unit_power.retreats[unit] - for dest in retreat_locs: - dest = dest.upper() - if not self._unit_owner('A {}'.format(dest[:3]), coast_required=0) \ - and not self._unit_owner('F {}'.format(dest[:3]), coast_required=0): - possible_orders += ['{} R {}'.format(unit, dest)] + # Build + if power_build_count > 0: + for site in power_build_sites: + for loc in self.map.find_coasts(site): + unit_on_coast = '/' in loc + if self.map.is_valid_unit('A ' + loc): + possible_orders[loc].add('A ' + loc + ' B') + if self.map.is_valid_unit('F ' + loc): + possible_orders[loc].add('F ' + loc + ' B') + if unit_on_coast: + possible_orders[loc[:3]].add('F ' + loc + ' B') + + # Waive + if power_build_count > 0: + for site in power_build_sites: + for loc in self.map.find_coasts(site): + possible_orders[loc].add('WAIVE') - # Adjustment Phase - if self.phase_type == 'A': - build_sites = self._build_sites(unit_power) - - # Disband - if build_count < 0 and unit: - possible_orders += ['{} D'.format(unit)] - - # Build Army / Fleet - if build_count > 0 \ - and loc[:3] in build_sites \ - and not self._unit_owner('A ' + loc[:3], coast_required=0) \ - and not self._unit_owner('F ' + loc[:3], coast_required=0): - if self.map.is_valid_unit('A {}'.format(loc)): - possible_orders += ['A {} B'.format(loc)] - if self.map.is_valid_unit('F {}'.format(loc)): - possible_orders += ['F {} B'.format(loc)] - - # Waive - if build_count > 0: - possible_orders += ['WAIVE'] - - # Removing duplicate - return remove_duplicates(possible_orders) + # Returning + return {loc: list(possible_orders[loc]) for loc in possible_orders} # ==================================================================== # Private Interface - CONVOYS Methods diff --git a/diplomacy/engine/map.py b/diplomacy/engine/map.py index acbc089..2730168 100644 --- a/diplomacy/engine/map.py +++ b/diplomacy/engine/map.py @@ -44,6 +44,8 @@ class Map(): e.g. {'RUSSIA': ['MOS', 'SEV', 'STP', 'WAR'], 'FRANCE': ['BRE', 'MAR', 'PAR'], ... } - convoy_paths: Contains a list of all possible convoys paths bucketed by number of fleets format: {nb of fleets: [(START_LOC, {FLEET LOC}, {DEST LOCS})]} + - dest_with_coasts: Contains a dictionary of locs with all destinations (incl coasts) that can be reached + e.g. {'PAR': ['BRE', 'PIC', 'BUR', ...], ...} - dummies: Indicates the list of powers that are dummies e.g. ['FRANCE', 'ITALY'] - error: Contains a list of errors that the map generated @@ -112,7 +114,8 @@ class Map(): __slots__ = ['name', 'first_year', 'victory', 'phase', 'validated', 'flow_sign', 'root_map', 'abuts_cache', 'homes', 'loc_name', 'loc_type', 'loc_abut', 'loc_coasts', 'own_word', 'abbrev', 'centers', 'units', 'pow_name', 'rules', 'files', 'powers', 'scs', 'owns', 'inhabits', 'flow', 'dummies', 'locs', 'error', - 'seq', 'phase_abbrev', 'unclear', 'unit_names', 'keywords', 'aliases', 'convoy_paths'] + 'seq', 'phase_abbrev', 'unclear', 'unit_names', 'keywords', 'aliases', 'convoy_paths', + 'dest_with_coasts'] def __new__(cls, name='standard', use_cache=True): """ New function - Retrieving object from cache if possible @@ -140,7 +143,7 @@ class Map(): self.rules, self.files, self.powers, self.scs, self.owns, self.inhabits = [], [], [], [], [], [] self.flow, self.dummies, self.locs = [], [], [] self.error, self.seq = [], [] - self.phase_abbrev, self.unclear = {}, {} + self.phase_abbrev, self.unclear, self.dest_with_coasts = {}, {}, {} self.unit_names = {'A': 'ARMY', 'F': 'FLEET'} self.keywords, self.aliases = KEYWORDS.copy(), ALIASES.copy() self.load() @@ -682,6 +685,13 @@ class Map(): query_tuple = (unit_type, unit_loc, order_type, other_loc) self.abuts_cache[query_tuple] = self._abuts(*query_tuple) + # Building dest_with_coasts + for loc in self.locs: + loc = loc.upper() + dest_1_hops = [l.upper() for l in self.abut_list(loc, incl_no_coast=True)] + dest_with_coasts = [self.find_coasts(dest) for dest in dest_1_hops] + self.dest_with_coasts[loc] = list({val for sublist in dest_with_coasts for val in sublist}) + def add_homes(self, power, homes, reinit): """ Add new homes (and deletes previous homes if reinit) :param power: Name of power (e.g. ITALY) diff --git a/diplomacy/tests/test_game.py b/diplomacy/tests/test_game.py index 20994c8..cec1df7 100644 --- a/diplomacy/tests/test_game.py +++ b/diplomacy/tests/test_game.py @@ -518,7 +518,7 @@ def test_set_current_phase(): game.clear_cache() assert game.get_current_phase() == 'W1901A' assert game.phase_type == 'A' - assert 'A PAR B' in game.get_all_possible_orders('PAR') + assert 'A PAR B' in game.get_all_possible_orders()['PAR'] def test_process_game(): """ Tests - Process game """ diff --git a/diplomacy/utils/export.py b/diplomacy/utils/export.py index 459313d..3a03de1 100644 --- a/diplomacy/utils/export.py +++ b/diplomacy/utils/export.py @@ -118,13 +118,14 @@ def is_valid_saved_game(saved_game): # Validating orders orders = game.get_orders() + possible_orders = game.get_all_possible_orders() for power_name in orders: if sorted(orders[power_name]) != sorted(current_phase['orders'][power_name]): return False if 'NO_CHECK' not in game.rules: for order in orders[power_name]: loc = order.split()[1] - if order not in game.get_all_possible_orders(loc): + if order not in possible_orders[loc]: return False # Validating resulting state -- cgit v1.2.3