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 ]
I've written the last bit first by yicky yacky (4.00 / 1) #3 Mon Nov 06, 2006 at 03:14:13 AM EST

// ...
OpposingManager.push();
decorum -= shakeHands();
if (decorum < basicMinimum) {
    throw new HissyFit();
}
return SHEEPISHLY;


----
Vacuity abhors a vacuum.
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!

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

Nigerian associate will contact you shortly.


----
Vacuity abhors a vacuum.
[ Parent ]
Serious by yicky yacky (4.00 / 2) #8 Mon Nov 06, 2006 at 04:02:51 AM EST

1.) When you say, "Each round will consist of a separate run of your program which will be passed the following lines via the standard input", do you mean:

a.) passed via standard input during the run of the program (i.e. the program has to request and parse the info during runtime)?, or ...

b.) passed on the standard input during the shell call (i.e. passed as args to the program)?

I'm guessing the latter but clarification would be good.

2.) What would the four argument formats be? I'm guessing they're all unsigned integers ...

3.) I take it that source is a prerequisite.


----
Vacuity abhors a vacuum.
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 ]
Except that, by yicky yacky (2.00 / 0) #16 Mon Nov 06, 2006 at 08:45:58 AM EST

if you're gambling (as this algorithm is "doing"), huge and / or idiosyncratic outliers are a valid part of the game. I'd say stick with the mean or total. You're not being asked to maximize the cumulative yield with the minimal possible standard deviation; you're being asked to maximize the yield full-stop.

To put it another way: If I were bankrolling two gamblers and one came back with a million, having earned 10,000 a pop each go, and the other came back with two million, but having got nothing on ninety-six goes and sky-rocketing on four, I wouldn't care; I'm still loving the 2-million-gambler twice as much as the accountant.


----
Vacuity abhors a vacuum.
[ 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 ]
There is the by yicky yacky (4.00 / 1) #28 Mon Nov 06, 2006 at 01:16:57 PM EST

basis of a very quick and dirty test program here.

If anyone uses it, please read the comments in it first, especially the long comment before the main segment. USE AT YOUR OWN RISK. Dirty code. Very possibly buggy. Very definitely fragile. Not fit for any purpose. Etc., etc.


----
Vacuity abhors a vacuum.
[ 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 ]
As I understood it, by yicky yacky (2.00 / 0) #30 Mon Nov 06, 2006 at 01:42:27 PM EST

you couldn't bet zero or you'd get trapped in an infinite loop as next time you'd only be allowed to bet a maximum of (2 * 0 = 0)


----
Vacuity abhors a vacuum.
[ 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 ]
True by yicky yacky (2.00 / 0) #33 Mon Nov 06, 2006 at 01:54:00 PM EST

plus, as garlic says, it's in the rules, although I mis-interpreted that line. Gizza sec: I'll fix it.


----
Vacuity abhors a vacuum.
[ 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 ]
I know about shuufle, ta [nt] by yicky yacky (2.00 / 0) #41 Wed Nov 08, 2006 at 10:10:02 AM EST

----
Vacuity abhors a vacuum.
[ 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 ]
Hmmmm. Possibly. by yicky yacky (4.00 / 1) #43 Thu Nov 09, 2006 at 02:15:58 AM EST

But I interpreted this ...

... 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 loses it.

... to mean that the gambler loses in the event of a draw, hence the test based on face rank. I guess we need a TPD judgement to be sure.


----
Vacuity abhors a vacuum.
[ 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 ]
Coolio by yicky yacky (4.00 / 1) #46 Thu Nov 09, 2006 at 05:30:54 AM EST

On the contrary, sir; I'm suffering from a basic reading and comprehension skills shortage. I guess you are modelling the situation where each suit has itself a rank relative to the others, whereas I was channeling a Brucie bonus. You get nothing for a pair ...

Script fix0r3d, I think; the power of abstraction (and hulver's file renaming code).

Your way yields higher totals than mine. Yippee. Now I have to see if my top secret, shit-hot algorithm still holds ...


----
Vacuity abhors a vacuum.
[ 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 ]
I don't know by yicky yacky (4.00 / 1) #48 Tue Nov 21, 2006 at 01:58:32 AM EST

It could be to do with your shell (have you got a UTF-8 or UCS2 shell, perchance?) or the exact nature of what your test app spits out (VT control codes?), or any one of a number of factors. Bear in mind that the script has changed numerous times since it was first posted and it's completely unguaranteed beyond the system I wrote it for (i.e. mine, where it works fine).

I would note that, while doing that probably makes it compatible with some system which I haven't got access to, it's also inherently dangerous. Any test program which returned a string like "os.system('rm -Rdf ~/')" [or the windows equivalent] could screw up your whole day. This was also a weakness in the original script (although via a different mechanism), which is why it was changed. Your comment may help others, though, so cheers.


----
Vacuity abhors a vacuum.
[ 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 ]
Aha by yicky yacky (2.00 / 0) #50 Tue Nov 21, 2006 at 06:11:28 AM EST

That'll be the problem. The code expects ints, not floats (on the basis that you can't bid a float of a Sule, I believe, but I may have got that wrong also). When you eval the float, python recognises it as being a numerical value and interprets it as a python float type, which is then int-ified by the int() call. When you don't eval the float, the int() call operates directly on the string type returned by read(), so when it hits the decimal point, it'll throw something exception-ish like a TypeError or a ValueError because it's not expecting it. Because the exception's not caught, it breaks the script (which was semi-intentional in the original version). You could change the eval() call to a float() call and it should still work (and be safer).

Python's fussier than perl in many respects; it's not really a weakly-typed language as such, just dynamically-typed; once a variable's type has been decided, it's quite strongly fixed from that point forwards. Python doesn't have a 'taint mode' equivalent - at least not any more. It used to have a module called 'rexec' ("restricted execution"), but it was disabled as of version 2.3 for numerous reasons (not least of which is that taint modes aren't foolproof and are no real substitution for writing the code correctly) - but mainly because concurrency and new-style classes lead to all sorts of crafty exploits, which meant it was safer to disable it rather than have people over-depend on it.


----
Vacuity abhors a vacuum.
[ 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 ]
float() by yicky yacky (4.00 / 1) #52 Tue Nov 21, 2006 at 06:49:39 AM EST

float() takes a string, or any "number" and converts it to a float type. int() takes the same and converts it to an int type. The only difference at the input (arguments) end is that float() won't choke on the decimal point in an input string, whereas int() will. It'd essentially be doing the exact same thing as the eval() call but less open.


----
Vacuity abhors a vacuum.
[ 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



First Attempt by yicky yacky (4.00 / 1) #38 Mon Nov 06, 2006 at 02:46:08 PM EST
AKA The Race To The Bottom

#!/usr/bin/env python
import sys
if __name__ == "__main__":
    a = sys.argv
    if len(a) != 5:
        print "1"
        sys.exit(0)
    c = int(a[1]); m = int(a[2]); b = int(a[3]); l = int(a[4])
    t = b + l; p = float(b) / t; s  = p * c
    if s < 1: s = 1
    elif s > m: s = m
    else: s = int(round(s))
    print "%d" % s


----
Vacuity abhors a vacuum.
[ 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