Print Story Programming Fun Challenge 18: The good gambler
Puzzles & Riddles
By TPD (Mon Nov 06, 2006 at 02:49:54 AM EST) PFC, Programming fun Challenge (all tags)
well it's been along time since the last PFC, and I'm not really sure whether the interest exists on the site for another one(?)

However I for one miss them and assuming there are enough people who would like to see the original fun challenge revived, I propose PFC18: The good gambler



During my last visit to Zorastavia, I came upon a game played in many casinos in that little known Eastern European country.

The gambler starts off with 64 Sules having payed considerably extra to enter the game in the first place*, and a full deck of randomly shuffled numbered cards (numbered 1 to 52).

The first card is drawn and the gambler then has to bet (up to a maximum of the 64 Sules he or she holds) on whether that card is higher than the next card that will be drawn out - if the card drawn out is lower the gambler gets double his bet back (ie if he put down 5 Sules and won he would be on a total of 69 Sules for the next round), otherwise he looses it.

Whether the gambler wins or looses he gets to bet on the following card but with the limitation that he can only bet a maximum of twice the stake (assuming he has the money to do so) he put on the previous round. The game continues for 51 rounds so the final round assuming the gambler has been paying attention he knows exactly whether he will win or loose his hand). If at any point the gambler bids 0 Sules he or she will take no further part in the game for the rest of that deck.

The Challenge then is to write a program that is a good player of the above game, being able to card count is assumed to keep the problem from being a chore programatically. Each round will consist of a separate run of your program which will be passed the following lines via the standard input

Total Money currently held
Maximum bet allowed
Number of cards left in the pack which your current card will beat
Number of cards left in the pack which will beat you current card

and will be expected to output a single value as to how much it will bet.

The problem will be judged on results based on a number of full games (probably in the order of 100) each starting from scratch at 64 sules total. Each program will face the same decks and the program(s) that have won the most (or lost the least) after all the games will be crowned winner.

Entries should be put in your files with a link in a comment on this diary - and the closing date from entries is 1pm GMT on Monday the 20th, a simple test framework will be posted at least a prior weak prior to the deadline.

*(I conveniently forget the exact number)

< Attn: LHuSi infidels | BBC White season: 'Rivers of Blood' >
Programming Fun Challenge 18: The good gambler | 54 comments (54 topical, 0 hidden) | Trackback
Programming? by DullTrev (4.00 / 4) #1 Mon Nov 06, 2006 at 03:01:11 AM EST

What do you take us for? Writing, yes. Music, sure. Photos, fine. Comics, absolutely. We're artistic and interesting, not boring and nerdy.

So, like any restrictions on what it is coded in? HTML would do this, right?


--
DFJ?
We're artistic and interesting, not boring and.... by TPD (2.00 / 0) #2 Mon Nov 06, 2006 at 03:09:07 AM EST
nerdy

Oi speak for yourself!

Taken from this page http://community.moertel.com/ss/space/Programming+Fun+Challenge....

Notes on solutions

    * Any programming language is acceptable, provided that open-source compilers or interpretors for that language are available, and provided that the judge can execute programs written in that language on test computers.


why sit, when you can sit and swivel with The Ab-SwivellerTM

[ Parent ]
I am by Phage (2.00 / 0) #4 Mon Nov 06, 2006 at 03:14:20 AM EST
Although I miss the motorcycle posts.

[ Parent ]
If you just draw a Visio diagram, by ambrosen (2.00 / 0) #7 Mon Nov 06, 2006 at 04:00:55 AM EST
then someone will implement it for you and you can get all the glory.

I hope you're not too offended. I mean, you're not a Rational Rose user, are you?

[ Parent ]
Are you like a fiftysomething manager? by bob6 (4.00 / 1) #12 Mon Nov 06, 2006 at 07:08:41 AM EST
Stuff is done in XML nowadays.

Cheers.
[ Parent ]
(Comment Deleted) by yicky yacky (4.00 / 1) #3 Mon Nov 06, 2006 at 03:14:13 AM EST

This comment has been deleted by yicky yacky



I understand nothing about this by nebbish (4.00 / 1) #5 Mon Nov 06, 2006 at 03:45:09 AM EST
But if anyone comes up with something that will guarantee I win money pls PM me.

--------
It's political correctness gone mad!

(Comment Deleted) by yicky yacky (4.00 / 9) #6 Mon Nov 06, 2006 at 03:49:25 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
(Comment Deleted) by yicky yacky (4.00 / 2) #8 Mon Nov 06, 2006 at 04:02:51 AM EST

This comment has been deleted by yicky yacky



1.) args is probably simpler by TPD (4.00 / 1) #9 Mon Nov 06, 2006 at 04:33:22 AM EST
I was thinking "Standard Input" because I was initially thinking the program would have a life time beyond a single round.... ie read card output bet read card output bet etc

but with the program run once per bet as I decided on making it, passing on the commandline probably makes more sense, but if anyone prefers one over the other I will make the test framework be able to supply either.

2.) yes 4 unsigned integers.

3.) yes.

why sit, when you can sit and swivel with The Ab-SwivellerTM

[ Parent ]
Clever by Xenocide (4.00 / 1) #10 Mon Nov 06, 2006 at 06:09:43 AM EST
Clearly the winner will be decided primarily by quality of analysis of the game. I was hoping Wikipedia would have such a game, but the closest they come is a game called "casino war." And cleverly, your problem is pretty much unsearchable on Google, at least without knowing the name of this particular game.

If anyone else is wondering where to start thinking about this game, I think you might consider the case where there are only 3 cards left.

what aspect of the results? by garlic (4.00 / 2) #11 Mon Nov 06, 2006 at 06:59:28 AM EST
I can get very quickly create an algorithm with an average win of over 1000 (in 10,000 runs) but the std deviation is huge. 1 big win can be a huge skew on the mean.



Eeek..... by TPD (2.00 / 0) #13 Mon Nov 06, 2006 at 07:24:37 AM EST
hopefully I don't fail it.

The idea was to have 100 runs and the winner to be the one who had the highest total summing together the final scores of all their efforts.

But it may well be that the problem is so skewed by winning streaks that it needs a bit of a rework.

why sit, when you can sit and swivel with The Ab-SwivellerTM

[ Parent ]
well, by garlic (2.00 / 0) #14 Mon Nov 06, 2006 at 07:49:43 AM EST
a median result might be a better comparotor. this will take high runs and low runs into account, but a 0 return gets weighted equally with a 20,000 return. The median result means that ~ half the time you get that amount or higher, and ~ half the time you get that amount or lower.

Another option would be to involve the std deviation into the scoring. An algorithm resulting in a high std deviation needs a bigger starting wad of cash so that you can play long enough to hit the mean.


[ Parent ]
(Comment Deleted) by yicky yacky (2.00 / 0) #16 Mon Nov 06, 2006 at 08:45:58 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
depends on the who, now doesn't it. by garlic (2.00 / 0) #17 Mon Nov 06, 2006 at 08:58:58 AM EST
I know that assuming I count cards correctly and build a team up and don't get caught, I can eventually make a ton of money playing blackjack. But that takes a huge bankroll. The longer an algorithm takes to make returns, the worse it is for someone with a smaller bankroll.

I guess we are accounting for that some assuming a 6400 + whatever bankroll.


[ Parent ]
While I'm probably going to keep the challenge by TPD (2.00 / 0) #39 Tue Nov 07, 2006 at 04:49:49 AM EST
pretty much as is (now it's been formalised and this diary is less prominent).

those scoring schemes would probably have been more interesting in the context of this challenge (which I'm starting to wish I'd considerred more closely). I will at least on final write up look at which at the performance chacteristics of each entry.

why sit, when you can sit and swivel with The Ab-SwivellerTM

[ Parent ]
Just to get your test framework going by komet (4.00 / 2) #15 Mon Nov 06, 2006 at 08:33:24 AM EST
here's my initial entry - I may or may not enter a better program later.


#!/bin/sh

if [ $3 -gt $4 ]; then
        echo $2
        exit
fi
echo 1


--
<ni> komet: You are functionally illiterate as regards trashy erotica.

dammit by 256 (4.00 / 1) #18 Mon Nov 06, 2006 at 09:27:05 AM EST
that was going to be my entry.

okay, here is my untested entry, with which i hope only to beat komet's.

#!/bin/sh

bet=$(( $1 - $3 - $4 + 1 ))
if [ $3 -gt $4 ]; then
        if [ $bet -gt $2 ]; then
                echo $2
                exit
        fi
        if [ $bet -gt 1 ]; then
                echo $bet
                exit
        fi
fi
echo 1
---
I don't think anyone's ever really died from smoking. --ni

[ Parent ]
(Comment Deleted) by 256 (2.00 / 0) #19 Mon Nov 06, 2006 at 09:56:33 AM EST

This comment has been deleted by 256



[ Parent ]
for kicks by 256 (2.00 / 0) #20 Mon Nov 06, 2006 at 10:51:52 AM EST
here's the same program as a one line perl script, with an added test to not bet on the last round if a loss is guaranteed. now i'm really done.

#!/usr/bin/perl
use List::Util qw(max min);
print ((($ARGV[2] > $ARGV[3]) ? (max 1, (min $ARGV[1] , ( $ARGV[0] - $ARGV[2] - $ARGV[3] + 1))) : (min 1 ,  ($ARGV[2] * $ARGV[0] - $ARGV[3] + 1))) . "\n");
---
I don't think anyone's ever really died from smoking. --ni

[ Parent ]
gah.... by 256 (4.00 / 1) #21 Mon Nov 06, 2006 at 10:56:20 AM EST
fucking boundary conditions.

#!/usr/bin/perl
use List::Util qw(max min);
print ((($ARGV[2] > $ARGV[3]) ? (max 1, (min $ARGV[1] , ( $ARGV[0] - $ARGV[2] - $ARGV[3] + 1))) : (min 1 ,  (max 0, ($ARGV[2] * $ARGV[0] - $ARGV[3] + 1)))) . "n");

---
I don't think anyone's ever really died from smoking. --ni

[ Parent ]
fine. by garlic (2.00 / 0) #22 Mon Nov 06, 2006 at 12:12:27 PM EST
parent post of spoilered post.


using matlab by garlic (2.00 / 0) #24 Mon Nov 06, 2006 at 12:26:52 PM EST
Here's the key bits. the rest of the code made the runs work correctly.

odds = (cards_left - cards_higher) / cards_left;
% bet money * odds. don't exceed max, don't go to 0.
bet = min(floor(money*odds),max_bet);
if money>0 &bet == 0
bet = 1;
end;

mean of 1,169.
max of 34,814.
median of 266.
std dev of 3,694
went broke 11 times.
didn't exceed 65 30 times.


[ Parent ]
Q: by komet (2.00 / 0) #23 Mon Nov 06, 2006 at 12:15:38 PM EST
Is it permissible to save state on disk? One might want to do this in order to keep track of one's opponent and possible flaws in their algorithm. Though I would prefer state-keeping to be explicitly forbidden by the rules, if only to keep the challenge simple.

How will invalid bets be handled - does one lose by forfeit, or does the framework correct too-high bids down to the maximum?

Is each round played against a single opponent? I'm not sure it actually matters.



--
<ni> komet: You are functionally illiterate as regards trashy erotica.

oh wait by komet (2.00 / 0) #25 Mon Nov 06, 2006 at 12:29:12 PM EST
one isn't actually playing against any other programs, one just bets on the cards that show up, right? Disregard my questions, they make no sense in that case.

The exact winning condition does need to be defined more rigorously (as per your conversation with garlic) because I think it has a big effect on the strategy.

--
<ni> komet: You are functionally illiterate as regards trashy erotica.

[ Parent ]
aren't you playing against the house? by garlic (2.00 / 0) #26 Mon Nov 06, 2006 at 12:31:33 PM EST
The house wins money in that they make you pay something like 100 sheckals to get 64 sheckals in tokens. They then assume (ussually correctly) that you can't really count cards. Then, assuming they're like the US, if you start winning too much, they ask you to leave to minimize their losses.


[ Parent ]
(Comment Deleted) by yicky yacky (4.00 / 1) #28 Mon Nov 06, 2006 at 01:16:57 PM EST

This comment has been deleted by yicky yacky



[ Parent ]
doesn't accept by 256 (2.00 / 0) #29 Mon Nov 06, 2006 at 01:36:48 PM EST
zero bets
---
I don't think anyone's ever really died from smoking. --ni
[ Parent ]
(Comment Deleted) by yicky yacky (2.00 / 0) #30 Mon Nov 06, 2006 at 01:42:27 PM EST

This comment has been deleted by yicky yacky



[ Parent ]
nope. by garlic (4.00 / 1) #31 Mon Nov 06, 2006 at 01:51:41 PM EST
when you bet 0, you're done. You can do it however.


[ Parent ]
right by 256 (4.00 / 1) #32 Mon Nov 06, 2006 at 01:52:34 PM EST
but on the final turn of each round, you definitely want to either bet zero or your max bet, as you have perfect knowledge and there is no next turn to worry about.
---
I don't think anyone's ever really died from smoking. --ni
[ Parent ]
(Comment Deleted) by yicky yacky (2.00 / 0) #33 Mon Nov 06, 2006 at 01:54:00 PM EST

This comment has been deleted by yicky yacky



[ Parent ]
no worries by 256 (4.00 / 1) #34 Mon Nov 06, 2006 at 01:58:01 PM EST
i already fixed it. but i didn't figure it would save you any time for me to post a diff
---
I don't think anyone's ever really died from smoking. --ni
[ Parent ]
and because i'm a cretin by 256 (4.00 / 1) #35 Mon Nov 06, 2006 at 01:58:46 PM EST
i forgot to thank you for the test app in the first place.
---
I don't think anyone's ever really died from smoking. --ni
[ Parent ]
hey, um, by komet (2.00 / 0) #40 Wed Nov 08, 2006 at 09:16:28 AM EST
I think you should have a look at the random.shuffle() function in the standard library...



--
<ni> komet: You are functionally illiterate as regards trashy erotica.

[ Parent ]
(Comment Deleted) by yicky yacky (2.00 / 0) #41 Wed Nov 08, 2006 at 10:10:02 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
Rules by bob6 (4.00 / 1) #42 Thu Nov 09, 2006 at 01:09:40 AM EST
As I understood the rules, the cards are numbered from 1 to 52. A card beats another if its number is higher. In your program you translate the number into a suited rank.
The difference is not critical though there are 3 more cards that can beat yours in a deck...

Am I correct?

Cheers.
[ Parent ]
(Comment Deleted) by yicky yacky (4.00 / 1) #43 Thu Nov 09, 2006 at 02:15:58 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
bob's right by TPD (4.00 / 1) #45 Thu Nov 09, 2006 at 03:58:02 AM EST
I'm just english bad at, there are no draws as such

why sit, when you can sit and swivel with The Ab-SwivellerTM
[ Parent ]
(Comment Deleted) by yicky yacky (4.00 / 1) #46 Thu Nov 09, 2006 at 05:30:54 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
IANAPP by motty (4.00 / 1) #47 Mon Nov 20, 2006 at 08:58:43 AM EST

Why did I have to change line 190 to this:

tempBet = int(eval(child_out_err.read().strip()))

I amd itn ecaptiaghle of drinking sthis d dar - Dr T
[ Parent ]
(Comment Deleted) by yicky yacky (4.00 / 1) #48 Tue Nov 21, 2006 at 01:58:32 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
Similarly, cheers for the test thing by motty (4.00 / 1) #49 Tue Nov 21, 2006 at 05:37:11 AM EST
I wrote a player but I really couldn't be arsed to write a test environment, so it's great just to have one so ta for that. Should have said that before.

My player app spits out floats to 2dp (both with or without newlines at the end) and I'm used to Perlische strings that are numbers of any sort being able to be automatically and silently interpreted as such in suitable context - with no basis whatever I'd thought Python did the same, and, now thinking about it again, perhaps it sometimes does, since you obviously had it working without the eval. Where's the 'behave sensibly' switch in Python?

As for the eval, unnecessary layers of security are my favourite - you could just read the string in and then verify it contained only digits and at most one dot before evalling it. Not much harm thereafter. Does Python have a taint mode equivalent?

I amd itn ecaptiaghle of drinking sthis d dar - Dr T

[ Parent ]
(Comment Deleted) by yicky yacky (2.00 / 0) #50 Tue Nov 21, 2006 at 06:11:28 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
Aha and the Sulettes by motty (2.00 / 0) #51 Tue Nov 21, 2006 at 06:40:21 AM EST

You're absolutely right. There's nothing in the question to say explicitly that Sules are divided into 100 Sulettes, or anything else, so in the absence of clarification it makes sense to only allow integer values of Sules. For some reason I assumed that Sules divide into 100 smaller denomination thingies and coded accordingly. That was pretty dumb.

So float() in Python takes a float and returns an int?

If you use taint as a substitute for writing the code correctly, you may as well not bother; I find taint useful to the extent that it can help write some of the code correctly. rexec looks rather different and be to do with untrusted code rather than untrusted data. It would have had to have been extremely clever if it ever worked, I think.

I amd itn ecaptiaghle of drinking sthis d dar - Dr T

[ Parent ]
(Comment Deleted) by yicky yacky (4.00 / 1) #52 Tue Nov 21, 2006 at 06:49:39 AM EST

This comment has been deleted by yicky yacky



[ Parent ]
Doh! by motty (4.00 / 1) #53 Tue Nov 21, 2006 at 07:03:49 AM EST
I am teh dumb.

I amd itn ecaptiaghle of drinking sthis d dar - Dr T
[ Parent ]
(Comment Deleted) by yicky yacky (2.00 / 0) #27 Mon Nov 06, 2006 at 01:01:54 PM EST

This comment has been deleted by yicky yacky



[ Parent ]
i fial it by 256 (2.00 / 0) #36 Mon Nov 06, 2006 at 02:34:36 PM EST
my program outperforms

#!/usr/bin/perl
print ((int( rand($ARGV[1])) + 1) . "n");

but fails to beat komet's.
---
I don't think anyone's ever really died from smoking. --ni

(Comment Deleted) by yicky yacky (2.00 / 0) #37 Mon Nov 06, 2006 at 02:43:31 PM EST

This comment has been deleted by yicky yacky



(Comment Deleted) by yicky yacky (4.00 / 1) #38 Mon Nov 06, 2006 at 02:46:08 PM EST

This comment has been deleted by yicky yacky



[ Parent ]
Too many not so fun programming language entries by bob6 (4.00 / 1) #44 Thu Nov 09, 2006 at 02:53:54 AM EST
Get the SWI-Prolog interpreter and run:

#!/usr/bin/pl -q -t main -f

main :-
    current_prolog_flag(argv, Args0),
        append(_, [--|Args], Args0),
    maplist(term_to_atom,[Money, MaxBet, Lower, Higher],Args),

    once(bet(Money, MaxBet, Lower, Higher, Bet0)),
    Bet is min(min(Bet0, Money), MaxBet),
    write_ln(Bet).

bet(_, MaxBet, Lower, Higher, MaxBet) :- Lower > Higher.
bet(_, MaxBet, Lower, Higher, Bet) :- Bet is round(MaxBet * (Lower / (Lower + Higher))).

If you want to experiment different strategies, change the bet/5 predicate. main/0 will cut any choice-point left by bet/5, so only the first successful solution will be printed.

Acknowledgments: komet and garlic for algorithm inspiration, yy for the test script.

Cheers.
My Duff Entry by motty (4.00 / 1) #54 Wed Nov 22, 2006 at 04:33:53 PM EST
Is here

I'd intended to try different things but couldn't be arsed in the end. I also for some reason initially assumed that Sules divided into 100 cents, which they don't, otherwise we'd have been told they did.

Bah.

I amd itn ecaptiaghle of drinking sthis d dar - Dr T

Programming Fun Challenge 18: The good gambler | 54 comments (54 topical, 0 hidden) | Trackback