## Is it possible to card count a blackjack computer?

The header picture is a five dollar blackjack machine in Las Vegas (at the Palazzo), and a very good game it is too. I spent quite a few hours playing it (basic strategy). I did see another version of the machine – at Monte Carlo and Mirage, and I actually prefer those machines as they seemed a little slicker, but that is purely a personal preference.

When playing the machine, the question I had was “There are all these people using phones whilst playing blackjack, what is to stop them running an app and card counting?

After looking at the rules, I realised how the casinos have this covered. The computer uses four packs of cards (so 208 cards), and shuffles after 80 cards have been dealt. If you know anything about physical blackjack you’ll know that penetration is around 75%. That is about 75% of the cards are dealt before the cards are shuffled. Although casinos usually use six or eight decks in their shoes, if they used four decks, they would deal about 156 cards before they shoe was shuffled.

The fact that they shuffle when round 38% (80*100)/208)) of the cards have been dealt effectively makes card counting irrelevant. At least, I think it does, I have not done the maths, but it certainly means that any card counting strategy is not as effective if 156 cards were dealt before a shuffle.

But you can’t blame the casinos. The machines fill a need. There are players that want to play blackjack for \$5 a hand, whereas all the tables (at least in many of the casinos on the Las Vegas strip) have a starting minimum of \$10. Presumably, it is not cost effective to open a physical table with a \$5 minimum and so a computer meets that need. At least it does if you don’t have to have somebody man it, which you would if you had to monitor for card counters.

So, whilst it is interesting to look at the card counting potential, it is also good that the casinos, even the higher class casinos, are willing to offer a \$5 blackjack game.

As an aside, if I was to offer one suggestion to the manufacturers, I would change the video a little. Not sure how many times I saw the same cocktail waitress with a try of the same drinks and how many times I saw the guy in the red suit (he’s there now, as is the cocktail waitress!) walk up to the bar, look around and then walk off. I saw these images hundreds of times (as they repeat every thirty seconds or so). It can’t be that hard to make the video more interesting?

As a further aside, you might be interested in a paper I wrote on blackjack a few years ago.

I also published this post on LinkedIn.

## My First Java Project

It’s been a while since I decided to use Java as my new programming language of choice. Since my last post I have been honing my Java skills, with my first java project.

I had a project I needed to do that is about analyzing academic papers, comparing them in various ways, sorting them, writing out reports etc.

My first instinct was to use PHP (which I learnt a few years ago – and I really like the language) but the only development environment I have is on a server. I could set up a development environment on my desktop, but it did not seem worth it for the times that I would use that environment in anger.

The other option was C++, but that went against what I was trying to do for this project, as you’ll understand if you read earlier posts in this project.

So, the obvious solution was to use Java.

As my first Java project, it seemed to have suitable complexity for a first time Java user, but allowing for the fact that I have a programming background. I suspect that the project would not be suitable for a complete newbie to programming.

The details of what the project has to deliver is not that important but the lessons learnt are important, as these are things that I can use in later, larger, projects. These included:

• Reading in a CSV (Comma Separated Variable) file. This is always a useful thing to be able to do. It’s one of those fall backs that is useful to have in your armoury as it makes accessing files such as spreadsheets and databases easy to do as they invariably have an option to save as a CSV file. Of course, it’s usually possible to access spreadsheets and databases directly (which is what I used to do under C++ using ODBC) but for this project I thought I would get to grips with CSV first. After some searching, I came across a package called CsvReader. It’s not the most basic package (which is a good thing), and it did have good reviews. I had some challenges installing it, but that was not to do with the package but the fact that this is the first time I have installed a Java package. Once I had sorted that out, it worked perfectly.
• Writing out a latex/PDF file. One of the things I wanted to do was produce a half decent looking report. My initial thought was to write out a text file and then use Word to manually format it. This, for many reasons, is not a good idea; not least of all as it would be labour intensive every time I produced a new version of the report. I like to think that I had a flash of inspiration (but perhaps it is the obvious thing to do) and I decided to write out a latex file that I would convert to PDF via a suitable editor (my editor of choice at the moment is TexStudio, although I have used WinEdt in the past). This seems to work pretty well and I can now produce nice looking reports, without having to worry too much about the look of the final document as Latex will handle this as long as I have some idea of the structure as I develop the program. Of course, the beauty is that the report is complete, once the program has been run, without any need for any other processing/formatting. In a future blog I’ll provide a few more details as to how I did this as a) I think it’s interesting and b) I am sure that there are better ways of doing things and I’d like to get some ideas for developing the system further.
• Writing files. An obvious thing I had to do when writing out latex files, was to learn out to write out files. As any Java programmer will know, this is very easy using the PrintWriter package.
• Sorting arrays. I had a need to sort an array on one of the fields. In fact (see below), this involved sorting an array of class instantiations. This was probably the most difficult thing I did when developing my first Java project, and it took a while before it came together. But following a few examples from the web, and I had this working pretty quickly. It certainly seems easier than C++, which always seemed complicated and involved having to have friends of classes. I’m sure that there are easier ways in C++ but I never really got my head around it.
• Classes and data. This is not really a Java thing and maybe I am totally wrong, but I quickly found that my data and member functions were making the class quite large, so I decided to have a class called (say) ‘Papers’ and another class called ‘PapersData’. The PapersData class simply holds all the data and the Papers class provides access to it, as well as providing all the other functionality. This leads to (at least in the way I do it) too many getters and setters, but it does separate the data/functions. But, the main reason I did this is because I wanted to hold different data types for my various objects and an ArrayList (or other array type objects) would not allow this. I am happy to be corrected but I was trying to recreate the struct (i.e. a class) type concept of C++. Anyhow, it seemed to work for what I wanted, but whether it would scale to larger projects is another matter.

The system I have ended up with, seems to work well. Whether it is scalable to larger projects remains to be seen, but it has certainly been a very good learning experience. I have doubts that if I was trying to learn C++, even with a good programmimg background, I would have progressed as fast as I have with Java.

No doubt, other people would pick up C++ faster than I would have done but, for me, Java is a lot easier to learn.

The other big bonus is the Eclipse IDE.  No doubt, I have only scratched the surface but the autocomplete (Ctrl/0) and the suggested error correction (Ctrl/1) are my new best friends!

So, as my first Java project, I think, has been a worth while exercise and I have learnt a great deal.

## Crowdfunding: A new model to fund research?

A few weeks ago I came across something called crowdfunding. I have known about crowdsourcing for a while, but crowdfunding had escapsed me.

I am not sure it is a good idea but I thought I would try it out (see my project here, it develops my project for football prediction or, for more general blogs on forecasting, see here).

Of course, it would be nice to get the project funded but it is also an experiment as, if crowd funding does take off, I want to be able to have some knowledge/experince of the medium.

The idea is that you get a crowd of people to fund a project by contributing small amounts in the hope that you can reach the goal required for you to carry out the project. In order to motivate people to contribute, you offer a series of rewards with the rewards getting better the more that is contributed.

The research community has recently started to show an interest in this model of rasing funds for research. It is still in the very early stages, but I believe that it will become a more pominent feature of the funding landscape in the coming months/years.

If you are interested, there has been some limited scientific publications on Crowdfunding. This is certainly not a complete list, but here are some publications I found via a quick search on Web of Knowledge.

• Finding philanthropy: Like it? Pay for it (link)
• Crowd-Funded Micro-Grants for Genomics and “Big Data”: An Actionable Idea Connecting Small (Artisan) Science, Infrastructure Science, and Citizen Philanthropy (link)
• Strapped for funding, medical researchers pitch to the crowd (vol 18, pg 1307, 2012) (link)
• Crowd-funding: transforming customers into investors through innovative service platforms (link)

If you are interested in crowd funding platforms, there are many listed on wikipedia.

## Free online access to Journal of the Operational Research Society in April 2013

Please don’t miss the opportunity to access Palgrave Macmillan journals free of charge during April 2013. I specifically mention the Journal of the Operational Research Society, as I am an Associate Editor of this journal. The official announcement is as follows:

From April 1-30, 2013 Palgrave Macmillan is offering FREE online access to all its journals, including current content and available online archives.

As a member of the Editorial Team for Journal of the Operational Research Society we wanted you to be aware of this promotion, as it is a great way of introducing the journal and extending its profile. We do hope you’ll share this email and spread the word to your colleagues and contacts!

## New Blog Theme

I am impressed with WordPress. It tends to do what it says on the tin and the range of plugins and themes you can get enable you to add almost any sort of functionality.

Yesterday I decided to bite the bullet and install another theme. Actually, installing a theme is very easy. It really is a case of downloading it, activating it, and then seeing how it looks. In fact, you can even do a live preview so that you can see what it looks like before you activate it.

The problems potentially start after you activate the new theme. The type of issues that you might have to resolve are things like re-installing (or more accurately replacing) your widgets. This is quite easy if you can recall what widgets you had previously (so check beforehand). If you have a text widget where you have written your own html, javascript etc. best make sure that that you copy that text before you activate the new theme.

The other issue you might have is if you have updated any WordPress PHP scripts to add increased functionality, fix errors, or just change small things to make the theme look slightly better. In fact, I try not to amend the PHP scripts for exactly these reasons, but sometimes you just have to, to get the features that you need.

I decided to install the WordPress Twenty Eleven theme.  The previous one I was using was JaS Personal Publisher. I was actually very happy with it but I just wanted a change, as well as getting used to installing themes so that I could do it more easily in the future.

The only real problem I had was the fact that on smaller devices (phones, ipads, when you make the browser window smaller), the side bar goes below the main display. Apparently this is a design feature (and I’ve worked in the IT industry long enough to know what this means!).

It took a while, but I eventually found a fix for this feature. In essence, you delete a few lines from the style.css file and this forces a horizontal scroll bar, rather than moving the sidebar downwards.

The only piece of advice, which I was not aware of before, is to create a child theme. This inherits everything (in the same way that inheritance works in Object Oriented programming) from the main theme but if you ever get an update, then your changes are not overwritten.

Once I had the basics up and running, it was a case of making sure that all the settings were correct, uploading some header pictures to replace the standard ones that are supplied. I have gone with a loosely travel theme, where the pictures are of modes of transport at the moment. Things like planes, trams, cars and even cable care. Well, transport is a big Operational Research issue, which is one my main research interests.

The final thing I added was a couple of plugins that I downloaded. One enables people to vote whether they like/dislike a particular post. The other enables readers to share the post to various social networking platforms such as facebook and twitter.

I do like the look of the new theme, but I don’t think that it is perfect and I am still on the look out for something that looks good and provides all the functionality that I think I need.

The search continues but, for now, I am very happy with the new look and functionality of my blog pages.

## Random Number Generation

We all know that computer generated random numbers are not really random at all, but just pseudo-random. And I know that is a lot of discussion about how best to generate random numbers.

To be honest, I have not taken much notice of this in all the programming that I have done but today I found out that it is important.

Without going into the (boring) details, I have been generating a random number that is either 1 or 2 – but I generate quite a few very quickly.

For anybody that is interested the code is something like

r = rand() % n +1 [where n is the range you are interested in]

The problem is, I was returning the same number every time. Only very occasionally did I get the odd difference.

If I increased the range (say generating numbers between 1 and 20), this made no difference (I always got the same number).

However, if I put in a delay between each call to rand(), this “solved” the problem, but this is not a good solution.

Doing some reading around the subject, I think it is to do with the low/high order bits when generating the random numbers.

But that does not help me generate a decent distribution when making very frequent calls to rand().

I seem to recall that there is a C++ class called RNG (Random Number Generator) available and I am sure that Numerical Recipes in C will have something to say on the issue, but I need to look into these.

## Hyper-heuristics: An Ongoing Research Idea

For the past few months a colleague and I have been putting a day aside every six weeks or so to work on a joint project. This is the first time I have programmed with somebody but its working out well. We each take responsibility for a C++ class and then plug everything together at the end of the day.

The first few days went very well and we got results that were close to the best known, but things have slowed down a bit recently and we have stood back and looked at exactly what we are trying to achieve. The programming today was about redesigning the software framework. We did not quite finish, but we made good progress.

The domain we are tackling is the examination timetabling. We chose this as the data is readily available, there has been a lot of work done in this area already and there are lots of results that we can compare against.
(In case you are interested, we are initially using the Carter datasets. There is more recent dataset known as the ITC (International Timetabling Competition) datasets which we might look at in the future.)

But, the main focus of the research is not to solve examination timetabling problems, but to investigate an idea we had about hyper-heuristics. We are not sure if it is going to work yet (that’s the idea of research!) but the outline idea is that we evolve sequences of add/delete heuristics, perhaps in a co-evolutionary environment. That may sound a bit woolly at the moment, and you’d be right as we are still very much in the planning phase. In essence, we are just developing a software development framework that will enable us to test a variety of hypotheses.

So, at the moment, work in progress and more later.

## MISTA Conference: Plenary Talk (Raymond Kwan)

Our second plenary talk took place this morning. Raymond Kwan, from The University of Leeds, gave a talk entitled “Case Studies of Successful Train Crew Scheduling.”
The talk was based on his spin out company (TrainTRACS) that markets software to UK train operators across the UK and is used to schedule train crews. As well as giving an overview of the problem, his talk discussed how complex the problem is and the methodologies that they use to solve it.
In the picture is Raymond Kwan (foreground) and Barry McCollum (session chair).

## Football Scheduling: News Story

The English football season has just started and, to coincide with the kick off, the Communications Office at The University of Nottingham offered to issue a press release about my work is this area.

This resulted in an interview on BBC Radio Nottingham (broadcast 8th Aug 2009) and a colleague, from another university, sending me a link (thanks Mike) that he had come across.
The story also contains a link to the University of Nottingham press release.

I have always found the following example interesting. I remember that it was Peter Ross who first showed me this during a presentation at a conferenec we were both attending.

The example demonstrates that an algorithm can act in an unexpected way when you make a very small change to the input data.

The example is drawn from bin packing. In this problem, you are given a number of items, all of which have a weight. Let’s assume that we have the following 33 items.

442, 252, 127, 106, 37, 10, 10, 252, 252, 127, 106, 37, 10, 9, 252, 252, 127, 85, 12, 10, 9, 252, 127, 106, 84, 12, 10, 252, 127, 106, 46, 12, 10

We are also given an infinite number of bins, each one having a certain capacity. Let’s assume that the capacity of our bins is 524.

The aim is to pack all 33 items into as few bins as possible.

How would you do it? What algorithm would you use?

One possible algorithm is as follows:

1) Sort the items into descending order of size, thus:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 46, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

2) Take each item in turn and place it into the first bin that will accommodate it. The bins are also considered in the order they were first used.
So, to start we have no bins available, so we open one. We take the first item (442) and place it in that bin. Now we take the next item (252). We cannot fit this into the bin we have just opened (as 442+252 > 524) so we open another bin.
The next item (252) will be placed in the second bin. The next item (252) will have to open a third bin.

… and so on.

If you apply this algorithm, you will get this solution

Bin 1: 442, 46, 12, 12, 12 = 524
Bin 2: 252, 252, 10, 10 = 524
Bin 3: 252, 252, 10, 10 = 524
Bin 4: 252, 252, 10, 10 = 524
Bin 5: 252, 127, 127, 9, 9 = 524
Bin 6: 127, 127, 127, 106, 37 = 524
Bin 7: 106, 106, 106, 85, 84, 37 = 524

You’ll notice that we have a solution that requires 7 bins and, moreoever, each bin is completely full. Therefore, we know we have found an optimal solution.

As an aside, what we have just done is used a heuristic (a rule of thumb). This one is known as Largest Fit, First Fit. We could come up with many more. For example, we could sort the pieces in different ways, we could consider all the open bins before deciding which one to use etc.

The question now arises, is the largest fit, first fit heuristic always the best heuristic to use for the bin packing problem?

Let’s see.

Take our list of sorted items again. That is:

442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9

But this time remove an item (say 46 – which has been removed from the list above).
We know that we can use seven bins to pack these items, and have 46 units left over.

So, let’s apply the largest fit, first fit heuristic and see what happens.

This is the result.

Bin 1: 442, 37, 37 = 516
Bin 2: 252, 252, 12 = 516
Bin 3: 252, 252, 12 = 516
Bin 4: 252, 252, 12 = 516
Bin 5: 252, 127, 127, 10 = 516
Bin 6: 127, 127, 127, 106, 10, 10, 10 = 517
Bin 7: 106, 106, 106, 85, 84, 10, 10, 9 = 516
Bin 8: 9 = 9

This is quite surprising (well, it is to me). We have removed an item, but had to use an extra bin.

Of course, we could develop another heuristic that only used 7 bins, but would that heuristic work well on other problem instances? Or, to put it another way, if you were presented with an instance of a problem you had not seen which heuristic would you use?

There is some work being done in an area termed hyper-heuristics (which I’ll blog more about in the future) which is trying to address problems such as those described above.

If you are interested in reading more about hyper-heuristics, you might like to visit my publications page (http://www.cs.nott.ac.uk/~gxk/gxk1/publications.html).

Good introductory articles are:

1. Cowling P., Kendall G., Soubeiga E.A Hyperheuristic Approach to Scheduling a Sales Summit. In LNCS 2079, Practice and Theory of Automated Timetabling III : Third International Conference, PATAT 2000, Konstanz, Germany, August 2000, selected papers (eds Burke E.K. and Erben W), Springer-Verlag, pp 176-190, ISBN : 3-540-42421-0
2. Burke E.K., Kendall G. and Soubeiga E. (2003) A Tabu-Search Hyper-Heuristic for Timetabling and Rostering. Journal of Heuristics , 9(6), 451-470, 2003
3. Burke E., Hart E., Kendall G., Newall J., Ross P. and Schulenburg S. (2003) Hyper-Heuristics: An Emerging Direction in Modern Search Technology. Handbook of Meta-Heuristics (Glover F., ed), pp 457 – 474, Kluwer