Fast calculation of probability distribution in board game Da Vinci Code

user_17940040 0
Viewed 73

I'm interested in efficiently calculating the probability distribution over possible secret numbers given what one can observe of the opponents' hand (and your own hand) in the board game Da Vinci Code. A link to the game here: https://boardgamegeek.com/boardgame/8946/da-vinci-code

I have abstracted the problem into the following: You are given an array A of length N and a finite set of numbers Si for each index i of the array. Now,

  1. we are to place a number from Si at each index i to fill the entire array A;
  2. while ensuring that the number is unique across the entire array A;
  3. and for 3 disjoint subarrays A1, A2, A3 of A such that concat(A1, A2, A3) = A, the numbers in each subarray must follow a strictly increasing order; given all the possible numbers to form A that satisfy the above constraints, what is the probability ditribution over each number at each index?

Here I provide an example below: Assuming we have the following array of length 5 with each column representing Si at the index of the column

| 6 6 | 6 6 | 6 |
|   5 |   5 |   |
| 4 4 |     | 4 |
|     | 3 3 |   |
| 2   | 2 2 |   |
| 1 1 |     |   | 
| ___ | __  | _ |
| A1  | A2  | A3|

The set of all possible arrays are: 14236 14256 14356 15234 15236 15264 15364 16234 16254 16354 24356 25364 26354 45236

Therefore the probability distribution over each number [1-6] at each index is:

 
6  0      4/14  0     3/14  6/14 

5  0      6/14  0     6/14  0    

4  1/14   4/14  0     0     8/14 

3  0      0     6/14  5/14  0    

2  3/14   0     8/14  0     0    

1  10/14  0     0     0     0    

___________   __________   ______

    A1          A2          A3

Brute forcing this problem is obviously doable but I have a gut feeling that there must be some more efficient algorithms for this.

The reason why I think so is due to the fact that one can derive the probability distribution from the set of all possibilities but not the other way around, so the distribution itself must contain less information then the set of all possibilities have. Therefore, I believe that we do not need to generate all possibilites just to obtain the probability distribution.

Hence, I am wondering if there is any smart matrix operation we could use for this problem or even fixed-point iteration/density evolution to approximate the end probability distribution? Some other potentially more efficient approaches to this problem are also appreciated.

probability linear-algebra combinatorics matrix algorithm
1 Answers

A simple idea to get an approximation for the distribution is to use a Monte Carlo approach.

Set a variable total: = 0 and a matrix M[N][Q] with all entries initially set to zero (Q is the total of numbers allowed).

Fix a positive integer K. Perform K iterations. At each iteration, for each i in [1..N], take a random element from Si and fill the array A. When the array A is all filled, verify in O(N) if it satisfies your conditions. If so, increment by one the variable total and iterate through the array, incrementing the matrix entries M[i][A[i]] by one, for i in [1..N].

In the end, iterate through all the elements of the matrix M in O(N Q) and divide its elements by total to get an approximation for the distribution.

Total time complexity is O(N (K + Q)).

You can also precalculate stuff to make the approximation more precise. For example, you can precalculate all increasing sequences in the groups A1, A2 and A3. Put them in arrays I1, I2, I3. Then, at each iteration, instead of taking random elements from each Si, you take random sequences from I1, I2 and I3 and verify if the concatenation has no repeated elements (in O(N)). If so, proceed as before. The total time complexity (apart from the expensive precalculation) remains O(N (K + Q)).

user_117090210
Related