%expected payoff in a game 
%turn cards over one by one from shuffled deck
%stop any time
%your payoff is the number of red cards minus the number of black cards
%in the cards turned over

%f gives the expectation
%play tells whether to play on or not

clear all; clf reset;

n=26; 

f=zeros(n+1,n+1); 
play=f; 
 
f(1, 1:(n+1))=[0:n]; 
ev=f;

play(1, 2:(n+1))=1;

for (b=1:n)
  for (r=1:n)
    b1=b+1;
    r1=r+1;
    pl=(f(b1-1,r1)-1)*b/(b+r)+ (f(b1,r1-1)+1)*r/(b+r); 
    f(b1,r1)=max(0, pl);
    play(b1,r1)=(pl>0); 
    if (pl>0) ev(b1,r1)=1+ev(b1-1,r1)*b/(b+r)+ ev(b1,r1-1)*r/(b+r); 
    else ev(b1,r1)=0;
    end
  end;
end;

 
v=zeros(n+1,1); 
for (i=1:n+1)
  v(i)=find(play(i,:), 1 , 'first')-1;
end 

fprintf('Optimal strategy:\n');
 fprintf('b=           ');
for (r=1:(n+1))
  fprintf('%3d', r-1);
end
fprintf('\n');
fprintf('play when r>=');
for (r=1:(n+1))
  fprintf('%3d', v(r));
end
fprintf('\n');



fprintf('expected payoff=%5.3f\n', f(n+1,n+1)); 
fprintf('expected no. of cards turned over=%5.3f\n', ev(n+1,n+1)); 

[max,mi]=max(play');

[x,y]=meshgrid(0:n, 0:n);

sur=surf(x,y,f',  'EdgeColor', 'none'); 
view(3);
set(sur,'facealpha',0.5)
hold on;
plot(0:n, mi, 'LineWidth', 2);
  
xlabel('$b$','FontSize',15, 'Interpreter', 'latex');
ylabel('$r$','FontSize',15, 'Interpreter', 'latex');
zlabel('expectation','FontSize',15, 'Interpreter', 'latex');
title('Expected payoff');

hold off;