Probability of rolling n dice to match another set of dice, d, given r rolls (like yahtzee)

Question

(Note: I will eventually code this, but i'm primarily interested in the math behind it)

I'm trying to create a function in Java to calculate the probability of getting a desired outcome from n rolled 6 sided dice given r "yahtzee style" tries. By yahtzee style i mean if you roll a result which matches 2 of the desired outcome, you can just reroll the remaining.

So we could have a function like this, if you are a programmer like myself: double probDice(int n = numDice, int[] d = desiredSet, int r = numRolls).

So if we wanted the pobability of getting {1,3,3} with 3 dice and 4 rolls, we would say that the probability = probDice(3, {1,3,3}, 4);

I know the probability of getting 1,3,3 on the first try. It's a distinct value out of all possible values, in this case 1/6^3 = 1/216. However, that 1 could be in 3 positions so it's 3/216 or 1/72.

What if we don't get it on the first shot, we only have 1/72 chance afterall. We now have to consider what happens when one dice matches, when two match, or when none match. The reason for that is because if one matches, then we would only want to reroll the two that do not match. So then we would recurse and say:

" We have 1/72 of getting it on first shot, plus we have (num of one matching sets)(prob of matching two given 3 rolls left) plus we have (num of two matching sets)(prob of matching one given 3 rolls left) plus we have (num of no matching sets) * (prob of matching 3 given 3 rolls left)"

In coding this is just recursion, we would basically call the same function with one less in rolls left, however many dice we want to reroll, and something to match... Ex:

      1match, reroll 2        2match, reroll 1      0 match, reroll 3

prob = 1/72 + num1MatchesprobDice(2, {?,?}, 3) + num2MatchesprobDice(1, {?}, 3) + num0Matches*probDice(3, {1,3,3}, 3);

The problem here is I have no idea what to put in {?,?}. This sort of breaks my algorithm. Originally I thought I could just replace {1,3,3} with {A,B,B} since i just want to know what the probability it is of getting a unique val and 2 duplicates. BUT, that doesn't quite work since I need a particular {A,B,B}, not just any! So I have to divide by something.

It looks like I could adjust my function by instead of taking {1,3,3}, it could take some other input which denoted how many unique elements, how many duplicates, etc or just the string "A,B,B" which has all this information.

I'm still stuck though on how to recurse... if i match 1 and need to reroll 2, do I pass {B,B} or {A,B}. I don't know which one I matched!

I think I may be going about this the wrong way... again, the problem I wish to solve is finding the probability of getting a unique dice roll given some number of rolls where you can reroll parts of the result.

I think this can be described purely mathematically, and then I can just automate that in the code, but I can't quite find the right way to represent it. Any advice on how I would calculate this on paper? (So I can then use my coding knowledge to translate it to code).

Maybe an example... odds of getting {1,3,3} given 3 rolls (like yahtzee). I think a Transition Matrix (Markov) might be the answer here, but I don't know how to accommodate for "unique" desired values. I want {1,3,3} specifically, not just {A,B,B}, since what if I wanted the sum to be 7? A + B + B != 7 for all rolls.

Any help is appreciated, this is just for fun... trying to implement a "Yahtzee solver" to get the best possible score based on game trees and probabilities of getting rolls. If you think stackoverflow might get me a better answer, ill move this there. Thanks very much!

EDIT: I wanted to be a little more clear with my description of this function as it's very important for a correct mathematical implementation.

1. You roll n dice and get a result, r_1. We have 3 rolls, this was the first
2. You have a pattern you wish to match with your dice, say {1,3,3}.
3. Your first roll, r_1, yields {2,3,4}. We can easily find that we got one of our threes in {1,3,3}, but the {2,4} do not match the remaining {1,3}. So we must reroll them. This step in the algorithm simply finds HOW MANY dice we need to reroll
4. Use ONE reroll to reroll all dice you want. Just like in yahtzee, you can reroll one, two, three, four, or five of the dice but it only takes one of your "rolls" (You get 3 in yahtzee).
5. We roll two dice, leaving the 3, and this time get {6,1}. Great! We got a 1, so now we only need to reroll the 6. This was our second roll, one left.
6. We roll the one dice and it's a 5. Drat, we didn't get the last 3 we needed.

The thing here is, there are ways to abstract the desired value {1,3,3} from it's concrete value. Consider the question: What are the odds of getting {1,3,3} from 3 dice? The probability is the same as {A,B,B}, since {2,6,6} is the same probability as {1,3,3}. So you can just do (3!/2!) / 6^3 which is the permutations of {A,B,B} with replication/duplication, divided by total possibilities. We didn't even care it was {1,3,3}, just the form {A,B,B}. But the tricky part is, what about the NEXT roll? Do we need to consider every possible roll from here? This is expensive. Or can we be smart and just consider the cases we can go from here and add up the partial probabilities?

Perhaps the answer is like this? We need to consider cases. We know we want {A,B,B} now what could happen? We could get an A, and be left with {B,B}. Or, we could get a B and be left with {A,B}. That's the one match case and subcases. Next, we could get two matches, and the only possible left is {A} (Note that this could be {B}, but the point is it's just one element, letters dont matter they just denote differences. A != B etc.). Okay so we have {A,B}, {B,B}, and {A} to consider for our next roll.

Now our probability is prob = probOfGettingOnThisRoll + (probMatchOne)*(prob {a,b}) + (probMatchOne) * (prob {B,B}) + (probMatchTwo)(prob {A}) + probMatchNone(prob {A,B,B}).