2
$\begingroup$

Motivated by the recent question about the optimal strategy in the strike-ball game, I wanted to inquire what are the pragmatic approaches one could use to solve such problems in practice. Let me attempt to define a generalized problem

  1. There is a large discrete enumerated set of states $S$.
  2. There is an unknown value function $v: S \rightarrow Bool$ defined over the elements of this set, which is true for one element and false for all the others. Call the element for which the function is true the "secret" element
  3. There is a known distance function $d: S^2 \rightarrow \mathbb{N}^{0+}$ defined for a pair of elements. The distance is a positive integer if the elements are distinct, and zero if they are the same. It is symmetric wrt order of the pair. It does not in general satisfy the triangle inequality. It is also known that the entire set $S$ possesses some amount of symmetry with respect to $d$. In an example application, the states could be points on an N-simplex of integer side-length, and $d$ could be the euclidean distance.
  4. It is possible to ask the game for the distance between the secret element and any other element.
  5. The goal of the game is to determine the secret element in smallest possible number of questions. The number of mental computations including computing distances between two known elements is essentially free, the only thing that counts is the number of questions about the secret element asked.

Strategy I propose:

  1. Make a copy $S'$ of the above set
  2. Pick a random element $r_i\in S'$ from the set, ask for the distance $d_i = d(r_i, x)$ to the secret element $x$
  3. Find all elements $E = \{s \in S' : d(r_i, s) \neq d_i\}$ that are not at the distance $d_i$ from the element $r_i$. Remove them from $S'$
  4. Repeat 1-3 until only one element remains in the set

Problems with my strategy:

  1. While it always asks questions that increase knowledge, it does not take advantage of some questions being potentially more useful than others.
  2. More importantly, it requires the storage and looping over all possible states, which may be unfeasible in real applications

Actual question(s): What are the possible approaches one can attempt to algorithmically solve such problems in a more memory-realistic manner? If I were to only store a list of questions and answers I have received, as well as some small amount of auxiliary variables, would it possible to efficiently determine at least one state that can't be excluded to be the secret state based on current knowledge? Are there approximate approaches that are guaranteed to converge but do not necessarily ask the optimal amount of questions, while having small memory? Any examples or links to literature are welcome

Edit: I emphasize again that computer processing power is irrelevant to me. There are two goals - minimizing the number of questions asked and minimizing the amount of memory used to solve the problem. I want a compromise strategy

$\endgroup$
  • $\begingroup$ It's unclear that only questions regarding the distance to the secret element count as your primitive operation and that all others are free. Please emphasize that more. $\endgroup$ – orlp Sep 5 '18 at 5:55
  • $\begingroup$ I will, thanks for noticing $\endgroup$ – Aleksejs Fomins Sep 5 '18 at 5:56
  • $\begingroup$ Furthermore, you may want to specify whether your distance function satisfies the triangle inequality. That generally tends to matter quite a bit for these optimization problems. $\endgroup$ – orlp Sep 5 '18 at 5:56
  • $\begingroup$ I think it is possible for it to not be satisfied. In general, board games can have a weird graph beneath them. Noted in the question $\endgroup$ – Aleksejs Fomins Sep 5 '18 at 6:06
0
$\begingroup$

You only need to keep in memory a handful of elements as you enumerate the state space.

Initially your memoized set of pairs $M$ is empty. When adding an element $m$ to $M$ you store $d(m, s)$ together with it (where $s$ is the secret element), costing a query.

Then as you enumerate $S$ for each element $x$ you check for each element $m \in M$ whether $d(m, s) = d(m, x)$. If $x = s$ this must be true, if this is false we know $x$ is not the secret element and can immediately discard it. This also doesn't cost a query because we already know $d(m, s)$ and $d(m, x)$ is free.

If $x$ passes this check for each $m \in M$ you add it to $M$ as said above, with the caveat that you can stop if $d(x, s) = 0$, as you've found the secret element.

As an exercise to the reader, convince yourself that the above algorithm only stores $k$ elements in $M$, where $k$ is the degrees of freedom the elements of $S$ have. E.g. if $S$ is some subset of $\mathbb{R}^2$ you will only store two elements in $M$.

To visualize this, consider asking a mere one question in the $\mathbb{R^2}$ scenario for some point $p$. Now you can draw a circle with radius $d(p, s)$ and know that $s$ must lie on that circle. The circle is a sphere for three degrees of freedom, a hypersphere for four, etc. Each question you ask reduces the degrees of freedom by one.

What exactly can be considered a degree of freedom depends on the distance metric.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.