I disbelieve, but I'll talk to him at Intercon. For this game, it's a constraint-solving problem of something like 20 variables of various types, which is pretty horrific. Just dealing with matching up two different dimensions of factions is tricky enough to begin with. (Indeed, I'm needing to tweak the game as I cast, to match the players better.)
Still, it's interesting to think about what heuristics could be applied to ease the problem, and assist in the process -- there are probably some numerical approximations that would at least be better than doing it manually by spreadsheet. I'll have to see what Nat's done...
iam not surehwo nat did whathe did but i woudl immagine it is possible to fill outthe questonaire form teh perspective of each character, and then ahve software match that with each player's answers...
Conceptually, that's a good approach -- indeed, we've used that at times in the past. It's one motivation for the Emerald City Productions style of questionnaire, which is more quantitative than most.
But in practice, my questionnaires produce so much data that there is no such thing as a perfect fit, and even getting a good fit for a single player can be tricky. My guess is that it would have to be done with numerical approximations, and that's subject to various pathologies. Balancing the importance of the various questions is utterly crucial and quite difficult, and my suspicion is that most algorithms will be subject to getting stuck in local minima. So I can imagine a program that would *help* with the process -- essentially a spreadsheet for casting, that allows you to tweak and tune and see what happens when you change things. But it's difficult at best to do it well in a completely automated fashion.
Indeed, I think it's probably a bad idea anyway, because you learn a lot as you cast. I hit frequent cases of, "Oh, that player won't enjoy that character because of X", which usually indicates that X is actually a bug in the character, that needs to be fixed. Games change and mutate a *lot* as you attach faces to the characters. (At least, mine do: I pretty much always wind up customizing the game somewhat, and it's always for the better.)
From the algorithmic point of view — which is to say, paying attention to some mathematical abstraction, and ignoring how close it is to the real problem — I think you're okay. Edmonds's "blossom" algorithm (Canad. J. Math 1965) is a polynomial-time algoritm for solving the minimal-weight perfect-matching problem: given a score for how much "cognitive dissonance" each person would have playing each character (which could just be a distance between the high-dimensional points corresponding to their questionnaire responses, but more involved is ok too), the algorithm will produce the matching with the minimal total dissonance.
One glaring shortcoming for your real problem is that it can't take inter-assignment relationships into account: "Player A will be much happier playing role X if B plays Y than if C plays Y" is right out. (Mathematically, that would mean your objective function isn't linear in the matching.) I don't know how much you do that sort of thing.
There's some of that, although I don't think of it in quite that form. I think of it, rather, as a faction-matching problem.
I have clumps of players who want to play together, and in some cases players who really *don't* want to play together. (The latter often being the more important cases.) And I have "factions" in the game, groups that are relatively strongly associated with each other -- heavily overlapping in a good game, but each faction represents a natural grouping from the story POV. Just to make it worse, the factions are fuzzy on both sides, especially on the player side, since they are generally expressed unidirectionally. (That is, Player A says that he wants to be associated with B and C, and not with D; the others may say something quite different.)
Ideally, I want the player factions to align as best as I can with the character factions, so that players who want to be together overlap along some sort of factional lines (and will therefore naturally wind up interacting in the game), and those who don't much like each other will be off in different parts of the story.
This really is the hardest part of the problem, and the main thing that makes it tricky -- balancing the factional desires with the personal fits is pretty tricky, especially since the factions are fairly small: typically 3-7 on both sides of the equation, so my options are limited. So I'm trying to produce a best-fit not just on the individual player level, but for the groupings as well, introducing a sort of graph-solving problem on top of the individual fits...
Actually, I wish I lived closer so I could further complicate your life by being one of your players! AI in chess didn't make the papers when they could first do it, it made the papers when they could do it as well as a human! :D :D :D -- Dagonell
Actually, I wish I lived closer so I could further complicate your life by being one of your players!
Well, one of these years you should travel out East for Intercon New England. I think you'd enjoy it, and we have folks come from all over the world by now.
AI in chess didn't make the papers when they could first do it, it made the papers when they could do it as well as a human!
Just so. I could see a program doing a decent rough draft, but doing well enough for my tastes, especially in a game as messy as this one to cast -- that's really hard. I agonize over every compromise in the casting as it is; it would have to be a damned impressive program to be good enough for me.
One of the interesting realizations while casting the morning run today has been that casting this game is actually much harder than average, precisely because the players know the scenario so well. It means they have *much* stronger opinions about what they want, which is harder to work around. The evening run, which is tomorrow's project, should be somewhat easier, precisely because I have more players who are new to the story, so they're more flexible...
The classic turning point on this was when AI critic Hubert Dreyfuss, who'd written a paper titled "Why Computers Can't Play Chess", visited MIT and played their MacHackIV program (years prior to Apple monopolizing the "Mac" prefix for computer things). And lost badly.
MIT folk promptly wrote an underground, never officially published, tech report titled "Why Dreyfuss Can't Play Chess".
no subject
no subject
Still, it's interesting to think about what heuristics could be applied to ease the problem, and assist in the process -- there are probably some numerical approximations that would at least be better than doing it manually by spreadsheet. I'll have to see what Nat's done...
no subject
no subject
But in practice, my questionnaires produce so much data that there is no such thing as a perfect fit, and even getting a good fit for a single player can be tricky. My guess is that it would have to be done with numerical approximations, and that's subject to various pathologies. Balancing the importance of the various questions is utterly crucial and quite difficult, and my suspicion is that most algorithms will be subject to getting stuck in local minima. So I can imagine a program that would *help* with the process -- essentially a spreadsheet for casting, that allows you to tweak and tune and see what happens when you change things. But it's difficult at best to do it well in a completely automated fashion.
Indeed, I think it's probably a bad idea anyway, because you learn a lot as you cast. I hit frequent cases of, "Oh, that player won't enjoy that character because of X", which usually indicates that X is actually a bug in the character, that needs to be fixed. Games change and mutate a *lot* as you attach faces to the characters. (At least, mine do: I pretty much always wind up customizing the game somewhat, and it's always for the better.)
no subject
One glaring shortcoming for your real problem is that it can't take inter-assignment relationships into account: "Player A will be much happier playing role X if B plays Y than if C plays Y" is right out. (Mathematically, that would mean your objective function isn't linear in the matching.) I don't know how much you do that sort of thing.
no subject
I have clumps of players who want to play together, and in some cases players who really *don't* want to play together. (The latter often being the more important cases.) And I have "factions" in the game, groups that are relatively strongly associated with each other -- heavily overlapping in a good game, but each faction represents a natural grouping from the story POV. Just to make it worse, the factions are fuzzy on both sides, especially on the player side, since they are generally expressed unidirectionally. (That is, Player A says that he wants to be associated with B and C, and not with D; the others may say something quite different.)
Ideally, I want the player factions to align as best as I can with the character factions, so that players who want to be together overlap along some sort of factional lines (and will therefore naturally wind up interacting in the game), and those who don't much like each other will be off in different parts of the story.
This really is the hardest part of the problem, and the main thing that makes it tricky -- balancing the factional desires with the personal fits is pretty tricky, especially since the factions are fairly small: typically 3-7 on both sides of the equation, so my options are limited. So I'm trying to produce a best-fit not just on the individual player level, but for the groupings as well, introducing a sort of graph-solving problem on top of the individual fits...
no subject
-- Dagonell
no subject
Well, one of these years you should travel out East for Intercon New England. I think you'd enjoy it, and we have folks come from all over the world by now.
AI in chess didn't make the papers when they could first do it, it made the papers when they could do it as well as a human!
Just so. I could see a program doing a decent rough draft, but doing well enough for my tastes, especially in a game as messy as this one to cast -- that's really hard. I agonize over every compromise in the casting as it is; it would have to be a damned impressive program to be good enough for me.
One of the interesting realizations while casting the morning run today has been that casting this game is actually much harder than average, precisely because the players know the scenario so well. It means they have *much* stronger opinions about what they want, which is harder to work around. The evening run, which is tomorrow's project, should be somewhat easier, precisely because I have more players who are new to the story, so they're more flexible...
no subject
MIT folk promptly wrote an underground, never officially published, tech report titled "Why Dreyfuss Can't Play Chess".