Testing out roulette strategies with kdb+/q

picjumbo.com, licensed under Creative Commons 0

Unless you’re very into physics (and plan to model out a whole lot of interactions), roulette is a simple game. You place a bet, a random number comes out and then you either win or lose. I came upon the idea of analyzing different betting strategies in Building Skills in Object-Oriented Design and have been having nightmares ever since^M^M thought implementing the meat of it could be a fun exercise to do in q.

The plan was simple: build the table which gives out random numbers between 0–36, store the color information somewhere easy to access, throw the bet history into a table and finish it off by appointing every strategy a short function.

I set out to compare the three following strategies:

• Naïve
• Martingale
• 1326 Sequence

Preliminaries and Utilities

The first thing we did was to try to simulate the roulette table:

spin:{first 1?37}
colr:"grbrbrbrbrbbrbrbrbrrbrbrbrbrbbrbrbrbr"
play_r:{2*x*"r"=colr spin[]} 

play_r[x] assumes you bet on “Red” and gives you the outcome depending on your bet amount: either 2x if you win or 0 if you lose. Assuming the bet was “Red” can be justified as 1:2 bets have the least house edge and “Red” is no different than “Black”, “Even” or “Odd” (We abuse this later on). Keeping the color information turned out to be extremely simple as our roulette table was putting out integers. We represented every color here (green, red, black) with its initial. Declaring the history structure was also quite straightforward with kdb+’s table definition:

hist:([]bet:();out:();player:())

Since we’re aiming to do numerical analysis, we should write a handy trial function that takes in a strategy and repeatedly runs simulations. As we’re going to iterate on the implementations, a trial length of 1000 and a trial size of 10 for each strategy should suffice:

ltr:1000;ntr:10;
trial:{do[ntr;y:y+1;do[ltr;`hist insert(s,play_r[s:x[]],y)]]}

Here, do[n;ex] is a for-loop that repeats the given expressions for n times. We take the strategy function x , and feed its output to play_r to generate the outcome of the bet, which we then insert into the database. The functions can freely look into the database to pick out their next moves. Since the path is open now, we can start implementing the strategies.

Strategies

Naïve

This one is extremely simple to explain and implement: it always bets 1. We only need a function returning 1, ie nv:{1} . (Ideally, we should inline it when giving this function to trial because looking 3 lines up to see the definition isn’t really worth the hassle. )

Martingale

In this strategy, we start by betting 1 and doubling our bet every time we lose. If we win, we start again at 1. This strategy guarantees every win carries us forward 1, regardless of how many losses we have had before.

In implementation, we should take a look at the last outcome and play 1 if the outcome is positive and double the last bet if the outcome is zero.

mrtg:{h:last hist;$[0=h`out;2*h`bet;1]}

We’re using the ` shorthand of accessing dictionary records here. ( last hist returns a dictionary (as the last row) with the same keys as hist ) The $[q;x;y] can be recognized as the ternary operator in other languages (with added syntax sugar for more cases).

Martingale with Ceiling

Unfortunately, in real life roulette tables tend to have upper limits. Assuming the upper limit to be 200$, we can define this variation using the max verb | . In the simulation, we’ll consider both variations but this one will be more realistic.

mrtg_c:{200|mrtg[]}

1326

This is an interesting strategy which depends on how many times in a row you won before. After one win you play 3, after two you play 2, after three you play 6. If you win the fourth, you reset back to 1.

Naively, we might need to count back the wins in the previous four games; but a much more simpler way to determine the next bet can be derived solely from the last outcome: After the first win the outcome is 2, the second 6 and the third 4. All other outcomes (0, 12) lead us to play 1. So we can define this with a simple cond :

strat:{$[2=x:last hist.out;3;6=x;2;4=x;6;1]}

hist.out retrieves all the outcome values for us in which we use the last one (an alternative way to obtain this could be (last hist)`out ). We assign the value to x for easy access and carry on with the cond .

Complexity Issues

Up until now, we didn’t care much about complexity or the right way of doing things. The idiomatic way of doing this analysis would be by generating a sequence of roulette outcomes and reducing it with the strategies. Also the way we are now doing this has a huge fault: in q table lookups are in linear time, which increases our complexity to quadratic. In most other languages we could mitigate this by declaring a variable above the functions’ scope and modifying it, but q does not allow it. When you try to modify an outside value in a q function, you are greeted with a rather terse error:

t:12
{t:t+1;t}[] / prints '2018.04.27T12:54:02.627 t

However, we can do simple workaround (which I borrowed from Reason’s mutable values): Dicts and tables are mutable inside functions (remember how we insert into hist in our trial function), so wrapping our value in a dict should work out fine

val:(enlist `t)!(enlist 12) / single valued dicts are quite verbose
/ mostly because ! expects both arguments to be lists
{val[`t]:1+val`t}[]
val`t / prints 13

In this spirit, we define a “latest value” dict, and a helper function to reset it between players

lst:`out`bet`ply!1 1 0;rst:{lst[`out`bet`ply]:1 1,1+lst`ply}

Now we modify play_r to insert the relevant values and the strategies to look up from lst

play_r:{lst[`out]:2*(lst[`bet]:x)*18>first 1?37;lst`out}
strat:{$[2=x:lst`out;3;6=x;2;4=x;6;1]}
mrtg:{$[0=lst`out;2*lst`bet;1]}
mrtg_c:{$[0=lst`out;200&2*lst`bet;1]}

Also note that we’ve swapped out the spin and colr functions with 18>first 1?37 , for a simple 18/37 chance of getting a 1 (win). Now we run the trials with

trial'[({1};strat;mrtg;mrtg_c)]

Data Analysis

Now that we have all the data we need, we should probably consider the net gains from each round. We can get that with

hist.out-hist.bet

However, the result will be a long list of length 4*ltr*ntr . To make sense of it, we should keep each trial in its own row. We can reshape the list by doing

(0N,ltr)#hist.out-hist.bet

A reasonable metric for comparing the strategies would be the average loss/win for each trial. We can obtain the end results of each trial by summing each row. Thanks to q, we can apply sum for each row using the ' adverb:

(sum')(0N,ltr)#hist.out-hist.bet

Now we’re left with a 4*ntr-long list with the final results of each trial. If we reshape it with four rows, every row would have the final results of their corresponding strategy, which we could then average over:

(avg')(4,ntr)#(sum')(0N,ltr)#hist.out-hist.bet

And voila! We have our results. In my case, they were like this:

-248.86 -558.37 4853.9 -1661.49

for naive, 1326, martingale and martingale with ceiling respectively. There is no doubt that the martingale strategy is superior, but the existence of table limits sets it back pretty hard. My personal favorite strategy of enjoying my “free” drinks while playing red every once in a while is quite preferable in a realistic setting. That’s nice to know.

As the code snippets above might prove hard to follow, here’s what the whole thing looks like in the end:

lst:`out`bet`ply!1 1 0;rst:{lst[`out`bet`ply]:1 1,1+lst`ply}
play_r:{lst[`out]:2*(lst[`bet]:x)*18>first 1?37;lst`out}
strat:{$[2=x:lst`out;3;6=x;2;4=x;6;1]}
mrtg:{$[0=lst`out;2*lst`bet;1]}
mrtg_c:{$[0=lst`out;200&2*lst`bet;1]}                                            hist:([]bet:();out:();player:())
 
ltr:10000;ntr:100;
trial:{do[ntr;rst[];do[ltr;`hist insert(s,play_r[s:x[]],lst`ply)]]}
\t trial'[({1};strat;mrtg;mrtg_c)]
 
(avg')(4,ntr)#(sum')(0N,ltr)#hist.out-hist.bet

Here, I ran 100 trials with length 10000, and used the \t macro to track the time of calculations. On my laptop with a i7 7600-U (utilizing a single core due to my free license), the whole thing took about 16 seconds.

Possible Future Expansions

• As I noted, this imperative way of doing things does not sit well with me. We might have increased performance if we construct the strategies as reducers over roulette outcomes.
• Creating a complete roulette application seems like it could be fun, and also a nice excuse for learning Reason
• Trying this same problem in a lower-level language could be interesting. It can also help us compare it to q for performance and semantics in this context (simulation analysis)