18
\$\begingroup\$

The bots are looking for love. Can you help them?

The rules

The goal of this game is find the bot you have the highest compatibility with. However, robots, who are inexperienced at dating are unable to tell how well a date went.

In the game, bots take turns "speed dating" some other bot. After each date, each bot chooses whether to get married or to continue dating. If both bots agree to get married both are removed from the dating pool and their compatibility rank (100% is if you found the best one, 0% for the worst one) is their final score.

Bots won't be able to tell what the compatibility is, but they can compare dates. For example if bot A went on a date with bot B and C, they'll be able to tell if B or C was more compatible but not by how much.

Bot A's compatibility with B does not equal B's compatibility with A, but they are correlated.

If every bot has dated every other bot, the ordering is shuffled and any remaining bots can try again. However, everyone's final score is reduced by 25% (exponential) for every round they stay single. If a entire round ends without any new marriages the game ends and all remaining bots get a score of 0.

Example bot

class BetterThanFirst:
    """
    This bot will use its first date as a reference, then marry any bot that's better than it
    """

    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.first_date = None

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        pass # called if a full round finished, optional

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.first_date is None:
            self.first_date = other
        else:
            return other > self.first_date

Other rules

  • No IO
  • No RNG except via the provided PRNG
  • No inspecting other bots. You are only allowed to use the >, <, <=, >=, == operators on other bots.
  • No exploiting the controller.

Controller

enter image description here

The controller repo is here: https://codeberg.org/Mousetail/KOTH-dating-game

Results, and the active game (if any) can be viewed here: https://koth.mousetail.nl/

\$\endgroup\$
19
  • 1
    \$\begingroup\$ Does compatability change in-between rounds or games? \$\endgroup\$ Apr 12, 2023 at 8:42
  • 1
    \$\begingroup\$ @justhalf It's 30 games. \$\endgroup\$
    – brendan
    Apr 14, 2023 at 8:36
  • 1
    \$\begingroup\$ @gsitcia It's a newly initialized instance of the bot each game, so I guess the answer is no? \$\endgroup\$
    – brendan
    Apr 14, 2023 at 8:37
  • 1
    \$\begingroup\$ @mousetail Right now the theoretically optimal strategy of "lower your threshold for acceptance in later rounds to avoid being left alone" is not very beneficial, since most of the dating pool that's still around in round 3 is bitter bots who would rather die alone than settle. (I'm sure there is no analogy to real life here...) Although I have ideas for more variations, I don't want to flood the field with my bots, and it seems especially fraught since I know that this would boost my existing bots in the rankings. (I have tested on a local server.) How much do you think is too much? \$\endgroup\$
    – brendan
    Apr 14, 2023 at 8:50
  • 1
    \$\begingroup\$ @brendan If every bot you submit has a meaningfully different strategy, and competes for it's own win rather than only serving to help other bots, you are free to submit as many bots as you like. It's ok if your bots incidentally help each-other as long as they primarily are trying to win themselves. \$\endgroup\$
    – mousetail
    Apr 14, 2023 at 8:53

19 Answers 19

7
\$\begingroup\$

Optimal Average

class OptimalAverage:
    def __init__(self, nrof_bots, rng):
        self.test_num = round((nrof_bots - 1)**0.5)
        self.tests = []

    def round_finished(self, nrof_remaining_bots):
        self.test_num = round((nrof_remaining_bots - 1)**0.5)
        self.tests = []

    def date(self, other) -> bool:
        if len(self.tests) < self.test_num:
            self.tests.append(other)
            return False
        else:
            return all(f <= other for f in self.tests)

Similar to @Spitemaster's answer but we skip the first \$\sqrt{n}\$ bots instead. While their strategy has been proven optimal for maximizing one's chance at getting the best candidate, this strategy is optimal for obtaining the best average score assuming that there is value in candidates that are not the best, which is the case here. Of course this still misses the same important notes; that the opposing bot won't always agree, and that bots will be dropping out as it goes along.

\$\endgroup\$
1
  • \$\begingroup\$ A game has started, come watch if you are interested: koth.mousetail.nl \$\endgroup\$
    – mousetail
    Apr 11, 2023 at 18:32
6
\$\begingroup\$

Optimal Stopping Time

class OptimalStoppingTime:
    def __init__(self, nrof_bots, rng):
        import math
        self.dates_left = math.ceil((nrof_bots - 1)/ 2.718)
        self.dates = []

    def round_finished(self, nrof_remaining_bots):
        pass

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.dates_left > 0:
            self.dates_left -= 1
            self.dates += [other]
        else:
            return all(other >= x for x in self.dates)

The optimal stopping time for the secretary problem is to skip the first n/e and then accept any better than the best seen so far. There may be a better strategy because it's not symmetric and other bots may not agree - and it doesn't account for bots dropping out.

\$\endgroup\$
6
  • \$\begingroup\$ Importing something seems to have exposed some bugs with my controller :/ \$\endgroup\$
    – mousetail
    Apr 11, 2023 at 18:21
  • \$\begingroup\$ @mousetail My python is rusty... might work now (I moved the import inside the function, so it shouldn't cause any more problems). \$\endgroup\$ Apr 11, 2023 at 22:26
  • 2
    \$\begingroup\$ Interesting point about dropout. In the usual secretary problem, N is the entire population of candidates that can be interviewed. But here, we can't expect to ever see all N candidates, since many will be paired up by the time we've gone on many dates. I suppose you could modify this to find the expected stopping time of this strategy with N candidates, and use that as a modified input - with candidates dropping out of the pool, we can't afford to wait as long. Of course, how long to wait will depend on other candidates' own strategies, which vastly complicates matters. \$\endgroup\$ Apr 12, 2023 at 16:00
  • \$\begingroup\$ @NuclearHoagie I'd be very interested to see your modified version submission \$\endgroup\$
    – mousetail
    Apr 12, 2023 at 18:22
  • 1
    \$\begingroup\$ @mousetail I made a terrible mistake and did > rather than >=. Should be much better now. \$\endgroup\$ Apr 12, 2023 at 18:41
4
\$\begingroup\$

Naive Elitist

class NaiveElitist:
    def __init__(self, nrof_bots, rng):
        self.best = None
    
    def round_finished(self, nrof_remaining_bots):
        pass
    
    def date(self, other) -> bool:
        if self.best is None or other >= self.best:
            self.best = other
        return other >= self.best

This bot will settle for nothing less than the best!

...But it can't imagine that anything better than what it's already found could be possible, even if it's only experienced a single date.

\$\endgroup\$
2
  • \$\begingroup\$ Nice job, you are currently ranked #3 \$\endgroup\$
    – mousetail
    Apr 12, 2023 at 7:21
  • \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Apr 12, 2023 at 13:22
4
\$\begingroup\$

Crossing out options

class crossing_out_options:
    """accepts any bot at least as good as the best remaining bot which it hasn't accepted yet"""
    def __init__(self, nrof_bots, rng):
        self.candidates = []
        self.rejected_me = []
        self.pool = []
        self.first_date = True
    def round_finished(self, nrof_remaining_bots):
        self.candidates = [x for x in self.candidates if x in self.pool]
        self.pool = []
    def date(self, other) -> bool:
        self.pool += [other]
        if self.first_date:
            self.candidates = [other]
            self.first_date = False
            return False
        if other in self.rejected_me:
            return True  # no shame
        if all(other >= x for x in self.candidates):
            self.candidates = [x for x in self.candidates if x != other]
            self.rejected_me += [other]
            return True
        if not other in self.candidates:
            self.candidates += [other]
        return False

This bot keeps a list of all the "candidate" bots it has dated but not accepted, and which ones it tried to accept. It accepts the best bot from the candidate list. (Or any better bot, even if they rejected it before! No grudges!). At the end of the round it removes bots from the candidate list if it didn't encounter them this round.

The result is that it accepts any bot that "better than first" would accept, but learns and moves on if its best matches are already taken or don't love it back.

\$\endgroup\$
3
\$\begingroup\$

Always Accepts

class EveryoneIsFine:
    """This bot just accepts everyone"""
    def __init__(self, nrof_bots, rng):
        self.botmotto="Accept everyone."
    def round_finished(self, nrof_remaining_bots):
        pass
    def date(self, other) -> bool:
        return True

This bot just doesn't care who they're married to.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ You might have noticed this is already a example bot \$\endgroup\$
    – mousetail
    Apr 11, 2023 at 17:08
  • 1
    \$\begingroup\$ @mousetail really? i dont think so. \$\endgroup\$ Apr 11, 2023 at 17:11
  • 1
    \$\begingroup\$ @mousetail and i cant get poetry to work... \$\endgroup\$ Apr 11, 2023 at 17:11
  • \$\begingroup\$ Yes it is, it's added if the bot count is odd \$\endgroup\$
    – mousetail
    Apr 11, 2023 at 17:12
  • 4
    \$\begingroup\$ @Hippopotomonstrosesquipedalian it's here btw \$\endgroup\$
    – The Thonnu
    Apr 11, 2023 at 17:26
3
\$\begingroup\$

C+ dater

class c_plus_dater:
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.round = 0
        self.betterbots = 0
        self.bestbot = None

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        self.round += 1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        marry = False
        if self.bestbot is None:
            self.bestbot = other
        else:
            if other > self.bestbot:
                self.betterbots += 1
                self.bestbot = other
                if self.betterbots >= 3:
                     marry = True
        return marry

Edited to avoid comparing a bot to a constant, instead only to each other. This bot takes any bot that is better than at least 3 other bots. But it probably gets buggy in the second round.

Old version: Bot takes anything above 70% in the first round, and lowers its standard each round after that.

[I'm counting on compatibility being between 0 and 1]

\$\endgroup\$
5
  • \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Apr 13, 2023 at 5:33
  • \$\begingroup\$ You can't actually know the value of each bot, you are only able to compare them to other bots \$\endgroup\$
    – mousetail
    Apr 13, 2023 at 5:45
  • \$\begingroup\$ Ah, so that's a rule we have to follow in our answer, not built into the interface \$\endgroup\$
    – tim654321
    Apr 13, 2023 at 23:06
  • \$\begingroup\$ @tim654321 It's built into the interface, the "bot" you get is generated with funktools.cmp_to_key so it's actually very hard/impossible to extract the key used to generate it \$\endgroup\$
    – mousetail
    Apr 14, 2023 at 5:18
  • \$\begingroup\$ I guess after round 1 self.bestbot will actually be the best bot, so other > self.bestbot will be False even when other == self.bestbot. Sigh, another bot with unrealistic expectations for love. ;-) \$\endgroup\$
    – brendan
    Apr 14, 2023 at 8:35
3
\$\begingroup\$

Logger

class Logger:
 """Logs how everyone was on the first round (rejecting all) and uses that to determine the best bot."""
 def __init__(self, nrof_bots, rng):
  self.botlist=[]
  self.counter=0
  self.bots=nrof_bots
 def round_finished(self, nrof_remaining_bots):
  self.counter=self.counter+1
  if nrof_remaining_bots!=self.bots:
   self.counter=0
   self.bots=nrof_remaining_bots
 def date(self, other):
  if self.counter==0:
   self.botlist.append(other)
   return False
  else:
   return other==max(self.botlist)

This bot gets the best bot by logging each bot and picking the one with the best compatibility. If the bot with the best compatibility marries a bot other than the Logger, the Logger is screwed the logger only notices at the end of the round and re-evaluates each bot.

\$\endgroup\$
7
  • \$\begingroup\$ Traceback (most recent call last) File "/home/mousetail/SideProjects/dating_game_koth/game.py", line 138, in date bot2.instance.date( File "Logger.py", line 12, in date if counter == 0: NameError: name 'counter' is not defined \$\endgroup\$
    – mousetail
    Apr 12, 2023 at 8:38
  • 1
    \$\begingroup\$ You probably want self.counter \$\endgroup\$
    – mousetail
    Apr 12, 2023 at 8:38
  • \$\begingroup\$ New error: Traceback (most recent call last) File "/app/KOTH-dating-game/game.py", line 138, in date bot2.instance.date( File "Logger.py", line 16, in date return other == max(self.botlist) ValueError: max() arg is an empty sequence \$\endgroup\$
    – mousetail
    Apr 12, 2023 at 8:53
  • 1
    \$\begingroup\$ if counter==0 should be if self.counter==0 and the return False within that if-statement should be after the self.botlist.append(other). \$\endgroup\$ Apr 12, 2023 at 9:35
  • \$\begingroup\$ @KevinCruijssen fixed \$\endgroup\$ Apr 12, 2023 at 10:39
3
\$\begingroup\$

The Hopeless Romantic

This hopelessy romantic bot falls in love with the first robot it ever sees, and will pursue its subject of aspirations til the end of times. Which, it turns out, is quite long for robots.

class HopeLessRomantic:
    """
    This hopelessy romantic bot falls in love with the first robot it ever sees, and will pursue its subject of aspirations til the end of warranty. Which is long for robots.
    """

    def __init__(self, nrof_bots, rng):
        # nrof_bots is the total number of bots playing
        self.firstlove= None

    def round_finished(self, nrof_remaining_bots):
        #alas! the light of my live has rejected me. *sad robot noise*
        pass 

    def date(self, other) -> bool:  
        if self.firstlove is None:
            self.firstlove= other              # madly fall in robolove
            return True
        elif self.firstlove==other:
            return True
        else:
            return False
\$\endgroup\$
6
  • \$\begingroup\$ Did you want to return true if you met your first love again? \$\endgroup\$
    – mousetail
    Apr 14, 2023 at 14:58
  • \$\begingroup\$ Yes. This bot is hopelessly in love at first sight. Tragically pursuing the love that can not be if it is rejected. \$\endgroup\$
    – MPIchael
    Apr 14, 2023 at 21:07
  • \$\begingroup\$ Your bot has been added to the game and you are under no obligation to change anything. However, you might consider the case where your soulmate is still single in the second round and you can run in to them again \$\endgroup\$
    – mousetail
    Apr 14, 2023 at 21:08
  • 1
    \$\begingroup\$ Yes. I changed it so the bot recognizes its first love:-) thanks for the hint! \$\endgroup\$
    – MPIchael
    Apr 14, 2023 at 21:10
  • \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Apr 14, 2023 at 21:10
3
\$\begingroup\$

Optimal Cutoffs

import math
    
def value(n, k, j):
    return sum(i*math.comb(i,j)*math.comb(n-i-1,k-j-1) for i in range(j,n-k+j+1)) / math.comb(n,k)

def get_cutoff(n, k0):
    cutoff = {}
    for k in range(n,0,-1):
        if k >= k0: bst = 0
        z=0
        cutoff[k] = k
        for j in range(k-1,-1,-1):
            v = value(n,k,j)
            if v > bst:
                z += v
            else:
                cutoff[k] = j+(v<bst)
                z += (j+1)*bst
                break
        bst=z/k
    return cutoff

class OptimalCutoffs:
    def __init__(self, nrof_bots, rng):
        self.first_round = True
        n = nrof_bots - 1
        self.cutoff = get_cutoff(n, int(n * 3/4))
        self.met = []
    def round_finished(self, nrof_remaining_bots):
        self.first_round = False
    def date(self, other):
        if not self.first_round: return True
        self.met.append(other)
        self.met.sort()
        if self.met.index(other) >= self.cutoff[len(self.met)]:
            self.met.remove(other)
            return True
        else:
            return False

Uses dynamic programming to calculate the optimal cutoffs assuming the bot will meet 3/4 of the other bots, the other bot will always accept, and there is no payoff after the first round. Always accepts in rounds after the first.

\$\endgroup\$
1
  • \$\begingroup\$ Well done, you are now #1 \$\endgroup\$
    – mousetail
    Apr 17, 2023 at 13:08
2
\$\begingroup\$

Third Time Lucky

class ThirdTimeLucky:
    """Picks the bot from the third date"""
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        self.number = 1

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        self.number = 1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        if self.number >= 3:
            self.number = 1
            return True
        else:
            self.number += 1
            return False

This bot believes that three dates is the correct number to go on and will be happy to marry the third bot. If the other bot refuses, then they go on another three dates, accepting only the third.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ You don't need to end lines with semicolons in python, and true and false are spelled True and False in python \$\endgroup\$
    – mousetail
    Apr 12, 2023 at 5:23
2
\$\begingroup\$

Lower standards

class lower_standards:
    def __init__(self, nrof_bots, rng):
        self.sample_size = round((nrof_bots-1)**0.5)
        self.sample = [] # sample of dates (from the first round)
        self.curr = [] # all dates from the current round
        self.prev = [] # all dates from the previous round
        self.pool = nrof_bots - 1 # size of the dating pool
        self.round = 0 # round number
    def round_finished(self, nrof_remaining_bots):
        self.pool = nrof_remaining_bots - 1
        self.prev = self.curr
        self.curr = []
        self.round += 1
    def date(self, other) -> bool:
        self.curr += [other]
        if self.round == 0 :
            if len(self.sample) < self.sample_size :
                self.sample += [other]
                return False
            if all(other >= x for x in self.sample) :
                return True
        else :
            if sum(x > other for x in self.prev) <= len(self.prev) - self.pool + self.round - 1:
                return True
        return False

In the first round, this bot behaves like OptimalAverage.

On the second round, it behaves like a much more pessimistic version of Logger. Rather than assuming the current dating pool is the same as in the previous round, it takes into account that some bots have left. When the round ends, it looks at the number of bots still in the dating pool, and assumes that the remaining options are the worst possible subset of the previous round. It then accepts any bot which would be best in this reduced pool.

On the third and subsequent rounds, it becomes even less picky, accepting second best in the pessimistically reduced pool, then 3rd best, etc.

\$\endgroup\$
1
  • \$\begingroup\$ Good job, you are currently ranked #2 \$\endgroup\$
    – mousetail
    Apr 13, 2023 at 13:18
2
\$\begingroup\$

Wait for it...

class wait_for_it:
    """always rejects in the first round,
     then only accepts the top 2 it saw in the previous round,
     until it sees that the game is about to end,
     at which point it panics and accepts anyone."""
    def __init__(self, nrof_bots, rng):
        self.pool_size = nrof_bots
        self.curr = []  # all dates from the current round
        self.prev = []  # all dates from the previous round
        self.end_count = 0  # number of rounds with no matches made
    def round_finished(self, nrof_remaining_bots):
        if nrof_remaining_bots == self.pool_size:
            self.end_count += 1
        else:
            self.end_count = 0
        self.pool_size = nrof_remaining_bots
        self.prev = self.curr
        self.curr = []
    def date(self, other) -> bool:
        self.curr += [other]
        if not self.prev:
            return False
        if self.end_count == 2:
            return True
        if sum(x > other for x in self.prev) <= 1:
            return True
        return False

This bot is always a step behind. In each round, it will accept either of the top 2 matches it saw in the previous round. However, it also keeps tabs on the end condition, and if two rounds have gone without a match being made, it will accept anyone to avoid ending up alone.

\$\endgroup\$
3
  • \$\begingroup\$ I guess you have improved my logger. \$\endgroup\$ Apr 14, 2023 at 17:41
  • \$\begingroup\$ I didn't look at logger's code carefully enough at first, I didn't realize that it re-made its log when the size of the dating pool changed. I think that makes it the first bot in the competition to have that kind of logic! For sure, this is a similar idea, but less picky. \$\endgroup\$
    – brendan
    Apr 15, 2023 at 7:48
  • \$\begingroup\$ I actually updated the bot to have that at some point. \$\endgroup\$ Apr 17, 2023 at 11:36
2
\$\begingroup\$

Optimal Desperation

class optimal_desperation:
    """
    starts out believing in a beautiful theorem it heard about,
    but if that doesn't work out, it takes what it can get
    """
    def __init__(self, nrof_bots, rng):
        import math
        self.dates_left = math.ceil((nrof_bots-1)/2.718)
        self.best = None
        self.desperate = False
    def round_finished(self, nrof_remaining_bots):
        pass
    def date(self, other) -> bool:
        if self.desperate:
            return True
        if self.best is None:
            self.best = other
            self.dates_left -= 1
            return False
        if self.dates_left > 0:
            self.dates_left -= 1
            self.best = max(other, self.best)
            return False
        if other >= self.best:
            self.desperate = True
            return True
        return False

Inspired by Spitemaster's Optimal Stopping Time, but when its optimally true love rejects it, it gets desperate and says "yes" to anyone and everyone.

\$\endgroup\$
2
\$\begingroup\$

Partygoer

While sober, the partygoer doesn't care for dating. However, it likes meeting new people, so, just for the sake of it, the partygoer decided to join the - hey, look! Beer!

class Partygoer:
    """
    Decides when to marry depending on how sober it is. Then, it drinks.
    """

    def __init__(self, nrof_bots, rng):
        self.sobriety = 1.0
        self.rng = rng

    def round_finished(self, nrof_remaining_bots):
        self.sobriety -= .05

    def date(self, other) -> bool:
        limit = self.rng.random()
        flag = False
        if limit > self.sobriety:
            flag = True
        self.sobriety -= 0.01
        return flag

Uses the PRNG to decide a limit. Every time it goes on a date, it checks its sobriety. If it's greater than the limit, it decides to marry. Regardless, though, it takes a drink, decreasing its sobriety a little. If an entire round goes past without getting married, it decreases sobriety by a larger margin.

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf, and nice bot! \$\endgroup\$ Apr 16, 2023 at 22:47
  • \$\begingroup\$ Your bot has been added \$\endgroup\$
    – mousetail
    Apr 17, 2023 at 5:15
1
\$\begingroup\$

Anything but the worst

class AnythingButTheWorst:
    """
    Will accept anyone as long as there is someone worse
    """

    # rng is a seeded PRNG you can use, no other forms of randomness allowed
    def __init__(self, nrof_bots, rng):
        # nrof_bots is the total number of bots playing
        self.worst = None

    # the number of bots still in the game
    def round_finished(self, nrof_remaining_bots):
        pass  # called if a full round finished, optional

    def date(self, other) -> bool:  # Return True if you want to marry this bot, False otherwise
        if self.worst is None:
            self.worst = other
        else:
            self.worst = min(self.worst, other)

        return other > self.worst

Will settle for any bot except the worst one.

\$\endgroup\$
1
\$\begingroup\$

Adaptive Better-than-median

class adaptive_better_than_median:
    """
    accepts bots better than the median,
    while updating the median as the game evolves
    """
    def __init__(self, nrof_bots, rng):
        self.curr = []
        self.prev = None

    # the number of bots still in the game
    def round_finished(self, nrof_remaining_bots):
        self.prev = self.curr
        self.curr = []

    def date(self, other) -> bool:
        self.curr += [other]
        if self.prev is None:
            return sum(other > x for x in self.curr) >= len(self.curr)//2
        return sum(other > x for x in self.prev) >= len(self.curr)//2

Just what the name says; behaves in the first and second rounds like "Better than Median", but then adjusts the median based on who dropped out in previous rounds.

\$\endgroup\$
1
\$\begingroup\$

Top Three Previous

class TopThreePrevious:
    """
    Will marry any of the top three it has seen from the previous round.
    If it's the first round, it flips a coin instead.
    """

    def __init__(self, nrof_bots, rng):
        self.rng = rng
        self.best = []
        self.previousBest = []
        self.bots = []

    def round_finished(self, nrof_remaining_bots):
        self.best = []
        self.bots.sort(reverse = True)
        for i in range(3):
            self.best.append(self.bots[i])
        self.bots = []

    def date(self, other) -> bool:
        self.bots += [other]
        if len(self.best) == 0:
            return self.rng.random()>0.5
        return other in self.best

This bot simply checks if the bot it's currently dating was one of the top three it has seen in the previous round, or flips a coin if it's the first round (it uses the length of self.best to determine this).

\$\endgroup\$
1
  • \$\begingroup\$ Your bot has been added to the site, sorry for the delay \$\endgroup\$
    – mousetail
    May 2, 2023 at 6:57
1
\$\begingroup\$

T

*** not working ***

class T:
    def __init__(self, nrof_bots, rng):
        self.NR    =  nrof_bots
        self.d     =  {}
        self.mc    =  0
        self.r     = 1
        self.rc    = 1
        self.xrs   = []               # unseen in current round
        self.x     = set()            # seen in previous round
        self.xn    = []               # seen in this round
        self.c     =  0              # for debugging
    def update(self, other):
        self.c += 1
        self.rc += 1
        if other not in self.d: self.d[other] = 0 # Set if new
        self.d[other] += 1
        self.mc = max(self.mc, self.d[other])     # Highest number seen
        if self.mc > self.r: # update round
            missing_in_round = set(self.x).difference(set(self.xn))
            NR_ = self.NR - len(missing_in_round)
            self.NR = NR_
            self.r = self.mc                         # set round
            self.x = set(self.xn)                        # seen in prev round
            self.xrs = self.xn                           # All are unseen
            self.xn = []                                 # reset round
            self.rc = 1
        self.xn.append(other)
        xrs_ = set(self.xrs).difference({other})      # update unseen
        self.xrs  = list(xrs_)
        self.xrs.sort()                               # sort unseen

    def get1(rc, NR, xrs, xn):
         average_acceptance = 0.3
         N_ = NR - rc * 0.3
         dec = 0.7 * N_ / (N_+ 1)
         return dec

    def getd(rc, NR, xrs, xn):
        if len(xrs) == 0: # end of round
            xn_ = xn.copy()
            xn_.sort()
            dec = xn_[round(len(xn_) * 0.7)]
        else:
            dec = xrs[min(round(NR*0.7 - rc*0.14), len(xrs) - 1)]
        return dec

    def round_finished(self, nrof_remaining_bots):
        return None

    def date(self, other): # Return True if you want to marry this bot, False otherwise
        self.update(other)
        espouse = other >= (T.getd,T.get1)[self.r==1](self.rc, self.NR, self.xrs, self.xn)
        print(f'{self.c}:{other:3.2f} :::{espouse}')
        return espouse

\$\endgroup\$
4
  • \$\begingroup\$ Your bot has been added to the site, sorry for the delay \$\endgroup\$
    – mousetail
    May 2, 2023 at 6:57
  • \$\begingroup\$ Thanks for your impressive and inspiring work! Just noticed there was an (for me unexpected error): if other not in self.d: TypeError: unhashable type: 'functools.KeyWrapper' \$\endgroup\$
    – Hunaphu
    May 2, 2023 at 14:04
  • \$\begingroup\$ Btw your bot crashes currenly because bots are not hashable \$\endgroup\$
    – mousetail
    May 2, 2023 at 14:05
  • \$\begingroup\$ Sorry for my misunderstanding, I thought other was a number. Please remove it and sorry for the inconvenience. \$\endgroup\$
    – Hunaphu
    May 2, 2023 at 14:08
1
\$\begingroup\$
class IDK_bot:
    """
    This bot will use its first date as a reference, then marry any bot that's better than it
    """
    def __init__(self, nrof_bots, rng): # rng is a seeded PRNG you can use, no other forms of randomness allowed
        # nrof_bots is the total number of bots playing
        import math
        self.rng=rng
        self.numbots=nrof_bots
        self.dates=[]
        self.cutoff=int(self.numbots/math.e)**(4/5))
        self.num=0
        self.rounds=0

    def round_finished(self, nrof_remaining_bots): # the number of bots still in the game
        import math
        self.numbots=nrof_remaining_bots
        self.cutoff=int(self.numbots/math.e)**(4/5))
        self.rounds+=1

    def date(self, other) -> bool: # Return True if you want to marry this bot, False otherwise
        self.dates.append(other)
        self.dates.sort()
        self.num+=1
        if self.num<self.cutoff:
            return False
        score=self.dates.index(other)/self.num
        if score<0.5:
            return False
        return self.rng.random()<=score*(self.num/self.bots*1.2)**(1/3)*(1+self.rounds/5)

The bot defines a "cutoff" based on the n/e rule which has been proven to be approximately optimal for the secretary problem. However, since you aren't guaranteed to see every possible date, that limit is raised to the 4/5th power (an arbitrary number I selected) to give more potential candidates to select.

The actual selection is based on RNG. The bot first calculates the date's score, which is the relative ranking of the date in relation to the other dates it has seen, represented as a number from 0 to 1. The bot rejects any candidate with a score less than 0.5. The bot multiplies the score by a bunch of math, effectively taking into account the fraction of dates seen so far and how many rounds it has been in.

This lets the "score" be the largest part in deciding whether or not to accept a candidate, but also makes it so that the probability of acceptance increases as more bots are seen and as more rounds pass.

I haven't been able to test this, so please let me know if there are any bugs I need to fix.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.