PDA

View Full Version : Applying a Greedy algorithm to dnd



oxinabox
2009-08-27, 08:28 AM
So we all know waht a greedy algorithm (http://en.wikipedia.org/wiki/Greedy_algorithm), is right?
vaguely everyone who doesn't plan ahead ends up roughly using a greedy algorithm.
But nooone does it fully.
What would happen if you always took the best option each time you lvled?
With no planning for the future.

You'ld not be a Wizard.
You'ld end up with alot of 1 lvl dips (lets ignore the no more than 3 base class rule)
You'ld proably never qualify for a PrC, and if you did you might not take it.

How suboptimal would you be?
What would be thge progression?

I'm guessing statring with Barbarian, or Paladin maybe (though paladins multiclass may distort the algorithm).
Next maybe two lvls of Similar would be done for psywarrior (or fighter_.
but you'ld never toake more than 2 lvls of fighter (or Psywarrior) cos they is no class features at lvl 3.

Can we actually make a Greedy algorithm Solution to DnD?

If we can then does that imply you can Solve DnD?
Peoplke have solved, and tic-tac-toe and Draughts. (though obviosly not using a greedy algorithm)

Fenix_of_Doom
2009-08-27, 08:35 AM
my first thought was that you'd end up druid 20

Level 1 druid is about as good as you can get, spells AC, decent fighter yourself. level 2 is tricky, the question is is the second druid spell worth more than another class first level spells?
Probably not, which is to bad if you would be able to get druid 2 that druid 3 would also be an optimal choice.

an important question would be how ability scores are decided.

Irreverent Fool
2009-08-27, 08:56 AM
I think there are simply too many variables to apply a greedy algorithm to D&D classes in an unbiased fashion. Even any attempts would have to imply value in the abilities and make choice based on those values. "At each level, advance a level in a class which grants additional base attack bonus and/or a new class feature, choosing both if possible" would run into problems since there are many such classes which will fill that role. Let's not let that stop us form trying though.

Perhaps it could be based on the most prevalent abilities of monsters of the appropriate CR.

At higher levels, I think Tome of Battle classes would become more valuable.

obnoxious
sig

Doc Roc
2009-08-27, 08:57 AM
:: flinches :: Okay, greedy algorithm. Yes. That's an attack strategy used in cases where there are clear and quantifiable better options. Is D&D one of those cases? I think that's the first line of inquiry. I hold no, or Pun-Pun is the "solution" to D&D.

Douglas
2009-08-27, 08:58 AM
lets ignore the no more than 3 base class rule
That rule exists only in Neverwinter Nights, and possibly certain other computer games modeled after D&D rules. In actual D&D, there is no limit to how many different classes you can have levels in.

Irreverent Fool
2009-08-27, 09:04 AM
:: flinches :: Okay, greedy algorithm. Yes. That's an attack strategy used in cases where there are clear and quantifiable better options. Is D&D one of those cases? I think that's the first line of inquiry. I hold no, or Pun-Pun is the "solution" to D&D.

So much more eloquently put.


That rule exists only in Neverwinter Nights, and possibly certain other computer games modeled after D&D rules. In actual D&D, there is no limit to how many different classes you can have levels in.

NWN rules seem to get mistaken for D&D RAW a lot. Poor computers and their limited brains.

obnoxious
sig

pasko77
2009-08-27, 09:06 AM
my first thought was that you'd end up druid 20.


Mine too.
Or bard 10, sublime chord thereafter. Maybe with a dragon disciple dip.

Jack Zander
2009-08-27, 09:14 AM
It may be easier to do this if you take each class and apply the greedy algorithm to thier own class features. Take wizard up to 20, and decide each level which spells and feats the wizard will take, which are based on what the wizard needs at the time, and not at all based on future expectations.

Then you could do one for the fighter, TOB classes, etc. It may be a little more difficult to do it for devine casters, since they typically have all their spells to begin with. So they pretty much win.

Fenix_of_Doom
2009-08-27, 04:12 PM
Here is what I came up with assuming wisdom as only high casting stat:

Druid
Crusader
Warblade
Swordsage
Barbarian
Cleric
Knight
Psychic Warrior
Psychic Warrior
Fighter
Fighter
Rogue
Factotem
Druid
Druid
Druid
Druid
Druid
Druid
Druid

alternative: take swordsage 2 and then take swordsage all the way.

And there should probably be some classes I'm not really familiar with after the Factotem, D&D simply has to many classes.
In core you'd end up with Druid1/cleric1/barb1/fighter2/rogue1/druid14 which is a lot better.

oxinabox
2009-08-27, 06:23 PM
That rule exists only in Neverwinter Nights, and possibly certain other computer games modeled after D&D rules. In actual D&D, there is no limit to how many different classes you can have levels in.I';m never played NWN. I swear there is a rule that says "You may have 3 classes, but not four" but on rereading both th 3.0 and the 3.5 PHBs i found none. wow.

kjones
2009-08-27, 06:30 PM
Applying this algorithm would only give meaningful results if we had a meaningful comparator between classes. Is +1 BAB "better" than +2 to all saves? I don't think that's a question with an answer.

Gralamin
2009-08-27, 06:36 PM
I think, what we actually need is a goal. What type of character are we trying to make?

A skill monkey is likely to take 1st level in Rogue for the initial pool of skill points (Or Swordsage if you believe the x6 is not a mistake), and then go into Factotum and probably then go into Chameleon if possible.

A Warrior will probably take Fighter 2 (When the feats are the most useful), then go into Warblade for the vastly superior Maneuvers, moving into another class when necessary.

I could continue, but lets get a definite goal, and look at all the options level by level for it.


Applying this algorithm would only give meaningful results if we had a meaningful comparator between classes. Is +1 BAB "better" than +2 to all saves? I don't think that's a question with an answer.

Fixed by having a goal. If your a Warrior, and your job is "Hit things as often as possible, doing as much damage as possible" or some such, then you will want +1 BAB over +2 to all saves.

Ravens_cry
2009-08-27, 06:43 PM
I';m never played NWN. I swear there is a rule that says "You may have 3 classes, but not four" but on rereading both th 3.0 and the 3.5 PHBs i found none. wow.
Maybe it's just a common houserule. Like how the RAW in Monopoly say nothing happens on the Free Parking space, but most rule 0 it to give some kind of jackpot. Also, in my family at least, we never used the auction rules.

Leewei
2009-08-27, 08:06 PM
A possible solution would be Cleric-20. Select based on:

1. Number of spells known per level.
2. Spells usable per day / Desirability of spells.
3. Effective Caster Level (weigh this HEAVILY for ECL1+).
4. BAB.
5. Hit Die type.
6. Strong saves.
7. Armor and Weapon choice.
8. Other desirable class features (Domains, Animal Companions, Incantations, etc.)

Cleric-1 chosen for breadth and quantity of spells known, heavy armor and shield use, d8 HD, 3/4 BAB and two strong saves. This choice appears somewhat better than Druid-1 at a glance, however the Animal Companion might outweigh the armor and domain abilities.

From there, it gets interesting. If the domains chosen scale with level, the relatively weak 2nd Cleric level which increases BAB and two saves. Increasing ECL by 1 would probably seal the deal.

Once level 2 is obtained, 3rd level and higher are a no-brainer.

Skill and Feat selection become interesting. Concentration and Spellcraft are probably kept maxed out. Assign any additional available ranks based on Class skills utilizing high character stats.

Feats should be picked based on their immediate effect on the character. Combat Casting, Skill Focus (Concentration), and a whole slew of other feats that become worthless in the high levels will probably be gobbled up. Oddly enough, once a PC is a few levels higher, Power Attack and Cleave look to be likely choices.

kjones
2009-08-27, 08:46 PM
Fixed by having a goal. If your a Warrior, and your job is "Hit things as often as possible, doing as much damage as possible" or some such, then you will want +1 BAB over +2 to all saves.

Sure, but if you fail your save versus a save-or-die/suck, this will hinder your ability to deal damage to an extent.

That's what I'm trying to say - you can come up with dumb heuristics pretty easily, but creating a good heuristic is very hard. You have to be very specific.

ShneekeyTheLost
2009-08-27, 08:55 PM
The only thing a Greedy Algorithm would do is make it much more difficult to qualify for PrC's, because you wouldn't be 'planning ahead', and taking mostly worthless Feats at lower levels because they are prerequisites for higher levels.

In other words, you'd probably end up Wizard 20 and still win the game.

Milskidasith
2009-08-27, 08:59 PM
Wizard 20 isn't an optimal decision, simply because taking cleric 1, druid 1, warblade 1, etc. are all better than getting a few more first level spell slots with wizard 2.

Gralamin
2009-08-27, 09:00 PM
Sure, but if you fail your save versus a save-or-die/suck, this will hinder your ability to deal damage to an extent.

That's what I'm trying to say - you can come up with dumb heuristics pretty easily, but creating a good heuristic is very hard. You have to be very specific.

If we do it right, we'll only need one swing :smalltongue:

Irreverent Fool
2009-08-27, 09:04 PM
Maybe it's just a common houserule. Like how the RAW in Monopoly say nothing happens on the Free Parking space, but most rule 0 it to give some kind of jackpot. Also, in my family at least, we never used the auction rules.

I don't know how common it is. I'd never heard of it prior to this topic. Most of the super builds don't require that many base classes so I can think of no reason to limit multiclassing to 3 classes in D&D 3.5. But my group has equally silly houserules.

obnoxious
sig

ShneekeyTheLost
2009-08-27, 09:13 PM
Wizard 20 isn't an optimal decision, simply because taking cleric 1, druid 1, warblade 1, etc. are all better than getting a few more first level spell slots with wizard 2.

I disagree. Gaining additional Wizard spell slots is better because you can then cast more times per day. You are getting +1 BAB from Wiz2, so it isn't like any of the full BAB classes have anything to offer him.

So, vs any caster, you are getting +1 BAB that you would otherwise not get, and vs any non-caster, you are getting improved spellcasting.

SilverClawShift
2009-08-27, 09:30 PM
I don't know how common it is. I'd never heard of it prior to this topic.

Really? I've never known anyone who didn't play that way. Me and a friend got into an almost-board-flipping argument over wether or not it was the actual rule (after I pointed out that it technically wasn't).

FMArthur
2009-08-27, 09:33 PM
You would wind up in Beholder Mage for all 10 levels as soon as you could afford a casting of Polymorph Any Object on you. It is quantifiably the best class in D&D and is so at all of its levels.

Milskidasith
2009-08-27, 09:33 PM
I disagree. Gaining additional Wizard spell slots is better because you can then cast more times per day. You are getting +1 BAB from Wiz2, so it isn't like any of the full BAB classes have anything to offer him.

So, vs any caster, you are getting +1 BAB that you would otherwise not get, and vs any non-caster, you are getting improved spellcasting.

You can cast more times per day, yes. But you cannot cast more times per day than if you take a level in wizard and a level in cleric, and either way you still have level one spells. Getting around double the spell slots and two of what are essentially bonus feats beats out getting an extra spell slot, assuming level 1 spells are really good enough to win out in a greedy algorithm against warblades and such.

I'm not arguing that going full wizard would be bad. But with a greedy algorithm, getting a level in multiple casting classes gives you far more abilities than you get by taking levels in one class, and since nothing will get you level two spells, more level 1 spells is better at that specific level.

erikun
2009-08-27, 10:06 PM
I can see Cleric 20 or Druid 20 (possibly throwing in some prestige classes) to come out on top. Possibly a few levels of Barbarian thrown in at the beginning. Between spells, armor, and HP, the divine casters outweigh both fighters and most of the other primary casters. +1 BAB and an extra feat doesn't really match two domains and a half dozen spells, or comparing full armor and double HP to a wizard's spell selection.

ShneekeyTheLost
2009-08-27, 10:10 PM
You can cast more times per day, yes. But you cannot cast more times per day than if you take a level in wizard and a level in cleric, and either way you still have level one spells. Getting around double the spell slots and two of what are essentially bonus feats beats out getting an extra spell slot, assuming level 1 spells are really good enough to win out in a greedy algorithm against warblades and such.

I'm not arguing that going full wizard would be bad. But with a greedy algorithm, getting a level in multiple casting classes gives you far more abilities than you get by taking levels in one class, and since nothing will get you level two spells, more level 1 spells is better at that specific level.

But you get more spells PLUS a +1 BAB. So that beats out ALL melee classes cold.

I might see one level in Cleric, then one in Druid. But then the next level has to be one of the above classes, since a +1 in any of them will also net a +1 BAB.

From there, whichever one hit 2 goes all the way to 17. Probably Druid.

aje8
2009-08-27, 10:20 PM
Druid, go Planar Sheperd ASAP then go back to Druid for all remaining levels.

At level 1, Riding Dog with the Feral Animal companion feat= much much better than the Fighter. Take Grenbound Summoning as well and your summons will also be better than the Fighter. Make sure you're an Anthro-Bat because that's about as cheesy and powerful as you can get without venturing into Pun-Pun territory.

Oh and yes, you have to be Neutral Evil for this build. Alignment wasn't specified.

See...... Wizard doesn't actually outpace Druid till level 13 or even higher so going Wizard ever is probably wrong. In fact, Wizard one is a pretty horrible level.

Cleric isn't as good as Druid at lv.1 or for quite a while. In fact, I can't pinpoint a level where Cleric is better than Druid.

Curmudgeon
2009-08-27, 10:52 PM
(lets ignore the no more than 3 base class rule)
I've also never heard of this houserule before.

valadil
2009-08-27, 11:04 PM
I've seen players use greedy algorithms to build characters for one shot games. In particular I was going to run a level 2 one shot. A player wanted to be wizard/sorcerer. Nobody would ever player wizard/sorcerer, but it is advantageous over wizard 2 or sorcerer 2 in this situation. I told him he could play it, but I reserved the right to level up the characters midway through the dungeon.

Kroy
2009-08-28, 12:09 AM
I've also never heard of this houserule before.

Me either. I'm guessing Druid 1/Cleric 1/Druid 18.

oxinabox
2009-08-28, 12:49 AM
It wouild be very unblikely to ever take 2classes the smae in a row,
esp casters who don't leanr new spells.

therefore ruling out ever ending up with wizard 20.

ShneekeyTheLost
2009-08-28, 09:54 AM
It wouild be very unblikely to ever take 2classes the smae in a row,
esp casters who don't leanr new spells.

therefore ruling out ever ending up with wizard 20.

On levels they don't get a new spell level, they get +BAB, which makes them superior to any non-casting classes. Also, for example, at 6th level Wizard, a single 3rd level spell is worth more than some entire class's 20 level progression, much less a one-level dip.

Heliomance
2009-08-28, 10:02 AM
That rule exists only in Neverwinter Nights, and possibly certain other computer games modeled after D&D rules. In actual D&D, there is no limit to how many different classes you can have levels in.

Actually, there kinda is. Multiclassing penalties mean that it's possible to build a character that has a 100% experience penalty and can never thereafter level.

Kylarra
2009-08-28, 10:05 AM
Actually, there kinda is. Multiclassing penalties mean that it's possible to build a character that has a 100% experience penalty and can never thereafter level.
You could still chain say, good BAB base classes at 1-2 levels each without suffering penalties though, and then go into a prestige class or two when you get high enough. So for the purposes of this thought experiment, the limit doesn't really exist.

Tyndmyr
2009-08-28, 10:24 AM
It's rare to see a player ever actually take the multiclass penalty hit. Between favored classes, classes of similar level, prestige classes, and of course, being human, it's rather easy to avoid.

For an algorithm-driven selection, this might be more of a problem...but certainly not an unsolvable one, and clearly, getting a 100% xp penalty would never be the optimal choice.

Doc Roc
2009-08-28, 10:37 AM
The unsolvable part of this is that there is no good heuristic! What the heck, people? I don't go around suggesting we try and use a Runge-Kutta approach to D&D, or that perhaps we should apply macro-economic theory, or optimize based on parametric fit.

I don't think the term greedy algorithm makes any sense in the context of D&D except as a colloquialism for an internalized thought process common to optimizers. There's no real way to easily program a heuristic, or construct an invariant algorithm. There's a way of thinking, and I do approach D&D with the CO Mantra* in mind. But that's more than a little different from trying to discuss a viable attack based on the greedy strategy. :: sighs ::



* OM MANI MORE MORE MORE PADME

ScreamingDoom
2009-08-28, 10:57 AM
The unsolvable part of this is that there is no good heuristic!

This is the problem. However, what you could do is define fitness parameters. This would probably be good enough.

For instance, you could define "fitness" as max-damage per round, average-damage per round, max-HP per level, etc. If you wanted to be more sophisticated, you could use more than one with different priority ratings based on theoretical maximums at level (so the closer one gets to the theoretical maximum, the less "pull" a particular fitness attribute has in the decision process, leading to a more balanced character over all). If you wanted to get really complicated, you could even set up simulations of typical enemies a character will face at a particular level and base fitness on how fast they take down the enemy and how much damage they take in the process (faster is better, less damage is better).

Doc Roc
2009-08-28, 11:15 AM
That might work, but that begins to resemble genetic programming more than a strict read of the greedy algorithm, particularly because it is likely that to get good results we'd need to run through a good number of guided cycles. Still, a potentially interesting idea.

The issue is that a lot of abilities in D&D which are amazing have no naturally quantifiable value. Would we go through and weight each of them individually? I think we probably could get away with slicing out a lot of the trash before we even started doing this. As long as we stick to mid-range optimization... :: hums intently :: I mean, the issue is that I can't see a clean way to get a purely greedy attack to pick up on things like tashalatoran psychic warrior.

Tyndmyr
2009-08-28, 11:22 AM
Well, at it's basics, staying alive is a good goal. Damage, defence, all of this ideally helps your character continue to live.

Encounters can be models statistically, using the chances of each CR encounter given in the DMG, as well as randomly selecting monsters that would create the appropriate CR encounter. This will not perfectly model a human DM, obviously, but it should give you a rough idea of the challenges that need to be overcome.

Given equal challenges, a build that has a higher chance to survive is objectively better. The biggest challenge will be in determining how exactly everything affects your chances to survive, but while this is a huge task, it's at least theoretically solvable.

kamikasei
2009-08-28, 11:26 AM
That might work, but that begins to resemble genetic programming more than a strict read of the greedy algorithm, particularly because it is likely that to get good results we'd need to run through a good number of guided cycles. Still, a potentially interesting idea.

The greater problem is that this pretty much amounts to creating Skynet, but for D&D. I'm not one of those revenge-of-the-robots nuts, I don't think there's any reason why AI should be malevolent. But build it on a foundation of D&D, and it might start looking at all these low-CR humanoids running around and put two and two together...

Doc Roc
2009-08-28, 11:28 AM
The issue is that the greedy approach to algorithm design desires a lexical ordering for available options, at least along some axis. You may find it helpful to give it more than one axis of consideration, but that would increase complexity significantly.

Dixieboy
2009-08-28, 12:07 PM
The greater problem is that this pretty much amounts to creating Skynet, but for D&D. I'm not one of those revenge-of-the-robots nuts, I don't think there's any reason why AI should be malevolent. But build it on a foundation of D&D, and it might start looking at all these low-CR humanoids running around and put two and two together...
We have nothing to fear, at some point it's gonna stumble upon Elminster.

Tyndmyr
2009-08-28, 12:29 PM
Well, to use any algorithm at all, you need to be able to categorize and rank the options. Doing that alone is non-trivial. The ranking itself may need to be done genetically, because seriously, trying each option or combination out against all possible...or even all likely encounters is going to take a while.

If you stick to core, it's more doable, but it's still a rather difficult problem, and if you factor item purchases into it, it's even more insane.

HamsterOfTheGod
2009-08-29, 04:39 PM
Many have aluded to the difficulty of assigning a value to each level choice. But it can be intuitively seen that the best choice at each level, if not some generally good class like cleric, will not lead to an optimal solution. In part that is do to the fact that power does not increase linearly and equally across all classes and levels. But in general, in strategy games, the greedy algorithm will not work (for ex it does not work in chess) and this is by design.

CrazedPachyderm
2009-08-29, 05:42 PM
The first step one would need to take is to quantify the value of each class at each level. Why not try taking cues from the Class Construction Engine (http://www.dandwiki.com/wiki/Class_Construction_System_%28DnD_Guideline%29) (or the original pdf here (http://rumkin.com/reference/dnd/media/classconstruction.pdf))?

Yukitsu
2009-08-29, 06:25 PM
I apply this sort of logic to creation of martial type characters, because most are front stacked, and I don't particularly like most of the martial PRCs. However, I do this with the caveat that I only take classes that will benefit me in my particular style, as opposed to the absolute value of the abilities in isolation.

chiasaur11
2009-08-29, 06:46 PM
We have nothing to fear, at some point it's gonna stumble upon Elminster.

So it'll go after Greenwood first?

That barely gives us an extra week.

Indon
2009-08-29, 06:46 PM
I disagree. Gaining additional Wizard spell slots is better because you can then cast more times per day. You are getting +1 BAB from Wiz2, so it isn't like any of the full BAB classes have anything to offer him.

So, vs any caster, you are getting +1 BAB that you would otherwise not get, and vs any non-caster, you are getting improved spellcasting.

Unless you weigh Scribe Scroll very heavily, you'll never even take Wizard 1. You'll take Sorceror 1 instead.

pingcode20
2009-08-29, 07:22 PM
Also, note that 1st levels are very highly weighted compared to non-1st levels - every time you take a first level, you scoop up an extra +2 to all good saves.

Monk 1 would not be an unreasonable first choice for a greedy algorithm - +2 to all saves, two free feats, flurry of blows, wisdom to AC, and bonus unarmed strike damage.

Monk 2 might be a strong candidate for a second level - +1 to all saves, +1 BAB, Bonus Feat, and Evasion. But I can't see it going much further than that.

Cleric 1 would be a next good choice - +2 to Fort and Will, Spells, Undead Turning, and two Domain Powers.

Et cetera, et cetera. Greedy Algorithms don't think ahead. If spells are the most heavily weighted factor, then spellcasters keep picking up more spellcasting classes, spontaneous before prepared, until they run out of choices. If BAB is more highly weighted, you end up picking up lots of combat classes with a smattering of spellcasting.

Indon
2009-08-29, 08:31 PM
The Monk may not be a good greedy choice either - bear in mind that the greedy algorithm is going to try to wear the best armor possible at the lowest level possible, meaning classes that can do so (fighter) have an advantage, and classes that can not do so (monk, druid) have a disadvantage there.

Ditto weapons, though I guess a greedy algorithm might find the Elf to be a good choice there to get weapon proficiencies.

Godskook
2009-08-29, 08:55 PM
I think the original poster's question is better phrased as 'when playing a game at level X when you won't level, period, what would your build be?', and then applying it from L1 to L20, using the previous build as a required base.