No Title Found

AbstractNo Abstract Found

After examining a variety of heuristic strategies that perform variably under different configuration of rules, a natural question arise: for a given set of rules, does there exist an optimal strategy? The answer is “yes”. In this chapter, we will explore several techniques that enable us to find such a strategy.

Overview

An optimal strategy is a strategy that achieves a certain objective in an optimal manner. In this chapter, we will focus on the following three objectives, in order of strength of optimality:1

Note that there may be other objectives for a strategy, such as minimizing the number of guesses evaluated. See, for example, Temporel and Kovacs (2003). However, those objectives are not studied in this chapter.

Optionally, additional constraints could be enforced for an optimal strategy. Commonly used constraints include:

The theory to find an optimal strategy is simple. Since the number of possible secrets as well as sequence of (non-redundant) guesses are finite, the code breaker can employ an exhaustive search to find out the optimal guessing strategy. However, the scale of the problem is very big and many optimization techniques are required to achieve an efficient (or even feasible) implementation. These technique are discussed in this chapter.

[could copy Neuwirth’s illustration of finding an optimal strategy]

[show the search scale of the problem]

[show that an optimal strategy is not unique]


  1. In each objective presented, we could replace “reveal” with “determine”, which are subtly different from an information perspective (see 2.4). The overall methodology remains the same. Therefore in this chapter we will focus on strategies that aim to reveal the secret.

Obvious Guesses

Some definitions. Partitions, feedback count, etc.

While finding an optimal strategy for the general game is complex, in certain cases it’s easy. For example, when there’s only one possibility left, we should guess it. When there are only two possibilities left, we should guess (either) one of them. [these appear in Neuwirth 82]. When there are more than two possibilities, it’s still possible.

An obviously-optimal guess is an optimal guess that doesn’t require too much effort to identify. Depending on the techniques used to identify such, the “obvious”-ty could vary. Here we use the technique introduced by (Koyama {1993}).

[Definition.] An obviously-optimal guess is a guess that partitions the remaining possibilities into discrete cells, i.e. where every cell contains exactly one element.

If such a guess exists and comes from the possibility set, then it is optimal because it reveals one potential secret (itself) in the immediate step and reveals all the other potential secrets in two steps. It is easy to see that no other strategy could do better. If no such guess exists in the possibility set but one exists outside the possibility set, then that one is optimal because it reveals all secrets in two steps.

Note that an obviously-optimal guess is fairly generic about the goal – it is optimal both in terms of the worst-case number of steps and the expected number of steps to determine or reveal the secret.

A necessary condition for an obviously-optimal guess to exist is that the number of remaining possibilities does not exceed the number of distinct feedbacks. For a game with \(p\) pegs, the number of distinct feedbacks is \(p(p+3)/2\). For example, in a four-peg game, there can be at most 14 secrets left for an obviously-optimal guess to exist. This is a useful check in practice to reduce unnecessary efforts to search for an obviously optimal guess.

Note also that in practice we may only want to check in the remaining possibilities (so that the effort is minimized). In turns out that if we check outside the remaining possibilities, it is equivalent to a full-run of a heuristic function, as we show below.

It turns out (not so surprisingly) that the heuristics introduced in the previous chapter will yield an obviously-optimal guess when one exists. We only need to show that the partition of an obviously-optimal guess (which we will call an obviously optimal partition and denote by \(Q\) below) achieves the lowest possible heuristic value.

Let \(P\) denote any given partition. Let \(k\) denote the number of (non-empty) cells in \(P\). Let \(n_i\) denote the number of elements in the \(i\)-th cell. Let \(n = \sum_{i=1}^k\) denote the total number of elements, which is invariant across different \(P\). Finally, let \(Q\) denote the partition of an obviously-optimal guess, i.e. one with all singleton cells.

h(P) = _1 i n n_i 1 = h(Q).

The heuristic value of an obviously optimal partition is one. This is the minimum value of the heuristic function.

h(P) = _i=1^k n_i _1 i k n_i 1 = h(Q).

The heuristic value of an obviously optimal partition is one. This is the minimum value of the function.

h(P) = - _i=1^k = ?

The heuristic value of an obviously optimal partition is ?. This is the maximum value of the function.

h(P) = k n = h(Q).

The heuristic value of an obviously optimal partition is \(n\). This is the maximum value of the function.

Since all four heuristics introduced yield an obviously optimal guess when one exists, we can insert the step to find an optimal guess into the strategy as a shortcut to save computation time, knowing that this will not alter the output of the heuristic strategy.

Less Obvious Guesses