Worker placement in Orleans board game/combinations

Question

I am trying to program the board game Orleans. I am planning on making a computer player that plays randomly at first. The part of the game that I'm struggling to code elegantly at the moment has to do with the planning of worker placement. I'll try to explain it in a way that doesn't require familiarity with the game. A player can have workers of 6 different types (and 1 wildcard type), and each action space requires some combination of those 6 types to activate. Each action space requires 1-3 workers of different types. I want to develop a list of all the possible action spaces that can be triggered given a player's current collection of workers, and the requirements of each action space. This is with a view to then randomly select from these later.

I have a Player class, which has a dictionary that stores the action spaces a player has access to, and a list of workers that the player has access to. The list of actions can expand as the game progresses, and the number and type of workers can also change.

class Player:

    def __init__(self):
        self.workers = ["boatman", "farmer", "craftsman", "trader"]
        self.action_spaces = {'farmhouse': ActionSpace(["boatman", "craftsman"]),
                              'village': ActionSpace(["boatman", "craftsman"]),
                              'university': ActionSpace(["farmer", "craftsman", "trader"]),
                              'castle': ActionSpace(["boatman", "farmer", "trader"]),
                              'monastery': ActionSpace(["scholar", "trader"]),
                              'wagon': ActionSpace(["farmer", "trader", "knight"]),
                              'ship': ActionSpace(["boatman", "farmer", "knight"]),
                              'guildhall': ActionSpace(["farmer", "craftsman", "knight"]),
                              'scriptorium': ActionSpace(["knight", "scholar"]),
                              'townhall': ActionSpace([])}

And an action space class that codes the requirements and current workers placed on each action space.

class ActionSpace:

    def __init__(self, requirements):
        self.requirements = requirements
        self.placed_workers = []

Then I have some very tortuous code that uses that information to produce a list of the possible combinations of action spaces that can be triggered with the player's workers.

def plan_worker_placement(player):
    # loop through all action spaces that a player owns and make a list of tuples recording the requirements for each action space. I convert it to a set because I will find the intersection with this set and another later
    reqs_of_available_spaces = set([tuple(v.requirements) for k, v in player.action_spaces.items()])
    # get a list of workers
    workers = [w for w in player.workers]
    combos_of_workers = []
    # get all possible combinations of workers for groups of size 1-3 workers
    for r in range(1, 4):
        combos_of_workers.extend(set(combinations(workers, r)))
    # narrow down list to those action spaces that are playable given the player's workers
    reqs_of_playable_spaces = reqs_of_available_spaces.intersection(combos_of_workers)
    # convert back to list of lists
    reqs_of_playable_spaces = [list(c) for c in reqs_of_playable_spaces]
    combos_of_reqs_of_playable_spaces = []
    # can activate 1 or more action space
    for r in range(1, len(reqs_of_playable_spaces) + 1):
        combos_of_reqs_of_playable_spaces.extend(combinations(reqs_of_playable_spaces, r))
        combos_of_reqs_of_playable_spaces = [list(c) for c in combos_of_reqs_of_playable_spaces]
    valid_combos_of_reqs_of_playable_spaces = []
    for combo in combos_of_reqs_of_playable_spaces:
        # flatten out the list
        flat_combo = [item for sublist in combo for item in sublist]
        # check whether player has enough workers of each type to play that combination of action spaces
        if check_valid(flat_combo, followers):
            # if the player has enough workers add that combo of action spaces to the list of possibles
            valid_combos_of_reqs_of_playable_spaces.append(combo)
    valid_combos_of_reqs_of_playable_spaces = [tuple(c) for c in valid_combos_of_reqs_of_playable_spaces]
    return convert_reqs_to_spaces(valid_combos_of_reqs_of_playable_spaces)

# function to convert from a list of requirements back to the name of the action space
def convert_reqs_to_spaces(reqs):
    converter = {tuple(sorted(["boatman", "craftsman"])): 'village',
                 tuple(sorted(["boatman", "farmer", "trader"])): 'castle',
                 tuple(sorted(["farmer", "trader", "knight"])): 'wagon',
                 tuple(sorted(["boatman", "farmer", "knight"])): 'ship',
                 tuple(sorted(["farmer", "craftsman", "knight"])): 'guildhall',
                 tuple(sorted(["knight", "scholar"])): 'scriptorium',
                 tuple(sorted(["scholar", "trader"])): 'monastery',
                 tuple(sorted(["farmer", "craftsman", "trader"])): 'university',
                 tuple(sorted(["boatman", "craftsman"])): 'farmhouse'}
    spaces = []
    for s in reqs:
        spaces.append([converter[tuple(sorted(req))] for req in s])
    return spaces

# function to check to whether a player has enough of each type of worker to activate a given set of action space requirements
def check_valid(flat, followers):
    c1, c2 = Counter(flat), Counter(followers)
    for k, n in c1.items():
        if n > c2[k]:
            return False
    return True

I don't like the way I am having to convert from lists to sets and back to lists again. It seems there should be a much cleaner way of doing things.

Answer 1

The way you explain it in plain english is similar to a simple, cleaner way to do it in the code :

I want to develop a list of all the possible action spaces

With some conditional restriction. This is a complete rewrite. Enumeration can be done through recursive algorithm :

def enumerate_action_space(actions, available_workers):
    accumulator = [[]] # It is always possible to do nothing
    actions_copy = actions.copy()
    for a in actions.keys():
        # Conditionals go here. The more you restrict your space, the faster the enumeration
        if not set(actions[a].required_workers).issubset(set(available_workers)):
            continue
        # Select the action, then enumerate all possible following actions for that one
        current_action = actions_copy.pop(a)
        workers = set(available_workers) - set(current_action.required_workers)
        l = enumerate_action_space(actions_copy, workers)
        # Collect results
        l2 = [action + [a] for action in l] 
        accumulator.extend(l2)
    return accumulator


actions = {
        'key1': ActionSpace('A',['a']), # First is name, second the worker requirements
        'key2': ActionSpace('B', ['b']),
        'key3': ActionSpace('C', ['a', 'b'])
        }

print (enumerate_action_space(actions, ['a', 'b'])) # Two workers available
# -> [[], [ActionSpace('A')], [ActionSpace('B'), ActionSpace('A')], [ActionSpace('C')], [ActionSpace('B')]] #

You can add more conditions to restrict more the action space, based on arbitrary parameters.

Note that I don't push back elements as I remove them. This is to avoid enumerating both ['A', 'B'] and ['B', 'A'].