Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes (Q1586758)

In Ulam's game, player 1 thinks of a number from 1 to \(N\). Player 2 asks yes or no questions to player 1 who is allowed to lie up to \(\ell\) times. This is equivalent to the problem of transmitting messages over a noisy binary channel with noiseless feedback. The author solves the game for \(\ell=3\) and makes considerable progress in general. The author's solution requires \(N>265\). (If \(N\leq 265\) then an exhaustive computer search is feasible.) The solution is in three parts. A fixed ``opening book'' is used for the first three questions. Then an algorithm is given for calculating the next question in a general ``mid-game'' position. At this point, we are at most 15 questions away from victory, and can apply Guzicki's algorithm for the ``end-game''.