## Dynamic Programming Task - really confusing

This is the place for queries that don't fit in any of the other categories.

### Dynamic Programming Task - really confusing

The Dark Eye is a popular fantasy role-playing game, the German equivalent of Dungeons and Dragons. In this system a character has a number of attributes and talents. Each talent has several attributes associated with it, and to make a talent check the player rolls a d20 (a 20-sided die) for each associated attribute. Each time a roll result exceeds the attribute score, the difference between roll and attribute is added up. If this difference total (the excess ) is greater than the talent value, the check fails.

Example: The climb talent has the attributes courage, agility and strength associated with it. The climbing character has courage/agility/strength scores of 12, 13 and 12 respectively, and 7 ranks in climb. The player rolls a d20 three times, getting 13, 16 and 5. He exceeds his ability score by 1, 3 and 0 respectively for an excess of 1 + 3 = 4 ≤ 7 ranks, so the check succeeds.

Your first task for this tutorial is to write a function that takes as input a list of attribute scores associated with a talent as well as the talent ranks, and returns the probability that the test succeeds. Your algorithm must work efficiently for lists of arbitrary length.

Hint: First write a function that computes the probability distribution for the excess. This can be done efficiently using dynamic programming.

What does this mean? I solved the knapsack problem without any major issues (both 0/1 and unbounded), but I have no idea what to do with this?

The smallest problem to solve first would be rank 1 with a single attribute of say 12 (using the example above) - the probability of passing would be 12/20 right? then rank 2 would be 13/20 then rank 3 would be 14/20? But how do I add a second die?

Am I on the right track? I feel like I might be misunderstanding the actual game rules.
Last edited by stranac on Mon May 12, 2014 12:50 pm, edited 1 time in total.
Reason: First post lock.
lukasaurus

Posts: 2
Joined: Mon May 12, 2014 11:56 am

### Re: Dynamic Programming Task - really confusing

The smallest problem to solve first would be rank 1 with a single attribute of say 12 (using the example above) - the probability of passing would be 12/20 right?

Not quite. The "talent check" (and also later confusingly referred to as a "test") uses <= when comparing the excesses to the rank. So with rank 1 and an attribute of 12, you can also roll a 13 and the "talent check" will succeed: the excess is (13 - 12) which is <= to the rank of 1.

But how do I add a second die?

Why do you need a second die? There is no difference between rolling 4 dice one time each and rolling 1 die four times.
7stud

Posts: 106
Joined: Wed Apr 02, 2014 2:36 am

### Re: Dynamic Programming Task - really confusing

I do need to add a second die because that's the principle behind Dynamic Programming. Solve the smaller subsets first and then store their results and reuse them later

So rank 0 with an attribute of 12 results in a 12/20 chance, rank 1 with an attribute of 12 results in a 13/20 chance etc, all the way up to the rank we want. Then we have to do it with a second die, keeping in mind the possibility of the first die. But that's where I get stuck. And then we have to do it with a third die. Finally, if we store the results in a m*n 2d array, the answer should be in the m,n position in the array as we build it up to the answer we want.
lukasaurus

Posts: 2
Joined: Mon May 12, 2014 11:56 am

### Re: Dynamic Programming Task - really confusing

I do need to add a second die because that's the principle behind Dynamic Programming.

I don't know anything about that, but you can do this:

Code: Select all
`import randomdef die20():    return random.randint(1, 20)die1 = die20die2 = die20print die1(), die2()`
7stud

Posts: 106
Joined: Wed Apr 02, 2014 2:36 am