First-price sealed-bid auction

32

11

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.

Colera Su

Posted 2017-11-09T14:29:39.293

Reputation: 2 291

5Do they get 500 dollars each round, or each auction (that lasts 10 rounds)? – Stewie Griffin – 2017-11-09T14:45:39.357

So just to make sure, between the 10 rounds you can store state right? – HyperNeutrino – 2017-11-09T14:46:17.547

@StewieGriffin they'll get 500 dollar each round. – Colera Su – 2017-11-09T14:52:06.343

@HyperNeutrino yes (or you won't even know how much you have). There's no winner in an auction. Overall winner should win the most rounds in all auctions. – Colera Su – 2017-11-09T14:54:05.200

If I make multiple bots, should they all be in one answer, or should I have separate answers? – Kamil Drakari – 2017-11-09T15:57:19.890

@KamilDrakari both are okay. – Colera Su – 2017-11-09T16:42:08.257

One more, what happens if an error occurs? For example, your controller raises a ValueError if an invalid bid is provided. Will the offending bot be disqualified while the remainder bots get to continue or would the entire competition need to be restarted? – Kamil Drakari – 2017-11-09T16:53:46.203

1@KamilDrakari competition will restart with the offending bot removed from the list. – Colera Su – 2017-11-09T16:59:42.467

Having to put the bot's code into an answer where everyone can see seems like there's a significant advantage to waiting until the last minute to post since I would think there's a lot to be gained from knowing your opponents' strategies. – Shufflepants – 2017-11-09T21:36:03.660

4@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. :) – Kevin Cruijssen – 2017-11-09T22:09:25.797

1Can a bid of 0 win if all other players tie out? – thegreatemu – 2017-11-10T20:17:14.343

@thegreatemu yes. – Colera Su – 2017-11-11T01:26:49.163

Will these example bots take part in the competition? – Zaid – 2017-11-11T09:06:56.103

@Zaid no. It's mentioned in the post. – Colera Su – 2017-11-11T09:26:51.443

4Here's a test run on TIO with all of the current bots. – Steadybox – 2017-11-11T15:25:07.413

1This challenge might be more interesting if different rounds had weighted values, and the weight of rounds you had won counted proportionally towards your final score. That way there would be an extra layer of strategy to how much to bid. – mypetlion – 2017-11-14T20:35:30.327

@mypetlion that's a good idea. Maybe I can use it in further challenges (not this one, since it will make a big difference). – Colera Su – 2017-11-16T00:58:31.823

2It's a tight race at the moment... – Zaid – 2017-11-22T18:46:20.983

Answers

13

hard_coded

class hard_coded:
  def __init__(self):
    self.money = 0
    self.round = 0

  def play_round(self, did_i_win, amount):
    self.money += 500
    self.round += 1
    if did_i_win == 0:
      self.money -= amount
    prob = [500, 992, 1170, 1181, 1499, 1276, 1290, 1401, 2166, 5000][self.round - 1]
    if prob > self.money:
      return self.money
    else:
      return prob    

This bot is the results of genetic training against a lot of other pseudo-random bots (and some of the bots in other answers). I've spent some time fine-tuning at the end, but its structure is actually very simple.

The decisions are based only on a fixed set of parameters and not on the outcome of previous rounds.

The key seems to be the first round: you have to go all-in, bidding 500 is the safe move. Too many bots are trying to outsmart the initial move by bidding 499 or 498. Winning the first round gives you a big advantage for the rest of the auction. You are only 500 dollars behind, and you have time to recover.

A safe bet in the second round is a little over 990, but even bidding 0 gives some good result. Bidding too high and winning could be worse than losing this round.

In the third round, most bots stop escalating: 50% of them have less than 1500 dollars by now, so there is no need to waste money on this round, 1170 is a good tradeoff. Same thing in the fourth round. If you lost the first three, you can win this one very cheap, and still have enough money for the next.

After that, the average money required to win a round is 1500 dollars (which is the logical conclusion: everyone wins a round out of four by now, bidding less to win later is just wasting money, the situation has stabilized and it's just round-robin from now on).

The last round must be all-in, and the other parameters are fine-tuned to win the last round by bidding as low as possible until then.

A lot of bots try to win the ninth round by bidding more than 2000 dollars, so I took that into account and try to overbid them (I can't win both the last two rounds anyway, and the last will be harder).

G B

Posted 2017-11-09T14:29:39.293

Reputation: 11 099

1Well, that's one way to win. Congratulations! – Luca H – 2017-11-23T14:22:24.367

But I gotta admit that I like other submissions more, because there went another form of thought into. Not trying out how I would win against those other bots, but what could be a good tactic against any random bot. – Luca H – 2017-11-23T14:30:41.617

I can understand, I liked (and upvoted) some other submissions, but this is a problem on a finite domain, and a lot of submissions are just too complex. The core of the problem is generating a sequence of 10 numbers, so I chose to optimize for a specific domain instead of finding a general procedure. I am an engineer, not a mathematician. – G B – 2017-11-23T14:37:05.193

Fair enough, the problem is pretty finite... Here, take my upvote, you convinced me :p – Luca H – 2017-11-23T14:43:00.513

Grazie mille und arrivederci. :-) – G B – 2017-11-23T15:05:46.180

2@LucaH the apparent simplicity of the approach belies the amount of work required to arrive at this particular set of numbers. I was attempting a similar thing with my own bot from a statistical viewpoint, and it wasn't easy – Zaid – 2017-11-23T15:07:05.217

1@Zaid of course there is a lot of work going into it, but brute forcing is just so... brute ;) – Luca H – 2017-11-23T15:10:58.990

12

Above Average

Bids above the average amount of money the other players have. Bids everything in the last round.

class above_average:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
  def play_round(self, winner, winning_bid):
    self.round += 1
    self.player_money = [x+500 for x in self.player_money]
    if winner != -1:
      self.player_money[winner] -= winning_bid
    if self.round == 10:
      return self.player_money[0]
    bid = sum(self.player_money[1:]) / 3 + 1
    if bid > self.player_money[0]:
      return self.player_money[0]
    return min(self.player_money[0], bid)

Okx

Posted 2017-11-09T14:29:39.293

Reputation: 15 025

12

I Don't Even

class I_Dont_Even:
	def __init__(self):
		self.money = 0
		self.round = 0
	def play_round(self, loser, bid):
		self.money += 500 - (not loser) * bid
		self.round += 1
		return self.money * (self.round & 1 or self.round == 10)

Only participates in odd rounds and the last round.

Dennis

Posted 2017-11-09T14:29:39.293

Reputation: 196 637

7

The forgetful bot doesn't know how much money he has, so he just puts in the money he was given for this round. If he finds he has some money at the end, he just donates it to a charity.

class forgetful_bot:
  def play_round(self, winner, amt):
    return 500

RamenChef

Posted 2017-11-09T14:29:39.293

Reputation: 1 163

15I'm not the downvoter, but maybe it is 'cause you did not put any effort into your bot – Mischa – 2017-11-09T16:18:48.120

9This is one of the first answers. Something is needed to get the ball rolling. – Khuldraeseth na'Barya – 2017-11-09T18:54:06.577

I didn't downvote, but maybe it's because even though something needed to get the ball rolling, maybe do something slightly more interesting? Especially since this is practically identical to One Dollar Bob which was used to get it kind of started – HyperNeutrino – 2017-11-14T21:37:22.940

7

Patient Bot

class patient_bot:
    def __init__(self):
        self.round = 0
        self.money = 0
    def rand(self, seed, max):
        return (394587485 - self.money*self.round*seed) % (max + 1)
    def play_round(self, winner, amount):
        self.round += 1
        self.money += 500
        if winner == 0:
            self.money -= amount
        if self.round < 6:
            return 0
        else:
            bid = 980 + self.rand(amount, 35)
            if self.money < bid or self.round == 10:
                bid = self.money
            return bid

Bids nothing for the first five rounds, then bids ~1000 dollars for the next four rounds, and finally bids everything it has in the last round.

Steadybox

Posted 2017-11-09T14:29:39.293

Reputation: 15 798

7

One Upper

I don't know much about Python, so I might make some kind of error

class one_upper:
    def __init__(self): 
        self.money = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.money += 500
        if winner == 0: self.money -= win_amount
        self.round += 1
        bid = win_amount + 1
        if self.money < bid or self.round == 10:
            bid = self.money
        return bid

bids 1 higher than the previous winning bid, or goes all-in during the last round.

I may in the future decide on a different strategy for when win_amount is -1

Kamil Drakari

Posted 2017-11-09T14:29:39.293

Reputation: 3 461

7

Copycat Or Sad

Third and final bot.
This bot will bid exactly the same amount as the previous winner (including itself). However, if it doesn't have enough cash to do so it will be sad, and will bid a measly 1 dollar bill with his tear on it instead. In the final round it will go all-in.

class copycat_or_sad:
  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: bid all-in
    if self.round == 9:
      return self.money
    # Else-if there was no previous winner, or it doesn't have enough money left: bid 1
    if win_amount < 1 or self.money < win_amount:
      return 1
    # Else: bid the exact same as the previous winner
    return win_amount

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

Kevin Cruijssen

Posted 2017-11-09T14:29:39.293

Reputation: 67 575

2This bids -1 on the first auction. – Okx – 2017-11-09T16:44:52.490

7

Test run

I've edited a previous test run put together by Steadybox adding in the newest submissions.

I'm posting it here so there is a place where the link can be updated with more recent versions, this post is a community wiki so feel free to update it if you post a new submission, modify an old one, or simply see something new from some other submission!

Here's the link to the test run! (TIO)

Leo

Posted 2017-11-09T14:29:39.293

Reputation: 8 482

should I be depressed that my bot that was meant to be disruptive beats out my two "real" submissions? – thegreatemu – 2017-11-17T16:18:25.220

@thegreatemu It's interesting to see how the bots interact with each other. A single new bot could dramatically change the rankings. Something interesting I found is that if histocrat's deleted blacklist bot participates, my two bots move to the top of the rankings. :) – Jo. – 2017-11-18T03:39:53.607

6

Half In

This bot always bids half of what it has left, except in the final round where it will go all in.

class half_in:
  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: bid all in
    if self.round == 9:
      return self.money
    # Else: Bid half what it has left:
    return self.money / 2

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

Kevin Cruijssen

Posted 2017-11-09T14:29:39.293

Reputation: 67 575

6

AverageMine

This player calculates the percentage (bid / total money) for the winner of each round and bids his (total money * average winning percentage + 85) unless he has more money than all the other players, then he bids 1 more than the highest competitor. Starts with a bid of 99.0% of the starting amount.

class AverageMine:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0
        self.average = 0
    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            if i == winner:
                self.average = (self.average * (self.round - 2) + (win_amt / self.money[i])) / (self.round - 1)
                self.money[i] -= win_amt
                self.wins[i] += 1
            self.money[i] += 500
        if self.round == 1:
            return int(0.990 * self.money[0])
        elif self.round < self.maxrounds:
            if self.money[0] > self.money[1] + 1 and self.money[0] > self.money[2] + 1 and self.money[0] > self.money[3] + 1:
                return max(self.money[1],self.money[2],self.money[3]) + 1
            bid = int(self.average * self.money[0]) + 85
            return min(self.money[0],bid)
        else:
            bid = self.money[0]
            return bid

Jo.

Posted 2017-11-09T14:29:39.293

Reputation: 974

6

Graylist

class Graylist:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
    self.ratios = {1}
    self.diffs = {0}
  def play_round(self, winner, winning_bid):
    self.round += 1
    if winner != -1:
      if winner >0 and winning_bid>0:
        self.ratios.add(self.player_money[winner]/winning_bid)
        self.diffs.add(self.player_money[winner]-winning_bid)
      self.player_money[winner] -= winning_bid
    self.player_money = [x+500 for x in self.player_money]
    tentative_bid = min(self.player_money[0],max(self.player_money[1:])+1, winning_bid+169, sum(self.player_money[1:])//3+169)
    while tentative_bid and (tentative_bid in (round(m*r) for m in self.player_money[1:] for r in self.ratios)) or (tentative_bid in (m-d for m in self.player_money[1:] for d in self.diffs)):
      tentative_bid = tentative_bid - 1
    return tentative_bid

Inspired by the blacklist submission by histocrat, this bot keeps in memory all the previous winning bets of other players as both the ratio of money they bet compared to their full money and the difference between their bet amount and the full amount. In order to avoid losing to a tie (which apparently is actually a big factor in this competition) it then avoids betting any number that could give the same results given its opponents' current moneys.

EDIT: as the starting value for the bid now uses the minimum between: its current money, 1 more than the money of the richest opponent, X more than the last winning bet, or Y more than the average money of its opponents. X and Y are constants that will probably be modified before the end of the competition.

Leo

Posted 2017-11-09T14:29:39.293

Reputation: 8 482

6

Eenie Meanie More

This player is identical to Meanie, except for one variable. This version bids more aggressively and causes some players to spend more than meanie thinks the auction is worth.

class eenie_meanie_more:
    def __init__(self):
        self.money = [0] * 4
        self.rounds = 11
        self.total_spent = 0

    def play_round(self, winner, winning_bid):
        self.money = [x+500 for x in self.money]
        self.rounds -= 1
        if winner != -1:
            self.money[winner] -= winning_bid
            self.total_spent += winning_bid
        bid = 500
        if self.rounds > 0 and self.total_spent < 20000:
            bid = int((20000 - self.total_spent)/self.rounds/4)+440
        return min(bid, max(self.money[1:])+1, self.money[0])

Nope

Posted 2017-11-09T14:29:39.293

Reputation: 61

5

Distributer

When this bot loses a round, he distributes the excess cash among all of the next rounds. He puts in $499 on the first round thinking that the others will tie with $500 and be eliminated.

class distributer:
  def __init__(self):
    self.money = 0
    self.rounds = 11
  def play_round(self, winner, amt):
    self.money += 500
    self.rounds -= 1
    if self.rounds == 10:
      return 499
    if winner == 0:
      self.money -= amt
    return ((self.rounds - 1) * 500 + self.money) / self.rounds

RamenChef

Posted 2017-11-09T14:29:39.293

Reputation: 1 163

1Using rounds instead of self.rounds will cause errors. Same with money. – Jeremy Weirich – 2017-11-09T21:36:14.253

5

Meanie

This player takes the total cash that will enter play to get the mean bid across the number of players and remaining rounds. If this target is more than all other players currently hold it lowers its bid to the balance of its greatest competitor plus one. If the player cannot afford its target, it is all-in.

class meanie:
    def __init__(self):
        self.money = [0] * 4
        self.rounds = 11
        self.total_spent = 0

    def play_round(self,winner,winning_bid):
        self.money = [x+500 for x in self.money]
        self.rounds -= 1
        if winner != -1:
            self.money[winner] -= winning_bid
            self.total_spent += winning_bid
        bid = 500
        if self.rounds > 0 and self.total_spent < 20000:
            bid = int((20000 - self.total_spent)/self.rounds/4)+1
        return min(bid,max(self.money[1:])+1,self.money[0])

Nope

Posted 2017-11-09T14:29:39.293

Reputation: 51

5

Beat the Winner

Bid 1 more than the player with the most wins so far

class BeatTheWinner:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0

    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            self.money[i] += 500
            if i == winner:
                self.money[i] -= win_amt
                self.wins[i] += 1
        mymoney = self.money[0]
        for w,m in sorted(zip(self.wins, self.money),reverse=True):
            if mymoney > m:
                return m+1
        #if we get here we can't afford our default strategy, so
        return int(mymoney/10)

thegreatemu

Posted 2017-11-09T14:29:39.293

Reputation: 311

4Are your m,w in the correct order? – Jo. – 2017-11-11T07:23:46.043

5

Bid Higher

class bid_higher:
    def __init__(self):
        self.dollar = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.dollar += 500
        self.round += 1
        inc = 131
        if winner == 0: self.dollar -= win_amount
        if self.round == 10: return self.dollar
        if win_amount == 0: win_amount = 500
        if self.dollar > (win_amount + inc):
            return win_amount + inc
        else:
            if self.dollar > 1:
                return self.dollar -1
            else:
                return 0

Still learning python; bid a bit higher than the last winner.

rancid_banana

Posted 2017-11-09T14:29:39.293

Reputation: 111

Welcome to PPCG! It seems that your bot gets even better a score if you change inc = 100 to inc = 101.

– Steadybox – 2017-11-13T16:33:56.363

I'm really going against my own interests here, but you could easily improve your score by keeping track of the turns and going all-in on the final round ;) – Leo – 2017-11-14T00:51:49.120

Thanks for the suggestions; I added a last-round all-in, fine-tuned the increment, and added a couple of wingmen bots to give this bot a boost.. – rancid_banana – 2017-11-14T20:55:58.060

Hi, I hope you don't mind, but I was putting together a testbench with all the current submission and I've found out that your code was sometimes returning invalid values on the last round, so I've fixed the bug by rearranging the order a couple of lines. Sorry if I changed anything you wouldn't have, feel free to revert the changes and fix the bug in another way! – Leo – 2017-11-14T22:50:39.490

@Leo:No problem, thanks for taking an interest.. – rancid_banana – 2017-11-14T23:27:58.607

5

Minus One

class minus_one:
    def __init__(self):
        self.money = 0
    def play_round(self, winner, amount):
        self.money += 500
        if winner == 0:
            self.money -= amount
        return self.money - 1

Steadybox

Posted 2017-11-09T14:29:39.293

Reputation: 15 798

4

Showoff

This is that guy who shows off his math ability in situations that truly do not require anything so complicated. Until the last round (in which he goes all-in), he uses a logistic model to determine his bid, more if his enemies have a greater portion of their money remaining.

class Showoff:
  def __init__(self):
      self.moneys = [0, 0, 0]
      self.roundsLeft = 10
  def play_round(self, winner, winning_bid):
      import math
      self.moneys = [self.moneys[0] + 500,
                     self.moneys[1] + 1500,
                     self.moneys[2] + 1500]
      self.roundsLeft -= 1
      if winner > 0:
          self.moneys[1] -= winning_bid
      if winner == 0:
          self.moneys[0] -= winning_bid
      if self.roundsLeft == 0:
          return self.moneys[0]
      ratio = self.moneys[1] / self.moneys[2]
      logisticized = (1 + (math.e ** (-8 * (ratio - 0.5)))) ** -1
      return math.floor(self.moneys[0] * logisticized)

The logistic curve used is f(x)=1/(1+e-8(x-0.5)), where x is the ratio of current enemy-money to the round's total potential enemy-money. The more the others have, the more he bids. This has the possible benefit of bidding almost-but-not-quite $500 the first round.

Khuldraeseth na'Barya

Posted 2017-11-09T14:29:39.293

Reputation: 2 608

4

Escalating Quickly

Bids increasing fractions of its money each round (please let me know if any errors, a while since I used Python)

class escalating:
  def __init__(self):
    self.money = 0
    self.round = 0
  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

    # bid round number in percent times remaining money, floored to integer
    return self.money * self.round // 10

Scott

Posted 2017-11-09T14:29:39.293

Reputation: 171

4

FiveFiveFive

Skips the first round and bids $555 on remaining rounds. In last round, will go all in unless 2 other bots have the same amount (and will presumably tie out).

class FiveFiveFive:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0

    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            self.money[i] += 500
            if i == winner:
                self.money[i] -= win_amt
                self.wins[i] += 1
        if self.round == 1:
            return 0
        elif self.round < self.maxrounds:
            return min(555, self.money[0])
        else:
            bid = self.money[0]
            return bid if self.money.count(bid) < 3 else bid-1

thegreatemu

Posted 2017-11-09T14:29:39.293

Reputation: 311

4

Almost All In

class Almost_All_In:
	def __init__(self):
		self.money = 0
		self.round = 0
	def play_round(self, loser, bid):
		self.money += 500 - (not loser) * bid
		self.round += 1
		return self.money - self.round % 3 * 3 - 3

Always bids slightly less than it has.

Dennis

Posted 2017-11-09T14:29:39.293

Reputation: 196 637

4

Below Average

Similar to above average, but goes a bit lower

class below_average:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
  def play_round(self, winner, winning_bid):
    self.round += 1
    self.player_money = [x+500 for x in self.player_money]
    if winner != -1:
      self.player_money[winner] -= winning_bid
    if self.round == 10:
      return self.player_money[0]
    bid = sum(self.player_money[1:]) / 3 - 2
    if bid > self.player_money[0]:
      return self.player_money[0]
    return min(self.player_money[0], bid)

Okx

Posted 2017-11-09T14:29:39.293

Reputation: 15 025

4

Modular Blacklist

class blacklist_mod:
  def __init__(self):
    self.round = 0
    self.player_money = [0] * 4
    self.blacklist = {0, 499}
  def play_round(self, winner, winning_bid):
    self.round += 1
    self.player_money = [x+500 for x in self.player_money]
    if winner != -1:
      self.player_money[winner] -= winning_bid
      self.blacklist.add(winning_bid % 500)
      self.blacklist |= {x % 500 for x in self.player_money[1:]}
    tentative_bid = self.player_money[0]
    autowin = max(self.player_money[1:])+1
    if tentative_bid < autowin:
      while tentative_bid and (tentative_bid % 500) in self.blacklist:
        tentative_bid = tentative_bid - 1
    else:
      tentative_bid = autowin
    self.blacklist.add(tentative_bid % 500)
    return tentative_bid

Bets the highest amount it can that isn't congruent modulo 500 to any numbers it's seen before.

Edited to not apply the blacklist when it can get a guaranteed win.

histocrat

Posted 2017-11-09T14:29:39.293

Reputation: 20 600

Curiously, it seems that the latest update to your other bot is affecting this bot negatively. Currently, blacklist_mod is fifth on the leaderboard, whereas blacklist is in the second place. If the older version of blacklist is used instead, blacklist falls to the sixth place, but blacklist_mod takes the lead!

– Steadybox – 2017-11-12T00:11:30.637

Throwing blacklist out altogether seems to give blacklist_mod even a more solid lead, but that's inconclusive.

– Steadybox – 2017-11-12T00:19:13.883

Oh, thanks, that makes sense--they're close to the same algorithm early on without the old special-case logic, so they step on each others' toes. I think I'll just remove the original bot; I can't think of a good reason to keep it around. – histocrat – 2017-11-12T01:40:53.467

4

HighHorse

This player bids all his money minus the current round number, except on the last round, where he goes all in.

class HighHorse:
    maxrounds = 10
    def __init__(self):
        self.money = 0
        self.round = 0
    def play_round(self, winner, win_amt):
        self.round += 1
        if 0 == winner:
            self.money -= win_amt
        self.money += 500
        if self.round < self.maxrounds:
            return self.money - self.round
        else:
            bid = self.money
            return bid

Jo.

Posted 2017-11-09T14:29:39.293

Reputation: 974

4

Swapper

Alternates between bidding one under his max and going all in.

class Swapper:
    def __init__(self):
        self.money = 0
        self.round = 0
    def play_round(self, loser, bid):
        self.money += 500 - (not loser) * bid
        self.round += 1
        if self.round & 1:
            return self.money - 1
        return self.money

I figured I needed to find something that could beat Steadybox's minus_one. :)

Jo.

Posted 2017-11-09T14:29:39.293

Reputation: 974

4

Heurist

The Heurist treats this game as one of repeatable probability, so it knows where to draw the line.

It is also miserly, so it bids the bare minimum required for a win when it can.

class heurist:
    def __init__(self):
        self.money = 0
        self.round = -1
        self.net_worth = [0] * 4
    def play_round(self, winner, bid):
        self.round += 1
        self.money += 500
        if winner == 0: self.money -= bid
        if winner != -1: self.net_worth[winner] -= bid
        self.net_worth = [x+500 for x in self.net_worth]
        max_bid = [498,1000,1223,1391,1250,1921,2511,1666,1600,5000][self.round]
        if self.money > max_bid:
            return 1 + min(max_bid,max(self.net_worth[1:3]))
        else:
            return self.money

Disclaimer: max_bid is subject to change

Zaid

Posted 2017-11-09T14:29:39.293

Reputation: 1 015

4

bob_hater

This bot does not like Bob and thus will always bid 2$ to win against Bob.

class bob_hater:
    def play_round(bob,will,loose):
        return 2

Luca H

Posted 2017-11-09T14:29:39.293

Reputation: 163

3

AntiMaxer

Match the highest amount we can afford of all player's money. Will cause any bot going for all-in on that round to tie out.

class AntiMaxer:
    nplayers = 4
    maxrounds = 10
    def __init__(self):
        self.money = [0] * self.nplayers
        self.wins = [0] * self.nplayers
        self.round = 0

    def play_round(self, winner, win_amt):
        self.round += 1
        for i in range(self.nplayers):
            self.money[i] += 500
            if i == winner:
                self.money[i] -= win_amt
                self.wins[i] += 1
        return max((m for m in self.money[1:] if m<=self.money[0]),
                   default=0)    

thegreatemu

Posted 2017-11-09T14:29:39.293

Reputation: 311

3

Simple Bot

class simple_bot:
    def __init__(self):
        self.round = 0
        self.money = 0
    def rand(self, seed, max):
        return (394587485 - self.money*self.round*seed) % (max + 1)
    def play_round(self, winner, amount):
        self.round += 1
        self.money += 500
        if winner == 0:
            self.money -= amount
        bid = 980 + self.rand(amount, 135)
        if self.money < bid or self.round == 10:
            bid = self.money
        return bid

Almost the same as Patient Bot, but not as patient. Gets a much better score than it, though.

Steadybox

Posted 2017-11-09T14:29:39.293

Reputation: 15 798

3

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

rancid_banana

Posted 2017-11-09T14:29:39.293

Reputation: 111

Your code won't work because you need indentation for the stuff in the class – HyperNeutrino – 2017-11-14T20:36:18.910

Thanks for pointing that out; I haven't got the hang of the {} code editing yet. – rancid_banana – 2017-11-14T20:42:20.617

1Clever, 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. – histocrat – 2017-11-14T21:16:12.507

1@Steadybox:Thanks, fixed the all-in code. – rancid_banana – 2017-11-14T22:08:05.117

3

Wingman 2

If one wingman is good, two must be better ?

class wingman_2:
    def __init__(self):
        self.dollar = 0
        self.round = 0
    def play_round(self, winner, win_amount):
        self.round += 1
        self.dollar += 500
        inc = 129
        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

rancid_banana

Posted 2017-11-09T14:29:39.293

Reputation: 111

Your code won't work because you need indentation for the stuff in the class – HyperNeutrino – 2017-11-14T20:36:16.907

Interestingly, both of your wingmen seem to beat your original bot (the pastebin link contains the TIO link, which is too long for posting in a comment and even too long for URL shorteners...)

– Steadybox – 2017-11-14T21:32:28.703

1I found the results were very sensitive to the pool of other bots; minor changes in the increment value seem to have disproportionate results. – rancid_banana – 2017-11-14T22:04:19.297

3

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

coolioasjulio

Posted 2017-11-09T14:29:39.293

Reputation: 141

1Right, my bad. Fixed. Thanks for the input! – coolioasjulio – 2017-11-14T21:42:41.323

2

class one_dollar_bob:
  def play_round(x,y,z):
    return 1

KSmarts

Posted 2017-11-09T14:29:39.293

Reputation: 1 830

2

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

Kevin Cruijssen

Posted 2017-11-09T14:29:39.293

Reputation: 67 575

1Your check for the final round will fire on round 11, not 10. Same with your Half In bot. – Jeremy Weirich – 2017-11-09T21:16:10.520

@JeremyWeirich Thanks! Fixed. – Kevin Cruijssen – 2017-11-09T21:54:57.530