32
\$\begingroup\$

Final Result

The competition is over. Congratulations to hard_coded!

Some interesting facts:

  • In 31600 out of 40920 auctions (77.2%), the winner of the first round won the most rounds in that auction.

  • If example bots are included in the competition, the top nine places won't change except that AverageMine and heurist will swap their positions.

  • Top 10 results in an auction:

[2, 2, 3, 3] 16637
[0, 3, 3, 4] 7186
[1, 3, 3, 3] 6217
[1, 2, 3, 4] 4561
[0, 1, 4, 5] 1148
[0, 2, 4, 4] 1111
[2, 2, 2, 4] 765
[0, 2, 3, 5] 593
[1, 1, 4, 4] 471
[0, 0, 5, 5] 462
  • Tie count (number of auctions that the i-th round had no winner): [719, 126, 25, 36, 15, 58, 10, 7, 19, 38].

  • Average winning bid of the i-th round: [449.4, 855.6, 1100.8, 1166.8, 1290.6, 1386.3, 1500.2, 1526.5, 1639.3, 3227.1].

Scoreboard

Bot count: 33
hard_coded            Score: 16141  Total: 20075170
eenie_meanie_more     Score: 15633  Total: 18513346
minus_one             Score: 15288  Total: 19862540
AverageMine           Score: 15287  Total: 19389331
heurist               Score: 15270  Total: 19442892
blacklist_mod         Score: 15199  Total: 19572326
Swapper               Score: 15155  Total: 19730832
Almost_All_In         Score: 15001  Total: 19731428
HighHorse             Score: 14976  Total: 19740760
bid_higher            Score: 14950  Total: 18545549
Graylist              Score: 14936  Total: 17823051
above_average         Score: 14936  Total: 19712477
below_average         Score: 14813  Total: 19819816
Wingman_1             Score: 14456  Total: 18480040
wingman_2             Score: 14047  Total: 18482699
simple_bot            Score: 13855  Total: 20935527
I_Dont_Even           Score: 13505  Total: 20062500
AntiMaxer             Score: 13260  Total: 16528523
Showoff               Score: 13208  Total: 20941233
average_joe           Score: 13066  Total: 18712157
BeatTheWinner         Score: 12991  Total: 15859037
escalating            Score: 12914  Total: 18832696
one_upper             Score: 12618  Total: 18613875
half_in               Score: 12605  Total: 19592760
distributer           Score: 12581  Total: 18680641
copycat_or_sad        Score: 11573  Total: 19026290
slow_starter          Score: 11132  Total: 20458100
meanie                Score: 10559  Total: 12185779
FiveFiveFive          Score: 7110   Total: 24144915
patient_bot           Score: 7088   Total: 22967773
forgetful_bot         Score: 2943   Total: 1471500
bob_hater             Score: 650    Total: 1300
one_dollar_bob        Score: 401    Total: 401

In this game, we will simulate a sealed-bid auction.

Each auction is a 4-player game, consists of 10 rounds. Initially, players have no money. At the start of each round, each player will get $500, and then make their own bids. The bid can be any non-negative integer less or equal than the amount they have. Usually, one who bid the highest win the round. However, to make things more interesting, if several players bid the same price, their bid won't be taken into account (thus can't win the round). For example, if four players bid 400 400 300 200, the one bids 300 wins; if they bid 400 400 300 300, no one wins. The winner should pay what they bid.

Since it is a "sealed-bid" auction, the only information player will know about the bidding is the winner and how much they paid when next round starts (so player can know how much everyone has).


Scoring

One auction will be held for every possible 4-player combination. That is, if there are N bots in total, there will be NC4 auction. The bot which wins the most rounds will be the final winner. In the case that there's a tie, the bot which paid the least in total will win. If there's still a tie, in the same way as the bidding, those ties will be removed.


Coding

You should implement a Python 3 class with a member function play_round (and __init__ or others if you need). play_round should take 3 arguments (including self). The second and third argument will be, in order: the id of winner of the previous round, followed by how much they paid. If no one wins or it is the first round, they will both be -1. Your id will always be 0, and id 1–3 will be other players in an order only determined by the position on this post.


Additional rules

1. Deterministic: The behavior of your function should depend only on the input arguments within an auction. That is, you can't access files, time, global variables or anything that will store states between different auctions or bots. If you want to use a pseudorandom generator, it's better to write it by yourself (to prevent affecting others' programs like random in Python lib), and make sure you have it reset with a fixed seed in __init__ or the first round.

2. Three Bots per Person: You're allowed to submit at most 3 bots, so you can develop a strategy to make your bots "cooperate" in some way.

3. Not Too Slow: Since there will be many auctions, make sure that your bots won't run too slow. Your bots should be able to finish at least 1,000 auctions in a second.


Controller

Here's the controller I'm using. All bots will be imported and added to bot_list in the order on this post.

# from some_bots import some_bots

bot_list = [
    #one_bot, another_bot, 
]

import hashlib

def decide_order(ls):
    hash = int(hashlib.sha1(str(ls).encode()).hexdigest(), 16) % 24
    nls = []
    for i in range(4, 0, -1):
        nls.append(ls[hash % i])
        del ls[hash % i]
        hash //= i
    return nls

N = len(bot_list)
score = [0] * N
total = [0] * N

def auction(ls):
    global score, total
    pl = decide_order(sorted(ls))
    bots = [bot_list[i]() for i in pl]
    dollar = [0] * 4
    prev_win, prev_bid = -1, -1
    for rounds in range(10):
        bids = []
        for i in range(4): dollar[i] += 500
        for i in range(4):
            tmp_win = prev_win
            if prev_win == i: tmp_win = 0
            elif prev_win != -1 and prev_win < i: tmp_win += 1
            bid = int(bots[i].play_round(tmp_win, prev_bid))
            if bid < 0 or bid > dollar[i]: raise ValueError(pl[i])
            bids.append((bid, i))
        bids.sort(reverse = True)
        winner = 0
        if bids[0][0] == bids[1][0]:
            if bids[2][0] == bids[3][0]: winner = -1
            elif bids[1][0] == bids[2][0]: winner = 3
            else: winner = 2
        if winner == -1:
            prev_win, prev_bid = -1, -1
        else:
            prev_bid, prev_win = bids[winner]
            score[pl[prev_win]] += 1
            total[pl[prev_win]] += prev_bid
            dollar[prev_win] -= prev_bid

for a in range(N - 3):
    for b in range(a + 1, N - 2):
        for c in range(b + 1, N - 1):
            for d in range(c + 1, N): auction([a, b, c, d])

res = sorted(map(list, zip(score, total, bot_list)), key = lambda k: (-k[0], k[1]))

class TIE_REMOVED: pass

for i in range(N - 1):
    if (res[i][0], res[i][1]) == (res[i + 1][0], res[i + 1][1]):
        res[i][2] = res[i + 1][2] = TIE_REMOVED
for sc, t, tp in res:
    print('%-20s Score: %-6d Total: %d' % (tp.__name__, sc, t))

Examples

If you need a pseudorandom generator, here is a simple one.

class myrand:
    def __init__(self, seed): self.val = seed
    def randint(self, a, b):
        self.val = (self.val * 6364136223846793005 + 1) % (1 << 64)
        return (self.val >> 32) % (b - a + 1) + a

class zero_bot:
    def play_round(self, i_dont, care): return 0

class all_in_bot:
    def __init__(self): self.dollar = 0
    def play_round(self, winner, win_amount):
        self.dollar += 500
        if winner == 0: self.dollar -= win_amount
        return self.dollar

class random_bot:
    def __init__(self):
        self.dollar = 0
        self.random = myrand(1)
    def play_round(self, winner, win_amount):
        self.dollar += 500
        if winner == 0: self.dollar -= win_amount
        return self.random.randint(0, self.dollar)

class average_bot:
    def __init__(self):
        self.dollar = 0
        self.round = 11
    def play_round(self, winner, win_amount):
        self.dollar += 500
        self.round -= 1
        if winner == 0: self.dollar -= win_amount
        return self.dollar / self.round

class fortytwo_bot:
    def play_round(self, i_dont, care): return 42

Result

all_in_bot           Score: 20     Total: 15500
random_bot           Score: 15     Total: 14264
average_bot          Score: 15     Total: 20000
TIE_REMOVED          Score: 0      Total: 0
TIE_REMOVED          Score: 0      Total: 0

The winner is all_in_bot. Note that zero_bot and fortytwo_bot have the same score and total, so they're removed.

These bots will not be included in the competition. You can use them if you think they are great.


The final competition will be held at 2017/11/23 14:00 (UTC). You can make any change to your bots before that.

\$\endgroup\$
  • 5
    \$\begingroup\$ Do they get 500 dollars each round, or each auction (that lasts 10 rounds)? \$\endgroup\$ – Stewie Griffin Nov 9 '17 at 14:45
  • 1
    \$\begingroup\$ @KamilDrakari competition will restart with the offending bot removed from the list. \$\endgroup\$ – Colera Su Nov 9 '17 at 16:59
  • 4
    \$\begingroup\$ @Shufflepants True, but this is always the case with KotH challenges. In the past some people indeed made a bot near the end to counter all bots up to that point. But it's just part of the KotH-style challenge. And the way most KotH-challenges work, this one included, the advantage won't be that great. You can only counter so many bots at the same time.. Nice first challenge, Colera Su, and welcome to PPCG! Looking forward to the results. :) \$\endgroup\$ – Kevin Cruijssen Nov 9 '17 at 22:09
  • 4
    \$\begingroup\$ Here's a test run on TIO with all of the current bots. \$\endgroup\$ – Steadybox Nov 11 '17 at 15:25
  • 2
    \$\begingroup\$ It's a tight race at the moment... \$\endgroup\$ – Zaid Nov 22 '17 at 18:46

34 Answers 34

3
\$\begingroup\$

average_joe

I'm not sure if I'm allowed to use a utility class or not, its below the bot class. (it's Tracker) Anyway, the bot bets 475 on the first round, and goes all in on the last round. In all the other rounds, it randomly chooses between beating the average winning bid, or beating the average current balance between all other bots.

MONEY_PER_ROUND = 500
NUM_ROUNDS = 10

class Random:
    def __init__(self, seed):
        self.val = seed
    def randint(self, a, b):
        self.val = (self.val * 6364136223846793005 + 1) % (1 << 64)
        return (self.val >> 32) % (b - a + 1) + a
    def choice(self, arr):
        return arr[self.randint(0,len(arr)-1)]

class average_joe:
    running_sum = 0

    def __init__(self):
        self.random = Random(42)

    def play_round(self, winner, winning_bid):
        if winner == -1 and winning_bid == -1:
            self.tracker = Tracker()
            self.tracker.next_round(money=MONEY_PER_ROUND)
            return 475
        else:
            self.tracker.next_round(money = MONEY_PER_ROUND)
            self.tracker.update_balance(winner, winning_bid)
            self.running_sum += winning_bid
            if self.tracker.rounds == NUM_ROUNDS:
                balance = self.tracker.get_balance(0)
                return balance
            else:
                strategy = self.random.choice([self.beat_mean_history, self.beat_mean_balance])
                return strategy()

    def beat_mean_history(self):
        mean = self.running_sum // self.tracker.rounds
        return max(min(mean + 2, self.tracker.get_balance(0)),0)

    def beat_mean_balance(self):
        mean = self.tracker.get_average_balance()
        return max(min(mean+2, self.tracker.get_balance(0)),0)

# Tracker utility class
class Tracker:
    def __init__(self):
        self.rounds = 0
        self.player_balance = dict.fromkeys(range(4), 0)

    def get_values(self):
        return [self.player_balance[player] for player in self.player_balance.keys()]

    def next_round(self, money=500):
        self.rounds += 1
        for player in self.player_balance.keys():
            self.player_balance[player] += money

    def get_balance(self, player):
        return self.player_balance[player]

    def update_balance(self, player, expense):
        self.player_balance[player] -= expense

    def get_average_balance(self):
        values = self.get_values()[1:]
        return round(sum(values) / len(values))
\$\endgroup\$
  • 1
    \$\begingroup\$ Right, my bad. Fixed. Thanks for the input! \$\endgroup\$ – coolioasjulio Nov 14 '17 at 21:42
3
\$\begingroup\$

Wingman 1

Provide a wingman for bid_higher, as protection. (Same algorithm, just slightly lower increment.)

class Wingman_1:
    def __init__(self):
        self.dollar = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.dollar += 500
        self.round += 1
        inc = 130
        if win_amount == 0: win_amount = 500
        if winner == 0: self.dollar -= win_amount
        if self.round == 10: return self.dollar
        if self.dollar > win_amount + inc:
            return win_amount + inc
        else:
            if self.dollar > 1: return self.dollar -1
            else:
                return 0
\$\endgroup\$
  • \$\begingroup\$ Your code won't work because you need indentation for the stuff in the class \$\endgroup\$ – HyperNeutrino Nov 14 '17 at 20:36
  • \$\begingroup\$ Thanks for pointing that out; I haven't got the hang of the {} code editing yet. \$\endgroup\$ – rancid_banana Nov 14 '17 at 20:42
  • 1
    \$\begingroup\$ Clever, I'd been worried the best answer was going to be sniped at the finish line by a duplicate but this form of protection works for at least some bots. \$\endgroup\$ – histocrat Nov 14 '17 at 21:16
  • 1
    \$\begingroup\$ @Steadybox:Thanks, fixed the all-in code. \$\endgroup\$ – rancid_banana Nov 14 '17 at 22:08
2
\$\begingroup\$
class one_dollar_bob:
  def play_round(x,y,z):
    return 1
\$\endgroup\$
2
\$\begingroup\$

Slow Starter

This bot starts with a bid of 0 in the first round, then 200, then 400, etc. It bids 200 more every round, or plays all-in if it doesn't have enough left anymore. It will also go all in in the final round.

class slow_starter:
  def __init__(self):
    self.money = 0
    self.round = -1
  def play_round(self, winner, win_amount):
    # Default actions:
    #  Collect 500 dollars
    self.money += 500
    #  If it was the winner: subtract the win_amount from his money
    if winner == 0:
      self.money -= win_amount
    #  One round further
    self.round += 1

    # If it's the final round or if it doesn't have enough money left: bid all in
    if self.round == 9 or self.round * 200 > self.money:
      return self.money
    # Else: bid 200 multiplied with the current round we're playing
    #  (Note: It bids 0 the first round)
    return self.round * 200

I never program in Python, so if you see any mistakes let me know..

\$\endgroup\$
  • 1
    \$\begingroup\$ Your check for the final round will fire on round 11, not 10. Same with your Half In bot. \$\endgroup\$ – Jeremy Weirich Nov 9 '17 at 21:16
  • \$\begingroup\$ @JeremyWeirich Thanks! Fixed. \$\endgroup\$ – Kevin Cruijssen Nov 9 '17 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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