Java, $804,991
Score is from 1001 rounds. It is probably too close to call between this answer and Stephan Schinkel's.
This is based on my answer in the previous challenge, in that it uses the same entropy-based calculation to estimate payoffs. The main difference is that it simply now takes envelopes in pairs (1 & 2, then 3 & 4, so on) and looks at the possible combinations of take-take, take-pass, pass-take, etc. It also calculates the exact estimated score when the number of valid envelopes is really small.
The "wrapper" I wrote isn't really a true wrapper, it just gives envelopes in pairs instead of calling an Oracle(1)
function every other round.
Overall, I would say that, despite the increased complexity, this bot really isn't better than my previous one.
Player
import java.lang.Math;
public class Player2
{
public int[] V;
public Player2(int s)
{
V = new int[s];
for(int i = 0; i<V.length; i++)
{
V[i] = i+1;
}
////System.out.println();
}
public boolean [] takeQ(int x, int y)
{
//System.out.println("Look: " + x + " " + y);
boolean [] move = new boolean[]{false,false};
double max = 0;
double val = 0;
int[] nextV = V;
////System.out.println("look " + x);
int i = find(V,x);
if(i >= 0) //if found
{
//try taking first envelope
int[] newVt = takeSlice(V,i);
//System.out.println(" T: " + ats(newVt));
int j = find(newVt,y);
if(j >= 0)
{
//try taking first and second
int[] newVtt = takeSlice(newVt,j);
val = x + y + calcVal(newVtt);
//System.out.println(" TT: " + ats(newVtt) + " " + val);
if(val > max)
{
move = new boolean[]{true,true};
max = val;
nextV = newVtt;
}
}
//try taking first and passing second
int[] newVtp = passSlice(newVt,j);
val = x + calcVal(newVtp);
//System.out.println(" TP: " + ats(newVtp) + " " + val);
if(val > max)
{
move = new boolean[]{true,false};
max = val;
nextV = newVtp;
}
}
int[] newVp = passSlice(V,i);
//System.out.println(" V: " + ats(V));
//System.out.println(" P: " + ats(newVp));
int j = find(newVp,y);
if(j >= 0)
{
//try passing first and taking second
int[] newVpt = takeSlice(newVp,j);
val = y + calcVal(newVpt);
//System.out.println(" PT: " + ats(newVpt) + " " + val);
if(val > max)
{
move = new boolean[]{false,true};
max = val;
nextV = newVpt;
}
}
//try taking first and passing second
int[] newVpp = passSlice(newVp,j);
val = calcVal(newVpp);
//System.out.println(" PP: " + ats(newVpp) + " " + val);
if(val > max)
{
move = new boolean[]{false,false};
max = val;
nextV = newVpp;
}
V = nextV;
//System.out.println(" NEW: " + ats(V));
return move;
}
public static String ats(int [] a)
{
String s = "";
for(int i = 0; i < a.length; i++)
{
s += a[i] + ",";
}
return s;
}
public static int[] takeSlice (int[] list, int loc)
{
int [] newlist = new int[list.length - loc - 1];
for(int j = loc + 1; j < list.length; j++)
{
newlist[j - loc - 1] = list[j];
}
return newlist;
}
public static int[] passSlice (int[] list, int loc)
{
int [] newlist = list;
if(loc >= 0)
{
newlist = new int[list.length-1];
for(int k = 0; k < loc; k++)
{
newlist[k] = list[k];
}
for(int k = loc + 1; k < list.length; k++)
{
newlist[k-1] = list[k];
}
}
return newlist;
}
public static double calcVal(int [] list)
{
if(list.length < 8)
{
for(int i : list)
{
////System.out.print(i + ",");
}
////System.out.println();
return computeMean(list);
}
return smoothEstimate(list);
}
public static double computeMean(int[] V)
{
if(V.length == 1)
{
return V[0];
}
else if(V.length > 1)
{
double[] Es = new double[V.length];
for(int i = 0; i < V.length; i++)
{
int[] newVp = new int[V.length - 1];
for(int j = 0; j < i; j++)
{
newVp[j] = V[j];
}
for(int j = i + 1; j < V.length; j++)
{
newVp[j-1] = V[j];
}
double pass = computeMean(newVp);
int[] newVt = new int[V.length - i - 1];
for(int j = i + 1; j < V.length; j++)
{
newVt[j - i - 1] = V[j];
}
double take = V[i] + computeMean(newVt);
if(take > pass)
{
Es[i] = take;
}
else
{
Es[i] = pass;
}
}
double sum = 0;
for(double d : Es)
{
sum += d;
}
return sum/V.length;
}
else
{
return 0;
}
}
public static double smoothEstimate(int [] list)
{
double total = 0;
for(int i : list)
{
total+=i;
}
double ent = 0;
for(int i : list)
{
if(i > 0)
{
ent -= i/total * Math.log(i/total);
}
}
////System.out.println(" total " + total);
////System.out.println(" entro " + Math.exp(ent));
////System.out.println(" count " + list.length);
return total * Math.pow(Math.exp(ent),-0.5) * 4.0/3;// * 1.1287 + 0.05284);
}
public static int find(int[] list, int search)
{
int first = 0;
int last = list.length - 1;
int middle = (first + last)/2;
while( first <= last )
{
if ( list[middle] < search )
first = middle + 1;
else if ( list[middle] == search )
break;
else
last = middle - 1;
middle = (first + last)/2;
}
if(first > last)
{
return -1;
}
return middle;
}
}
Controller
import java.lang.Math;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;
public class Controller2
{
public static void main(String [] args)
{
int size = 10000;
int rounds = 1001;
ArrayList<Integer> results = new ArrayList<Integer>();
for(int round = 0; round < rounds; round++)
{
int[] envelopes = new int[size];
for(int i = 0; i<envelopes.length; i++)
{
envelopes[i] = i+1;
}
shuffleArray(envelopes);
Player2 p = new Player2(size);
int cutoff = 0;
int winnings = 0;
for(int i = 0; i<envelopes.length; i+=2)
{
boolean [] take = p.takeQ(envelopes[i],envelopes[i+1]);
if(take[0] && envelopes[i] >= cutoff)
{
winnings += envelopes[i];
cutoff = envelopes[i];
}
if(take[1] && envelopes[i+1] >= cutoff)
{
winnings += envelopes[i+1];
cutoff = envelopes[i+1];
}
}
results.add(winnings);
}
Collections.sort(results);
System.out.println(rounds + " rounds, median is " + results.get(results.size()/2));
}
//stol... I mean borrowed from http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array
static void shuffleArray(int[] ar)
{
Random rnd = new Random();
for (int i = ar.length - 1; i > 0; i--)
{
int index = rnd.nextInt(i + 1);
// Simple swap
int a = ar[index];
ar[index] = ar[i];
ar[i] = a;
}
}
}
Bitcoin address: 1BVBs9ZEP8YY4EpV868nxi2R23YfL7hdMq
Wow, I can't believe I overslept :O – Beta Decay – 2015-08-03T07:18:13.417
@Beta Decay clock is ticking! :) – LivingInformation – 2015-08-03T07:19:12.467
What's the sense of the rracle? You could build your own free oracle by just keeping a tally of all previously read envelopes. What am I getting wrong? – Luis Mendo – 2015-08-03T11:26:00.570
1@LuisMendo With your own tally, you can only know the mean of all remaining values. With the oracle, you can get the mean of the next
M
values, where you get to chooseM
. – Reto Koradi – 2015-08-03T13:34:52.4031Since all solutions to your previous challenge are also valid solutions to this challenge, can we consider them implicitly submitted? – Reto Koradi – 2015-08-03T13:36:14.873
@Reto updated the OP with a second note to that effect. – LivingInformation – 2015-08-03T14:40:50.467
@RetoKoradi Got it. Thanks – Luis Mendo – 2015-08-03T17:20:46.370