Calculating Probability of Adjacent Tile Groups

Sometimes calculating probability of certain events is not simple. There is not always a neat equation, which can express the model and number of possible outcomes is too large for a naive approach. While finding general solution is still limited, for any practical purposes optimizations could be done to bring calculations to a possibility. Let us consider the following game of random chance.

• Grid consists of 20 tiles arranged in 5 columns and 4 rows.
• Each round every tile will be assigned a random type out of 8 possible options with equal probability of 1.25% or \(1\over8\).
• Tile Groups consist of 5 or more vertically or horizontally adjacent tiles with the same type.

Any Group Frequency

Total number of possible combinations \(C_n^m = n^m\), where n is total number of tiles and m number of different tile types.
Brute-force approach would result in evaluating 1,152,921,504,606,847,000 options.
Going through more than one quintillion might not be very practical, so we need to simplify and reduce the problem to compute.

One way of achieving our goal would be to separate affecting variables.
Let us try to define the probability of a group of type t with s tiles appearing. \[P_t^s = \sum_{i=s}^n {w_t}^i (w_{total}-w_t)^{n-i} A_s^i \] \(A_s^i\) Would signify the amount of possible arrangements, where i tiles would actually result in s of them forming an adjacent group.

We have reduced one part of the problem to a complexity of \(2^n\).
Following code loops through all 1048576 possible arrangements and outputs a nxn matrix with corresponding group counts.

const total = columns * rows, temp = new Uint8Array(total)
const out = Array(total * total).fill(0)
for(let i = 2 ** total; i > 0; i--){
    let filled = 0
    temp[0]++
    for(let j = 0; j < total; j++)
        if(temp[j] === 1) filled++
        else if(temp[j]){
            temp[j+1]++
            temp[j] = 0
        }
    //for each group
    //out[(filled - 1) * total + count - 1]++
}
//A(s,i) = out[(s-1) * total + i - 1]
                

Above graph demonstrates a usefull technique - validation via running simulations also known as Monte Carlo method.
For illustrative purposes distribution is shown for any tile type of specific group size. Number of tile types was reduced so that it would converge faster.
Horizontal axis values were normalized, for reference frequency of 20x group is once in 524288.

Dependent events

So far we have been only concerned with independent events. Even though multiple groups can appear at the same time, frequency of individual groups is an independent statistic.
What if we were to add a balance bar, which would move either left or right depending on appearing tile groups.
To calculate average amount of rounds it takes to reach either side Markov chain model can be used.
However, in order to create state transition matrix, having individual group probabilities is not enough.
For example, if there are two groups of the same size and opposite color they would cancel each other out.
We would have to take into account all possible combinations of multiple groups appearing at the same time.

Given that adjacent groups start at size 5, \(({n\over5})^n = 4^{20} = 1099511627776\)
Number of all combinations seems large enough that we should consider applying various optimizations to our algorithm.

• We can start by ignoring all groups \(s < 5\).
• Only consider unique combinations. \(\{10,6\} \equiv \{6,10\}\)
• Avoid counting adjacent groups multiple times when possible.

function permutate(index, item, empty){
    const remaining = total - index
    if(key[item - 1] + remaining < minThreshold) return
                    

    if(remaining == 0){
        //for each group
        //if(count >= minThreshold) hits[item - 1].push(count)
        
        if(hits[item - 1].length) out[key][hit]++
        else return

        if(empty >= minThreshold){
            key[item] = 0
            hits[item] = []
            permutate(0, item + 1, empty)
            key.length--
            hits.length--
        }
        return
    }
                    

    if(temp[index] == 0 && (item < 2 || key[item - 1] < key[item - 2])){
        temp[index] = item
        key[item - 1]++
        permutate(index + 1, item, empty - 1)
        key[item - 1]--
        temp[index] = 0
    }
    permutate(index + 1, item, empty)
}
                    

Resulting set would consist of only 105665736 even though algorithm complexity is still \(O(n^n)\) since depth is only constrained by our arbitrary rules.
While above code would still run for a significant amount of time, output depends only on grid dimensions and can be precalculated once.

Probability States

Transition Matrix would hold chances to transition from any particular state into another.
In our case Matrix would be of size 1x33, since chances are fixed and do not depend on current state.
\(|\{-16,-15,...,-1,0,1,...,15,16\}| = 33\)
Every state would correspond to all combinations of adjacent groups resulting in a specific delta balance.

Let us bring back the number of possible tile types. We would need to go through every unique combination of tile groups once more.

function recursive(index, prevCount,  counts, items){
    const remaining = Math.min(totalTiles - prevCount, index ? counts[index - 1] : totalTiles)

    for(let count = remaining; count >= minThreshold; count--)
    for(let i = 0; i < weights.length; i++){
        if(items.indexOf(i) != -1 || !weights[i]) continue
        if(index && count === counts[index - 1] && i < items[index - 1]) continue

        //...

        if((totalTiles - prevCount) - count >= minThreshold)
            recursive(index + 1, prevCount + count)
    }
}
                    

const weight = items.reduce((total, i, j) => total * weights[i] ** counts[j], 1) *
(totalWeight - items.reduce((total, i) => total + weights[i], 0)) **
(totalTiles - counts.reduce((total, count) => total + count, 0))

for(let hit in arrangements[counts]){
    const chance = arrangements[counts][hit] * weight / totalCombinations
    //...
}
                    

const delta = hits.reduce((total, delta) => total + delta, 0)
out[delta] += chance

if(hits.length > 1) for(let i = hits.length - 1; i >= 0; i--){
    const prevDelta = delta - hits[i]
    out[prevDelta] -= chance
}
                    

Using iterative discrete model we can now calculate average number of rounds to reach one side. \[R_{avg} = \sum_{i=1}^\infty i M_{il} | l = 20\] where M is chance to reach leftmost state in i steps.
Since \(\lim_{i\to\infty} {iM_{il}} \to 0\), model will converge resulting in frequency of ~3208.68.

Additional Control Variables

If we would want to adjust parameters, so that reaching left or right side would be much more frequent, we need to introduce another mechanism to our ruleset.
First of all we would use weighted chance for every tile type. Additionaly we can define multiple weight tables and assign weights to them.
That will result in every weight table skewing towards specific tile types. Contrary to how tiles are determined, weight table is only randomized once per round.
One way of modelling that would be to have additional types of tiles, which would get tile type from separate weight table. \[ P_{t} = {(w_{t}+w_{z})z_{t}}\over{w_{total}z_{total}} \]

while(items[0] > 0){
    const nextWeights = weights.slice(0, -mystery.length)
    items.forEach((index, i) => nextWeights[index] += weights[nextWeights.length + i])
    const weight = items.reduce((total, index, i) => total * mystery[i][index], 1)
    out.push({ weights: nextWeights, chance: weight / totalWeight })
    items[items.length - 1]--
    for(let i = items.length - 1; i > 0; i--)
    if(items[i] <= 0){
        items[i - 1]--
        items[i] = mystery[i].length - 1
    }
}
                

We can move all those calculations outside by flattening back into multiple weight tables.
The above will produce \(m^z\) tables, where z would indicate the number of different shared tile types.

Finally let us take a look at a modification required to support substitution.
Specific tile types would be counted as other tile types when evaluating outcomes.
Our previous code for accumulating tile group frequencies:

const weight = (weights[item] ** tiles) * ((totalWeight - weights[item]) ** (total - tiles))
for(let i = 1; i <= total; i++)
    out[i - 1][item] += weight * arrangements[(tiles-1) * total + i - 1] / combinations
                

We would have to additionally keep track of chances that particular group can be of any type, that canbe converted into relevant one.
We would then have to subtract chances where group would otherwise be converted into a different type.
We only count actually adjacent tiles, since that does not apply to any other tiles of the same type, which are not connected.

const otherWeight = weights.filter((_, i) => substitute(i, item) || substitute(item, i)).reduce((t, w) => t + w, 0)
const itemWeight = weights.filter((_, i) => substitute(i, item)).reduce((t, w) => t + w, 0)
for(let i = 1; i <= total; i++){
    const weight = itemWeight**i * otherWeight**(tiles-i) * (totalWeight-otherWeight)**(total-tiles)
    const invWeight = (itemWeight-weights[item])**i * otherWeight**(tiles-i) * (totalWeight-otherWeight)**(total-tiles)
    out[i - 1][item] += (weight - invWeight) * arrangements[(tiles-1) * total + i - 1] / combinations
}
                

Summary

Described approach will not scale for larger grid sizes. It can however accomodate additional complex rules, multiple tile types and weighted type selection.
Arbitrary ruleset does not always result in cleanly looking equations, but rather produces a large number of combinations. In this case the most efficient approach is taking a brute-force evaluation method and optimizing it to a practical degree.
Whenever this is not possible, a simpler simulation method is advised.