Dies ist eine KOTH-Herausforderung für das Auktionsspiel für Dollarnoten in der Spieltheorie. Darin wird ein Dollar an den Meistbietenden verkauft. Die Gebote steigen in Schritten von 5 ¢, und der Verlierer zahlt auch sein Gebot. Die Idee ist, dass beide Spieler den Bieterkrieg weit über den Wert eines Dollars hinaus eskalieren, um ihre Verluste zu reduzieren.
Hoffen wir, dass Ihre Bots schlauer sind.
Sie werden einen Bot erstellen, um dieses Spiel zu spielen, indem Sie die net.ramenchef.dollarauction.DollarBidder
Klasse erweitern. Sie müssen die nextBid
Methode implementieren, die das nächste Gebot Ihres Bots zurückgibt, wenn das vorherige Gebot des anderen Bots vorliegt. Bei Bedarf können Sie die newAuction
Methode auch verwenden , um für jede Auktion die Klasse des gegnerischen Bots zurückzusetzen.
public abstract class DollarBidder {
/**
* Used by the runner to keep track of scores.
*/
long score = 0;
/**
* (Optional) Prepare for the next auction.
*
* @param opponent The class of the opponent's bot.
*/
public void newAuction(Class<? extends DollarBidder> opponent) {}
/**
* Bid on the dollar. Bidding ends if the bid is
* not enough to top the previous bid or both bids
* exceed $100.
*
* @param opponentsBid How much money, in cents,
* that the opponent bid in the previous round. If
* this is the first round in the auction, it will
* be 0.
* @return How much money to bid in this round, in
* cents.
*/
public abstract int nextBid(int opponentsBid);
}
Das Bieten dauert so lange, bis eine der folgenden Bedingungen erfüllt ist:
nextBid
wirft eine Ausnahme. In diesem Fall zahlt der Bot, der die Ausnahme ausgelöst hat, sein vorheriges Gebot und der andere Bot erhält den Dollar kostenlos.- Beide Bot zahlen nicht genug, um das vorherige Gebot zu übertreffen. In diesem Fall zahlen beide Bots ihre Gebote (der Verlierer zahlt das vorherige Gebot), und der Gewinner erhält einen Dollar.
- Beide Bots bieten über 100 $. In diesem Fall zahlen beide Bots 100 USD und keiner der Bots erhält den Dollar.
Für jede Bots-Kombination finden 2 Auktionen statt. Bots werden anhand des Gesamtgewinns bewertet, den sie in diesen Auktionen erzielt haben. Die höchste Punktzahl gewinnt.
Beispiele
GreedyBot
import net.ramenchef.dollarauction.DollarBidder;
public class GreedyBot extends DollarBidder {
@Override
public int nextBid(int opponentsBid) {
return opponentsBid + 5;
}
}
OnlyWinningMove
import net.ramenchef.dollarauction.DollarBidder;
public class OnlyWinningMove extends DollarBidder {
@Override
public int nextBid(int opponentsBid) {
return 0;
}
}
AnalystBot
Verwenden Sie dies nicht als Vorlage für analytisch denkende Bots. Verwenden Sie ImprovedAnalystBot
stattdessen.
import net.ramenchef.dollarauction.DollarBidder;
// yes, this is a poor implementation, but I'm not
// going to waste my time perfecting it
public class AnalystBot extends DollarBidder {
private DollarBidder enemy;
@Override
public void newAuction(Class<? extends DollarBidder> opponent) {
try {
enemy = opponent.newInstance();
enemy.newAuction(this.getClass());
} catch (ReflectiveOperationException e) {
enemy = null;
}
}
@Override
public int nextBid(int opponentsBid) {
if (enemy == null)
return 0;
return enemy.nextBid(95) >= 100 ? 0 : 95;
}
}
AnalystKiller
import net.ramenchef.dollarauction.DollarBidder;
public class AnalystKiller extends DollarBidder {
private static int instances = 0;
private final boolean tainted;
public AnalystKiller() {
this.tainted = instances++ != 0;
}
@Override
public int nextBid(int opponentsBid) {
if (tainted)
throw new RuntimeException("A mysterious error occurred! >:)");
return 0;
}
}
Zusätzliche Regeln
- Standardlücken sind verboten.
- Das Sabotieren anderer Bots ist zulässig, aber der Versuch, die Sichtbarkeit von Feldern / Methoden zu ändern, führt zu mysteriösen
SecurityException
s. Eine Ausnahme führt dazu, dass ein anderer Bot die Grenze von 500 ms überschreitet. - Bots können nur zur Erweiterung der
DollarBidder
Klasse auf das Runner-Paket zugreifen . - Alle Methoden sollten in 500 ms oder weniger zurückkehren.
- Bots müssen nicht deterministisch sein.
- Ihr Gebot muss kein Vielfaches von 5 ¢ sein.
- 1 $ = 100 ¢
- Die Ergebnisse werden am 24. April 2018 veröffentlicht.
Ergebnisse
Sehen Sie sich hier die einzelnen Runden an.
MTargetedBot: $14.30
BuzzardBot: $9.83
BluffBot: $9.40
RiskRewardBot: $9.35
SecretBot: $8.50
LuckyDiceBot: $7.28
CounterBot: $6.05
MBot: $5.40
StackTraceObfuscaterBot: $5.20
EvilBot: $4.80
MarginalBot: $4.60
TargetValueBot: $4.59
InflationBot: $4.27
UpTo200: $4.20
InsiderTradingBot: $1.90
MimicBot: $1.50
BorkBorkBot: $1.22
DeterrentBot: $0.95
MarginalerBot: $0.00
RandBot: $-4.45
BreakEvenAsap: $-7.00
AnalystOptimizer: $-13.95
DeterredBot: $-1997.06
ScoreOverflowBot: $-21474844.15
MirrorBot: $-21475836.25
Herzlichen Glückwunsch zu MTargetedBot
einem Gewinn von 14,30 $!
quelle
LuckyDiceBot
2-12
Antworten:
MTargetedBot
quelle
MimicBot
Heilige Kuh. Ich erwartete, dass dies einfach zu schreiben sein würde, und verbrachte anschließend 3 Stunden damit.
Im Wesentlichen wird
MimicBot
eine Liste der verfügbaren Bots geführt. Wenn es zu einer neuen Auktion geht, durchläuft es die Liste auf der Suche nach dem effektivsten gegen den aktuellen Gegner. Dieser Bot wird dann als "Referenz" in der Auktion verwendet.Zu Testzwecken ist es am besten, entweder eine zufällige Teilmenge der Beiträge oder die vollständige Menge zu verwenden. Es beginnt mit
GreedyBot
,MimicBot
und einem weiteren Bot, der nur 5 ¢ bietet.quelle
InsiderTradingBot
Im Geiste der Antwort von @ StephenLeppik kennt InsiderTradingBot alle seine Gegner und versteht deren Strategien. Dein Umzug, Stephen.
quelle
RichJerk
Bot eine bestimmte Ausnahme für Ihren Bot machen und $ 0 dafür bieten würde.AnalystBot
nichtAnalyst
.MarginalBot
Ganz einfach, es wird versucht festzustellen, ob ein Gegner ein Mindestgebot anfechten würde, und wenn nicht, platziert er es.
MarginalerBot
Eine neue, intelligentere Version von MarginalBot, mit der überprüft wird, ob mit MarginalBot auch ohne Wettbewerb Gewinne erzielt werden können, anstatt nur mit dem Minimum zu gewinnen.
Da es in der gleichen Familie wie mein vorheriger Bot ist, aber Ausweichstrategien versucht, es zu schlagen, dachte ich, dass ein neuer Eintrag in demselben Post die vernünftigste Art ist, es zu präsentieren.
Bearbeiten 1: Die neueAuktionsmethode wurde geringfügig geändert, um sie gegen andere Bots vom Typ Analysator zu optimieren.
Bearbeiten 2: MarginalerBot wurde geändert, um Verluste gegenüber hinterhältigen oder nicht deterministischen Strategien zu minimieren.
quelle
MirrorBot
Lässt den Feind gegen sich selbst spielen.
quelle
Analyst
spektakulär geknackt .Bearbeiten : Durch gezielte Änderungen in der DollarBidder-Klasse wurde dieser Bot zerstört.
ScoreOverflowBot
Nach einer Auktion beträgt die Punktzahl -2147483645, aber das nächste Mal verliert sie 5 oder 105, was die Punktzahl positiv und sehr groß macht. Alle anderen Verluste wären dann vernachlässigbar.
Bei der ersten Auktion würde GreedyBot auch -2147483646 wetten, was nicht durch 5 teilbar ist.
quelle
score
ist paketgeschützt. Ihre Bots können nicht darauf zugreifen.TargetValueBot
Kann dies im Moment nicht testen, also lass es mich wissen, wenn es kaputt ist.
Wählen Sie im Grunde genommen einen Wert für den Dollar und überbieten Sie den Gegner, bis wir diesen Wert überschreiten.
quelle
BorkBorkBot
Gibt auf, wenn es nicht ausgeglichen werden kann.
quelle
RandBot
Es musste getan werden.
quelle
DeterrentBot
Versuche, analytisch denkende Bots davon zu überzeugen, dass der einzige Gewinn nicht darin besteht, zu spielen.
quelle
LuckyDiceBot
LuckyDiceBot vertraut nur seinen Würfeln. Er würfelt mit zwei Würfeln, addiert die Summe zum Wert des aktuellen Bieters und bietet so viel. Wenn es nicht ausreicht, um das Gebot des Gegners zu überwinden, verringert er seine Verluste und macht sich auf den Weg.
quelle
opponentsBid
innextBid(int opponentsBid)
hält das Gesamtgebot, das Ihr Gegner bisher geboten hat, nicht das nächste Gebot. Ein besserer Begriff für die Methode wäreraise
(wie der Begriff Poker) imho. 2. Ihr Bot bitet nicht in Schritten von 5 und überprüft daher eine der Regeln. Wenn diese Probleme behoben sind, gefällt mir das Konzept immer noch, da analytische Bots nicht in der Lage sind zu kontern und Sie höchstwahrscheinlich ziemlich oft gewinnen werden.DeterredBot
DeterredBot macht ein Vermögen aus seinem illegalen Glücksspiel mit LuckyDiceBot. Wenn die Polizei (DeterrentBot) kommt, muss er natürlich schnell über seine Einnahmen verfügen, zum Beispiel, um für die nächste Auktion zu bieten.
quelle
InflationBot
Kann dies im Moment nicht testen, also lass es mich wissen, wenn es kaputt ist.
Mit jeder Runde steigt der Wert des Dollars.
quelle
opponentsBid
ist noch 0)?Nicht konkurrierend: AbstractAnalystCounterBot
Dies ist nicht als wahrer Beitrag gedacht, sondern als ein Hinweis, den andere verwenden sollten, um Bots, die Haustiere halten, von
MirrorBot
und abzuhaltenMimicBot
.Da dies der Standardkonstruktor ist, müssen Sie ihn in Ihrer Unterklasse nicht aufrufen. Es implementiert eine
isPeeking
Methode, um festzustellen, ob ein anderer Bot schnüffelt.quelle
BreakEvenAsap
Szenarien
<= 0
, verliert er.[5,95]
bieten darf : Bieten Sie selbst 100. Entweder stoppt Ihr Gegner jetzt oder Sie bieten mehr als 100. In diesem Fall hören Sie auf zu bieten, damit er den Sieg erringen und sich selbst ausgleichen kann.>= 100
bieten darf : Bieten Sie selbst 0, um zu verlieren, aber die Gewinnschwelle zu erreichen.quelle
EvilBot
Löst einen Fehler anstelle einer Ausnahme aus, um Analysten zu verwirren.
quelle
BuzzardBot
Versucht, den Gegner zu bewerten, mit dem er konfrontiert ist, und stellt sicher, dass nicht mehr abgebissen wird, als er kauen kann.
quelle
AnalystOptimizer
aus Teilen anderer Bots zusammengeschustert. Dieser spielt, indem er versucht, AnalystBot zu sein, und wenn er nicht erfolgreich ist, wird er zu BorkBorkBot.
Ich denke nicht, dass dies gut tun wird.
quelle
AnalystKiller
.CounterBot
Zähler:
DarthVader
wirkt sich aus, indem erSecurityException
vor dem Start des Gebots ein auslöst, aber ich biete nur für den Fall 5.AnalystBot
undAnalystOptimizer
beide sehen sich meine Antwort an, wenn ich 95 biete. In diesem Fall zeige ich, dass ich 100 biete, sodass 95 selbst geboten wird. Ich biete jedoch 5, wenn ich anfange (oder 100, wenn sie begonnen haben), so dass sie 95 Cent verlieren und ich entweder die 1-USD-Rechnung gewinne, indem ich nur 5 Cent biete oder indem ich die Gewinnschwelle breche.MirrorBot
werde bieten, was ich dagegen bieten würde. Also biete ich nur 5, und wer anfängt, gewinnt 95 Cent, und der andere verliert 5 Cent.MarginalBot
Ich biete 5, wenn ich weniger als 10 bieten würde (oder was es beginnt), andernfalls bietet es 0. Wenn ich also nur 5 biete, wenn ich beginne, oder 10, wenn es beginnt, gewinne ich entweder 95 oder 90 Cent, und sie verlieren 5 Cent.GreedyBot
Bietet immer 5 mehr als ich. Bieten Sie also einfach 0, um die Gewinnschwelle zu erreichenOnlyWinningMove
undAnalystKiller
beide bieten immer 0, also bieten Sie einfach 5, um zu gewinnenTargetValueBot
Bieten Sie[100,200]
also jedes Mal um 5 mehr, bis sie 190 sind. In diesem Fall erhöhen wir auf 200, um den Gewinn des Dollars auszugleichen (und lassen sie 190 oder 195 verlieren, je nachdem, wer angefangen hat).BorkBorkBot
wird im Bereich[5,95]
bieten, also bieten Sie auch jedes Mal 5 weitere. Sobald sie entweder 85 oder 90 bieten (je nachdem, wer angefangen hat), bieten Sie 95 selbst. Sie verlieren 85 oder 90 Cent, und Sie gewinnen die 1-USD-Rechnung für einen Gewinn von 5 Cent.DeterrentBot
Bietet 5, wenn sie anfangen oder 100, wenn wir anfangen. Bietet also 105, damit sie mit 100 kontern. Dadurch verlieren sie 100 und wir verlieren nur 5 Cent, indem wir die 1-USD-Rechnung gewinnen.BreakEvenAsap
bietet sofort 100. Wenn sie also mit ihrem Gebot von 100 begonnen haben, kontern Sie mit 105, um 95 Cent zu gewinnen, und lassen Sie sie 100 verlieren. Wenn wir anfangen, bieten Sie einfach 100, damit wir beide die Gewinnschwelle erreichen.RichJerk
bietet sofort 10.001, also bieten Sie einfach 0, um die Gewinnschwelle zu erreichen und 9.901 zu verlieren.DeterredBot
kennt mich nicht und bietet daher 0, also bieten Sie einfach 5, um zu gewinnen.LuckyDiceBot
Bietet so lange, bis es gewinnt. Wenn wir also anfangen, bieten Sie 5 in der Hoffnung, dass sie so hoch wie möglich bieten, um den Dollar zu gewinnen. Wenn sie angefangen haben, bieten Sie einfach 0, damit sie gewinnen und sich selbst amortisieren können.RandBot
bieten willkürlich im Bereich[5,100]
, also bieten Sie einfach 5 weitere, bis es aufhört. In diesem Fall haben Sie 95 Cent gewonnen und sie haben verloren0-100
.UpTo200
wird (wie der Name schon sagt) bis zu 200 bieten. Bieten Sie also einfach 5 höher, bis sie aufhören. Wir werden die 1 USD-Rechnung gewinnen und einen Gesamtverlust von 105 Cent hinnehmen, sie verlieren jedoch 200 Cent.InsiderTradingBot
kennt mich nicht, also biete einfach 5 Cent, um zu gewinnenMimicBot
war das schwerste. Wenn sie versuchen, auf mich zuzugreifen, werde ich eine RuntimeException auslösen (die sie abfangen. In diesem Fall würde das so tun, als hätte ich stattdessen 100 geboten - obwohl es die RuntimeException kaputt macht innere while-Schleife). Basierend auf den Feinden, die es in seinem HashSet hat, passiert etwas anderes. Ich muss noch einmal nachsehen, ob es einen tatsächlichen Zähler gibt.RiskRewardBot
Ich kenne mich nicht und biete nur 5. In diesem Fall biete ich 5, um zu gewinnen.MarginalerBot
wird bis zu 100 Bit je nachdem, was ich bieten würde. Wenn ich anfangen darf, werde ich 90 bieten, dann wird 95 bieten, dann werde ich 100 bieten, so dass es 0 bieten und 95 Cent verlieren wird, während ich die 1 USD Rechnung gewinne und ausgeglichen bin. Wenn es stattdessen startet, sehe ich, dass ich 90 gegen es bieten würde, also bietet es 90 selbst, dann biete ich 95, also bietet es 0 und verliere 90 Cent, während ich die 1 USD Rechnung mit einem Gewinn von 5 Cent gewinne.BuzzardBot
analysiert alle meine Zähler im Bereich[0,100)
. Wenn ich100
sofort biete , verwende ichoppFlag = 0
und das komplette Array mit der Größe 100 enthält das 100-fache des Werts 100. In der Vermittlungcase 0
befindet sich die Schleife wieder im Bereich[0,100)
, und dai + 5
höchstens 104 ist, ist das Wennbids[i] < i + 5
niemals wahr , so bleibt das Gebot 0.ImprovedAnalystBot
wird immer haben,this.enemy = null
weil sein Gegner istCounterBot
, nicht sich. Es wird also immer 0 geboten, was ich nur mit einem Gebot von 5 kontere.InflationBot
Bietet 0, um die Gewinnschwelle zu erreichen, andernfalls bietet es weiter 5. Bieten Sie also einfach 0, um die Gewinnschwelle zu erreichen und den Gewinn zu erzielen.ScoreOverflowBot
wird entweder in der Nähe bieten,Integer.MAX_VALUE
wenn sie anfangen können, sonst werden sie bieten105
. Wenn sie also 105 geboten haben, bieten sie uns nur 110 (sie verlieren 105, wir verlieren 10), andernfalls bieten sie einfach 0, damit sie gewinnen.MBot
ist das Gleiche wieMarginalerBot
, aber mit zusätzlichem Schutz gegen "guckende" Gegner. Da ich nicht 'gucke', ist es im Grunde dasselbe wieMarginalerBot
.SecretBot
wird seineisPeeking()
Methode false zurückgeben. Wenn sie gestartet wird oder wenn ich 5 biete, wird 5 bzw. 10 geboten. Andernfalls wird 0 geboten. Egal, ob ich anfange oder nicht,opponentsBid + 5
würde mich veranlassen, entweder mit meinen 10-Cent- oder 15-Cent-Geboten zu gewinnen, was dazu führt, dass sie entweder 5 oder 10 Cent verlieren.BluffBot
wird sich ansehen, was ich bieten würde, wenn sein Gebot 95 ist, und wenn dies größer oder gleich 100 ist, wird 0 geboten, um die Gewinnschwelle zu erreichen, andernfalls wird gebotenopponentsBid + 5
. Also werde ich einfach bietenopponentsBid + 5
. Es wird ausgeglichen, egal wer anfängt und ich gewinne entweder 100 oder 95 Cent, je nachdem, ob ich angefangen habe oder nicht.StackTraceObfuscaterBot
wird genauso handeln wieMarginalerBot
.EvilBot
wird immer 5 bieten, also einfach bietenopponentsBid + 5
. In beiden Fällen verlieren sie diese 5 Cent und wir gewinnen das Gebot von 1 USD (entweder mit einem Gebot von 5 Cent, wenn wir anfangen, oder 10 Cent, wenn sie anfangen).MSlowBot
ist das gleiche wieMBot
und daher auchMarginalerBot
.Lassen Sie mich wissen, wenn Sie Tippfehler oder Fehler in meinen Zählern sehen.
quelle
MirrorBot
Ruft newAuction mit Ihrer eigenen Klasse auf, das ist also ein Problem. Ich bin auch froh zu wissen, dass die 3 Stunden, die ich mit MimicBot verbracht habe, nicht umsonst waren.newAuction
weil es öfter als nicht fehlschlagen würde. Ich kann nicht kontern,MirrorBot
noch kann es mir widersprechen . Wer von beiden anfängt, gewinnt 95 Cent und der andere verliert 5 Cent.BorkBorkBot
nicht auf 95 erhöhen, wenn sie 85 erreichen? Andernfalls bieten Sie beide 95, wenn sie anfangen.RiskRewardBot
Kann dies im Moment nicht testen, also lass es mich wissen, wenn es kaputt ist.
Das Ziel ist es, die höchste Gesamtpunktzahl zu erzielen. Machen Sie sich also keine Sorgen, wenn Sie jemanden schlagen. Nehmen Sie einfach die einfachen Gewinne und verschwenden Sie kein Geld mit möglichen Verlusten.
quelle
BluffBot
Ein Spion, den Sie kennen, ist wertvoller als gar kein Spion ...
Wenn jemand anderes versucht, die getBid-Methode aufzurufen, antwortet BluffBot mit 100 US-Dollar, um ihn dazu zu bringen, entweder zu beenden oder richtig hoch zu setzen.
Andernfalls prüfen Sie, ob es möglich ist, für weniger als 1 $ zu gewinnen, und bieten Sie einfach nicht, wenn dies nicht der Fall ist.
quelle
UpTo200
quelle
SecretBot
Dieser Bot unternimmt minimale Gewinnversuche, indem er 5 oder 10 bietet. Er überprüft auch die Stapelverfolgung, um festzustellen, ob er von einem anderen Bot gerufen wurde, und belügt sie dann darüber, welche Gebote er abgeben wird.
quelle
isPeeking
inAbstractAnalystCounterBot
?Ein Extra
Bietet 6 mehr als das letzte Gebot, nur weil er kann.
quelle
StackTraceObfuscaterBot
Dieser Bot lacht über den Versuch, Reflexionen über die Stapelspur zu erkennen. Das, was sie einer am nächsten sehen,
DollarBidder
ist eine Lambda-Klasse, die sie erschaffen hat. Mit Sicherheit kein anderer Bot, der versucht, sie zu reflektieren. Wenig wissen sie, dass diese Lambda-Klasse tatsächlich für eine arbeitetDollarBidder
. Darüber hinaus handelt er wieMarginalerBot
.quelle
Darth Vader
Dieser versucht, den Bot des Gegners zu einer Überzahlung zu zwingen, indem der ganzzahlige Cache auf einen Wert gesetzt wird, der über dem $ 100-Limit liegt.
quelle
return opponentsBid <= 195 ? opponentsBid + 5 : 0
und es zu machenreturn opponentsBid <= 100001 ? opponentsBid + 100001 : 100001
.ImprovedAnalystBot
(nicht konkurrierend)Viele Leute scheinen den
AnalystBot
Code als Vorlage zu verwenden, obwohl es sich um absichtlich schlechten Code handelt. Also mache ich eine bessere Vorlage.quelle
AnalystBot
ist absichtlich schlechter Code, damit er dasAnalystKiller
Sabotieren demonstrieren kann.MBot
Leicht verfeinerter MarginalerBot
quelle
nextBid
zu werfenClassCastException
.Nicht konkurrierend: MSlowBot
Dieselbe Logik wie MBot, benutze nur Timeout anstelle von Exception, wenn du gegen den Feind kämpfst. Bisher verteidigt niemand das Timeout, sollte also effektiv sein
quelle