Is this solvable without a computer? Probably not. But is it solvable?

Qwinn

New member
Joined
Jun 13, 2013
Messages
3
This isn't a math problem I've been assigned in school, but it IS a problem that I really want to solve and I'll probably need math to solve it. Here's the premise. A 14-player game is played using 32 different classes, but each player doesn't have a chance to pick their class; instead, the 14-person group chooses a pool of 25 classes out of the 32 total, and at the start of the game, 14 of these 25 classes are randomly distributed, one to each person. (Which sounds kind of complicated, but I promise this a real question I'm asking for a real reason.) The game is meant to be played with every man for himself, but the playerbase of this game has found that the game is both easier and more fun if you partner up with one of the other classes during the game and work together. So, it's extremely strategically disadvantageous for someone to not partner up, and each person can only partner up with one other class. On top of this, not every partnership is equal - you could theoretically make a list of all 496 matchups that ranks them from best to worst, or from 1 to 10 (there's probably a fair deal of 0-valued matchups that are basically useless). Imagine I have this kind of list and have assigned each matchup a numberical value. The question is this:

Which 25 classes should I choose to create a pool with in order for the 14 players to have the highest probability of all getting valuable match-ups?

There's obviously a really really large number of combinations involved, so I can't exactly brute-force it. I'm not sure if I can brute-force a computer to do it for me, either. What I think I'd need to do is create a program like this: first, assign the numerical values of each 2-person matchup, then have the computer generate every possible 2-person combination, then have the computer assign a numerical value to each combination based on the added values of all involved match-ups (which would be hard; each class could potentially partner up with any other class, so the computer would have to figure out on its own how to calculate the value of the 14-person set using the numerical values of the highest-value match-ups for each person), then calculate every possible 25-person pool and calculate each of these pools' potential 14-person calculations, then go back, look at the numerical values it had assigned for each 14-person matchup, and make a fraction for each pool of the number of high-value 14-person sets over the number of low-value 14-person sets, maybe? Then whichever pool has the highest value fraction is the 25 classes I'd want to pool? That would be a lot of numbers to calculate. A completely ridiculous amount, really, I don't even want to begin to imagine.

So, there's two problems. One, if there's any way I can make that process more efficient, I'd like to know. Two, I don't know anything about computers at all. How would I even begin to build this? Am I even going about this the right way at all? I know barely anything about combinatorics, just the concept of weighting different combinations based on the value of the items in the set is beyond me and I'm not even sure if it's still the same field of math. All I've formally learned in school is the "calculate total number of permutations, calculate total number of combinations" stuff. But this question is really bugging me, so any help you could offer at me at all would be really helpful. Thanks! Also, sorry if I put this in the wrong section; I wasn't sure where else it'd go.
 
Got a headache just reading your post...you owe me 2 Tylenols!

What d'heck are "classes"?

Even if we could figure this out, it would be next to impossible to explain it
to you, since you state you know nothing about computers and combinations.

Can you use a simpler case, like 3 teams and 7 "classes", and demonstrate
how this intriguing game is played? S'got to be more interesting than
Subhotosh's cricket game :rolleyes:

Haha, I was having a hard time keeping track of it myself. Uh, classes within the concept of the game are like different modes of gameplay that each require different strategies to win, I guess - within the context of the problem they're just combinable objects that make up the largest set. Also, for what it's worth, any information you can give me about where to start with combinations or computer-based math would be greatly appreciated, I'll try to build from there. I think I have an intro to C++ book lying around somewhere that I'll be able to go look for later, so I'll see if I can come back and rephrase my question into whatever computer science lingo it is I'm looking for.

Also, I worked through what the problem would look like with smaller sets, this one using colors. The premise would be something like: "You're painting your room by mixing two colors together, but you don't get to choose which two colors you end up using. Instead, you choose three colors from a list of five, and then two of the chosen three are mixed at random. You have strong preferences about your colors, so you've made a list for yourself rating each color you could possibly generate from 1 to 4 stars. Which three colors should you choose to have the highest chance of getting a color you like?"

So then, the largest set, the single colors, is: {Red, Yellow, Blue, White, Black}.

And, your ratings for each of the potential combined colors is as follows:

Red+Yellow: Orange: 1
Red+Blue: Purple: 4
Red+White: Pink: 3
Red+Black: Dark Red: 1

Yellow+Red: Orange: 1
Yellow+Blue: Green: 4
Yellow+White: Light Yellow: 2
Yellow+Black: Dark Yellow: 1

Blue+Red: Purple: 4
Blue+Yellow: Green: 4
Blue+White: Light Blue: 1
Blue+Black: Dark Blue: 1

White+Red: Pink: 3
White+Yellow: Light Yellow: 2
White+Blue: Light Blue: 1
White+Black: Grey: 4

Black+Red: Dark Red: 1
Black+Yellow: Dark Yellow: 1
Black+Blue: Dark Blue: 1
Black+White: Grey: 4

And from there, the possible combined colors each 3-color group could make:

Red+Yellow+Blue:
RY 1
Rbl 4
Ybl 4
TOTAL: 9

Red+White+Blue:
RW 3
Rbl 4
Wbl 1
TOTAL: 8

Red+Black+Blue:
RB 1
Rbl 4
Bbl 1
TOTAL: 7

Red+Yellow+White:
RY 1
RW 4
YW 2
TOTAL: 7

Red+Yellow+Black:
RY: 1
RB: 1
YB: 1
TOTAL: 3

Red+White+Black:
RW: 4
RB: 1
WB: 4
TOTAL: 9

Yellow+Blue+White:
Ybl 4
YW 2
Wbl 1
TOTAL: 7

Yellow+Blue+Black:
Ybl 4
YB 1
Bbl 1
TOTAL: 6

Yellow+White+Black:
YW 2
YB 1
WB 4
TOTAL: 7

Blue+White+Black:
Wbl 1
Bbl 1
WB 4
TOTAL: 6

So I guess from there you can surmise that your best options are picking {Red, Yellow, Blue} or {Red, White, Black}, and your worst option is {Red, Yellow, Black}, unless there's some human error in there somewhere, which is quite possible. (Although, in this smaller problem, all of the "good choices" are ones that have the 1 in 3 potential of giving you a 1-star color - in a larger problem it would probably be more useful to choose not the 3-color group that produces the most 4-star colors, but the one that's least likely to produce a 1-star color, in order to avoid that chance of complete disappointment. So although in this problem I judged the "value" of each 3-color group by adding up the sum of each color combination it produces, in the larger problem I would probably rather judge the "value" by creating a fraction of (potential combinations valued over median value x)/(potential combinations valued under median value x), or something like that. So what I'd want to do from there is figure out a way to do that same brute-force combinatorial stuff faster, with the aid of a computer. Does that help? I hope that I'm making a little more sense now, I wasn't sure how to make the problem any less complicated while still preserving the main part I had questions about.


 
I am not sure that I can answer this because I am not sure that I understand it. Although formally there is no difference, this seems to me to be a programming problem more than a math problem.

You have 32 classes, classes 1 through 32. Each pair of classes has a value. It makes no difference to the analysis (as I understand it) how you assign values to a class. Furthermore, pair 6, 5 has the same value as pair 5, 6, correct?

OK the number of possible pairs is \(\displaystyle \dbinom{32}{2} = \dfrac{32!}{2! * (32 - 2)!} = \dfrac{32!}{2 * 30!} = \dfrac{32 * 31}{2} = 496.\)

I'd set up a table showing the values corresponding to the various pairs. So for example a row of the table might say 6, 19, 3, which would mean that the pair 6 and 19 has a value of 3. You would not need to do this in real time; it can be done once and stored. Now things get really confusing for me. Are the players selecting the 25 classes or are you doing it quasi-randomly subject to a constraint yet to be determined?

I suspect you want to constrain future choices as the players make initial choices. You have not said what the process is for the players to make choices. What would be fairly simple is for each player in order to choose one class. That gives 14 classes. Then the computer picks 11 more. How might you have the computer do that? Choose one of the classes already chosen, class A, and choose a previously unchosen class has the highest score when combined with A. This would require 18 compares. Computer can do that lickety split. Put A and this high ranking companion into the pool. Now repeat the process with the remaining classes that were chosen by the players. Total number of compares required would be 171 - 36 = 135, quite doable. If you want to get fancy you can put in a randomizing element for ties or for choosing which of the 14 classes chosen by the players is to be matched up next or for choosing which player chooses next or for all of them.

Your players will have picked 14 out of the 32 for inclusion into the pool, and the computer will have picked out 11 for inclusion in the pool that will avoid the worst scores.

I don't think you need to learn C++ for this. Denis will probably suggest Basic. My son keeps telling me to learn Python.
 
Last edited:
I think I get the thing you're suggesting I do - but unfortunately, I think the method of selection involved is going to be a lot messier to sort through.

There's exactly one choice made by humans in the process: one person chooses 25 different classes out of the 32 classes available. Which 14 of the chosen 25 end up in the game itself is completely random. (Within the context of the game, it's so that everyone involved has an idea of which classes the other people MIGHT have, but without being fully sure which classes are actually in the game. It's important to guess what class the other 13 people have on your own, so the randomized pool provides you with your list of guesses. That's not really important for the problem, though, ignore this.) So, let me see if I can run through the steps involved that the computer does:

Human portion:
1. Working with a set of 32, select 25 classes. We want to know which 25 classes will give us the most favorable results from the randomized portion. With all else equal, humans could create 3365856 different initial groups for the game to work with ((32!/7!)/25!, I think).

Game-generated portion:
1. Working with a set of 25, select 14 classes at random. So, for any given set of 25, the computer will generate one of 4457400 groups (if my math is correct: (25!/11!)/14!).

I'm not really good at explaining things, but this is what I think a computer evaluating the worth of each human-generated group would have to do:

For any one of the 3365856 sets of 25: Evaluate all 4457400 groups of 14.

For any one of the 4457400 groups of 14: Evaluate how the the players should pair up in 7 groups of 2 in order to rate the group of 14 as highly as possible - in other words:
For any one of the 4457400 groups of 14: Evaluate every different way the players could pair up. (The problem involved here is: if you have 14 people, how many different ways could they pair up? I'm not actually entirely sure how to solve this one. I think it should be 135135 ways: in other words, 13 * 11 * 9 * 7 * 5 * 3, or (14!)/(27*7!).)

For any one of the 135135 ways to pair up any one of the groups of 14: Refer back to the set of values each one of these 2-person groups has been assigned and add all 7 of them up, giving the total group some sort of numerical value. Do this to all 135135 and then select the one that has the highest value. Now we're back to the 4457400 groups of 14, and each of them has some given numerical value.

For all of the 4457400 groups of 14: Calculate a value based on the following: (Number of valuable groups) divided by (Number of nonvaluable groups.) Or, (Number of groups above numerical value X) divided by (Number of groups below numerical value X). This gives you a fraction that represents the larger unit you're working with: the set of 25. Right?

That's for one set of 25. So, the computer would have to do that 3365855 more times.

That's my dilemma here: the numbers are too big. Just multiplying 3365856*4457400*135135 gives me over 1018 things for the computer to run through - and if I understand anything from my cursory run-through of the Wikipedia page on processor speed, it's not actually going to be able to do that in any real time frame.

So, you're right about assigning values to each of the 496 possible pairs, and storing that somewhere for the program to check back on - but the way the computer needs to check back on those values is a lot messier. I'm sorry that I'm not explaining it very well, maybe it would work better if I designed some sort of flowchart? But right now I think you just have the place where human input happens mixed up, you think that it's at the point where the 14-class set is chosen but it's actually where the 25-class set is chosen.

By the way, I was told Basic is inefficient, which is why I was going for C++ instead. The problem is pretty inherently inefficient already. If I could maybe solve a problem about half the size as this one for now (i.e. instead of 32-unit set --> 25-unit set --> 14-unit set, something like 16-unit set --> 12-unit set --> 6-unit set?) I would be satisfied.

(How do you do mathematical notations on this forum, by the way? Does it support LaTeX syntax? Are you using some sort of MathML creation software and pasting the code here? I don't have much experience doing math online.)
 
Top