A Monster for Every Season: Summer 2
You can get A Monster for Every Season: Summer 2 now at Gumroad
Results 1 to 25 of 25
  1. - Top - End - #1
    Ettin in the Playground
     
    MindFlayer

    Join Date
    Mar 2015
    Gender
    Male

    Default D&D/Computer science question

    So as you will be able to work out.. I am not a computer scientist and probably not great at the whole algorithming thinking thing but a question came up in my last session that I thought was an interesting one (though probably trivial to better minds than my own).

    It is about class selection. Imagine we have a set of D&D players in a group.

    Each player has certain classes they are happy to play (ignore multiclassing for the moment), but the complicating factor is that this may depend on what other classes people will play.

    For example someone might only want to play warrior classes and not primary spellcasters. Others may only be happy playing a class if no other player is playing that class. Others may have a personal sense of 'optimal ranking' of classes and are happy to play anything as long as no one else has something significantly higher ranked...

    If we have a set of N inputs (where N is number of players), each of which is an M by M matrix (where M is the number of classes in the game) and the i,j entry in that matrix is a 1 if the player would not play class i if any other player is playing class j can we in a determinisitc way:

    a) easily establish if there exists an assignment of classes to players such that everyone would be happy
    b) calculate how many of these assignments there are
    c) have an efficient algorithm for finding a happy assignmnet
    d) have an efficient algorithm for finding all happy assignments
    e) establish bounds on how hard answering these questions will be in the worst case

  2. - Top - End - #2
    Dwarf in the Playground
    Join Date
    Jun 2020

    Default Re: D&D/Computer science question

    a) yes. Enumerating all possible class-player assignments is easy, as is checking if a particular assignment satisfies all preferences, so you can just check them all in order until you find one or you have checked them all.
    b) yes, see above. There are M^N possible assignments so party sizes above 12 or so might take a while, but if you have 12 players in a DND game class selection is just the beginning of your intractibility woes.
    c) not sure if you can do better than exponential on the number of players. My intuition says yes.
    d) ditto, but my intuition says no
    e) worst case upper bound for the brute force approach is at most M^N. Maybe you can do better, but for realistic values of M and N you probably don't need to.

  3. - Top - End - #3
    Troll in the Playground
     
    Kobold

    Join Date
    May 2009

    Default Re: D&D/Computer science question

    Without any a priori restrictions on what rules/preferences are to be respected, I don't see how you can guarantee any of those things.

    For instance, to take an extreme example, imagine Amy only wants to play a druid, and Bob doesn't want to have a druid in the party. Within the framework of the matrix you describe, it would be quite simple to express those preferences, but there's clearly no way to make both players happy.
    "None of us likes to be hated, none of us likes to be shunned. A natural result of these conditions is, that we consciously or unconsciously pay more attention to tuning our opinions to our neighbor’s pitch and preserving his approval than we do to examining the opinions searchingly and seeing to it that they are right and sound." - Mark Twain

  4. - Top - End - #4
    Dwarf in the Playground
     
    Kobold

    Join Date
    Aug 2020

    Default Re: D&D/Computer science question

    Well I see this less as algorithmic issue by economic one, you've got people with different preferences that wants to divide some "assets" between them. I know there was a nobel prize in this matter Alvin E. Roth and Lloyd S. Shapley “for the theory of stable allocations and the practice of market design”, I think that one, so it would be good to look for work by those two.

    I think usual approach is to have a "clearing house" i.e. every participants list there preferences in order up to bottom and a 3rd party match persons with the most preferred solution, usually you limit the participants to 3 but as you would have some ifs there it will be a little more problematic, so you could give them few options like
    1) Which class would you chose if you wouldn't care what other take,
    2) which class would you chose if 1 given class was in the party
    etc
    and for every question they would asses there preference and then you chose the person who give 1 the biggest score, and go from there.
    for having all items you would have to acquire all possibility of a party evaluated by the players and then chose the one that has most points,

    I think you could also could try some kind of auction, where for making a choice they need to sacrifice something or receive something, so in first auction you provide some higher prize if someone decide to chose class without knowing what other chose, this also should effectively maximize utility although in-game perk can be problematic for the game itself.

    2 think that, although obvious, it's good to mention:
    a) those preferences are not Transitive relation as such choosing one will change others most preferable preferences, so depending on point of start you will end with different maximum utility, as such I thing there is no other way then doing this by "hand" for every possibility.
    b) those preferences will change in time so don't spend to much time on those :)
    "By Google's own reckoning, 60% of the ads that are charged for are never seen by any human being – literally the majority of the industry's product is a figment of feverish machine imaginations." Pluralistic

    The bots are selling ads to bots which mostly bots are viewing, We really are living in XXI century.

  5. - Top - End - #5
    Ettin in the Playground
     
    MindFlayer

    Join Date
    Mar 2015
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by Hyoi View Post
    a) yes. Enumerating all possible class-player assignments is easy, as is checking if a particular assignment satisfies all preferences, so you can just check them all in order until you find one or you have checked them all.
    b) yes, see above. There are M^N possible assignments so party sizes above 12 or so might take a while, but if you have 12 players in a DND game class selection is just the beginning of your intractibility woes.
    c) not sure if you can do better than exponential on the number of players. My intuition says yes.
    d) ditto, but my intuition says no
    e) worst case upper bound for the brute force approach is at most M^N. Maybe you can do better, but for realistic values of M and N you probably don't need to.
    Heh. Good point. I kind of looked at this and thought "oh, this explodes quite quickly", but acually for something like D&D 5e with 13 classes and with a party size of about 5 people it really isn't totally problematic. Having said that most of this is about trying to think of a cleverer way of doing it, which I guess still holds from a fun perspective, if not a pracical requirement.

    Quote Originally Posted by veti View Post
    Without any a priori restrictions on what rules/preferences are to be respected, I don't see how you can guarantee any of those things.

    For instance, to take an extreme example, imagine Amy only wants to play a druid, and Bob doesn't want to have a druid in the party. Within the framework of the matrix you describe, it would be quite simple to express those preferences, but there's clearly no way to make both players happy.
    Yeah, sorry - I don't think I explained this well. This was what I was meaning by my point a) - is there an easy way to tell if there exists an appropriate solution.

    Quote Originally Posted by asda fasda View Post
    Well I see this less as algorithmic issue by economic one, you've got people with different preferences that wants to divide some "assets" between them. I know there was a nobel prize in this matter Alvin E. Roth and Lloyd S. Shapley “for the theory of stable allocations and the practice of market design”, I think that one, so it would be good to look for work by those two.

    I think usual approach is to have a "clearing house" i.e. every participants list there preferences in order up to bottom and a 3rd party match persons with the most preferred solution, usually you limit the participants to 3 but as you would have some ifs there it will be a little more problematic, so you could give them few options like
    1) Which class would you chose if you wouldn't care what other take,
    2) which class would you chose if 1 given class was in the party
    etc
    and for every question they would asses there preference and then you chose the person who give 1 the biggest score, and go from there.
    for having all items you would have to acquire all possibility of a party evaluated by the players and then chose the one that has most points,

    I think you could also could try some kind of auction, where for making a choice they need to sacrifice something or receive something, so in first auction you provide some higher prize if someone decide to chose class without knowing what other chose, this also should effectively maximize utility although in-game perk can be problematic for the game itself.

    2 think that, although obvious, it's good to mention:
    a) those preferences are not Transitive relation as such choosing one will change others most preferable preferences, so depending on point of start you will end with different maximum utility, as such I thing there is no other way then doing this by "hand" for every possibility.
    b) those preferences will change in time so don't spend to much time on those :)
    Oddly enough, this is an algorithm I am actually familliar with! I was going o say I was looking a it just the other day for a project, but thinking back it was about 4 years ago and now I realise just how much time has passed. The difference there is that there is additional information in the form of preferences but also that it is a matching algorithm (if I remember correcly) so the preference is two sided. I.e. you would need not just a reference of each player for the class but a preference by each class for which player would play it.

    I also think it would be difficult to adapt to the score where the score changes depending on what other people play. It also has the implicit assumption that the entities cannot be duplicaed - so whilst it can assign classes to players, it might run into problems if the table is fine with there being three Wizards (admittedly there is another problem with my initial suggestion in that it cant come with "two wizards are OK bu three is too many).

    Raising auction theory is an ineresting point though and I do think here could be someting very interesting there in terms of "character rights" or similar like auctions of spectra. If you were to give all players a resource pool to bid on classes and the winning player "owned" that class and he rights to permit or forbid someone from playing it it could be interesting. So if you wanted to play Class A but only if no one were to play Class B you would need the rights to both - or you could use the rights to keep something clear but negoiate for access to something else.

  6. - Top - End - #6
    Halfling in the Playground
     
    Lizardfolk

    Join Date
    Aug 2022
    Location
    the other Pacific coast
    Gender
    Male

    Default Re: D&D/Computer science question

    on the surface the problem does sound suspiciously similar to either some variant of "stable marriage", or an auction

    As you noted, there is no unambiguous way to establish the classes' "preference" for players
    (it's possible, but your players might disagree)

    You also explained some advantages of the auction approach, and it does make it game-like/fun in a way.
    I'd be cautions because is creates an incentive for players to compete in a zero-sum manner, which IMHO isn't ideal for character creation in D&D.

    Going back to the start,
    Given your preference input matrices, the easiest way to check if a solution exists, would be to take the element-wise FUNc of all input matrices.
    FUNC is the element-wise sum if 1 means "no", or element-wise product if 1 means "yes".
    To check a class-combo, you take a sub-matrix with only rows/columns of those classes, and if it's all "yes"s then, it's a "valid" combo.
    For example, any "yes"s on the diagonal will mean that all players are OK if everyone plays only that one class. (e.g. an all-rogue party)

    And here we get to the first limitation of this approach:
    it assumes a player's preference for a class is the same regardless of how many other people play it.

    Taking that into account would require a much more complicated scheme.

    -------

    I propose a small frame-challenge:

    If you're trying to go about it algorithmically, you can think of it like a variant of the LoL ban-list when selecting champions.
    Essentially this means that each player declares an ultimatum about what class combo they absolutely reject.

    If the picks don't clash, then all's fine. Everyone can pick their favourite class.

    If the ultimatums do clash with the picks, the environment isn't conducive to roleplaying. At that point an algorithm won't help you.
    It's better to employ good ol' negotiation to try and soften up at least some of the "ultimatums".

    Here you can go with the "auction" approach, for example by offering a player additional goodies for "violating" their personal "ultimatum".

    However, this in turn creates a perverse incentive for players to make the least reasonable ultimatum, in hopes that it gets violated and they get a reward.

  7. - Top - End - #7
    Barbarian in the Playground
    Join Date
    Jul 2007
    Gender
    Male

    Default Re: D&D/Computer science question

    It reminds me of an algorithm related to a game, which I forgot its name.
    In the game, a player secretly fills four empty slots with colored sticks. When someone else guesses, the player puts white or black flags, depending on whether the other player got things right.
    The computational approach to solving it that I read in Wikipedia years ago, is to start with a set of all possible configurations, than after each round exclude those that the black and white flags make impossible.
    I'm going to suggest a similar algorithm.

    Quote Originally Posted by MrStabby View Post
    a) easily establish if there exists an assignment of classes to players such that everyone would be happy
    b) calculate how many of these assignments there are
    c) have an efficient algorithm for finding a happy assignmnet
    d) have an efficient algorithm for finding all happy assignments
    e) establish bounds on how hard answering these questions will be in the worst case
    I will not bother testing it in code, but I think this algorithm will work:
    Order the players according to which players excludes the most options from other players. If it's not trivial to determine, you could sort it by which player has the least class options.

    In the order of the most exclusionary player to the most exclusionary, choose each class option, and make a list of possible choices for everyone according to it. If you can't seem to find one after checking all of that player's options, it means it's impossible to satisfy everyone. If you're just worried about finding a single happy assignment, you can just pick the first option that this algorithm returns.

    In practice, I think this algorithm will be quite fast. Here is how I estimate the efficiency of different cases (P = number of players, C = number of classes):
    a) Best case - it's the first arrangement that is chosen, so O(P), since you will need to pass through all the players once. Worst case is that there is no valid solution, but that somehow everyone has a ton of class options. So that will be something like O(C^P).
    b) This algorithm efficiency will be based on how many good arrangements there are. Theoretically, you could feed it with data that means that everyone if fine with playing anything, which will make it O(C^P).
    c) In practice, the algorithm I suggested would probably finish very quickly.
    d) Same as my assessment for b, except the same complexity also applies to the amount of memory.
    e) O(C^P). But the worst case isn't a very realistic possibility in this context, because if there are a ton of viable options the people on the table will realize it pretty quickly and won't bother typing the information into the algorithm.

    Edit: I have a feeling that an asymptotically more efficient algorithm could somehow be made by splitting the original input into groups, but that would be overkill.

    Edit 2: I forgot to include the sorting complexity in the O(stuff) estimations.
    Last edited by akma; 2022-09-27 at 07:31 AM.
    Madly In Science, an RPG in which you play mad scientists, you can get it for free.

    Spoiler: Some other things.
    Show
    A world behind the mirror (stand alone plane)
    (Wall) passer, a rogue variant
    My not realy extanded homebrewer signature

    Quote Originally Posted by Grinner View Post
    In a world ruled by small birds, mankind cannot help but wonder how this state of affairs came about.

  8. - Top - End - #8
    Dwarf in the Playground
     
    Kobold

    Join Date
    Aug 2020

    Default Re: D&D/Computer science question

    Quote Originally Posted by MrStabby View Post

    a) easily establish if there exists an assignment of classes to players such that everyone would be happy
    b) calculate how many of these assignments there are
    c) have an efficient algorithm for finding a happy assignmnet
    d) have an efficient algorithm for finding all happy assignments

    e) establish bounds on how hard answering these questions will be in the worst case
    Oh, I just notice something, you asked for algorithm to find "a happy" assignment, that will not be problematic, the algorithms mentioned by akma would be my go, or quite easy to use would be just make everyone to chose there class one by one, just let everyone to have 3 options to chose, so first guy chose a class without knowing what others prefer, and then after everyone has chosen he can either change the class or stay with it, so unless someone would actually try to be an <unconsidered person> this will easily find a solution in which everyone is happy, especially if they can discuss while making a choice

    but for me this is not an interesting problem this finding a solution where everyone is happy, the real challenge is to find an algorithm to identify the most favorable solution of all's. As it will be easy to find solution everyone are ok with, but there might be solutions that for someone is less then good, and generally on his own he would not chose that option, but for someone else the option would dream come true so his gain in "utility" would be much higher then the loss of the first person. For that clearing house I think work best because you do not start from the least favorable options but from most favorable
    "By Google's own reckoning, 60% of the ads that are charged for are never seen by any human being – literally the majority of the industry's product is a figment of feverish machine imaginations." Pluralistic

    The bots are selling ads to bots which mostly bots are viewing, We really are living in XXI century.

  9. - Top - End - #9
    Troll in the Playground
    Join Date
    Jan 2007

    Default Re: D&D/Computer science question

    Quote Originally Posted by akma View Post
    It reminds me of an algorithm related to a game, which I forgot its name.
    In the game, a player secretly fills four empty slots with colored sticks. When someone else guesses, the player puts white or black flags, depending on whether the other player got things right.
    The computational approach to solving it that I read in Wikipedia years ago, is to start with a set of all possible configurations, than after each round exclude those that the black and white flags make impossible.
    Not that relevant, but the game is called Mastermind.
    In a war it doesn't matter who's right, only who's left.

  10. - Top - End - #10
    Halfling in the Playground
     
    Lizardfolk

    Join Date
    Aug 2022
    Location
    the other Pacific coast
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by asda fasda View Post
    but for me this is not an interesting problem this finding a solution where everyone is happy, the real challenge is to find an algorithm to identify the most favorable solution of all's
    here we reach the limitations of human hardware, because for practical intents and purposes it's impossible to accurately assign a "favourableness" score to any given class-combination.

    We might do better with a sort of ranking (option A > option B) instead of a score, but I sincerely doubt such a ranking would be transitive.
    i.e. A>B, B>C, but C>A, which is intransitive, but absolutely a conceivable outcome when trying to find the middle ground between multiple subjective tastes.

  11. - Top - End - #11
    Orc in the Playground
     
    Kobold

    Join Date
    Aug 2019

    Default Re: D&D/Computer science question

    Your problem is probably computationally hard and the time required grows exponentially with the number of players.

    A program can easily take too long to complete.

  12. - Top - End - #12
    Titan in the Playground
     
    Tyndmyr's Avatar

    Join Date
    Aug 2009
    Location
    Maryland
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by Rydiro View Post
    Your problem is probably computationally hard and the time required grows exponentially with the number of players.

    A program can easily take too long to complete.
    For the size of data we are talking about here, it is not likely to be a problem.

    D&D groups generally have a modest number of players. I think the largest group I have ever been in was 14, and that was quite unwieldy and likely a poor decision.

    The number of potential classes is also finite and relatively modest in every RPG I have played, with all base classes expressible in a two digit number.

    There is a data entry hump if you want to get a lot of detail, but honestly, just having people enter their top three picks is probably sufficient. You should not generally have to care about the difference between someone's 11th choice and 12th choice pick.

    Assign points relative to priority picks, and find the combo with the maximum point value for the party. Even if you take the implicit limitation of "only one of each class", which is not really a hard limit, it's a pretty easy thing to code.

  13. - Top - End - #13
    Orc in the Playground
     
    Kobold

    Join Date
    Aug 2019

    Default Re: D&D/Computer science question

    Quote Originally Posted by Tyndmyr View Post
    For the size of data we are talking about here, it is not likely to be a problem.

    D&D groups generally have a modest number of players. I think the largest group I have ever been in was 14, and that was quite unwieldy and likely a poor decision.

    The number of potential classes is also finite and relatively modest in every RPG I have played, with all base classes expressible in a two digit number.

    There is a data entry hump if you want to get a lot of detail, but honestly, just having people enter their top three picks is probably sufficient. You should not generally have to care about the difference between someone's 11th choice and 12th choice pick.

    Assign points relative to priority picks, and find the combo with the maximum point value for the party. Even if you take the implicit limitation of "only one of each class", which is not really a hard limit, it's a pretty easy thing to code.
    When you go with ten players and ten available classes, you arrive at the order of 10^10 operations which will be a challenge for your computer.

    Sure, you can limit your search space, but then you might be missing out on solutions.
    Last edited by Rydiro; 2022-09-30 at 05:57 AM.

  14. - Top - End - #14
    Titan in the Playground
     
    Tyndmyr's Avatar

    Join Date
    Aug 2009
    Location
    Maryland
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by Rydiro View Post
    When you go with ten players and ten available classes, you arrive at the order of 10^10 operations which will be a challenge for your computer.
    Oh, not in the slightest. Further optimization to limit search space isn't even an issue if you're only checking 100 possibilities. Checking a search space of millions isn't a big of a deal now.

    So, yeah, you could optimize it, but it's probably going to take longer to type the info in than for the computer to process it.

  15. - Top - End - #15
    Dwarf in the Playground
     
    Kobold

    Join Date
    Aug 2020

    Default Re: D&D/Computer science question

    Quote Originally Posted by Rydiro View Post
    When you go with ten players and ten available classes, you arrive at the order of 10^10 operations which will be a challenge for your computer.

    Sure, you can limit your search space, but then you might be missing out on solutions.
    Quote Originally Posted by Tyndmyr View Post
    Oh, not in the slightest. Further optimization to limit search space isn't even an issue if you're only checking 100 possibilities. Checking a search space of millions isn't a big of a deal now.

    So, yeah, you could optimize it, but it's probably going to take longer to type the info in than for the computer to process it.

    10^10 will be 10.000.000.000 not 100, But I think Rydiro has improper calculated number of option, it's not 10^10, as it doesn't matter if you have ABC or BCA the team is the same, it should be calculated as 10 times 10^1 (10 different persons is making a choice of 1 of 10 possibilities) which is 100
    "By Google's own reckoning, 60% of the ads that are charged for are never seen by any human being – literally the majority of the industry's product is a figment of feverish machine imaginations." Pluralistic

    The bots are selling ads to bots which mostly bots are viewing, We really are living in XXI century.

  16. - Top - End - #16
    Barbarian in the Playground
    Join Date
    Jul 2007
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by Rydiro View Post
    When you go with ten players and ten available classes, you arrive at the order of 10^10 operations which will be a challenge for your computer.
    If you put a limit that no two players can have the same class, it is actually 10!, which is 3,628,800. If every player selects 3 choices, it will end up as 3^10, which is 59049. And if it truly was fine for each player to choose anything, you wouldn't bother running the code, as any choice would be viable.

    Regardless, even if it was 10^10, it wouldn't matter. Unless you'll turn this algorithm into some sort of server side public service, you would need to call it very rarely (once every few months or years), which means it wouldn't really matter if it even takes minutes to compute. The more strict the constraints are, the less options you'll need to iterate and the faster the program will run, and the looser they are, the less likely you will even need to bother typing them in.
    Madly In Science, an RPG in which you play mad scientists, you can get it for free.

    Spoiler: Some other things.
    Show
    A world behind the mirror (stand alone plane)
    (Wall) passer, a rogue variant
    My not realy extanded homebrewer signature

    Quote Originally Posted by Grinner View Post
    In a world ruled by small birds, mankind cannot help but wonder how this state of affairs came about.

  17. - Top - End - #17
    Orc in the Playground
    Join Date
    Sep 2009

    Default Re: D&D/Computer science question

    I don't think you'd need to brute force this. It's a fairly straightforward task of eliminating possibilities- sort of like a game of Soduku.

    1) Start with a simple 2-dimension bool array, where columns represent players and rows represent classes. Fill the array with 'true' for all values.

    2) Organize the preferences into 'rules', such as "Bob doesn't want to play a fighter" and "Sally only wants to play a caster class".

    3) Run through each rule and change all array values that would violate it to "false".

    4) Check to see if each player has at least one "true" in his columns.

    It'd really only be a challenge if you got really esoteric with some of your rules.

    Quote Originally Posted by Rydiro View Post
    When you go with ten players and ten available classes, you arrive at the order of 10^10 operations which will be a challenge for your computer.

    Sure, you can limit your search space, but then you might be missing out on solutions.
    10,000,000,000 is not a challenging number of operations for a modern computer. Your graphics card does more work than that every second if you're playing a AAA video game.
    Last edited by BloodSquirrel; 2022-10-13 at 10:48 PM.

  18. - Top - End - #18
    Ettin in the Playground
     
    Lord Torath's Avatar

    Join Date
    Aug 2011
    Location
    Sharangar's Revenge
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by BloodSquirrel View Post
    10,000,000,000 is not a challenging number of operations for a modern computer. Your graphics card does more work than that every second if you're playing a AAA video game.
    You've got a 10 GHz video card? Dang!
    Warhammer 40,000 Campaign Skirmish Game: Warpstrike
    My Spelljammer stuff (including an orbit tracker), 2E AD&D spreadsheet, and Vault of the Drow maps are available in my Dropbox. Feel free to use or not use it as you see fit!
    Thri-Kreen Ranger/Psionicist by me, based off of Rich's A Monster for Every Season

  19. - Top - End - #19
    Troll in the Playground
    Join Date
    Jan 2007

    Default Re: D&D/Computer science question

    Quote Originally Posted by Lord Torath View Post
    You've got a 10 GHz video card? Dang!
    A graphic card has typically many processors working in parallel. One of the reasons why they are useful for heavy computations.
    In a war it doesn't matter who's right, only who's left.

  20. - Top - End - #20
    Titan in the Playground
     
    tyckspoon's Avatar

    Join Date
    Nov 2007
    Location
    Indianapolis
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by Lord Torath View Post
    You've got a 10 GHz video card? Dang!
    One of the ways you can measure a computer system's capacity is in -flops, short for Fl(oating Point) Operations Per Second. Modern ones are currently counted in Tera on the SI prefixes. So yeah, 10 Giga is not an especially big ask.

  21. - Top - End - #21
    Bugbear in the Playground
    Join Date
    Mar 2022

    Default Re: D&D/Computer science question

    I know it’s less relevant because experienced players typically apply to your concept more.

    When I am introducing somebody to D&D, I ask them what kind of character they want to play: is it something from a movie you like, a favorite character from a television show, something you enjoyed in a video game?

    Present me that idea, and I tend to guide them to the correct classes for achieving that goal.

    Alternatively, I have a different series of questions to ask relevant to general roles and abilities commonly expressed in many different games:
    Do you want to? be able to take a lot of damage?
    Do you want to avoid damage?
    Do you like to blow stuff up?
    Do you want to have a lot of skills?
    Do you want to be sneaky?
    Do you want to hit hard?
    Do you want to take control of the enemy?
    Do you want to change the battlefield?
    Do you like spells?
    Do you like pets?

    Naturally the questions get more specific after I’ve narrowed down some of the initial preferences.

    Ok, that’s just looks like entirely the wrong direction… The reason I put this down:
    It helps to know a general direction to expect the average player will go based on their experience with the game and personal preference.
    Last edited by animorte; 2022-10-16 at 01:57 AM.

  22. - Top - End - #22
    Pixie in the Playground
     
    MindFlayer

    Join Date
    Nov 2022

    confused Re: D&D/Computer science question

    Quote Originally Posted by MrStabby View Post
    Others may have a personal sense of 'optimal ranking' of classes and are happy to play anything as long as no one else has something significantly higher ranked...
    Instead of making a program, how about not playing with these people?


  23. - Top - End - #23
    Orc in the Playground
     
    PaladinGuy

    Join Date
    Feb 2012
    Location
    Poland
    Gender
    Male

    Default Re: D&D/Computer science question

    I would just make a chart and give every player 10 points to assign in whatever way they want to the classes:

    _________| Class1 _|_Class2_|_Class3_|_Class4_|_Class5|
    Player A __|___ 10 __|__ 0 ___|__ 0 __|__ 0 __|__ 0 __|
    Player B __|____ 5 __|__ 3 ___|__ 2 __|__ 0 __|__ 0 __|
    Player C __|____ 2 __|__ 3 ___|__ 2 __|__ 2 __|__ 1 __|
    Player D __|____ 3 __|__ 5 ___|__ 1 __|__ 1 __|__ 0 __|
    Player E __|____ 0 __|__ 10 __|__ 0 __|__ 0 __|__ 0 __|

    Top choice: ____A__|__ E __|__ B/C __|__ C/D __|__ C __|

    From the example chart we could see not everyone will get their top choice. Especially Player D will not be happy.

    You can just go with the results or let the players reassign points (anonymously or after an open discussion).

    A way to encourage a "wider" spread of points could be to give some bonuses if you don't end up with your top pick, e.g. "you get X rerolls on attributes if you ended up with your Xth choice"

  24. - Top - End - #24
    Barbarian in the Playground
     
    GnomePirate

    Join Date
    Apr 2020
    Location
    United States
    Gender
    Male

    Default Re: D&D/Computer science question

    Quote Originally Posted by Bulhakov View Post
    I would just make a chart and give every player 10 points to assign in whatever way they want to the classes:

    _________| Class1 _|_Class2_|_Class3_|_Class4_|_Class5|
    Player A __|___ 10 __|__ 0 ___|__ 0 __|__ 0 __|__ 0 __|
    Player B __|____ 5 __|__ 3 ___|__ 2 __|__ 0 __|__ 0 __|
    Player C __|____ 2 __|__ 3 ___|__ 2 __|__ 2 __|__ 1 __|
    Player D __|____ 3 __|__ 5 ___|__ 1 __|__ 1 __|__ 0 __|
    Player E __|____ 0 __|__ 10 __|__ 0 __|__ 0 __|__ 0 __|

    Top choice: ____A__|__ E __|__ B/C __|__ C/D __|__ C __|

    From the example chart we could see not everyone will get their top choice. Especially Player D will not be happy.

    You can just go with the results or let the players reassign points (anonymously or after an open discussion).

    A way to encourage a "wider" spread of points could be to give some bonuses if you don't end up with your top pick, e.g. "you get X rerolls on attributes if you ended up with your Xth choice"
    I have a better solution. Have each player rank order their preferred class selection. The code then assigns a point value based on the rank order.

    For example:
    #1 preferred class = 5 pts
    #2 preferred class = 4 pts
    #3 preferred class = 3 pts
    #4 preferred class = 2 pts
    #5 preferred class = 1 pts

    The algorithm would the determine the combinations with the highest point values. That way 5 players each getting their #2 pic would be worth 20 points. A combination where 1 player gets #1, 2 players get #3, 1 gets #4, and 1 gets #5 would be worth 14 points.

    You could add modifiers for survivability. For example, combinations with at least one healer could have a +1 point.
    "Sure, Philosophers can say 'But how do we know the sun will rise tomorrow?' to which the correct response is 'Shut up nerd! Stop playing 3D chess against your own brain and find something real to worry about'."

    -ContraPoints

  25. - Top - End - #25
    Pixie in the Playground
     
    Kobold

    Join Date
    Nov 2022

    Default Re: D&D/Computer science question

    I don't want to spoil the fun, but this problem and others like it are constraint solving problems with lots of research behind them. You might be familiar with the term "SAT solvers", which work on finding values for boolean variables that SATisfy a set of logical expressions like (A and B or C, Not A or Not C). You would encode each person*class as a variable (A is "player 1 picks druid") and go to town. If you want to get crazy you can extend it to support preferences and other arbitrary constraints (search for linear programming). Then you could solve problems like "The party requires a healer and a striker and a utility, but you shouldn't have all mages and also Jeff is banned from playing anything that can cast 'conjure X' unless we really can't find a better solution"

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •