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.