Liars and Guessers

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)!
Too small, guess again!
Too big, guess again!
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
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
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!

• Yuck, a language-specific challenge. Please try to avoid these as much as possible. – Makonede Mar 10 at 17:28
• @Makonede Most KOTH challenges are language-specific. – Arnauld Mar 10 at 17:31
• Hmm, I guess you have a point. – Makonede Mar 10 at 17:33
• Is the guesser function supposed to make a single guess and be called by the game runner multiple times or is it supposed to be called just once and make all the required guesses by itself? From the snippet it seems it should be called just once, but then how would the game runner know the amount of guesses? I just wanted to double check before to write an entire answer based on wrong beliefs – Sheik Yerbouti Mar 10 at 18:44
• @SheikYerbouti It will only be called once. The function passed to it is not actually the function defined by the liar, but a wrapper around it. – Artemis Mar 10 at 21:43

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.

• Spoken like a true Pythonista. – StackMeter Apr 20 at 19:19

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.

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

• This is very much like what I had in mind, my bets are on it being the best guesser – Leo Mar 14 at 0:22

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.

• I wonder if this submission could be optimised. It currently takes around 0.08s per game on my laptop, and that's not counting the time taken by the liar. With three liars, each guesser plays 768 games, so 0.08s per game is over a minute in total. And that's just with one repetition, by default the runner does 10. – Artemis Mar 12 at 17:40
• If I understand correctly: the score for any number is the number of the most recent guess that returned a result which would make it possible for that number to be the secret. However, the code only cares about numbers where their score is the max score, ie where the most recent guess returned a result favouring that number. So we just need to find the midpoint of the numbers the most recent guess said were possible. However, I tried implementing this and it did much worse. What did I get wrong? – Artemis Mar 12 at 17:59
• – Artemis Mar 12 at 18:00
• I've clearly misunderstood your algorithm as max_score is rarely near len(previous). However, here's a less radically optimised version that gets the same results but brings execution time down to 0.01s: paste.artemisdev.xyz/savev.py – Artemis Mar 12 at 18:24
• i will try to optimize them maybe later. they could be optimized by cache the score instead of calculate them everytime. i will have a look on your pastebin later when i have full internet access. – tsh Mar 13 at 6:01

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.

• An instance of random.Random is not a callable that returns a number between 0 and 1. You can get that functionality by called self.rng.random(), but the random library provides a lot of utilities to simplify random number generation, for example self.rng.randint(1, 100). See the docs here. – Artemis Mar 11 at 18:40
• Thank you for the help, I discovered that python have a lot of random methods – Sheik Yerbouti Mar 12 at 12:55

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

• total = weight = 0. neither of these are ever used? – Artemis Mar 12 at 17:00
• Also, I wonder if this could be optimised, it currently takes 0.014s per game on my laptop (10s for a tournament against 3 liars, 100s with 10 repetitions). – Artemis Mar 12 at 17:42

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 ^^"

• Thanks for being truthful, but I'll still ask you 64 times :) – Citty Mar 18 at 13:41
• Similar to tsh's solution but same direction no matter odd or even – l4m2 Mar 19 at 4:52
• @l4m2 nope, this is exactly the opposite of tsh's solution (and performs much worse) – Leo Mar 19 at 5:24

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!

• Please give your submission a title (eg. "my awesome guesser") – Artemis Mar 18 at 22:12

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

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


• You're missing imports for the type hints – Artemis Mar 12 at 18:40
• Thanks I totally missed that! Now everyone knows how often i use type hints :P – M Virts Mar 13 at 4:50
• Please use rng.gauss instead of random.gauss so that results are replicable with the same seed. – Artemis Mar 13 at 12:36
• Thanks again! I didn’t read the docs on random well enough... I thought it would be tied to rng for some reason. – M Virts Mar 13 at 23:38
• NameError error: name 'u' is not defined Did you mean ub? – Artemis Mar 14 at 10:57

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.

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:
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).

• Maybe you have some typo in your post. 1. indention of first line is incorrect. 2. secret used in __call__ is not defined in its scope. Maybe you want self.secret. 3. Maybe you need to swap 1 and -1 in your post? I'm not sure what you are going to do with it. – tsh Mar 12 at 4:02
• Yep, I got all those things wrong. Thanks! – Spitemaster Mar 12 at 14:47
• You're missing import random for the type hint. – Artemis Mar 12 at 18:39
• Why # Should never happen? Surely it will happen if the guesser guesses your fake secret. – Artemis Mar 14 at 10:53
• @Artemis because self.secret is not an integer. If the guesser wants to try and target me and guesses correct, then bully for them! – Spitemaster Mar 14 at 18:18

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.

• low, high, guess and res are out of scope for write access inside makeAguess You can add the line nonlocal low, high, guess, res to the start of makeAguess to get access to them. PEP 3104. – Artemis Mar 11 at 18:43
• I added the line, thank you very much! – Sheik Yerbouti Mar 11 at 19:08
• It is now throwing RecursionError error: maximum recursion depth exceeded while calling a Python object. The default limit for recursion in Python is 1000 (low enough that the game won't end first, high enough that if your submission were working correctly it wouldn't hit it). I recommend getting the runner set up so you can test for yourself. It has no dependencies except Python, so it shouldn't be too hard. – Artemis Mar 11 at 19:15
• All right, I am going to try it. Thanks for the support – Sheik Yerbouti Mar 11 at 19:20

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.

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.

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
self.low = guess + 1
else:
self.high = guess - 1


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?

• You forgot to import random and defaultdict:) – Artemis Mar 20 at 12:18
• @Artemis forgot to import random, defaultdict import was just in the class as I was using the TIO runner, fixed! – Citty Mar 22 at 13:02

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.