Tuesday, June 23, 2020

Errata: How replayable is Onitama using the 16 move cards in the base game?

In our earlier discussion of Onitama, there was an error in the calculation of the number of sets of five cards which have an asymmetric card without its mirror, which we labeled $n_3$, helpfully pointed out by a reader in the comments.  On reflection, the error is somewhat obvious, as we computed that there are more of these cases than the total number of ways of select five cards, $n_1$.
n_1 &= 4368 \\
n_3 &= 8008 \\
n_3 &> n_1
We avoided spotting the error because we subtracted half of $n_3$ from $n_1$, and since $n_1 > n_3/2$, we still got a positive number.  However, a simple check of the scale of these two numbers would have indicated the error.

But what is the error?  It's that we double counted many cases (I really should be saying I here, as I made the error, and you're following along at home probably spotting my error!).  Recall the construction of $n_3$.  We selected one of the asymmetric cards, and then allowed the remaining cards to be any of the cards except the mirror of the first card.  However, that includes cases where there is an additional unmatched asymmetric card.  Those cases get counted again when we get to picking the unmatched card as the first card.

Correcting this gets messy.  I'd still like the largely follow the flow that I used originally, so let's just recompute $n_3$ correctly.  Unfortunately, the best way that I've been able to come up with involves summing over every possible number of unmatched asymmetric cards as well as looking at every possible number of matched asymmetric cards.  The crux is this: if we include an asymmetric card we must know whether or not its pair is included.  Given the number of unmatched asymmetric cards, $u$, and the number of matched pairs, $m$, we can find the number of ways to come up with a valid selection.  First, there are $\binom{8}{u}$ ways to select $u$ unmatched asymmetric cards out of the total of 8, with $u$ from 1 to 4.  The maximum is 4, because there are only 4 pairs of matches cards, so we can't get 5 unmatches ones.  A fifth card would have to match.  That leaves us with $16-u$ cards, but only $4- u$ pairs of matched asymmetric cards ($8-2 \cdot u$ cards in total).  This means there are $\binom{4-u}{m}$ ways to select the matched pairs.  If $u \geq 4$, then there's no space for matched pairs.  In general, we have to keep the total number of matched and unmatched cards to 5 or less, so
u + 2\cdot m \leq 5 .
This limits $m$ to satisfy,
m \leq \frac{5-u}{2}
From the binomial coefficient along, we can see that $m \leq 4-u$, but the above requirement is more restrictive here, since $m$ must be an integer.
u &4-u&\frac{5-u}{2}\\\hline
This leaves a remaining $5-u-2 \cdot m$ cards to be chosen from the remaining 8 symmetric cards, which there are $\binom{8}{5-u-2 \cdot m}$ to select.  Putting this together we get the following when we sum over the ranges computed above.
n_3 &= \sum_{u=1}^4 \sum_{m=0}^{\lfloor \frac{5-u}{2} \rfloor} \binom{8}{u} \cdot \binom{4-u}{m} \cdot \binom{8}{5-u-2 \cdot m} \\
n_3 &= 5456
Unfortunately, I've made another mistake, since the new $n_3$ calculation is still larger than $n_1$.

Perhaps you noticed that I did a poor job of selecting the number of ways to choose $u$ unmatched asymmetric cards.  It holds up to $u=1$, but not above.  We can't choose any of the 8 cards, as we can choose at most one of each pair.  Thus, when selecting each card, we need to choose which pair to select from, of which there are $\binom{4}{u}$ ways to do, and then select which card inside each set.  For each unmatched asymmetric card there are 2 ways of doing that (since there are two cards), so in total there are $2^u$ ways of selecting the $u$ cards once selecting the pairs.  This provides us with a new equation for $n_3$.
n_3 &= \sum_{u=1}^4 \sum_{m=0}^{\lfloor \frac{5-u}{2} \rfloor} \binom{4}{u} \cdot 2^u \cdot \binom{4-u}{m} \cdot \binom{8}{5-u-2 \cdot m} \\
n_3 &= 4040
Finally, we've gotten a number that's less than $n_1$.  It seems surprisingly large, in that almost all of the ways to select 5 cards out of 16 results in at least one unmatched asymmetric card.  Let's come up with a check that our methodology is correct.  If we add in the case that we get no unmatched pairs, that is $u=0$,
then we should get $n_1$.  Let's try that.
n_3 +  \sum_{m=0}^{\lfloor \frac{5}{2} \rfloor} \binom{4}{m} \cdot \binom{8}{5-2 m} &= \sum_{u=0}^4 \sum_{m=0}^{\lfloor \frac{5-u}{2} \rfloor} \binom{4}{u} \cdot 2^u \cdot \binom{4-u}{m} \cdot \binom{8}{5-u-2m} \\
 &= 4368 \\
&= \binom{16}{5} \\
&= n_1
This does a pretty good job of confirming that our methodology is correct, as our somewhat convoluted summation gives us the same value for $n_1$.  Now we can bring this all together and calculate the total number of initial positions considering  isomorphs.  Recall that we had the number of ways to select 5 cards excluding isomorphs is as follows.
n_4 &= n_1 - \frac{n_3}{2} \\
&= \binom{16}{5} - \frac{1}{2} \cdot  \sum_{u=1}^4 \sum_{m=0}^{\lfloor \frac{5-u}{2} \rfloor} \binom{4}{u} \cdot 2^u \cdot \binom{4-u}{m} \cdot \binom{8}{5-u-2m}\\
&= 4365 - \frac{4040}{2} \\
&= 2345
To get the number of initial positions with isomorphs, we need to multiply by $\frac{5!}{2 \cdot 2}$ as before.
n_5 &= n_4 \cdot \frac{5!}{2 \cdot 2} \\
&= 2345  \cdot \frac{5!}{2 \cdot 2} \\
&= 2345 \cdot 30 \\
&= 70350

No comments:

Post a Comment