Este é um desafio KOTH para o jogo de leilão de notas de dólar na teoria dos jogos. Nele, um dólar está sendo vendido pelo maior lance. Os lances aumentam em incrementos de 5 ¢ e o perdedor também paga o lance. A idéia é que ambos os jogadores escalem a guerra de lances muito além do valor de um dólar para reduzir suas perdas.
Vamos torcer para que seus bots sejam mais inteligentes que isso.
Você criará um bot para jogar este jogo, estendendo a net.ramenchef.dollarauction.DollarBidder
classe. Você deve implementar o nextBid
método que retorna o próximo lance do seu bot, considerando o lance anterior do outro bot. Se necessário, você também pode usar o newAuction
método para redefinir para cada leilão a classe do bot do oponente.
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);
}
Os lances vão até que aconteça um dos seguintes:
nextBid
lança uma exceção. Se isso acontecer, o bot que lançou a exceção paga o lance anterior e o outro bot recebe o dólar de graça.- Qualquer bot não paga o suficiente para cobrir o lance anterior. Se isso acontecer, ambos os bots pagam seus lances (o perdedor paga seu lance anterior) e o vencedor recebe um dólar.
- Ambos os bots oferecem lances acima de US $ 100. Se isso acontecer, ambos os bots pagam US $ 100 e nenhum bot recebe o dólar.
São realizados 2 leilões para cada combinação de bots. Os robôs são pontuados pelo lucro total que obtiveram nesses leilões. A pontuação mais alta vence.
Exemplos
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
Não use isso como modelo para bots com análise analítica; use em ImprovedAnalystBot
vez disso.
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;
}
}
Regras adicionais
- As brechas padrão são proibidas.
- É permitido sabotar outros bots, mas tentar alterar a visibilidade do campo / método resultará em
SecurityException
s misteriosos . Uma exceção está fazendo com que outro bot ultrapasse o limite de 500ms. - Os robôs não podem acessar o pacote do corredor, exceto para estender a
DollarBidder
classe. - Todos os métodos devem retornar em 500 ms ou menos.
- Bots não precisam ser determinísticos.
- Seu lance não precisa ser múltiplo de 5 ¢.
- $ 1 = 100 ¢
- Os resultados serão publicados em 24 de abril de 2018.
Resultados
Veja as rondas individuais aqui.
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
Parabéns MTargetedBot
com um lucro de $ 14,30!
fonte
LuckyDiceBot
Por exemplo, lances em incrementos2-12
aleatórios.Respostas:
MTargetedBot
fonte
MimicBot
Vaca sagrada. Eu esperava que isso fosse simples de escrever e depois passei 3 horas nele.
Em essência,
MimicBot
mantém uma lista contínua dos bots disponíveis. Quando se trata de um novo leilão, ele percorre a lista em busca do mais eficaz contra o atual oponente. Ele então usa esse bot como uma "referência" no leilão.Para fins de teste, seria melhor usar um subconjunto aleatório dos envios ou o conjunto completo. Ela começa com
GreedyBot
,MimicBot
e mais um bot que só ordena 5 ¢.fonte
InsiderTradingBot
No espírito da resposta de @ StephenLeppik, o InsiderTradingBot conhece todos os seus oponentes e entende suas estratégias. Sua vez, Stephen.
fonte
RichJerk
bot fizesse uma exceção específica para ele e oferecesse US $ 0 por ele.AnalystBot
, nãoAnalyst
.MirrorBot
Faz o inimigo jogar contra si mesmo.
fonte
Analyst
espetacularmente.Edit : Alterações direcionadas na classe DollarBidder quebraram este bot.
ScoreOverflowBot
Após um leilão, sua pontuação será -2147483645, mas na próxima vez perderá 5 ¢ ou 105 ¢, tornando a pontuação positiva e muito grande. Todas as outras perdas seriam insignificantes.
No primeiro leilão, também faria a GreedyBot apostar -2147483646, que não é divisível por 5.
fonte
score
está protegido por pacotes. Seus bots não podem acessá-lo.TargetValueBot
Não é possível testar isso no momento, então, deixe-me saber se está quebrado.
Basicamente, escolha um valor para o dólar e supere o oponente até excedermos esse valor.
fonte
MarginalBot
Muito simples, tenta determinar se um oponente contestaria uma oferta mínima e, se não, colocá-la.
MarginalerBot
Uma versão nova e mais inteligente do MarginalBot que verifica se pode fazer algum movimento lucrativo sem contestação, em vez de apenas esperar ganhar com o mínimo.
Como está na mesma família do meu bot anterior, mas evita estratégias que tentam vencê-lo, achei que uma nova entrada no mesmo post era a maneira mais razoável de apresentá-la.
Editar 1: fez uma pequena alteração no método newAuction para otimizar contra outros bots do tipo analisador.
Edit 2: Alterou o MarginalerBot para minimizar as perdas contra estratégias sorrateiras ou não determinísticas.
fonte
BorkBorkBot
Desiste se não pode empatar.
fonte
RandBot
Tinha que ser feito.
fonte
DeterrentBot
Tentativas de persuadir quaisquer bots analiticamente pensados de que o único movimento vencedor é não jogar.
fonte
LuckyDiceBot
LuckyDiceBot confia apenas em seus dados. Ele joga dois dados, adiciona a soma ao valor do licitante atual e oferece muito. Se não for suficiente para superar a oferta do oponente, ele reduz suas perdas e segue seu caminho.
fonte
opponentsBid
innextBid(int opponentsBid)
mantém o lance total que seu oponente fez até o momento, não o próximo lance. Um termo melhor para o método seriaraise
(como o termo do Poker) imho. 2. Seu bot não morde incrementos de 5, portanto, está validando uma das regras. Se esses problemas forem resolvidos, ainda gosto do conceito, porque os bots analíticos não serão capazes de combater e, portanto, você provavelmente vencerá com bastante frequência.DeterredBot
DeterredBot ganha uma fortuna com seus jogos ilegais com o LuckyDiceBot. Então, é claro que quando a polícia (DeterrentBot) chega, ele precisa rapidamente dispor de seus ganhos de alguma forma, como licitar no próximo leilão.
fonte
InfllationBot
Não é possível testar isso no momento, então, deixe-me saber se está quebrado.
A cada rodada, o valor do dólar aumenta.
fonte
opponentsBid
ainda é 0)?Não concorrente: AbstractAnalystCounterBot
Isso não pretende ser uma submissão verdadeira, mas sim um modelo para outros usarem para impedir bots de criação de animais de estimação como
MirrorBot
eMimicBot
.Como é o construtor padrão, não há necessidade de chamá-lo em sua subclasse. Ele implementa um
isPeeking
método para determinar se outro bot está bisbilhotando.fonte
BreakEvenAsap
Cenários
<= 0
ele perde.[5,95]
: ofereça 100 você mesmo. Seu oponente para agora, ou faz lances acima de 100 no total. Nesse caso, você para de oferecer para que eles tenham a vitória e se igualam.>= 100
: ofereça 0 a si próprio para perder, mas empate.fonte
EvilBot
Lança um erro em vez de uma exceção para confundir os analistas.
fonte
BuzzardBot
Tenta avaliar o oponente com o qual se defronta e certifique-se de não morder mais do que pode mastigar.
fonte
AnalystOptimizer
paralelepípedos de partes de outros bots. este é reproduzido ao tentar ser AnalystBot e, se malsucedido, torna-se BorkBorkBot.
Eu não acho que este fará isso bem.
fonte
AnalystKiller
.CounterBot
Contadores:
DarthVader
contadores, causando umSecurityException
antes do início da licitação, mas lancei 5 apenas por precaução.AnalystBot
eAnalystOptimizer
ambos olharão para a minha resposta quando oferecer um lance de 95. Nesse caso, mostrarei que lancei 100 para que ele faça um lance de 95. No entanto, lancei 5, se eu começar (ou 100, se eles começaram), para que eles percam 95 centavos e eu ganhe a nota de 1 USD oferecendo apenas 5 centavos ou empatando.MirrorBot
vai oferecer o que eu iria oferecer contra ele. Então, lancei apenas 5, e quem começar ganha 95 centavos e o outro perde 5 centavos.MarginalBot
oferecerá 5 se eu oferecer menos que 10 (ou o que começa), caso contrário, oferecerá 0. Portanto, se eu oferecer apenas 5 quando eu começar ou 10 quando começar, eu ganho 95 ou 90 centavos e eles perdem 5 centavos.GreedyBot
sempre oferece mais 5 do que eu, então lance 0 para empatar e deixe que eles tenham a vitóriaOnlyWinningMove
eAnalystKiller
ambos sempre dão lances 0, então lance 5 para ganharTargetValueBot
fará lances no intervalo[100,200]
, então lance mais 5 a cada vez até chegar aos 190. Nesse caso, aumentamos para 200 para atingir o ponto de equilíbrio ao ganhar o dólar (e deixá-los perder 190 ou 195, dependendo de quem começou)BorkBorkBot
fará lances no intervalo[5,95]
, então lance 5 a mais também. Assim que eles oferecerem 85 ou 90 (dependendo de quem começou), ofereça 95 você mesmo. Eles perderão 85 ou 90 centavos e você ganha a nota de 1 USD por um lucro de 5 centavos.DeterrentBot
oferecerá 5 se eles começarem ou 100 se começarmos, então apenas ofereça 105 para que contrariem com 100, fazendo com que eles percam 100 e nós percam apenas 5 centavos ao ganhar a nota de 1 dólar.BreakEvenAsap
oferecerá 100 imediatamente. Portanto, se eles começaram com seu lance de 100, contra-105 para ganhar 95 centavos e deixe-os perder 100. Se podemos começar apenas lance 100, então ambos empatamos.RichJerk
ofereça 10.001 imediatamente, portanto, ofereça 0 para empatar e deixe que eles percam 9.901.DeterredBot
não me conhece e, portanto, dará lance 0, então lance 5 para ganhar.LuckyDiceBot
continua a licitar até vencer. Portanto, se começássemos, ofereça 5 na esperança de que eles ofereçam o mais alto possível para ganhar o dólar. Se eles começaram, lance apenas 0 para permitir que eles tenham a vitória e se igualem.RandBot
oferecerá lances aleatórios no intervalo[5,100]
, portanto, ofereça mais 5 até que pare. Nesse caso, você ganhou 95 centavos e eles perderam0-100
.UpTo200
fará (como o nome indica) oferecer até 200. Portanto, faça um lance 5 mais alto até que eles parem. Ganharemos a nota de 1 dólar e teremos uma perda total de 105 centavos, mas eles perdem 200 centavos.InsiderTradingBot
não me conhece, então lance 5 centavos para ganharMimicBot
foi o mais difícil. Apenas faça um lance de 10 para começar ou contrariar o primeiro lance de 5. Se eles tentarem me acessar, lançarei uma RuntimeException (que eles capturarão, nesse caso, ela atuaria como se eu tivesse feito um lance de 100) - embora isso interrompa o loop while interno). Com base nos inimigos que ele possui, o HashSet acontece de maneira diferente. Vou ter que revisitar e olhar mais de perto para ver se há um contador real.RiskRewardBot
não me conhece, lance apenas 5, caso em que lancei 5 para ganhar.MarginalerBot
vai bit até 100, dependendo do que eu ofereceria. Se eu puder começar, lance 90, lance 95, lance 100, para que lance 0 e perca 95 centavos, enquanto eu ganho a nota de 1 USD e o mesmo empate. Se, em vez disso, começar, ele verá que eu ofereceria 90 contra ele, então fará um lance de 90, então lancei 95 para que faça um lance de 0 e perca 90 centavos, enquanto eu ganho a nota de 1 USD com um lucro de 5 centavos.BuzzardBot
analisará todos os meus contadores no intervalo[0,100)
. Se eu fizer um lance100
imediatamente, ele usaráoppFlag = 0
e a matriz completa de 100 tamanhos conterá 100x o valor 100. No switchcase 0
, o loop estará no intervalo[0,100)
novamente e, comoi + 5
no máximo será 104, o ifbids[i] < i + 5
nunca será verdadeiro , portanto, o lance permanece 0.ImprovedAnalystBot
sempre teráthis.enemy = null
porque seu oponente éCounterBot
, não ele próprio. Por isso, ele sempre oferecerá 0, o que eu contra-atento com um lance de 5.InflationBot
fará um lance de 0 para empatar quando começar, caso contrário, continuará fazendo um lance de 5. Então, faça um lance de 0 para empatar imediatamente e deixe que eles tenham a vitória.ScoreOverflowBot
fará um lance próximoInteger.MAX_VALUE
se eles começarem, caso contrário, fará um lance105
. Portanto, se eles fizeram um lance de 105, apenas lance 110 (eles perderão 105, perderemos 10); caso contrário, lance 0 para permitir que eles tenham a vitória.MBot
é o mesmo queMarginalerBot
, mas com proteção adicional contra 'espreitar' os oponentes. Desde que eu não 'espio', é basicamente o mesmo queMarginalerBot
.SecretBot
fará com que seuisPeeking()
método retorne false; portanto, se ele iniciar ou se eu oferecer 5, oferecerá 5 ou 10, respectivamente. Caso contrário, ele oferecerá 0. Portanto, se eu começar ou não,opponentsBid + 5
me levará a ganhar de qualquer maneira, com meus 10 centavos ou 15 centavos, fazendo com que eles percam 5 ou 10 centavos.BluffBot
analisará o que eu ofereceria quando o lance dele for 95 e, se for maior ou igual a 100, o lance será 0 para empate, caso contrário, o lance seráopponentsBid + 5
. Então, eu apenas lanceiopponentsBid + 5
. Ficará empatado, independentemente de quem começar, e eu ganho 100 ou 95 centavos, dependendo de ter começado ou não.StackTraceObfuscaterBot
agirá da mesma forma queMarginalerBot
.EvilBot
lance sempre 5, então lanceopponentsBid + 5
. De qualquer forma, eles perderão esses 5 centavos e ganharemos o lance de 1 USD (com um lance de 5 centavos se começarmos ou 10 lances de centavo se eles começarem).MSlowBot
é o mesmo queMBot
e, portanto, tambémMarginalerBot
.Deixe-me saber se você encontrar algum erro de digitação ou falha em meus contadores.
fonte
MirrorBot
chama newAuction com sua própria classe, então isso é um problema. Além disso, fico feliz em saber que as três horas que passei no MimicBot não foram em vão.newAuction
porque falharia com mais frequência do que não .. Não posso combaterMirrorBot
nem pode me contrariar. Quem começa dos dois ganha 95 centavos e o outro perde 5 centavos.BorkBorkBot
, você não deve aumentar para 95 quando atingir 85? Caso contrário, você estará oferecendo 95 se eles começarem.RiskRewardBot
Não é possível testar isso no momento, então, deixe-me saber se está quebrado.
O objetivo é obter a maior pontuação total, portanto, não se preocupe em bater em ninguém. Basta ter as vitórias fáceis e não desperdiçar dinheiro com possíveis perdas.
fonte
BluffBot
Um espião que você conhece é mais valioso do que nenhum espião ...
Se alguém tentar chamar o método getBid, o BluffBot responderá com US $ 100 para induzi-lo a desistir ou apostar muito alto.
Caso contrário, veja se é possível ganhar com menos de US $ 1 e simplesmente não lance se não for.
fonte
UpTo200
fonte
SecretBot
Esse bot faz tentativas mínimas de vitória, oferecendo 5 ou 10. Ele também verifica o rastreamento da pilha para ver se ele foi chamado por outro Bot e depois mente para eles sobre quais lances ele fará.
fonte
isPeeking
entrarAbstractAnalystCounterBot
?One Extra
Oferece 6 a mais do que o último lance, apenas porque ele pode.
fonte
StackTraceObfuscaterBot
Este bot ri de tentativas de detectar reflexão através do rastreamento de pilha. A coisa mais próxima que eles vêem
DollarBidder
é uma classe lambda que ele criou. Claramente, nenhum outro bot tentando refleti-los. Mal sabem eles que a classe lambda está realmente trabalhando para aDollarBidder
. Além disso, ele age assimMarginalerBot
.fonte
Darth Vader
Este tenta forçar o bot do oponente a pagar em excesso, definindo o cache inteiro como um valor acima do limite de US $ 100.
fonte
return opponentsBid <= 195 ? opponentsBid + 5 : 0
e torná-lasreturn opponentsBid <= 100001 ? opponentsBid + 100001 : 100001
.ImprovedAnalystBot
(não concorrente)Muitas pessoas parecem estar usando o
AnalystBot
código como modelo, mesmo que seja um código deliberadamente ruim. Então, eu estou fazendo um modelo melhor.fonte
AnalystBot
é um código deliberadamente incorreto, para que possa demonstrar aAnalystKiller
sabotagem.MBot
MarginalerBot ligeiramente refinado
fonte
nextBid
jogarClassCastException
.Não concorrente: MSlowBot
Mesma lógica do MBot, basta usar timeout em vez de Exception ao lutar contra o inimigo. Até agora, ninguém está defendendo novamente o tempo limite, portanto deve ser eficaz
fonte