You have probably played, and may even have written a program to play, a simple number guessing game. If so, this probably looks familiar:
Try to guess my number (1 to 100)! Please enter a guess: 50 Too small, guess again! Please enter a guess: 75 Too big, guess again! Please enter a guess: 63 Correct!
(Obviously, it usually takes a little longer.)
But what if your opponent lied? Or, to be more generous, isn't very good at comparing numbers.
There are two parts to this challenge.
1: The liar
- Your program will be passed a number between 0 and 255 inclusive.
- Your program will be passed a guess, within the same bounds.
- Your program should return one of -1 (the guess is smaller than your number), 0 (the guess is your number) or 1 (the guess is greater than your number).
- You may store state for the duration of a single game.
- You may return an inaccurate result (lie!) up to 8 times in a game.
- If you return 0 when the guess is not equal to your number, your opponent will win anyway. However, you may chose not to return 0 even when the guess is equal to your number (this counts as one of your allotted lies).
- Your aim is to delay returning 0 for as long as possible ("long" as in most calls to the program, not length of time, obviously).
2: The guesser
- Your program will be passed a function to call. You should pass this function a guess, between 0 and 255. It will return -1 (indicating that you should guess lower), 0 (indicating that your guess was correct) or 1 (indicating that you should guess higher).
- The function may return an inaccurate result up to 8 times in a single invocation of your program.
- Your aim is to receive output of 0 from the function after calling it the fewest possible times.
- Once the liar has used up their allotted lies, the function passed to the guesser (henceforth "guess function") will simply begin returning the correct answer without invoking the liar.
- The maximum number of guesses is 2304 (equivalent to trying every possible number 9 times). After this, the guess function will return 0 and end the game.
- Practically, the guess function will never return 0, it will just end the game. So the guesser only needs to handle a return of -1 or 1.
- The best guesser is the one that takes the fewest guesses to end the game. The best liar is the one that delays the end of the game for the greatest number of guesses.
All submissions must be written in Python 3. Answers should use the following template:
# <type>: <name> <code> <description>
<type> is either
Guesser. Every submission should define a callable called
Main (this may be a class or function).
For the liar, it should accept two parameters: an instance of
random.Random, to generate any non-determinism needed, and an
int, which is the secret to protect. It should return another callable, which accepts a guess (as an
int) and returns
1 (it is never advantageous to return
0). The recommended way of implementing this is as a class, for example:
class Main: """Liar that always returns one.""" def __init__(self, rng: random.Random, secret: int): """Store the rng and secret even though we do nothing with them.""" self.rng = rng self.secret = secret def __call__(self, guess: int) -> int: """Return 1.""" return 1
For the guesser,
Main should also accept to arguments: an instance of
random.Random, as above, and a callable (the guess function). For example:
def Main(rng: random.Random, liar: Callable[[int], int]): """Guess randomly.""" while True: liar(rng.randrange(256))
Note that the function never needs to exit, this will be handled by the game runner.
10 repetitions with seed XHMS2Z: Top liars: ------------------------------------- tsh_equal_lie 499 mojo_black_one_big_lie 497 mojo_black_keep_away 486 qwatry_illusionist 485 sheik_yerbouti_the_liar_king 353 citty_mislead 346 spitemaster_look_over_there 341 leo_knave 99 Top guessers: ------------------------------------- user1502040_bayes_bot 26 mojo_black_phoenoix_wright 29 l4m2_fib_trust 30 tsh_most_correct_guess 30 att_top_median 32 sheik_yerbouti_no_matter_what 61 tsh_most_recent_guess 65 citty_pester 67 m_virts_binary_reset_gaussian 1528 m_virts_binary_reset 2015 Slowest submissions: ------------------------------------- m_virts_binary_reset_gaussian 0.0063s m_virts_binary_reset 0.0049s user1502040_bayes_bot 0.0028s l4m2_fib_trust 0.0021s tsh_most_recent_guess 0.0013s att_top_median 0.00089s tsh_most_correct_guess 0.00073s mojo_black_keep_away 0.00052s qwatry_illusionist 0.00042s mojo_black_one_big_lie 0.00042s tsh_equal_lie 0.00037s citty_pester 0.00018s citty_mislead 0.00016s sheik_yerbouti_no_matter_what 0.00016s spitemaster_look_over_there 0.00015s sheik_yerbouti_the_liar_king 0.00013s mojo_black_phoenoix_wright 0.0001s leo_knave 7.5e-06s 0 submissions were disqualified.
Congrats to tsh and user1502040 for topping the leaderboards!