1. ## 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. ## 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. ## 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.

4. ## 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 :)

5. ## Re: D&D/Computer science question

Originally Posted by Hyoi
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.

Originally Posted by veti
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.

Originally Posted by asda fasda
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. ## 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. ## 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.

Originally Posted by MrStabby
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.

8. ## Re: D&D/Computer science question

Originally Posted by MrStabby

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

9. ## Re: D&D/Computer science question

Originally Posted by akma
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.

10. ## Re: D&D/Computer science question

Originally Posted by asda fasda
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. ## 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. ## Re: D&D/Computer science question

Originally Posted by Rydiro
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. ## Re: D&D/Computer science question

Originally Posted by Tyndmyr
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.

14. ## Re: D&D/Computer science question

Originally Posted by Rydiro
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. ## Re: D&D/Computer science question

Originally Posted by Rydiro
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.
Originally Posted by Tyndmyr
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

16. ## Re: D&D/Computer science question

Originally Posted by Rydiro
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.

17. ## 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.

Originally Posted by Rydiro
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.

18. ## Re: D&D/Computer science question

Originally Posted by BloodSquirrel
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!

19. ## Re: D&D/Computer science question

Originally Posted by Lord Torath
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.

20. ## Re: D&D/Computer science question

Originally Posted by Lord Torath
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. ## 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.

22. ## Re: D&D/Computer science question

Originally Posted by MrStabby
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. ## 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. ## Re: D&D/Computer science question

Originally Posted by Bulhakov
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.

25. ## 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
•