From ab82a735cd57dd20236135447b774643faf7e1c1 Mon Sep 17 00:00:00 2001
From: Philip Paquette <pcpaquette@gmail.com>
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 +-
2 files changed, 190 insertions(+), 172 deletions(-)
(limited to 'diplomacy/engine')
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)
--
cgit v1.2.3