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.

Football Prediction: A decision to be made

Today I have been working on my research that is investigating if it is possible to predict the outcome of football matches. The measure I will eventually use, to see if the predictions can be considered successful, will include if it can make money at the bookmakers, if it it more successful than other tipsters etc.

One of the functions I have in my system is to be able to generate the league table for a given date. That is, taking into account the fixtures played to date, generate the league table for any point in the season.

I believe that my function is working correctly and today I was carrying out some tests to see if the league tables I generated were:

1. Correct at the end of the season. That is, taking into account every match played, is my input data correct and does my algorithm process that data correctly.
2. Does my algorithm, given a date, generate the correct table for that point in the season.

I initially thought that point 2 would be very time consuming to check but I found a very useful web site. http://www.statto.com is not only a very useful web site (for all sorts of reasons) but one of the facilities it offers is to generate a league table for a particular point in the season.

When doing my checks (and there are still a lot more to do), I have found some problems where my generated tables are not correct. This is almost certainly down to my inputting the results incorrectly, so I need to check all those.

However, my checks also highlighted another problem. Actually, I knew this was something that I needed to address but I had not really thought it through.

The problem arises when teams having points taken away. I knew that this happened and I had yet to include it in my system so I was expecting the tables not to match exactly.

However, I had assumed that the points were deducted at the start of the season but this does not seem to be the case. It appears that the points can be deducted at any time in the season.
This is not too much of an issue. It just makes the programming more complex than I had hoped.

The real issue is what do I do when a team has had points deducted?

Let me give you an example. A team has won 3 games and drawn 2. That means that they have received 11 points (you get 3 points for a win and 1 point or a draw). But, if they have had 10 points deducted then they will only have 1 point. This obviously affects their league position. If I am using the league position as one of the contributory factors in my predictive model, is this fair - or should I ignore the points deduction for the purposes of prediction?
On the other hand, their league position, with the points deduction, may affect the way they play, and could be a factor in the prediction.

I'm not quite sure what I am going to do yet.

Football (Soccer) Prediction: Data Collection (#002)

If you have read previous versions of this blog you'll know that a) I have an interest in trying to predict football (soccer) matches and b) I am currently developing a system (as a research project) that I hope to get up and running in the next month or so.

What kept me busy for a lot of last season was collecting the data.

Fixtures
The fixtures were easy to collect, being readily available from various sources. As my basic reference guide I used the Sky Sports Yearbook as this is a piece of published work that will be available to future generations. I could have used may of the web sites that are available but as a scientist we don't really like to rely on web sites as they may not stand the test of time. The fact that web sites are not peer reviewed are another factor we also have to consider.

Results
The results are also easy to collect as they are a matter of public record and are reported in the media and, from a research point of view, we can validate them for years to come (e.g. newspapers, next seasons Sky Sports Yearbook etc.)

Bookmakers Odds
One of the other things I wanted to collect was the bookmakers odds. This proved a lot more challenging. There are a couple of problems. As far as I am aware they are not a matter of public record (at least that stand the test of time). Or, to put it another way, can you go and verify what the odds were for a given match at a given time - just by accessing publicly available information? Importantly, if two (or more) people are independently given the same task will they come back with the same answer? And, is it the correct answer anyway?
The second problem is that odds change over time anyway, with the weight of money that has been bet.

Anyway, over the course of last season, I made regular visits to the bookmakers to pick up their fixed odd coupons and I filed them away as evidence of the odds I was using.

Since carrying out the data collection (particularly the odds) I have discovered a couple of interesting other sources. I believe that the Racing Post (which, importantly, is also published as a daily paper, so is a matter of public record) publishes the best odds available on the fixtures for a given day.
I was also pointed to a web site recently (http://www.football-data.co.uk). This is a very good web site that not only has a lot of information but also has at least seven seasons worth of fixtures data including results and odds information from a selection of bookmakers.

I have checked the odds I collected last season against the ones on this web site and they match up, which is encouraging.
It also provides me with more than just last season to carry out initial testing before I use the system in anger on this season.

The downside of the http://www.football-data.co.uk web site is two-fold.

1. I don't think they will make their data available until a few hours before the kick off time. This might be a problem for the system that I am developing.
2. The data is still a web site so, from a research point of view, I should not really cite it as the web site may not be available in 1/10/100 years time.

Please don't take this as a criticism of the web site. They have done (and are doing) a fantastic job of collating all this data and, for this particular research project, will save me HOURS of data collection and data entry time.

Football (Soccer) Prediction: Development Framework (#001)

As the new football (soccer in the USA) season approaches I am trying to get a football prediction system up and running. I think I will struggle to get it ready for the start of the new season (which starts Aug 7th) but that is not so important as this is mostly a research project. In any case, the system I have in mind will take a few weeks before it is usable as I need to get some results posted for the prediction system to work on.

I did a quick check on how much time I have spent so far on the programming. As a rough estimate, I think it is about 100 hours, mostly (if not all) at weekends. I still have a lot to do but I almost have the "football framework" that I need. That is, I can read in the data that I have been collecting, generate a league table for a given date in the season and collate various other statistics that I will eventually need. I also have various data structures that I will "pass around" the prediction part of the system.

I reckon that I need about another 20 hours and then I'll have the framework completed. Then I can start to work on the prediction parts of the system.

One thing that I need to implement is an Artificial Neural Network (ANN). I have one from another project I worked on (stock market forecasting) but I want to re-engineer it. At the moment the ANN is only a feed forward network as it was used in an evolutionary setting. That is, the predictions were evolved rather than a more traditional training mechanism.
One thing lacking in my ANN class (I program in C++) is a back propagation training (BP) mechanism So, apart from tidying up the code, I also want to implement a back propagation method, as this seems one potential way to carry out the prediction.

So I have my work cut out over the coming weeks, but I hope that it will be interesting and, you never know, it might just work.

Football Prediction: Follow up

Whilst searching around the net looking for relevant resources for my plan to predict football matches, I came across The Sports Exchange. It looks like a relatively new web site, but seems very nice.

I posted a comment in their blog (about football pools prediction), and received a number of replies. The blog entry can be seen here.

Predicting the Results of Football Matches

I have recently become interested in trying to predict the results of football matches.

The interest grew from wondering what else I could use the data for, that I had collected for generating football fixtures (see JORS paper). The data included the travel distances between all the teams in each division. I also maintained the fixtures that were actually played over the Christmas/New Year period so that I could compare the fixtures I generated against those that were actually played. Needless to say, it took a long time to collect all this data.

As I had gone to all the time and trouble of collecting the data I want to maximise its usage, so I began to look for other uses that I could put it to, and prediction seemed an obvious challenge.

With this in mind, for most of last season I collected additional data that I think might be important in predicting football matches. For example, I have been updating all the scores as each fixture was played. I have also been keeping a record of the odds that bookmakers were offering. Just collecting this data was a large data collection exercise in itself and I certainly did not get the odds on every fixture, but I have enough to be going on with.

I'm not totally sure what I am going to do with this data yet but I know if I don't collect some of it as and when it is available, it becomes almost impossible (or at least a lot more difficult) to collect.

I have started programming some support functions. For example, given a date and a set of results I can generate the relevant league table for that point in the season.

My ultimate goal is to develop a prediction model and test out how good it is on the 2008-2009 season and, if I find a good model I will try and predict the fixtures for the 2009-2010 season before the matches are actually played.

The new season starts quite soon (kick off is 8th August 2009, but there is one match scheduled on the 7th August 2009).

If I am going to have ever chance of testing the prediction model over the coming season, I need to get programming!

Horse Race Prediction with Neural Networks

I was sorting through some old papers recently and I came across my undergraduate final year dissertation. I recall that it started as a project about genetic algorithms but quickly turned into a project that used neural networks to predict the outcome of horse races.

I trained a back propagation network and used the final network to predict the outcome of (selected) races that the network had not been trained on. One of the biggest challenges was finding suitable data. I was lucky enough that a couple of companies (Timeform and Raceform - thank you) sent me their databases which made the data collection side of things a lot easier than it might have been.

One item that was missing from both datasets were the starting prices. Due to this I could not really judge if the predictions would result in a profit. However I did a few calculations and assumed that the average odds were either 2/1 (3.00), evens (2.00) or 1/2 (1.50) (see note, for a description of the odds calculation). I also made an assumption that the odds would also capture any tax that had to be paid.
Using these figures it was possible to make a profit even when the average odds were as low as 1/2 (1.50).

I wonder if it really is possible to develop a prediction system that can make a profit from backing horses? Although my undergraduate dissertation suggested that it is, it would need a lot more development, testing and analysis.
I would also like to investigate other methodologies, in addition to neural networks - but that needs a little more thinking about.

Of course, it's not possible to predict the result of every race but you only need to predict enough races, at good enough odds, to show a profit.

One of the issues when betting is the amount of tax you have to pay but with new methods of betting (such as spread betting and betting exchanges) becoming ever more popular, perhaps this might not be so much of an issue.
I know that betting exchanges (such as betfair) still charge a tax but at least you are betting against other punters and are not limited by the odds being offered by the bookmakers.

I'll keep this one of the back burner for a while, but I think there is some potential in exploring it further.

Note on odds: I have shown the odds in two ways. The UK way of expressing odds is (for example) 2/1 which means you have to place a stake of 1 unit to win 2 units. You also receive back your stake. So if you bet 1 unit at odds of 2/1, and the horse wins you receive 3 units back (the 2 units you won + your 1 unit stake = 3 units; less any tax - but let's ignore that for the purpose of this discussion).
Another way of expressing odds is the decimal format (which I have shown in brackets). This is used, for example, on betfair. This says how much you will receive for 1 unit, including getting your stake back. So if you bet 1 unit at odds of 3.00, and the horse wins, you get 3 units back.
So the two ways are just the same way of expressing the same thing, but you might be more used to seeing one system over another, depending on where you live/bet.