Liars and Guessers

Question

Github

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.

General notes

• 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.

Submissions

All submissions must be written in Python 3. Answers should use the following template:

# <type>: <name>

<code>

<description>

Where <type> is either Liar or 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, 0 or 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.

Latest Results

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!

Answer 1

Guesser: phoenix_wright

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    while liar(0) == -1: pass
    previous = {0:1}
    lb = 0
    ub = 255
    while True:
        while lb <= ub:
            g = (lb+ub)//2
            if g in previous:
                r = previous[g]
            else:
                r = liar(g)
            if r == 1:
                lb = g+1
            elif r == -1:
                ub = g-1
            previous[g] = r
        k = g == ub
        n = 0
        while True:
            n += 1
            g = min(max(ub+k,0),255)
            k = 1-k
            r = liar(g)
            if previous[g] != r:
                previous[g] = r
                break
        lb = 0
        ub = 255

My idea was to cross-examine the liar witness (do a binary search), and when it finds a contradiction, press it (specifically, if it finds a -1 right next to a 1, it repeatedly guesses between the two). If that didn't solve the case, then we get a new testimony (reset the binary search bounds). The idea is to quickly cause the liar to run out of lies. It also has other optimizations. It keeps track of previous responses, so when it resets after the contradiction goes away, it doesn't actually have to use guesses to get back to where it was before. It also begins by checking that the liar isn't lying at the very beginning.

Answer 2

Liar, equal_lie

"""A liar that only lies when equal."""
import random


class Main:

    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret

    def __call__(self, guess: int) -> int:
        """Work out the correct response. mostly."""
        if guess == self.secret:
            if guess % 2:
                return -1
            return 1
        if guess < self.secret:
            return 1
        return -1

I have no idea why this works.

Answer 3

Guesser: top_median

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    poss=[0]*256
    while True:
        height = max(poss)
        top = [i for i in range(256) if poss[i]==height]
        guess = top[len(top)//2]
        
        i = liar(guess)
        for j in [range(guess+1), range(guess,256)][i<0]:
            poss[j] -= 1

Answer 4

Guesser, most_recent_guess

"""A guesser that based on recent guesses."""
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    scores, current = [0] * 256, 0
    while True:
        max_score = max(scores)
        values = [val for val, score in enumerate(scores) if score == max_score]
        guess = values[len(values) // 2]
        result = liar(guess)
        current -= 1
        if result > 0:
            scores[:guess + 1] = [current] * (guess + 1)
        else:
            scores[guess:] = [current] * (256 - guess)

Basic idea: The more recent response would be more trustable.

Answer 5

Liar: theLiarKing

import random, math

class Main:

    def __init__(self, rng: random.Random, secret: int):
        self.rng = rng
        self.secret = secret

    def __call__(self, guess: int) -> int:
        timeToLie = self.rng.randint(1,16)
        if guess == self.secret:
            res = self.rng.choice([-1,1])
        elif timeToLie == 1:
            if self.secret > guess:
                res = -1
            else:
                res = 1
        elif self.secret > guess:
            res = 1
        else:
            res = -1
        return res

This liar has a 6.25% chance to lie in each turn, and also lies every time the guesser guesses the right number.

I chose 6.25% (1/16) because in this way, on average, it lies againist my guesser one time because the guess was right and one time just because it wanted to lie.

Check my guesser answer

Answer 6

Guesser, most_correct_guess

"""A guesser that based number of correct times."""
import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    scores = [1] * 256
    while True:
        index, mid_score = 0, sum(scores) >> 1
        while mid_score > 0:
            mid_score, index = mid_score - scores[index], index + 1
        guess = max(0, index - 1)
        result = liar(guess)
        for index in (range(guess + 1, 256) if result > 0 else range(guess)):
            scores[index] <<= 1

Basic idea: We just consider all response from liar with same possibility of lying. There for, an answer may be correct if more responses support it. I still have no idea why 1 << is added there. It just works better than infinity weight (use max instead) and 0 weight (only use sum).

Answer 7

Liar: Knave

import random

class Main:
    """A **real** liar"""

    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret

    def __call__(self, guess: int) -> int:
        """You can trust me, really"""
        if guess > self.secret:
            return 1
        return -1

I think this challenge needs more Liar submissions. Here's a very straightforward one, lying as much as it can. As simple as it is, it can really throw off some guessers.

---

Extra: here's a TIO link to test submissions online that I put together by vandalizing modifying Artemis' code from Github. Feel free to use it to test your future submissions (add your submission to the header, with a unique name instead of "main", and remember to append it to either the guessers or liars list).

This liar turned out to be not exactly great, my consolation is that at least it managed to mess with the top positions of the guessers board ^^"

Answer 8

Guesser: FibTrust

#def Main(rng: random.Random, liar: Callable[[int], int]):
def Main(rng, liar):
    times=[8]*256
    weight=[1,2,3,5,8,13,21,34,55]
    while 1:
        a=[i>=0 and weight[i] for i in times]
        b=(sum(a)+1)/2
        guess=-1
        #print(times)
        while b>0:
            guess=guess+1
            b=b-a[guess]
        cmp=liar(guess)
        times=[times[i]-(i==guess or (cmp<0)^(i<guess)) for i in range(256)]

Try it online!

Answer 9

Liar: keep_away

"""A liar that tries to keep the guesser away from the secret"""
import random

class Main:
    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret
        self.lb = 0
        self.ub = 255
        self.lies = 4
    def __call__(self,guess):
        r = (guess <= self.secret) - (guess > self.secret)
        a = (self.lb+self.secret)//2
        b = (self.ub+self.secret)//2
        if self.lies:
            if a <= guess < self.secret:
                self.lies -= 1
                self.lb = guess
                r = -r
            elif self.secret < guess <= b:
                self.lies -= 1
                self.ub = guess
                r = -r
        return r

Similar to my other liar, this tries to waste time, but instead it keeps track of how close the guesser has gotten, and lies when it gets too close (the threshold for too close gets smaller each time).

Answer 10

Guesser, BinaryReset

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    """Guess deterministically."""
    ub=255
    lb=0
    while True:
        g=(ub-lb)//2+lb
        r=liar(g)
        if r==-1:
            lb=g
        elif r==1:
            ub=g
        if lb>=ub:
            ub=255
            lb=0

Untested, for now ill just hope it works.

Guesser, BinaryResetGaussian

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    """Guess less deterministically."""
    ub=255
    lb=0
    while True:
        g=max(0,min(255,int(rng.gauss((ub+lb)//2,(ub-lb)/6))))
        r=liar(g)
        if r==-1:
            lb=g+1
        elif r==1:
            ub=g-1
        if lb>=ub:
            ub=255
            lb=0

Instead of fixing my binary search, why not just add randomness?

Answer 11

Guesser: BayesBot

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    num_possibilities = 256
    max_lies = 8

    distribution = {(secret, max_lies) : 1. / num_possibilities for secret in range(num_possibilities)}

    lie_rates = [
        0, 0.211, 0.195,
        0.188, 0.138, 0.207,
        0.202, 0.140, 0.228,
    ]

    while True:
        secret_distribution = [0] * num_possibilities
        for (secrets, _), p in distribution.items():
            secret_distribution[secrets] += p
        q = 0.5
        for guess, p in enumerate(secret_distribution):
            q -= p
            if q < 0:
                break

        result = liar(guess)

        next_distribution = {}
        for (secret, lies), p in distribution.items():
            if secret == guess:
                lie = True
                cond_p_result = 0.55 if secret % 2 else 0.83
                if result == -1:
                    cond_p_result = 1 - cond_p_result
            else:
                lie = (result == 1) != (guess < secret)
                cond_p_result = lie_rates[lies] if lie else 1 - lie_rates[lies]
            if lies == 0 and lie:
                continue
            next_p = p * cond_p_result
            if lie:
                next_distribution[(secret, lies - 1)] = next_p
            else:
                next_distribution[(secret, lies)] = next_p

        c = 1. / sum(next_distribution.values())
        distribution = {k : c * p for k, p in next_distribution.items()}

Uses a statistical model to estimate the probability that each number is the secret, then always guesses the median of this distribution. Sort of like a fuzzy binary search.

Answer 12

Liar: LookOverThere

class Main:
    """Liar that picks a number 64 off from the actual target and pretends that's the correct answer."""

    def __init__(self, rng, secret: int):
        """Pick a new secret."""
        self.secret = secret + 63.5 if secret < 128 else secret - 63.5

    def __call__(self, guess: int) -> int:
        """Return the 'correct' answer."""
        if guess < self.secret:
            return 1
        elif guess > self.secret:
            return -1
        # Should never happen
        return 0

Maximizing time spent lying is probably the way to go. So we want to give the correct answer most of the time, lying only when necessary. I may adjust the difference after testing (down to 32 off or 16 off the correct answer).

Answer 13

Guesser: noMatterWhat

import random
from typing import Callable

def Main(rng: random.Random, liar: Callable[[int], int]):
    i = 0

    while i < 9:
        low = j = 0
        high = 255

        while j < 8:
            guess = (low + high) // 2
            res = liar( guess )
            if res > 0:
                low = guess + 1
            else:
                high = guess - 1
            j += 1

        i += 1

The code implements a binary search to look for the secret value.
A binary search over 256 values is granted to find the key in 8 steps.
But since the liar can lie 8 times, a single binary search is not enough, we need at most 9 of them.

So this guesser is granted to end the game in at most 8 * 9 = 72 turns, no matter what's the strategy implemented by the liar.

Special thanks go to Artemis, who had the patience to explain me how to run the game, so that I could debug my answers.

Check my liar answer

Answer 14

Guesser: Pester

import random
from typing import Callable

def guess_lies(liar, guess, lies):
    tries = [liar(guess) for _ in range(9-lies)]
    return tries[-1], lies + min((tries.count(-1),tries.count(1)))

def Main(rng: random.Random, liar: Callable[[int], int]):
    while True:
        low = 0
        high = 255
        lies = 0
        for j in range(8):
            guess = (low + high) // 2
            res,lies = guess_lies(liar, guess, lies)
            if res > 0:
                low = guess + 1
            else:
                high = guess - 1

Repeatedly guesses the possible amount of times that the liar could lie at any instance + 1, and assumes the last answer is correct. This is only slightly worse than just doing 9 binary searches.

Answer 15

Liar: one_big_lie

"""A liar that lies once at the very beginning"""
import random

class Main:
    def __init__(self, rng: random.Random, secret: int):
        """Store the rng and secret."""
        self.rng = rng
        self.secret = secret
        self.lied = False
    def __call__(self,guess):
        r = (guess <= self.secret) - (guess > self.secret)
        if not self.lied:
            self.lied = True
            r = -r
        return r

The idea is that lying on the very first turn would waste a lot of time for the guesser while using a minimal number of lies.

Answer 16

Liar: Mislead

from collections import defaultdict
import random

class Main:
    """Liar that tries to foil binary searchers and repeat guesses"""

    def __init__(self, rng: random.Random, secret: int):
        self.rng = rng
        self.secret = secret
        self.lies = 0
        self.low = 0
        self.high = 255
        self.prev_guess = defaultdict(int)

    def __call__(self, guess: int) -> int:
        """Return 1"""
        if self.prev_guess[guess] > 0:
            if guess != self.secret:
                if self.rng.randint(0,self.prev_guess[guess]-1) == 0:
                    self.lies += 1
                    answer = -1 if guess > self.secret else 1
                else:
                    answer = 1 if guess > self.secret else -1

        
        if guess == self.secret:
            self.lies += 1
            return self.rng.choice((-1, 1))
        
        self.prev_guess[guess] += 1

        if not (self.low <= guess <= self.high):
            self.low = 0
            self.high = 255
            self.prev_guess = defaultdict(int)

        if self.low <= self.secret <= self.high: 
            if self.rng.randint(1,self.lies+1) == 1:
                self.lies += 1
                if not (guess <= self.secret <= self.high):
                    self.low = guess + 1
                    return 1
                else:
                    self.high = guess - 1
                    return -1

        answer = -1 if self.secret < guess else 1
        if answer < 0:
            self.low = guess + 1
        else:
            self.high = guess - 1
        return answer

Tries to break binary searchers and doesn't seem to do a great job at it, also lies to people who ask the same guess multiple times. Isn't great but at least it beats LookOverThere?

Answer 17

Liar: Illusionist

import random
class Main:
    def __init__(self, rng: random.Random, secret: int):
        self.rng = rng
        self.secret = secret
        self.fake_secret = (127-secret)%256
        self.unreserved_lies = 4
        self.prev_lies = []
    def __call__(self, guess: int) -> int:
        if guess < self.secret:
            secret_direction = 1
        elif guess > self.secret:
            secret_direction = -1
        else:
            secret_direction = 0
        if self.unreserved_lies and guess not in self.prev_lies:
            if guess < self.fake_secret:
                if secret_direction != 1:
                    self.prev_lies.append(guess)
                    self.unreserved_lies -= 1
                return 1
            if secret_direction != -1:
                self.prev_lies.append(guess)
                self.unreserved_lies -= 1
            return -1
        elif secret_direction != 0:
            return secret_direction
        return -1

The liar picks an illusory number to lead the guesser towards. However, if the guesser double checks the liar's answer, it will tell the truth in order to avoid wasting lies. The liar reserves 4 lies for when the guesser chooses a number equal to the real secret.