An improved heuristic for "Ulam-Rényi game"

Abstract

We consider the problem of searching for an unknown integer in the set {1,2, . . . , n}, by using questions that can be answered yes or no and with up to e errors in the answers. This problem is usually referred to as the Ulam–Rényi game with e lies. Solutions requiring a minimum number of questions have been given for any n and e ∈ {1,2,3} and for arbitrary e provided that n is sufficiently large. However, from the solution given for the general case for arbitrary e, it seems difficult to efficiently extract the optimal searching strategy. Therefore, suboptimal easy-to-implement heuristics have been proposed in the literature. It is the purpose of this paper to present an improved heuristic for the Ulam–Rényi game. Our heuristic also allows us to exactly solve the problem for a few cases of n and e which were left open by previous papers.  2000 Published by Elsevier Science B.V. All rights reserved.

Topics

1 Figures and Tables

Download Full PDF Version (Non-Commercial Use)